2018/03/21 by Currie, James D., Mol, Lucas, Rampersad, Narad
#68R15 #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.1803.08145
A word is called β-free if it has no factors of exponent greater than or equal to β. The repetition threshold RT(k) is the infimum of the set of all β such that there are arbitrarily long k-ary β-free words (or equivalently, there are k-ary β-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 β such that - there are arbitrarily long k-ary β-free circular words is called the weak circular repetition threshold, denoted CRTW(k); - there are k-ary β-free circular words of every sufficiently large length is called the intermediate circular repetition threshold, denoted CRTI(k); - there are k-ary β-free circular words of every length is called the strong circular repetition threshold, denoted CRTS(k). We prove that CRTS(4)=\tfrac32 and CRTS(5)=\tfrac43, confirming a conjecture of Gorbunova and providing the last unknown values of the strong circular repetition threshold. We also prove that CRTI(3)=CRTW(3)=RT(3)=\tfrac74.