BinSYS
Project
Eotvos Lorand University, Faculty of Informatics,
Department of Computer Algebra
Detailed mathematical description
Let L be a lattice in Rk,
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 di Î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 Aj (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
Zk. In the following let
t = |det(M)|
= 2, so we consider the generalized
binary number expansions.
Let (Zk, M, D) be a radix system having the
necessary conditions in Theorem 1 with
|det(M)|
= 2 and let e1 =
(1,0,…0)T. It is easy
to see that
(Zk, M, D) is a number
system if and only if
M is similar to the Frobenius (companion) matrix CM of M and the
system (Zk, CM,
D={0,e1}) is a number
system. Therefore it is enough to
examine the linear operators with characteristic polynomial
cM(x) = xk +
ck-1xk-1 + … + c0, where
c0 = 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,e1}.
The similarity
of two linear
operators A, B Î Zk´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).