View source for Sesquipower

{{TEX|done}}{{MSC|68R15}}

A '''sesquipower''' or '''Zimin word''' is a string over an alphabet with identical prefix and suffix.  Sesquipowers are [[unavoidable pattern]]s, in the sense that all sufficiently long strings contain one.

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$.<ref name=LotII135>Lothaire (2011) p.&nbsp;135</ref>  The ''degree'' of a non-empty word $w$ is the largest integer $d$ such that $w$ is a sesquipower of order $d$'.<ref name=LotII136>Lothaire (2011) p.&nbsp;136</ref>

The Zimin words $Z_n$ over the alphabet $\{x_1,\ldots,x_n\}$ are defined by $Z_1 = x_1$ and $Z_n = Z_{n-1} x_n Z_{n-1}$ for $n>1$.  The infinite Zimin word $\mathbf{Z}$ may be defined as the word whose $i$-th position, for $i\ge 1$, contains $x_{j+1}$ where $2^j$ is the largest power of 2 dividing $i$.  Each $Z_n$ is the initial segment of $\mathbf{Z}$ of length $2^n-1$.

A '''bi-ideal sequence''' is a sequence of words $f_i$ where $f_1 \in A^+$ and
$$
f_{i+1} = f_i g_i f_i
$$
for some $g_i \in A^*$ and $i \ge 1$.  The degree of a word $w$ is thus the length of the longest bi-ideal sequence ending in $w$.<ref name=LotII136/>

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 pattern]]s''.<ref name=LotII137>Lothaire (2011) p.&nbsp;137</ref><ref name=BLRS132>Berstel et al (2009) p.132</ref>

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
$$
\mathbf{f} = f_1 g_1 f_2 g_2 \cdots \ . 
$$

We define an infinite word to be a sesquipower if is the limit of an infinite bi-ideal sequence.<ref name=LotII141>Lothiare (2011) p.&nbsp;141</ref>  An infinite word is a sesquipower if and only if it is a [[recurrent word]],<ref name=LotII141/><ref name=BLRS133/> that is, every factor occurs infinitely often.<ref name=LotII30>Lothaire (2011) p.&nbsp;30</ref>

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$-[[Monoid factorisation|factorisation]] into [[Lyndon word]]s.<ref name=BLRS133>Berstel et al (2009) p.133</ref>

==References==
<references/>
* Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V.; "Combinatorics on words. Christoffel words and repetitions in words", CRM Monograph Series '''27''', American Mathematical Society (2009) {{ISBN|978-0-8218-4480-9}}  {{ZBL|1161.68043}} 
* Lothaire, M.; "Algebraic combinatorics on words", Encyclopedia of Mathematics and Its Applications '''90''' Cambridge University Press (2011) {{ISBN|978-0-521-18071-9}} {{ZBL|1221.68183}} 
* Pytheas Fogg, N.; "Substitutions in dynamics, arithmetics and combinatorics", Lecture Notes in Mathematics '''1794''' Springer-Verlag (2002) {{ISBN|3-540-44141-7}} {{ZBL|1014.11015}}
* Sapir, Mark V., "Combinatorial algebra: syntax and semantics" Springer Verlag (2014) {{ISBN|978-3-319-08030-7}}