An IDEAL Group, CLC, Project

]> An IDEAL Group, CLC, Project

SOME RESULTS ON RECURRENCE AND ENTROPY

DISSERTATIO $N$

Presented in Partial Fulfillment of the Requirements for

the Degree Doctor of Philosophy in the Graduate

School of the Ohio State University

Ronald Lee Pavlov Jr., B.S., $M . S$ .

$* * * *$ $*$

The Ohio State University

2007

Dissertation Committee:

$\mapsto 133 C 1 b C l b l \cup 11 \cup \cup 111111 l b b C C$ . Approved by

Professor Vitaly Bergelson, Advisor

Professor Alexander Leibman

Advisor

Professor Manfred Einsiedler Graduate Program in $M ξ$

Graduate Program in Mathematics

ABSTRACT

This thesis is comprised primarily of two separate portions. In the first portion, we

exhibit, for any sparse enough increasing sequence ${p_{n}}$ of integers, a totally minimal,

totally uniquely ergodic, and topologically mixing system $(X, T)$ and $f \in C (X)$ for

which the averages $\frac{1}{N} \sum_{n = 0}^{N - 1} f (T^{p_{n}} x)$ fail to converge on a residual set in $X$ , answering

negatively an open question of Bergelson. We also construct here a totally minimal,

totally uniquely ergodic, and topologically mixing system $(X^{'}, T^{'})$ and $x^{'} \in X^{'}$ for

which $x^{'} \notin {T^{p_{n}} x^{'}}$ .

In the second portion, we study perturbations of multidimensional shifts of finite

type. Given any $Z^{d}$ shift of finite type $X$ for $d > 1$ and any word $w$ in the language of

$X$ , denote by $X_{w}$ the set of elements of $X$ in which $w$ does not appear. If $X$ satisfies

a uniform mixing condition called strong irreducibility, we obtain exponential upper

and lower bounds on $h^{t o p} (X) - h^{t o p} (X_{w})$ dependent only on the size of $w$ . This result

generalizes a result of Lind about $Z$ shifts of finite type.

To Dilip

ill

ACKNOWLEDGMENTS

First and foremost, I would like to thank my advisor Vitaly Bergelson. This the-

sis could never have been completed without his help. His infectious enthusiasm

for mathematics, along with a willingness to share his knowledge, were a constant

inspiration.

I would also like to thank my other committee members, Professors Alexander Leib-

man and Manfred Einsiedler, for agreeing to serve on my committee and for many

fruitful mathematical discussions.

Finally, I thank my friends and loved ones, without whom I would never have been

able to get as far as I have. In no particular order:

Thank you to Mom and Dad, who have always been willing to do anything to

support me and have always believed in me.

Thank you to Greg, without whose friendship and sense of humor graduate school

would have been much less bearable.

Thank you to Jasmine, who was always there for me. I can never thank you

enough for your constant love and support.

VITA

2000-Present . . . . . . . . . . . . . . . . . . . . . . . . . . Graduate Teaching Associate,

The Ohio State University

1998-1999 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Student Instructional Associate,

The Ohio State University

2003 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . $M . S$ . in Mathematics,

The Ohio State University

2000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . $B . S$ . in Mathematics,

The Ohio State University

$v$

PUBLICATIONS

Research Papers

$•$ Some Counterexamples In Topological Dynamics (Ergodic Theory and Dynam-

ical Systems, to appear)

$•$ Perturbations of Multidimensional Shifts of Finite Type (submitted)

FIELDS OF STUDY

Major Field: Mathematics

Specialization: Ergodic Theory and Dynamical Systems

TABLE OF CONTENTS

Abstract ii

Dedication . $i i i$

Acknowledgments . 1V

Vita $v$

List of Figures ix

CHAPTER PAGE

1Introduction 1

2Recurrence and convergence of ergodic averages along sparse sequences 8

2.1 Introduction 8

2.2 Some general symbolic constructions 16

2.3 Some symbolic counterexamples 31

2.4 Some general constructions on connected manifolds . 42

2.5 Some counterexamples on connected manifolds 55

2.6 A counterexample about simultaneous recurrence 61

2.7 Questions 65

3Perturbations of multidimensional shifts of finite type 67

3.1 Introduction 67

3.2 Some measure-theoretic preliminaries 84

3.3 A replacement theorem 93

3.4 The proof of the main result 114

3.5 A closer look at the main result 146

3.6 An application to an undecidability question 155

3.7 Questions 159

Vll

Bibliography

161

Vlll

LIST OF FIGURES

FIGURE PAGE

3.1 $f_{2}$ 's action on a sample element of $Y$ 73

3.2 A portion of a sample element of $Z$ 76

3.3 $a_{4}$ 77

3.4 $b_{4}$ 77

3.5 $R_{k (j_{1} + R), k (j_{2} + R), ..., k (j_{d} + R)}$ 85

3.6 A standard replacement of $u$ . 95

3.7 A sample element $S$ of $R_{j}$ 97

3.8 An element $S$ of $R_{j}$ associated to two standard replacements 98

3.9 The suboctants of $B_{j}$ 99

3.10 Elements $S$ , $S^{'}$ of $R_{j}$ whose difference is a multiple of $e_{i}$ tOO

3.11 An element $S$ of $R_{j}$ which contains $O$ 106

3.12 107

3.13 $B_{j}^{'}$ 108

3.14 Intersecting occurrences of $w$ 116

3.15 $S_{i} ∖ S_{i}^{(R)}$ 120

3.16 Disallowed and allowed pairs of overlapping $w_{j, d}$ 127

3.17 A point $x \in X_{y}$ 138

3.18 The correspondence between copies of $Γ_{W}$ and points in $Γ_{j}^{(2)}$

139

3.19 How a copy of $Γ_{W}$ is filled if $b_{j, d} (p) = 1$ 140

3.20 $f^{'}$

141

$x$

(JIAPTER 1

INTRODUCTION

This introduction will serve as a brief mathematical and historical overview of both

of the main problems that we will examine in this thesis. Due to their somewhat

disparate natures, the two portions of this thesis will each contain a more in-depth

introduction as well. For this reason, we will for the most part relegate formal defi-

nitions to their pertinent introduction.

Ergodic theory is the study of average or long-term behavior of systems which evolve

with time. For example, one can consider a particle bouncing in a box at fixed speed.

Its position and velocity at any time can be represented by a vector in $R^{6}$ . One can

then model this behavior by taking $X$ to be the space of all possible positions and

velocities for the particle, and $T$ a self-map of $X$ which, given a position and velocity,

gives the position and velocity one second later. This pairing of a space $X$ with a

self-map $T$ is called a dynamical system.

The more general setup is that of a group $G$ acting on a space $X$ with some sort

of structure by maps ${T_{g}}_{g \in G}$ preserving this structure. In this thesis, $G$ is always

$Z^{d}$ for some $d \in$ N. Measure-theoretic ergodic theory occurs when $X$ is a measure

space with a probability measure $μ$ invariant under each $T_{g}$ , and so in this case we call

$(X, B, μ, {T_{g}}_{g \in G})$ a measure-preserving dynamical system. Topological dynam-

ics occurs when $X$ is a compact topological space and each $T_{g}$ is a homeomorphism,

and so in this case we call $(X, {T_{g}}_{g \in G})$ a topological dynamical system. In ei-

ther type of system, if $G = Z$ , then $T_{n} = (T_{1})^{n}$ for any integer $n$ , and so we shorten

$(X, B, μ, {T_{n}}_{n \in Z})$ to $(X, B, μ, T)$ and $(X, {T_{n}}_{n \in Z})$ to $(X, T)$ . (Here $T = T_{1} .$ )

These cases are not as disjoint as they may first appear: the famed Bogoliouboff-

Krylov theorem states that any topological dynamical system $(X, {T_{g}}_{g \in G})$ has at

least one invariant probability measure $μ$ as long as $G$ is an amenable group. (An

examination of amenability is beyond the scope of this thesis, but we mention that

amenable groups are a class which contain all abelian groups. We only consider

$G = Z^{d}$ in this thesis, so all topological dynamical systems examined here will possess

invariant measures.) This sometimes allows one to examine topological properties of

a system via properties of invariant measures. For instance, in Chapter 3, we will

prove some purely combinatorial properties of a $Z^{d}$ -action by homeomorphisms of a

Cantor set by means of studying the invariant measures of this action.

Chapter 2 deals primarily with ergodic averaging. One of the fundamental results of

ergodic theory is Birkhoff's ergodic theorem:

Theorem 1.0.1. ([Bi]) For any measure-preserving dynamical system $(X, B, μ, T)$

and any $f \in L^{1} (X)$ , $\lim_{n \to \infty} \frac{1}{n} \sum_{i = 0}^{n - 1} f (T^{i} x)$ exists for $μ$ -almost every $x \in X$ .

Several results have been proven about the convergence of such averages when one

averages not along all powers of $T$ , but only along some distinguished subset of the

integers. ([Bou], [Bou2], [Wi]) In particular, when one averages along ${p (n)}$ for a

polynomial $p (n)$ with integer coefficients, there is the following result of Bourgain:

Theorem 2.1.12. ([Bou], p. 7, Theorem t) For any measure-preserving dynamical

system $(X, B, μ, T)$ , for any polynomial $q (t) \in Z [t]$ , and for any $f \in L^{p} (X, B, μ)$ with

$p > 1$ , $\lim_{N \to \infty} \frac{1}{N} \sum_{n = 1}^{N} f (T^{q (n)} x)$ exists for $μ$ -almost every $x \in X$ .

Theorem 2.1.12 can be interpreted as follows: for any polynomial $q (t) \in Z [t]$ , any

measure-preserving system $(X, B, μ, T)$ , and any measure-theoretically "nice" func-

tion $f$ , the set of points $x$ where $\lim_{N \to \infty} \frac{1}{N} \sum_{n = 1}^{N} f (T^{q (n)} x)$ fails to converge is of mea-

sure zero, or negligible measure-theoretically. It is then natural to wonder whether or

not there is a topological parallel to this result using topological notions of "niceness"

(continuity) and negligibility (first category), and in fact such a question was posed

by Bergelson:

Question 2.1.13. ([Be], p. 51, Question 5) Assume that a topological dynamical

system $(X, T)$ is uniquely $e r g o d i c^{1}$ , and let $p \in Z [t]$ and $f \in C (X)$ . Is it true that for

all but a first category set of points $\lim_{n \to \infty} \frac{1}{n} \sum_{i = 0}^{n - 1} f (T^{p (i)} x)$ exists?

One of our results is a (quite negative) answer to Question 2.1.13:

Theorem 2.1.15. For any increasing sequence ${p_{n}}$ of integers with upper Banach

density $z e r o^{2}$ , there exists a totally minimal, totally uniquely ergodic, and topologically

1A topological dynamical system $(X, B, μ, T)$ is uniquely ergodic if there exists exactly one T-

invariant measure $μ$ .

$2 A$ set $A \subseteq N$ has upper Banach density zero if $\lim \sup_{n \to \infty} \sup_{m \in N} \frac{| {m, m + 1, ..., m + n - 1} \cap A |}{n} = 0$ .

mixing topological dynamical system $(X, T)$ and a continuous function $f$ on $X$ with

the property that $\frac{1}{N} \sum_{n = 0}^{N - 1} f (T^{p_{n}} x)$ fails to converge for a residual set of $x$ .

We also examine recurrence along distinguished subsets of the integers, motivated

primarily by the following result:

Theorem 2.1.17. ( $[B e L]$ , p. 14, Corollary 1.8) For any $d \in N$ , any $m i n i m a l^{3}$ topolog-

ical dynamical system $(X, {T_{v}}_{v \in Z^{d}})$ and any polynomials $q_{1} (t)$ , $q_{2} (t)$ , $...$ , $q_{d} (t) \in Z [t]$

with $q_{i} (0) = 0$ for $1 \underline{<} i \underline{<} d$ , for a residual set of $x \in X$ there exists a sequence

${n_{i}}$ of positive integers such that $T_{q (n_{i}) e_{i}} x \to x$ for $1 \underline{<} i \underline{<} d$ , where ${e_{i}}_{i = 1}^{d}$ is the

standard orthonormal basis of $R^{d}$ .

In particular, this implies that for any minimal topological dynamical system $(X, T)$

and any polynomial $q (t) \in Z [t]$ with $q (0) = 0$ , the set of $x \in X$ with $x \in {T^{q (n)} x}_{n \in N}$

is residual. The following result shows that for $q$ with degree at least two, this residual

set is not necessarily all of $X$ .

Theorem 2.1.18. For any increasing sequence ${p_{n}}$ of integers with upper Banach

density zero, there exists a totally minimal, totally uniquely ergodic, and topologically

mixing topological dynamical system (X,T) and an uncountable set A $\subset X$ such that

for every x $\in A$ , the sequence ${T^{p_{n}} x}$ does not have x as a limit point, i.e. there is

no sequence of positive integers ${n_{i}}$ such that $T^{p_{n_{i}}}$ x converges to x.

Another consequence of Theorem 2.1.17 is that for any commuting minimal homeo-

morphisms $T$ and $S$ of a compact space $X$ , there exists a residual set of $x$ for which

sA topological dynamical system $(X, B, μ, T)$ is minimal if there exist no nonempty proper closed

$T$ -invariant subsets of $X$ .

there exists a sequence of positive integers ${n_{i}}$ such that $T^{n_{i}} x \to x$ and $S^{n_{i}} x \to x$ .

The following theorem shows that for some systems, it is the case that this residual

set of $x$ is not all of $X$ .

Theorem 2.1.21. There exists a totally minimal topological dynamical system (X,T)

and a point x $\in X$ such that for any positive integers r $\neq s$ , any sequence ${n_{i}}$ of

integers satisfying $T^{r n_{i}} x \to x$ and $T^{s n_{i}} x \to x$ is eventually zero.

The systems which we construct to prove Theorems 2.1.15 and 2.1.18 are symbolic

dynamical systems. A symbolic dynamical system is defined by first choosing a

finite set $A$ , called the alphabet. $Ω = A^{G}$ endowed with the product topology is a

compact space, and for any $g \in G$ , we may define $σ_{g}$ the shift homeomorphism by

$(σ_{g} ω) (h) = ω (h g)$ for $ω$ $\in$ Q. Any closed set $X \underline{\subset} Ω$ has a topology induced by $Ω$ , and

if $X$ is invariant under each $T_{g}$ , then $(X, {σ_{g}}_{g \in G})$ is a topological dynamical system

which we call a symbolic dynamical system.

In Chapter 3, we examine symbolic dynamical systems exclusively. There, we consider

a specific type of symbolic dynamical system called a shift of finite type. A $Z^{d}$ -shift

of finite type is a symbolic dynamical system $(X, {σ_{v}}_{v \in Z^{d}})$ where $X$ is defined by

specifying a finite set $F$ of finite words (a word is a function from a finite subset of

$Z^{d}$ to $A$ ) and taking $X$ to be the set of all elements of $Ω$ in which none of the words

in $F$ appear. The shift of finite type $X$ specified by a finite set $F$ of words in this

way is denoted by $Ω_{F}$ . For example, the set of all biinfinite sequences of zeroes and

ones in which no two ones occur consecutively is a shift of finite type, as is the set of

all $Z^{2}$ arrays of zeroes and ones in which no three-by-four blocks of all zeroes or all

ones appear.

We are particularly interested in the effects of forbidding a particular word from a

shift of finite type $X$ . Given any word $w$ , define $X_{w}$ to be the set of elements of $X$ in

which $w$ does not appear. Then clearly $X_{w}$ is a subset of $X$ , and so the topological

entropy $h^{t o p} (X_{w})$ of $X_{w}$ is not greater than the topological entropy $h^{t o p} (X)$ of $X$ . It

is natural to wonder how much the topological entropy drops by when $w$ is removed,

as it is a sort of measure of how important $w$ is to the information-retaining capacity

of $X$ . In [L], Lind proved the following: (the condition $w \in L_{Γ_{n}} (X)$ means that

$w \in A^{[1, ..., n]^{d}}$ and that $w$ appears in some element of $X .$ )

Theorem 3.1.16. ([L], p. 360, Theorem 3) For any topologically transitive Z-shift

of finite type $X = Ω_{F}$ with positive topological entropy $h^{t o p} (X)$ , there exist constants

$C_{X}$ , $D_{X}$ , and $N_{X}$ such that for any $n >$ $N_{X}$ and any word $w \in L_{Γ_{n}} (X)$ , if we denote

by $X_{w}$ the shift of finite type $Ω_{F u {w}}$ , then

$\frac{C_{X}}{e^{h^{t o p} (X) n}} < h^{t o p} (X) - h^{t o p} (X_{w}) < \frac{D_{X}}{e^{h^{t o p} (X) n}}$ .

Our main result is a generalization of Theorem 3.1.16 for $Z^{d}$ -shifts of finite type

which satisfy a mixing condition called strong irreducibility. (We formally define

strong irreducibility in Definition 3.1.19.)

Theorem 3.1.22. For any d $>$ 1 and any strongly irreducible $Z^{d}$ -shift X $= Ω_{F}$

of finite type with uniform filling length R and positive topological entropy $h^{t o p} (X)$ ,

there exist constants $N_{X} \in N$ and $D_{X} \in R$ such that for any $n >$ $N_{X}$ and any word

$w \in L_{Γ_{n}} (X)$ , if we denote by $X_{w}$ the shift of finite type $Ω_{F u {w}}$ , then

$\frac{1}{e^{h^{t o p} (X) (n + 44 R + 70)^{d}}} < h^{t o p} (X) - h^{t o p} (X_{w}) < \frac{D_{X}}{e^{h^{t o p} (X) (n - 2 R)^{d}}}$ .

One way in which $Z^{d}$ -shifts of finite type are more difficult to deal with for $d > 1$ is

that given a finite collection $F$ of patterns, it is undecidable whether or not the shift

of finite type $X$ induced by $F$ is even nonempty. Our methods yield a situation in

which this question can be answered:

Theorem 3.6.1. For any alphabet A, there exist F, G $\in N$ such that for any m $> 0$

and any finite set of words $F_{m} = {w_{k} \in L_{Γ_{n_{k}}} (X)$ : $1 \underline{<} k \underline{<} m}$ satisfying $n_{1} > G$

and $n_{k} \underline{>} F (n_{k - 1})^{4 d^{2}}$ for $1 < k \underline{<} m$ , $Ω_{F_{m}} \neq \emptyset$ .

(JIAPTER 2

RECURRENCE AND CONVERGENCE OF ERGODIC

AVERAGES ALONG SPARSE SEQUENCES

2.1 Introduction

In this chapter, we are concerned with the convergence of averages of the form

$\frac{1}{N} \sum_{n = 0}^{N - 1} f (T^{p_{n}} x)$ for an increasing sequence of integers ${p_{n}}$ . We begin with some

definitions.

Definition 2.1.1. A measure-preserving dynamical system $(X, B, μ, {T_{g}}_{g \in G})$

consists of a measure space $X$ , a probability measure $μ$ with $σ$ -algebra 8 of measurable

sets, and a group action ${T_{g}}_{g \in G}$ of transformations $T_{g}$ : $X \to X$ with $μ (T_{g}^{- 1} A) =$

$μ (A)$ for all $A \in B$ .

Definition 2.1.2. A measure-preserving dynamical system (X,B, $μ, {T_{g}}_{g \in G})$ is er-

godic if any set A satisfying $T_{g} A \underline{\subset}$ A for all g $\in G$ has $μ (A) \in$ {0,1}.

Definition 2.1.3. A topological dynamical system (X, ${T_{g}}_{g \in G})$ consists of $a$

compact topological space X and a group action ${T_{g}}_{g \in G}$ of homeomorphisms $T_{g}$ :

X $\to X$ .

Definition 2.1.4. Given a topological dynamical system (X, ${T_{g}}_{g \in G})$ , a Borel prob-

ability measure $μ$ on X is called ergodic if (X, $B (X)$ , $μ$ , ${T_{g}}_{g \in G})$ is an ergodic

measure-preserving dynamical system, where $B (X)$ is the Borel $σ$ -algebra of X.

In this chapter, all dynamical systems have $G = Z$ , so as already described we

will use the notations $(X, B, μ, T)$ and $(X, T)$ for measure-preserving and topological

dynamical systems respectively.

Definition 2.1.5. A topological dynamical system (X,T) is minimal if for any

closed set K with $T^{- 1} K \underline{\subset} K$ , K $= \emptyset$ or K $= X$ . (X,T) is totally minimal if

(X, $T^{n})$ is minimal for every n $\in$ O.

Definition 2.1.6. A topological dynamical system (X,T) is uniquely ergodic if

there is only one Borel measure $μ$ on X such that $μ (A) = μ (T^{- 1} A)$ for every Borel

set $A \underline{\subset}$ X. (X,T) is totally uniquely ergodic if (X, $T^{n})$ is uniquely ergodic for

every n $\in N$ .

Definition 2.1.7. A topological dynamical system (X,T) is topologically mixing

if for any open sets U, $V \underline{\subset} X$ , there exists N $\in N$ such that for any n $>$ N,

$U \cap T^{n} V \neq \emptyset$ .

Definition 2.1.8. For any set $A \underline{\subset} N$ , the upper Banach density of A is defined

$d^{*} (A) = \lim \sup \sup \frac{| {m, m + 1, ..., m + n - 1} \cap A |}{n}$ .

$n \to \infty m \in N$

Definition 2.1.9. For any set $A \underline{\subset} N$ , the upper density of A is defined by

$\bar{d} (A) = \lim_{n \to} \sup_{\infty} \frac{| {1, ..., n} \cap A |}{n}$ .

Definition 2.1.10. For a set $A \underline{\subset} N$ , the density of A is defined by

$d (A) = \lim_{n \to \infty} \frac{| {1, ..., n} \cap A |}{n}$

if this limit exists.

Definition 2.1.11. Given a topological dynamical system (X,T) and a T-invariant

Borel probability measure $μ$ , a point x $\in X$ is (T, $μ)$ -generic if for every f $\in C (X)$ ,

$\lim_{n \to \infty} \frac{1}{n} \sum_{i = 0}^{n - 1} f (T^{i} x) = \int f d μ$ .

In the measure-preserving setup, there are several positive results about convergence

of averages of the form $\frac{1}{N} \sum_{n = 0}^{N - 1} f (T^{p_{n}} x)$ , including this theorem of Bourgain:

Theorem 2.1.12. ([Bou], p. 7, Theorem t) For any measure-preserving dynamical

system $(X, B, μ, T)$ , for any polynomial $q (t) \in Z [t]$ , and for any $f \in L^{p} (X, B, μ)$ with

$p > 1$ , $\lim_{N \to \infty} \frac{1}{N} \sum_{n = 1}^{N} f (T^{q (n)} x)$ exists for $μ$ -almost every $x \in X$ .

The following question regarding a possible topological version of Theorem 2.1.12 was

posed by Bergelson:

Question 2.1.13. ([Be], p. 51, Question 5) Assume that a topological dynamical

system $(X, T)$ is uniquely ergodic, and let $p \in Z [t]$ and $f \in C (X)$ . Is it true that for

all but a first category set of points $\lim_{n \to \infty} \frac{1}{n} \sum_{i = 0}^{n - 1} f (T^{p (i)} x)$ exists?

Bergelson added the hypothesis of unique ergodicity because it is a classical result

that a system $(X, T)$ is uniquely ergodic with unique $T$ -invariant measure $μ$ if and

only if for every $x \in X$ and $f \in C (X)$ , $\lim_{n \to \infty} \frac{1}{n} \sum_{i = 0}^{n - 1} f (T^{i} x) = \int_{X} f d μ$ , and so in

the topological setup this is a natural assumption to make about $(X, T)$ to achieve

the desired result.

However, Bergelson was particularly interested in the convergence of these averages

to the "correct limit," i.e. $\int_{X} f d μ$ where $μ$ is the unique $T$ -invariant measure on

$X$ . To have any hope for such a result, it also becomes necessary to assume ergod-

icity for all powers of $T$ in order to avoid some natural counterexamples related to

distribution (mod $k$ ) of $p (n)$ for positive integers $k$ . For example, if $p (n) = n^{2}$ , $T$ is

the permutation on $X = {0, 1, 2}$ defined by $T x = x + 1$ (mod 3), $μ$ is normalized

counting measure on $X$ , and $f = χ {0}$ , then $(X, T)$ is obviously uniquely ergodic with

unique invariant measure $μ = \frac{δ_{0} + δ_{1} + δ_{2}}{3}$ , but

$\lim_{n \to \infty} \frac{1}{n} \sum_{i = 0}^{n - 1} f (T^{p (i)} x) =$ $i f x = 1 i f x = 0 i f f x = 2'$ , .and

To avoid such examples, we would need $T$ to be totally ergodic as well as uniquely

ergodic, and so it makes sense to assume total unique ergodicity to encompass both

properties. Bergelson's revised question then looks like this:

Question 2.1.14. Assume that a topological dynamical system (X,T) is totally uniquely

ergodic with unique $T$ -invariant measure $μ$ , and let $p \in Z [t]$ and $f \in C (X)$ . Is it true

that for all but a first category set of points $\lim_{n \to \infty} \frac{1}{n} \sum_{i = 0}^{n - 1} f (T^{p (i)} x) = \int_{X} f d μ^{l} .$ ?

We answer Questions 2.1.13 and 2.1.14 negatively in the case where the degree of

$p$ is at least two, and in fact prove some slightly more general results. The level of

generality depends on what hypotheses we place on the space $X$ . In particular, we

can exhibit more counterexamples in the case where $X$ is a totally disconnected space

than we can in the case where $X$ is a connected space such as $T^{k}$ .

Theorem 2.1.15. For any increasing sequence ${p_{n}}$ of integers with upper Banach

density zero, there exists a totally minimal, totally uniquely ergodic, and topologically

mixing topological dynamical system $(X, T)$ and a continuous function $f$ on $X$ with

the property that $\frac{1}{N} \sum_{n = 0}^{N - 1} f (T^{p_{n}} x)$ fails to converge for a residual set of $x$ .

Theorem 2.1.16. For any increasing sequence ${p_{n}}$ of integers with the property

that for some integer $d$ , $p_{n + 1} < (p_{n + 1} - p_{n})^{d}$ for all suffiffifficiently large $n$ , there ex-

ists a totally minimal, totally uniquely ergodic, and topologically mixing topological

dynamical system $(X, T)$ and a continuous function $f$ on $X$ with the property that

$\frac{1}{N} \sum_{n = 0}^{N - 1} f (T^{p_{n}} x)$ fails to converge for a residual set of $x$ . In addition, the space $X$ is

a connected $2 d +$ 9-manifold.

We note that Theorems 2.1.15 and 2.1.16 answer Question 2.1.13 negatively for $p$

with degree at least two, since the sequence $p_{n} = p (n)$ for any nonlinear $p (t) \in Z [t]$

satisfies the hypotheses of both theorems.

Theorems 2.1.15 and 2.1.16 are about nonconvergence of ergodic averages along cer-

tain sequences of powers of $x$ . We also prove two similar results about nonrecurrence

of points. As motivation, we note that a minimal system has the property that every

point is recurrent. In other words, if $(X, T)$ is minimal, then for all $x \in X$ , it is the

case that $x \in {T^{n} x}_{n \in N}$ . If $(X, T)$ is totally minimal, then all points are recurrent

even along infinite arithmetic progressions: for any nonnegative integers $a$ , $b$ , and for

all $x \in X$ , $x \in {T^{a n + b} x}_{n \in N}$ . It is then natural to wonder if the same is true for other

sequences of powers of $T$ , and in this vein there is the following result of Bergelson

and Leibman, which is a corollary to their Polynomial van der Waerden theorem:

Theorem 2.1.17. ( $[B e L]$ , p. 14, Corollary 1.8) For any $d \in N$ , any minimal topolog-

ical dynamical system $(X, {T_{v}}_{v \in Z^{d}})$ and any polynomials $q_{1} (t)$ , $q_{2} (t)$ , $...$ , $q_{d} (t) \in Z [t]$

with $q_{i} (0) = 0$ for $1 \underline{<} i \underline{<} d$ , for a residual set of $x \in X$ there exists a sequence

${n_{i}}$ of positive integers such that $T_{q (n_{i}) e_{i}} x \to x$ for $1 \underline{<} i \underline{<} d$ , where ${e_{i}}_{i = 1}^{d}$ is the

standard orthonormal basis of $R^{d}$ .

In particular, Theorem 2.1.17 implies that for a minimal system $(X, T)$ and any

polynomial $p (t)$ with $p (0) = 0$ , the set of $x$ such that $x \in {T^{p (n)} x}_{n \in N}$ is residual. If

$(X, T)$ is assumed to be totally minimal, then by definition if the degree of $p$ is one,

then every point $x \in X$ is in ${T^{p (n)} x}_{n \in N}$ . The following two results imply that if the

degree of $p$ is greater than one, total minimality of $(X, T)$ does not necessarily imply

that every point $x \in X$ is in ${T^{p (n)} x}_{n \in N}$ .

Theorem 2.1.18. For any increasing sequence ${p_{n}}$ of integers with upper Banach

density zero, there exists a totally minimal, totally uniquely ergodic, and topologically

mixing topological dynamical system (X,T) and an uncountable set A $\subset X$ such that

for every $x \in A$ , the sequence ${T^{p_{n}} x}$ does not have $x$ as a limit point, $i . e$ . there is

no sequence of positive integers ${n_{i}}$ such that $T^{p_{n_{i}}} x$ converges to $x$ .

Theorem 2.1.19. For any increasing sequence ${p_{n}}$ of integers with the property

that for some integer $d$ , $p_{n + 1} < (p_{n + 1} - p_{n})^{d}$ for all suffiffifficiently large $n$ , there exists $a$

totally minimal, totally uniquely ergodic, and topologically mixing topological dynam-

ical system $(X, T)$ and a point $x \in X$ such that the sequence ${T^{p_{n}} x}$ does not have

$x$ as a limit point, $i . e$ . there is no sequence of positive integers ${n_{i}}$ such that $T^{p_{n_{i}}} x$

converges to $x$ . In addition, the space $X$ is a connected $2 d +$ 7-manifold.

The following simple lemma shows that if $(X, T)$ is topologically mixing, then The-

orems 2.1.18 and 2.1.19 cannot be improved too much, i.e. there is no increasing

sequence ${p_{n}}$ for which we can exhibit topologically mixing examples with a second

category set of such nonrecurrent points.

Lemma 2.1.20. If a topological dynamical system (X,T) is topologically mixing, then

for any increasing sequence ${p_{n}}$ , the set of x $\in X$ for which x $\notin {T^{p_{n}} x}$ is of first

category.

Proof: Define $C_{ε} = {x : d (x, T^{p_{n}} x) \underline{>} \in \forall n \in Z}$ . It is clear that $C_{ε}$ is closed. We

claim that $C_{ε}$ contains no nonempty open set, which shows that it is nowhere dense,

implying that $C = \cup_{n = 1}^{\infty} C_{\frac{1}{n}}$ the set of points $x$ for which $x$ is not a limit point of

${T^{p_{n}} x}$ is of first category. Suppose, for a contradiction, that there is a nonempty

open set $U$ with $U \underline{\subset} C_{ε}$ for some $ε$ . Then, there exists $V$ with diam(V $< ε$ such that

$V \underline{\subset} U \underline{\subset} C_{ε}$ . By topological mixing, there exists $n$ such that $V \cap T^{- p_{n}} V \neq \emptyset$ . This

implies that there exists $x \in V$ so that $T^{p_{n}} x \in V$ . Since diam(V $< ε$ , $d (x, T^{p_{n}} x) < ε$ .

However, $x \in V \underline{\subset} C_{ε}$ , so we have a contradiction.

$□$

Theorem 2.1.18 shows that it is possible for this set of points nonrecurrent along $p_{n}$

to be uncountable though.

We mention that some mixing condition is necessary for a statement like Lemma 2.1.20;

as a simple example, consider an irrational circle rotation $T$ : $x \mapsto x + α$ on the cir-

cle T. There is clearly some increasing sequence of integers ${p_{n}}$ such that $p_{n} (y$

(mod $1$ ) $\to \frac{1}{2}$ . Then, for any $x \in T$ , $T^{p_{n}} x \to x + \frac{1}{2}$ , and so for every $x \in X$ , ${T^{p_{n}} x}$

does not have $x$ as a limit point.

We also prove a result about simultaneous recurrence. Theorem 2.1.17 implies that

for any commuting minimal homeomorphisms $T$ and $S$ of a compact space $X$ , there

exists a residual set of $x$ for which there exists a sequence of positive integers ${n_{i}}$

such that $T^{n_{i}} x \to x$ and $S^{n_{i}} x \to x$ . The following theorem shows that for some

systems, it is the case that this residual set of $x$ is not all of X. (In this particular

example, $T$ and $S$ are powers of the same homeomorphism.)

Theorem 2.1.21. There exists a totally minimal topological dynamical system (X,T)

and a point x $\in X$ such that for any positive integers r $\neq s$ , any sequence ${n_{i}}$ of

integers satisfying $T^{r n_{i}} x \to x$ and $T^{s n_{i}} x \to x$ is eventually zero.

Before proceeding with the proofs, we now give a brief description of the content of

this chapter. In Section 2.2, we will describe some general symbolic constructions of

topological dynamical systems with particular mixing properties. At the end of this

section, we will arrive at a construction of a system which is totally minimal, totally

uniquely ergodic, and topologically mixing, and which has as a parameter a sequence

of integers ${n_{k}}$ .

In Section 2.3, by taking this sequence ${n_{k}}$ to grow very quickly, we will show

that the examples constructed in Section 2.2 are sufficient to prove Theorems 2.1.15

and 2.1.18. Some interesting questions also arise and are answered in Section 2.3

pertaining to the upper Banach density of countable unions of sets of upper Banach

density zero.

In Section 2.4, we create a flow under a function with base transformation a skew

product, which acts on a connected manifold, and which is totally minimal, totally

uniquely ergodic, and topologically mixing. This transformation has as a parameter

a function $f \in C (T)$ . We use conditions of Fayad ([Fa]) on flows under functions

to achieve topological mixing, and some conditions of Furstenberg ([Fu]) on skew

products to prove total unique ergodicity.

In Section 2.5, by a judicious choice of $f$ , we use the examples of Section 2.4 to prove

Theorems 2.1.16 and 2.1.19.

In Section 2.6, we prove Theorem 2.1.21.

Finally, in Section 2.7 we give some open questions about strengthening our results.

2.2 Some general symbolic constructions

Definition 2.2.1. An alphabet is any finite set, whose elements are called letters.

Definition 2.2.2. A symbolic dynamical system with alphabet $A$ is a topological

dynamical system $(X, {σ_{g}}_{g \in G})$ where for any $g \in G$ , $σ_{g}$ is the shift homeomorphism

of $Ω = A^{G}$ defined by $(σ_{g} ω) (h) = ω (h g)$ for $ω \in Ω$ , and $X$ is any closed subset of $Ω$

invariant under each $σ_{g}$ .

Definition 2.2.3. A word on the alphabet A is any element of $A^{F}$ for some finite

set F $\subset G$ . F is called the shape of w.

For any words $v$ of length $m$ and $w$ of length $n$ , we denote by $v w$ their concatenation,

i.e. the word $v [1] v [2] ...$ $v [m] w [1] w [2] ...$ $w [n]$ of length $m + n$ . We denote by $w^{k}$ the

word torn . . . $w$ given by the concatenation of $k$ copies of $w$ .

Definition 2.2.4. Given any symbolic dynamical system (X, ${σ_{g}}_{g \in G})$ , the language

of X, denoted by $L (X)$ , is the set of all words which appear as subwords of X.

All symbolic dynamical systems appearing in this chapter have alphabet {0, 1}, $G =$

Z. We also restrict ourselves in this chapter to words with shape ${$ 1, $...$ , $n}$ for some

$n$ . In other words, a word can be thought of for now as a finite string of letters

$w = w (1) w (2) ...$ $w (n)$ . The number of letters in a word $w$ is called its length.

Definition 2.2.5. A word w of length n is a subword of a sequence u $\in Ω$ if there

exists k $\in Z$ such that $u (i + k) = w (i)$ for $1 \underline{<} i \underline{<} n$ . Analogously, w is a subword

of a word v of length m if there exists $0 < k < m$ -n such that $v (i + k) = w (i)$ for

$1 \underline{<} i \underline{<} n$ .

We will outline three constructions which algorithmically create $X$ such that $(X, σ)$

have certain properties. (Here the "certain properties" in question depend on which

construction is used.) It should also be mentioned that many ideas from these con-

structions are taken from work of Hahn and Katznelson $([H a K])$ , where they also

algorithmically constructed symbolic topological dynamical systems with certain er-

godicity and mixing properties.

Construction 1: (Minimal) We define inductively $n_{k}$ and $A_{k}$ , which are, respec-

tively, sequences of positive integers and sets of words on the alphabet {0, 1}. Each

word in $A_{k}$ is of length $n_{k}$ . (We will use the term " $A_{k}$ -word" to refer to a member of

$A_{k}$ from now on.) We define these as follows: always define $n_{1} = 1$ and $A_{1} = {0, 1}$ .

Then, for any $k \underline{>} 1$ , $n_{k + 1}$ is defined to be any integer greater than or equal to $n_{k} | A_{k} |$

which is also a multiple of $n_{k}$ , and then $A_{k + 1}$ is chosen to be the set of words of

length $n_{k + 1}$ which are concatenations of $A_{k}$ -words, containing each $A_{k}$ word in the

concatenation at least once.

We then define $X$ to be the set of all $x \in Ω$ which are limits of shifted $A_{k}$ words In

other words, $x \in X$ if there exist $w_{k} \in A_{k}$ and $m_{k} \in Z$ such that for all large enough

$i$ , $x (i) = w_{k} (i - m_{k})$ . Since $Ω$ is compact, such $x$ exist by a standard diagonalization

argument. It is easily checkable that $X$ is closed and a-invariant. The claim is that

regardless of the choice of the integers $n_{k}$ , as long as $n_{k}$ divides $n_{k + 1}$ , and $n_{k + 1} \underline{>}$

$n_{k} | A_{k} |$ , $(X, σ)$ is minimal. It suffices to show that for any $y \in X$ , ${σ^{n} y}_{n \in Z} = X$ .

Choose any $y \in X$ and $w \in L (X)$ . By the definition of $X$ , there exists $k$ and some

$A_{k}$ word $w_{k}$ such that $w$ is a subword of $w_{k}$ . $w_{k}$ is an $A_{k}$ -word, so by definition,

every $A_{k + 1}$ -word contains $w_{k}$ , and therefore $w$ , as a subword. Finally, note that again

by the definition of Construction 1, $y$ is an biinfinite concatenation of $A_{k + 1}$ words

This implies that $y (1)$ . . . $y (2 n_{k + 1})$ contains some $A_{k + 1}$ word, and therefore $w$ , as a

subword, and so there exists $n \in Z$ so that $σ^{n} y$ begins with $w$ . Since $w$ was an

arbitrary word in $L (X)$ , this implies that ${σ^{n} y}_{n \in Z} = X$ , and so $(X, σ)$ is minimal.

$□$

So, we have now demonstrated a way of constructing minimal $(X, σ)$ . We will now

make this construction a bit more complex in order to make $(X, σ)$ totally minimal.

Construction 2: (Totally minimal) We define inductively $n_{k}$ and $A_{k}$ , which are,

respectively, sequences of positive integers and sets of words on the alphabet {0, 1}.

Each word in $A_{k}$ is of length $n_{k}$ . We define these as follows: always define $n_{1} = 1$

and $A_{1} = {0, 1}$ . Then, for any $k \underline{>} 1$ , $n_{k + 1}$ is defined to be any integer greater than

or equal to $(k!)^{2} n_{k} | A_{k} | + k! + n_{k}^{2}$ , and then $A_{k + 1}$ is chosen to be the set of words $w$ of

length $n_{k + 1}$ which are concatenations of $A_{k}$ -words and the word 1 with the following

properties: the word 1 does not appear at the beginning or end of $w^{'}$ , only a single

1 can be concatenated between two $A_{k}$ -words, and for every $w^{'} \in A_{k}$ , and for every

$0 \underline{<} i < k!$ , $w$ appears in $w^{'}$ at an $i$ (mod $k!$ )-indexed place. That is, there exists

$m \equiv i$ (mod $k!$ ) with $w (m) w (m + 1)$ . . . $w (m + n_{k} - 1)$ $= w^{'}$ . From now on, to refer

to this second condition, we say that every $w^{'} \in A_{k}$ occurs in $w$ at places indexed by

all residue classes modulo $k!$ .

Since this construction is a bit complicated, a few quick examples may be in or-

der. Suppose that $n_{2} = 6$ , $| A_{2} | = 4$ , and we choose $n_{3} = 134$ . Say that $A_{2} =$

${a, b, c, d} . T h e n w = a b c d 1 a b c d 1 d a b c d a b c a b c d a b$ is an $A_{3} - w o r d$ : each $A_{2}$ word ap-

pears at least once beginning with a letter of $w$ with an odd index, and at least

once beginning with a letter of $w$ with an even index. Examples of words which

would not be $A_{3}$ -words include abcdllabcddabcdababcabcd (1 is concatenated twice

between $d$ and $a$ ), abcdo lbcdldbcdaabcbbbbdc (occurrences of the word $a$ begin only

with even-indexed letters), or abcdldcbabcdabcdabcdadb (wrong number of letters.)

We can then define $X$ to again be the set of all $x \in Ω$ which are limits of shifted

$A_{k}$ -words. For this definition to make sense, it suffices to show that $A_{k}$ is nonempty

for all $k$ , since if this is true then $X \neq \emptyset$ by compactness of $Ω$ and a diagonalization

argument just as in Construction 1. $A_{1}$ is nonempty, so it suffices to show that $A_{k} \neq \emptyset$

implies $A_{k + 1} \neq \emptyset$ for all $k$ . For any $k$ , assume that $w_{k} \in A_{k}$ . Then, enumerate the

elements of $A_{k}$ by $w_{k} = \frac{a_{1}, a_{2}, ..., a_{| A_{k} |}, a n_{k} d d n_{k + 1^{- k^{1} (k^{1} n_{k} | A_{k} | + 1) - i (n + 1)}}}{n_{k}}$ efine the words $u_{k + 1} = a_{1}^{k!} a_{2}^{k!}$ . . . $a_{| A_{k} |}^{k!}$

and $w^{'} = (u_{k + 1} 1)^{k!} (a_{1} 1)^{i} a_{1}$ , where $i \equiv n_{k + 1} - k!$ (mod $n_{k}$ ). Since

$n_{k + 1} > (k!)^{2} n_{k} | A_{k} | + k! + n_{k}^{2}$ , $w^{'}$ exists, and is a concatenation of $A_{k}$ -words and the

word 1 with length $n_{k + 1}$ . In $w^{'}$ , at most a single 1 is concatenated between any two

$A_{k}$ -words and 1 does not appear at the beginning or end of $w^{'}$ . Also, since the length

of $u_{k + 1}$ is divisible by $k!$ , and since all $A_{k}$ -words are subwords of $u_{k + 1}$ , all $A_{k}$ words

appear in $(u_{k + 1} 1)^{k!}$ at places indexed by all residue classes modulo $k!$ , and so all

$A_{k}$ words appear in $w^{'}$ at places indexed by all residue classes modulo $k!$ as well.

Therefore, $w^{'} \in A_{k + 1}$ , and so $A_{k + 1}$ is nonempty.

We will show that $(X, σ)$ is totally minimal. Fix any $m > 0$ . We wish to show that

for any $y \in X$ , ${σ^{m n} y}_{n \in Z} = X$ . Choose any such $y$ , and fix any word $w \in L (X)$ .

By definition of $X$ , there exists $k$ and an $A_{k}$ word $w_{k}$ such that $w$ is a subword of

$w_{k}$ . Without loss of generality, we assume that $k > m$ . By the construction, $w_{k}$

occurs in every $A_{k + 1}$ -word, and it occurs at places indexed by every residue class

modulo $k!$ . Since $k > m$ , in particular this implies that $w_{k}$ , and therefore $w$ , occurs

in every $A_{k + 1}$ -word at places indexed by every residue class modulo $m$ . By definition

of Construction 2, $y$ is a biinfinite concatenation of $A_{k + 1}$ -words and the word 1.

Therefore, $y (1)$ . . . $y (2 n_{k + 1} + 2)$ contains some $A_{k + 1}$ -word as a subword, and so $w$

occurs in $y (1)$ . . . $y (2 n_{k + 1} + 2)$ at places indexed by every residue class modulo $m$ .

There then exists $n$ so that $σ^{m n} y$ begins with $w$ . Since $w$ was an arbitrary word of

$L (X)$ , this shows that ${σ^{m n} y}_{n \in Z} = X$ , and since $m$ was arbitrary, that $(X, σ)$ is

totally minimal.

$□$

We now define one more general type of construction, again more complex than the

last, so that the system created is always totally uniquely ergodic and topologically

mixing, in addition to being totally minimal. For this last construction, we first need

a couple of definitions.

Definition 2.2.6. For any integers $0 \underline{<} i < m$ and $k$ , and $w \in A_{k - 1}$ and $w^{'} \in$

$A_{k}$ , we define $f r_{i, m}^{*}$ $(w, w^{'})$ to be the ratio of the number of occurrences of $w$ as $a$

concatenated $A_{k - 1}$ -rvord at $i$ (mod $m$ )-indexed places in $w^{'}$ to the total number of

$A_{k - 1}$ -rvords concatenated in $w^{'}$ .

We consider any positive integer to be equal to 0 (mod t) for the purposes of this

definition. An example is clearly in order: if $A_{1} = {01, 10}$ , $w = 01$ , (in Construc-

tions 2 and 3, $A_{1}$ is always taken to be {0, 1}, but here we deviate from this for

illustrative purposes) and $w^{'}$ is the $A_{2}$ word Ot $| 10 | 1 | 01$ $| 10$ (here vertical bars show

where breaks in the concatenation occur), then $w$ occurs twice out of four $A_{1}$ -words,

so $f r_{0, 1}^{*}$ $(w, w^{'})$ $= \frac{1}{2}$ . Since one of these occurrences begins at $w^{'} (1)$ and one begins at

$w^{'} (6)$ , $f r_{0, 2}^{*} (w, w^{'}) = f r_{1, 2}^{*} (w, w^{'}) = \frac{1}{4}$ . We make a quick note here that there could

be some ambiguity here if an $A_{k + 1}$ -word could be decomposed as a concatenation of

$A_{k}$ words and ones in more than one way. For this reason, we just assume that when

computing $f r_{i, j}^{*}$ $(w, w^{'})$ , the definition of the $A_{k + 1}$ word $w^{'}$ includes its representation

as a concatenation of $A_{k}$ -words and ones. (i.e. in the example given, $w^{'}$ is defined

as the concatenation Of $| 10 | 1 | 01$ $| 10$ of $A_{1}$ -words and ones, rather than the nine-letter

word 011010110.)

Definition 2.2.7. Given any words $w^{'}$ of length $n^{'}$ and w of length $n \underline{<} n^{'}$ , and any

integers $0 \underline{<} i < m$ , define $f r_{i, m}$ (w, $w^{'})$ to be the number of occurrences of w at $i$

(mod m)-indexed places in $w^{'}$ , divided by $n^{'} - n + 1$ .

Taking the previous example again, $f r_{0, 1} (w, w^{'}) = \frac{3}{8}$ , since 01 occurs three times as

a subword of 011010110. Since two of these occurrences begin at letters of $w^{'}$ with

even indices and one begins at a letter of $w^{'}$ with odd index, $f r_{0, 2} (w, w^{'}) = \frac{2}{8}$ and

$f r_{1, 2} (w, w^{'}) = \frac{1}{8}$ .

Construction 3: (Totally minimal, totally uniquely ergodic, and topologi-

cally mixing) We define inductively $n_{k}$ and $A_{k}$ , which are, respectively, sequences

of positive integers and sets of words on the alphabet {0, 1}. Each word in $A_{k}$ is of

length $n_{k}$ . We define these as follows: always define $n_{1} = 1$ and $A_{1} = {0, 1}$ . Then,

we fix any sequence ${d_{k}}$ of positive reals such that $\sum_{k = 1}^{\infty} d_{k} < \infty$ and define, for each

$k \underline{>} 1$ , some $n_{k + 1} = C_{k} (k + 1)! | A_{k} | n_{k} + p$ for any integer $C_{k} > n_{k} > \frac{1}{d_{k}}$ and prime

$n_{k} < p \underline{<} 2 n_{k}$ (We may choose such a $p$ by Bertrand's postulate. $[H a W]$ ) Note that

this implies that $(n_{k}, k!) = 1$ for all $k \in N$ . We then define $A_{k + 1}$ to be the set of words

$w^{'}$ of length $n_{k + 1}$ with all of the same properties as in Construction 2, along with the

property that, for any $w \in A_{k}$ , and for any $0 \underline{<} i < k!$ , $f r_{i, k!}^{*} (w, w^{'}) \in [\frac{1 - d_{k}}{k! | A_{k} |}, \frac{1 + d_{k}}{k! | A_{k} |}]$ .

$X$ is again taken to be the set of $x \in Ω$ which are limits of shifted $A_{k}$ words For

this definition to make sense, it suffices to show that $A_{k}$ is nonempty for all $k$ , since

if this is true then $X \neq \emptyset$ by compactness of $Ω$ and a diagonalization argument

just as in Construction 1. $A_{1}$ is nonempty, so it suffices to show that $A_{k} \neq \emptyset$

implies $A_{k + 1} \neq \emptyset$ for all $k$ . For any $k$ , assume that $w_{k} \in A_{k}$ . Then, enumerate the

elements of $A_{k}$ by $w_{k} = a_{1}$ , $a_{2}$ , $...$ , $a | A_{k} |$ , and define the words $u_{k + 1} = a_{1}^{k!} a_{2}^{k!}$ . . . $a_{| A_{k} |}^{k!}$

and $w^{'} =$ $(u_{k + 1})^{C_{k} (k + 1) - p} (u_{k + 1} 1)^{p}$ . Clearly for large $k$ , $w^{'}$ exists, and is a concatenation

of $A_{k}$ -words and the word 1 with length $n_{k + 1}$ . In $w^{'}$ , at most a single 1 is concatenated

between any two $A_{k}$ -words and 1 does not appear at the beginning or end of $w^{'}$ . Since

$(n_{k}, k!) = 1$ , for every $0 \underline{<} i < k!$ and $x \in A_{k}$ , $x$ appears in $u_{k + 1}$ exactly once as a

concatenated $A_{k}$ -word at an $i$ (mod $k!$ )-indexed place. Therefore, $x$ appears in $w^{'}$

exactly $C_{k} (k + 1)$ times as a concatenated $A_{k}$ -word at $i$ (mod $k!$ )-indexed places, and

so $f r_{i, k!}^{*} (x, w^{'}) = \frac{1}{| A_{k} | n_{k} k!}$ . Since $i$ and $x$ were arbitrary, $w^{'} \in A_{k + 1}$ , and so $A_{k + 1} \neq \emptyset$ .

$(X, σ)$ is totally minimal by the same proof used for Construction 2. We claim that

$(X, σ)$ is also totally uniquely ergodic. Take any word $w \in L (X)$ , and any fixed integer

$j$ . We define two sequences ${m_{k}^{(j)}}$ and ${M_{k}^{(j)}}$ as follows: $m_{k}^{(j)}$ is the minimum value

of $f r_{i, j} (w, w^{'})$ , where $0 \underline{<} i < j$ and $w^{'}$ ranges over all $A_{k}$ word and $M_{k}^{(j)}$ is the

maximum value of $f r_{i, j}$ $(w, w^{'})$ , where $0 \underline{<} i < j$ and $w^{'}$ ranges over all $A_{k}$ -words.

Suppose that $m_{k}^{(j)}$ and $M_{k}^{(j)}$ are known, and that $k > j$ . We wish to show that $a m_{k + 1}^{(j)}$

and $M_{k + 1}^{(j)}$ are very close to each other. Let us consider any element $w^{'}$ of $A_{k + 1}$ and,

for any fixed $0 \underline{<} i < j$ , see how few occurrences of $w$ there could possibly be at $i$

(mod $j$ )-indexed places in $w^{'}$ . By the definition of Construction 3, for every $w^{'} \in A_{k}$ ,

and $0 \underline{<} i^{'} < k!$ , the ratio of the number of times $w^{'}$ occurs as a concatenated $A_{k}$ word

in $w^{'}$ whose first letter is a letter of $w^{'}$ whose index is equal to $i^{'}$ (mod $k!$ ) to the total

number of $A_{k}$ -words concatenated in $w^{'}$ is at least $\frac{1 - d_{k}}{k! | A_{k} |}$ . Since $j$ divides $k!$ , then for

any $0 \underline{<} i^{'} < j$ , the ratio of the number of times that $w^{'}$ occurs as a concatenated $A_{k^{-}}$

word at $i^{'}$ (mod $j$ )-indexed places in $w^{'}$ to the total number of $A_{k}$ -words concatenated

in $w^{'}$ is at least $\frac{1 - d_{k}}{j | A_{k} |}$ . Since the total number of $A_{k}$ -words concatenated in $w^{'}$ is at

least $\frac{n_{k + 1}}{n_{k} + 1}$ , this implies that the number of such occurrences of $w^{'}$ in $w^{'}$ is at least

$\frac{1 - d_{k}}{j | A_{k} |} \frac{n_{k + 1}}{n_{k} + 1}$ for any $i^{'}$ and $w^{'}$ . For any $w^{'}$ and $i^{'}$ , the number of times that $w$ occurs at $i$

(mod $j$ )-indexed places in $w^{'}$ as a subword of an occurrence of $w^{'}$ that occurs at an $i^{'}$

(mod $j$ )-indexed place in $w$ is then at least $\frac{1 - d_{k}}{j | A_{k} |} \frac{n_{k + 1}}{n_{k} + 1} (n_{k} - | w | + 1) f r_{i - i^{'}} (m o d j), j (w, w^{'})$ .

Summing over all $w^{'} \in A_{k}$ and $0 \underline{<} i^{'} < j$ , the number of occurrences of $w$ in $w^{'}$ at $i$

(mod $j$ )-indexed places is at least

$(1 - d_{k}) n_{k + 1} \frac{n_{k} - | w | + 1}{n_{k} + 1} \frac{\sum_{w^{'} \in A_{k}} \sum_{m = 0}^{j - 1} f r_{m, j} (w, w^{'})}{j | A_{k} |}$ .

Since $w^{'}$ was arbitrary in $A_{k + 1}$ and $0 \underline{<} i < j$ was arbitrary,

$m_{k + 1}^{(j)} \underline{>}$ $(1 - d_{k}) \frac{n_{k + 1}}{n_{k + 1} - | w | + 1} \frac{n_{k} - | w | + 1}{n_{k} + 1} \frac{\sum_{w^{'} \in A_{k}} \sum_{m = 0}^{j - 1} f r_{m, j} (w, w^{'})}{j | A_{k} |}$ .

Let us now bound from above the number of occurrences of $w$ in $w^{'}$ at $i$ (mod $j$ )-

indexed places. By precisely the same reasons as above, for any $0 \underline{<} i < j$ , the

number of occurrences of $w$ at $i$ (mod $j$ )-indexed places which lie entirely within a

concatenated $A_{k}$ -word in $w^{'}$ is not more than

$(1 + d_{k}) n_{k + 1} \frac{n_{k} - | w | + 1}{n_{k}} \frac{\sum_{w^{'} \in A_{k}} \sum_{m = 0}^{j - 1} f r_{m, j} (w, w^{'})}{j | A_{k} |}$ .

(The denominator of the first fraction changed because there are at most $\frac{n_{k + 1}}{n_{k}} A_{k^{-}}$

words concatenated in $w^{'} .$ ) However, it is possible that there are occurrences of $w$

in $w^{'}$ which do not lie entirely within a concatenated $A_{k}$ -word in $w^{'}$ . The number

of such occurrences of $w$ is not more than $| w | + 1$ times the number of concatenated

$A_{k}$ words in $w^{'}$ , which in turn is less than or equal to $(| w | + 1)$ $\frac{n_{k + 1}}{n_{k}}$ . This means that

the number of occurrences of $w$ at $i$ (mod $j$ )-indexed places in $w^{'}$ is bounded from

above by

$(1 + d_{k}) n_{k + 1} \frac{n_{k} - | w | + 1}{n_{k}} \frac{\sum_{w^{'} \in A_{k}} \sum_{m = 0}^{j - 1} f r_{m, j} (w, w^{'})}{j | A_{k} |} + (| w | + 1) \frac{n_{k + 1}}{n_{k}}$ ,

and since $0 \underline{<} i < j$ was arbitrary, this implies that

$M_{k + 1}^{(j)} \underline{<}$ $(1 + d_{k}) \frac{n_{k} - | w | + 1}{n_{k}} \frac{\sum_{w^{'} \in A_{k}} \sum_{m = 0}^{j - 1} f r_{m, j} (w, w^{'})}{j | A_{k} |} \underline{n_{k + 1}}$

$n_{k + 1} - | w | + 1$

$+ \underline{n_{k + 1}} \underline{| w | + 1}$ .

$n_{k + 1} - | w | + 1$ $n_{k}$

This implies that

$M_{k + 1}^{(j)} - m_{k + 1}^{(j)} \underline{<} 2 d_{k} \frac{n_{k + 1}}{n_{k + 1} - | w | + 1} \frac{n_{k} - | w | + 1}{n_{k}} \frac{\sum_{w^{'} \in A_{k}} \sum_{m = 0}^{j - 1} f r_{m, j} (w, w^{'})}{j | A_{k} |}$

$+ \underline{n_{k + 1}} \underline{| w | + 1}$ .

$n_{k + 1} - | w | + 1$ $n_{k}$

Since $f r_{m, j} (w, w^{'}) \underline{<} 1$ for every $0 \underline{<} m < j$ and $w^{'} \in A_{k}$ , for large $k$ this shows that

$M_{k + 1}^{(j)} - m_{k + 1}^{(j)} \underline{<} 2 d_{k} + \frac{2 (| w | + 1)}{n_{k}}$ , which clearly approaches zero as $k \to \infty$ .

We now note that since

and since by definition $f r_{m, j} (w, w^{'}) \underline{>} m_{k}^{(j)}$ for all $w^{'} \in A_{k}$ , we see that $m_{k + 1}^{(j)} \underline{>}$

$(1 - d_{k}) \frac{n_{k + 1}}{n_{k + 1} - | w | + 1} \frac{n_{k} - | w | + 1}{n_{k} + 1} m_{k}^{(j)}$ , and so

$m_{k + 1}^{(j)} - m_{k}^{(j)} \underline{>} m_{k}^{(j)} [(1 - d_{k}) (1 + \frac{| w |}{n_{k + 1} - | w | + 1}) (1 - \frac{| w | - 1}{n_{k} + 1}) - 1]$

$\underline{>} - m_{k}^{(j)} (d_{k} + \frac{| w |}{n_{k} + 1}) \underline{>} - (d_{k} + \frac{| w |}{n_{k}})$ .

By almost completely analogous reasoning, for large $k$

$M_{k + 1}^{(j)} - M_{k}^{(j)} \underline{<} M_{k}^{(j)} [(1 + d_{k}) (1 + \frac{| w | - 1}{n_{k + 1} - | w | + 1}) (1 - \frac{| w | - 1}{n_{k}}) - 1]$

$+ \frac{n_{k + 1}}{n_{k + 1} - | w | + 1} \frac{| w | + 1}{n_{k}} \underline{<} M_{k}^{(j)} d_{k} + \frac{2 (| w | + 1)}{n_{k}} \underline{<} d_{k} + \frac{2 | w | + 1}{n_{k}}$ .

Therefore,

$m_{k + 1}^{(j)} \underline{<} M_{k + 1}^{(j)} \underline{<} M_{k}^{(j)} + d_{k} + \frac{2 | w | + 1}{n_{k}} \underline{<} m_{k}^{(j)}$ a $2 d_{k - 1} + \frac{2 (| w | + 1)}{n_{k - 1}} + d_{k} + \frac{2 | w | + 1}{n_{k}}$

$\underline{<} m_{k}^{(j)} + 2 d_{k - 1} + d_{k} + \frac{4 | w | + 3}{n_{k - 1}}$ ,

so $| m_{k + 1}^{(j)} - m_{k}^{(j)} | \underline{<} d_{k} + 2 d_{k - 1} + \frac{4 | w | + 3}{n_{k - 1}}$ . In a completely analogous fashion, $| M_{k + 1}^{(j)} -$

$M_{k}^{(j)} | \underline{<} d_{k} + 2 d_{k - 1} + \frac{3 | w | + 2}{n_{k - 1}}$ . We know that $\sum_{k = 1}^{\infty} d_{k}$ converges, and since $n_{k} \underline{>} 2^{k}$ for

all $k$ , $\sum_{k = 1}^{\infty} \frac{1}{n_{k}}$ converges as well. Therefore, we see that the sequences ${m_{k}^{(j)}}$ and

${M_{k}^{(j)}}$ are Cauchy, and converge. Since we also showed that $M_{k}^{(j)} - m_{k}^{(j)} \to 0$ , we

know that they have the same limit, call it $(y$ .

This implies that for very large $k$ , $| f r_{i, j} (w, w^{'}) - α |$ is very small for every $0 \underline{<} i < j$ and

$w^{'} \in A_{k}$ . We claim that this, in turn, implies that for very large $N$ , $| f r_{i, j} (w, w^{'}) - α |$ is

very small for every word $w^{'} \in L (X)$ of length $N$ : fix any $ε > 0$ , and take $k$ such that

$| f r_{i, j} (w, w^{'}) - α | <$ : for every $0 \underline{<} i < j$ and $w^{'} \in A_{k}$ , and such that $\frac{1 + | w |}{n_{k}} < \frac{ε}{4}$ . Then

for any word $w^{'} \in L (X)$ of length at least $\frac{8 n_{k}}{ε}$ , $w^{'}$ is a subword of a concatenation

of $A_{k}$ -words and copies of the word 1. The number of full $A_{k}$ -words appearing in

the concatenation formi $n g$ $w^{'}$ iiss aatt lleeaasstt $\frac{| w^{'} |}{n_{k} + 1} - 2$ , and aatt mmoosstt $\frac{| w^{'} |}{n_{k}}$ . So, the number

of occurrences of $w$ at $i$ (mod $j$ )-indexed places in $w^{'}$ which are contained entirely

within a concatenated $A_{k}$ -word is at least $(\frac{(n_{k} - | w | + 1) | w^{'} |}{n_{k} + 1} - 2 (n_{k} - | w | + 1)) (α - \frac{ε}{2})$ $\underline{>}$

$| w^{'} | ((1 - \frac{ε}{4}) - \frac{ε}{4}) (α - \frac{ε}{2}) \underline{>} | w^{'} | (α - ε)$ , and at most $| w^{'} | \frac{n_{k} - | w | + 1}{n_{k}} (α + \frac{ε}{2}) \underline{<} | w^{'} | (α + \frac{ε}{2})$ .

Since there are at most $\frac{(| w | + 1) | w^{'} |}{n_{k}} < | w^{'} | \frac{ε}{4}$ occurrences of $w$ not contained entirely

within a concatenated $A_{k}$ -word, this implies that $f r_{i, j} (w, w^{'})$ is at least ( $y$ $- ε$ , and

at most a $+ ε$ . Since for any $ε > 0$ , this statement is true for any long enough word

$w^{'} \in L (X)$ and $0 \underline{<} i < j$ , we see that $\frac{1}{n} \sum_{i = 0}^{n - 1} χ [w] (σ^{i j} y) \to$ a uniformly for $y \in X$ .

Since $w$ was arbitrary, and since characteristic functions of cylinder sets are dense in

$C (X)$ , $\frac{1}{n} \sum_{i = 0}^{n - 1} f (σ^{i j} y)$ approaches a uniform limit for all $f \in C (X)$ , and so $(X, σ^{j})$

is uniquely ergodic for every $j \in$ N. Since an invariant measure for $(X, σ)$ would be

invariant for any $(X, σ^{j})$ as well, the unique invariant measure is the same for every

$j$ .

Finally, we claim that $(X, σ)$ is also topologically mixing. Consider any words $w$ , $w^{'} \in$

$L (X)$ . By construction, there exists $k$ so that there are $A_{k}$ words $y$ , $y^{'}$ with $w$ a

subword of $y$ and $w^{'}$ a subword of $y^{'}$ . We also claim that for any $\frac{n_{k + 1}}{6} < i < \frac{5 n_{k + 1}}{6}$ , there

exists an $A_{k + 1}$ word $b_{i}$ where $b_{i} (i + 1) b_{i} (i + 2)$ . . . $b_{i} (i + n_{k}) = y$ , and similarly $b_{i}^{'} \in A_{k + 1}$

with $b_{i}^{'} (i + 1) b_{i}^{'} (i + 2)$ . . . $b_{i}^{'} (i + n_{k}) = y^{'}$ . We show only the existence of $b_{i}$ , as the proof for

$b_{i}^{'}$ is trivially similar. Consider any $\frac{n_{k + 1}}{6} < i < \frac{5 n_{k + 1}}{6}$ , and take $j = i$ (mod $n_{k}$ ). Then,

if we enumerate the elements of $A_{k}$ by $a_{1}$ , $a_{2}$ , $...$ , $a | A_{k} |$ , first define the word $u_{k + 1} =$

$a_{1}^{k!} a_{2}^{k!} ...$ $a_{| A_{k} |}^{k!}$ , and then define the word $y_{i} = (u_{k + 1} 1)^{j} (u_{k + 1})^{C_{k} (k + 1) - p} (u_{k + 1} 1)^{p - j}$ . $y_{i}$

has the property that $y_{i} (i + 1) y_{i} (i + 2)$ . . . $y_{i} (i + n_{k})$ is a concatenated $A_{k}$ -word in $y_{i}$ as

long as $y_{i} (i + 1) y_{i} (i + 2)$ . . . $y_{i} (i + n_{k})$ lies in the subword $(u_{k + 1})^{C_{k} (k + 1) - p}$ of $y_{i}$ , which is

true for large $k$ and $i \in (\frac{n_{k + 1}}{6}, \frac{5 n_{k + 1}}{6})$ . This means that if we reorder $a_{1}$ , $...$ , $a_{| A_{k} |}$ in the

definition of $u_{k + 1}$ , we may create a word $b_{i}$ where $b_{i} (i + 1) b_{i} (i + 2)$ . . . $b_{i} (i + n_{k}) = y$ .

$b_{i} \in A_{k + 1}$ , since for every $0 \underline{<} i < k!$ and $x \in A_{k}$ , $x$ appears exactly $C (k + 1)$

times in $b_{i}$ as a concatenated $A_{k}$ -word at $i$ (mod $k!$ )-indexed places, implying that

$f r_{i, k!}^{*} (x, b_{i}) = \frac{1}{| A_{k} | n_{k} k!}$ (This uses the fact that ( $n_{k}$ , $k!) = 1$ , which was already shown.)

We create $b_{i}^{'}$ in the same way for each $i$ . Since $w$ is a subword of $y$ and $w^{'}$ is a subword

of $y^{'}$ , for every $\frac{n_{k + 1}}{6} + n_{k} \underline{<} i \underline{<} \frac{5 n_{k + 1}}{6} - n_{k}$ , it is easy to choose a word $z_{i}$ to be $b_{j}$

for properly chosen $j$ so that $z_{i} (i + 1)$ . . . $z_{i} (i + | w |) = w$ , and similarly $z_{i}^{'}$ so that

$z_{i}^{'} (i + 1)$ . . . $z_{i}^{'} (i + | w^{'} |) = w^{'}$ . For large $k$ , this means that we can construct such $z_{i}$

and $z_{i}^{'}$ for any $i \in [\frac{n_{k + 1}}{5}, \frac{4 n_{k + 1}}{5}]$ .

We will now use these $z_{i}$ and $z_{i}^{'}$ to prove that for any $n > | w | + n_{k + 1}$ , there exists a

word $x \in L (X)$ of length $n$ such that rvxrv' $\in L (X)$ . We do this by proving a lemma:

Lemma 2.2.8. For any t $> k + 1$ , and for any $0 \underline{<} i$ , j $< n_{t}$ such that there exists an

$A_{t}$ word x where $x (i + 1) x (i + 2)$ . . . $x (i + n_{k + 1})$ and $x (j + 1) x (j + 2)$ . . . $x (j + n_{k + 1})$ are

concatenated $A_{k + 1}$ -rvords in x, and for any trvo $A_{k + 1}$ words z and $z^{'}$ , there exists an

$A_{t}$ word $x^{'}$ where $x^{'} (i + 1) x^{'} (i + 2) ...$ $x^{'} (i + n_{k + 1}) = z$ and $x^{'} (j + 1) x^{'} (j + 2)$ . . . $x^{'} (j +$

$n_{k + 1}) = z^{'}$ .

Proof: We prove this by induction. First we prove the base case $t = k + 2$ ; take an

$A_{k + 2}$ word $x$ where $x (i + 1) x (i + 2)$ . . . $x (i + n_{k + 1})$ and $x (j + 1) x (j + 2)$ . . . $x (j + n_{k + 1})$

are concatenated $A_{k + 1}$ -words in $x$ , call them $a$ and $b$ respectively. Since $x$ is an $A_{k + 2^{-}}$

word, there exists an occurrence of $z$ at an ( $i$ (mod $(k + 1)$ !)) (mod $(k + 1)$ $!$ )-indexed

place, i.e. there exists $i^{'} \equiv i$ (mod (A +1)!) such that $x (i^{'} + 1) x (i^{'} + 2)$ . . . $x (i^{'} +$

$n_{k + 1}) = z$ . Similarly, there exists $j^{'} \equiv j$ (mod (A +1)!) such that $x (j^{'} + 1) x (j^{'} +$

2) . . . $x (j^{'} + n_{k + 1}) = z^{'}$ . We now create $x^{'}$ by leaving almost all of $x$ alone, but defining

$x^{'} (i + 1)$ . . . $x^{'} (i + n_{k + 1}) = z$ , $x^{'} (j + 1)$ . . . $x^{'} (j + n_{k + 1}) = z^{'}$ , $x^{'} (i^{'} + 1)$ . . . $x^{'} (i^{'} + n_{k + 1}) = a$ ,

and $x^{'} (j^{'} + 1)$ . . . $x^{'} (j^{'} + n_{k + 1}) = b$ . This new word $x^{'}$ is still a concatenation of $A_{k + 1^{-}}$

words and ones, and since we switched two pairs of $A_{k + 1}$ -words which occurred at

indices with the same residue class modulo $(k + 1)!$ , $f r_{i, (k + 1)!}^{*} (w, x) = f r_{i, (k + 1)!}^{*} (w, x^{'})$

for all $0 \underline{<} i < (k + 1)!$ and $w \in A_{k + 1}$ . Therefore, $x^{'}$ is an $A_{k + 2}$ -word, with $z$ and $z^{'}$

occurring at the proper places, completing our proof of the base case.

Now, let us assume that the inductive hypothesis is true for a certain value of $t$ ,

and prove it for $t + 1$ . Consider an $A_{t + 1}$ word $x$ where $x (i + 1)$ . . . $x (i + n_{k + 1})$ and

$x (j + 1)$ . . . $x (j + n_{k + 1})$ are concatenated $A_{k + 1}$ -words in x, call them a and b. Call

the concatenated $A_{t}$ -word that $x (i + 1)$ $...$ $x (i + n_{k + 1})$ is a subword of $a^{'}$ , and denote

by $b^{'}$ the corresponding $A_{t}$ -word for $x (j + 1)$ . . . $x (j + n_{k + 1})$ $b^{'}$ . From now on, when

we speak of these words $a$ , $b$ , $a^{'}$ , $b^{'}$ , we are talking about the pertinent occurrences at

the places within $x$ already described. There are two cases; either $a^{'}$ and $b^{'}$ are the

same; i.e. the same $A_{t}$ -word in $x$ , occurring at the same place, or they are not. If $a^{'}$

and $b^{'}$ do occur at the same place, then by the inductive hypothesis, there exists an

$A_{t}$ -word $c$ with an occurrence of $z$ at the same place as $a$ occurs in $a^{'} = b^{'}$ , and an

occurrence of $z^{'}$ at the same place as $b$ occurs in $a^{'} = b^{'}$ . If we can replace $a^{'} = b^{'}$

by $c$ in $x$ , then we will be done. If $a^{'}$ and $b^{'}$ do not occur at the same place, then

since $a$ is a concatenated $A_{k + 1}$ -word in $a^{'}$ , by the inductive hypothesis there exists

an $A_{t}$ -word $a^{'}$ such that $a^{'}$ has $z$ occurring at the same place where $a$ occurs in $a^{'}$ .

Similarly, there exists an $A_{t}$ -word $b^{'}$ such that $b^{'}$ has an occurrence of $z^{'}$ at the same

place where $b$ occurs in $b^{'}$ . If we replace $a^{'}$ by $a^{'}$ and $b^{'}$ by $b^{'}$ in $x$ , then we will be

done. So regardless of which case we are in, our goal is to replace one or two chosen

$A_{t}$ -words within $x$ with one or two other $A_{t}$ -words. We will show how to replace

two, which clearly implies that replacing one is possible. We wish to replace $a^{'}$ by

$a^{'}$ and $b^{'}$ by $b^{'}$ . We do this in exactly the same way as in the base case; say that

$a^{'} = x (i^{'} + 1)$ . . . $x (i^{'} + n_{t})$ and $b^{'} = x (j^{'} + 1)$ . . . $x (j^{'} + n_{t})$ . Since $a^{'} \in A_{t}$ , there

exists $i^{'} = i^{'}$ (mod $t!$ ) and $j^{'} = j^{'}$ (mod $t!$ ) such that $x (i^{'} + 1)$ . . . $x (i^{'} + n_{t}) = a^{'}$

and $x (j^{'} + 1)$ . . . $x (j^{'} + n_{t}) = b^{'}$ . As in the base case, we create $x^{'}$ by making

$x^{'} (i^{'} + 1)$ . . . $x^{'} (i^{'} + n_{t}) = a^{'}$ and $x^{'} (i^{'} + 1)$ . . . $x^{'} (i^{'} + n_{t}) = a^{'}$ , $x^{'} (j^{'} + 1)$ . . . $x^{'} (j^{'} + n_{t}) = b^{'}$ ,

and $x^{'} (j^{'} + 1)$ . . . $x^{'} (j^{'} + n_{t}) = b^{'}$ . Then $x^{'}$ is an $A_{t + 1^{-}}$ word, and by construction

$x^{'} (i + 1)$ . . . $x^{'} (i + n_{k + 1}) = z$ and $x^{'} (j + 1)$ . . . $x^{'} (j + n_{k + 1}) = z^{'}$ .

$□$

Choose any sequence ${v_{m}}$ of $A_{m}$ -words for all $m > k + 1$ . For any such $m$ , take

$P_{m} =$ { $n$ : $v_{m} (n + 1)$ $...$ $v_{m} (n + n_{k + 1})$ is a concatenated $A_{k + 1}$ word in $v_{m}$ }. Since

$v_{m}$ is a concatenation of $A_{k + 1}$ -words and ones, if we write the elements of $P_{m}$ as

$p_{1}^{(m)} < p_{2}^{(m)} < ... < p_{t}^{(m)}$ , then for any $1 \underline{<} l$ $< t$ , $p_{l + 1}^{(m)} - p_{l}^{(m)} \underline{<}$ a $k + 1 + 1$ . For any

$1 < l$ $< t$ , and $i$ , $j \in [\frac{n_{k + 1}}{5}, \frac{4 n_{k + 1}}{5}]$ , by Lemma 2.2.8, there exists an $A_{m}$ word $v$ with the

property that $v (p_{1}^{(m)} + 1)$ $...$ $v (p_{1}^{(m)} + n_{k + 1}) = z_{i}$ and $v (p_{l}^{(m)} + 1)$ $...$ $v (p_{l}^{(m)} + n_{k + 1}) = z_{j}^{'}$ .

This implies that there is a subword of $v$ of the form rvxrv' where the length of $x$ is

$p_{l}^{(m)} - p_{1}^{(m)} + (j - i) - | w |$ . We note that $j - i$ can take any integer value between $- \frac{3 n_{k + 1}}{5}$

and $\frac{3 n_{k + 1}}{5}$ inclusive. Therefore, the set of possible lengths of $x$ for which rvxrv' $\in L (X)$

contains

$l = 2 \cup^{t} {(| w | + p_{l}^{(m)} - p_{1}^{(m)} + [- \frac{3 n_{k + 1}}{5}, \frac{3 n_{k + 1}}{5}])}$ .

When $l$ is increased by one, $p_{l}^{(m)}$ is increased by at most $n_{k + 1} + 1$ . This, along with

the fact that the intervals $[- \frac{3 n_{k + 1}}{5}, \frac{3 n_{k + 1}}{5}]$ have length $\frac{6 n_{k + 1}}{5}$ , which for large $k$ exceeds

$n_{k + 1} + 1$ , implies that this set of possible lengths of $v$ contains [ $| w | + p_{2}^{(m)} - p_{1}^{(m)}$ -

$\frac{3 n_{k + 1}}{5}$ , $| w | + p_{t}^{(m)} - p_{1}^{(m)} + \frac{3 n_{k + 1}}{5}] \underline{\supset} [| w | + n_{k + 1}, | w | + n_{m} - 2 n_{k + 1}]$ . Since this entire

argument could be made for any $m$ , we see that for any $n > | w | + n_{k + 1}$ , there exists

$x \in L (X)$ of length $n$ so that rvxrv' $\in L (X)$ . Then, for any nonempty open sets

$U$ , $V \underline{\subset} X$ , there exist $w$ and $w^{'}$ such that $[w] \underline{\subset} U$ and $[w^{'}] \underline{\subset} V$ . By the above

arguments, there exists $N$ so that for any $n > N$ , $[w] \cap σ^{n} [w^{'}] \neq \emptyset$ , implying that

$U \cap σ^{n} V \neq \emptyset$ . This shows that $(X, σ)$ is topologically mixing.

$□$

2.3 Some symbolic counterexamples

Proof of Theorem 2.1.15: We take the continuous function $f (y) = y (0)$ for all

$y \in X$ , and first note that

${y \in X$ : $\frac{1}{N} \sum_{n = 0}^{N - 1} f (σ^{p_{n}} y)$ does not $c o n v e r g e}$

$\underline{\supset}$ $(\cap \cup n > 0 k > n {y \in X$ : $f r_{0, 1}$ $(0, y (p_{1}) y (p_{2})$ . . . $y (p_{k})) < \frac{1}{4}}) \cap$

$(\cap \cup n > 0 k > n {y \in X$ : $f r_{0, 1} (0, y (p_{1}) y (p_{2}) ... y (p_{k})) > \frac{3}{4}}$ ),

and that the latter set, call it $B$ , is clearly a $G_{δ}$ . We will choose $n_{k}$ so that $B$ is dense

in $X$ . This will imply that $B$ is a dense $G_{δ}$ , and since $X$ is a complete metric space,

by the Baire category theorem, that $B$ is residual, which will prove Theorem 2.1.15.

Now let us describe the construction of ${n_{k}}$ .

Recall that we have assumed that the sequence ${p_{n}}$ has upper Banach density zero.

We define $A : = {p_{n} : n \in N}$ . We also define the intervals of integers $B_{j} =$

$[2 j!, (j + 1)!] \cap N$ for every $j \in N$ , and take any partition of $N$ into infinitely many

disjoint infinite sets in $N$ , call them $C_{1}$ , $C_{2}$ , . . .. Define the set $D_{1} = \cup_{j \in C_{1}} B_{j}$ , and

then define the set $A_{1} = {p_{n} : n \in D_{1}} + 1$ . Next, choose some $r_{2}$ large enough so that

$(\min C_{r_{2}})! > 2 ċ 2$ , and define $D_{2} = \cup_{j \in C_{r_{2}}} B_{j}$ , and then define $A_{2} = {p_{n} : n \in D_{2}} + 2$ .

Continuing in this way, we may inductively define $A_{k}$ , $D_{k}$ for all $k \in N$ so that for

1ll $k$ , $D_{k} = \cup_{j \in C_{r_{k}}} B_{j}$ for some $r_{k}$ with the property that $(\min C_{r_{k}})!$ $> 2 k$ , and

$A_{k} = {p_{n} : n \in D_{k}} + k$ . We will verify some properties of these sets. Most

importantly, we denote by $H$ the union $\cup_{n = 1}^{\infty} A_{n}$ , and claim that $d^{*} (H) = 0$ . We

show this by noting that $H$ has a certain structure; $H$ consists of shifted subintervals

of $A$ , separated by gaps which approach infinity. More rigorously:

Lemma 2.3.1. There exist intervals $I_{k} = [a_{k}, b_{k}] \cap N$ and integers $j_{k}$ such that

$H = \cup_{k = 1}^{\infty} ((A \cap I_{k}) + j_{k})$ and such that $\lim_{k \to \infty} (\min ((A \cap I_{k + 1}) + j_{k + 1}) - \max ((A \cap$

$I_{k}) + j_{k})) = \infty$ .

Proof: Take the set $Q = \cup_{k = 1}^{\infty} C_{r_{k}}$ , and denote its members by $q_{1} < q_{2} <$ . . ..

Then, for any $k$ , $B_{q k}$ is a subset of some $D_{s}$ . The interval $I_{k}$ is then defined to be

$[p_{2 (q_{k})!}, p_{(q_{k} + 1)!)}]$ , (which means $a_{k} = p_{2 (q_{k})!}$ and $b_{k} = p_{q_{k} (q_{k})!}$ ) and $j_{k}$ is defined to be $s$ .

It is just a rewriting of the definition of the $A_{k}$ that $H = \cup_{k = 1}^{\infty} ((A \cap I_{k}) + j_{k})$ with

these notations. All that must be checked is that $\lim_{k \to \infty} (\min ((A \cap I_{k + 1}) + j_{k + 1}) -$

$\max ((A \cap I_{k}) + j_{k})) = \infty$ . We will show that $a_{k + 1} + j_{k + 1} - b_{k} - j_{k} \to \infty$ , which

implies the desired result. Since $q_{k + 1} > q_{k}$ , $a_{k + 1} - b_{k} = (q_{k + 1})! > (q_{k})!$ . So, we must

simply show that $(q_{k})! - j_{k} \to \infty$ . Suppose that $B_{q k}$ is a subset of $D_{s}$ . Then $j_{k} = s$ .

We also note that by construction, $(\min C_{r_{s}})! > 2 s$ . But, since $B_{q k} \subset D_{s}$ , $q_{k} \in C_{r_{s}}$ ,

and so $\min C_{r_{s}} \underline{<} q_{k}$ . Therefore, $(q_{k})! > 2 s$ , and so $(q_{k})! - j_{k} = (q_{k})! - s > \frac{(q_{k})!}{2}$ , which

clearly shows that this quantity approaches $\infty$ , since ${q_{k}}$ is an increasing sequence

of integers.

$□$

We now prove a general lemma that implies, in particular, that $d^{*} (H) = 0$ .

Lemma 2.3.2. If $d^{*} (A) = 0$ , and if there exist intervals $I_{k} = [a_{k}, b_{k}] \cap N$ and integers

$j_{k}$ such that $\lim_{k \to \infty}$ ( $\min$ $((A \cap I_{k + 1}) + j_{k + 1}) - \max ((A \cap I_{k}) + j_{k})) = \infty$ , then the

set $B = \cup_{k = 1}^{\infty} (A \cap I_{k}) + j_{k}$ has upper Banach density zero.

Proof: Fix $ε > 0$ . By the fact that $d^{*} (A) = 0$ , there exists $N$ such that for any interval

$J$ of integers of length at least $N$ , $\frac{| A \cap J |}{| J |} < ε$ . Take $J$ to be any interval of integers of

length exactly $N$ . Since $\lim_{k \to \infty} (\min ((A \cap I_{k + 1}) + j_{k + 1}) - \max ((A \cap I_{k}) + j_{k})) = \infty$ ,

there is some $K$ such that if $J$ has nonempty intersection with $(A \cap I_{k}) + j_{k}$ for some

$k > K$ , it is disjoint from $(A \cap I_{k^{'}}) + j_{k^{'}}$ for every $k^{'} \neq k$ . Therefore, for intervals

$J$ of integers of length $N$ with large enough minimum element, $J \cap B$ consists of a

subset of a shifted copy of $J \cap A$ , and so $\frac{| B \cap J |}{| J |} \underline{<} \frac{| A \cap J^{'} |}{| J |}$ , for some interval $J^{'}$ of integers

whose length is also $N$ . This means that in this case, $\frac{| B \cap J |}{| J |} < ε$ . We have then shown

that for every $ε$ , there exist $N$ , $M$ such that for any interval of integers $J$ of length

$N$ with $\min J > M$ , $\frac{| B \cap J |}{| J |} < ε$ . We will show that this slightly modified definition

still implies that $d^{*} (B) = 0$ . Again fix $ε > 0$ , and define $M$ and $N$ as was just done.

Now consider any interval of integers I with length at least $\frac{N + M}{ε}$ . Then, partition $I$

into subintervals: define $I_{0} = I$ $\cap {1, ..., M}$ , and then break $I ∖ I_{0}$ into consecutive

subintervals of length $N$ , called $I_{1}$ , $I_{2}$ , $...$ , $I_{k}$ . There may be one last subinterval left

over of length less than $N$ ; call it $I_{k + 1}$ (which may be empty.) Note that $| I | \underline{>} N k$ ,

or $\frac{N}{| I |} \underline{<} \frac{1}{k}$ . We see that

$\frac{| B \cap I |}{| I |} = \frac{| B \cap I_{0} |}{| I |} + \sum_{i = 1}^{k} \frac{| B \cap I_{i} |}{| I |} + \frac{| B \cap I_{k + 1} |}{| I |} \underline{<} \frac{M}{| I |} + \frac{N}{| I |} (\sum_{i = 1}^{k} \frac{| B \cap I_{i} |}{| I_{i} |}) + \frac{N}{| I |}$

$\underline{<} \frac{M + N}{| I |} + \frac{1}{k} (k ε) < 2 ε$ .

Since $ε$ was arbitrary, $d^{*} (B) = 0$ .

$□$

By combining Lemmas 2.3.1 and 2.3.2, $d^{*} (H) = 0$ . We will now create $X$ . We note

that this part of our construction uses only the fact that $d^{*} (H) = 0$ , and no other

properties. We take $n_{1} = 1$ and $A_{1} = {0, 1}$ . We recall that ${n_{k}}$ must be a sequence

of integers with the following properties: for all $k > 1$ , $n_{k + 1} = C_{k} (k + 1)! | A_{k} | n_{k} + p$

for some positive integer $C_{k} > n_{k} > \frac{1}{d_{k}}$ and prime $n_{k} < p \underline{<} 2 n_{k}$ . We also require $n_{k}$

to grow quickly enough so that for all $k$ , and for any interval of integers I of length

at least $n_{k + 1}$ , $\frac{| I \cap H |}{| I |} < \frac{d_{k}}{2 k! | A_{k} | n_{k}}$ . That we may choose such $n_{k}$ is a consequence of the

fact that $d^{*} (H) = 0$ . Using these $n_{k}$ , we define $A_{k}$ as in Construction 3. We now

prove a lemma:

Lemma 2.3.3. For any k $\in N$ , m $\in Z$ , and for any u $\in$ {0, $1}^{N}$ , there exists an

$A_{k}$ -rvord $v_{u, k, m}$ such that $v_{u, k, m} (i$ -m) $= u (i)$ for all i $\in H \cap [m + 1, m + n_{k}]$ .

Proof: This is proved by induction on $k$ . Clearly the hypothesis is true for $k = 1$

and for any $u$ , $m$ . Now suppose it to be true for a particular $k$ . We will show

that it is true for $k + 1$ and every $u$ , $m$ . We again construct an auxiliary word

$u_{k + 1}$ : enumerate the elements of $A_{k}$ by $a_{1}$ , $a_{2}$ , $...$ , $a_{| A_{k} |}$ . Then, we again define the

word $u_{k + 1} = a_{1}^{k!} a_{2}^{k!} ...$ $a_{| A_{k} |}^{k!}$ . Define $v_{k + 1}^{'} =$ $(u_{k + 1} 1) p (u_{k + 1})^{C_{k} (k + 1) - p}$ , where $n_{k + 1} =$

$C_{k} (k + 1)! | A_{k} | n_{k} + p$ as above. We note that for any $0 \underline{<} i < k!$ and $w \in A_{k}$ ,

$w$ occurs exactly $C_{k} (k + 1)$ times as a concatenated $A_{k}$ -word at $i$ (mod $k!$ )-indexed

places in $v_{k + 1}^{'}$ . (This uses the fact that $(n_{k}, k!) = 1$ for all $k$ , which has already

been shown.) Now, fix $m \in Z$ . We wish to construct an $A_{k + 1}$ word $v_{u, k + 1, m}$ such

that $v_{u, k + 1, m} (i - m) = u (i)$ for all $i \in H \cap$ [ $m + 1$ , $m +$ a $k + 1$ ]. We begin with the

$A_{k + 1}$ word $v_{k + 1}^{'}$ . Clearly it is not necessarily true that $v_{k + 1}^{'} (i - m)$ $= u (i)$ for all

$i \in H \cap [m + 1, m + n_{k + 1}]$ . We force this condition to be true by changing some of the

$A_{k}$ -words concatenated in $v_{k + 1}^{'}$ . We show that this is possible; for any concatenated

$A_{k^{-}}$ word in $v_{k + 1}^{'}$ , say $v_{k + 1}^{'} (j) v_{k + 1}^{'} (j + 1)$ $...$ $v_{k + 1}^{'} (j + n_{k} - 1)$ , the necessary condition is

that ones or zeroes (depending on $u$ ) be introduced at digits whose indices are of the

form $i - m$ for all $i \in H \cap$ [ $m + j + 1$ , $...$ , a $+ j + n_{k} - 1$ ]. To do this, we replace this $A_{k^{-}}$

word by $v_{u, k, m + j}$ , which by the inductive hypothesis has the correct digits of $u$ at the

desired places. So, we may change $v_{k + 1}^{'}$ into a concatenation of $A_{k}$ -words and ones,

call it $v_{u, k + 1, m}$ , which has the proper digits of $u$ in all desired places. This may be done

by changing at most $| H \cap [m + 1, ..., m + n_{k + 1}] | < \frac{d_{k} n_{k + 1}}{2 k! | A_{k} | n_{k}} \underline{<} C_{k} (k + 1) d_{k} A_{k}$ -words.

Therefore, since for any $0 \underline{<} i < k!$ and $w \in A_{k}$ , $w$ occurred in $v_{k + 1}^{'}$ as a concatenated

$A_{k}$ -word at $i$ (mod $k!$ )-indexed places exactly $C_{k} (k + 1)$ times, $w$ occurs in $v_{u, k + 1, m}$ as

a concatenated $A_{k}$ -word at $i$ (mod $k!$ )-indexed places between $C_{k} (k + 1) (1 - d_{k})$ and

$C_{k} (k + 1) (1 + d_{k})$ times. This implies that $f r_{i, k!}^{*} (w, v_{k + 1, m}) \in [\frac{1 - d_{k}}{k! | A_{k} |}, \frac{1 + d_{k}}{k! | A_{k} |}]$ , and since

$i$ and $w$ were arbitrary, that $v_{k + 1, m}$ is an $A_{k + 1}$ -word. By induction, Lemma 2.3.3 is

proved.

$□$

This implies in particular that for every $u$ , $k$ there exists an $A_{k}$ -word $v_{u, k, - n_{k - 1}}$ with

$v_{u, k, n_{k - 1}} (i + n_{k - 1}) = u (i)$ for all $i \in H \cap (- n_{k - 1}$ , $...$ , $n_{k} - n_{k - 1}$ ]. By a standard

diagonalization argument, there exists a sequence ${k_{j}}$ and $x \in Ω$ such that for

all $i \in Z$ , $x (i) = v_{u, k_{j}, - n_{k_{j} - 1}} (i + n_{k_{j} - 1})$ for all large enough $j$ . Since for every $j$ ,

$v_{u, k_{j}, - n_{k_{j} - 1}} (i + n_{k_{j} - 1}) = u (i)$ for all $i \in H \cap (- n_{k_{j} - 1}, n_{k_{j}} - n_{k_{j} - 1}]$ , clearly $x (i) = u (i)$

for all $i \in H$ . Since $x$ is a limit of shifted $A_{k}$ -words, $x \in X$ . As mentioned above,

this entire construction could be done with any set of zero upper Banach density in

place of $H$ , which lets us state the following corollary:

Corollary 2.3.4. For any C $\subset N$ with $d^{*} (C) = 0$ , there exists (X, $σ)$ totally mini-

mal, totally uniquely ergodic, topologically mixing, and with the property that for any

sequence u $\in$ {0, $1}^{N}$ , there exists $x_{u} \in X$ such that $x_{u} (i) = u (i)$