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

 

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).

 



Home | My Account | Message Boards


Copyright © 2017 SZTAKI Desktop Grid