Sesquipower

In mathematics, a sesquipower or Zimin word is a string over an alphabet with identical prefix and suffix. Sesquipowers are unavoidable patterns, in the sense that all sufficiently long strings contain one.

Formal definition

Formally, let ''A'' be an alphabet and ''A''^∗ be the free monoid of finite strings over ''A''. Every non-empty word ''w'' in ''A''⁺ is a sesquipower of order 1. If ''u'' is a sesquipower of order ''n'' then any word ''w'' = ''uvu'' is a sesquipower of order ''n'' + 1.Lothaire (2011) p. 135 The ''degree'' of a non-empty word ''w'' is the largest integer ''d'' such that ''w'' is a sesquipower of order ''d''.Lothaire (2011) p. 136

Bi-ideal sequence

A bi-ideal sequence is a sequence of words ''f''_''i'' where ''f''₁ is in ''A''⁺ and

:$f_ = f_i g_i f_i \$

for some ''g''_''i'' in ''A''^∗ and ''i'' ≥ 1. The degree of a word ''w'' is thus the length of the longest bi-ideal sequence ending in ''w''.

Unavoidable patterns

For a finite alphabet ''A'' on ''k'' letters, there is an integer ''M'' depending on ''k'' and ''n'', such that any word of length ''M'' has a factor which is a sesquipower of order at least ''n''. We express this by saying that the sesquipowers are ''unavoidable patterns''.Lothaire (2011) p. 137Berstel et al (2009) p.132

Sesquipowers in infinite sequences

Given an infinite bi-ideal sequence, we note that each ''f''_''i'' is a prefix of ''f''_''i''+1 and so the ''f''_''i'' converge to an infinite sequence

:$f = f_1 g_1 f_1 g_2 f_1 g_1 f_1 g_3 f_1 \cdots \$

We define an infinite word to be a sesquipower if it is the limit of an infinite bi-ideal sequence.Lothiare (2011) p. 141 An infinite word is a sesquipower if and only if it is a recurrent word, that is, every factor occurs infinitely often.Lothaire (2011) p. 30

Fix a finite alphabet ''A'' and assume a total order on the letters. For given integers ''p'' and ''n'', every sufficiently long word in ''A''^∗ has either a factor which is a ''p''-power or a factor which is an ''n''-sesquipower; in the latter case the factor has an ''n''- factorisation into Lyndon words.Berstel et al (2009) p.133

See also

* ABACABA pattern

References

*
*
* {{cite book , last=Pytheas Fogg , first=N. , editor1=Berthé, Valérie, editor1-link=Valérie Berthé, editor2=Ferenczi, Sébastien, editor3=Mauduit, Christian, editor4=Siegel, Anne , title=Substitutions in dynamics, arithmetics and combinatorics , series=Lecture Notes in Mathematics , volume=1794 , location=Berlin , publisher=Springer-Verlag , year=2002 , isbn=3-540-44141-7 , zbl=1014.11015

Semigroup theory
Formal languages
Combinatorics on words