A density version of Cobham’s theorem. (English) Zbl 1477.11049

Cobham’s theorem states that each sequence which is automatic in two multiplicatively independent bases is eventually periodic. The authors extend this theorem and show that each automatic sequence which is almost everywhere equal to an automatic sequence in a multiplicatively independent base is periodic almost everywhere. Here, almost everywhere means that the exceptional set has zero density.
This answers a question of Jean-Marc Deshouillers that was motivated by the sequence of least non zero digits of \(n!\) in base 12, see [J.-M. Deshouillers and I. Z. Ruzsa, Publ. Math. 79, No. 3–4, 395–400 (2011; Zbl 1249.11044)]. In particular, it proves that the characteristic sequence of numbers \(n\) such that \(n!\) has a fixed least non zero digit \(y \in \{3,4,6,8,9\}\) in base 12 is not automatic. Independently, the bases \(b\) such that the sequence of least non zero digits of \(n!\) in base \(b\) is automatic were characterised in [E. Lipka, J. Théor. Nombres Bordx. 31, No. 1, 283–291 (2019; Zbl 1475.11039)], in particular the sequence is not automatic for \(b=12\).


11B85 Automata sequences
11A63 Radix representation; digital problems
37B10 Symbolic dynamics
68Q45 Formal languages and automata
68R15 Combinatorics on words
Full Text: DOI arXiv