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 .

DOI : 10.5802/jtnb.494
Steineder, Christian 1 ; Winkler, Reinhard 1

1 Technische Universität Wien Institut für Diskrete Mathematik und Geometrie Wiedner Hauptstraße 8-10 1040 Vienne, Autriche
@article{JTNB_2005__17_1_347_0,
     author = {Steineder, Christian and Winkler, Reinhard},
     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 = {http://www.numdam.org/articles/10.5802/jtnb.494/}
}
TY  - JOUR
AU  - Steineder, Christian
AU  - Winkler, Reinhard
TI  - Complexity of Hartman sequences
JO  - Journal de théorie des nombres de Bordeaux
PY  - 2005
SP  - 347
EP  - 357
VL  - 17
IS  - 1
PB  - Université Bordeaux 1
UR  - http://www.numdam.org/articles/10.5802/jtnb.494/
DO  - 10.5802/jtnb.494
LA  - en
ID  - JTNB_2005__17_1_347_0
ER  - 
%0 Journal Article
%A Steineder, Christian
%A Winkler, Reinhard
%T Complexity of Hartman sequences
%J Journal de théorie des nombres de Bordeaux
%D 2005
%P 347-357
%V 17
%N 1
%I Université Bordeaux 1
%U http://www.numdam.org/articles/10.5802/jtnb.494/
%R 10.5802/jtnb.494
%G en
%F JTNB_2005__17_1_347_0
Steineder, Christian; Winkler, Reinhard. 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. http://www.numdam.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 | 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

Cité par Sources :