Cellular automata and powers of p∕q
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Special issue dedicated to the 16th "Journées Montoises d’Informatique Théorique", Tome 51 (2017) no. 4, pp. 191-204.

We consider one-dimensional cellular automata F p , q which multiply numbers by p ∕ q in base p q for relatively prime integers p and q . By studying the structure of traces with respect to F p , q we show that for p ≥ 2 q - 1 (and then as a simple corollary for p > q > 1 ) there are arbitrarily small finite unions of intervals which contain the fractional parts of the sequence ξ ( p ∕ q ) n , ( n = 0 , 1 , 2 , ... ) , for some ξ > 0 . To the other direction, by studying the measure theoretical properties of , F p , q , we show that for p > q > 1 there are finite unions of intervals approximating the unit interval arbitrarily well wich don't contain the fractional parts of the whole sequence ξ ( p / q ) n for any ξ > 0 .

DOI : 10.1051/ita/2017014
Classification : 11J71, 37A25, 68Q80
Mots-clés : Distribution modulo 1, Z-numbers, cellular automata, ergodicity, strongly mixing
Kari, Jarkko 1 ; Kopra, Johan 1

1 
@article{ITA_2017__51_4_191_0,
     author = {Kari, Jarkko and Kopra, Johan},
     title = {Cellular automata and powers of p\ensuremath{/}q},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {191--204},
     publisher = {EDP-Sciences},
     volume = {51},
     number = {4},
     year = {2017},
     doi = {10.1051/ita/2017014},
     mrnumber = {3782820},
     zbl = {1432.11081},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ita/2017014/}
}
TY  - JOUR
AU  - Kari, Jarkko
AU  - Kopra, Johan
TI  - Cellular automata and powers of p∕q
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2017
SP  - 191
EP  - 204
VL  - 51
IS  - 4
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ita/2017014/
DO  - 10.1051/ita/2017014
LA  - en
ID  - ITA_2017__51_4_191_0
ER  - 
%0 Journal Article
%A Kari, Jarkko
%A Kopra, Johan
%T Cellular automata and powers of p∕q
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2017
%P 191-204
%V 51
%N 4
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ita/2017014/
%R 10.1051/ita/2017014
%G en
%F ITA_2017__51_4_191_0
Kari, Jarkko; Kopra, Johan. Cellular automata and powers of p∕q. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Special issue dedicated to the 16th "Journées Montoises d’Informatique Théorique", Tome 51 (2017) no. 4, pp. 191-204. doi : 10.1051/ita/2017014. http://archive.numdam.org/articles/10.1051/ita/2017014/

[1] S. Akiyama, Mahler’s Z-number and 3/2 number system. Unif. Distrib. Theory 3 (2008) 91–99. | MR | Zbl

[2] S. Akiyama, Ch. Frougny and J. Sakarovitch, Powers of rationals modulo 1 and rational base number systems. Isr. J. Math. 168 (2008) 53–91. | DOI | MR | Zbl

[3] A. Dubickas, On the powers of 3/2 and other rational numbers. Math. Nachr. 281 (2008) 951–958. | DOI | MR | Zbl

[4] L. Flatto, J.C. Lagarias and A.D. Pollington, On the range of fractional parts {ξ(p∕q)n }. Acta Arith. 70 (1995) 125–147. | DOI | MR | Zbl

[5] G. Hedlund, Endomorphisms and automorphisms of shift dynamical systems. Math. Syst. Theory 3 (1969) 320–375. | DOI | MR | Zbl

[6] J. Kari, Cellular automata, the Collatz conjecture and powers of 3/2, in Developments in Language Theory. Vol. 7410 of Lecture Notes in Computer Science (2012) 40–49. | DOI | MR | Zbl

[7] J. Kari, Universal pattern generation by cellular automata. Theor. Comput. Sci. 429 (2012) 180–184. | DOI | MR | Zbl

[8] K. Mahler, An unsolved problem on the powers of 3/2. J. Aust. Math. Soc. 8 (1968) 313–321. | DOI | MR | Zbl

[9] W. Rudin, Real and Complex Analysis. McGraw-Hill Book Company, New York (1966). | MR | Zbl

[10] P. Walters, An Introduction to Ergodic Theory. Springer-Verlag, New York (1982). | DOI | MR

[11] H. Weyl, Über die Gleichverteilung von Zahlen mod. Eins. Math. Ann. 77 (1916) 313–352. | DOI | JFM | MR

Cité par Sources :