# Finite and periodic orbits of shift radix systems

Peter Kirschenhofer[1]; Attila Pethő[2]; Paul Surer[3]; Jörg Thuswaldner[1]

• [1] Chair of Mathematics and Statistics University of Leoben Franz-Josef-Str. 18 A-8700 Leoben, AUSTRIA
• [2] Faculty of Informatics Number Theory Research Group Hungarian Academy of Sciences and University of Debrecen P.O. Box 12 H-4010 Debrecen, HUNGARY
• [3] 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
• Volume: 22, Issue: 2, page 421-448
• ISSN: 1246-7405

top

## Abstract

top
For $\mathbf{r}=\left({r}_{0},...,{r}_{d-1}\right)\in {ℝ}^{d}$ define the function${\tau }_{\mathbf{r}}:\phantom{\rule{0.166667em}{0ex}}{ℤ}^{d}\to {ℤ}^{d},\phantom{\rule{1em}{0ex}}\mathbf{z}=\left({z}_{0},...,{z}_{d-1}\right)↦\left({z}_{1},...,{z}_{d-1},-⌊\mathbf{rz}⌋\right),$where $\mathbf{rz}$ is the scalar product of the vectors $\mathbf{r}$ and $\mathbf{z}$. If each orbit of ${\tau }_{\mathbf{r}}$ ends up at $\mathbf{0}$, we call ${\tau }_{\mathbf{r}}$ a shift radix system. It is a well-known fact that each orbit of ${\tau }_{\mathbf{r}}$ ends up periodically if the polynomial ${t}^{d}+{r}_{d-1}{t}^{d-1}+\cdots +{r}_{0}$ associated to $\mathbf{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 ${\tau }_{\mathbf{r}}$ for vectors $\mathbf{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 $\mathbf{r}$ belonging to the above class the ultimate periodicity of the orbits of ${\tau }_{\mathbf{r}}$ is equivalent to the fact that ${\tau }_{\mathbf{s}}$ is a shift radix system or has another prescribed orbit structure for a certain parameter $\mathbf{s}$ related to $\mathbf{r}$. These results are combined with new algorithmic results in order to characterize vectors $\mathbf{r}$ of the above class that give rise to ultimately periodic orbits of ${\tau }_{\mathbf{r}}$ for each starting value. In particular, we work out the description of these vectors $\mathbf{r}$ for the case $d=3$. This leads to sets which seem to have a very intricate structure.

## How to cite

top

Kirschenhofer, Peter, et al. "Finite and periodic orbits of shift radix systems." Journal de Théorie des Nombres de Bordeaux 22.2 (2010): 421-448. <http://eudml.org/doc/116413>.

@article{Kirschenhofer2010,
abstract = {For $\mathbf\{r\}=(r_0,\ldots ,r_\{d-1\}) \in \mathbb\{R\}^d$ define the function$\tau \_\mathbf\{r\}: \, \{\mathbb\{Z\}\}^d \rightarrow \{\mathbb\{Z\}\}^d,\quad \mathbf\{z\}=(z\_0,\ldots ,z\_\{d-1\}) \mapsto (z\_1,\ldots ,z\_\{d-1\},-\left\lfloor \mathbf\{rz\} \right\rfloor ),$where $\mathbf\{rz\}$ is the scalar product of the vectors $\mathbf\{r\}$ and $\mathbf\{z\}$. If each orbit of $\tau _\mathbf\{r\}$ ends up at $\mathbf\{0\}$, we call $\tau _\mathbf\{r\}$ a shift radix system. It is a well-known fact that each orbit of $\tau _\mathbf\{r\}$ ends up periodically if the polynomial $t^d+r_\{d-1\}t^\{d-1\}+\cdots +r_0$ associated to $\mathbf\{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 $\tau _\mathbf\{r\}$ for vectors $\mathbf\{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 $\{\bf r\}$ belonging to the above class the ultimate periodicity of the orbits of $\tau _\mathbf\{r\}$ is equivalent to the fact that $\tau _\mathbf\{s\}$ is a shift radix system or has another prescribed orbit structure for a certain parameter $\mathbf\{s\}$ related to $\mathbf\{r\}$. These results are combined with new algorithmic results in order to characterize vectors $\mathbf\{r\}$ of the above class that give rise to ultimately periodic orbits of $\tau _\mathbf\{r\}$ for each starting value. In particular, we work out the description of these vectors $\mathbf\{r\}$ for the case $d=3$. This leads to sets which seem to have a very intricate structure.},
affiliation = {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; Chair of Mathematics and Statistics University of Leoben Franz-Josef-Str. 18 A-8700 Leoben, AUSTRIA},
author = {Kirschenhofer, Peter, Pethő, Attila, Surer, Paul, Thuswaldner, Jörg},
journal = {Journal de Théorie des Nombres de Bordeaux},
keywords = {Contractive polynomial; shift radix system; periodic orbit; periodic orbit shift radix system; periodic orbit shift radix system; periodic orbit shift radix system},
language = {eng},
number = {2},
pages = {421-448},
publisher = {Université Bordeaux 1},
title = {Finite and periodic orbits of shift radix systems},
url = {http://eudml.org/doc/116413},
volume = {22},
year = {2010},
}

TY - JOUR
AU - Kirschenhofer, Peter
AU - Pethő, Attila
AU - Surer, Paul
AU - Thuswaldner, Jörg
TI - Finite and periodic orbits of shift radix systems
JO - Journal de Théorie des Nombres de Bordeaux
PY - 2010
PB - Université Bordeaux 1
VL - 22
IS - 2
SP - 421
EP - 448
AB - For $\mathbf{r}=(r_0,\ldots ,r_{d-1}) \in \mathbb{R}^d$ define the function$\tau _\mathbf{r}: \, {\mathbb{Z}}^d \rightarrow {\mathbb{Z}}^d,\quad \mathbf{z}=(z_0,\ldots ,z_{d-1}) \mapsto (z_1,\ldots ,z_{d-1},-\left\lfloor \mathbf{rz} \right\rfloor ),$where $\mathbf{rz}$ is the scalar product of the vectors $\mathbf{r}$ and $\mathbf{z}$. If each orbit of $\tau _\mathbf{r}$ ends up at $\mathbf{0}$, we call $\tau _\mathbf{r}$ a shift radix system. It is a well-known fact that each orbit of $\tau _\mathbf{r}$ ends up periodically if the polynomial $t^d+r_{d-1}t^{d-1}+\cdots +r_0$ associated to $\mathbf{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 $\tau _\mathbf{r}$ for vectors $\mathbf{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 ${\bf r}$ belonging to the above class the ultimate periodicity of the orbits of $\tau _\mathbf{r}$ is equivalent to the fact that $\tau _\mathbf{s}$ is a shift radix system or has another prescribed orbit structure for a certain parameter $\mathbf{s}$ related to $\mathbf{r}$. These results are combined with new algorithmic results in order to characterize vectors $\mathbf{r}$ of the above class that give rise to ultimately periodic orbits of $\tau _\mathbf{r}$ for each starting value. In particular, we work out the description of these vectors $\mathbf{r}$ for the case $d=3$. This leads to sets which seem to have a very intricate structure.
LA - eng
KW - Contractive polynomial; shift radix system; periodic orbit; periodic orbit shift radix system; periodic orbit shift radix system; periodic orbit shift radix system
UR - http://eudml.org/doc/116413
ER -

## References

top
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. Zbl1110.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. Zbl1121.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. Zbl1209.37018MR2433023
4. S. Akiyama, H. Brunotte, A. Pethő, and J. M. Thuswaldner, Generalized radix representations and dynamical systems. II. Acta Arith. 121 (2006), 21–61. Zbl1142.11055MR2216302
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. Zbl1214.11089MR2448050
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. Zbl1053.11536MR1483916
7. H. Brunotte, On trinomial bases of radix representations of algebraic integers. Acta Sci. Math. (Szeged) 67 (2001), 521–527. Zbl0996.11067MR1876451
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. Zbl0377.93021MR528928
10. C. Frougny and B. Solomyak, Finite beta-expansions. Ergodic Theory Dynam. Systems 12 (1992), 713–723. Zbl0814.68065MR1200339
11. A. Huszti, K. Scheicher, P. Surer, and J. M. Thuswaldner, Three-dimensional symmetric shift radix systems. Acta Arith. 129 (2007), 147–166. Zbl1143.11006MR2342432
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. Zbl1230.11014MR2387921
13. E. Lehmer, On the magnitude of the coefficients of the cyclotomic polynomial. Bull. Amer. Math. Soc. 42 (1936), 389–392. Zbl0014.39203MR1563307
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. Zbl0933.37059MR1439807
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. Zbl0733.94014MR1151853
16. A. Pethő, On the boundary of the closure of the set of contractive polynomials. Integers 9 (2009), 311 – 325. Zbl1284.11017MR2534915
17. K. Schmidt, On periodic expansions of Pisot numbers and Salem numbers. Bull. London Math. Soc. 12 (1980), 269–278. Zbl0494.10040MR576976
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. Zbl1164.11012MR2363119
20. P. Surer, $\epsilon$-shift radix systems and radix representations with shifted digit sets. Publ. Math. (Debrecen) 74 (2009), 19–43. Zbl1192.11006MR2490420

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.