2006/08/24 by Jui-Yi Kao, Narad Rampersad, Kao, Jui-Yi +5
Computer Science · Mathematics · #68R15 #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #FOS: Mathematics #History and Theory of Mathematics #math.CO #msc:68R15 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.math/0608607
18 pages; Manuel Silva added as a co-author
openalex publication_date 2006/08/24 · arxiv created 2006/09/12 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Carpi constructed an infinite word over a 4-letter alphabet that avoids squares in all subsequences indexed by arithmetic progressions of odd difference. We show a connection between Carpi's construction and the paperfolding words. We extend Carpi's result by constructing uncountably many words that avoid squares in arithmetic progressions of odd difference. We also construct infinite words avoiding overlaps and infinite words avoiding arbitrarily large squares in arithmetic progressions of odd difference. We use these words to construct labelings of the 2-dimensional integer lattice such that any line through the lattice encounters a squarefree (resp. overlapfree) sequence of labels.