Sesquipower
# 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_1$ 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.

## 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

    $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. 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.

