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. The degree of a non-empty word w is the largest integer d such that w is a sesquipower of order d.

Bi-ideal sequence

A bi-ideal sequence is a sequence of words f_i where f₁ is in A⁺ and

[math]\displaystyle{ f_{i+1} = f_i g_i f_i \ }[/math]

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.

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

[math]\displaystyle{ f = f_1 g_1 f_1 g_2 f_1 g_1 f_1 g_3 f_1 \cdots \ }[/math]

We define an infinite word to be a sesquipower if it is the limit of an infinite bi-ideal sequence. An infinite word is a sesquipower if and only if it is a recurrent word, that is, every factor occurs infinitely often.

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.

See also

• ABACABA pattern

References

• Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009). Combinatorics on words. Christoffel words and repetitions in words. CRM Monograph Series. 27. Providence, RI: American Mathematical Society. ISBN 978-0-8218-4480-9. http://www.ams.org/bookpages/crmm-27. 
• Lothaire, M. (2011). Algebraic combinatorics on words. Encyclopedia of Mathematics and Its Applications. 90. With preface by Jean Berstel and Dominique Perrin (Reprint of the 2002 hardback ed.). Cambridge University Press. ISBN 978-0-521-18071-9. 
• Pytheas Fogg, N. (2002). Substitutions in dynamics, arithmetics and combinatorics. Lecture Notes in Mathematics. 1794. Berlin: Springer-Verlag. ISBN 3-540-44141-7.