Avoiding Fractional Powers over the Natural Numbers

TL;DR

The paper studies the lexicographically least \(a/b\)-power-free word on the nonnegative integers, showing many such words are fixed points or codings of uniform morphisms and yield \(k\)-regular sequences. It proves structure for infinite families and many sporadic rationals via automated symbolic proofs, and shows the \(27/23\)-power-free word is on \(\{0,1,2\}\) and is \(353\)-automatic.

Key findings

• For \(a/b \ge 2\), \(w_{a/b}=w_a\) and \(\rho(a/b)=a\); for \(5/3 \le a/b < 2\) with \(\gcd(b,2)=1\), \(w_{a/b}\) is a fixed point of a \((2a-b)\)-uniform morphism and \(\rho(a/b)=2a-b\).
• Explicit values include \(\rho(3/2)=6\), \(\rho(5/3)=7\), \(\rho(9/5)=13\), \(\rho(8/5)=733\), \(\rho(7/4)=50847\), \(\rho(6/5)=1001\), and \(\rho(4/3)=56\); Conjecture 6 would give \(\rho(7/5)=80874\).
• The sequence of letters in \(\tau(\phi^\infty(0'))\) for a \(k\)-uniform morphism \(\phi(n)=u(n+d)\) with transient is \(k\)-regular (Theorem 8); letters satisfy \(w(i)=O(\sqrt{i})\) (Theorem 9), and the possible \(k\) are unique up to multiplicative dependence (Corollary 10).
• The lexicographically least \(27/23\)-power-free word is a word on the finite alphabet \(\{0,1,2\}\) and is \(353\)-automatic (Theorem 71); 30 symbolic \(a/b\)-power-free morphisms are proved automatically (Theorems 21–50).

Methods

• Design: lexicographic greedy construction of \(w_{a/b}\), then identification of fixed points/codings of uniform morphisms \(\phi(n)=u(n+d)\), including transient prefixes \(v\) and a coding \(\tau\) with \(\tau(0')=0\), \(\tau(n)=n\).
• Data/computation: prefixes of \(w_{a/b}\) were computed for 910 rationals in \(1<a/b<2\), over 256 million letters; conjectural structure was identified for 520, of which 510 have a constant difference \(d\).
• Analysis: automated symbolic case analysis via the Mathematica package SymbolicWords, using locating lengths, finite factor lists, and symbolic inequality tests; explicit sporadic rationals were handled with computed prefixes and sliding windows, including a \(50847\)-uniform morphism for \(7/4\).

Limitations

• Stated: the structure of \(w_{5/4}\) is unknown; there is “no intuition” for \(k=50847\); Conjecture 6 is not proved because the computation would take too long; the paper leaves open whether \(\rho(a/b)\) is defined for every rational \(a/b>1\).
• Stated: the method did not look for relationships among words with different numbers of nonzero letters, has no decision procedure for equality of symbolic words, and proving Conjecture 51 is beyond the scope of the code.
• Evident from the text: many structural claims are conjectural, and some morphisms do not determine long-term structure for all rationals in their intervals — e.g., \(24/17\) satisfies Theorems 25, 26, 32, and 33, but the width-\(62\) morphisms do not persist.