Abstract
Let k≥2k≥2 be an integer. An abelian kkth power is a word of the form X1X2⋯XkX1X2⋯Xk where XiXi is a permutation of X1X1 for 2≤i≤k2≤i≤k. A word WW is said to be crucial with respect to abelian kkth powers if WW avoids abelian kkth powers, but WxWx ends with an abelian kkth power for any letter xx occurring in WW.
Evdokimov and Kitaev (2004) [2] have shown that the shortest length of a crucial word on nn letters avoiding abelian squares is 4n−74n−7 for n≥3n≥3. Furthermore, Glen et al. (2009) [3] proved that this length for abelian cubes is 9n−139n−13 for n≥5n≥5. They have also conjectured that for any k≥4k≥4 and sufficiently large nn, the shortest length of a crucial word on nn letters avoiding abelian kkth powers, denoted by ℓk(n)ℓk(n), is k2n−(k2+k+1)k2n−(k2+k+1). This is currently the best known upper bound for ℓk(n)ℓk(n), and the best known lower bound, provided in Glen et al., is 3kn−(4k+1)3kn−(4k+1) for n≥5n≥5 and k≥4k≥4. In this note, we improve this lower bound by proving that for n≥2k−1n≥2k−1, ℓk(n)≥k2n−(2k3−3k2+k+1)ℓk(n)≥k2n−(2k3−3k2+k+1); thus showing that the aforementioned conjecture is true asymptotically (up to a constant term) for growing nn.
Evdokimov and Kitaev (2004) [2] have shown that the shortest length of a crucial word on nn letters avoiding abelian squares is 4n−74n−7 for n≥3n≥3. Furthermore, Glen et al. (2009) [3] proved that this length for abelian cubes is 9n−139n−13 for n≥5n≥5. They have also conjectured that for any k≥4k≥4 and sufficiently large nn, the shortest length of a crucial word on nn letters avoiding abelian kkth powers, denoted by ℓk(n)ℓk(n), is k2n−(k2+k+1)k2n−(k2+k+1). This is currently the best known upper bound for ℓk(n)ℓk(n), and the best known lower bound, provided in Glen et al., is 3kn−(4k+1)3kn−(4k+1) for n≥5n≥5 and k≥4k≥4. In this note, we improve this lower bound by proving that for n≥2k−1n≥2k−1, ℓk(n)≥k2n−(2k3−3k2+k+1)ℓk(n)≥k2n−(2k3−3k2+k+1); thus showing that the aforementioned conjecture is true asymptotically (up to a constant term) for growing nn.
Original language | English |
---|---|
Pages (from-to) | 605-607 |
Number of pages | 3 |
Journal | Discrete Applied Mathematics |
Volume | 158 |
Issue number | 6 |
DOIs | |
Publication status | Published - 28 Mar 2010 |
Keywords
- pattern avoidance
- abelian powers
- crucial word