2021/04/20 by Matthieu Rosenfeld, Rosenfeld, Matthieu · 1 citation
Computer Science · #Algorithms and Data Compression #Coding theory and cryptography #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #semigroups and automata theory
paper · doi:10.48550/arxiv.2104.09965
openalex publication_date 2021/04/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In 2007, Grytczuk conjecture that for any sequence (ℓi)i≥1 of alphabets of size 3 there exists a square-free infinite word w such that for all i, the i-th letter of w belongs to ℓi. The result of Thue of 1906 implies that there is an infinite square-free word if all the ℓi are identical. On the other, hand Grytczuk, Przybyło and Zhu showed in 2011 that it also holds if the ℓi are of size 4 instead of 3. In this article, we first show that if the lists are of size 4, the number of square-free words is at least 2.45n (the previous similar bound was 2n). We then show our main result: we can construct such a square-free word if the lists are subsets of size 3 of the same alphabet of size 4. Our proof also implies that there are at least 1.25n square-free words of length n for any such list assignment. This proof relies on the existence of a set of coefficients verified with a computer. We suspect that the full conjecture could be resolved by this method with a much more powerful computer (but we might need to wait a few decades for such a computer to be available).