Circular repetition thresholds on some small alphabets: last cases of Gorbunova's conjecture

James D. Currie¹ ; Lucas Mol¹ ; Narad Rampersad¹

¹University of Winnipeg

The electronic journal of combinatorics, Tome 26 (2019) no. 2

Résumé

A word is called $\beta$-free if it has no factors of exponent greater than or equal to $\beta$. The repetition threshold $\mbox{RT}(k)$ is the infimum of the set of all $\beta$ such that there are arbitrarily long $k$-ary $\beta$-free words (or equivalently, there are $k$-ary $\beta$-free words of every sufficiently large length, or even every length). These three equivalent definitions of the repetition threshold give rise to three natural definitions of a repetition threshold for circular words. The infimum of the set of all $\beta$ such that there are arbitrarily long $k$-ary $\beta$-free circular words is called the weak circular repetition threshold, denoted $\mbox{CRT}_\mbox{W}(k)$; there are $k$-ary $\beta$-free circular words of every sufficiently large length is called the intermediate circular repetition threshold, denoted $\mbox{CRT}_\mbox{I}(k)$; there are $k$-ary $\beta$-free circular words of every length is called the strong circular repetition threshold, denoted $\mbox{CRT}_\mbox{S}(k)$. We prove that $\mbox{CRT}_\mbox{S}(4)=\tfrac{3}{2}$ and $\mbox{CRT}_\mbox{S}(5)=\tfrac{4}{3}$, confirming a conjecture of Gorbunova and providing the last unknown values of the strong circular repetition threshold. We also prove that $\mbox{CRT}_\mbox{S}(3)=\mbox{CRT}_\mbox{W}(3)=\mbox{RT}(3)=\tfrac{7}{4}$.

Détail

DOI : 10.37236/7985

Classification : 68R15