Finite and periodic orbits of shift radix systems
Journal de Théorie des Nombres de Bordeaux, Tome 22 (2010) no. 2, pp. 421-448.

Pour r=(r 0 ,...,r d-1 ) d , nous définissons la fonction

τr:dd,z=(z0,...,zd-1)(z1,...,zd-1,-rz),

rz est le produit scalaire des vecteurs r et z. Si chaque orbite de τ r se termine par 0, nous dirons que τ r est un shift radix system. Il est bien connu que chaque orbite de τ r est ultimement périodique si le polynôme t d +r d-1 t d-1 ++r 0 associé à r est contractant. D’autre part, si ce polynôme a au moins une racine en dehors du disque unité, il existe des vecteurs initiaux qui conduisent à des orbites non-bornées. Le présent article considère les cas restants pour les propriétés de périodicité des applications τ r pour des vecteurs r associés à des polynômes dont les racines ont un module supérieur ou égal à un, avec égalité dans au moins un cas. Nous montrons que pour une large classe de vecteurs r appartenant à la famille précédente, l’ultime périodicité des orbites est équivalente au fait que τ s est un shift radix system ou a une autre structure prescrite d’orbite pour un certain paramètre s dépendant de r. Ces résultats sont combinés avec de nouveaux résultats algorithmiques dans le but de caractériser les vecteurs r de la classe précédente qui donnent des orbites ultimement périodiques pour chaque valeur initiale. En particulier, nous donnons la description de ces vecteurs r pour le cas d=3. Cela conduit à des ensembles qui semblent avoir une structure très compliquée.

For r=(r 0 ,...,r d-1 ) d define the function

τr:dd,z=(z0,...,zd-1)(z1,...,zd-1,-rz),

where rz is the scalar product of the vectors r and z. If each orbit of τ r ends up at 0, we call τ r a shift radix system. It is a well-known fact that each orbit of τ r ends up periodically if the polynomial t d +r d-1 t d-1 ++r 0 associated to r is contractive. On the other hand, whenever this polynomial has at least one root outside the unit disc, there exist starting vectors that give rise to unbounded orbits. The present paper deals with the remaining situations of periodicity properties of the mappings τ r for vectors r associated to polynomials whose roots have modulus less than or equal to one with equality in at least one case. We show that for a large class of vectors r belonging to the above class the ultimate periodicity of the orbits of τ r is equivalent to the fact that τ s is a shift radix system or has another prescribed orbit structure for a certain parameter s related to r. These results are combined with new algorithmic results in order to characterize vectors r of the above class that give rise to ultimately periodic orbits of τ r for each starting value. In particular, we work out the description of these vectors r for the case d=3. This leads to sets which seem to have a very intricate structure.

Reçu le :
Publié le :
DOI : https://doi.org/10.5802/jtnb.725
Classification : 11A63
Mots clés : Contractive polynomial, shift radix system, periodic orbit
@article{JTNB_2010__22_2_421_0,
     author = {Peter Kirschenhofer and Attila Peth\H{o} and Paul Surer and J\"org Thuswaldner},
     title = {Finite and periodic orbits of shift radix systems},
     journal = {Journal de Th\'eorie des Nombres de Bordeaux},
     pages = {421--448},
     publisher = {Universit\'e Bordeaux 1},
     volume = {22},
     number = {2},
     year = {2010},
     doi = {10.5802/jtnb.725},
     mrnumber = {2769072},
     zbl = {1223.11012},
     language = {en},
     url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.725/}
}
Peter Kirschenhofer; Attila Pethő; Paul Surer; Jörg Thuswaldner. Finite and periodic orbits of shift radix systems. Journal de Théorie des Nombres de Bordeaux, Tome 22 (2010) no. 2, pp. 421-448. doi : 10.5802/jtnb.725. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.725/

[1] S. Akiyama, T. Borbély, H. Brunotte, A. Pethő, and J. M. Thuswaldner, Generalized radix representations and dynamical systems. I. Acta Math. Hungar. 108 (2005), 207–238. | Zbl 1110.11003

[2] S. Akiyama, H. Brunotte, A. Pethő, and W. Steiner, Remarks on a conjecture on certain integer sequences. Period. Math. Hungar. 52 (2006), 1–17. | Zbl 1121.11014

[3] S. Akiyama, H. Brunotte, A. Pethő, and W. Steiner, Periodicity of certain piecewise affine planar maps. Tsukuba J. Math. 32 (2008), 197–251. | MR 2433023 | Zbl pre05347943

[4] S. Akiyama, H. Brunotte, A. Pethő, and J. M. Thuswaldner, Generalized radix representations and dynamical systems. II. Acta Arith. 121 (2006), 21–61. | MR 2216302 | Zbl 1142.11055

[5] S. Akiyama, C. Frougny, and J. Sakarovitch, Powers of rationals modulo 1 and rational base number systems. Israel J. Math. 168 (2008), 53–91. | MR 2448050 | Zbl pre05508715

[6] D. W. Boyd, The beta expansion for Salem numbers. In Organic mathematics (Burnaby, BC, 1995), vol. 20 of CMS Conf. Proc. Amer. Math. Soc., Providence, RI, 1997, 117–131. | MR 1483916 | Zbl 1053.11536

[7] H. Brunotte, On trinomial bases of radix representations of algebraic integers. Acta Sci. Math. (Szeged) 67 (2001), 521–527. | MR 1876451 | Zbl 0996.11067

[8] A. T. Fam, The volume of the coefficient space stability domain of monic polynomials. Proc. IEEE Int. Symp. Circuits and Systems 2 (1989), 1780–1783.

[9] A. T. Fam and J. S. Meditch, A canonical parameter space for linear systems design. IEEE Trans. Autom. Control 23 (1978), 454–458. | MR 528928 | Zbl 0377.93021

[10] C. Frougny and B. Solomyak, Finite beta-expansions. Ergodic Theory Dynam. Systems 12 (1992), 713–723. | MR 1200339 | Zbl 0814.68065

[11] A. Huszti, K. Scheicher, P. Surer, and J. M. Thuswaldner, Three-dimensional symmetric shift radix systems. Acta Arith. 129 (2007), 147–166. | MR 2342432 | Zbl 1143.11006

[12] P. Kirschenhofer, A. Pethő, and J. M. Thuswaldner, On a family of three term nonlinear integer recurrences. Int. J. Number Theory 4 (2008), 135–146. | MR 2387921 | Zbl pre05275149

[13] E. Lehmer, On the magnitude of the coefficients of the cyclotomic polynomial. Bull. Amer. Math. Soc. 42 (1936), 389–392. | MR 1563307

[14] J. Lowenstein, S. Hatjispyros, and F. Vivaldi, Quasi-periodicity, global stability and scaling in a model of Hamiltonian round-off. Chaos 7 (1997), 49–66. | MR 1439807 | Zbl 0933.37059

[15] A. Pethő, On a polynomial transformation and its application to the construction of a public key cryptosystem. In Computational number theory (Debrecen, 1989), de Gruyter, Berlin, 1991, 31–43. | MR 1151853 | Zbl 0733.94014

[16] A. Pethő, On the boundary of the closure of the set of contractive polynomials. Integers 9 (2009), 311 – 325. | MR 2534915 | Zbl pre05617057

[17] K. Schmidt, On periodic expansions of Pisot numbers and Salem numbers. Bull. London Math. Soc. 12 (1980), 269–278. | MR 576976 | Zbl 0494.10040

[18] I. Schur, Über Potenzreihen, die im Innern des Einheitskreises beschränkt sind. II. J. reine und angew. Math 148 (1918), 122–145.

[19] P. Surer, Characterisation results for shift radix systems. Math. Pannon. 18 (2007), 265–297. | MR 2363119 | Zbl 1164.11012

[20] P. Surer, ε-shift radix systems and radix representations with shifted digit sets. Publ. Math. (Debrecen) 74 (2009), 19–43. | MR 2490420 | Zbl 1192.11006