Abelian repetition threshold revisited (Q2097234): Difference between revisions

The authors ``present a method of study of abelian power-free languages using random walks in prefix trees and some experimental results obtained by this method.'' Two words are A-equivalent (from abelian) if they are anagrams of each other. A-repetition in a word is a pair of A-equivalent factors. These are called A-squares if they are adjacent. A-cubes and \(k^{\mathrm{th}}\)-A-powers, and even \(\left(\frac{m}{n}\right)^{\mathrm{th}}\)-A-powers can be defined in a similar way. A word is \(\alpha\)-free if it contains no \(\left(\frac{m}{n}\right)^{\mathrm{th}}\)-powers with \(\frac{m}{n} \geq \alpha\). In a similar way \(\alpha\)-A-free words can be defined too. The \textit{repetition threshold} is defined as: \(\operatorname{RT}(k) = \inf\{\alpha: \text{there exists an infinite \(k\)-ary \(\alpha\)-free word}\}\). A similar definition can be given for the \textit{A-repetition threshold} \(\operatorname{ART}(k)\). Starting from a conjecture of \textit{A. V. Samsonov} and \textit{A. M. Shur} [RAIRO, Theor. Inform. Appl. 46, No. 1, 147--163 (2012; Zbl 1279.68240)], the authors state and discuss in detail the following conjecture: \[\operatorname{ART}(2) > 11/3;\quad 2 < \operatorname{ART}(3) \leq 5/2; \quad \operatorname{ART}(4) > 9/5;\] \[\operatorname{ART}(5) = 3/2;\quad 4/3 <\operatorname{ART}(6) < 3/2; \quad\operatorname{ART}(k) = \frac{k-3}{k-4} \text{ for } k \geq 7,\] that was justified by a series of experiments based on algorithms presented in the paper. By refining the conjecture, precise values were suggested for smaller \(k\). For the entire collection see [Zbl 1498.68013].