BinSYS
Project
Eotvos Lorand University, Faculty of Informatics,
Department of Computer Algebra
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_{k1}x^{k1} + … + 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.
Visit the project's homepage hosted by ELTE (Eötvös Loránd
University).