2010/12/02 by Elyot Grant, Grant, Elyot
Computer Science · Engineering · Mathematics · #05D99 #Coding theory and cryptography #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.1 #acm:05D99 #cs.DM #graph theory and CDMA systems #math.CO #msc:05D99 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1012.0524
5 pages
arxiv created 2010/12/02 · openalex publication_date 2010/12/02 · arxiv updated 2010/12/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A finite word w is an abelian square if w = xx^′ with x^′ a permutation of x. In 1972, Entringer, Jackson, and Schatz proved that every binary word of length k2 + 6k contains an abelian square of length ≥ 2k. We use Cartesian lattice paths to characterize abelian squares in binary sequences, and construct a binary word of length q(q+1) avoiding abelian squares of length ≥ 2√(2q(q+1)) or greater. We thus prove that the length of the longest binary word avoiding abelian squares of length 2k is Θ(k2).