logo CRAS
Comptes Rendus. Mathématique
Number Theory
The subword complexity of polynomial subsequences of the Thue–Morse sequence
Comptes Rendus. Mathématique, Volume 360 (2022), pp. 503-511.

Let t=(t(n)) n0 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 )) n0 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))) n0 attain the maximal subword complexity. Then he asked whether the same result holds for degH3. In this work, we shall give a positive answer to the above problem.

Soit t=(t(n)) n0 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 )) n0 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))) n0 atteignent la complexité maximale. Ensuite il demandait si le résultat est aussi valable pour degH3. 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
@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},
     publisher = {Acad\'emie des sciences, Paris},
     volume = {360},
     year = {2022},
     doi = {10.5802/crmath.321},
     language = {en},
}
TY  - JOUR
TI  - The subword complexity of polynomial subsequences of the Thue–Morse sequence
JO  - Comptes Rendus. Mathématique
PY  - 2022
DA  - 2022///
SP  - 503
EP  - 511
VL  - 360
PB  - Académie des sciences, Paris
UR  - https://doi.org/10.5802/crmath.321
DO  - 10.5802/crmath.321
LA  - en
ID  - CRMATH_2022__360_G5_503_0
ER  - 
%0 Journal Article
%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
%U https://doi.org/10.5802/crmath.321
%R 10.5802/crmath.321
%G en
%F CRMATH_2022__360_G5_503_0
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. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.5802/crmath.321/

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

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

[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: 1304871 | Zbl: 0839.05008

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

[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: 2201604 | Zbl: 1153.11307

[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 | Article | MR: 2819691 | Zbl: 1257.11009

[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 | Article | Zbl: 0155.09003

[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 | Article | MR: 993769 | Zbl: 0671.10050

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

[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 | Article | MR: 3666442 | Zbl: 1400.11119

[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: 3051450 | Zbl: 1315.11010

Cited by Sources: