Cellular automata and powers of p∕q

Kari, Jarkko¹   ; Kopra, Johan¹

¹

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

Résumé

We consider one-dimensional cellular automata $F_{p,q}$ which multiply numbers by $p∕q$ in base $pq$ for relatively prime integers $p$ and $q$. By studying the structure of traces with respect to $F_{p,q}$ we show that for $p\ge 2q-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 $\xi {\left(p∕q\right)}^n,(n=0,1,2,...)$, for some $\xi >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 $\xi {(p/q)}^n$ for any $\xi >0$.

Détail

DOI : 10.1051/ita/2017014

Classification : 11J71, 37A25, 68Q80
Keywords: Distribution modulo 1, Z-numbers, cellular automata, ergodicity, strongly mixing