### Abstract

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 |

### Fingerprint

### Keywords

- pattern avoidance
- abelian powers
- crucial word

### Cite this

*Discrete Applied Mathematics*,

*158*(6), 605-607. https://doi.org/10.1016/j.dam.2009.11.010

}

*Discrete Applied Mathematics*, vol. 158, no. 6, pp. 605-607. https://doi.org/10.1016/j.dam.2009.11.010

**On shortest crucial words avoiding abelian powers.** / Avgustinovich, Sergey; Glen, Amy; Halldorsson, Bjarni; Kitaev, Sergey.

Research output: Contribution to journal › Article

TY - JOUR

T1 - On shortest crucial words avoiding abelian powers

AU - Avgustinovich, Sergey

AU - Glen, Amy

AU - Halldorsson, Bjarni

AU - Kitaev, Sergey

PY - 2010/3/28

Y1 - 2010/3/28

N2 - 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.

AB - 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.

KW - pattern avoidance

KW - abelian powers

KW - crucial word

UR - https://personal.cis.strath.ac.uk/sergey.kitaev/index_files/Papers/AGHK.pdf

U2 - 10.1016/j.dam.2009.11.010

DO - 10.1016/j.dam.2009.11.010

M3 - Article

VL - 158

SP - 605

EP - 607

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - 6

ER -