The subword complexity of polynomial subsequences of the Thue–Morse sequence

Zhao Shen

doi:10.5802/crmath.321

Théorie des nombres

The subword complexity of polynomial subsequences of the Thue–Morse sequence
[La complexité de facteurs des sous-suites polynomiales de la suite de Thue–Morse]

Zhao Shen ¹

¹ Department of Mathematics, Tsinghua University, Beijing 100084, P. R. China

Comptes Rendus. Mathématique, Volume 360 (2022), pp. 503-511.

Résumé
Abstract

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 \in ℚ [T]$ avec $H (ℕ) \subseteq ℕ$ et $deg H = 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 $deg H ⩾ 3$ . Dans ce travail, nous allons donner une réponse positive au problème précédent.

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 \in ℚ [T]$ with $H (ℕ) \subseteq ℕ$ and $deg H = 2$ , all the subsequences ${(t (H (n)))}_{n ⩾ 0}$ attain the maximal subword complexity. Then he asked whether the same result holds for $deg H ⩾ 3$ . In this work, we shall give a positive answer to the above problem.

Reçu le : 2021-07-09
Révisé le : 2021-11-07
Accepté le : 2022-01-02
Publié le : 2022-05-23

DOI : 10.5802/crmath.321

Affiliations des auteurs :

Zhao Shen ¹

¹ Department of Mathematics, Tsinghua University, Beijing 100084, P. R. China

Licence :

CC-BY 4.0

Droits d'auteur : Les auteurs conservent leurs droits

@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
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

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/

Bibliographie
Cité par

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

Cité par Sources :

Commentaires - Politique