Conjecture on the maximum length of rich square-free words

Let r(n)r(n) be the maximum length of a rich square-free word over an alphabet of size nn, and let wnw_n be the recursively constructed rich square-free word over an alphabet of size nn. Conjecture. For every n1n\geq 1,

r(n)=maxwn,2wn1+1.r(n)=\operatorname{max}\\{|w_n|,2\cdot|w_{n-1}|+1\\}.

This conjecture asserts that the maximum length is the larger of the length of the paper's recursively constructed word and the length obtained from the basic recursion. The computed values for n=7,8,9,10n=7,8,9,10 motivate the conjecture, but the exact values for n=8n=8 and n=9n=9 were not computable in the paper.

Sources & referencesView supporting material

Primary source

Jetro Vesti, “Rich square-free words”, arXiv:1603.01058 (2016).

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.