Avoiding 5/4-Powers on the Alphabet of Nonnegative Integers

TL;DR

The paper identifies the lexicographically least infinite word \(w_{5/4}\) on nonnegative integers avoiding exact \(5/4\)-powers, showing it has the morphic form \(p\,\tau(\varphi(z)\varphi^2(z)\cdots)\) with \(p\) length 6764, \(z\) length 20226, \(\varphi\) a 6-uniform morphism, and \(\tau\) a coding. It derives a recurrence for its letters and proves the sequence of letters is 6-regular with rank 188, plus a general \(k\)-regularity theorem for similar recurrences.

Key findings

• The lexicographically least \(5/4\)-power-free word is \(w_{5/4}=p\,\tau(\varphi(z)\varphi^2(z)\cdots)\), where \(|p|=6764\), \(|z|=20226\), \(\varphi\) is 6-uniform, and \(\tau\) is a coding.
• The letters \(w(i)\) of \(w_{5/4}\) satisfy a recurrence (Corollary 5) involving the constants \(123061=6\cdot20510+1\) and \(5920\).
• The sequence of letters in \(w_{5/4}\) is 6-regular with rank 188 (Theorem 33).
• More generally, integer sequences satisfying a recurrence of the same type are \(k\)-regular (Theorem 6).

Methods

• The proof shows \(p\,\tau(\varphi(z)\varphi^2(z)\cdots)\) is \(5/4\)-power-free and lexicographically least, the latter by proving that decreasing any nonzero letter introduces a \(5/4\)-power ending at that position.
• Because \(\varphi\) is not \(5/4\)-power-free, the authors introduce pre-\(5/4\)-power-freeness, use locating lengths, and work with subscript-increasing words on an 8-letter-per-integer alphabet.
• The analysis uses extensive computation, including Mathematica checks and an explicit length-331040 prefix of \(w_{5/4}\).

Limitations

• The paper states open questions: the structures of \(w_{7/5}\), \(w_{7/6}\), and \(w_{11/6}\) are not known; it gives conjectures for five additional words and no conjecture for \(w_{11/6}\) and \(w_{11/8}\).
• The paper notes there is no systematic way to guess the structure of \(w_{a/b}\) even with many terms, and whether each \(w_{a/b}\) is \(k\)-regular remains open.
• Evident from the text: the proof relies on lengthy computer computations and a very long prefix, and the morphism \(\varphi\) does not preserve \(5/4\)-power-freeness, making the argument significantly more intricate.