Namespaces
Variants
Actions

Sesquipower

From Encyclopedia of Mathematics
Jump to: navigation, search

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

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$.[2]

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]

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

  1. Lothaire (2011) p. 135
  2. 2.0 2.1 Lothaire (2011) p. 136
  3. Lothaire (2011) p. 137
  4. Berstel et al (2009) p.132
  5. 5.0 5.1 Lothiare (2011) p. 141
  6. 6.0 6.1 Berstel et al (2009) p.133
  7. Lothaire (2011) p. 30
  • 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
How to Cite This Entry:
Sesquipower. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Sesquipower&oldid=39622