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.
[1] In the study of strings, concatenation is seen as analogous to multiplication of numbers.
This exponential notation may also be extended to fractional powers: if
is a non-negative rational number of the form
[1] 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.
[1] For alphabets of two symbols, however, there do exist infinite cube-free words, words with no substring of the form
More strongly, the Thue–Morse sequence contains no substring that is a power strictly greater than two.
[1] In 1972, Dejean investigated the problem of determining, for each possible alphabet size, the threshold between exponents
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;[2] this formula is Dejean's conjecture, now a theorem.
, the repeat threshold, to be the infimum of exponents
Thus, for instance, the Thue–Morse sequence shows that
, and an argument based on the Lovász local lemma can be used to show that
[1] Then Dejean's conjecture is that the repeat threshold can be calculated by the simple formula[1][2] except in two exceptional cases: and Dejean herself proved the conjecture for
[3] The next progress was by Moulin Ollagnier in 1992, who proved the conjecture for all alphabet sizes up to
[5] In the other direction, also in 2007, Arturo Carpi showed the conjecture to be true for large alphabets, with
[6] This reduced the problem to a finite number of remaining cases, which were solved in 2009 and published in 2011 by Currie and Rampersad[7] and independently by Rao.
[8] 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.