Maximum common-prefix conjecture for uniform squarefree morphisms

At least 6 years old · documented by

Let TT be the alphabet, and let an nn-uniform squarefree morphism be a morphism h:T∗→T∗h:T^*\to T^* for which every image h(a)h(a) has length nn and which maps squarefree words to squarefree words. Let lcp⁡(h)\operatorname{lcp}(h) be the length of the longest common prefix of the images {h(a):a∈T}\{h(a):a\in T\}, and let lcp⁡(n)\operatorname{lcp}(n) be the maximum value of lcp⁡(h)\operatorname{lcp}(h) over all nn-uniform squarefree morphisms h:T∗→T∗h:T^*\to T^*. Maximum common-prefix conjecture. For every n≥30n\geq 30, there exists an nn-uniform squarefree morphism h:T∗→T∗h:T^*\to T^* such that lcp⁡(h)=n−6\operatorname{lcp}(h)=n-6. The computed values for 18≤n≤7018\leq n\leq 70 suggest this conjecture; its validity for all n≥30n\geq 30 remains open.

References

Primary source

James Currie, Tero Harju, Pascal Ochem and Narad Rampersad, “Some further results on squarefree arithmetic progressions in infinite words”, arXiv:1901.06351 (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.