BinSYS
Project

Detailed mathematical description

Let L be a lattice in *R*^{k},
M : L® L be a
linear operator such that det(M) ¹
0 and let D be a finite subset of
L
containing 0.

**Definition****.**
The triple (L, M, D) is called a number system (or having
the unique representation property) if every element
x of L has a unique,
finite representation of the form

_{},

where d_{i} ÎD
and *l*Î *N*. The operator M
is called the base or radix,
D is the digit set.

Clearly,
both L and ML are abelian
groups under addition. The order of the factor
group L/ML is t
= |det(M)|. Let A_{j} (j=1,…t) denote the cosets of
this group. If two elements
are in the
same residue class then we
say that they are congruent
modulo M. The following theorem gives a necessary condition of having the
unique representation property.

**Theorem** 1. If (L, M, D) is a number system then

- D must be a full residue system modulo M
- M must be expansive (i.e. for all the eigenvalues l of M the inequality |l| > 1 holds)
- det(I - M) ¹ ±1.

It is known that in
general these condition are not
sufficient. Since basis transformations of L do not change the unique
represenation property, therefore the number
system concept can be examined without loss of
generality in the cubic lattice
*Z*^{k}. In the following let
t = |det(M)|
= 2, so we consider the generalized
binary number expansions.

Let (Z^{k}, M, D) be a radix system having the
necessary conditions in Theorem 1 with
|det(M)|
= 2 and let e_{1} =
(1,0,…0)^{T}. It is easy
to see that
(Z^{k}, M, D) is a number
system if and only if
M is similar to the Frobenius (companion) matrix C_{M} of M and the
system (Z^{k}, C_{M},
D={0,e_{1}}) is a number
system. Therefore it is enough to
examine the linear operators with characteristic polynomial

c_{M}(x) = x^{k} +
c_{k-1}x^{k-1} + … + c_{0}, where
c_{0} = 2.

The aim
of the project is to compute all
the monic, expanding polynomials in Z[x] for
dimensions 3,…,10,11. After
determining these polynomials it is another job to
prove exactly the number system
property of their Frobenius matrix with the
digit set D={0,e_{1}}.

The similarity
of two linear
operators A, B Î Z^{k}^{´k}
with the same characteristic polynomial c(x) is closely related to the
class number od the ring Z[q]/c . In particular, if the class
number of Z[q] is equal to 1, then
the two operators are similar.