On Avoiding Sufficiently Long Abelian Squares

Abstract

A finite word $w$ is an abelian square if $w=x{x}^{\prime }$ with $x^{\prime }$ a permutation of $x$. In 1972, Entringer, Jackson, and Schatz proved that every binary word of length $k^2+6k$ contains an abelian square of length $\ge 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 $\ge 2\sqrt{2q(q+1)}$ or greater. We thus prove that the length of the longest binary word avoiding abelian squares of length $2k$ is $\Theta (k^2)$.

5 pages