no. 13 · Wednesday 11 November 2026
An automated approach to structure theorems for minimally repetitive rich words
Abstract
Recent work on repetitions in rich words has led to the intensive study of the family of infinite rich words $\{{\mathbf u}_d:d\geq 2\}$, where ${\mathbf u}_d$ is the fixed point of the morphism $\varphi_d:Σ_d^*\rightarrow Σ_d^*$ defined by $\varphi_d(i)=\tt{0}(i+1)$ for $i\in\{\tt{0},\ldots,d-2\}$ and $\varphi_d(d-1)=\tt{0}(d-1)(d-1)$. For $d=2$ and $d=3$, it is known that the repetition threshold for infinite $d$-ary rich words is equal to the asymptotic critical exponent $E^*({\mathbf u}_{2d-1})$. Moreover, the structure of ${\mathbf u}_{2d-1}$ underlies the structure of all ``minimally repetitive'' $d$-ary rich words: there is a real number $t_d>E^*({\mathbf u}_{2d-1})$ such that every infinite $t_d$-power-free $d$-ary rich word contains the language of $π({\mathbf u}_{2d-1})$ for one of finitely many morphisms $π:Σ_{2d-1}^*\rightarrow Σ_d^*$. We conjecture that a similar situation holds for all $d\geq 2$, and prove this for the first unknown case $d=4$. To do this, we develop a new approach for proving such structure theorems. Two key new concepts are ``compatibility'' of return words to palindromes in recurrent rich words, and ``$t$-persistent repetitions''. They facilitate the automation of several aspects of the proofs which were previously done laboriously by hand. We first demonstrate our approach by giving a much shorter proof of the known structure theorem for infinite $\tfrac{16}{7}$-power-free ternary rich words. Then we prove a new structure theorem: every infinite $2.12$-power-free quaternary rich word contains the language of one of seven distinct words of the form $π({\mathbf u}_7)$, up to permutation of the letters. We prove that all seven words are rich and have critical exponent $E^*({\mathbf u}_7)$, so the repetition threshold for quaternary rich words is $E^*({\mathbf u}_7)\doteq 2.1197196907$.
- fields
- Combinatorics