Difference between revisions of "Sesquipower"
(Start article: Sesquipower) |
(→References: isbn) |
||
| (2 intermediate revisions by one other user not shown) | |||
| Line 4: | Line 4: | ||
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. 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. 136</ref> | 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. 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. 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 | A '''bi-ideal sequence''' is a sequence of words $f_i$ where $f_1 \in A^+$ and | ||
| Line 11: | Line 13: | ||
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 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 | + | 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. 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 | 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_2 g_2 \cdots \ . | + | \mathbf{f} = f_1 g_1 f_2 g_2 \cdots \ . |
$$ | $$ | ||
| Line 23: | Line 25: | ||
==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 | + | <references/> |
| − | * 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}} | + | * 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}} |
| − | * 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}} | + | * 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}} |
| − | * Sapir, Mark V., "Combinatorial algebra: syntax and semantics" Springer Verlag (2014) ISBN 978-3-319-08030-7 | + | * 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}} | ||
Latest revision as of 14:15, 12 November 2023
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$.[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
- 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
Sesquipower. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Sesquipower&oldid=38954