Namespaces
Variants
Actions

Difference between revisions of "Sesquipower"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Expand, cite Sapir)
 
(One intermediate revision by one other user not shown)
Line 13: 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 patterns''.<ref name=LotII137>Lothaire (2011) p.&nbsp;137</ref><ref name=BLRS132>Berstel et al (2009) p.132</ref>
+
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.&nbsp;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
Line 26: Line 26:
 
==References==
 
==References==
 
<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 978-0-8218-4480-9  {{ZBL|1161.68043}}  
+
* 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}}  
+
* 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}}
+
* 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
+
* 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

  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=38957