In the study of strings, concatenation is seen as analogous to multiplication of numbers. So, for instance, if is any string, then the concatenation of two copies of is called the square of, and denoted. This exponential notation may also be extended to fractional powers: if has length, and is a non-negativerational numberof the form, then denotes the string formed by the first characters of the infinite repetition. 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 to be square-free. For alphabets of two symbols, however, there do exist infinite cube-free words, words with no substring of the form. 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 for which there exists an infinite -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 be the number of symbols in an alphabet. For every, define, the repeat threshold, to be the infimum of exponents such that there exists an infinite -power-free word on a -symbol alphabet. 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 is finite for all. Then Dejean's conjecture is that the repeat threshold can be calculated by the simple formula except in two exceptional cases: and
Progress and proof
Dejean herself proved the conjecture for. The case 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. This analysis was extended up to 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. 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 is called a Dejean word. Thus, for instance, the Thue–Morse sequence is a Dejean word.
