Dejean's theorem

Dejean's theorem (formerly Dejean's conjecture) is a statement about repetitions in infinite strings of symbols. It belongs to the field of combinatorics on words; it was conjectured in 1972 by Françoise Dejean and proven in 2009 by Currie and Rampersad and, independently, by Rao.Template:R

Context

In the study of strings, concatenation is seen as analogous to multiplication of numbers. For instance, if $s$ is any string, then the concatenation $ss$ of two copies of $s$ is called the square of $s$, and denoted $s^2$. This exponential notation may also be extended to fractional powers: if $s$ has length $\ell$, and $e$ is a non-negative rational number of the form $n/\ell$, then $s^e$ denotes the string formed by the first $n$ characters of the infinite repetition $sssss\dots$.Template:R

A square-free word is a string that does not contain any square as a substring. In particular, it avoids repeating the same symbol consecutively, repeating the same pair of symbols, etc. Axel Thue showed that there exists an infinite square-free word using a three-symbol alphabet, the sequence of differences between consecutive elements of the Thue–Morse sequence. However, it is not possible for an infinite two-symbol word (or even a two-symbol word of length greater than three) to be square-free.Template:R

For alphabets of two symbols, however, there do exist infinite cube-free words, words with no substring of the form $sss$. One such example is the Thue–Morse sequence itself; another is the Kolakoski sequence. More strongly, the Thue–Morse sequence contains no substring that is a power strictly greater than two.Template:R

In 1972, Dejean investigated the problem of determining, for each possible alphabet size, the threshold between exponents $e$ for which there exists an infinite $e$-power-free word, and the exponents for which no such word exists. The problem was solved for two-symbol alphabets by the Thue–Morse sequence, and Dejean solved it as well for three-symbol alphabets. She conjectured a precise formula for the threshold exponent for every larger alphabet size;Template:R this formula is Dejean's conjecture, now a theorem.Template:R

Statement

Let $k$ be the number of symbols in an alphabet. For every $k$, define $\mathrm{RT}(k)$, the repeat threshold, to be the infimum of exponents $e$ such that there exists an infinite $e$-power-free word on a $k$-symbol alphabet. Thus, for instance, the Thue–Morse sequence shows that $\mathrm{RT}(2)=2$, and an argument based on the Lovász local lemma can be used to show that $\mathrm{RT}(k)$ is finite for all $k$.Template:R

Then Dejean's conjecture is that the repeat threshold can be calculated by the simple formulaTemplate:R

$\mathrm{RT}(k)=\frac{k}{k-1}$

except in two exceptional cases:

$\mathrm{RT}(3)=\frac{7}{4}$

and

$\mathrm{RT}(4)=\frac{7}{5}.$

Progress and proof

Dejean herself proved the conjecture for $k=3$.Template:R The case $k=4$ was proven by Jean-Jacques Pansiot in 1984.Template:R The next progress was by Moulin Ollagnier in 1992, who proved the conjecture for all alphabet sizes up to $k\le 11$.Template:R This analysis was extended up to $k\le 14$ in 2007 by Mohammad-Noori and Currie.Template:R

In the other direction, also in 2007, Arturo Carpi showed the conjecture to be true for large alphabets, with $k\ge 33$.Template:R This reduced the problem to a finite number of remaining cases, which were solved in 2009 and published in 2011 by Currie and RampersadTemplate:R and independently by Rao.Template:R

Dejean words

An infinite string that meets Dejean's formula (having no repetitions of exponent above the repetition threshold) is called a Dejean word. Thus, for instance, the Thue–Morse sequence is a Dejean word.