The nonchalant-word infinitude conjecture

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=NixNiN_{i+1}=N_i'xN_i”, where this is a square-free extension of NiN_i, NiN_i” is the shortest possible suffix of NiN_i, and xAnx\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 n3n\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.

Sources & referencesView supporting material

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.