On shortest crucial words avoiding abelian powers

Avgustinovich, Sergey and Glen, Amy and Halldorsson, Bjarni and Kitaev, Sergey (2010) On shortest crucial words avoiding abelian powers. Discrete Applied Mathematics, 158 (6). pp. 605-607. ISSN 0166-218X (https://doi.org/10.1016/j.dam.2009.11.010)

Full text not available in this repository.Request a copy

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.

ORCID iDs

Avgustinovich, Sergey, Glen, Amy, Halldorsson, Bjarni and Kitaev, Sergey ORCID logoORCID: https://orcid.org/0000-0003-3324-1647;
CORE (COnnecting REpositories)