Non-expansive matrix number systems with bases similar to certain Jordan blocks (Q6144388)

Let \(M\) be a fixed \(n\times n\) integer matrix and \(\mathcal{D}\) be a finite subset of \(\mathbb{Z}^{n}\). If we can write an element of \(\mathbb{Z}^{n}\) in the form \(v =\sum_{i=0}^{k}M^{i}a_{i}\) for some \(a_{i}\in \mathcal{D}\) we say that \(v\) has an \((M,\mathcal{D})\)-representation (we shall assume that \(a_{k}\neq 0\) when \(v\neq 0\)). We call \((M,\mathcal{D})\) a ``full number system'' if every \(v\in \mathbb{Z}^{n}\) has such a representation and we call \( (M,\mathcal{D})\) a ``canonical number system'' if additionally this representation is always unique. Simple arguments show that for a canonical number system \( M \) must be nonsingular with all its eigenvalues lying on the unit circle; by a well-known theorem of Kronecker this implies that all eigenvalues of \(M\) are roots of unity. In this paper the authors consider the special case where \(M\) is a single Jordan block \(J_{n}\) with eigenvalue \(1\). For \(n=2\) they give a complete description of the sets \(\mathcal{D}\) of size \(2\) for which \((J_{2},\mathcal{ D)}\) is a full number system. They also study the computational problem of representing \((0,0)^{T}\) when \(\mathcal{D}:=\{(0,1)^{T},(0,-1)^{T}\}\) and show that the underlying language is not context-free but can be recognized by a Turing machine with memory logarithmic in the size of the input. For \(n\geq 3\) they show that there exists a set \(\mathcal{D}\) of size \(n\) such that \((J_{n},\mathcal{D})\) is a full number system but no smaller set of digits will work.