Dejean's Conjecture

A finite or infinite word
a1a2a3a4...
is said to have period p if
ai=ai+p for each i.
For example, abcabcabcabcab has periods 3, 6, 9 and 12.

If word w has length l and period p, then w is a k-power, where k=l/p. For example, eraser is a 3/2-power. An infinite word over a unary alphabet contains k-powers for arbitrarily large k. On the other hand, Thue constructed an infinite binary word avoiding any k-powers with k>2. The repetitive threshold over an n-letter alphabet is

RT(n)=inf{k: some infinite word over an n-letter alphabet avoids k-powers.}
Dejean's conjecture (DC) was published in 1972, but is only now finally close to solution. She conjectured that for positive integer n>1:
RT(n) =
7/4, n =3
7/5, n = 4
n/(n-1), n ≠ 3, 4
Several authors have chipped away at this problem, and recently Carpi reduced its resolution to establishing finitely many cases. The current state of knowledge is as follows:

Values of n State of DC Result by Date
2ConfirmedThue1906
3ConfirmedDejean1972
4ConfirmedPansiot1984
5 ≤ n ≤ 11ConfirmedMoulin-Ollagnier1992
12 ≤ n ≤ 14ConfirmedCurrie, Mohammad-Noori2004
15 ≤ n ≤ 26Open??
27 ≤ n ≤ 32ConfirmedCurrie, Rampersad2008
33 ≤ nConfirmedCarpi2007

Evidently, the task now is to chip away at the gap from 15 to 29. It is quite conceivable that the methods of [4,7,8] may be sharpened to do this, eventually resolving this important conjecture.

News Flash: Dejean's conjecture has been solved! See papers by Currie and Rampersad and Rao for details.

Bibliography

  1. Berstel, J. (1995). Axel Thue's papers on repetitions in words: a translation. In: Publications du LaCIM, vol. 20. Universite du Quebec a Montreal.
  2. F. J. Brandenburg, Uniformly growing k-th powerfree homomorphisms, Theoret. Comput. Sci. 23 (1983), 69 – 82.
  3. J. Brinkhuis, Non-repetitive sequences on three symbols, Quart. J. Math. Oxford (2) 34 (1983), 145 – 149.
  4. A. Carpi, On Dejean's conjecture over large alphabets, Theor. Comput. Sci. 385 (2007), 137 – 151.
  5. J. Currie, N. Rampersad, Dejean's conjecture holds for n ≥ 27, preprint (Click here.)
  6. Françoise Dejean, Sur un théorème de Thue, J. Combin. Theory Ser. A 13 (1972), 90 – 99.
  7. M. Mohammad-Noori, J. D. Currie, Dejean's conjecture and Sturmian words, Euro. J. Combin. 28 (2007), 876 – 890.
  8. Jean Moulin-Ollagnier, Proof of Dejean's conjecture for alphabets with 5, 6, 7, 8, 9, 10 and 11 letters, Theoret. Comput. Sci. 95 (1992), 187 – 205.
  9. Jean-Jacques Pansiot, A propos d'une conjecture de F. Dejean sur les répétitions dans les mots, Discrete Appl. Math. 7 (1984) 297 – 311.
  10. A. Thue, Über unendliche Zeichenreihen, Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiana No. 7 (1906).
  11. A. Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiana (1912), 1 – 67.