BinSYS Project

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.