| Popis: |
Let k>=2 be an integer. An abeliankth power is a word of the form X"1X"2...X"k where X"i is a permutation of X"1 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 Wx 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 4n-7 for n>=3. Furthermore, Glen et al. (2009) [3] proved that this length for abelian cubes is 9n-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 k^2n-(k^2+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 3kn-(4k+1) for n>=5 and k>=4. In this note, we improve this lower bound by proving that for n>=2k-1, @?"k(n)>=k^2n-(2k^3-3k^2+k+1); thus showing that the aforementioned conjecture is true asymptotically (up to a constant term) for growing n. |
Full Text from ScienceDirect