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.

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$.

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.

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.

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; this formula is Dejean's conjecture, now a theorem.

Statement

Let $k$ be the number of symbols in an alphabet.
For every $k$, define $\operatorname(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 $\operatorname(2)=2$, and an argument based on the Lovász local lemma can be used to show that $\operatorname(k)$ is finite for all $k$.

Then Dejean's conjecture is that the repeat threshold can be calculated by the simple formula
:$\operatorname(k)=\frac$
except in two exceptional cases:
:$\operatorname(3)=\frac$
and
:$\operatorname(4)=\frac.$

Progress and proof

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

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

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.

References

{{reflist, refs=

{{citation
, last = Carpi , first = Arturo
, doi = 10.1016/j.tcs.2007.06.001
, issue = 1–3
, journal = Theoretical Computer Science
, mr = 2356248
, pages = 137–151
, title = On Dejean's conjecture over large alphabets
, volume = 385
, year = 2007, doi-access =

{{citation
, last1 = Currie , first1 = James
, last2 = Rampersad , first2 = Narad
, doi = 10.1090/S0025-5718-2010-02407-X
, issue = 274
, journal = Mathematics of Computation
, mr = 2772111
, pages = 1063–1070
, title = A proof of Dejean's conjecture
, volume = 80
, year = 2011, arxiv = 0905.1129

{{citation
, last = Dejean , first = Françoise
, doi = 10.1016/0097-3165(72)90011-8
, journal = Journal of Combinatorial Theory
, mr = 0300959
, pages = 90–99
, series = Series A
, title = Sur un théorème de Thue
, volume = 13
, year = 1972, doi-access =

{{citation
, last1 = Mohammad-Noori , first1 = M.
, last2 = Currie , first2 = James D.
, doi = 10.1016/j.ejc.2005.11.005
, issue = 3
, journal = European Journal of Combinatorics
, mr = 2300768
, pages = 876–890
, title = Dejean's conjecture and Sturmian words
, volume = 28
, year = 2007, doi-access = free

{{citation
, last = Moulin Ollagnier , first = Jean
, doi = 10.1016/0304-3975(92)90264-G
, issue = 2
, journal = Theoretical Computer Science
, mr = 1156042
, pages = 187–205
, title = Proof of Dejean's conjecture for alphabets with 5, 6, 7, 8, 9, 10 and 11 letters
, volume = 95
, year = 1992, doi-access =

{{citation
, last = Pansiot , first = Jean-Jacques
, issue = 3
, journal = Discrete Applied Mathematics
, mr = 736893
, pages = 297–311
, title = À propos d'une conjecture de F. Dejean sur les répétitions dans les mots
, volume = 7
, year = 1984
, doi=10.1016/0166-218x(84)90006-4, doi-access = free

{{citation
, last = Rao , first = Michaël
, doi = 10.1016/j.tcs.2010.06.020
, issue = 27
, journal = Theoretical Computer Science
, mr = 2830264
, pages = 3010–3018
, title = Last cases of Dejean's conjecture
, volume = 412
, year = 2011, doi-access =

{{citation
, last1 = Rampersad , first1 = Narad
, last2 = Shallit , first2 = Jeffrey , author2-link = Jeffrey Shallit
, contribution = Repetitions in words
, mr = 3525483
, pages = 101–150
, publisher = Cambridge Univ. Press, Cambridge
, series = Encyclopedia Math. Appl.
, title = Combinatorics, words and symbolic dynamics
, volume = 159
, year = 2016

Combinatorics on words
Theorems in combinatorics
Conjectures that have been proved