In the study of combinatorics on words, researchers seek to understand the boundary between randomness and structure. A central tool in this quest is the critical exponent, which quantifies the "burstiness" of repetitions within a string. If a word contains a factor like $ababab$, it has a repetition of $(ab)^3$, or an exponent of 3. The repetition threshold for a given class of words is the smallest possible critical exponent that an infinite word in that class can possess. Essentially, it represents the absolute minimum amount of repetition that is mathematically unavoidable.
The Cost of Structure: Rich and Balanced Words
When we impose structural constraints on a word—such as requiring it to be "rich" in palindromes or "balanced" in symbol frequency—we often force the repetition threshold to climb.
Rich words are those that contain the maximum possible number of distinct palindromic substrings. Because palindromes are inherently symmetric, they tend to introduce repetitions. Baranwal investigated this trade-off in Repetitions in Infinite Palindrome-Rich Words, constructing a binary rich word with a critical exponent of $2 + \sqrt{2}/2$. This value is conjectured to be the lowest possible for the entire class of binary rich words, marking the point where the requirement for palindromic richness meets the desire for minimal repetition.
Similarly, balanced words require that the number of occurrences of any two symbols differs by at most one across any two factors of the same length. This strict regularity makes it difficult to avoid repetitions. In Critical Exponent of Infinite Balanced Words via the Pell Number System, Baranwal proved that for a 5-letter alphabet, the repetition threshold for balanced words is exactly $3/2$. The authors achieved this by identifying specific factors (length 6, period 4) that represent the "tightest" possible repetitions allowed under the balanced constraint.
Avoidance and the Power of Large Alphabets
A classic problem in this field is the construction of square-free words—strings that never repeat the same factor twice in a row ($xx$). While this is impossible for very small alphabets, larger alphabets provide more "room" to maneuver.
Hong et al. explored the limits of this maneuverability in No extremal square-free words over large alphabets. An "extremal" word is one that is square-free but cannot be extended by inserting any character at any position without creating a square. The authors proved that for alphabets with at least 17 symbols, such dead-ends do not exist. This suggests that with a sufficiently large alphabet, the combinatorial "space" is vast enough that you can always find a way to avoid repetition.
Beyond Simple Squares: Antisquares and Antipowers
Repetition is not always about exact identity. Researchers also study patterns based on complements and diversity.
- Antisquares: In binary strings, an antisquare is a factor of the form $x\bar{x}$, where $\bar{x}$ is the bitwise complement of $x$ (e.g., $0110 \cdot 1001$). Currie et al. showed in Antisquares and Critical Exponents that if we try to avoid all but the most basic antisquares, the repetition threshold is governed by the golden ratio: $2 + \phi$.
- Antipowers: A $k$-antipower is a concatenation of $k$ distinct subwords of the same length. While the Thue-Morse word is famous for avoiding squares and cubes, its relationship with these "diverse" patterns is more complex. Narayanan provided tight bounds on the lengths of these antipowers in Functions on antipower prefix lengths of the Thue-Morse word, revealing the deep structural regularity that persists even when a word avoids traditional repetition.
The Asymptotics of Periodicity
Finally, the study of repetitions extends to the global properties of strings. Every string has a period set—the collection of all lengths $p$ such that the string repeats itself every $p$ characters. A long-standing question asked how many distinct period sets can exist for strings of a certain length. In Convergence of the Number of Period sets in Strings, Rivals et al. resolved a decades-old conjecture, proving that the number of these sets converges asymptotically. This result provides a theoretical ceiling on the variety of repetitive structures that finite strings can exhibit, complementing the work on infinite words.
Key Foundational Work
Repetitions in Infinite Palindrome-Rich Words (2019) — contributed 9 concept elements to this direction.
Critical Exponent of Infinite Balanced Words via the Pell Number System (2019) — contributed 5 concept elements to this direction.
Functions on antipower prefix lengths of the Thue-Morse word (2020) — contributed 1 concept elements to this direction.