ENTROPY OF CONVOLUTIONS ON THE CIRCLE

ELON LINDENSTRAUSS, DAVID MEIRI AND YUVAL PERES

Abstract. Given ergodic p-invariant measures {μ_{i}} on the 1-torus 𝕋 = ℝ/ℤ, we give a sharp condition on their entropies, guaranteeing that the entropy of the convolution μ_{1} ∗ ⋯ ∗ μ_{n} converges to log p. We also prove a variant of this result for joinings of full entropy on 𝕋^{ℕ}. In conjunction with a method of Host, this yields the following. Denote σ_{q}(x) = qx (mod 1). Then for every p-invariant ergodic μ with positive entropy, 1 ; N ∑_{n=0}^{N−1} σ_{c_{n}}μ converges weak^{∗} to Lebesgue measure as N ⟶ ∞, under a certain mild combinatorial condition on {c_{k}}. (For instance, the condition is satisfied if p = 10 and c_{k} = 2^{k} + 6^{k} or c_{k} = 2^{2^{k}}.) This extends a result of Johnson and Rudolph, who considered the sequence c_{k} = q^{k} when p and q are multiplicatively independent.

We also obtain the following corollary concerning Hausdorff dimension of sum sets: For any sequence {S_{i}} of p-invariant closed subsets of 𝕋, if ∑ dim_{H}(S_{i})/| log dim_{H}(S_{i})| = ∞, then dim_{H}(S_{1} + ⋯ + S_{n}) ⟶ 1.

1. Introduction

Let p ≥ 2 be any integer (p need not be prime), and 𝕋 = ℝ/ℤ the 1-torus. Denote by σ_{p} the p-to-one map x ↦ px (mod 1). The pair (𝕋, σ_{p}) is a dynamical system that has additional structure: 𝕋 is a commutative group (with the group operation being addition mod 1), and σ_{p} is an endomorphism of it. Even in such a simple system, the interaction between the dynamics and the algebraic structure of 𝕋 can be quite subtle; the present work continues the study of this interaction, inspired by the fundamental work of Furstenberg (1967).

Say that a measure μ on 𝕋 is p-invariant if σ_{p}μ = μ, where for every set A ⊂ 𝕋

(σ_{p}μ)(A) =^{def} μ(σ_{p}^{−1}A)

(All measures we consider are Borel probability measures). Lebesgue measure on 𝕋, denoted λ, has entropy log p with respect to σ_{p}, and is the unique p-invariant measure of maximal entropy. Given two p-invariant measures μ and ν, the group structure of 𝕋 naturally yields another p-invariant measure — the convolution μ ∗ ν.

Date: June 5, 1998. Key words and phrases. Entropy, Convolution, Uniform distribution, Hausdorff dimension.

2 ELON LINDENSTRAUSS, DAVID MEIRI AND YUVAL PERES

Our main results, Theorems 1.1 and 1.8, concern the entropy growth for convolutions of p-invariant measures and their ergodic components. These results have applications to the Hausdorff dimension of sum sets and to genericity of the orbits of measures with positive entropy under multiplication by certain integer sequences.

Theorem 1.1. (The Convolution Theorem) Let {μ_{i}} be a sequence of p-invariant and ergodic measures on 𝕋 whose normalized base-p entropies h_{i} = h(μ_{i}, σ_{p})/ log p satisfy

∑_{i=1}^{∞} h_{i} ; | log h_{i}| = ∞.  (1)

Then

h(μ_{1} ∗ ⋯ ∗ μ_{n}, σ_{p}) ⟶ log p monotonically, as n ⟶ ∞.

In particular, μ_{1} ∗ ⋯ ∗ μ_{n} ⟶ λ weak^{∗} and in the d̄ metric (with respect to the base-p partition).

It is relatively easy to see that under hypotheses of the theorem, μ_{1} ∗ ⋯ ∗ μ_{n} ⟶ λ weak^{∗}. This means that

∫ f(x) dμ_{1} ∗ ⋯ ∗ μ_{n} ⟶ ∫ f(x) dλ

for all continuous f, and gives very little information on the dynamics of μ_{1} ∗ ⋯ ∗ μ_{n}.

The convergence of the entropy to log p is equivalent to the much stronger statement that μ_{1} ∗ ⋯ ∗ μ_{n} ⟶ λ in the d̄ metric. As we will not use this metric in our arguments, we only recall its definition here, and refer the reader to Rudolph (1990) for further information. Consider two p-invariant measures ν_{1} and ν_{2} on 𝕋. What d̄(ν_{1}, ν_{2}) < ϵ means, is that there exists a p-invariant measure ν̃ on 𝕋^{2} that projects to ν_{1} in the first coordinate and to ν_{2} in the second coordinate, such that for ν̃-almost every (x, y) ∈ 𝕋^{2}, the set of integers k ≥ 1 for which the kth digits in the base p expansions of x and y differ, has asymptotic density less than ϵ. Once we establish the entropy convergence, the d̄ convergence of μ_{1} ∗ ⋯ ∗ μ_{n} to λ is an immediate corollary of the fact that λ is a Bernoulli measure, and hence is finitely determined; see Rudolph (1990), chapters 6 and 7, for the relevant definitions and proofs.

The entropy condition in Theorem 1.1 is sharp: if {h_{i}} is a sequence of numbers in the range (0, 1) with ∑ h_{i}/| log h_{i}| < ∞, then there exists a sequence of p-invariant ergodic measures {μ_{i}}, such that h(μ_{i}, σ_{p})/ log p = h_{i}, yet μ_{1} ∗ ⋯ ∗ μ_{n} does not converge to Lebesgue measure λ even in the weak^{∗} topology; see Example 10.2.

The convolution theorem has implications for Hausdorff dimension of sum sets:

Corollary 1.2. Let {S_{i}} be a sequence of p-invariant closed subsets of 𝕋, and suppose that

∑_{i=1}^{∞} dim_{H}(S_{i}) | log dim_{H}(S_{i})| = ∞.

Then dim_{H}(S_{1} + ⋯ + S_{n}) ⟶ 1.

By Furstenberg (1967, III.2), the conclusion is equivalent to h_{top}(S_{1} + ⋯ + S_{n}, σ_{p}) → log p.

If the measures μ_{i} are not weakly-mixing, the measure μ_{1} ∗ ⋯ ∗ μ_{n} might be non-ergodic, with different fibers carrying different entropies (see Example 9.4). The reason for this is that for two measures μ and ν on 𝕋, the convolution μ ∗ ν is the projection of the product measure μ × ν on 𝕋 × 𝕋 to 𝕋; if μ and ν are not weakly mixing, then μ × ν need not be ergodic (indeed, μ is weakly mixing iff μ × μ is ergodic). In this case, ergodic components of μ × ν can project to ergodic components of μ ∗ ν with distinct entropies (however, it is easy to see that the entropy of almost all ergodic components of μ ∗ ν is at least the entropy of μ — see Corollary 9.3). In this more general situation, when μ_{i} are not assumed to be weakly mixing, it turns out to be both natural and important for the applications to give more accurate information than that provided by Theorem 1.1 regarding the ergodic components of μ_{1} ∗ ⋯ ∗ μ_{n}. This is done in Theorem 1.8 below; the proof of this more detailed result is rather delicate. As before, such a result can be used to obtain an estimate of Hausdorff dimension of sum sets:

Theorem 1.3. Let {μ_{i}} be a sequence of p-invariant ergodic measures on 𝕋, and suppose that inf_{i} h(μ_{i}, σ_{p}) > 0. Let {S_{i}} be a sequence of Borel subsets of 𝕋, and suppose that μ_{i}(S_{i}) > 0 for all i ≥ 1. Then dim_{H}(S_{1} + ⋯ + S_{n}) ⟶ 1.

Note that the the measures μ_{i}(S_{i}) can tend to zero arbitrarily fast.

Our initial motivation for studying entropy of convolutions of p-invariant measures was to find conditions on a sequence of integers {c_{n}} and a measure μ, which imply that μ is {c_{n}}-generic, i.e., the averages 1 ; N ∑_{n=0}^{N−1} σ_{c_{n}}μ converge weakly to Lebesgue measure λ. In certain cases, this could be established for ergodic p-invariant measures of sufficiently high entropy, and the idea was to deduce {c_{n}}-genericity for all ergodic p-invariant measures of positive entropy by repeated convolutions. Indeed, we establish Theorem 1.4 below using this scheme.

The works of Host (1995) and Meiri (1996) indicate that combinatorial properties of {c_{n}} can be used to prove {c_{n}}-genericity for invariant measures with positive entropy. The combinatorial property we need is weaker than those assumed in the quoted papers; we

4 ELON LINDENSTRAUSS, DAVID MEIRI AND YUVAL PERES

require that the number of pairs among the first p^{n} elements of {c_{n}} which are congruent mod p^{n}, is exponentially smaller than p^{2n}.

Definition 1.1. Given an integer-valued sequence {c_{n}} and an integer p > 1, we define the p-adic collision exponent of the sequence as

Γ_{p}({c_{n}}) = lim sup_{n→∞} log |{0 ≤ k, ℓ < p^{n} : c_{k} ≡ c_{ℓ} (mod p^{n})}| n log p.

Since pairs with k = ℓ are allowed, we always have 1 ≤ Γ_{p}({c_{n}}) ≤ 2. For example, whenever p, q > 1 are relatively prime, the p-adic collision exponent of {q^{n}} is 1. If we assume only that there is some prime factor of p which does not divide q, then {q^{n}} has padic collision exponent < 2. (See section 4 for more details and refinements of this definition.)

Using this definition we can state our results on genericity of orbits of p-invariant measures:

Theorem 1.4. Let {c_{n}} be a sequence with p-adic collision exponent < 2, for some p > 1. Then any p-invariant ergodic measure μ on 𝕋 with positive entropy is {c_{n}}-generic, i.e.,

1 ; N ∑_{n=0}^{N−1} σ_{c_{n}}μ ⟶ λ in the weak^{∗} topology.  (2)

For instance, the hypothesis is satisfied if p = 10 and c_{n} = 2^{n} + 6^{n} or c_{n} = 2^{2^{n}}; see Section 4 for other examples. In fact, the following stronger form of convergence holds. Recall that the space of probability measures on 𝕋 endowed with the weak^{∗} topology is a compact metric space, and take ρ_{∗} be some metric on it.

Theorem 1.5. Under the conditions of Theorem 1.4, μ is {c_{n}}-normal in probability, i.e.,

∫ ρ_{∗}( 1 ; N ∑_{n=0}^{N−1} δ_{c_{n}x} , λ) dμ(x) ⟶ 0.  (3)

To be more specific, let

μ̂(k) = ∫ e^{2πikx} dμ .

Then ρ_{∗}(μ, ν) = ∑_{k=−∞}^{∞} 2^{−|k|}|μ̂(k)−ν̂(k)|^{2} is a metric on the space of all p-invariant probability measures on 𝕋 with the weak^{∗} topology. Define for any integer k ≠ 0,

g_{N}^{(k)}(x) =^{def} 1 ; N ∑_{n=0}^{N−1} e(kc_{n}x),  (4)

where e(x) =^{def} e^{2πix}. Then (2) is equivalent to ∀k ≠ 0, ∫ g_{N}^{(k)}(x) dμ ⟶ 0, while (3) is equivalent to the stronger property: ∀k ≠ 0, ∫ |g_{N}^{(k)}(x)|^{2} dμ ⟶ 0.

ENTROPY OF CONVOLUTIONS ON THE CIRCLE 5

The case c_{n} = q^{n} is known, and inspired our general investigation. Even though there are multiplicatively-independent p and q with Γ_{p}({q^{n}}) = 2, the following is still a corollary of the above results.

Corollary 1.6. [Johnson and Rudolph (1995), Theorem 8.6] Suppose that p, q > 1 are multiplicatively-independent and μ is a p-invariant and ergodic measure on 𝕋 with positive entropy. Then μ is {q^{n}}-normal in probability.

Our proofs of Theorems 1.4–1.5 use two main tools. Host (1995) developed a harmonic analysis method which is most powerful when the entropy of μ is large. The following general result then allows us to use Host’s method for all measures with non-zero entropy by reduction (via convolutions) to the case where the entropy of the measure μ is sufficiently high.

Theorem 1.7. (The Bootstrap Lemma) Suppose that C is a class of p-invariant measures on 𝕋 with the following properties:

(i) If μ is p-invariant and ergodic and μ ∗ μ ∈ C, then μ ∈ C. (ii) If μ is p-invariant and almost every ergodic component of μ is in C, then μ ∈ C. (iii) There exists some constant h_{0} < log p such that every p-invariant and ergodic measure μ with h(μ, σ_{p}) > h_{0} is in C. Then C contains all p-invariant ergodic measures with positive entropy.

We derive Theorem 1.7 from a variant of Theorem 1.1 for joinings of full entropy:

Definition 1.2. Let {μ_{i}}_{i≥1} be a sequence of p-invariant and ergodic measures on 𝕋. A measure ν^{(n)} on 𝕋^{n} is called a joining of μ_{1}, …, μ_{n} if

(i) ν^{(n)} is σ_{p} × ⋯ × σ_{p} invariant, (ii) The projection of ν^{(n)} on the ith coordinate is μ_{i}, for i = 1, …, n. The measure ν^{(n)} is called a joining of full entropy of μ_{1}, …, μ_{n} if in addition

h(ν^{(n)}, σ_{p} × ⋯ × σ_{p}) = ∑_{i=1}^{n} h(μ_{i}, σ_{p}).

A measure μ̃ on 𝕋^{ℕ} is called a joining of full entropy of {μ_{i}}_{i=1}^{∞} if for every n, the projection of μ̃ to the first n coordinates is a joining of full entropy of μ_{1}, …, μ_{n}.

Theorem 1.8. Let {μ_{i}}_{i=1}^{∞} be a sequence of p-invariant and ergodic measures on 𝕋 such that inf_{i} h(μ_{i}, σ_{p}) > 0. Suppose that μ̃ is a joining of full entropy of {μ_{i}}. Define Θ^{n} : 𝕋^{ℕ} → 𝕋 by Θ^{n}(x) = x_{1} + ⋯ + x_{n} (mod 1). Then

h(Θ^{n}μ̃, σ_{p}) ⟶ log p monotonically, as n ⟶ ∞.

6 ELON LINDENSTRAUSS, DAVID MEIRI AND YUVAL PERES

Theorem 1.8 is not valid under the weaker entropy assumptions of Theorem 1.1. Indeed, it is possible to find a joining of full entropy μ̃ with entropies satisfying (1), such that Θ^{n}μ̃ does not even converge weak^{∗} to λ. See Example 10.5.

1.1. Background. In Furstenberg (1967) many aspects of the dynamics of (𝕋, σ_{p}) are discussed, and in particular it is shown that there are no non-trivial σ_{p}-invariant closed subsets of 𝕋 that are also invariant under σ_{q} for p and q multiplicatively independent (i.e. log p/ log q ∉ ℚ), the trivial examples being the whole of 𝕋 and some finite sets of periodic points. Furstenberg conjectured the following stronger result: Furstenberg’s Conjecture (1967) The only ergodic invariant measures for the semigroup of circle endomorphisms generated by σ_{p}, and σ_{q} for p and q multiplicatively independent are Lebesgue measure λ, and atomic measures concentrated on periodic orbits.

Most of the research on the dynamics of (𝕋, σ_{p}) has been related to this conjecture. It has been proven for measures with positive entropy — a partial result was proved by Lyons (1988), and the case of p and q relatively prime was settled by Rudolph (1990a). The case of p and q multiplicatively independent but not relatively prime is harder, and was proved by Johnson (1992). Another argument along the lines of Lyons (1988) for the multiplicatively independent case was given by Feldman (1993). To tackle the case of measures with zero entropy it seems that a totally different method is needed.

In Feldman and Smorodinsky (1992), Johnson and Rudolph (1995) and Host (1995), the measure is only assumed to be σ_{p}-invariant, and the authors consider the action of σ_{c_{n}} on μ for the special case of c_{n} = q^{n}. As shown in Meiri (1996), the methods of Host (1995) imply the following result:

Theorem A. For p > 1, let {c_{n}} be a sequence with p-adic collision exponent 1. Then any p-invariant ergodic measure μ with positive entropy is {c_{n}}-normal a.e., i.e., {c_{n}x (mod 1)} is uniformly distributed for μ-almost every x ∈ 𝕋.

This theorem gives a significantly stronger statement than Theorems 1.4–1.5, but for a smaller class of sequences {c_{n}} — and in particular gives no information for the case c_{n} = q^{n}, with p and q not relatively prime. (Recalling the definition of g_{N}^{(k)} in (4), this assertion is equivalent to ∀k ≠ 0, g_{N}^{(k)} ⟶ 0 μ−a.e.) A more detailed history of this problem can be found in Host (1995) and Meiri (1996).

For the convolution results (Theorems 1.1 and 1.8), the case of measures with zero entropy is not interesting, as the entropy of a convolution of measures, each having zero entropy, has zero entropy, and hence does not converge d̄ to λ.

ENTROPY OF CONVOLUTIONS ON THE CIRCLE 7

Regarding Theorems 1.2–1.3, one can ask if a stronger conclusion holds, namely, that S_{1} + ⋯ + S_{n} contains an interval for all n sufficiently large. Brown and Williamson (1987) showed that if μ is a measure on 𝕋 which makes the digits in base p i.i.d. non-degenerate variables, and μ(S_{i}) > 0 for all i, then this stronger assertion is true. However, under our weaker assumptions, this conclusion is not valid, even if all the sets S_{i} coincide: By Furstenberg (1967, Thm. III.2) there exists a minimal p-invariant closed set S ⊂ 𝕋 with positive dimension. By Proposition IV.1 of the same article, the sum sets S + ⋯ + S of any finite order have Lebesgue measure zero. For more information about Lebesgue measure of sum sets see Brown, Keane, Moran and Pearce (1988).

1.2. Overview. The paper is organized as follows.

In Section 2 we show how one can deduce the Bootstrap Lemma from Theorem 1.8, and proceed to prove Theorem 1.4.

In Section 3 we discuss convergence in probability and prove Theorem 1.5.

In Section 4 we derive Corollary 1.6 from Theorem 1.4, and discuss p-adic combinatorial properties, and in particular we give an algorithm for computing the p-adic collision exponent of linear recursive sequences.

In sections 5–7 we prove our main results, Theorems 1.1 and 1.8. The simplest case is proving Theorem 1.1 for prime p. In this case, however, one does not need to use a substantial part of the ideas behind the proof. We recommend for first reading to have in mind the case p = 10, with μ_{i} = μ for all i for Theorem 1.1. Theorem 1.8 is interesting already when p is a prime (and we again recommend considering first the case where all μ_{i} are identical).

Section 5 contains results about finite cyclic groups which are crucial to the proof of the convolution theorems. Lemmas 5.1 and 5.2 study convolutions of measures on a finite cyclic group and contain one key idea in the proof, namely that the convolution of a sequence of measures on a finite cyclic group of order N (we shall use N = p^{k}) tends to be invariant under a subgroup that will typically be rather large (in the cases we will be interested in, this subgroup will be of order approximately p^{αk} for some 0 < α < 1). Lemma 5.3 shows that if a measure on ℤ/p^{k}ℤ is almost invariant under a subgroup of size p^{αk}, the distribution of the αk high order digits is nearly uniform.

In Section 6 we begin to show how convolutions of measures on ℤ/p^{k}ℤ relate to convolutions of measures on 𝕋, where we get measures on ℤ/p^{k}ℤ from measures on 𝕋 by considering the conditional distribution of the first k digits in the base-p expansion of x ∈ 𝕋, given the rest of the digits. In Section 7 we continue in this approach and prove Theorem 1.1. The

8 ELON LINDENSTRAUSS, DAVID MEIRI AND YUVAL PERES

basic argument is that if the entropy of μ_{1} ∗ ⋯ ∗ μ_{n} is almost

sup_{N∈ℕ}h(μ_{1} ∗ ⋯ ∗ μ_{N}, σ_{p}),

then for any k ≥ 1 the distribution of the first k digits of x given the rest of the digits (x chosen according to μ_{1} ∗ ⋯ ∗ μ_{n}) must be nearly invariant under a subgroup G ⊂ ℤ/p^{k}ℤ of size p^{αk} — for if it is not, then the entropy of μ_{1} ∗ ⋯ ∗ μ_{n} can be significantly increased by further convolutions. This implies that the first αk digits of x are distributed nearly uniformly. Since k is arbitrary, it follows that h(μ_{1} ∗ ⋯ ∗ μ_{n}, σ_{p}) ≃ log p.

In Section 8 we prove Theorem 1.8. The main observation is that if one chooses an element in 𝕋^{ℕ} according to a joining of full entropy, the components of this vector are almost independent (Lemma 8.1). This allows us to prove Theorem 1.8 along similar lines as Theorem 1.1.

In Section 9 we use the connection between entropy of measures and Hausdorff dimension, to derive Theorems 1.2–1.3 from the results about convolutions of measures.

Section 10 contains some concluding remarks, questions and examples.

2. Proof of the Bootstrap Lemma and Theorem 1.4

In order to derive the Bootstrap Lemma from Theorem 1.8, we need the following lemma:

Lemma 2.1. Let μ denote a p-invariant and ergodic measure on 𝕋, and let μ × μ = ∫ ν_{γ} dγ denote the ergodic decomposition of μ × μ. Then ν_{γ} is a self-joining of μ for a.e. γ, and h(ν_{γ}, σ_{p} × σ_{p}) = 2h(μ, σ_{p}) a.e.

Proof. By ergodicity of μ, almost-surely ν_{γ} projects to μ in both coordinates. Obviously, h(ν_{γ}, σ_{p} × σ_{p}) ≤ h(μ × μ, σ_{p} × σ_{p}) = 2h(μ, σ_{p}). On the other hand, by Rokhlin’s theorem, h(μ × μ, σ_{p} × σ_{p}) = ∫ h(ν_{γ}, σ_{p} × σ_{p}) dγ, therefore h(ν_{γ}, σ_{p} × σ_{p}) = 2h(μ, σ_{p}) a.e. ■

Proof of Theorem 1.7 (The Bootstrap Lemma): Let μ be some p-invariant and ergodic measure with positive entropy. We claim that μ ∈ C. Suppose that this is not the case, and write ν^{(1)} =^{def} μ and h =^{def} h(μ, σ_{p}) > 0. From property (i) of C, also μ ∗ μ ∉ C. Let μ × μ = ∫ ν_{γ} dγ denote the ergodic decomposition of μ × μ with respect to σ_{p} × σ_{p}. Then

μ ∗ μ = Θ^{2}(μ × μ) = ∫ Θ^{2}(ν_{γ}) dγ,

where as before Θ^{k}(x_{1}, …, x_{k}) =^{def} x_{1} + ⋯ + x_{k} (mod 1). From property (ii), for a set of γ with positive measure, Θ^{2}(ν_{γ}) ∉ C. By Lemma 2.1, there exists an ergodic component of μ × μ, which we designate ν^{(2)}, such that ν^{(2)} is an ergodic self-joining of μ with entropy

ENTROPY OF CONVOLUTIONS ON THE CIRCLE 9

2h and Θ^{2}(ν^{(2)}) ∉ C. Apply now the same procedure to ν^{(2)}, finding an ergodic component ν^{(4)} of ν^{(2)} × ν^{(2)}, such that ν^{(4)} is a self-joining of ν^{(2)} with entropy 4h, and Θ^{4}(ν^{(4)}) ∉ C. Continuing this way we obtain a sequence of measures {ν^{(k)}}, defined for k a power of 2, such that Θ^{k}(ν^{(k)}) ∉ C, ν^{(k)} is an ergodic self-joining of μ in 𝕋^{k}, and h(ν^{(k)}, σ_{p} × ⋯ × σ_{p}) = kh. Define ν^{(k)} for other values of k by projection, and let μ̃ be the inverse limit of these measures, defined on 𝕋^{ℕ}. Then μ̃ is a joining of full entropy. Applying Theorem 1.8 we conclude that h(Θ^{k}ν^{(k)}, σ_{p}) = h(Θ^{k}μ̃, σ_{p}) ⟶ log p. As Θ^{k}μ̃ ∉ C for k a power of 2, this contradicts property (iii). ■

We next deduce Theorem 1.4 from the Bootstrap Lemma. Given an integer-valued sequence {c_{n}}, say that a measure μ is {c_{n}}-generic if

1 ; N ∑_{n=0}^{N−1} σ_{c_{n}}μ ⟶ λ weakly, as N ⟶ ∞.

The basic tool we use is the following observation in Meiri (1996, Theorem 3.1, and note in section 8, Problem 3), based on Host (1995):

Proposition 2.2. Fix an integer p > 1 and a sequence {c_{k}} with p-adic collision exponent < 2. Then there exists a constant h_{0} < log p such that every p-invariant and ergodic measure μ with h(μ, σ_{p}) > h_{0} is {c_{n}}-normal a.e.; in particular, μ is {c_{n}}-generic.

Remark: This proposition, as well as Theorems 1.4–1.5, hold under the weaker assumption that the reduced p-adic exponent of {c_{k}} is less than 2; see section 4 for the definition and more details.

The following lemma is a consequence of the extremality of ergodic measures:

Lemma 2.3. [Johnson and Rudolph, 1995] Suppose that ν, ν_{1}, ν_{2}, … are invariant measures, and that ν is ergodic. Suppose also that

1 ; N ∑_{n=1}^{N} ν_{n} ⟶ ν weakly.

Then there exists a zero-density set J ⊂ ℕ such that ν_{n} ⟶ ν (weakly) as n ⟶_{n∉J} ∞.

Proposition 2.4. An invariant measure μ is {c_{n}}-generic iff μ ∗ μ is {c_{n}}-generic.

Proof. By the previous lemma, μ is {c_{n}}-generic iff there exists a zero-density set J ⊂ ℕ such that σ_{c_{n}}μ ⟶ λ as n ⟶_{n∉J} ∞. This is equivalent to

lim_{n∉J} μ̂(ac_{n}) = 0, for all a ∈ ℤ ∖ {0}.  (5)

Since { \atop μ ∗ μ} = μ̂^{2}, equation (5) holds iff it holds when μ is replaced by μ ∗ μ. ■

Proof of Theorem 1.4: From Propositions 2.2 and 2.4 it follows that the class of pinvariant measures which are {c_{n}}-generic satisfies the conditions of the Bootstrap Lemma (Theorem 1.7), and the assertion follows. ■

3. Convergence in Probability and Proof of Theorem 1.5

Recall the definition (4) of g_{N}^{(k)}. Given a measure μ, define μ_{#} by μ_{#}(A) = μ(−A).

Lemma 3.1. For any measure μ,

∫ |g_{N}^{(k)}(x)|^{2} dμ ≤ (∫ |g_{N}^{(k)}(x)|^{2} dμ∗μ_{#})^{1 2} .

Proof. As { \atop μ∗μ_{#}} = |μ̂|^{2}, by Cauchy-Schwarz we have

∫ |g_{N}^{(k)}(x)|^{2} dμ = 1 ; N^{2} ∑_{m,l=0}^{N−1} ∫ e(k(c_{l} − c_{m})x) dμ = 1 ; N^{2} ∑_{m,l=0}^{N−1} μ̂(k(c_{l} − c_{m}))

≤ 1 ; N ( ∑_{m,l=0}^{N−1} |μ̂(k(c_{l} − c_{m}))|^{2})^{1 2} = (∫ |g_{N}^{(k)}(x)|^{2} dμ∗μ_{#})^{1 2} . ■

Proof of Theorem 1.5: A slight change in the proof of the Bootstrap Lemma lets us replace the first condition by the following: (i’) If μ is p-invariant and μ∗μ_{#} ∈ C, then μ ∈ C. Taking C to be the class of p-invariant measures for which (3) holds, condition (i’) is satisfied by the last lemma, (ii) is immediate by Lebesgue Dominated Convergence, while (iii) follows from Proposition 2.2. ■

The type of convergence in Theorem 1.5 is, in general, stronger than weak convergence:

Example: Let c_{n} = 2^{2^{n}}. For j = 0, 1 consider random variables X^{(j)} = ∑_{i=1}^{∞} x_{i}^{(j)}2^{−i}, where x_{k^{2}}^{(j)} = j for all k, and all other digits are i.i.d. uniform on {0, 1}. Let μ_{j} be the distribution of X_{j}, and take μ = 1 2(μ_{1} +μ_{2}). Then μ is {2^{2^{n}}}-generic, but is not {2^{2^{n}}}-normal in probability.

However, there are cases where the stronger type of convergence follows from the weaker one. The following proposition was obtained by Johnson and Rudolph (1995, §8) using general convex analysis. Here we give a more direct argument.

Proposition 3.2. Let q > 1. Then if μ is {q^{n}}-generic, it is also {q^{n}}-normal in probability.

Proof. For any L, by Cauchy-Schwarz,

| 1 ; N ∑_{n=0}^{N−1} g_{L}^{(k)} ∘ σ_{q^{n}} |^{2} ≤ 1 ; N ∑_{n=0}^{N−1} |g_{L}^{(k)}|^{2} ∘ σ_{q^{n}} ,

and so by (2) applied for c_{n} = q^{n},

lim sup_{N→∞} ∫ | 1 ; N ∑_{n=0}^{N−1} g_{L}^{(k)} ∘ σ_{q^{n}} |^{2} dμ ≤ lim sup_{N→∞} 1 ; N ∑_{n=0}^{N−1} ∫ |g_{L}^{(k)}|^{2} ∘ σ_{q^{n}} dμ = ∫ |g_{L}^{(k)}|^{2} dλ = 1 ; L .

Since

|g_{N}^{(k)} − 1 ; N ∑_{n=0}^{N−1} g_{L}^{(k)} ∘ σ_{q^{n}} | ≤ 2L ; N,

we conclude that for any L,

lim sup_{N→∞} ∫ |g_{N}^{(k)}|^{2} dμ ≤ 1 ; L

it follows that μ is {q^{n}}-normal in probability. ■

4. The p-adic Collision Exponent

Denote by ord_{G}(x) the order of an element x in a finite group G. The following statement was noted by Host (1995):

Proposition 4.1. If p, q > 1 and p, q are relatively prime, then there exists α > 0 such that

∀n ≥ 1, ord_{ℤ/p^{n}ℤ}(q) ≥ αp^{n}.

In particular, in this case the p-adic collision exponent of {q^{n}} is 1.

Proposition 4.2. Suppose that p, q > 1 and there exists some prime factor p_{∗} of p that does not divide q. Then the p-adic collision exponent of {q^{n}} is < 2.

Proof. Define o_{n} =^{def} ord_{ℤ/p_{∗}^{n}ℤ}(q), and use Proposition 4.1 to find α > 0 such that o_{n} ≥ αp_{∗}^{n}. If q^{k} ≡ q^{ℓ} (mod p^{n}) then p_{∗}^{n}|q^{|k−ℓ|} − 1, hence o_{n}|k − ℓ. Thus

|{0 ≤ k, ℓ < p^{n} : q^{k} ≡ q^{ℓ} (mod p^{n})}| ≤ p^{n} · (p^{n}/o_{n}).

Hence

Γ_{p}({q^{n}}) = lim sup_{n→∞} log |{0 ≤ k, ℓ < p^{n} : q^{k} ≡ q^{ℓ} (mod p^{n})}| n log p
≤ lim sup_{n→∞} log(p^{n} · (p^{n}/o_{n})) ; n log p ≤ 2 − log p_{∗} ; log p < 2.
■

12 ELON LINDENSTRAUSS, DAVID MEIRI AND YUVAL PERES

Proof of Corollary 1.6: By Proposition 3.2, it is enough to prove weak convergence. If some prime factor of p does not divide q, we are done by the last proposition and Theorem 1.4. Otherwise, note the following simple observations: (A) If the theorem holds replacing q by some power q^{ℓ}, then it holds for q as well. The reason is that we can decompose

1 ; Nℓ ∑_{n=0}^{Nℓ−1} σ_{q^{n}}μ = 1 ; ℓ ∑_{k=0}^{ℓ−1} 1 ; N ∑_{n=0}^{N−1} σ_{q^{ℓn}}(σ_{q^{k}}μ)

and apply the theorem to the measures σ_{q^{k}}μ, for k = 0, …, ℓ − 1. (B) If p|q and the theorem holds for p and q/p, then it also holds for p and q. This is because σ_{q/p}μ = σ_{q}μ for p-invariant μ.

For any multiplicatively independent p, q we can find some k, ℓ such that p^{k}|q^{ℓ} and some prime factor of p does not divide q′ = q^{ℓ}/p^{k}, and use the above. ■

It is easy to see that Theorems 1.4–1.5 are not affected if we only assume that {c_{n}} differs on a set of arbitrarily small density from a sequence with p-adic collision exponent smaller than 2. This motivates the following definition:

Definition 4.1. The reduced p-adic collision exponent of a sequence {c_{n}} is

Γ′_{p}({c_{n}}) = lim_{ε→0} inf_{{c′_{n}}} Γ_{p}({c′_{n}}),

where {c′_{n}} ranges over sequences which agree with {c_{n}} on a set of indices with density ≥ 1 − ε.

We always have 1 ≤ Γ′_{p}({c_{n}}) ≤ Γ_{p}({c_{n}}) ≤ 2. The sequence c_{n} = n^{ℓ} for ℓ ≥ 2 has p-adic collision exponent 2(1 − ℓ^{−1}), while its reduced collision exponent can be seen to be 1.

Computation of Γ′_{q}({c_{n}}) for a linear recursion. We conclude this section with an algorithm for computing the reduced q-adic collision exponent of any linear recursion sequence and any integer q > 1. Let {c_{k}} be such a sequence, i.e., for certain integers a_{0}, …, a_{n−1} (a_{0} ≠ 0) we have

∀k > n, c_{k} + a_{n−1}c_{k−1} + a_{n−2}c_{k−2} + ⋯ + a_{0}c_{k−n} = 0.  (6)

Denote by f(x) = x^{n} + a_{n−1}x^{n−1} + ⋯ + a_{1}x + a_{0} the recursion polynomial of (6). We can assume that f is of minimal degree. If {c_{k}} is constant along some arithmetic progression, surely Γ′_{q}({c_{n}}) = 2. Call f non-degenerate if the only sequence {c_{k}} satisfying f and having a constant arithmetic subsequence is the zero sequence. We quote the following results:

ENTROPY OF CONVOLUTIONS ON THE CIRCLE 13

Theorem 4.3. [Meiri (1996), Theorems 5.1–5.2] Let f denote a linear recursion.

(i) f is non-degenerate iff no roots of f, or their ratios, are roots of unity. (ii) Let {c_{k}} be a sequence of integers satisfying f, and suppose that {c_{k}} has no constant arithmetic subsequences. Then Γ′_{q}({c_{k}}) = 1 for any q > 1 relatively prime to f(0).

Note: In fact a stronger result is proved there: after discarding a set of arbitrarily small density, {c_{k}} has bounded cells, i.e.,

sup_{n} max_{0≤t<q^{n}} |{0 ≤ k < q^{n} : c_{k} ≡ t (mod q^{n})}| < ∞.

For proofs of the results in the rest of this section, see Meiri (1997).

Call a sequence {c_{k}} an intertwining of the sequences {c_{k}^{(1)}}, …, {c_{k}^{(N)}} if c_{N(k−1)+r} = c_{k}^{(r)} for all k ≥ 1 and r = 1, …, N.

Lemma 4.4. If {c_{k}} is an intertwining of the sequences {c_{k}^{(1)}}, …, {c_{k}^{(N)}}, then

Γ_{q}({c_{k}}) = max_{1≤r≤N} Γ_{q}({c_{k}^{(r)}}),  (7)

and a similar result holds for the reduced collision exponent.

For a polynomial f(x) = x^{n} + a_{n−1}x^{n−1} + ⋯ + a_{1}x + a_{0}, define

gcd[f] = gcd(a_{0}, a_{1}, …, a_{n−1}).

Theorem 4.5. Let {c_{k}} be a linear recursion sequence, and suppose that its minimal recursion polynomial f is non-degenerate. Decompose q = q_{1}q_{2} such that q_{1} is the maximal factor of q that is relatively prime to gcd[f]. Then

Γ′_{q}({c_{k}}) = 2 − log q_{1} ; log q = 1 + log q_{2} ; log q .  (8)

In particular we have Γ′_{q}({c_{k}}) = 1 iff no prime factor of q divides gcd[f], and Γ′_{q}({c_{k}}) = 2 iff all prime factors of q divide gcd[f].

Algorithm. Computing the reduced q-adic collision exponent of a linear recursion sequence.

1. Compute the minimal recursion polynomial f of {c_{k}}.

Method: solve linear equations on the coefficients of f.

2. If f(−1) = 0, consider separately {c_{2k}} and {c_{2k+1}}: each satisfies a recursion of lower degree; apply Lemma 4.4.

3. If f(1) = 0, f′(1) ≠ 0, find constants r, s such that the minimal polynomial of {rc_{k} − s} does not vanish at 1, and replace {c_{k}} by the latter sequence. The minimal polynomial of the new

14 ELON LINDENSTRAUSS, DAVID MEIRI AND YUVAL PERES

sequence does not vanish at 1.

Method: find a rational number s/r such that {c_{k} − s/r} satisfies f(x)/(x − 1).

4. If f(1) = f′(1) = 0, then Γ′_{q}({c_{k}}) = 1.

5. Check if f is an intertwining of sequences, satisfying shorter recursions. Method: find the maximal number D such that φ(D) ≤ n, where φ is Euler’s totient function. For d = 2, …, D, display {c_{k}} as an intertwining of d subsequences, and compute their minimal polynomials. If for some d all the resulting polynomials have degree less than deg f, apply Lemma 4.4. If not, then f is non-degenerate.

6. If f is non-degenerate, apply (8) to compute Γ′_{q}({c_{k}}).

Examples:

1. The sequence 4, 9, 39, 219, … which satisfies the recursion c_{k} = 7c_{k−1} −6c_{k−2} has minimal polynomial f(x) = x^{2} − 7x + 6. In step 3 we see that f(1) = 0; indeed, c_{k} = 3 + 6^{k} and so Γ′_{q}({c_{k}}) = Γ_{q}({c_{k}}) = Γ_{q}({6^{k}}) = 1 + log 2^{m}3^{ℓ} ; log q, assuming that 2^{m}∥q, 3^{ℓ}∥q. On the other hand, a sequence {c_{k}} whose minimal polynomial is (x − 1)f(x) satisfies Γ′_{q}({c_{k}}) = 1 for every q > 1.

2. Suppose that f(x) = 1 + x^{3} + x^{6} is the minimal recursion of {c_{k}}. Then {c_{k}} is an intertwining of 3 sequences, each satisfying the Fibonacci recursion F_{k} = F_{k−1} + F_{k−2}. If either of these sequences is identically zero, then Γ′_{q}({c_{k}}) = 2. Otherwise, Γ′_{q}({c_{k}}) = 1.

3. If the minimal polynomial f of {c_{k}} is non-degenerate, and some prime factor of q does not divide gcd[f], then Γ′_{q}({c_{k}}) < 2.

4. Suppose that c_{k} = r_{1}(k)q_{1}^{k} + … + r_{N}(k)q_{N}^{k}, where r_{i} are polynomials. Suppose also that there exists some prime factor of q that does not divide some q_{i}. Then Γ′_{q}({c_{k}}) < 2.

5. Uniform Distribution in Subgroups

The next three simple lemmas are the key to proving Theorem 1.1.

Lemma 5.1. Let {X_{n}} be an infinite sequence of independent random variables with values in ℤ_{N} =^{def} ℤ/Nℤ, for some fixed integer N > 1. Suppose that for some non-zero g ∈ ℤ_{N},

∑_{j=1}^{∞} ∑_{x=0}^{N−1} min{ℙ(X_{j} = x), ℙ(X_{j} = x + g)} = ∞.  (9)

Let S_{n} = X_{1} + ⋯ + X_{n} (mod N). Then for any x ∈ ℤ_{N},

lim_{n→∞} (ℙ(S_{n} = x + g) − ℙ(S_{n} = x)) = 0 .  (10)

Proof. We first prove the following property of Fourier coefficients of S_{n}:

∀ℓ ∈ ℤ_{N}, gℓ ≢ 0 (mod N) ⟹ lim_{n→∞} Ŝ_{n}(ℓ) = 0.  (11)

For some x ∈ ℤ_{N} we have

∑_{j=1}^{∞} min{ℙ(X_{j} = x), ℙ(X_{j} = x + g)} = ∞.

Set p_{j} = min{ℙ(X_{j} = x), ℙ(X_{j} = x + g)}. Denoting φ_{ℓ}(t) = exp(2πiℓt/N), we have

Ŝ_{n}(ℓ) = E φ_{ℓ}(∑_{j=1}^{n}X_{j}) = ∏_{j=1}^{n} E φ_{ℓ}(X_{j}).

Write

|E φ_{ℓ}(X_{j})| = | ∑_{k=0}^{N−1} ℙ(X_{j} = k)φ_{ℓ}(k)|
≤ p_{j} |φ_{ℓ}(x) + φ_{ℓ}(x + g) ; 2| + (1 − p_{j}) = p_{j} |1 + exp(2πiℓg/N) ; 2| + (1 − p_{j}) .

Since N ∤ gℓ, we have |1 + exp(2πiℓg/N)|/2 ≤ γ < 1, for γ =^{def} |1 + exp(2πi/N)|/2. Hence

|E φ_{ℓ}(X_{j})| ≤ 1 − (1 − γ)p_{j}.

By our assumptions, ∑_{j=1}^{∞}(1 − γ)p_{j} = ∞, hence lim_{n→∞} ∏_{j=1}^{n} |E φ_{ℓ}(X_{j})| = 0, and (11) follows.

To prove (10), use inverse Fourier transform to write

ℙ(S_{n} = x + g) − ℙ(S_{n} = x) = 1 ; N ∑_{ℓ=0}^{N−1} Ŝ_{n}(ℓ)(φ_{−ℓ}(x + g) − φ_{−ℓ}(x)).

If N|gℓ we have φ_{−ℓ}(x + g) − φ_{−ℓ}(x) = 0. If N ∤ gℓ, apply (11). ■

Lemma 5.2. Let {X_{n}} be an infinite sequence of independent random variables with values in ℤ_{N} =^{def} ℤ/Nℤ, for some fixed integer N > 1. Suppose that there exists a subgroup G ⊆ ℤ_{N}, generated by g_{1}, …, g_{r}, such that (9) holds for g = g_{1}, …, g_{r}. Let S_{n} = X_{1} + ⋯ + X_{n} ( mod N), and let S_{n} mod G denote the projection of S_{n} to ℤ_{N}/G. Then

E H(S_{n}|S_{n} mod G) ⟶ log |G|.

Proof. Let g_{0} ∈ G be a generator of G. Applying Lemma 5.1 for g = g_{1}, …, g_{r}, we see that (10) holds for g = g_{0} as well. Denote for a moment S̃_{n} = S_{n} mod G. If G = ℤ_{N}, the result is clear: S̃_{n} is constant, while the distribution of S_{n} converges to the uniform distribution on ℤ_{N}, whose entropy is log |ℤ_{N}| = log |G|. In the general case, write

E H(S_{n}|S̃_{n}) = ∑_{t+G∈ℤ_{N} /G}ℙ(S̃_{n} = t + G)H(S_{n}|S̃_{n} = t + G).

By (10) for g = g_{0}, the conditional distribution of S_{n} on every coset t + G converges to the uniform distribution whose entropy is again log |G|, and we are done. ■

In the next lemma we restrict our attention to N = p^{k} and identify ℤ_{p^{k}} with k-digit numbers in base p. For n ≤ k, let π_{n} : ℤ_{p^{k}} ⟶ ℤ_{p^{n}} denote the projection to the n mostsignificant digits, i.e., π_{n}(z) = ⌊z/p^{k−n}⌋.

Lemma 5.3. Let Y be a ℤ_{p^{k}}-valued random variable. Let G be a subgroup of ℤ_{p^{k}}, and suppose that n satisfies p^{n} ≥ |G|. Then

H(π_{n}(Y)) ≥ H(Y |Y mod G) = H(Y) − H(Y mod G).

Proof. In every coset t + G, the projection π_{n} is one-to-one. Thus π_{n}(Y) and Y mod G determine Y, hence H(π_{n}(Y)) + H(Y mod G) ≥ H(Y). ■

Finally, we state the following simple lemma that will be used to show that the subgroup G we get in 5.1 will be large. For t = ∑_{i=1}^{k} t_{i}p^{k−i} ∈ ℤ/p^{k}ℤ we call t_{i} the ith digit of t.

Lemma 5.4. Let t ∈ G ⊂ ℤ/p^{k}ℤ, and suppose that the ith digit of t is non-zero. Then t generates in G a subgroup of order at least p_{∗}^{i}, where p_{∗} is the smallest prime divisor of p.

We leave the proof of this lemma to the reader.

6. Entropy and Subgroups

Notations: Suppose that μ̃ is a σ_{p} × σ_{p} × ⋯ -invariant measure on 𝕋^{ℕ}. For x ∈ 𝕋^{ℕ} we denote its projection on coordinates by superscripts, e.g., x^{a...b} = π^{a...b}(x) denotes projection to coordinates a, …, b. Similarly, x^{a} = x^{a...a} = π^{a}(x). We identify numbers in 𝕋 with their base-p expansion. In this identification, σ_{p} is equivalent to a shift map on {0, …, p − 1}^{ℕ}, and we denote by x_{c...d}^{i} the d − c + 1 digits starting at point c in the base-p expansion of x^{i}. For every i let α_{1}^{i} denote the partition of 𝕋^{ℕ} according to the first digit of x^{i}, and we use the notation

α_{c...d}^{a...b} =^{def} ⋁_{i=a}^{b} ⋁_{j=c}^{d} σ_{p}^{−j+1}α_{1}^{i} .

ENTROPY OF CONVOLUTIONS ON THE CIRCLE 17

for the partition of 𝕋^{ℕ} according to the digits c, …, d of x^{a}, …, x^{b}. By a slight abuse of notation α_{1}^{i} also denotes the analogous partition of π^{i}(𝕋^{ℕ}). Recall the definition of the function Θ^{n}: 𝕋^{ℕ} → 𝕋 as the sum mod 1 of x^{1}, …, x^{n}. We denote the partition of 𝕋^{ℕ} according to the first k digits of Θ^{n}(x) by θ_{1...k}^{n}, etc.

We also use the following notation for a measure μ and a finite partition γ: we denote by D_{μ}(γ) the probability vector {μ(C) : C ∈ γ}, and by H_{μ}(γ) = H(D_{μ}(γ)) its entropy. Similarly, given a σ-algebra 𝔅 we denote by D_{μ}(γ|𝔅) the conditional distribution of γ given 𝔅, and by H_{μ}(γ|𝔅) = H(D_{μ}(γ|𝔅)) its entropy; note that this is a function on the measure space, not a constant.

In our context it is natural to view x_{1...k}^{a} as an element of ℤ/p^{k}ℤ, and thus if G is a subgroup of ℤ/p^{k}ℤ, it makes sense to consider x_{1...k}^{a} mod G or the corresponding partition of π^{a}(𝕋^{ℕ}), which is α_{1...k}^{a} mod G.

Proposition 6.1. Let μ, ν be two p-invariant measures, and G a subgroup of ℤ/p^{k}ℤ for some k ∈ ℕ. Then

E H_{μ∗ν}(x_{1...k} mod G|x_{k+1...∞}) ≥ E H_{μ}(x_{1...k} mod G|x_{k+1...∞}).

Proof. Define independent random variables X, Y with X ∼ μ and Y ∼ ν. Then X + Y ∼ μ ∗ ν. Denote by α, β, γ the partitions according to the first digit in the base-p expansion of X, Y and X + Y, respectively. We have

E H_{μ∗ν}(x_{1...k} mod G|x_{k+1...∞}) = E H_{μ×ν}(γ_{1...k} mod G|γ_{k+1...∞})
≥ E H_{μ×ν}(γ_{1...k} mod G|α_{k+1...∞} ∨ β_{1...∞}).  (12)

However, given all we have conditioned upon on the right hand side of (12), α_{1...k} mod G uniquely determines γ_{1...k} mod G, and v.v. Hence

H_{μ×ν}(γ_{1...k} mod G|α_{k+1...∞} ∨ β_{1...∞}) = H_{μ×ν}(α_{1...k} mod G|α_{k+1...∞} ∨ β_{1...∞})
= H_{μ×ν}(α_{1...k} mod G|α_{k+1...∞}),

using the independence of α and β in the last equality. This gives the required inequality. ■

Corollary 6.2. Let {μ_{i}} be a sequence of p-invariant measures, and denote μ̃ = ∏ μ_{i}. Suppose that G is a subgroup of ℤ/p^{k}ℤ for some k ∈ ℕ. Then

E Hμ̃(θ_{1...k}^{n} mod G|θ_{k+1...∞}^{n})

is monotone nondecreasing in n.

Lemma 6.3. Let μ be a measure on 𝕋, and suppose that G ⊂ ℤ/p^{k}ℤ is a group of size ≥ p^{ℓ}. Then

H(α_{1...ℓ}) ≥ (ℓ − 1) log p − log |G| + ∫ H(α_{1...k}|α_{1...k} mod G ∨ α_{k+1...∞}) dμ.

Proof. Let n = ⌈log |G|/ log p⌉. Applying Lemma 5.3 in each fiber we get

H(α_{1...n}) ≥ ∫ H(α_{1...n}|α_{k+1...∞}) dμ ≥ ∫ H(α_{1...k}|α_{1...k} mod G ∨ α_{k+1...∞}) dμ.

Since n ≥ ℓ, we also have

n log p − H(α_{1...n}) ≥ ℓ log p − H(α_{1...ℓ}).

Now combine the two inequalities. ■

Finally, we quote the following extension of the Borel-Cantelli Lemma (ex. 22.4 in Billingsley (1986)).

Lemma 6.4. Let Y_{1}, Y_{2}, … be a sequence of non-negative bounded independent random variables. Suppose that ∑ E Y_{i} = ∞. Then ∑ Y_{i} = ∞ almost-surely.

7. The Convolution Theorem

In this section we prove Theorem 1.1. Fix p, and consider the function

ψ(β) = H(1 − β, β ; p − 1, …, β ; p − 1).  (13)

Clearly ψ : [0, 1 − 1 ; p] → [0, log p] is increasing, onto and concave. A quick calculation shows that the inverse function ψ^{−1} satisfies

ψ^{−1}(h) ≥ C · h ; | log(h/ log p)|  (14)

for some constant C and for all h sufficiently small.

Given a probability distribution ν on {0, …, p − 1} define ∥ν∥_{∞} = max_{k=0,... ,p−1} ν(k). It can be easily verified that

1 − ∥ν∥_{∞} ≤ 1 ; p ∑_{x=0}^{p−1} ∑_{g=1}^{p−1} min{ν(x), ν(x + g mod p)}  (15)

and also

H(ν) ≤ ψ(1 − ∥ν∥_{∞}).  (16)

ENTROPY OF CONVOLUTIONS ON THE CIRCLE 19

Let μ denote an non-atomic measure on 𝕋, not necessarily invariant. For x ∈ 𝕋 denote by x = ∑ x_{i}p^{−i} its expansion in base p, and define

I_{k}(μ)(x) = − log μ(x_{1...k}|x_{k+1...∞}).

Then E I_{k}(μ) = E H_{μ}(x_{1...k}|x_{k+1...∞}). Similarly, given a subgroup G ⊂ ℤ_{p^{k}} =^{def} ℤ/p^{k}ℤ define

I_{G}(μ)(x) = − log μ(x_{1...k}|x_{1...k} mod G ∨ x_{k+1...∞}).

Then I_{k} = I_{G} for G = ℤ_{p^{k}}. We remark that

E I_{G}(μ) = − ∫ log ( dμ ; dδ_{G} ∗ μ) dμ,

where δ_{G} =^{def} ∑_{g∈G} δ_{g/p^{k}}.

Lemma 7.1. Let G ⊂ ℤ_{p^{k}}, and suppose that μ and ν are non-atomic measures on 𝕋. Then

E I_{k}(μ ∗ ν) − E I_{k}(μ) ≥ E I_{G}(μ ∗ ν) − E I_{G}(μ).

Proof. Rewrite the desired inequality as

E I_{k}(μ ∗ ν) − E I_{G}(μ ∗ ν) ≥ E I_{k}(μ) − E I_{G}(μ).  (17)

We have

E I_{k}(μ) − E I_{G}(μ) = E H_{μ}(x_{1...k}|x_{k+1...∞}) − E H_{μ}(x_{1...k}|x_{1...k} mod G ∨ x_{k+1...∞})
= E H_{μ}(x_{1...k} mod G|x_{k+1...∞}).

Applying the same consideration to μ ∗ ν, we see that (17) is equivalent to

E H_{μ∗ν}(x_{1...k} mod G|x_{k+1...∞}) ≥ E H_{μ}(x_{1...k} mod G|x_{k+1...∞}),

which follows from Proposition 6.1. ■

Lemma 7.2. Let {μ_{n}} be a sequence of probability measures on 𝕋, and form the product measure μ̃ = ∏ μ_{i}. Suppose that for some fixed number k,

∑_{i=1}^{∞} E ψ^{−1}(H_{μ_{i}}(x_{k}^{i}|t_{k+1...∞}^{i})) = ∞.  (18)

Then for μ̃-almost-every t ∈ 𝕋^{ℕ} there exists a group G_{k}(t) ⊂ ℤ_{p^{k}} such that

E I_{G_{k}(t)}(μ_{1} ∗ ⋯ ∗ μ_{n}) ⟶ E log |G_{k}(t)| .  (19)

Furthermore, the map t ↦ G_{k}(t) is measurable, and |G_{k}(t)| ≥ p_{∗}^{k} a.e., where p_{∗} is the smallest prime factor of p.

20 ELON LINDENSTRAUSS, DAVID MEIRI AND YUVAL PERES

Proof. We claim that

∑_{n=1}^{∞} ∑_{x_{k}=0}^{p−1} ∑_{g_{k}=1}^{p−1} min{μ_{n}(x_{k}|t_{k+1...∞}^{n}), μ_{n}(x_{k} + g_{k} mod p|t_{k+1...∞}^{n})} = ∞ μ̃-a.e.  (20)

Indeed, by Lemma 6.4, for every t in a set of full μ̃ measure, ∑_{i=1}^{∞} ψ^{−1}(H_{μ_{i}}(x_{k}^{i}|t_{k+1...∞}^{i})) = ∞. By (16), for all such t we have

∑_{n=1}^{∞} (1 − ∥D_{μ_{n}}(α_{k}^{n}|t_{k+1...∞}^{n})∥_{∞}) = ∞ .

Using (15), we conclude that a.e. t satisfies (20).

Define for t ∈ 𝕋^{ℕ} a group G_{k}(t) by

G_{k}(t) = ⟨g ∈ ℤ_{p^{k}} | ∑_{n=1}^{∞} ∑_{x=0}^{p^{k}−1} min{μ_{n}(x|t_{k+1...∞}^{n}), μ_{n}(x + g mod p^{k}|t_{k+1...∞}^{n})} = ∞⟩ .

To prove the lemma, take some t satisfying (20). We first show that |G_{k}(t)| ≥ p_{∗}^{k}. There exist distinct x_{k}, y_{k} ∈ {0, …, p − 1} such that

∑_{n=1}^{∞} μ_{n}(x_{k}|t_{k+1...∞}^{n}) = ∞,

and similarly for y_{k}. Since

μ_{n}(x_{k}|t_{k+1...∞}^{n}) = ∑_{{x=0,... ,p^{k}−1 \atop x≡x_{k} (mod p)}} μ_{n}(x|t_{k+1...∞}^{n}),

there exists x ∈ {0, …, p^{k} − 1} with x ≡ x_{k} (mod p) such that

∑_{n=1}^{∞} μ_{n}(x|t_{k+1...∞}^{n}) = ∞.

Similarly, there exists y ∈ {0, …, p^{k} − 1} with y ≡ y_{k} (mod p) and

∑_{n=1}^{∞} μ_{n}(y|t_{k+1...∞}^{n}) = ∞.

By definition, y − x ∈ G_{k}(t). But the least significant digit of y − x is y_{k} − x_{k} ≠ 0. By Lemma 5.4, |G_{k}(t)| ≥ p_{∗}^{k}.

It remains to prove (19). Clearly, I_{G_{k}(t)}(μ_{1} ∗ ⋯ ∗ μ_{n}) ≤ log |G_{k}(t)|. But

E I_{G_{k}(t)}(μ_{1} ∗ ⋯ ∗ μ_{n}) = E Hμ̃(θ_{1...k}^{n}|θ_{1...k}^{n} mod G_{k}(t) ∨ θ_{k+1...∞}^{n}) ≥ E Hμ̃(θ_{1...k}^{n}|θ_{1...k}^{n} mod G_{k}(t) ∨ t_{k+1...∞}^{1...n}) ⟶ E log |G_{k}(t)|,

ENTROPY OF CONVOLUTIONS ON THE CIRCLE 21

by an application of Lemma 5.2 for the random variables X_{i} ∼ D_{μ_{i}}(α_{1...k}^{i}|t_{k+1...∞}^{i}). This concludes the proof of (19). ■

Lemma 7.3. Under the assumptions of Lemma 7.2, define

h_{k} = sup_{n} 1 ; kE H_{μ_{1}∗···∗μ_{n}}(x_{1...k}|x_{k+1...∞}).  (21)

For any m, if 1 ; kE H_{μ_{1}∗···∗μ_{m}}(x_{1...k}|x_{k+1...∞}) > h_{k} − ε, then

H_{μ_{1}∗···∗μ_{m}}(t_{1...ℓ}) ≥ (ℓ − 1) log p − (k + 1)ε,  (22)

where ℓ = ℓ(k) = ⌊k log p_{∗} ; log p ⌋.

Proof. We have |G_{k}(t)| ≥ p_{∗}^{k} ≥ p^{ℓ} almost-everywhere. By Lemma 6.3,

H_{μ_{1}∗···∗μ_{m}}(t_{1...ℓ}) ≥ (ℓ − 1) log p − ∫ [ log |G_{k}| − I_{G_{k}}(μ_{1} ∗ ⋯ ∗ μ_{m})] dμ̃.  (23)

By Lemma 7.2, there exists some n > m such that E I_{G_{k}}(μ_{1} ∗ ⋯ ∗ μ_{n}) ≥ E log |G_{k}| − ε. Applying Lemma 7.1 we get

kε ≥ E I_{k}(μ_{1} ∗ ⋯ ∗ μ_{n}) − E I_{k}(μ_{1} ∗ ⋯ ∗ μ_{m})
≥ E I_{G_{k}}(μ_{1} ∗ ⋯ ∗ μ_{n}) − E I_{G_{k}}(μ_{1} ∗ ⋯ ∗ μ_{m})
≥ E log |G_{k}| − ε − E I_{G_{k}}(μ_{1} ∗ ⋯ ∗ μ_{m}).

Substituting this into (23) gives the desired result. ■

Proof of Theorem 1.1: By convexity of ψ^{−1} we have

∑_{n=1}^{∞} E ψ^{−1}(H_{μ_{n}}(t_{k}|t_{k+1...∞})) ≥ ∑_{n=1}^{∞} ψ^{−1}(E H_{μ_{n}}(t_{k}|t_{k+1...∞}))
= ∑_{n=1}^{∞} ψ^{−1}(h(μ_{n}, σ_{p})) = ∞,

applying (1) and (14). Hence the assumptions of Lemmas 7.2–7.3 hold.

By Proposition 6.2, h(μ_{1} ∗ ⋯ ∗ μ_{n}, σ_{p}) is monotone nondecreasing in n. Define

h =^{def} lim_{n→∞} h(μ_{1} ∗ ⋯ ∗ μ_{n}, σ_{p}) = sup_{n} h(μ_{1} ∗ ⋯ ∗ μ_{n}, σ_{p}).

We need to show that h = log p.

The h_{k} defined in (21) satisfy h_{k} = h for all k, by invariance of μ_{1} ∗ ⋯ ∗ μ_{n}. For arbitrary ε, let m be big enough so that h(μ_{1} ∗ ⋯ ∗ μ_{m}, σ_{p}) > h − ε. By Lemma 7.3, (22) holds for every k, with ℓ(k) = ⌊k log p_{∗} ; log p ⌋. Hence

h(μ_{1} ∗ ⋯ ∗ μ_{m}, σ_{p}) ≥ lim_{k→∞} (ℓ(k) − 1) log p − (k + 1)ε ; ℓ(k) = log p − ε log p ; log p_{∗} .

Letting ε ↓ 0 proves the theorem. ■

8. Joinings of Full Entropy

In this section we study basic properties of joinings of full entropy, and prove Theorem 1.8. Let α^{a...b} =^{def} α_{1...∞}^{a...b}, and denote by T^{i} =^{def} ⋀_{j=1}^{∞} α_{j...∞}^{i} the tail σ-algebra of π^{i}(𝕋^{ℕ}). We

denote by T the σ-algebra ⋁_{a=1}^{∞} (⋀_{j=1}^{∞} α_{j...∞}^{1...a}).

The simplest example of a joining of full entropy is a product measure μ̃ = ∏ μ_{i}. The following lemma shows that in the general case, a similar independence property holds.

Lemma 8.1. Let μ̃ be a joining of full entropy of {μ_{i}}_{i=1}^{∞}. Then the random variables {x^{i}} are conditionally independent given T .

Proof. For any k, n ≥ 1 we have

∫ Hμ̃(α_{1...k}^{1...n}|α_{k+1...∞}^{1...n}) dμ̃ ≤ ∫ ∑_{i=1}^{n} Hμ̃(α_{1...k}^{i}|α_{k+1...∞}^{1...n}) dμ̃  (24)
≤ ∫ ∑_{i=1}^{n} H_{μ_{i}}(α_{1...k}^{i}|α_{k+1...∞}^{i}) dμ_{i} .  (25)

Since h(π^{1...n}(μ̃), σ_{p} × ⋯ × σ_{p}) = ∑_{i=1}^{n} h(μ_{i}, σ_{p}), both inequalities must in fact be equalities. Equality in (24) implies that the random variables {x_{1...k}^{i}}_{i=1}^{n} are independent given α_{k+1...∞}^{1...n}. A reverse martingale argument shows that in fact {x_{1...k}^{i}}_{i=1}^{n} are independent given ⋀_{j=1}^{∞} α_{j...∞}^{1...n}. By a standard martingale argument, {x_{1...k}^{i}}_{i=1}^{n} are independent given T = ⋁_{a=1}^{∞} (⋀_{j=1}^{∞} α_{j...∞}^{1...a}). Since this is true for any k, n ≥ 1, the assertion follows. ■

We obtain the following corollary:

Lemma 8.2. Let μ̃ denote a joining of full entropy of {μ_{i}}_{i=1}^{∞}, and denote by L = ⋀_{a=1}^{∞} α_{1...∞}^{a...∞} the tail σ-algebra of the stochastic process {x^{i}}. Then L ⊂ T . (“The bottom tail is contained in the right tail”.)

Proof. Let A be some L-measurable set. Denote by τ the factor map corresponding to T . By Lemma 8.1, given τ(x) the random variables {x^{i}}_{i=1}^{∞} are independent. By Kolmogorov’s 0-1 Law, μ̃(A|T ) is either 0 or 1. ■

We cite the following technical Lemma:

Lemma 8.3. Let (X, T, D, ν) denote a measure preserving system, and suppose that β and γ are two finite partitions of X. Denote by T_{γ} the tail σ-algebra corresponding to γ and ν.

Then for all k ≥ 1,

D(β_{1...k}|β_{k+1...∞} ∨ T_{γ}) = D(β_{1...k}|β_{k+1...∞}) ν-a.e.

The same applies if instead of T_{γ} one takes a limit of an increasing sequence of tails of finite partitions.

Proof. See Rudolph (1990), Corollary 5.28 p. 99, or Parry (1981), Lemma 7 p. 65. ■

We also need the following monotonicity property of conditional entropy, which follows from Jensen’s inequality.

Lemma 8.4. Let α, β, β′, γ denote partitions in a measure preserving system (X, T, D, ν), and suppose that γ ≤ β ≤ β′. Then

E (H_{ν}(α|β) | γ)(x) ≥ E (H_{ν}(α|β′) | γ)(x) ν-a.e.

The same applies if β and γ are limits of increasing sequences of partitions.

Proposition 8.5. Let μ̃ be a joining of full entropy, k ∈ ℕ, G is a subgroup of ℤ/p^{k}ℤ. Then for a.e. x,

E (Hμ̃(θ_{1...k}^{n} mod G|θ_{k+1...∞}^{n}) | T )(x)

is monotone nondecreasing in n.

Proof. By Lemma 8.3, we have μ̃-a.e.

E (Hμ̃(θ_{1...k}^{n} mod G|θ_{k+1...∞}^{n}) | T )(x) = E (Hμ̃(θ_{1...k}^{n} mod G|θ_{k+1...∞}^{n} ∨ T ) | T )(x).

Now apply 6.2 in each fiber. ■ We leave the proof of the following estimate to the reader.

Lemma 8.6. Let X be a random variable such that 0 ≤ X ≤ M and E X ≥ η. Then

ℙ(X > η ; 2) ≥ η ; 2M .

Corollary 8.7. If X is as in Lemma 8.6, g a monotone nondecreasing function, then

E (g(X)) ≥ ηg(η/2) ; 2M

The last lemma we need is the following variant of Shannon’s theorem. Denote by (μ|F) the measure μ conditioned on F, i.e., (μ|F)(A) = μ(A ∩ F)/μ(F)

24 ELON LINDENSTRAUSS, DAVID MEIRI AND YUVAL PERES

Lemma 8.8. Let β be a finite partition in an ergodic measure preserving system (X, μ, T), and denote β_{1...k} = β ∨ … ∨ T^{−(k−1)}β. Suppose that for some sequence of subsets {F_{k}} and a constant γ > 0, for every k large enough μ(F_{k}) ≥ γ. Then

h_{μ}(β, T) ≥ lim sup_{k→∞} 1 ; kH_{μ|F_{k}}(β_{1...k}).

Proof. Let ε > 0, and denote by N the number of atoms in β. By Shannon’s theorem, for k large enough it is possible to cover a subset of X of μ-measure 1 − εγ by at most exp(k(h_{μ}(β, T) + ε)) atoms of β_{1...k}. In particular, the μ|F_{k}-measure of the union of these atoms is at least 1 − ε. Hence by a standard property of entropy (see Rudolph (1990), cor. 5.17)

1 ; kH_{μ|F_{k}}(β_{1...k}) ≤ 1 ; k · (H(ε, 1 − ε) + k(h_{μ}(β, T) + ε) + εk log N).

Letting k → ∞ and ε → 0 proves the lemma. ■

Proof of Theorem 1.8: By Lemma 2.1, the ergodic components of μ̃ are also joinings of full entropy of {μ_{i}}. Since by Rokhlin’s theorem the entropy of a measure is the average of the entropies of its ergodic components, it is enough to consider the case where μ̃ is ergodic.

By Proposition 8.5, h(Θ^{n}μ̃, σ_{p}) is monotone nondecreasing in n. Define

h =^{def} lim_{n→∞} h(Θ^{n}μ̃, σ_{p}) = sup_{n} h(Θ^{n}μ̃, σ_{p}).

We need to show that h = log p.

Define conditional measures μ̄_{i} ∼ Dμ̃(α_{1...∞}^{i}|T ). The sequence {μ̄_{i}} is a random sequence of measures, depending on a choice of fiber (a point in T ). By Lemma 8.1, {μ̄_{i}} are independent. We claim that the assumptions of Lemmas 7.2–7.3 hold for {μ̄_{i}} with positive probability. To see this, consider the random variables

Z_{i} = E (ψ^{−1}(H_{μ_{i}}(α_{k}^{i}|t_{k+1...∞}^{i})) | T )
W_{i} = E (H_{μ_{i}}(α_{k}^{i}|t_{k+1...∞}^{i}) | T ) .

To prove that (18) holds with positive probability, we need to show that ℙ(∑ Z_{i} = ∞) > 0. Let η =^{def} inf_{i} h(μ_{i}, σ_{p}) > 0. By Corollary 8.7

Z_{i} ≥ W_{i}ψ^{−1}(W_{i}/2) ; 2 log p  (26)

Since E (W_{i}) = h(μ_{i}, σ_{p}) ≥ η, by Lemma 8.6 and (26),

ℙ(Z_{i} > ηψ^{−1}(η/4) ; 4 log p) > η^{∗} =^{def} η ; 2 log p.

ENTROPY OF CONVOLUTIONS ON THE CIRCLE 25

Hence ℙ(∑ Z_{i} = ∞) ≥ ℙ(Z_{i} > ηψ^{−1}(η/4) ; 4 log p i.o.) ≥ η^{∗} > 0.

Fix ε ∈ (0, η^{∗}), and choose m with h − h(Θ^{m}μ̃, σ_{p}) ≤ ε^{2}. For any k, define

Υ_{k}^{(n)}(t) = 1 ; kE (Hμ̃(θ_{1...k}^{n}|θ_{k+1...∞}^{n}) | T )(t),
Υ_{k}(t) = sup_{n} Υ_{k}^{(n)}(t).

By Proposition 8.5, Υ_{k}^{(n)}(t) is almost-surely monotonically increasing in n. Thus

0 ≤ E (Υ_{k} − Υ_{k}^{(m)}) = h − h(Θ^{m}μ̃, σ_{p}) ≤ ε^{2},

hence by Markov’s inequality

μ̃[Υ_{k} − Υ_{k}^{(m)} ≥ ε] ≤ ε^{2} ; ε = ε.

Define F_{k} = {∑ Z_{i} = ∞} \ {Υ_{k} − Υ_{k}^{(m)} ≥ ε}. The event {∑ Z_{i} = ∞} is T -measurable by Lemma 8.2, hence F_{k} is T -measurable as well. Clearly μ̃(F_{k}) ≥ η^{∗} −ε. Applying Lemma 7.3, we have (denoting ℓ = ℓ(k) = ⌊k log p_{∗} ; log p ⌋)

∀t ∈ F_{k}, Hμ̃(θ_{1...ℓ}^{m}|T )(t) ≥ (ℓ − 1) log p − (k + 1)ε.

Thus by Lemma 8.4

H_{μ̃|F_{k}}(θ_{1...ℓ}^{m}) = E (Hμ̃(θ_{1...ℓ}^{m}|{F_{k}, F_{k}^{c}}) | F_{k}) ≥ (ℓ − 1) log p − (k + 1)ε.

Dividing by ℓ and applying Lemma 8.8 we get

h(Θ^{m}μ̃, σ_{p}) ≥ log p − log p ; log p_{∗} ε.

Letting ε ↓ 0 proves the theorem. ■

9. Dimension of Sum Sets

For any measure μ, let

dim μ =^{def} inf{dim_{H} S | S is a Borel set with μ(S) = 1}.  (27)

Define the lower dimension of μ by

dim μ =^{def} inf{dim_{H} S | S is a Borel set with μ(S) > 0}.  (28)

To compute dimension of measures we use the following lemma from Billingsley (1965).

Billingsley’s Lemma. Let μ be a positive finite measure on 𝕋. Assume K ⊂ 𝕋 is a Borel set satisfying μ(K) > 0 and

K ⊂ {x ∈ 𝕋 : lim inf_{ε↓0} log μ[B_{ε}(x)] ; log ε ≤ γ}.

Then dim_{H} K ≤ γ. If the lim inf is γ a.e., then dim_{H} K = γ.

Here B_{ε}(x) can be the interval of length ε centered at x, or the mesh interval with edge ε containing x, etc.

In most of this section we restrict attention to p-invariant measures on 𝕋, for some fixed integer p > 1. In this case, by the Shannon-McMillan-Breiman (SMB) Theorem, it follows that if μ is ergodic then dim μ = h(μ, σ_{p})/ log p. If μ is not ergodic, denote by μ = ∫ μ_{θ} dθ its ergodic decomposition, and then

dim μ = ess-sup_{θ} dim μ_{θ}.  (29)

This (known) fact is proved in Meiri and Peres (1996) in a more general context. We wish to derive the equivalent statement for lower dimension.

Theorem 9.1. Let μ be a p-invariant measure on 𝕋, and denote its ergodic decomposition by μ = ∫ μ_{θ} dθ. Then dim μ = ess-inf_{θ} dim μ_{θ}.

Proof. Denote γ =^{def} ess-inf dim μ_{θ}. By the above remarks, γ = ess-inf h(μ_{θ}, σ_{p})/ log p. Let ψ(x) denote the SMB function of μ, i.e., ψ(x) =^{def} lim 1 ; nI_{α_{0}^{n−1}}(x) for the partition α = {[ j ; p, j+1 ; p]}_{j=0}^{p−1} (see Meiri and Peres (1996) for more details). The function ψ is constant on fibers, and the SMB theorem for non-ergodic transformations implies that for almost every θ we have ψ(x) = h(μ_{θ}, σ_{p}) μ_{θ}-a.e. (cf. Parry 1981; p. 39). Fix some ε > 0, and let

B = {x : ψ(x) ; log p < γ + ε} .

From the definition of γ we have μ(B) > 0, hence dim μ ≤ dim_{H} B. From Billingsley’s Lemma and the SMB Theorem we know that dim_{H} B ≤ γ + ε. Since ε was arbitrary, we conclude that dim μ ≤ γ. The other direction is proved similarly: if dim μ < γ, then there exists a Borel set B and some ε > 0 such that μ(B) > 0 and dim_{H} B < γ − ε. Applying once again Billingsley’s Lemma and the SMB Theorem we get ψ(x)/ log p ≤ γ − ε for x ∈ B, contradicting the definition of γ. ■

In particular, if μ is p-invariant and ergodic, we conclude that

dim μ = dim μ = h(μ, σ_{p}) ; log p.  (30)

Lemma 9.2. Any two measures μ and ν on 𝕋 satisfy dim(μ ∗ ν) ≥ dim μ.

ENTROPY OF CONVOLUTIONS ON THE CIRCLE 27

Proof. Suppose that B is a Borel set with dim_{H} B < dim μ. We need to prove that (μ ∗ ν)(B) = 0. For any t ∈ 𝕋 we have dim_{H}(B − t) = dim_{H} B < dim μ, so μ(B − t) = 0. Hence (μ ∗ ν)(B) = ∫ μ(B − t) dν(t) = 0. ■

Corollary 9.3. Let μ and ν be p-invariant measures on 𝕋, with μ ergodic. Let μ∗ν = ∫ φ_{θ}dθ be the the ergodic decomposition of μ ∗ ν. Then h(φ_{θ}, σ_{p}) ≥ h(μ, σ_{p}) for almost-every θ.

Proof. Write

ess-inf h(φ_{θ}, σ_{p}) ; log p = dim(μ ∗ ν)  by Theorem 9.1
≥ dim μ  by Lemma 9.2
= h(μ, σ_{p}) ; log p  by (30).

This proves the assertion. ■

The point in the last corollary is that μ ∗ ν need not, in general, be ergodic, even if μ and ν are ergodic. Furthermore, the entropy of its ergodic components need not be equal, as seen in the following example:

Example 9.4. A non-ergodic convolution.

Take p = 2 and let X = ∑_{i=1}^{∞} x_{i}p^{−i} denote the random variable on 𝕋 for which x_{i} = 0 if i ≢ 0 (mod 5), and otherwise x_{i} is 0 or 1 with probability 1 2. Denote by μ the distribution of X + pX + ⋯ + p^{4}X (mod 1). Then (𝕋, μ, σ_{p}) is ergodic but not weakly-mixing (since σ_{p}^{5} is not ergodic). Also, μ^{∗5} is not ergodic, and decomposes to (finitely many) components with different entropies (one of them is Lebesgue). It is also possible to construct an example with a continuum of components.

We turn now to topological corollaries of Theorems 1.1 and 1.8.

Proof of Corollary 1.2: By the variational principle for expansive maps (see Walters 1982), for every i there exists a p-invariant and ergodic measure μ_{i} supported on S_{i} with h(μ_{i}, σ_{p}) = h_{top}(S_{i}, σ_{p}). Recall that h_{top}(S_{i}, σ_{p})/ log p = dim_{H} S_{i}, hence dim μ_{i} = h(μ_{i}, σ_{p})/ log p = dim_{H} S_{i}, by (30). By our assumptions, h_{i} =^{def} h(μ_{i}, σ_{p})/ log p satisfy (1).

Denote ν^{(n)} = μ_{1} ∗ ⋯ ∗ μ_{n}. Since ν^{(n)}(S_{1} + ⋯ + S_{n}) = 1, we have

dim ν^{(n)} ≤ dim_{H}(S_{1} + ⋯ + S_{n}),

so it is enough to show that dim ν^{(n)} ⟶ 1. Denote by ν^{(n)} = ∫ ν_{θ}^{(n)} dθ the ergodic decomposition of ν^{(n)}. Then

dim ν^{(n)} = ess-sup{dim ν_{θ}^{(n)}}  by (29)
= 1 ; log p ess-sup h(ν_{θ}^{(n)}, σ_{p})  by (30)

≥ 1 ; log p ∫ h(ν_{θ}^{(n)}, σ_{p}) dθ

= 1 ; log ph(ν^{(n)}, σ_{p})  by Rokhlin’s Theorem
⟶ 1.  by Theorem 1.1
■

Proof of Theorem 1.3: We define inductively a joining of full entropy μ̃. Let ν^{(1)} = μ_{1}. Consider the ergodic decomposition of μ_{1} × μ_{2}. Since μ_{1} × μ_{2}(S_{1} × S_{2}) > 0, by Lemma 2.1 we can find an ergodic component ν^{(2)} such that

(i) h(ν^{(2)}, σ_{p} × σ_{p}) = h(μ_{1}, σ_{p}) + h(μ_{2}, σ_{p}), (ii) ν^{(2)} projects to μ_{1} and μ_{2}, and (iii) ν^{(2)}(S_{1} × S_{2}) > 0.

Consider next the ergodic decomposition of ν^{(2)} × μ_{3}, and find an ergodic component ν^{(3)} with similar properties. Continue in this manner to define a sequence of measures ν^{(n)} such that ν^{(n)} is an ergodic joining of full entropy of μ_{1}, …, μ_{n}, and ν^{(n)}(S_{1} × ⋯ × S_{n}) > 0. Let μ̃ be the inverse limit of this system. Then, by Theorem 1.8, h(Θ^{n}ν^{(n)}, σ_{p}) ⟶ log p. As ν^{(n)} is ergodic, Θ^{n}ν^{(n)} is ergodic as well. Since (Θ^{n}ν^{(n)})(S_{1} + ⋯ + S_{n}) > 0, by (27) and (30) we conclude that

dim_{H}(S_{1} + ⋯ + S_{n}) ≥ dim Θ^{n}ν^{(n)} = h(Θ^{n}ν^{(n)}, σ_{p}) ; log p ⟶ 1,

as stated. ■

10. Examples and questions

1. Recall that a measure μ on 𝕋 is {c_{n}}-normal a.e. if {c_{n}x (mod 1)} is uniformly-distributed for μ-almost every x ∈ 𝕋. Suppose that μ is a p-invariant ergodic measure, such that μ ∗ μ is {q^{n}}-normal. Does it follow that μ is {q^{n}}-normal as well? For non-invariant measures, the assertion is false:

Example 10.1. μ ∗ μ normal does not imply that μ is normal.

ENTROPY OF CONVOLUTIONS ON THE CIRCLE 29

Let {X_{i}} and {Y_{i}} be independent sequences of random bits with ℙ(X_{i} = 0) = 1 2 and ℙ(Y_{i} = 0) = 1/i for all i ≥ 1. For 2^{k} ≤ i < 2^{k+1} define Z_{i} = X_{i}Y_{k}. Let μ be the distribution of ∑ 2^{−i}Z_{i}. Then μ is {2^{n}}-normal in probability, but not {2^{n}}-normal a.e. Also, μ ∗ μ is {2^{n}}-normal a.e.

2. Suppose that μ is a p-invariant and ergodic measure on 𝕋 with positive entropy. Does it follow that dim(μ^{∗n}) → 1 as n → ∞? This would mean that the convergence h(μ^{∗n}, σ_{p}) → log p is uniform on all ergodic components of μ^{∗n}.

3. As we remarked in the introduction, the entropy condition in Theorem 1.1 is sharp.

Example 10.2. Given numbers 0 < h_{i} < 1 with ∑ h_{i} ; | log h_{i}| < ∞, we construct a sequence of p-invariant ergodic measures {μ_{i}} such that h(μ_{i}, σ_{p})/ log p = h_{i}, yet μ_{1} ∗ ⋯ ∗ μ_{n} −̸→ λ weak^{∗}.

For a sequence {β_{i}}, let X_{j}^{(i)} be independent random variables on {0, …, p − 1} with ℙ(X_{j}^{(i)} = 0) = 1 − β_{i}, and ℙ(X_{j}^{(i)} = k) = β_{i}/(p − 1) for k = 1, …, p − 1. Define μ_{i} to be the distribution of ∑_{j=1}^{∞} X_{j}^{(i)}p^{−j}. Then {μ_{i}} are Bernoulli measures, and

h(μ_{i}, σ_{p}) = H(1 − β_{i}, β_{i} ; p − 1, …, β_{i} ; p − 1) ∼ β_{i} log 1 ; β_{i} .

Define β_{i} by requiring that h(μ_{i}, σ_{p}) = h_{i} log p. Then from the condition on {h_{i}} we get ∑ β_{i} < ∞ (see §6). It is not hard to see that |μ̂_{i}(1) − 1| ≤ 4πβ_{i}. Thus ∑ |μ̂_{i}(1) − 1| < ∞, hence ∑ |μ̂_{i}(1)| = ∞. But then

|(μ_{1} ∗ ⋯ ∗ μ_{n})^{∧}(1)| = | ∏_{i=1}^{n} μ̂_{i}(1)| ≥ ∏_{i=1}^{∞} |μ̂_{i}(1)| > 0,

whence (μ_{1} ∗ ⋯ ∗ μ_{n})^{∧}(1) −̸→ 0.

4. Is the dimension condition of Corollary 1.2 sharp as well? Specifically, given a sequence of numbers 0 < d_{i} < 1 such that ∑ d_{i}/| log d_{i}| < ∞, can one always find p-invariant closed subsets S_{i} ⊂ 𝕋 with dim_{H} S_{i} = d_{i} and lim dim_{H}(S_{1} + ⋯ + S_{n}) < 1? Currently we can construct sets satisfying the desired conclusion, but only when ∑ d_{i}/| log d_{i}| is small enough.

Example 10.3. Given numbers 0 < d_{i} < 1 with ∑ d_{i} ; | log d_{i}| < c(p) (for some c(p) that can be made explicit) there is a sequence of p-invariant closed sets S_{i} such that dim_{H} S_{i} = d_{i}, yet lim dim_{H}(S_{1} + ⋯ + S_{n}) < 1.

Indeed, consider the set

S(N, β) = {x ∈ 𝕋 : ∀n ∈ ℕ, (# non-0 digits in x_{n...n+N−1}) ≤ βN}.

If μ(β) is constructed in the same way the measures μ_{i} were defined in the previous subsection, then clearly

dim_{H} S(N, β) = h_{top}S(N, β) ; log p ⟶ h(μ(β)) ; log p as N ⟶ ∞.

Thus we can chose N_{i} and β_{i} so that if S_{i} = S(N_{i}, β_{i}), then

d_{i} < dim_{H} S_{i} < (1 + ε)d_{i}, and
(1 − ε)d_{i} < h(μ(β_{i})) ; log p < (1 + ε)d_{i}.  (31)

We also assume N_{i}|N_{i+1} and N_{i} ≥ 2^{i}/ε for all i. The exact condition we need is that ∑_{i=0}^{∞} β_{i} < 1 − ε, which can be translated to a condition on ∑_{i=0}^{∞} d_{i}/| log d_{i}| via (31).

We shall presently show that lim dim_{H}(S_{1} +⋯+S_{n}) < 1. It is possible to replace the sets S_{i} by S′_{i} ⊂ S_{i} such that dim_{H} S′_{i} = d_{i}, using the fact that the S_{i}’s we defined above are shifts of finite type. Shifts of finite type have many closed p-invariant subsets, and in particular have a closed p-invariant subset with any Hausdorff dimension between 0 and the dimension of the full set. Thus there is a closed p-invariant subset S′_{i} ⊂ S_{i} with the required Hausdorff dimension (properties of shifts of finite type are discussed in Denker et. al. (1976); the above result is a consequence of the Jewett-Krieger theorem, chapter 29 in that reference). Clearly lim dim_{H}(S′_{1}+⋯+S′_{n}) ≤ lim dim_{H}(S_{1}+⋯+S_{n}). The proof that lim dim_{H}(S_{1}+⋯+S_{n}) < 1 follows from the following proposition:

Proposition 10.4. If N|M,

S(N, β) + S(M, β′) ⊂ S(M, β + β′ + 1 ; M)

Proof. Consider the M-block z_{n...n+M−1} for any z ∈ S(N, β) + S(M, β′) as an element of ℤ/p^{M}ℤ. Then there are x ∈ S(N, β) and x′ ∈ S(M, β′) such that

x_{n...n+M−1} + x′_{n...n+M−1} mod p^{M} ≤ z_{n...n+M−1} ≤ (x_{n...n+M−1} + x′_{n...n+M−1} mod p^{M}) + p − 1.

Note that for any a, b ∈ ℕ, their base-p expansions satisfy

(# non-0 digits in a) + (# non-0 digits in b) ≥ (# non-0 digits in a + b).  (32)

This can be shown e.g. by induction.

Now in x_{n...n+M−1} there are at most βM non-0 digits, and in x′_{n...n+M−1} at most β′M non-0 digits. Thus using (32), z_{n...n+M−1} can have at most (β + β′)M + 1 non-0 digits, and the Proposition follows. ■

Using the above Proposition, we see that for any n,

S_{1} + ⋯ + S_{n} ⊂ S(N_{n}, ϵ + ∑_{i=1}^{∞} β_{i}).

As ϵ + ∑_{i=1}^{∞} β_{i} < 1, we see that

lim_{n→∞} dim_{H}(S_{1} + ⋯ + S_{n}) ≤ h(μ(ϵ + ∑_{i=1}^{∞} β_{i})) ; log p < 1

5. Does Theorem A of §1.1 hold under the weaker assumption that the collision exponent is smaller than two? By the Bootstrap Lemma, a positive answer to the first question in this section would give a positive answer to this question. In particular, this would imply that every p-invariant measure of positive entropy is {q^{n}}-normal, for any p, q such that some prime factor of p does not divide q. The case where μ is a Bernoulli measure is covered by Feldman and Smorodinsky (1992), for any multiplicatively-independent p, q.

The following example shows that Theorem 1.8 is not valid under the weaker assumptions of Theorem 1.1. In fact, even weak convergence is not guaranteed:

Example 10.5. A joining of full entropy μ̃ with ∑ h_{n} ; | log h_{n}| = ∞, yet Θ^{n}μ̃ −̸→ λ weak^{∗}.

Take p = 2, and fix some irrational α. Let t_{0} be a uniform random variable on the unit interval, and define t_{n} = t_{0} +nα (mod 1). Let {Y_{i}^{j}}_{i,j=1}^{∞} be a sequence of i.i.d. variables with ℙ(Y_{i}^{j} = 0) = ℙ(Y_{i}^{j} = 1) = 1 2. Given a non-negative sequence {h_{j}}, define

X_{i}^{j} = \begin{cases}0 & if t_{i} ≥ h_{j}, \\ Y_{i}^{j} & if t_{i} < h_{j} \end{cases}

and let X^{j} = ∑_{i=1}^{∞} X_{i}^{j}2^{−i}. Denote by μ_{j} the distribution of X^{j}, and by μ̃ the distribution of {X^{j}}_{j=1}^{∞} on 𝕋^{ℕ}. Then μ_{j} is a σ_{2}-invariant and ergodic measure with entropy h_{j} (in base 2), and μ̃ is a joining of full entropy. Take h_{j} = 1 ; j+1. We claim that for small enough α we have Θ^{k}μ̃ −̸→ λ weak^{∗}. To see that, define the following events:

A_{N} = {∀j ∈ ℕ ∀i = 1, …, N X_{i}^{j} = 0},
B_{N} = {∀i > N ∀j > 2^{i/2} X_{i}^{j} = 0}.

If t_{i} ≥ h_{1} then X_{i}^{j} = 0 for all j. Take N such that ∑_{i=N+1}^{∞} 2^{−i/2} ≤ 1 8, and fix α ∈ (0, 1 ; 4N). Clearly ℙ(A_{N}) ≥ ℙ(t_{i} ≥ h_{i} ∀i = 1, …, N) ≥ ℙ(t_{1} ∈ ( 1 2, 3 4)) = 1 4.

Also, ℙ(B_{N}^{c}) ≤ ℙ(∃i > N, t_{i} < 2^{−i/2}), since if t_{i} ≥ 2^{−i/2} for all i > N, then for all j > 2^{i/2} we have t_{i} > 1 ; j > h_{j}, hence X_{i}^{j} = 0. By our choice of N,

ℙ(B_{N}^{c}) ≤ ∑_{i=N+1}^{∞} ℙ(t_{i} < 2^{−i/2}) = ∑_{i=N+1}^{∞} 2^{−i/2} ≤ 1 8,

and we conclude that ℙ(A_{N} ∩ B_{N}) ≥ ℙ(A_{N}) − ℙ(B_{N}^{c}) ≥ 1 8. For (X_{i}^{j}) ∈ A_{N} ∩ B_{N}, for any k the first N/4 digits of the sum X^{1} + ⋯ + X^{k} (mod 1) are zero, and so Θ^{k}μ̃ −̸→ λ weak^{∗}. Acknowledgments. Parts of this work are contained in the Ph.D. theses of the first two authors. We are grateful to Hillel Furstenberg, Dan Rudolph and Benjamin Weiss for helpful discussions. We also thank Bryna Kra, Russell Lyons and Wilhelm Schlag for useful comments on the presentation.

References

[1] P. Billingsley (1965), Ergodic Theory and Information, Wiley, New York.

[2] P. Billingsley (1986), Probability and Measure, Wiley, New York.

[3] G. Brown, M. S. Keane, W. Moran and C. Pearce (1988), An inequality, with applications to Cantor measures and normal numbers, Mathematika 35, 87–94.

[4] G. Brown and J. H. Williamson (1987), Coin tossing and sum sets, J. Austral. Math. Soc. (Series A) 43, 211–219.

[5] M. Denker, C. Grillenberger and K. Sigmund (1976), Ergodic Theory on Compact Spaces, Springer-Verlag, Berlin.

[6] J. Feldman (1993), A generalization of a result of Lyons about measures in [0, 1], Israel Journal of Mathematics 81, 281–287.

[7] J. Feldman and M. Smorodinsky (1992), Normal numbers from independent processes, Ergodic Theory and Dynamical Systems 12, 707–712.

[8] H. Furstenberg (1967), Disjointness in ergodic theory, minimal sets, and a problem in Diophantine approximation, Math. Systems Theory 1, 1–49.

[9] B. Host (1995), Nombres normaux, entropie, translations, Israel Journal of Mathematics 91, 419–428.

[10] A. Johnson (1992), Measures on the circle invariant under multiplication by a nonlacunary subgroup of the integers, Israel Journal of Mathematics 77, 211–240.

[11] A. Johnson and D. Rudolph (1995), Convergence under ×_{p} of ×_{q} invariant measures on the Circle, Advances in Mathematics 115, 117–140.

[12] R. Lyons (1988), On measures simultaneously 2- and 3-invariant, Israel Journal of Mathematics 61, 219–224.

ENTROPY OF CONVOLUTIONS ON THE CIRCLE 33

[13] D. Meiri (1996), Entropy and uniform distribution of orbits in 𝕋^{d}, Israel Journal of Mathematics, to appear^{†}.

[14] D. Meiri (1997), Entropy, dimension and distribution of orbits in 𝕋^{d}, Ph.D. thesis, Hebrew University, Jerusalem^{†}.

[15] D. Meiri and Y. Peres (1996), Bi-invariant sets and measures have integer Hausdorff dimension, Ergodic Theory and Dynamical Systems, to appear^{†}.

[16] W. Parry (1981), Topics in Ergodic Theory, Cambridge University Press.

[17] D. Rudolph (1990), Fundamentals of Measurable Dynamics, Oxford University Press, New York.

[18] D. Rudolph (1990a), ×2 and ×3 invariant measures and entropy, Ergodic Theory and Dynamical systems 10, 395–406.

[19] P. Walters (1982), An introduction to Ergodic Theory, Springer-Verlag, Berlin.

Institute of Mathematics, The Hebrew University, Jerusalem 91904, Israel

   E-mail address: elon@math.huji.ac.il, dafid@math.huji.ac.il, peres@math.huji.ac.il

†can be obtained at http://www.ma.huji.ac.il/∼dafid.