On shortest crucial words avoiding abelian powers

Avgustinovich, S., Glen, A., Halldórsson, B.V. and Kitaev, S. (2010) On shortest crucial words avoiding abelian powers. Discrete Applied Mathematics, 158 (6). pp. 605-607.

PDF - Authors' Version Download (149kB)

Abstract

Let k ≥ 2 be an integer. An abeliank th power is a word of the form X1 X2 ⋯ Xk where Xi is a permutation of X1 for 2 ≤ i ≤ k. A word W is said to be crucial with respect to abelian kth powers if W avoids abelian kth powers, but W x ends with an abelian kth power for any letter x occurring in W. Evdokimov and Kitaev (2004) [2] have shown that the shortest length of a crucial word on n letters avoiding abelian squares is 4 n - 7 for n ≥ 3. Furthermore, Glen et al. (2009) [3] proved that this length for abelian cubes is 9 n - 13 for n ≥ 5. They have also conjectured that for any k ≥ 4 and sufficiently large n, the shortest length of a crucial word on n letters avoiding abelian kth powers, denoted by ℓk (n), is k2 n - (k2 + k + 1). This is currently the best known upper bound for ℓk (n), and the best known lower bound, provided in Glen et al., is 3 k n - (4 k + 1) for n ≥ 5 and k ≥ 4. In this note, we improve this lower bound by proving that for n ≥ 2 k - 1, ℓk (n) ≥ k2 n - (2 k3 - 3 k2 + k + 1); thus showing that the aforementioned conjecture is true asymptotically (up to a constant term) for growing n.