Characterisation results for Shift Radix Systems

About the article

Abstract

For r∈d define the function τr: d → d in the following way:

τr: d → d, a=(a1,…,ad)(a2,…,ad,−⌊ra⌋).

τr is called a Shift Radix System (SRS) if ∀a∈d ∃k∈: τrk(a) = 0. In this paper we deal with new results concerning the characterisation of the set 0d:={r∈d|τr is an SRS}, especially for d=2. For this purpose we adapt and generalise several results and methods presented in earlier papers.

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ő, J. M. Thuswaldner, Generalized radix representations and dynamical systems II, Acta Arith. 121 (2006), 21—61.
4. H. Brunotte, On trinomial bases of radix representations of algebraic integers, Acta Sci. Math. Acta Sci. Math. (Szeged) 67 (2001), 521—527.
5. K. Fukuda, cdd and cddplus Homepage, ETHZ, Zürich, Switzerland, http://www.ifor.math.ethz.ch/~fukuda/cdd_home/index.html.
6. S. Lagarias, Y. Wang, Self affine Tiles in Self affine Tiles in n, Adv. Math. 121 (1996), 21—49.
7. T. S. Motzkin, H. Raiffa, G. L. Thompson, R. L. Thrall, The double description method Contributions to the theory of games, vol. 2, pp. 51-73. Annals of Mathematics Studies, no. 28. Princeton University Press, Princeton, N. J. 1953.
8. W. Parry, On the β-expansions of real numbers, Acta Math. Acad. Sci. Hungar. 11 (1960), 401—416.
9. A. Pethő, On a polynomial transformation and its application to the construction of a public key cryptosystem, Computational number theory (Debrecen, 1989), de Gruyter, Berlin, 1991, 31—43.
10. A. Rényi, Representations for real numbers and their ergodic properties, Acta Math. Acad. Sci. Hungar. 8 (1957), 477—493.
11. P. Surer, Personal homepage, http://www.palovsky.com/links/p12007.htm.
12. R. Tarjan, Depth-first search and linear graph algorithms, SIAM J. Comput. 1 (1972), 146—160.

Download

Mathematica^® Notebook-File (Version 5.1) with an implementation of the algorithm Br.
download Br

Mathematica^® Notebook-File (Version 5.1) with an implementation of the algorithm Ak.
download Ak

Mathematica^® Notebook-File (Version 5.1) with a list of all known nonempty periods. Because it consists of a lot of periods (more than 1000) this list is suitable for computational use only.
download list

Links

Mathematica Pannonica
Austrian Science Foundation (FWF)
National Research Network (NFN) S9600