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