Journal de Théorie des Nombres de Bordeaux 00 (XXXX), 000–000

Complexity of Hartman sequences

par Christian STEINEDER et Reinhard WINKLER

Résumé. Soit T : x ↦ 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 : ℤ ↦ {0, 1} défine par a(k) = 1 si T^{k}(0_{C}) ∈ M et a(k) = 0 sinon, est dite de Hartman. Notons Pa(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 Pa(n). Celle-ci est toujours sous-exponentielle et ce résultat est optimal. Dans le cas où T est une translation ergodique x ↦ 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} Pa(n)/n^{s} = 2^{s} ∏_{j=1}^{s} ρ_{j}^{s−1}.

Abstract. Let T : x ↦ x + g be an ergodic translation on the compact group C and M ⊆ C 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 Pa(n), where Pa(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 x ↦ 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} Pa(n)/n^{s} = 2^{s} ∏_{j=1}^{s} ρ_{j}^{s−1}.

Acknowledgement. The authors thank the Austrian Science Foundation FWF for supporting the research for this paper through projects no. S8312 and no. S8302.

1. Motivation and Notation

The notion of a Hartman sequence has recently been introduced and studied (cf. [5], [10], [12]). It can be seen as a generalisation of the notion of a Sturmian sequence. Sturmian sequences (and their close relatives, the Beatty sequences) are very interesting objects, as well from the combinatorial, the number theoretic and the dynamical point of view. Let us sketch two approaches.

Consider sequences a = (a_{k}) of two symbols, say 0 and 1, where k runs through the set ℤ of all integers or ℕ of all positive integers. Such sequences are also called two resp. one sided infinite binary words. Let Pa(n) be the number of different binary words of length n occurring in a. The mapping n ↦ Pa(n) is called the complexity function of a. It is easily seen that the complexity function is bounded if and only if a is (in the one sided case: eventually) periodic. Among all aperiodic sequences Sturmian sequences have minimal complexity, namely P (n) = n + 1. This is the combinatorial approach to characterise Sturmian sequences, which has been introduced in [6] and [7].

A different characterisation uses the symbolic coding of irrational rotations. If 𝕋 = ℝ/ℤ denotes the circle group (one dimensional torus) and M is a segment of 𝕋 of angle 2πα with irrational α ∈ 𝕋, then the definition a_{k} = 1 if and only if kα ∈ M defines a Sturmian sequence (cf. for instance [2]).

For understanding the definition of a Hartman sequence the second approach is more appropriate. Replace 𝕋 by more general compact abelian groups C with normalised Haar measure μ = μ_{C} and replace α by any ergodic group translation. This means that we are interested in the transformation T : C ↦ C, T : x ↦ x + g, where g is a generating element of C, i.e. the orbit {kg : k ∈ ℤ} is dense in C. Thus C is required to be monothetic. C can also be interpreted as a group compactification of ℤ since C is the closure of the image of ℤ under the dense homomorphic embedding ι : ℤ → C, ι(k) = kg. (Note that for group compactifications one usually does not require ι to be injective. But to avoid trivial case distinctions we will demand that ι(ℤ) is infinite.) This approach is particularly appropriate for Theorems 1 and 2. For the classical theory of ergodic group translations we refer for instance to [11].

A set M ⊂ C is called a (μ_{C}-)continuity set if μ_{C}(∂M) = 0 holds for its topological boundary ∂M. For a continuity set M consider the induced binary sequence a = (a_{k})_{k=−∞}^{∞} defined by a_{k} = 1 if T^{k}(0_{C}) ∈ M and a_{k} = 0 otherwise. Such sequences are called Hartman sequences. The set H ⊂ ℤ defined by k ∈ H if and only if a_{k} = 1 is accordingly called a Hartman set. Thus, by definition, a Hartman set H is the preimage H = ι^{−1}(M) of a continuity set M ⊆ C where (C, ι) is a group compactification of ℤ and we can write a = 1_{H}. Note that for C = 𝕋^{s} and g = (α_{1}, …, α_{s}), where the family {1, α_{1}, …, α_{s}} is linearly independent over ℤ, Hartman sequences are binary coding sequences of Kronecker sequences.

As a consequence of uniform distribution of ergodic group translations (for the theory of uniform distribution of sequences we refer to [9]), Hartman sequences share some nice properties with Sturmian sequences (cf. [5], [10]). In particular each finite subword occurs with a uniform asymptotic density.

More precisely: If the measure of a Hartman set H = ι^{−1}(M) is defined by μ(H) := μ_{C}(M), then

μ(H) = dens(H) = lim_{n→∞} \frac{card(H ∩ \{k, k + 1, …, k + n − 1\})}{n}

holds uniformly in k ∈ ℤ, cf. [5]. In particular, for a given Hartman set H, this value neither depends on (C, ι) nor on M. In terms of Hartman sequences: If, for a = (a_{k}) = 1_{H}, A_{k}(n) denotes the number of occurrences of 1’s in the block a_{k}a_{k+1} … a_{k+n−1} of length n, there exists a bound c_{M}(n) = o(1), n → ∞, such that

|\frac{A_{k}(n)}{n} − μ_{C}(M)| ≤ c_{M}(n)

for all k ∈ ℕ. This has been used in [12] to develop a new approach to identify the underlying dynamical system from its symbolic coding.

In this paper we start to investigate the complexity of Hartman sequences. Corresponding to the zero entropy of the underlying dynamical system, the growth rate of the complexity function of any Hartman sequence is subexponential. This upper bound turns out to be best possible. In particular, the complexity of a Hartman sequence might be much higher than, for instance, interval coding sequences for which the complexity essentially is linear (cf. for instance [1] and [3]). In some sense this fact is due to the more general choice of M rather than to the more general choice of the compact group C. Nevertheless, for the case of an M with a very simple geometric structure, namely a box in a finite dimensional compactification C = 𝕋^{s} the complexity grows polynomially of maximal order s. A more systematic investigation of the role of the geometric properties of M and the further development of the arguments used here is to be the object of future research. So the results in this paper are the following:

• For any Hartman sequence a and λ > 1 we have Pa(n) = o(λ^{n}) for n → ∞ (Theorem 1).

• For any sequence P_{n} of subexponential growth rate and any compactification (C, ι) there is a Hartman sequence a coming from (C, ι) with P_{n} = o(Pa(n)). This is even true, if Pa(n) counts only binary words which occur in a with strictly positive density (Theorem 2).

• Assumes that M is a box of side lengths ρ_{j}, j = 1, …, s, in 𝕋^{s}. Then the complexity Pa(n) of the induced Hartman sequence a has the asymptotic growth rate cn^{s} if ρ_{j} ∉ α_{j}ℤ + ℤ for all j = 1, …, s. The multiplicative constant c is given by c = 2^{s} ∏_{j=1}^{s} ρ_{j}^{s−1} (Theorem 3).

2. A universal upper bound for the complexity of Hartman sequences

Corresponding to the fact that ergodic group translations have entropy 0, one conjectures that the complexity of a Hartman sequence is subexponential. Note that the topological entropy of shift spaces and complexity are very closely related. Nevertheless we cannot apply immediately pertinent theorems in textbooks as [4] or [11] to obtain an upper bound for the complexity of a Hartman sequence in terms of the entropy of the underlying group rotation. Therefore we give a direct proof that the above conjecture is true.

Theorem 1. For any compactification (C, ι) of ℤ and any continuity set M ⊆ C the complexity Pa(n) of the corresponding Hartman sequence a = 1_{H} with H = ι^{−1}(M) satisfies

lim_{n→∞} \frac{log Pa(n)}{n} = 0.

Proof. By Theorem 4 in [10] we may presume that there is a metric d for the topology on C. Let g = ι(1) ∈ C denote the generating element of the compactification.

We write M′ for the complement C \ M and M_{δ} for the set of all x ∈ C with d(x, y) < δ for some y ∈ M. Fix ε > 0. Using the regularity of the Haar measure μ_{C} and the μ_{C}-continuity of M, we obtain μ_{C}(R) < ε for R = (M_{δ_{1}} \ M) ∪ (M′_{δ_{1}} \ M′) whenever δ_{1} > 0 is sufficiently small. By a standard argument we may assume that R is a continuity set. At least one of the sets M and M′, say M, has nonempty interior. This means that there is some open ball B with center x and positive diameter δ < δ_{1}/2 with B ⊂ M. For the sake of simpler notation we assume x = 0.

Let W_{l} denote the set of all binary words a_{0} … a_{l−1} of length l with a_{k} = 1 whenever kg + B ⊆ M and a_{k} = 0 whenever kg + B ⊆ M′.

By compactness of C there is some N_{0} ∈ ℕ such that

C ⊆ ⋃_{n=0}^{N_{0}−1}(−ng + B),

showing that for every y ∈ C there is some n ∈ {0, 1, …, N_{0} − 1} with y + ng ∈ B.

Thus any word w of length N_{0} + l occurring in a lies in some of the sets W_{N_{0}+l,i}, 0 ≤ i ≤ N_{0} − 1, consisting of all words

b_{0}b_{1} … b_{i−1}a_{0} … a_{l−1}b_{i} … b_{N_{0}−1}

with a_{0}a_{1} … a_{l−1} ∈ W_{l} and b_{0}b_{1} … b_{N_{0}−1} ∈ {0, 1}^{n}. Since |W_{N_{0}+l,i}| = 2^{N_{0}}|W_{l}|, this shows Pa(N_{0} + l) ≤ N_{0}2^{N_{0}}|W_{l}|.

Note that each translate y + B is totally contained either in M or in M′ whenever y ∉ R. Thus, by the uniform distribution of (ng)_{n} in C, the subset T ⊆ ℤ of all k ∈ ℤ such that y = kg ∉ R has density μ_{C}(C \ R) > 1 − ε.

It follows that |W_{l}| ≤ 2^{2εl}, hence Pa(N_{0}+l) ≤ N_{0}2^{N_{0}+2εl} for l sufficiently large. This yields

log Pa(N_{0} + l) ≤ log N_{0} + (N_{0} + 2εl) log 2

and, for n = N_{0} + l

lim sup_{n→∞} \frac{log Pa(n)}{n} ≤ lim sup_{l→∞} \frac{log N_{0} + (N_{0} + 2εl) log 2}{N_{0} + l} ≤ 2ε log 2.

Since ε > 0 can be chosen arbitrarily small this proves the theorem. □

3. A Hartman sequence of arbitrarily subexponential complexity

We are going to show that the bound deduced in Theorem 1 is best possible.

Let (C, ι) be any group compactification of ℤ and ϕ : ℕ ↦ ℕ. Suppose ϕ(n) = ε_{n}n ≤ n with lim_{n→∞} ε_{n} = 0. We have to show that there exists a continuity set M ⊂ C such that the Hartman sequence a := 1_{H} with H = ι^{−1}(M) fulfills Pa(n) ≥ 2^{ϕ(n)}.

By Theorem 4 in [12] it suffices to prove the assertion for metrisable C and by Theorem 8.3 in [8] there is an invariant metric d for the topology on C. For c ∈ C we write ∥c∥ = d(c, 0). For each n ∈ ℕ choose a subset H^{(n)} of {0, …, n − 1} of cardinality A_{n} ≥ ε_{n}n and containing 0 such that the diameter d_{n} of ι(H^{(n)}) is minimal. We claim that lim_{n→∞} d_{n} = 0.

Otherwise we had a sequence n_{1} < n_{2} < … and a δ > 0 such that d_{n_{k}} ≥ 2δ for all k. There is some r ∈ (0, δ) such that the open ball B with center 0 ∈ C and radius r is a continuity set. By construction, the lower density of the set of all n with ι(n) ∈ B is at most ε_{n_{k}} for all k. By uniform distribution of ι(n), the lower density is a density and coincides with the Haar measure, hence μ(B) ≤ lim_{k→∞} ε_{n_{k}} = 0. This contradicts the fact that nonempty open sets have positive measure.

Let now H_{n}(0), H_{n}(1), …, H_{n}(2^{A_{n}} − 1) be an enumeration of all subsets of H^{(n)}. Define recursively m_{n}(0) = 0 and m_{n}(i + 1) to be the minimal integer > m_{n}(i) + n such that ∥ι(m_{n}(i + 1))∥ < d_{n}. We put H_{n} = ⋃_{i=0}^{2^{An}−1}(m_{n}(i) + H_{n}(i)). Obviously H_{n} is a finite set of nonnegative integers bounded by, say h_{n} ∈ ℕ. Observe furthermore that by construction ∥ι(h)∥ < 2d_{n} for all h ∈ H_{n}. Define, again recursively, l_{0} = 1 and l_{n+1} to be the minimal integer > l_{n} + h_{n} such that ∥ι(l_{n+1})∥ < d_{n}. For the union H = ⋃_{n=0}^{∞}(H_{n} + l_{n}) this implies lim_{n→∞,n∈H} ι(n) = 0. Thus M = ι(H) is a countable closed subset of C with the only accumulation point 0, hence a continuity set of measure 0 and H = ι^{−1}(M) is a Hartman set.

In the corresponding Hartman sequence each H_{n} induces at least 2^{A_{n}} different binary words of length n. Thus the complexity function P (n) is bounded below by

P (n) ≥ 2^{A_{n}} ≥ 2^{ε_{n}n} = 2^{ϕ(n)}.

This construction generates a zero set M. Hence each word in a containing the letter 1 has asymptotic density 0. It would be nice to get a positive frequency for many words. Let therefore M = {0, m_{1}, m_{2}, …} be an enumeration of M. There are δ_{n} > 0 with δ_{n} → 0 such that balls B_{n}, n ∈ ℕ, with center m_{n} and radius δ_{n} are pairwise disjoint continuity sets. Replace M by the union of all B_{n}, which is again a continuity set. This shows:

Theorem 2. Let (C, ι) be any group compactification of ℤ. Assume ϕ(n) ≤ n and ϕ(n) = o(n) for n → ∞. Then there exists a continuity set M ⊂ C such that its Hartman sequence a := 1_{ι^{−1}(M)} fulfills Pa(n) ≥ 2^{ϕ(n)}. Furthermore M can be chosen in such a way that for each n ∈ ℕ at least 2^{ϕ(n)} words of length n occur in a with strictly positive density.

4. The case of Kronecker sequences and Boxes

We finally restrict our attention to the special case that C = 𝕋^{s} is a finite dimensional compactification with generating element g = (α_{1}, …, α_{s}) modulo 1, i.e. ι : k ↦ kg = k(α_{1}, …, α_{s}), where the family {1, α_{1}, …, α_{s}} is linearly independent over ℤ (such (kg)_{k} are also called Kronecker sequences), and M a box in 𝕋^{s}. To be more precise we use the following notational convention.

As usual, {r} = r − [r] and [r] = max{k ∈ ℤ : k ≤ r} denote the fractional respectively integer part of r ∈ ℝ. Thus 𝕋^{s} = (ℝ/ℤ)^{s} = κ(ℝ^{s}) is considered to be the image of the additive group ℝ^{s} under the mapping κ = κ_{s} : (x_{1}, …, x_{s}) ↦ ({x_{1}}, …, {x_{s}}). Although 𝕋 has no order structure it is useful to think about intervals in 𝕋 as images of intervals in ℝ under κ_{1}, boxes in 𝕋^{s} as images of boxes in ℝ^{s} etc. To avoid too cumbersome notation we therefore write, for instance, ∏_{j=1}^{s}[−ρ_{j}/2, ρ_{j}/2), ρ_{j} ∈ (0, 1) also for the set M = κ_{s}(∏_{j=1}^{s}[−ρ_{j}/2, ρ_{j}/2)). It is natural to call a set M = ∏_{j=1}^{s}[m_{j}, m_{j} + ρ_{j}) ⊆ 𝕋^{s} an s-dimensional box in 𝕋^{s} with side lengths ρ_{j}, j = 1, …, s. We are especially interested in Hartman sequences a = 1_{H}, H = ι^{−1}(M), for this kind of M and call such a Bohr sequences.

Let us fix a box M of side lengths ρ_{j}, j = 1, …, s, and assume that no ρ_{j} is in α_{j}ℤ + ℤ. We are going to determine the asymptotic behaviour of Pb(n) for the Bohr sequence b = 1_{H}, H = ι^{−1}(M).

We will use the following notation: For a word w = a_{0} … a_{n−1} ∈ {0, 1}^{n} we introduce the set

A_{w} := {x ∈ 𝕋^{s} : (x + ig ∈ M ⇔ a_{i} = 1) for i = 0, …, n − 1}

and write w = w(x) for x ∈ A_{w}. Note that, provided A_{w} ≠ ∅, A_{w} has inner points. Because of the density of the set {ng : n ∈ ℕ}, the continuity of T and the special form of M this implies

Pb(n) = |{w ∈ {0, 1}^{n} : A_{w} ≠ ∅}|.

To compute the number of all nonempty A_{w} we first consider a half open cube C_{0} := c_{0} + [−σ/2, σ/2)^{s} ⊆ 𝕋^{s} with center c_{0} and side length σ < ρ_{j} for all j = 1, …, s. We are going to estimate the local complexity function P (C_{0}, n) := |W | for W = W (C_{0}) := {w ∈ {0, 1}^{n} : A_{w} ∩ C_{0} ≠ ∅}. Note that for k cubes C_{1}, …, C_{k} in 𝕋^{s} with disjoint closures we have

Pa(n) ≥ ∑_{j=1}^{k} P (C_{j}, n)

for sufficiently large n. As above, A_{w} ∩ C_{0} ≠ ∅ implies μ_{C}(A_{w} ∩ C_{0}) > 0. So P (C_{0}, n) is the number of different words w = b_{i} … b_{i+n−1} of length n in b with ig ∈ C_{0}. Define

M_{0} := ∏_{j=1}^{s}[−\frac{ρ_{j}}{2} + \frac{σ}{2} , \frac{ρ_{j}}{2} − \frac{σ}{2} ), M_{1} := ∏_{j=1}^{s}[−\frac{ρ_{j}}{2} − \frac{σ}{2} , \frac{ρ_{j}}{2} + \frac{σ}{2} ), Γ := M_{1}\M_{0},

and furthermore, for each j = 1, …, s,

Q_{1}^{(j)} := \{x = (x_{1}, …, x_{s}) ∈ M_{1} : x_{j} < −\frac{ρ_{j}}{2} + \frac{σ}{2} or x_{j} ≥ \frac{ρ_{j}}{2} − \frac{σ}{2} \},
Q_{0}^{(j)} := Q_{1}^{(j)} \ ⋃_{j′≠j} Q_{1}^{(j′)}.

Observe that the sets Q_{0}^{(j)} (in contrast to the Q_{1}^{(j)}) are pairwise disjoint. For w = a_{0} … a_{n−1} in W note that

(c_{0} + ig ∈ M_{0} ⇒ a_{i} = 1) and (c_{0} + ig ∉ M_{1} ⇒ a_{i} = 0).

This shows that for w = a_{0} … a_{n−1} and w′ = a′_{0} … a′_{n−1} in W the letters a_{i} and a′_{i} can differ only if c_{0} + ig ∈ Γ. Since Γ = ⋃_{j=1}^{s} Q_{1}^{(j)}, we define, for j = 1, …, s and l = 0, 1,

I_{l}^{(j)} := {i ∈ {0, …, n − 1} : c_{0} + ig ∈ Q_{l}^{(j)}},
I_{l} := ⋃_{j=1}^{s} I_{l}^{(j)}.

Due to the special geometric situation (C_{0} and M are boxes), for x = (x_{1}, …, x_{s}) ∈ C_{0}, w = w(x) = (a_{i}(x))_{0≤i<n} ∈ W, j ∈ {1, …, s}, the tuple (a_{i}(x))_{i∈I_{0}^{(j)}} depends only on x_{j}, namely in the following way. Let X_{j} = [y_{0}, y_{0} + σ) be the interval for the j-th coordinate of points in C_{0}. Then for each i ∈ I_{0}^{(j)} there is one point y_{i} (namely either ρ_{j}/2 − ig or −ρ_{j}/2 − ig) such that y_{i} splits the interval X_{j} into two subintervals X_{j}^{(0)}

and X_{j}^{(1)} such that a_{i}(x) = 0 for x_{j} ∈ X_{j}^{(0)} and a_{i}(x) = 1 for x_{j} ∈ X_{j}^{(1)}.

Since ρ_{j} ∉ α_{j}ℤ + ℤ, all y_{i}, i ∈ I_{0}^{(j)}, are distinct. As a consequence the mapping x_{j} ↦ (a_{i}(x))_{i∈I_{0}^{(j)}} takes at least |I_{0}^{(j)} + 1| different values, hence

A_{j} = |{(a_{i}(x))_{i∈I_{0}^{(j)}} : x ∈ C_{0}}| ≥ |I_{0}^{(j)} + 1|.

Since the sets I_{0}^{(j)}, j = 1, …, s, are pairwise disjoint and all coordinates j can be treated independently, we conclude

P (C_{0}, n) = |W | ≥ ∏_{j=1}^{s}(|I_{0}^{(j)}| + 1).

For ε > 0 we know by uniform distribution of the sequence (ng)_{n} that

|I_{0}^{(j)}| ≥ μ(Q_{0}^{(j)})n − εn

for n sufficiently large. Since μ(Q_{0}^{(j)}) = 2 ∏_{j=1,j≠i}^{s}(ρ_{j} − σ)σ, j = 1, …, s, we get

|W | ≥ n^{s} ∏_{i=1}^{s} (2 ∏_{j=1,j≠i}^{s}((ρ_{j} − σ)σ − ε)

for n sufficiently large. Thus we obtain

lim inf_{n→∞} \frac{P (C_{0}, n)}{n^{s}} ≥ 2^{s} ∏_{i=1}^{s} ( ∏_{j=1,j≠i}^{s}(ρ_{j} − σ)σ − ε)

for all ε > 0 and therefore

lim inf_{n→∞} \frac{P (C_{0}, n)}{n^{s}} ≥ 2^{s} ∏_{i=1}^{s} ∏_{j=1,j≠i}^{s}(ρ_{j} − σ)σ.

As a consequence of uniform distribution we know that d(x, x′) > δ implies w(x) ≠ w(x′) if the words are sufficiently long. Thus W (C_{0}) and W (C′_{0}) are disjoint whenever two cubes C_{0} and C′_{0} are separated by a strictly positive distance δ. Fix now k ∈ ℕ and consider the disjoint cubes C_{1}, …, C_{k^{s}} with centers c_{i} = (m_{i}/k), m_{i} ∈ {0, …, k − 1} and side length σ = 1/k − δ, 0 < δ < \frac{1}{k}. We get

lim inf_{n→∞} \frac{Pb(n)}{n^{s}} ≥ ∑_{i=1}^{k^{s}} lim inf_{n→∞} \frac{P (C_{i}, n)}{n^{s}} ≥ k^{s}2^{s}(\frac{1}{k} − δ)^{s} ∏_{i=1}^{s} ∏_{j=1,j≠i}^{s}(ρ_{j} − \frac{1}{k} + δ).

Since this holds for all δ > 0 we can consider the limit δ → 0 to get

lim inf_{n→∞} \frac{Pb(n)}{n^{s}} ≥ k^{s}2^{s} \frac{1}{k^{s}} ∏_{i=1}^{s} ∏_{j=1,j≠i}^{s}(ρ_{j} − \frac{1}{k}) = 2^{s} ∏_{j=1}^{s}(ρ_{j} − \frac{1}{k})^{s−1}.

For k → ∞ this finally shows the lower bound

lim inf_{n→∞} \frac{Pb(n)}{n^{s}} ≥ 2^{s} ∏_{j=1}^{s} ρ_{j}^{s−1}.

To obtain an upper bound for the complexity we consider instead of A_{j} as defined above the numbers

B_{j} = |{(a_{i}(x))_{i∈I_{1}^{(j)}} : x ∈ C_{0}}| ≤ |I_{1}^{(j)} + 1|.

Note that the sets I_{1}^{(j)}, j = 1, …, s, are (in contrast to the sets I_{0}^{(j)}) not disjoint. This implies that a_{i}(x) possibly depends on more than one component of x. Comparison with the argument for the lower bound shows that the relevant mapping x ↦ (a_{i}(x))_{i∈I_{1}^{(j)}}, x ∈ C_{0}, can only take one

additional value, namely the zero word a_{i}(x) = 0 for all i ∈ I_{1}^{(j)}. Thus arguments similar (in fact even simpler) to those above show that |B_{j}| ≤ |I_{1}^{(j)}| + 2 and finally

lim sup_{n→∞} \frac{Pb(n)}{n^{s}} ≤ 2^{s} ∏_{j=1}^{s} ρ_{j}^{s−1}.

Since the same argument applies if M is not centered at 0 we have proved:

Theorem 3. Consider an ergodic translation T : x ↦ x + g on 𝕋^{s} with g = (α_{1}, …, α_{s}). Assume ρ_{j} ∈ (0, 1) \ (α_{j}ℤ + ℤ) for all j = 1, …, s. For m_{j} ∈ [0, 1), j = 1, …, s, let M = ∏_{j=1}^{s}[m_{j}, m_{j} + ρ_{j}) denote an sdimensional box of side lengths ρ_{j}, and b the corresponding Bohr sequence. Then the complexity function of b satisfies

lim_{n→∞} \frac{Pb(n)}{n^{s}} = 2^{s} ∏_{j=1}^{s} ρ_{j}^{s−1}.

We add the following remarks. Complexity and volume versus surface: Let V (M) denote the volume of a box M in 𝕋^{s} and v_{j}(M) = ∏_{i=1,i≠j}^{s} ρ_{i} the (s−1)-dimensional measures (surfaces) of the facettes of M. Then we can express the formula in Theorem 3 in terms of V (M) as well as in terms of the v_{j}(M):

2^{s} ∏_{j=1}^{s} ρ_{j}^{s−1} = 2^{s}V (M)^{s−1} = 2^{s} ∏_{j=1}^{s} v_{j}(M)

Consider first M′ := M_{0} ∪ M_{1}, where the M_{i} are disjoint translates of M. The same arguments as in the proof of Theorem 3 show that M′ induces a Hartman sequence a′ of complexity

lim_{n→∞} \frac{Pa′(n)}{n^{s}} = 2^{s} ∏_{j=1}^{s}(2v_{j}(M)).

Comparison with the value 2^{s} ∏_{j=1}^{s} v_{j}(M) for M indicates that the complexity is related to the surface rather than to the volume.

On the other hand we can consider an automorphism A of 𝕋^{s} (i.e. A ∈ SL(s, ℤ)). The topological generator A(g) and the parallelepiped A(M) induce the same Hartman sequence as g and M. Here the volume V (M) = V (A(M)) is invariant while the product of the surface measures may change.

The interplay between the geometry of more general sets M and the complexity of the corresponding Hartman sequences might be an interesting topic of more systematic future investigations.

Dropping linear independence: If the assumption ρ_{j} ∉ α_{j}ℤ + ℤ fails for j_{1}, …, j_{l}, an investigation of the proof of Theorem 3 shows that

lim_{n→∞} \frac{Pb(n)}{n^{s}} = 2^{s−l} ∏_{j=1}^{s} ρ_{j}^{s−1}.

Complexity determines dimension: Given Pb(n) and the information that M is a box (of some unknown dimension s and unknown side lengths ρ_{j}), Theorem 3 tells us how s can be determined.

References

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

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

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

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

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

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

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

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

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

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

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

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

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

E-mail : christian.steineder@tuwien.ac.at

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

E-mail : reinhard.winkler@tuwien.ac.at