Complexity of Hartman sequences

Christian Steineder; Reinhard Winkler

doi:10.5802/jtnb.494

Christian Steineder ¹ ; Reinhard Winkler ¹

¹ Technische Universität Wien Institut für Diskrete Mathematik und Geometrie Wiedner Hauptstraße 8-10 1040 Vienne, Autriche

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

Résumé
Abstract

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 $a : ℤ \mapsto {0, 1}$ définie par $a (k) = 1$ si $T^{k} (0_{C}) \in 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 $x \mapsto x + α$ $(α = (α_{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} \prod_{j = 1}^{s} ρ_{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 $a : ℤ \mapsto {0, 1}$ defined by $a (k) = 1$ if $T^{k} (0_{C}) \in 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 \in ℕ$ occurring in $a$ . The growth rate is always subexponential and this result is optimal. If $T$ is an ergodic translation $x \mapsto x + α$ $(α = (α_{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} \prod_{j = 1}^{s} ρ_{j}^{s - 1}$ .

MR Zbl

DOI : 10.5802/jtnb.494

Affiliations des auteurs :

Christian Steineder ¹ ; Reinhard Winkler ¹

¹ 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 = {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},
     mrnumber = {2152228},
     zbl = {1162.11320},
     language = {en},
     url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.494/}
}

TY  - JOUR
AU  - Christian Steineder
AU  - Reinhard Winkler
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  - https://jtnb.centre-mersenne.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 Christian Steineder
%A Reinhard Winkler
%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 https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.494/
%R 10.5802/jtnb.494
%G en
%F JTNB_2005__17_1_347_0

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/

Bibliographie
Cité par

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