Exhaustive search methods for CNS polynomials (Q1022357)

A polynomial \(P(x) \in \mathbb{Z}[x]\) defines a canonical number system (CNS) if every element of \(\mathbb{Z}[x]/P(x)\mathbb{Z}[x]\) has a finite representation of the form \(\sum_{j=0}^k d_j x^j\), with \(d_j \in \{0,1,\ldots,|P(0)|-1\}\). It is well known that every CNS-polynomial is expansive, i.e., all its roots must lie outside the unit circle. The authors present a method for finding all expanding polynomials (with integer coefficients) with given degree and given constant term. The method is based on the power series representation of \(P(x)/P^*(x)\), where \(P^*(x)\) denotes the reciprocal polynomial of \(P(x)\). A focus is put on polynomials with constant term 2, which means that the digit set is \(\{0,1\}\). Up to degree 8, all CNS polynomials with constant term 2 are listed in [the second author, Ann. Univ. Sci. Budap. Rolando Eötvös, Sect. Comput. 20, 195--206 (2001; Zbl 0988.11002)]. Here, the CNS polynomials of degrees 9, 10, 11 with constant term 2 are given, as well as the number of expanding polynomials and CNS polynomials for small degrees and small constant terms. The authors also define semi-CNS polynomials as those \(P(x) \in \mathbb{Z}[x]\) where the finite expansions of the form \(\sum_{j=0}^k d_j x^j\), \(d_j \in \{0,1,\ldots,|P(0)|-1\}\), form an additive semigroup in \(\mathbb{Z}[x]/P(x)\mathbb{Z}[x]\). It should be noted that this property is called positive finiteness in [\textit{S. Akiyama}, Positive finiteness of number systems. Number theory. Tradition and modernization. Papers from the 3rd China-Japan seminar on number theory, Xi'an, China, February 12--16, 2004. New York, NY: Springer. Dev. Math. 15, 1--10 (2006; Zbl 1211.11011)]. Akiyama proved that all irreducible semi-CNS polynomials are of the form given in Theorem 3.4, and his proof can be easily adapted to reducible polynomials. Therefore, Theorem 3.4 gives all semi-CNS polynomials, which means that there are exactly \(\binom{n+k-3}{k-2}\) of them with degree \(n\) and constant term \(-k\).