Logic and \(p\)-recognizable sets of integers (Q1326952): Difference between revisions

A theorem of \textit{A. Cobham} [Math. Syst. Theory 3, 186--192 (1969; Zbl 0253.02029)] asserts that if \(p\) and \(q\) are two multiplicatively independent integers (i.e. \(\log p/ \log q\) is irrational), then a sequence both \(p\)-automatic and \(q\)-automatic is necessarily ultimately periodic. The proof given by Cobham is rather intricate and many works have been devoted to simplify it. One of them, due to Semenov, uses arguments from logic to prove a multidimensional version of Cobham's theorem and... is not particularly simple. In the extremely interesting paper under review the authors give a very general and complete survey on these results (as well as the relationship with algebraic formal power series on a finite field and the Christol, Kamae, Mendès France and Rauzy theorem). Furthermore they give and simplify a proof of the Cobham-Semenov theorem, originally due to Muchnik. An essential result is that a sequence is \(p\)-automatic if and only if it is (first-order) definable in \(\langle \mathbb{N}, + ,V_p \rangle\), where \(V_p(n) = p^{v_p(n)}\) and \(v_p(n)\) is the largest \(\alpha\) such that \(p^\alpha\) divides \(n\) (here \(p\) is prime). Note that in the case \(p=2\) Büchi stated the result but used \(P_2\) instead of \(v_2\) where \(P_2(x)\) is the unary relation ``\(x\) is a power of 2''. MacNaughton noticed that the proof was wrong and the correct formulation and proof with \(v_p\) are due to the first author in her ``Mémoire de fin d'études'' written in 1985.