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 sequipower of order n then any word w = uvu is a sesquipower of order n + 1.^[1] The degree of a non-empty word w is the largest integer d such that w is a sesquipower of order d.^[2]

Bi-ideal sequence

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

f_{{i+1}}=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.^[2]

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.^[3]^[4]

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 is the limit of an infinite bi-ideal sequence.^[5] An infinite word is a sesquipower if and only if it is a recurrent word,^[5]^[6] that is, every factor occurs infinitely often.^[7]

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.^[6]

References

↑ Lothaire (2011) p. 135
1 2 Lothaire (2011) p. 136
↑ Lothaire (2011) p. 137
↑ Berstel et al (2009) p.132
1 2 Lothiare (2011) p. 141
1 2 Berstel et al (2009) p.133
↑ Lothaire (2011) p. 30

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. Zbl 1161.68043.
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. Zbl 1221.68183.
Pytheas Fogg, N. (2002). Substitutions in dynamics, arithmetics and combinatorics. Lecture Notes in Mathematics. 1794. Editors Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. Berlin: Springer-Verlag. ISBN 3-540-44141-7. Zbl 1014.11015.

This article is issued from Wikipedia - version of the 6/30/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.