There exist infinite cube-free words over any sequence of binary alphabets

2025/12/03 by Vuong Bui, Bui, Vuong, Matthieu Rosenfeld +1
Computer Science · #Cellular Automata and Applications #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #FOS: Mathematics #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2512.03670

openalex publication_date 2025/12/03 · openalex created_date 2025/12/05 · openalex updated_date 2026/07/28

Abstract

We prove that for any sequence of binary alphabets A₁,A₂,…, there exists a cube-free word c₁c₂… so that c₁\inA₁,c₂\inA₂,…. In particular, for every n, there are at least 1.35ⁿ cube-free words in A₁\timesA₂×…× A_n. We also prove that if the list of alphabets is computable then one of these words is computable and its nth letter can be computed in time polynomial in n.

Citations

• Local obstructions in sequences revisited
• Ann wins the nonrepetitive game over four letters and the erase-repetition game over six letters
• Avoiding squares over words with lists of size three amongst four symbols
• The Thue choice number versus the Thue chromatic number of graphs

Related

• Cubefree binary words avoiding long squares
• Cubefree words with many squares
• Avoiding squares over words with lists of size three amongst four symbols
• Counting ternary square-free words quickly
• Fewest repetitions in infinite binary words