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,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₁}) is a number system. Therefore it is enough to examine the linear operators with characteristic polynomial

c_M(x) = x^k + c_k-1x^k-1 + … + c₀, where c₀ = 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₁}.

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.