Comptes Rendus
Number Theory
The subword complexity of polynomial subsequences of the Thue–Morse sequence
Zhao Shen1 
1Department of Mathematics, Tsinghua University, Beijing 100084, P. R. China
Comptes Rendus. Mathématique, Volume 360 (2022), pp. 503-511

Let t=(t(n)) n⩾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⩾0 attains the maximal value. This problem was solved positively by Y. Moshe in 2007. Indeed Y. Moshe had shown that for all H∈ℚ[T] with H(ℕ)⊆ℕ and degH=2, all the subsequences (t(H(n))) n⩾0 attain the maximal subword complexity. Then he asked whether the same result holds for degH⩾3. In this work, we shall give a positive answer to the above problem.

Soit t=(t(n)) n⩾0 la suite de Thue–Morse en 0,1. J.-P. Allouche et J. Shallit demandaient en 2003 si la complexité de facteurs de la sous-suite (t(n 2 )) n⩾0 atteint la maximale. Le problème était résolu positivement par Y. Moshe en 2007. En fait, Y. Moshe avait démontré que pour tout H∈ℚ[T] avec H(ℕ)⊆ℕ et degH=2, toutes les sous-suites (t(H(n))) n⩾0 atteignent la complexité maximale. Ensuite il demandait si le résultat est aussi valable pour degH⩾3. Dans ce travail, nous allons donner une réponse positive au problème précédent.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/crmath.321

Zhao Shen  1

1 Department of Mathematics, Tsinghua University, Beijing 100084, P. R. China
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights
Zhao Shen. The subword complexity of polynomial subsequences of the Thue–Morse sequence. Comptes Rendus. Mathématique, Volume 360 (2022), pp. 503-511. doi: 10.5802/crmath.321
@article{CRMATH_2022__360_G5_503_0,
     author = {Zhao Shen},
     title = {The subword complexity of polynomial subsequences of the {Thue{\textendash}Morse} sequence},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {503--511},
     year = {2022},
     publisher = {Acad\'emie des sciences, Paris},
     volume = {360},
     doi = {10.5802/crmath.321},
     language = {en},
}
TY  - JOUR
AU  - Zhao Shen
TI  - The subword complexity of polynomial subsequences of the Thue–Morse sequence
JO  - Comptes Rendus. Mathématique
PY  - 2022
SP  - 503
EP  - 511
VL  - 360
PB  - Académie des sciences, Paris
DO  - 10.5802/crmath.321
LA  - en
ID  - CRMATH_2022__360_G5_503_0
ER  - 
%0 Journal Article
%A Zhao Shen
%T The subword complexity of polynomial subsequences of the Thue–Morse sequence
%J Comptes Rendus. Mathématique
%D 2022
%P 503-511
%V 360
%I Académie des sciences, Paris
%R 10.5802/crmath.321
%G en
%F CRMATH_2022__360_G5_503_0

[1] Jean-Paul Allouche Somme des chiffres et transcendance, Bull. Soc. Math. Fr., Volume 110 (1982), pp. 279-285 | DOI | MR | Numdam | Zbl

[2] Jean-Paul Allouche; Jeffrey Shallit Automatic sequences. Theory, applications, generalizations, Cambridge University Press, 2003 | DOI | Zbl

[3] Sergeĭ V. Avgustinovich The number of different subwords of given length in the Morse–Hedlund sequence, Sibirsk. Zh. Issled. Oper., Volume 1 (1994) no. 2, pp. 3-7 | MR | Zbl

[4] Srećko Brlek Enumeration of factors in the Thue-Morse word, Discrete Appl. Math., Volume 24 (1989) no. 1-3, pp. 83-96 | DOI | MR | Zbl

[5] Cécile Dartyge; Gérald Tenenbaum Congruences de sommes de chiffres de valeurs polynomiales, Bull. Lond. Math. Soc., Volume 38 (2006) no. 1, pp. 61-69 | MR | Zbl

[6] Michael Drmota; Christian Mauduit; Joël Rivat The sum-of-digits function of polynomial sequences, J. Lond. Math. Soc., Volume 84 (2011) no. 1, pp. 81-102 | DOI | MR | Zbl

[7] Aleksandr O. Gel’fond Sur les nombres qui ont des propriétés additives et multiplicatives données, Acta Arith., Volume 13 (1967), pp. 259-265 | DOI | Zbl

[8] Aldo de Luca; Stefano Varricchio Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups, Theor. Comput. Sci., Volume 63 (1989) no. 3, pp. 333-348 | DOI | MR | Zbl

[9] Yossi Moshe On the subword complexity of Thue-Morse polynomial extractions, Theor. Comput. Sci., Volume 389 (2007) no. 1-2, pp. 318-329 | DOI | MR | Zbl

[10] Clemens Müllner; Lukas Spiegelhofer Normality of the Thue-Morse sequence along Piatetski-Shapiro sequences. II, Isr. J. Math., Volume 220 (2017) no. 2, pp. 691-738 | MR | DOI | Zbl

[11] Thomas Stoll The sum of digits of polynomial values in arithmetic progressions, Funct. Approximatio, Comment. Math., Volume 47 (2012) no. 2, pp. 233-239 | MR | Zbl

Cited by Sources:

Comments - Policy