Cellular Automata and Powers of $p/q$

Abstract

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 (p/q{)}^n$, ($n=0,1,2,\dots$) 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 which don't contain the fractional parts of the whole sequence $\xi (p/q{)}^n$ for any $\xi >0$.

15 pages, 8 figures. Accepted for publication in RAIRO-ITA