Dejean's Conjecture Solved!

Dejean's conjecture is one of the oldest conjectures in combinatorics on words. Yesterday, at the CANADAM conference in Montréal (where I also gave a talk), James Currie and my former Ph. D. student Narad Rampersad announced the final step in the proof of this famous conjecture. That's Narad at the left and James on the right. (Photo courtesy of Amy Glen.)



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². 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^kx' 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)²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!