The nonchalant-word infinitude conjecture

About 7 years old · traced to

Fix an ordered alphabet An={1,2,…,n}\mathbb A_n=\{\mathtt{1,2,\dots,n}\}. Define nonchalant words recursively by N1=1N_1=\mathtt 1 and Ni+1=Ni′xNi”N_{i+1}=N_i'xN_i”, where this is a square-free extension of NiN_i, Ni”N_i” is the shortest possible suffix of NiN_i, and x∈Anx\in\mathbb A_n is the earliest possible letter.

Nonchalant-word infinitude conjecture. The sequence of nonchalant words over An\mathbb A_n is infinite for every n⩾3n\geqslant 3.

The conjecture asserts that the greedy construction never stops. Computer experiments support it, including a ternary nonchalant word of length 1000010000, but the general claim remains open.

References

Primary source

Jarosław Grytczuk, Hubert Kordulewski and Bartłomiej Pawlik, “Square-free extensions of words”, arXiv:2104.04841 (2021).

Additional references

2 papers in this index state this conjecture (2019–2021). The statement above is taken from the most recent of them; the others are arXiv:1910.06226.

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.