The subword complexity of polynomial subsequences of the Thue–Morse sequence
Let $\mathbf{t}=(t(n))_{n\geqslant 0}$ be the Thue–Morse sequence in $0,1$. J.-P. Allouche and J. Shallit asked in 2003 whether the subword complexity of the subsequence $(t(n^2))_{n\geqslant 0}$ attains the maximal value. This problem was solved positively by Y. Moshe in 2007. Indeed Y. Moshe had s...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Académie des sciences
2022-05-01
|
| Series: | Comptes Rendus. Mathématique |
| Online Access: | https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.5802/crmath.321/ |
| Summary: | Let $\mathbf{t}=(t(n))_{n\geqslant 0}$ be the Thue–Morse sequence in $0,1$. J.-P. Allouche and J. Shallit asked in 2003 whether the subword complexity of the subsequence $(t(n^2))_{n\geqslant 0}$ attains the maximal value. This problem was solved positively by Y. Moshe in 2007. Indeed Y. Moshe had shown that for all $H\in \mathbb{Q}[T]$ with $H(\mathbb{N})\subseteq \mathbb{N}$ and $\deg H=2$, all the subsequences $(t(H(n)))_{n\geqslant 0}$ attain the maximal subword complexity. Then he asked whether the same result holds for $\deg H\geqslant 3$. In this work, we shall give a positive answer to the above problem. |
|---|---|
| ISSN: | 1778-3569 |