Finite and periodic orbits of shift radix systems

About the paper

Abstract

For r=(r0,…,rd-1)∈d define the function

τr: d → d, 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 td+rd-1td-1+^…+r0 associated to r is contractive. On the other hand, whenever this polynomial has at least one root outside the unit circle, 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 characterise 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.

References

1. S. Akiyama, T. Borbély, H. Brunotte, A. Pethő, J.M. Thuswaldner, Generalized radix representations and dynamical systems I, Acta Math. Hungar. 108 (2005), 207—238.
2. S. Akiyama, H. Brunotte, A. Pethő, W. Steiner, Remarks and conjecture on certain integer sequences, Period. Math Hungar. 52 (2006), 1—17.
3. S. Akiyama, H. Brunotte, A. Pethő, W. Steiner, Periodicity of certain piecewise affine planar maps, Tsukuba J. Math. 32 (2008), 197—251.
4. S. Akiyama, H. Brunotte, A. Pethő, J.M. Thuswaldner, Generalized radix representations and dynamical systems II, Acta Arith. 121 (2006), 21—61.
5. S. Akiyama, C. Frougny, J. Sakarovitch, Powers of rationals modulo 1 and rational base number systems, Israel J. Math. 168 (2008), 53—91.
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.
7. H. Brunotte, On trinomial bases of radix representations of algebraic integers, Acta Sci. Math. Acta Sci. Math. (Szeged) 67 (2001), 521—527.
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, J. S. Meditch, A canonical parameter space for linear systems design, IEEE Trans. Autom. Control 23 (1978), 454—458.
10. C. Frougny, B. Solomyak, Finite beta-expansions, Ergod. Th. and Dynam. Sys. 12 (1992), 713—723.
11. A. Huszti, K. Scheicher, P. Surer, J.M. Thuswaldner, Three-dimensional symmetric shift radix systems, Acta Arith., 129 (2007), 147—166.
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.
13. E. Lehmer, On the magnitude of the coefficients of the cyclotomic polynomial, Bull. Amer. Math. Soc. 42 (1936), 389—392.
14. J. Lowenstein, S. Hatjispyros, F. Vivaldi, Quasi-periodicity, global stability and scaling in a model of Hamiltonian round-off, Chaos 7 (1997), 49—66.
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.
16. A. Pethő, On the boundary of the closure of the set of contractive polynomials, Integers 9 (2009), 311—325.
17. K. Schmidt, On periodic expansions of Pisot numbers and Salem numbers, Bull. London Math. Soc., 12 (1980), 269—278.
18. I. Schur, Über Potenzreihen, die im inneren des Einheitskreises beschränkt sind, J. reine angew. Math., 148 (1918), 122—145.
19. P. Surer, Characterisation results for shift radix systems, Math. Pannon., 18 (2007), 265—297.
20. P. Surer, ε-shift radix systems and radix representations with shifted digit sets, Publ. Math. (Debrecen) 74 (2009), 19—43.

Links

Journal de Théorie des Nombres de Bordeaux
Austrian Science Foundation (FWF)
National Research Network (NFN) S9600
Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)