Complexity of Hartman sequences
Journal de Théorie des Nombres de Bordeaux, Tome 17 (2005) no. 1, pp. 347-357.

Soit T:xx+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 a:{0,1} définie par a(k)=1 si T k (0 C )M et a(k)=0 sinon, est dite de Hartman. Notons P a (n) le nombre de mots binaires de longueur n qui apparaissent dans la suite a vue comme un mot bi-infini. Cet article étudie la vitesse de croissance de P a (n). Celle-ci est toujours sous-exponentielle et ce résultat est optimal. Dans le cas où T est une translation ergodique xx+α (α=(α 1 ,...,α s )) sur 𝕋 s et M un parallélotope rectangle pour lequel la longueur du j-ème coté ρ j n’est pas dans α j + pour tout j=1,...,s, on obtient lim n P a (n)/n s =2 s j=1 s ρ j s-1 .

Let T:xx+g be an ergodic translation on the compact group C and MC a continuity set, i.e. a subset with topological boundary of Haar measure 0. An infinite binary sequence a:{0,1} defined by a(k)=1 if T k (0 C )M and a(k)=0 otherwise, is called a Hartman sequence. This paper studies the growth rate of P a (n), where P a (n) denotes the number of binary words of length n occurring in a. The growth rate is always subexponential and this result is optimal. If T is an ergodic translation xx+α (α=(α 1 ,...,α s )) on 𝕋 s and M is a box with side lengths ρ j not equal α j + for all j=1,...,s, we show that lim n P a (n)/n s =2 s j=1 s ρ j s-1 .

@article{JTNB_2005__17_1_347_0,
     author = {Christian Steineder and Reinhard Winkler},
     title = {Complexity of Hartman sequences},
     journal = {Journal de Th\'eorie des Nombres de Bordeaux},
     pages = {347--357},
     publisher = {Universit\'e Bordeaux 1},
     volume = {17},
     number = {1},
     year = {2005},
     doi = {10.5802/jtnb.494},
     zbl = {1162.11320},
     mrnumber = {2152228},
     language = {en},
     url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.494/}
}
Christian Steineder; Reinhard Winkler. Complexity of Hartman sequences. Journal de Théorie des Nombres de Bordeaux, Tome 17 (2005) no. 1, pp. 347-357. doi : 10.5802/jtnb.494. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.494/

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

[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 1970385

[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 1776754 | Zbl 0976.11014

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

[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 1692930 | Zbl 0931.43001

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

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

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

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

[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 1770477 | Zbl 0965.11035

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

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