Paper detail

Crucial words for abelian powers

A word is &#34;crucial&#34; with respect to a given set of &#34;prohibited words&#34; (or simply &#34;prohibitions&#34;) if it avoids the prohibitions but it cannot be extended to the right by any letter of its alphabet without creating a prohibition. A &#34;minimal crucial word&#34; is a crucial word of the shortest length. A word W contains an &#34;abelian k-th power&#34; if W has a factor of the form X_1X_2...X_k where X_i is a permutation of X_1 for 2<= i <= k. When k=2 or 3, one deals with &#34;abelian squares&#34; and &#34;abelian cubes&#34;, respectively. In 2004 (arXiv:math/0205217), Evdokimov and Kitaev showed that a minimal crucial word over an n-letter alphabet A_n = {1,2,..., n} avoiding abelian squares has length 4n-7 for n >= 3. In this paper we show that a minimal crucial word over A_n avoiding abelian cubes has length 9n-13 for n >= 5, and it has length 2, 5, 11, and 20 for n=1, 2, 3, and 4, respectively. Moreover, for n >= 4 and k >= 2, we give a construction of length k^2(n-1)-k-1 of a crucial word over A_n avoiding abelian k-th powers. This construction gives the minimal length for k=2 and k=3. For k >= 4 and n >= 5, we provide a lower bound for the length of crucial words over A_n avoiding abelian k-th powers.