Crucial abelian k-power-free words
Amy Glen, Bjarni Halldórsson, Sergey Kitaev
Abstract
In 1961, Erdős asked whether or not there exist words of
arbitrary
length over a fixed finite alphabet that avoid patterns of the form
XX'
where X' is a permutation of X (called
abelian
squares). This problem has since been solved in the affirmative
in
a series of papers from 1968 to 1992. Much less is known in the case
of
abelian k-th powers, i.e., words of the form
X1X2⋯Xk
where Xi is a permutation of
X1
for 2 ≤i ≤k. In this paper, we consider
crucial
words for abelian k-th powers, i.e., finite words
that
avoid abelian k-th powers, but which cannot be extended
to
the right by any letter of their own alphabets without creating an
abelian
k-th power. More specifically, we consider the problem of
determining
the minimal length of a crucial word avoiding abelian
k-th
powers. This problem has already been solved for abelian squares by
Evdokimov
and Kitaev (2004), who showed that a minimal crucial word over an
n-letter alphabet
An = {1,2,…,
n}
avoiding abelian squares has length 4n-7 for
n≥3.
Extending this result, we prove that a minimal crucial word over
An
avoiding abelian cubes has length 9n-13 for
n≥5,
and it has length 2, 5, 11, and 20 for n=1,2,3, and 4,
respectively.
Moreover, for n≥4 and k≥2, we
give
a construction of length k2(n-1)-k-1 of a
crucial
word over An avoiding
abelian
k-th powers. This construction gives the minimal length
for
k=2 and k=3. For k ≥4
and
n≥5, we provide a lower bound for the length of
crucial
words over An avoiding
abelian
k-th powers.
Full Text: PDF PostScript