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. 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-negative rational number of the form , then denotes the string formed by the first characters of the infinite repetition .[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 . 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 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;[2] this formula is Dejean's conjecture, now a theorem.[1]

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

Progress and proof

Dejean herself proved the conjecture for .[2] The case 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 .[4] This analysis was extended up to 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 .[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

  1. 1 2 3 4 5 6 7 Rampersad, Narad; Shallit, Jeffrey (2016), "Repetitions in words", Combinatorics, words and symbolic dynamics, Encyclopedia Math. Appl., vol. 159, Cambridge Univ. Press, Cambridge, pp. 101–150, MR 3525483
  2. 1 2 3 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.