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.


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

Topic revision: r1 - 2011-07-20 - JeffreyShallit
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback