Complexity of Hartman sequences

Steineder, Christian, and Winkler, Reinhard. "Complexity of Hartman sequences." Journal de Théorie des Nombres de Bordeaux 17.1 (2005): 347-357. <http://eudml.org/doc/249465>.

@article{Steineder2005,
abstract = {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 \lbrace 0,1\rbrace $ defined by $\mathbf\{a\}(k) =1$ if $T^k(0_C) \in M$ and $\mathbf\{a\}(k) =0$ otherwise, is called a Hartman sequence. This paper studies the growth rate of $P_\{\mathbf\{a\}\}(n)$, where $P_\{\mathbf\{a\}\}(n)$ 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,\ldots ,\alpha _s))$ on $\mathbb\{T\}^s$ and $M$ is a box with side lengths $\rho _j$ not equal $\alpha _j \mathbb\{Z\}+ \mathbb\{Z\}$ for all $j= 1,\ldots ,s$, we show that $\lim _n P_\{\mathbf\{a\}\}(n)/n^s = 2^s \prod _\{j=1\}^s \rho _j^\{s-1\}$.},
affiliation = {Technische Universität Wien Institut für Diskrete Mathematik und Geometrie Wiedner Hauptstraße 8-10 1040 Vienne, Autriche; Technische Universität Wien Institut für Diskrete Mathematik und Geometrie Wiedner Hauptstraße 8-10 1040 Vienne, Autriche},
author = {Steineder, Christian, Winkler, Reinhard},
journal = {Journal de Théorie des Nombres de Bordeaux},
language = {eng},
number = {1},
pages = {347-357},
publisher = {Université Bordeaux 1},
title = {Complexity of Hartman sequences},
url = {http://eudml.org/doc/249465},
volume = {17},
year = {2005},
}

TY - JOUR
AU - Steineder, Christian
AU - Winkler, Reinhard
TI - Complexity of Hartman sequences
JO - Journal de Théorie des Nombres de Bordeaux
PY - 2005
PB - Université Bordeaux 1
VL - 17
IS - 1
SP - 347
EP - 357
AB - 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 \lbrace 0,1\rbrace $ defined by $\mathbf{a}(k) =1$ if $T^k(0_C) \in M$ and $\mathbf{a}(k) =0$ otherwise, is called a Hartman sequence. This paper studies the growth rate of $P_{\mathbf{a}}(n)$, where $P_{\mathbf{a}}(n)$ 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,\ldots ,\alpha _s))$ on $\mathbb{T}^s$ and $M$ is a box with side lengths $\rho _j$ not equal $\alpha _j \mathbb{Z}+ \mathbb{Z}$ for all $j= 1,\ldots ,s$, we show that $\lim _n P_{\mathbf{a}}(n)/n^s = 2^s \prod _{j=1}^s \rho _j^{s-1}$.
LA - eng
UR - http://eudml.org/doc/249465
ER -