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

Shen, Zhao

Comptes Rendus. Mathématique, Tome 360 (2022) no. G5, pp. 503-511.

Soit $\mathbf{t}={\left(t\left(n\right)\right)}_{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 ${\left(t\left(n^2\right)\right)}_{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 \mathbb{Q}\left[T\right]$ avec $H\left(\mathbb{N}\right)\subseteq \mathbb{N}$ et $degH=2$, toutes les sous-suites ${\left(t\left(H\left(n\right)\right)\right)}_{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.

Let $\mathbf{t}={\left(t\left(n\right)\right)}_{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 ${\left(t\left(n^2\right)\right)}_{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 \mathbb{Q}\left[T\right]$ with $H\left(\mathbb{N}\right)\subseteq \mathbb{N}$ and $degH=2$, all the subsequences ${\left(t\left(H\left(n\right)\right)\right)}_{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.

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

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

[3] Avgustinovich, Sergeĭ V. 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] Brlek, Srećko Enumeration of factors in the Thue-Morse word, Discrete Appl. Math., Volume 24 (1989) no. 1-3, pp. 83-96 | DOI | MR | Zbl

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

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

[7] Gel’fond, Aleksandr O. 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] de Luca, Aldo; Varricchio, Stefano 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] Moshe, Yossi 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] Müllner, Clemens; Spiegelhofer, Lukas 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] Stoll, Thomas The sum of digits of polynomial values in arithmetic progressions, Funct. Approximatio, Comment. Math., Volume 47 (2012) no. 2, pp. 233-239 | MR | Zbl