Dejean's conjecture concerns repetitions in infinite words. A

*square*is a repetition of the form

*xx*, where

*x*is a nonempty word. We can write this in shorthand as

*x*

^{2}. Examples of squares include the English word

`hotshots`and the French word

`chercher`. A

*cube*is a repetition of the form

*xxx*; the only example I know of in English is the sort-of-word

`shshsh`. About a hundred years ago, the Norwegian mathematician Axel Thue gave examples of an infinite word over a 2-letter alphabet containing no cubes and an infinite word over a 3-letter alphabet containing no squares. It is easy to see that there are no infinite words without squares over a 2-letter alphabet, or cubes over a 1-letter alphabet.

More generally, one can try to avoid rational powers, not just integer powers. We say a string

*w*is a

*p*/

*q*power if it can be written in the form

*x*

^{k}

*x'*where

*x'*is a prefix of

*x*and the length of

*w*is

*p*/

*q*times the length of

*x*. For example, the French word

`entente`is a 7/3 power, as it can be written in the form

`(ent)`

^{2}

`e`. Similarly,

`entanglement`is a 4/3 power.

Dejean's conjecture concerns the largest possible exponent

*e*such that there exists no infinite word over a

*k*-letter alphabet avoiding powers of exponent

*e*or greater. We write this exponent as RT(

*k*), where RT stands for "repetitive threshold". Thue proved that RT(2) = 2. In 1972, Françoise Dejean proved that RT(3) = 7/4. She conjectured that RT(4) = 7/5 (which was later proved by Pansiot) and RT(

*k*) =

*k*/(

*k*-1) for

*k*≥ 5.

Over the last 35 years the range of exponents for which Dejean's conjecture was known to hold slowly increased. Moulin Ollagnier proved the conjecture for 5 ≤

*k*≤ 11; Mohammad-Noori and Currie proved it for 12 ≤

*k*≤ 14. A real breakthrough occurred a couple of years ago, when Carpi proved the conjecture for all

*k*≥ 33. Currie and Rampersad then improved Carpi's construction to resolve

*k*≥ 27, and more recently they used Moulin Ollagnier's techniques to resolve the remaining cases 15 ≤

*k*≤ 26. This competely resolves Dejean's conjecture. You can read Currie and Rampersad's paper here.

At the conference we also learned that (as is often the case in mathematics and computer science) nearly simultaneously, a proof of the remaining cases along different lines has been described by Michaël Rao of the Université de Bordeaux.

So congratulations to James Currie, Narad Rampersad, and Michaël Rao for finally resolving this famous conjecture!

## 4 comments:

Very nice work! Thanks for your clear exposition of the conjecture and its history.

Exciting!

And somehow very satisfying to hear about knowledge frontiers being pushed forward.

A cube is a repetition of the form xxx; the only example I know of in English is the sort-of-word shshsh.There is a bird called a

pipipi. There is also the dance called thechachacha(though that's more usually written as three words).I don't count words that don't appear in the OED. So "pipipi" doesn't qualify. Similarly, the OED doesn't list "chachacha" as a legitimate form.

Post a Comment