Substitutive systems and a finitary version of Cobham's theorem (Q2064759)

Let \(\mathcal{A}\) be a finite alphabet, \(\mathcal{A}^*\) the set of finite words over \(\mathcal{A}\) and \(\mathcal{A}^\omega\) the set of sequences with values in \(\mathcal{A}\). Cobham's theorem states that a sequence is simultaneously automatic with respect to multiplicatively independent bases if and only if it is ultimately periodic. A purely substitutive sequence is a fixed point of a substitution \(\varphi: \mathcal{A} \rightarrow \mathcal{A}^*\) and substitutive if it arises from a purely substitutive sequence over some alphabet \(\mathcal{B}\) after applying a coding \(\pi: \mathcal{B} \rightarrow \mathcal{A}\). A dynamical system \(X \subseteq \mathcal{A}^\omega\) is substitutive if it arises as the orbit closure of a substitutive sequence and transitive if has a point with a dense orbit. A standing assumption is that the length of the words \(\varphi^n(a)\) tends to infinity with \(n\) for all \(a\in\mathcal{A}\). A substitution \(\varphi\) is called primitive if there is an integer \(n\ge 1\) such that for any \(a,b\in \mathcal{A}\) the letter \(a\) appears in \(\varphi^n(b)\). Such systems have been extensively studied. A substitution is of constant length if \(\vert \varphi(a)\vert =k\) for each \(a\in\mathcal{A}\). A fixed point of a substitution of constant length \(k\) is called purely \(k\)-automatic. A \(k\)-automatic sequence is the image of a purely \(k\)-automatic sequence under a coding. The first major result of the paper is that every transitive subsystem of a substitutive system is substitutive. Further, every transitive subsystem of a \(k\)-automatic system is \(k\)-automatic. A more precise version of this result describes generators for such subsystems. The second major result is an application of the first to give a finitary version of Cobham's theorem and a complete characterisation of the sets of words that can appear as common factors of two automatic sequences defined over multiplicatively independent bases. Namely, let \(k,l\ge 2\) be multiplicatively independent integers and let \(U\subset \mathcal{A}^*\). The following conditions are equivalent: (1) There is a \(k\)-automatic sequence \(x\) and an \(l\)-automatic sequence \(y\) such that \(U\) is the set of common factors of \(x\) and \(y\). (2) The set \(U\) is a finite nonempty union of sets of the form \(\mathcal{L}(^{\omega} vuw^\omega)\), where \(u,v,w\) are (possibly empty) words over \(\mathcal{A}\) and \(^{\omega} vuw^\omega = \cdots vvvuwww\cdots\) and \(\mathcal{L}(y)\) denotes the set of factors of a word or sequence \(y\). The first step in the proof is to understand the structure of sets of the form \(S_x=\{n\ge0 \mid vU^nw \;\;{\mathrm{ is a factor of }} x\}\) for fixed nonempty words \(u,v,w\), when \(x\) is a \(k\)-automatic sequence. Assume \(v\) is not a suffix of \(u^n\) and \(w\) is not a prefix of \(u^n\) for any integer \(n\). Then \(S\) is a finite union of sets of the form \(\{ak^{mn}+b \mid n\ge0\}\) for some \(a,b\in\mathbb{Q}\) and \(m\in\mathbb{N}\) with \(a,b\ge0, a+b\in\mathbb{Z}\) and \((k^m-1)a\in\mathbb{Z}\). Let \(k,l\ge2\) be multiplicatively independent integers and let \(x\) be a \(k\)-automatic sequence and \(y\) an \(l\)-automatic sequence. Then \(vu^nw\) is a common factor of \(x\) and \(y\) only for finitely many \(n\). This follows from the form of the solutions in the first result because the S-unit equation \(ak^n+bl^m=c\) has only finitely many integer solutions \(m,n\). Thus far, the proof is effective. In dealing with general sequences, one step requires a bound on the rank of common factors and this step uses a compactness argument on \(\mathcal{A}^\omega\) and is not effective. As the authors remark, it would be interesting to explore whether there is an effective proof. The authors also discuss a range of potential extensions of Cobham's theorem inspired by results on the recognisability of subsets of integers and algebraic characterisations of automaticity.