Abelian Repetition Threshold Revisited

Abstract

In combinatorics on words, repetition thresholds are the numbers separating avoidable and unavoidable repetitions of a given type in a given class of words. For example, the meaning of the “classical” repetition threshold RT(k) is “every infinite k-ary word contains an α -power of a nonempty word for some α≥ RT(k) but some infinite k-ary words contain no such α -powers with α> RT(k) ”. It is well known that RT(k)=kk-1 with the exceptions for k= 3, 4. For Abelian repetition threshold ART(k), avoidance of fractional Abelian powers of words is considered. The exact values of ART(k) are unknown; the lower bound ART(2)≥113, ART(3 ) ≥ 2, ART(4)≥95, ART(k)≥k-2k-3 for all k≥ 5 was proved by Samsonov and Shur in 2012 and conjectured to be tight. We present a method of study of Abelian power-free languages using random walks in prefix trees and some experimental results obtained by this method. On the base of these results, we suggest that the lower bounds for ART(k) by Samsonov and Shur are not tight for all k except k= 5. We prove ART(k)>k-2k-3 for k= 6, 7, 8, 9, 10 and state a new conjecture on the Abelian repetition threshold. © 2022, Springer Nature Switzerland AG.