Exhaustive search methods for CNS polynomials
type: Item
instance of: scholarly article
title: Exhaustive search methods for CNS polynomials
zbMATH Open document ID: 1191.11004
author: J. Martínez
published in: Monatshefte für Mathematik
publication date: 2009-06-22T00:00:00Z
review text: 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 const…
reviewed by: Wolfgang Steiner
Mathematics Subject Classification ID: 11A63
zbMATH DE Number: 5567003
zbMATH Keywords: canonical number system
zbMATH Keywords: expansive polynomial
MaRDI profile type: Publication
full work available at URL: s00605-008-0005-y
OpenAlex ID: W2010798424
cites work: Cubic CNS polynomials, notes on a conjecture of W. J. Gilbert
cites work: Generalized radix representations and dynamical systems. I
cites work: On canonical number systems
cites work: New criteria for canonical number systems
cites work: Binary number systems for \(\mathbb Z^{k}\)
cites work: Pisot and Salem Numbers in Intervals of the Real Line
cites work: Q4432127
cites work: Q3150807
cites work: Q3428789
cites work: Fonctions méromorphes dans le cercle-unité et leurs séries de Taylor
cites work: Étude de certaines fonctions méromorphes bornées sur le cercle unité. Application à un ensemble fermé d'entiers algébriques
cites work: Radix representations of quadratic fields
cites work: Canonical number systems in imaginary quadratic fields
cites work: Q4166803
cites work: Canonical number systems in algebraic number fields
cites work: Q4537883
cites work: Number expansions in lattices
cites work: A Machine Method for Solving Polynomial Equations
cites work: Q5514782
cites work: On the characterization of canonical number systems
DOI: 10.1007/S00605-008-0005-Y
description: scientific article; zbMATH DE number 5567003