Word Morphism

A word morphism is a map between collections of finite words that preserves concatenation and the empty word. If and are alphabets and and denote their finite words, a word morphism satisfies

(1)

where , and sends the empty word to the empty word. Equivalently, it is a homomorphism between the monoids of words under concatenation. Its values on the individual letters determine its value on every word.

A -uniform word morphism replaces each letter by a word of length . For example, the binary word morphism , is 2-uniform. Repeated application to 0 produces initial segments of the Thue-Morse sequence. A binary word morphism is complementary if is obtained from by interchanging 0 and 1.

Repetition avoidance is often expressed using the critical exponent of a word. The exponent of a nonempty finite word of length is , where is the smallest positive shift for which letters positions apart agree wherever both occur. A word is -free if none of its finite contiguous substrings has exponent at least . It is -free if exponents equal to are allowed but larger exponents are forbidden. A word morphism is -free if it maps every -free word to an -free word. The analogous definition applies to .

Shallit et al. (2024) conjectured that the possible positive lengths of uniform binary word morphisms preserving these avoidance conditions are constant from the condition up to, but not including, the 3-free condition. An OpenAI Codex project reported that the admissible lengths are exactly all positive integers except 3 and 6, both for the condition and for every real number with . Every admissible length has a complementary example. At the strict condition, length 5 is impossible, although it is possible at (dot 2026).

For one family in the earlier construction, let be a contiguous block of the Thue-Morse sequence beginning 0110 or 1001 and ending 0010 or 1101. Define and , where interchanges 0 and 1. The reported strengthening asserts that

(2)

where is the critical exponent and is any cubefree word. A complementary length-12 example has images

			(3)
			(4)

Combining this example with powers of the word morphism generating the Thue-Morse sequence covers the remaining lengths in the family for .

As of Oct. 5, 2026, exact finite checks supported the construction, but the all-length and all-input argument had not received independent specialist review. The accompanying AI review was not an independent review, and no Lean formalization was supplied (dot 2026, VibeMathed 2026).