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