Dejean's conjecture (now a theorem) states that the largest power avoidable over a k-letter alphabet is given by RT(k), and RT(2) = 2, RT(3) = 7/4, RT(4) = 7/5, and RT(k) = k/(k-1) for k ≥ 5.

How many words of length n are there that avoid RT(k)⁺ powers? For k = 2 it is known that this number is bounded by a polynomial in n, and the same is true for exponents ≤ 7/3. For k = 3, 4 Ochem has proven that there are exponentially many words avoiding RT(k)⁺ powers. Kolpakov and Rao have announced a proof for 5 ≤ k ≤ 10. The cases k ≥ 11 seem to be open.

References:

A. M. Shur, Growth properties of power-free languages, in G. Mauri and A. Leporati, eds., Developments in Language Theory, 15th International Conference, DLT 2011, Lect. Notes in Comp. Sci., Vol. 6795, Springer, 2011, pp. 28-43.

-- JeffreyShallit - 20 Jul 2011