# Sesquipower

2010 Mathematics Subject Classification: Primary: 68R15 [MSN][ZBL]

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.

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

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

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.

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

How to Cite This Entry:
Sesquipower. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Sesquipower&oldid=39622