Ochem's exponential growth conjecture for threshold languages

About 7 years old · traced to

For every integer n≥2n\geq 2, let An={1,2,…,n}A_n=\{\texttt{1},\texttt{2},\dots,\texttt{n}\} and let TnT_n be the language of all RT⁡(n)+\operatorname{RT}(n)^+-free words over AnA_n, where RT⁡(n)\operatorname{RT}(n) is the repetition threshold for nn letters. Ochem's conjecture. For every n≥3n\geq 3, the language TnT_n of threshold words of order nn grows exponentially. The case n=2n=2 is exceptional: T2T_2 is the language of overlap-free binary words and has polynomial growth. This conjecture has been established for all n∉{12,14,…,26}n\notin\{12,14,\dots,26\} in the source, leaving the listed cases unresolved there.

References

Primary source

James D. Currie, Lucas Mol and Narad Rampersad, “The Number of Threshold Words on n Letters Grows Exponentially for Every n27”, arXiv:1911.05779 (2019).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.