Sesquipower

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

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