Finite and periodic orbits of shift radix systems

Peter Kirschenhofer; Attila Pethő; Paul Surer; Jörg Thuswaldner

doi:10.5802/jtnb.725

Peter Kirschenhofer ¹; Attila Pethő ²; Paul Surer ³; Jörg Thuswaldner ¹

¹ Chair of Mathematics and Statistics University of Leoben Franz-Josef-Str. 18 A-8700 Leoben, AUSTRIA
² Faculty of Informatics Number Theory Research Group Hungarian Academy of Sciences and University of Debrecen P.O. Box 12 H-4010 Debrecen, HUNGARY
³ Departamento de Matemática IBILCE - UNESP Rua Cristóvão Colombo, 2265 - Jardim Nazareth 15.054-000 São José do Rio Preto - SP, BRAZIL

Journal de théorie des nombres de Bordeaux, Volume 22 (2010) no. 2, pp. 421-448.

Abstract
Résumé

For $r = (r_{0}, ..., r_{d - 1}) \in ℝ^{d}$ define the function

τ_{r} : ℤ^{d} \to ℤ^{d}, z = (z_{0}, ..., z_{d - 1}) \mapsto (z_{1}, ..., z_{d - 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} + \dots + 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.

Pour $r = (r_{0}, ..., r_{d - 1}) \in ℝ^{d}$ , nous définissons la fonction

τ_{r} : ℤ^{d} \to ℤ^{d}, z = (z_{0}, ..., z_{d - 1}) \mapsto (z_{1}, ..., z_{d - 1}, - ⌊rz⌋),

où $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} + \dots + 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.

MR Zbl

DOI: 10.5802/jtnb.725

Classification: 11A63
Keywords: Contractive polynomial, shift radix system, periodic orbit

Author's affiliations:

Peter Kirschenhofer ¹; Attila Pethő ²; Paul Surer ³; Jörg Thuswaldner ¹

¹ Chair of Mathematics and Statistics University of Leoben Franz-Josef-Str. 18 A-8700 Leoben, AUSTRIA
² Faculty of Informatics Number Theory Research Group Hungarian Academy of Sciences and University of Debrecen P.O. Box 12 H-4010 Debrecen, HUNGARY
³ Departamento de Matemática IBILCE - UNESP Rua Cristóvão Colombo, 2265 - Jardim Nazareth 15.054-000 São José do Rio Preto - SP, BRAZIL

@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/}
}

TY  - JOUR
AU  - Peter Kirschenhofer
AU  - Attila Pethő
AU  - Paul Surer
AU  - Jörg Thuswaldner
TI  - Finite and periodic orbits of shift radix systems
JO  - Journal de théorie des nombres de Bordeaux
PY  - 2010
SP  - 421
EP  - 448
VL  - 22
IS  - 2
PB  - Université Bordeaux 1
UR  - https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.725/
DO  - 10.5802/jtnb.725
LA  - en
ID  - JTNB_2010__22_2_421_0
ER  -

%0 Journal Article
%A Peter Kirschenhofer
%A Attila Pethő
%A Paul Surer
%A Jörg Thuswaldner
%T Finite and periodic orbits of shift radix systems
%J Journal de théorie des nombres de Bordeaux
%D 2010
%P 421-448
%V 22
%N 2
%I Université Bordeaux 1
%U https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.725/
%R 10.5802/jtnb.725
%G en
%F JTNB_2010__22_2_421_0

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, Volume 22 (2010) no. 2, pp. 421-448. doi : 10.5802/jtnb.725. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.725/

References
Cited by

[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

[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

[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

[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 | Zbl

[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

[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 | Zbl

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

[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 | Zbl

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

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

[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

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

[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 | Zbl

[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 | Zbl

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

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

[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 | Zbl

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

Cited by Sources: