Low complexity binary words avoiding (5/2)⁺-powers

2025/06/23 by James D. Currie, Narad Rampersad, Currie, James +1
Computer Science · Engineering · #68R15 #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #graph theory and CDMA systems #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2506.19050

openalex publication_date 2025/06/23 · openalex created_date 2025/10/01 · openalex updated_date 2026/08/01

Abstract

Rote words are infinite words that contain 2n factors of length n for every n ≥ 1. Shallit and Shur, as well as Ollinger and Shallit, showed that there are Rote words that avoid (5/2)⁺-powers and that this is best possible. In this note we give a structure theorem for the Rote words that avoid (5/2)⁺-powers, confirming a conjecture of Ollinger and Shallit.

Citations

• Words with factor complexity 2n+1 and minimal critical exponent
• The Repetition Threshold for Rote Sequences
• Critical exponent of binary words with few distinct palindromes
• Properties of a Ternary Infinite Word
• Fife's Theorem Revisited
• Polynomial versus Exponential Growth in Repetition-Free Binary Words

Related

• The Repetition Threshold for Rote Sequences
• The repetition threshold for ternary rich words
• Infinite words containing squares at every position
• Growth rate of binary words avoiding xxx^R
• Avoiding abelian and additive powers in rich words