Complexity of Hartman sequences

Steineder, Christian; Winkler, Reinhard

Journal de théorie des nombres de Bordeaux, Tome 17 (2005) no. 1, pp. 347-357.

Soit $T:x\mapsto x+g$ une translation ergodique sur un groupe abélien compact $C$ et soit $M$ une partie de $C$ dont la frontière est de measure de Haar nulle. La suite binaire infinie $\mathbf{a}:\mathbb{Z}\mapsto \{0,1\}$ définie par $\mathbf{a}\left(k\right)=1$ si $T^k\left(0_C\right)\in M$ et $\mathbf{a}\left(k\right)=0$ sinon, est dite de Hartman. Notons $P_{\mathbf{a}}\left(n\right)$ le nombre de mots binaires de longueur $n$ qui apparaissent dans la suite $\mathbf{a}$ vue comme un mot bi-infini. Cet article étudie la vitesse de croissance de $P_{\mathbf{a}}\left(n\right)$. Celle-ci est toujours sous-exponentielle et ce résultat est optimal. Dans le cas où $T$ est une translation ergodique $x\mapsto x+\alpha$ $(\alpha =({\alpha }_1,...,{\alpha }_s))$ sur ${𝕋}^s$ et $M$ un parallélotope rectangle pour lequel la longueur du $j$-ème coté ${\rho }_j$ n’est pas dans ${\alpha }_j\mathbb{Z}+\mathbb{Z}$ pour tout $j=1,...,s$, on obtient ${lim}_n{P}_{\mathbf{a}}\left(n\right)/n^s=2^s{\prod }_{j=1}^s{\rho }_j^{s-1}$.

Let $T:x\mapsto x+g$ be an ergodic translation on the compact group $C$ and $M\subseteq C$ a continuity set, i.e. a subset with topological boundary of Haar measure 0. An infinite binary sequence $\mathbf{a}:\mathbb{Z}\mapsto \{0,1\}$ defined by $\mathbf{a}\left(k\right)=1$ if $T^k\left(0_C\right)\in M$ and $\mathbf{a}\left(k\right)=0$ otherwise, is called a Hartman sequence. This paper studies the growth rate of $P_{\mathbf{a}}\left(n\right)$, where $P_{\mathbf{a}}\left(n\right)$ denotes the number of binary words of length $n\in \mathbb{N}$ occurring in $\mathbf{a}$. The growth rate is always subexponential and this result is optimal. If $T$ is an ergodic translation $x\mapsto x+\alpha$ $(\alpha =({\alpha }_1,...,{\alpha }_s))$ on ${𝕋}^s$ and $M$ is a box with side lengths ${\rho }_j$ not equal ${\alpha }_j\mathbb{Z}+\mathbb{Z}$ for all $j=1,...,s$, we show that ${lim}_n{P}_{\mathbf{a}}\left(n\right)/n^s=2^s{\prod }_{j=1}^s{\rho }_j^{s-1}$.

[1] P. Alessandri, V. Berthé, Three Distance Theorems and Combinatorics on Words. Enseig. Math. 44 (1998), 103–132. | MR | Zbl

[2] P. Arnoux, V. Berthé, S. Ferenci, S. Ito, C. Mauduit, M. Mori, J. Peyrière, A. Siegel, J.- I. Tamura, Z.- Y. Wen, Substitutions in Dynamics, Arithmetics and Combinatorics. Lecture Notes in Mathematics 1794, Springer Verlag Berlin, 2002. | MR

[3] V. Berthé, Sequences of low complexity: Automatic and Sturmian sequences. Topics in Symbolic Dynamics and Applications. Lond. Math. Soc, Lecture Notes 279, 1–28, Cambridge University Press, 2000. | MR | Zbl

[4] M. Denker, Ch. Grillenberger, K. Sigmund, Ergodic Theory on Compact Spaces. Lecture Notes in Mathematics 527, Springer, Heidelberg, 1976. | MR | Zbl

[5] S. Frisch, M. Pašteka, R. F. Tichy, R. Winkler, Finitely additive measures on groups and rings. Rend. Circolo Mat. di Palermo 48 Series II (1999), 323–340. | MR | Zbl

[6] G. A. Hedlund, M. Morse, Symbolic Dynamics I. Amer. J. Math. 60 (1938), 815–866. | MR | Zbl

[7] G. A. Hedlund, M. Morse, Symbolic Dynamics II. Amer. J. Math. 62 (1940), 1–42. | MR | Zbl

[8] E. Hewitt, K. A. Ross, Abstract Harmonic Analysis I. Springer, Berlin—Göttingen—Heidelberg, 1963. | MR | Zbl

[9] L. Kuipers, H. Niederreiter, Uniform distribution of sequences. Wiley, New York, 1974. | MR | Zbl

[10] J. Schmeling, E. Szabó, R. Winkler, Hartman and Beatty bisequences. Algebraic Number Theory and Diophantine Analysis, 405–421, Walter de Gruyter, Berlin, 2000. | MR | Zbl

[11] P. Walters, An Introduction to Ergodic Theory. Grad. Texts in Math. Springer Verlag New York, 2000. | MR | Zbl

[12] R. Winkler, Ergodic Group Rotations, Hartman Sets and Kronecker Sequences. Monatsh. Math. 135 (2002), 333–343. | MR | Zbl