Avoiding squares and overlaps over the natural numbers

TL;DR

The paper studies greedy no-backtracking generation of lexicographically least infinite words over \(\mathbb N\) avoiding squares and overlaps. It identifies the squarefree case as the ruler sequence generated by a simple morphism, and constructs an explicit overlap-free morphism whose fixed point is the lexicographically least overlap-free word, with length, frequency, and symmetry properties.

Key findings

• For squares, the lexicographically least infinite squarefree word over \(\mathbb N\) is \(w_2=01020103\cdots\), the ruler sequence (Sloane A007814), equal to \(\gamma^\omega(0)\) for \(\gamma(i)=0\cdot(i+1)\); \(w_2[i]=\nu_2(i)\), the exponent of the highest power of 2 dividing \(i\).
• For overlaps, the lexicographically least infinite overlap-free word is \(w_{2^+}=\varphi^\omega(0)\), where \(\varphi(0)=001\), \(\varphi(1)=1001002\), \(\varphi(2)=200100110010020010011001003\ldots\); the morphism \(\varphi\) is overlap-free and irreducible.
• For all \(0\le h\le k\), the lexicographically least overlap-free word starting with \(h\) and ending with \(k\) is \(\psi(h,k)=\varphi^{k-h}(h)\). Lengths include \(a(0,k)=1,3,13,79,633,6331\) for \(k=0,\dots,5\), and \(|\varphi(h)|=3,7,27,159,1267,\ldots\), with \(|\varphi(h)|=a(h,h+1)=2a(0,h)+1\).
• The letter \(k\) occurs in \(w_{2^+}\) with limiting frequency \(1/(2^k k!\sqrt e)\); symmetry results include \(S^{-1}(\psi(0,k))=R(\psi(0,k))\), \(\psi(0,k)\cdot k^{-1}\) is a palindrome, and \(\varphi\) commutes with its reversed morphism.

Methods

• Theoretical combinatorics on words: defines a no-backtracking greedy algorithm over \(\mathbb N\) and the notions of irreducibility of words and morphisms with respect to a pattern.
• No empirical data or sample; the work constructs morphisms \(\gamma\) and \(\varphi_h/\varphi\) and proves properties by induction, using a left inverse \(\rho\) for \(\gamma\) and block decompositions for \(\varphi_h\).
• Main analysis proves squarefree/overlap-free and irreducible properties, derives recurrences for lengths \(a(h,k)\) and letter counts \(d(h,k)=2^{k-h}k!/h!\), and establishes limiting letter frequencies.

Limitations

• Stated: fractional powers are harder; it is not even clear that an infinite alphabet is needed, and the first million letters of \(w_{5/2}\), the lexicographically least infinite word over \(\mathbb N\) avoiding all powers with exponent \(\ge 5/2\), are all in \(\{0,1,2\}\).
• Stated: the proofs are presented for squares and overlaps, though they can be extended to arbitrary \(n\)th powers and \((n+)\)-powers; for finite alphabet \(\Sigma_3\), it is not known whether the number of positions one has to backtrack is bounded.
• Evident from the text: the main overlap result is over the infinite alphabet \(\mathbb N\) and relies on the no-backtracking algorithm, so finite-alphabet analogues and backtracking complexity are not settled here.