A1 Journal article – refereed

Cellular automata and powers of p/q

List of Authors: Jarkko Kari, Johan Kopra

Publisher: EDP Sciences

Publication year: 2017

Journal: RAIRO: Informatique Théorique et Applications / RAIRO: Theoretical Informatics and Applications

Journal name in source: RAIRO - Theoretical Informatics and Applications

Volume number: 51

Issue number: 4

Number of pages: 14

ISSN: 0988-3754

DOI: http://dx.doi.org/10.1051/ita/2017014

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* ≥ 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 which don’t contain the fractional parts of the whole sequence *ξ*(*p*∕*q*)^{n} for any *ξ* > 0.

Downloadable publication This is an electronic reprint of the original article. |