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]
Context
In the study of strings, concatenation is seen as analogous to multiplication of numbers. So, for instance, if s is any string, then the concatenation \( {\displaystyle 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 e is a non-negative rational number of the form \( {\displaystyle n/\ell } \), then \( {\displaystyle s^{e}} \) denotes the string formed by the first n characters of the infinite repetition \( {\displaystyle sssss\dots } \).[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 \( {\displaystyle 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.[1]
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;[2] this formula is Dejean's conjecture, now a theorem.[1]
Statement
Let k {\displaystyle k} k be the number of symbols in an alphabet. For every k, define \( {\displaystyle \operatorname {RT} (k)} \), the repeat threshold, to be the infimum of exponents e such that there exists an infinite e {\displaystyle e} e-power-free word on a k-symbol alphabet. Thus, for instance, the Thue–Morse sequence shows that \( {\displaystyle \operatorname {RT} (2)=2} \), and an argument based on the Lovász local lemma can be used to show that \( {\displaystyle \operatorname {RT} (k)} \) is finite for all k.[1]
Then Dejean's conjecture is that the repeat threshold can be calculated by the simple formula[1][2]
\( {\displaystyle \operatorname {RT} (k)={\frac {k}{k-1}}} \)
except in two exceptional cases:
\( {\displaystyle \operatorname {RT} (3)={\frac {7}{4}}} \)
and
\( {\displaystyle \operatorname {RT} (4)={\frac {7}{5}}.} \)
Progress and proof
Dejean herself proved the conjecture for k=3.[2] The case k=4 was proven by Jean-Jacques Pansiot in 1984.[3] The next progress was by Moulin Ollagnier in 1992, who proved the conjecture for all alphabet sizes up to \( {\displaystyle k\leq 11} \).[4] This analysis was extended up to \( {\displaystyle k\leq 14} \) in 2007 by Mohammad-Noori and Currie.[5]
In the other direction, also in 2007, Arturo Carpi showed the conjecture to be true for large alphabets, with \( {\displaystyle k\geq 33} \) .[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]
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
Rampersad, Narad; Shallit, Jeffrey (2016), "Repetitions in words", Combinatorics, words and symbolic dynamics, Encyclopedia Math. Appl., 159, Cambridge Univ. Press, Cambridge, pp. 101–150, MR 3525483
Dejean, Françoise (1972), "Sur un théorème de Thue", Journal of Combinatorial Theory, Series A, 13: 90–99, doi:10.1016/0097-3165(72)90011-8, MR 0300959
Pansiot, Jean-Jacques (1984), "À propos d'une conjecture de F. Dejean sur les répétitions dans les mots", Discrete Applied Mathematics, 7 (3): 297–311, doi:10.1016/0166-218x(84)90006-4, MR 0736893
Moulin Ollagnier, Jean (1992), "Proof of Dejean's conjecture for alphabets with 5, 6, 7, 8, 9, 10 and 11 letters", Theoretical Computer Science, 95 (2): 187–205, doi:10.1016/0304-3975(92)90264-G, MR 1156042
Mohammad-Noori, M.; Currie, James D. (2007), "Dejean's conjecture and Sturmian words", European Journal of Combinatorics, 28 (3): 876–890, doi:10.1016/j.ejc.2005.11.005, MR 2300768
Carpi, Arturo (2007), "On Dejean's conjecture over large alphabets", Theoretical Computer Science, 385 (1–3): 137–151, doi:10.1016/j.tcs.2007.06.001, MR 2356248
Currie, James; Rampersad, Narad (2011), "A proof of Dejean's conjecture", Mathematics of Computation, 80 (274): 1063–1070, arXiv:0905.1129, doi:10.1090/S0025-5718-2010-02407-X, MR 2772111
Rao, Michaël (2011), "Last cases of Dejean's conjecture", Theoretical Computer Science, 412 (27): 3010–3018, doi:10.1016/j.tcs.2010.06.020, MR 2830264
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
