You are currently browsing the tag archive for the ‘ergodic theory’ tag.

Vitaly Bergelson, Tamar Ziegler, and I have just uploaded to the arXiv our joint paper “Multiple recurrence and convergence results associated to ${{\bf F}_{p}^{\omega}}$-actions“. This paper is primarily concerned with limit formulae in the theory of multiple recurrence in ergodic theory. Perhaps the most basic formula of this type is the mean ergodic theorem, which (among other things) asserts that if ${(X,{\mathcal X}, \mu,T)}$ is a measure-preserving ${{\bf Z}}$-system (which, in this post, means that ${(X,{\mathcal X}, \mu)}$ is a probability space and ${T: X \mapsto X}$ is measure-preserving and invertible, thus giving an action ${(T^n)_{n \in {\bf Z}}}$ of the integers), and ${f,g \in L^2(X,{\mathcal X}, \mu)}$ are functions, and ${X}$ is ergodic (which means that ${L^2(X,{\mathcal X}, \mu)}$ contains no ${T}$-invariant functions other than the constants (up to almost everywhere equivalence, of course)), then the average

$\displaystyle \frac{1}{N} \sum_{n=1}^N \int_X f(x) g(T^n x)\ d\mu \ \ \ \ \ (1)$

converges as ${N \rightarrow \infty}$ to the expression

$\displaystyle (\int_X f(x)\ d\mu) (\int_X g(x)\ d\mu);$

see e.g. this previous blog post. Informally, one can interpret this limit formula as an equidistribution result: if ${x}$ is drawn at random from ${X}$ (using the probability measure ${\mu}$), and ${n}$ is drawn at random from ${\{1,\ldots,N\}}$ for some large ${N}$, then the pair ${(x, T^n x)}$ becomes uniformly distributed in the product space ${X \times X}$ (using product measure ${\mu \times \mu}$) in the limit as ${N \rightarrow \infty}$.

If we allow ${(X,\mu)}$ to be non-ergodic, then we still have a limit formula, but it is a bit more complicated. Let ${{\mathcal X}^T}$ be the ${T}$-invariant measurable sets in ${{\mathcal X}}$; the ${{\bf Z}}$-system ${(X, {\mathcal X}^T, \mu, T)}$ can then be viewed as a factor of the original system ${(X, {\mathcal X}, \mu, T)}$, which is equivalent (in the sense of measure-preserving systems) to a trivial system ${(Z_0, {\mathcal Z}_0, \mu_{Z_0}, 1)}$ (known as the invariant factor) in which the shift is trivial. There is then a projection map ${\pi_0: X \rightarrow Z_0}$ to the invariant factor which is a factor map, and the average (1) converges in the limit to the expression

$\displaystyle \int_{Z_0} (\pi_0)_* f(z) (\pi_0)_* g(z)\ d\mu_{Z_0}(x), \ \ \ \ \ (2)$

where ${(\pi_0)_*: L^2(X,{\mathcal X},\mu) \rightarrow L^2(Z_0,{\mathcal Z}_0,\mu_{Z_0})}$ is the pushforward map associated to the map ${\pi_0: X \rightarrow Z_0}$; see e.g. this previous blog post. We can interpret this as an equidistribution result. If ${(x,T^n x)}$ is a pair as before, then we no longer expect complete equidistribution in ${X \times X}$ in the non-ergodic, because there are now non-trivial constraints relating ${x}$ with ${T^n x}$; indeed, for any ${T}$-invariant function ${f: X \rightarrow {\bf C}}$, we have the constraint ${f(x) = f(T^n x)}$; putting all these constraints together we see that ${\pi_0(x) = \pi_0(T^n x)}$ (for almost every ${x}$, at least). The limit (2) can be viewed as an assertion that this constraint ${\pi_0(x) = \pi_0(T^n x)}$ are in some sense the “only” constraints between ${x}$ and ${T^n x}$, and that the pair ${(x,T^n x)}$ is uniformly distributed relative to these constraints.

Limit formulae are known for multiple ergodic averages as well, although the statement becomes more complicated. For instance, consider the expression

$\displaystyle \frac{1}{N} \sum_{n=1}^N \int_X f(x) g(T^n x) h(T^{2n} x)\ d\mu \ \ \ \ \ (3)$

for three functions ${f,g,h \in L^\infty(X, {\mathcal X}, \mu)}$; this is analogous to the combinatorial task of counting length three progressions in various sets. For simplicity we assume the system ${(X,{\mathcal X},\mu,T)}$ to be ergodic. Naively one might expect this limit to then converge to

$\displaystyle (\int_X f\ d\mu) (\int_X g\ d\mu) (\int_X h\ d\mu)$

which would roughly speaking correspond to an assertion that the triplet ${(x,T^n x, T^{2n} x)}$ is asymptotically equidistributed in ${X \times X \times X}$. However, even in the ergodic case there can be additional constraints on this triplet that cannot be seen at the level of the individual pairs ${(x,T^n x)}$, ${(x, T^{2n} x)}$. The key obstruction here is that of eigenfunctions of the shift ${T: X \rightarrow X}$, that is to say non-trivial functions ${f: X \rightarrow S^1}$ that obey the eigenfunction equation ${Tf = \lambda f}$ almost everywhere for some constant (or ${T}$-invariant) ${\lambda}$. Each such eigenfunction generates a constraint

$\displaystyle f(x) \overline{f(T^n x)}^2 f(T^{2n} x) = 1 \ \ \ \ \ (4)$

tying together ${x}$, ${T^n x}$, and ${T^{2n} x}$. However, it turns out that these are in some sense the only constraints on ${x,T^n x, T^{2n} x}$ that are relevant for the limit (3). More precisely, if one sets ${{\mathcal X}_1}$ to be the sub-algebra of ${{\mathcal X}}$ generated by the eigenfunctions of ${T}$, then it turns out that the factor ${(X, {\mathcal X}_1, \mu, T)}$ is isomorphic to a shift system ${(Z_1, {\mathcal Z}_1, \mu_{Z_1}, x \mapsto x+\alpha)}$ known as the Kronecker factor, for some compact abelian group ${Z_1 = (Z_1,+)}$ and some (irrational) shift ${\alpha \in Z_1}$; the factor map ${\pi_1: X \rightarrow Z_1}$ pushes eigenfunctions forward to (affine) characters on ${Z_1}$. It is then known that the limit of (3) is

$\displaystyle \int_\Sigma (\pi_1)_* f(x_0) (\pi_1)_* g(x_1) (\pi_1)_* h(x_2)\ d\mu_\Sigma$

where ${\Sigma \subset Z_1^3}$ is the closed subgroup

$\displaystyle \Sigma = \{ (x_1,x_2,x_3) \in Z_1^3: x_1-2x_2+x_3=0 \}$

and ${\mu_\Sigma}$ is the Haar probability measure on ${\Sigma}$; see this previous blog post. The equation ${x_1-2x_2+x_3=0}$ defining ${\Sigma}$ corresponds to the constraint (4) mentioned earlier. Among other things, this limit formula implies Roth’s theorem, which in the context of ergodic theory is the assertion that the limit (or at least the limit inferior) of (3) is positive when ${f=g=h}$ is non-negative and not identically vanishing.

If one considers a quadruple average

$\displaystyle \frac{1}{N} \sum_{n=1}^N \int_X f(x) g(T^n x) h(T^{2n} x) k(T^{3n} x)\ d\mu \ \ \ \ \ (5)$

(analogous to counting length four progressions) then the situation becomes more complicated still, even in the ergodic case. In addition to the (linear) eigenfunctions that already showed up in the computation of the triple average (3), a new type of constraint also arises from quadratic eigenfunctions ${f: X \rightarrow S^1}$, which obey an eigenfunction equation ${Tf = \lambda f}$ in which ${\lambda}$ is no longer constant, but is now a linear eigenfunction. For such functions, ${f(T^n x)}$ behaves quadratically in ${n}$, and one can compute the existence of a constraint

$\displaystyle f(x) \overline{f(T^n x)}^3 f(T^{2n} x)^3 \overline{f(T^{3n} x)} = 1 \ \ \ \ \ (6)$

between ${x}$, ${T^n x}$, ${T^{2n} x}$, and ${T^{3n} x}$ that is not detected at the triple average level. As it turns out, this is not the only type of constraint relevant for (5); there is a more general class of constraint involving two-step nilsystems which we will not detail here, but see e.g. this previous blog post for more discussion. Nevertheless there is still a similar limit formula to previous examples, involving a special factor ${(Z_2, {\mathcal Z}_2, \mu_{Z_2}, S)}$ which turns out to be an inverse limit of two-step nilsystems; this limit theorem can be extracted from the structural theory in this paper of Host and Kra combined with a limit formula for nilsystems obtained by Lesigne, but will not be reproduced here. The pattern continues to higher averages (and higher step nilsystems); this was first done explicitly by Ziegler, and can also in principle be extracted from the structural theory of Host-Kra combined with nilsystem equidistribution results of Leibman. These sorts of limit formulae can lead to various recurrence results refining Roth’s theorem in various ways; see this paper of Bergelson, Host, and Kra for some examples of this.

The above discussion was concerned with ${{\bf Z}}$-systems, but one can adapt much of the theory to measure-preserving ${G}$-systems for other discrete countable abelian groups ${G}$, in which one now has a family ${(T_g)_{g \in G}}$ of shifts indexed by ${G}$ rather than a single shift, obeying the compatibility relation ${T_{g+h}=T_g T_h}$. The role of the intervals ${\{1,\ldots,N\}}$ in this more general setting is replaced by that of Folner sequences. For arbitrary countable abelian ${G}$, the theory for double averages (1) and triple limits (3) is essentially identical to the ${{\bf Z}}$-system case. But when one turns to quadruple and higher limits, the situation becomes more complicated (and, for arbitrary ${G}$, still not fully understood). However one model case which is now well understood is the finite field case when ${G = {\bf F}_p^\omega = \bigcup_{n=1}^\infty {\bf F}_p^n}$ is an infinite-dimensional vector space over a finite field ${{\bf F}_p}$ (with the finite subspaces ${{\bf F}_p^n}$ then being a good choice for the Folner sequence). Here, the analogue of the structural theory of Host and Kra was worked out by Vitaly, Tamar, and myself in these previous papers (treating the high characteristic and low characteristic cases respectively). In the finite field setting, it turns out that nilsystems no longer appear, and one only needs to deal with linear, quadratic, and higher order eigenfunctions (known collectively as phase polynomials). It is then natural to look for a limit formula that asserts, roughly speaking, that if ${x}$ is drawn at random from a ${{\bf F}_p^\omega}$-system and ${n}$ drawn randomly from a large subspace of ${{\bf F}_p^\omega}$, then the only constraints between ${x, T^n x, \ldots, T^{(p-1)n} x}$ are those that arise from phase polynomials. The main theorem of this paper is to establish this limit formula (which, again, is a little complicated to state explicitly and will not be done here). In particular, we establish for the first time that the limit actually exists (a result which, for ${{\bf Z}}$-systems, was one of the main results of this paper of Host and Kra).

As a consequence, we can recover finite field analogues of most of the results of Bergelson-Host-Kra, though interestingly some of the counterexamples demonstrating sharpness of their results for ${{\bf Z}}$-systems (based on Behrend set constructions) do not seem to be present in the finite field setting (cf. this previous blog post on the cap set problem). In particular, we are able to largely settle the question of when one has a Khintchine-type theorem that asserts that for any measurable set ${A}$ in an ergodic ${{\bf F}_p^\omega}$-system and any ${\epsilon>0}$, one has

$\displaystyle \mu( T_{c_1 n} A \cap \ldots \cap T_{c_k n} A ) > \mu(A)^k - \epsilon$

for a syndetic set of ${n}$, where ${c_1,\ldots,c_k \in {\bf F}_p}$ are distinct residue classes. It turns out that Khintchine-type theorems always hold for ${k=1,2,3}$ (and for ${k=1,2}$ ergodicity is not required), and for ${k=4}$ it holds whenever ${c_1,c_2,c_3,c_4}$ form a parallelogram, but not otherwise (though the counterexample here was such a painful computation that we ended up removing it from the paper, and may end up putting it online somewhere instead), and for larger ${k}$ we could show that the Khintchine property failed for generic choices of ${c_1,\ldots,c_k}$, though the problem of determining exactly the tuples for which the Khintchine property failed looked to be rather messy and we did not completely settle it.

One of the basic objects of study in combinatorics are finite strings ${(a_n)_{n=0}^N}$ or infinite strings ${(a_n)_{n=0}^\infty}$ of symbols ${a_n}$ from some given alphabet ${{\mathcal A}}$, which could be either finite or infinite (but which we shall usually take to be compact). For instance, a set ${A}$ of natural numbers can be identified with the infinite string ${(1_A(n))_{n=0}^\infty}$ of ${0}$s and ${1}$s formed by the indicator of ${A}$, e.g. the even numbers can be identified with the string ${1010101\ldots}$ from the alphabet ${\{0,1\}}$, the multiples of three can be identified with the string ${100100100\ldots}$, and so forth. One can also consider doubly infinite strings ${(a_n)_{n \in {\bf Z}}}$, which among other things can be used to describe arbitrary subsets of integers.

On the other hand, the basic object of study in dynamics (and in related fields, such as ergodic theory) is that of a dynamical system ${(X,T)}$, that is to say a space ${X}$ together with a shift map ${T: X \rightarrow X}$ (which is often assumed to be invertible, although one can certainly study non-invertible dynamical systems as well). One often adds additional structure to this dynamical system, such as topological structure (giving rise topological dynamics), measure-theoretic structure (giving rise to ergodic theory), complex structure (giving rise to complex dynamics), and so forth. A dynamical system gives rise to an action of the natural numbers ${{\bf N}}$ on the space ${X}$ by using the iterates ${T^n: X \rightarrow X}$ of ${T}$ for ${n=0,1,2,\ldots}$; if ${T}$ is invertible, we can extend this action to an action of the integers ${{\bf Z}}$ on the same space. One can certainly also consider dynamical systems whose underlying group (or semi-group) is something other than ${{\bf N}}$ or ${{\bf Z}}$ (e.g. one can consider continuous dynamical systems in which the evolution group is ${{\bf R}}$), but we will restrict attention to the classical situation of ${{\bf N}}$ or ${{\bf Z}}$ actions here.

There is a fundamental correspondence principle connecting the study of strings (or subsets of natural numbers or integers) with the study of dynamical systems. In one direction, given a dynamical system ${(X,T)}$, an observable ${c: X \rightarrow {\mathcal A}}$ taking values in some alphabet ${{\mathcal A}}$, and some initial datum ${x_0 \in X}$, we can first form the forward orbit ${(T^n x_0)_{n=0}^\infty}$ of ${x_0}$, and then observe this orbit using ${c}$ to obtain an infinite string ${(c(T^n x_0))_{n=0}^\infty}$. If the shift ${T}$ in this system is invertible, one can extend this infinite string into a doubly infinite string ${(c(T^n x_0))_{n \in {\bf Z}}}$. Thus we see that every quadruplet ${(X,T,c,x_0)}$ consisting of a dynamical system ${(X,T)}$, an observable ${c}$, and an initial datum ${x_0}$ creates an infinite string.

Example 1 If ${X}$ is the three-element set ${X = {\bf Z}/3{\bf Z}}$ with the shift map ${Tx := x+1}$, ${c: {\bf Z}/3{\bf Z} \rightarrow \{0,1\}}$ is the observable that takes the value ${1}$ at the residue class ${0 \hbox{ mod } 3}$ and zero at the other two classes, and one starts with the initial datum ${x_0 = 0 \hbox{ mod } 3}$, then the observed string ${(c(T^n x_0))_{n=0}^\infty}$ becomes the indicator ${100100100\ldots}$ of the multiples of three.

In the converse direction, every infinite string ${(a_n)_{n=0}^\infty}$ in some alphabet ${{\mathcal A}}$ arises (in a decidedly non-unique fashion) from a quadruple ${(X,T,c,x_0)}$ in the above fashion. This can be easily seen by the following “universal” construction: take ${X}$ to be the set ${X:= {\mathcal A}^{\bf N}}$ of infinite strings ${(b_i)_{n=0}^\infty}$ in the alphabet ${{\mathcal A}}$, let ${T: X \rightarrow X}$ be the shift map

$\displaystyle T(b_i)_{n=0}^\infty := (b_{i+1})_{n=0}^\infty,$

let ${c: X \rightarrow {\mathcal A}}$ be the observable

$\displaystyle c((b_i)_{n=0}^\infty) := b_0,$

and let ${x_0 \in X}$ be the initial point

$\displaystyle x_0 := (a_i)_{n=0}^\infty.$

Then one easily sees that the observed string ${(c(T^n x_0))_{n=0}^\infty}$ is nothing more than the original string ${(a_n)_{n=0}^\infty}$. Note also that this construction can easily be adapted to doubly infinite strings by using ${{\mathcal A}^{\bf Z}}$ instead of ${{\mathcal A}^{\bf N}}$, at which point the shift map ${T}$ now becomes invertible. An important variant of this construction also attaches an invariant probability measure to ${X}$ that is associated to the limiting density of various sets associated to the string ${(a_i)_{n=0}^\infty}$, and leads to the Furstenberg correspondence principle, discussed for instance in these previous blog posts. Such principles allow one to rigorously pass back and forth between the combinatorics of strings and the dynamics of systems; for instance, Furstenberg famously used his correspondence principle to demonstrate the equivalence of Szemerédi’s theorem on arithmetic progressions with what is now known as the Furstenberg multiple recurrence theorem in ergodic theory.

In the case when the alphabet ${{\mathcal A}}$ is the binary alphabet ${\{0,1\}}$, and (for technical reasons related to the infamous non-injectivity ${0.999\ldots = 1.00\ldots}$ of the decimal representation system) the string ${(a_n)_{n=0}^\infty}$ does not end with an infinite string of ${1}$s, then one can reformulate the above universal construction by taking ${X}$ to be the interval ${[0,1)}$, ${T}$ to be the doubling map ${Tx := 2x \hbox{ mod } 1}$, ${c: X \rightarrow \{0,1\}}$ to be the observable that takes the value ${1}$ on ${[1/2,1)}$ and ${0}$ on ${[0,1/2)}$ (that is, ${c(x)}$ is the first binary digit of ${x}$), and ${x_0}$ is the real number ${x_0 := \sum_{n=0}^\infty a_n 2^{-n-1}}$ (that is, ${x_0 = 0.a_0a_1\ldots}$ in binary).

The above universal construction is very easy to describe, and is well suited for “generic” strings ${(a_n)_{n=0}^\infty}$ that have no further obvious structure to them, but it often leads to dynamical systems that are much larger and more complicated than is actually needed to produce the desired string ${(a_n)_{n=0}^\infty}$, and also often obscures some of the key dynamical features associated to that sequence. For instance, to generate the indicator ${100100100\ldots}$ of the multiples of three that were mentioned previously, the above universal construction requires an uncountable space ${X}$ and a dynamics which does not obviously reflect the key features of the sequence such as its periodicity. (Using the unit interval model, the dynamics arise from the orbit of ${2/7}$ under the doubling map, which is a rather artificial way to describe the indicator function of the multiples of three.)

A related aesthetic objection to the universal construction is that of the four components ${X,T,c,x_0}$ of the quadruplet ${(X,T,c,x_0)}$ used to generate the sequence ${(a_n)_{n=0}^\infty}$, three of the components ${X,T,c}$ are completely universal (in that they do not depend at all on the sequence ${(a_n)_{n=0}^\infty}$), leaving only the initial datum ${x_0}$ to carry all the distinctive features of the original sequence. While there is nothing wrong with this mathematically, from a conceptual point of view it would make sense to make all four components of the quadruplet to be adapted to the sequence, in order to take advantage of the accumulated intuition about various special dynamical systems (and special observables), not just special initial data.

One step in this direction can be made by restricting ${X}$ to the orbit ${\{ T^n x_0: n \in {\bf N} \}}$ of the initial datum ${x_0}$ (actually for technical reasons it is better to restrict to the topological closure ${\overline{\{ T^n x_0: n \in {\bf N} \}}}$ of this orbit, in order to keep ${X}$ compact). For instance, starting with the sequence ${100100100\ldots}$, the orbit now consists of just three points ${100100100\ldots}$, ${010010010\ldots}$, ${001001001\ldots}$, bringing the system more in line with the example in Example 1. Technically, this is the “optimal” representation of the sequence by a quadruplet ${(X,T,c,x_0)}$, because any other such representation ${(X',T',c',x'_0)}$ is a factor of this representation (in the sense that there is a unique map ${\pi: X \rightarrow X'}$ with ${T' \circ \pi = \pi \circ T}$, ${c' \circ \pi = c}$, and ${x'_0 = \pi(x_0)}$). However, from a conceptual point of view this representation is still somewhat unsatisfactory, given that the elements of the system ${X}$ are interpreted as infinite strings rather than elements of a more geometrically or algebraically rich object (e.g. points in a circle, torus, or other homogeneous space).

For general sequences ${(a_n)_{n=0}^\infty}$, locating relevant geometric or algebraic structure in a dynamical system generating that sequence is an important but very difficult task (see e.g. this paper of Host and Kra, which is more or less devoted to precisely this task in the context of working out what component of a dynamical system controls the multiple recurrence behaviour of that system). However, for specific examples of sequences ${(a_n)_{n=0}^\infty}$, one can use an informal procedure of educated guesswork in order to produce a more natural-looking quadruple ${(X,T,c,x_0)}$ that generates that sequence. This is not a particularly difficult or deep operation, but I found it very helpful in internalising the intuition behind the correspondence principle. Being non-rigorous, this procedure does not seem to be emphasised in most presentations of the correspondence principle, so I thought I would describe it here.

Two weeks ago I was at Oberwolfach, for the Arbeitsgemeinschaft in Ergodic Theory and Combinatorial Number Theory that I was one of the organisers for. At this workshop, I learned the details of a very nice recent convergence result of Miguel Walsh (who, incidentally, is an informal grandstudent of mine, as his advisor, Roman Sasyk, was my informal student), which considerably strengthens and generalises a number of previous convergence results in ergodic theory (including one of my own), with a remarkably simple proof. Walsh’s argument is phrased in a finitary language (somewhat similar, in fact, to the approach used in my paper mentioned previously), and (among other things) relies on the concept of metastability of sequences, a variant of the notion of convergence which is useful in situations in which one does not expect a uniform convergence rate; see this previous blog post for some discussion of metastability. When interpreted in a finitary setting, this concept requires a fair amount of “epsilon management” to manipulate; also, Walsh’s argument uses some other epsilon-intensive finitary arguments, such as a decomposition lemma of Gowers based on the Hahn-Banach theorem. As such, I was tempted to try to rewrite Walsh’s argument in the language of nonstandard analysis to see the extent to which these sorts of issues could be managed. As it turns out, the argument gets cleaned up rather nicely, with the notion of metastability being replaced with the simpler notion of external Cauchy convergence (which we will define below the fold).

Let’s first state Walsh’s theorem. This theorem is a norm convergence theorem in ergodic theory, and can be viewed as a substantial generalisation of one of the most fundamental theorems of this type, namely the mean ergodic theorem:

Theorem 1 (Mean ergodic theorem) Let ${(X,\mu,T)}$ be a measure-preserving system (a probability space ${(X,\mu)}$ with an invertible measure-preserving transformation ${T}$). Then for any ${f \in L^2(X,\mu)}$, the averages ${\frac{1}{N} \sum_{n=1}^N T^n f}$ converge in ${L^2(X,\mu)}$ norm as ${N \rightarrow \infty}$, where ${T^n f(x) := f(T^{-n} x)}$.

In this post, all functions in ${L^2(X,\mu)}$ and similar spaces will be taken to be real instead of complex-valued for simplicity, though the extension to the complex setting is routine.

Actually, we have a precise description of the limit of these averages, namely the orthogonal projection of ${f}$ to the ${T}$-invariant factors. (See for instance my lecture notes on this theorem.) While this theorem ostensibly involves measure theory, it can be abstracted to the more general setting of unitary operators on a Hilbert space:

Theorem 2 (von Neumann mean ergodic theorem) Let ${H}$ be a Hilbert space, and let ${U: H \rightarrow H}$ be a unitary operator on ${H}$. Then for any ${f \in H}$, the averages ${\frac{1}{N} \sum_{n=1}^N U^n f}$ converge strongly in ${H}$ as ${N \rightarrow \infty}$.

Again, see my lecture notes (or just about any text in ergodic theory) for a proof.

Now we turn to Walsh’s theorem.

Theorem 3 (Walsh’s convergence theorem) Let ${(X,\mu)}$ be a measure space with a measure-preserving action of a nilpotent group ${G}$. Let ${g_1,\ldots,g_k: {\bf Z} \rightarrow G}$ be polynomial sequences in ${G}$ (i.e. each ${g_i}$ takes the form ${g_i(n) = a_{i,1}^{p_{i,1}(n)} \ldots a_{i,j}^{p_{i,j}(n)}}$ for some ${a_{i,1},\ldots,a_{i,j} \in G}$ and polynomials ${p_{i,1},\ldots,p_{i,j}: {\bf Z} \rightarrow {\bf Z}}$). Then for any ${f_1,\ldots,f_k \in L^\infty(X,\mu)}$, the averages ${\frac{1}{N} \sum_{n=1}^N (g_1(n) f_1) \ldots (g_k(n) f_k)}$ converge in ${L^2(X,\mu)}$ norm as ${N \rightarrow \infty}$, where ${g(n) f(x) := f(g(n)^{-1} x)}$.

It turns out that this theorem can also be abstracted to some extent, although due to the multiplication in the summand ${(g_1(n) f_1) \ldots (g_k(n) f_k)}$, one cannot work purely with Hilbert spaces as in the von Neumann mean ergodic theorem, but must also work with something like the Banach algebra ${L^\infty(X,\mu)}$. There are a number of ways to formulate this abstraction (which will be of some minor convenience to us, as it will allow us to reduce the need to invoke the nonstandard measure theory of Loeb, discussed for instance in this blog post); we will use the notion of a (real) commutative probability space ${({\mathcal A},\tau)}$, which for us will be a commutative unital algebra ${{\mathcal A}}$ over the reals together with a linear functional ${\tau: {\mathcal A} \rightarrow {\bf R}}$ which maps ${1}$ to ${1}$ and obeys the non-negativity axiom ${\tau(f^2) \ge 0}$ for all ${f}$. The key example to keep in mind here is ${{\mathcal A} = L^\infty(X,\mu)}$ of essentially bounded real-valued measurable functions with the supremum norm, and with the trace ${\tau(f) := \int_X f\ d\mu}$. We will also assume in our definition of commutative probability spaces that all elements ${f}$ of ${{\mathcal A}}$ are bounded in the sense that the spectral radius ${\rho(f) := \lim_{k \rightarrow \infty} \tau(f^{2k})^{1/2k}}$ is finite. (In the concrete case of ${L^\infty(X,\mu)}$, the spectral radius is just the ${L^\infty}$ norm.)

Given a commutative probability space, we can form an inner product ${\langle, \rangle_{L^2(\tau)}}$ on it by the formula

$\displaystyle \langle f, g \rangle_{L^2(\tau)} := \tau(fg).$

This is a positive semi-definite form, and gives a (possibly degenerate) inner product structure on ${{\mathcal A}}$. We could complete this structure into a Hilbert space ${L^2(\tau)}$ (after quotienting out the elements of zero norm), but we will not do so here, instead just viewing ${L^2(\tau)}$ as providing a semi-metric on ${{\mathcal A}}$. For future reference we record the inequalities

$\displaystyle \rho(fg) \leq \rho(f) \rho(g)$

$\displaystyle \rho(f+g) \leq \rho(f) + \rho(g)$

$\displaystyle \| fg\|_{L^2(\tau)} \leq \|f\|_{L^2(\tau)} \rho(g)$

for any ${f,g}$, which we will use in the sequel without further comment; see e.g. these previous blog notes for proofs. (Actually, for the purposes of proving Theorem 3, one can specialise to the ${L^\infty(X,\mu)}$ case (and ultraproducts thereof), in which case these inequalities are just the triangle and Hölder inequalities.)

The abstract version of Theorem 3 is then

Theorem 4 (Walsh’s theorem, abstract version) Let ${({\mathcal A},\tau)}$ be a commutative probability space, and let ${G}$ be a nilpotent group acting on ${{\mathcal A}}$ by isomorphisms (preserving the algebra, conjugation, and trace structure, and thus also preserving the spectral radius and ${L^2(\tau)}$ norm). Let ${g_1,\ldots,g_k: {\bf Z} \rightarrow G}$ be polynomial sequences. Then for any ${f_1,\ldots,f_k \in {\mathcal A}}$, the averages ${\frac{1}{N} \sum_{n=1}^N (g_1(n) f_1) \ldots (g_k(n) f_k)}$ form a Cauchy sequence in ${L^2(\tau)}$ (semi-)norm as ${N \rightarrow \infty}$.

It is easy to see that this theorem generalises Theorem 3. Conversely, one can use the commutative Gelfand-Naimark theorem to deduce Theorem 4 from Theorem 3, although we will not need this implication. Note how we are abandoning all attempts to discern what the limit of the sequence actually is, instead contenting ourselves with demonstrating that it is merely a Cauchy sequence. With this phrasing, it is tempting to ask whether there is any analogue of Walsh’s theorem for noncommutative probability spaces, but unfortunately the answer to that question is negative for all but the simplest of averages, as was worked out in this paper of Austin, Eisner, and myself.

Our proof of Theorem 4 will proceed as follows. Firstly, in order to avoid the epsilon management alluded to earlier, we will take an ultraproduct to rephrase the theorem in the language of nonstandard analysis; for reasons that will be clearer later, we will also convert the convergence problem to a problem of obtaining metastability (external Cauchy convergence). Then, we observe that (the nonstandard counterpart of) the expression ${\|\frac{1}{N} \sum_{n=1}^N (g_1(n) f_1) \ldots (g_k(n) f_k)\|_{L^2(\tau)}^2}$ can be viewed as the inner product of (say) ${f_k}$ with a certain type of expression, which we call a dual function. By performing an orthogonal projection to the span of the dual functions, we can split ${f_k}$ into the sum of an expression orthogonal to all dual functions (the “pseudorandom” component), and a function that can be well approximated by finite linear combinations of dual functions (the “structured” component). The contribution of the pseudorandom component is asymptotically negligible, so we can reduce to consideration of the structured component. But by a little bit of rearrangement, this can be viewed as an average of expressions similar to the initial average ${\frac{1}{N} \sum_{n=1}^N (g_1(n) f_1) \ldots (g_k(n) f_k)}$, except with the polynomials ${g_1,\ldots,g_k}$ replaced by a “lower complexity” set of such polynomials, which can be greater in number, but which have slightly lower degrees in some sense. One can iterate this (using “PET induction”) until all the polynomials become trivial, at which point the claim follows.

Let ${G = (G,+)}$ be an abelian countable discrete group. A measure-preserving ${G}$-system ${X = (X, {\mathcal X}, \mu, (T_g)_{g \in G})}$ (or ${G}$-system for short) is a probability space ${(X, {\mathcal X}, \mu)}$, equipped with a measure-preserving action ${T_g: X \rightarrow X}$ of the group ${G}$, thus

$\displaystyle \mu( T_g(E) ) = \mu(E)$

for all ${E \in {\mathcal X}}$ and ${g \in G}$, and

$\displaystyle T_g T_h = T_{g+h}$

for all ${g, h \in G}$, with ${T_0}$ equal to the identity map. Classically, ergodic theory has focused on the cyclic case ${G={\bf Z}}$ (in which the ${T_g}$ are iterates of a single map ${T = T_1}$, with elements of ${G}$ being interpreted as a time parameter), but one can certainly consider actions of other groups ${G}$ also (including continuous or non-abelian groups).

A ${G}$-system is said to be strongly ${2}$-mixing, or strongly mixing for short, if one has

$\displaystyle \lim_{g \rightarrow \infty} \mu( A \cap T_g B ) = \mu(A) \mu(B)$

for all ${A, B \in {\mathcal X}}$, where the convergence is with respect to the one-point compactification of ${G}$ (thus, for every ${\epsilon > 0}$, there exists a compact (hence finite) subset ${K}$ of ${G}$ such that ${|\mu(A \cap T_g B) - \mu(A)\mu(B)| \leq \epsilon}$ for all ${g \not \in K}$).

Similarly, we say that a ${G}$-system is strongly ${3}$-mixing if one has

$\displaystyle \lim_{g,h,h-g \rightarrow \infty} \mu( A \cap T_g B \cap T_h C ) = \mu(A) \mu(B) \mu(C)$

for all ${A,B,C \in {\mathcal X}}$, thus for every ${\epsilon > 0}$, there exists a finite subset ${K}$ of ${G}$ such that

$\displaystyle |\mu( A \cap T_g B \cap T_h C ) - \mu(A) \mu(B) \mu(C)| \leq \epsilon$

whenever ${g, h, h-g}$ all lie outside ${K}$.

It is obvious that a strongly ${3}$-mixing system is necessarily strong ${2}$-mixing. In the case of ${{\bf Z}}$-systems, it has been an open problem for some time, due to Rohlin, whether the converse is true:

Problem 1 (Rohlin’s problem) Is every strongly mixing ${{\bf Z}}$-system necessarily strongly ${3}$-mixing?

This is a surprisingly difficult problem. In the positive direction, a routine application of the Cauchy-Schwarz inequality (via van der Corput’s inequality) shows that every strongly mixing system is weakly ${3}$-mixing, which roughly speaking means that ${\mu(A \cap T_g B \cap T_h C)}$ converges to ${\mu(A) \mu(B) \mu(C)}$ for most ${g, h \in {\bf Z}}$. Indeed, every weakly mixing system is in fact weakly mixing of all orders; see for instance this blog post of Carlos Matheus, or these lecture notes of myself. So the problem is to exclude the possibility of correlation between ${A}$, ${T_g B}$, and ${T_h C}$ for a small but non-trivial number of pairs ${(g,h)}$.

It is also known that the answer to Rohlin’s problem is affirmative for rank one transformations (a result of Kalikow) and for shifts with purely singular continuous spectrum (a result of Host; note that strongly mixing systems cannot have any non-trivial point spectrum). Indeed, any counterexample to the problem, if it exists, is likely to be highly pathological.

In the other direction, Rohlin’s problem is known to have a negative answer for ${{\bf Z}^2}$-systems, by a well-known counterexample of Ledrappier which can be described as follows. One can view a ${{\bf Z}^2}$-system as being essentially equivalent to a stationary process ${(x_{n,m})_{(n,m) \in {\bf Z}^2}}$ of random variables ${x_{n,m}}$ in some range space ${\Omega}$ indexed by ${{\bf Z}^2}$, with ${X}$ being ${\Omega^{{\bf Z}^2}}$ with the obvious shift map

$\displaystyle T_{(g,h)} (x_{n,m})_{(n,m) \in {\bf Z}^2} := (x_{n-g,m-h})_{(n,m) \in {\bf Z}^2}.$

In Ledrappier’s example, the ${x_{n,m}}$ take values in the finite field ${{\bf F}_2}$ of two elements, and are selected at uniformly random subject to the “Pascal’s triangle” linear constraints

$\displaystyle x_{n,m} = x_{n-1,m} + x_{n,m-1}.$

A routine application of the Kolmogorov extension theorem allows one to build such a process. The point is that due to the properties of Pascal’s triangle modulo ${2}$ (known as Sierpinski’s triangle), one has

$\displaystyle x_{n,m} = x_{n-2^k,m} + x_{n,m-2^k}$

for all powers of two ${2^k}$. This is enough to destroy strong ${3}$-mixing, because it shows a strong correlation between ${x}$, ${T_{(2^k,0)} x}$, and ${T_{(0,2^k)} x}$ for arbitrarily large ${k}$ and randomly chosen ${x \in X}$. On the other hand, one can still show that ${x}$ and ${T_g x}$ are asymptotically uncorrelated for large ${g}$, giving strong ${2}$-mixing. Unfortunately, there are significant obstructions to converting Ledrappier’s example from a ${{\bf Z}^2}$-system to a ${{\bf Z}}$-system, as pointed out by de la Rue.

In this post, I would like to record a “finite field” variant of Ledrappier’s construction, in which ${{\bf Z}^2}$ is replaced by the function field ring ${{\bf F}_3[t]}$, which is a “dyadic” (or more precisely, “triadic”) model for the integers (cf. this earlier blog post of mine). In other words:

Theorem 2 There exists a ${{\bf F}_3[t]}$-system that is strongly ${2}$-mixing but not strongly ${3}$-mixing.

The idea is much the same as that of Ledrappier; one builds a stationary ${{\bf F}_3[t]}$-process ${(x_n)_{n \in {\bf F}_3[t]}}$ in which ${x_n \in {\bf F}_3}$ are chosen uniformly at random subject to the constraints

$\displaystyle x_n + x_{n + t^k} + x_{n + 2t^k} = 0 \ \ \ \ \ (1)$

for all ${n \in {\bf F}_3[t]}$ and all ${k \geq 0}$. Again, this system is manifestly not strongly ${3}$-mixing, but can be shown to be strongly ${2}$-mixing; I give details below the fold.

As I discussed in this previous post, in many cases the dyadic model serves as a good guide for the non-dyadic model. However, in this case there is a curious rigidity phenomenon that seems to prevent Ledrappier-type examples from being transferable to the one-dimensional non-dyadic setting; once one restores the Archimedean nature of the underlying group, the constraints (1) not only reinforce each other strongly, but also force so much linearity on the system that one loses the strong mixing property.

I have recently finished a draft version of my blog book “Poincaré’s legacies: pages from year two of a mathematical blog“, which covers all the mathematical posts from my blog in 2008, excluding those posts which primarily originated from other authors or speakers.

The draft is much longer – 694 pages – than the analogous draft from 2007 (which was 374 pages using the same style files).  This is largely because of the two series of course lecture notes which dominate the book (and inspired its title), namely on ergodic theory and on the Poincaré conjecture.  I am talking with the AMS staff about the possibility of splitting the book into two volumes, one focusing on ergodic theory, number theory, and combinatorics, and the other focusing on geometry, topology, and PDE (though there will certainly be miscellaneous sections that will basically be divided arbitrarily amongst the two volumes).

The draft probably also needs an index, which I will attend to at some point before publication.

As in the previous book, those comments and corrections from readers which were of a substantive and mathematical nature have been acknowledged in the text.  In many cases, I was only able to refer to commenters by their internet handles; please email me if you wish to be attributed differently (or not to be attributed at all).

Any other suggestions, corrections, etc. are, of course welcome.

I learned some technical tricks for HTML to LaTeX conversion which made the process significantly faster than last year’s, although still rather tedious and time consuming; I thought I might share them below as they may be of use to anyone else contemplating a similar conversion.

This month I am at MSRI, for the programs of Ergodic Theory and Additive Combinatorics, and Analysis on Singular Spaces, that are currently ongoing here.  This week I am giving three lectures on the correspondence principle, and on finitary versions of ergodic theory, for the introductory workshop in the former program.  The article here is broadly describing the content of these talks (which are slightly different in theme from that announced in the abstract, due to some recent developments).  [These lectures were also recorded on video and should be available from the MSRI web site within a few months.]

In this lecture, I define the basic notion of a dynamical system (as well as the more structured notions of a topological dynamical system and a measure-preserving system), and describe the main topics we will cover in this course.

Next quarter, starting on Wednesday January 9, I will be teaching a graduate course entitled “Topics in Ergodic Theory“. As an experiment, I have decided to post my lecture notes on this blog as the course progresses, as it seems to be a good medium to encourage feedback and corrections. (On the other hand, I expect that my frequency of posting on non-ergodic theory topics is going to go down substantially during this quarter.) All of my class posts will be prefaced with the course number, 254A, and will be placed in their own special category.

The topics I plan to cover include

• Topological dynamics;
• Classical ergodic theorems;
• The Furstenberg-Zimmer structure theory of measure preserving systems;
• Multiple recurrence theorems, and the connections with Szemerédi-type theorems;
• Orbits in homogeneous spaces (and in particular, in nilmanifolds);
• (Special cases of) Ratner’s theorem, and applications to number theory (e.g. the Oppenheim conjecture).

If time allows I will cover some other topics in ergodic theory as well (I haven’t decided yet exactly which ones to discuss yet, and might be willing to entertain some suggestions in this regard.)

If this works out well then I plan to also do the same for my spring class, in which I will cover as much of Perelman’s proof of the Poincaré conjecture as I can manage. (Note though that this latter class will build upon a class on Ricci flow given by my colleague William Wylie in the winter quarter, which will thus be a de facto prerequisite for my spring course.)

Ciprian Demeter, Michael Lacey, Christoph Thiele and I have just uploaded our joint paper, “The Walsh model for $M_2^*$ Carleson” to the arXiv. This paper (which was recently accepted for publication in Revista Iberoamericana) establishes a simplified model for the key estimate (the “$M_2^*$ Carleson estimate”) in another (much longer) paper of ours on the return times theorem of Bourgain, in which the Fourier transform is replaced by its dyadic analogue, the Walsh-Fourier transform. This model estimate is established by the now-standard techniques of time-frequency analysis: one decomposes the expression to be estimated into a sum over tiles, and then uses combinatorial stopping time arguments into group the tiles into trees, and the trees into forests. One then uses (phase-space localised, and frequency-modulated) versions of classical Calderòn-Zygmund theory (or in this particular case, a certain maximal Fourier inequality of Bourgain) to control individual trees and forests, and sums up over the trees and forests using orthogonality methods (excluding an exceptional set if necessary).

Rather than discuss time-frequency analysis in detail here, I thought I would dwell instead on the return times theorem, and sketch how it is connected to the $M_2^*$ Carleson estimate; this is a more complicated version of the “$M_2$ Carleson estimate”, which is an estimate which is logically equivalent to Carleson’s famous theorem (and its extension by Hunt) on the almost everywhere convergence of Fourier series.

I’ve just uploaded to the ArXiV my paper “Norm convergence of multiple ergodic averages for commuting transformations“, submitted to
Ergodic Theory and Dynamical Systems. This paper settles in full generality the norm convergence problem for several commuting transformations. Specifically, if $(X, {\mathcal X},\mu)$ is a probability space and $T_1, \ldots, T_l: X \to X$ are commuting measure-preserving transformations, then for any bounded measurable functions $f_1, \ldots, f_l: X \to {\Bbb R}$, the multiple average

$\frac{1}{N} \sum_{n=0}^{N-1} \int_X T_1^n f_1 \ldots T_l^n f_l$ (1)

is convergent in the $L^2(X)$ norm topology (and thus also converges in probability). The corresponding question of pointwise almost everywhere convergence remains open (and quite difficult, in my opinion). My argument also does not readily establish a formula as to what this limit actually is (it really establishes that the sequence is Cauchy in $L^2$ rather than convergent).

The l=1 case of this theorem is the classical mean ergodic theorem (also known as the von Neumann ergodic theorem). The l=2 case was established by Conze and Lesigne. The higher l case was partially resolved by Frantzikinakis and Kra, under the additional hypotheses that all of the transformations $T_i$, as well as the quotients $T_i T_j^{-1}$, are ergodic. The special case $T_j=T^j$ was established by Host-Kra (with another proof given subsequently by Ziegler). Another relevant result is the Furstenberg-Katznelson theorem, which asserts among other things when $f_1=\ldots=f_l$ is non-negative and not identically zero, then the inner product of the expression (1) with f has a strictly positive limit inferior as $N \to \infty$. This latter result also implies Szemerédi’s theorem.

It is also known that the Furstenberg-Katznelson theorem can be proven by hypergraph methods, and in fact my paper also proceeds by a hypergraph-inspired approach, although the language of hypergraphs is not explicitly used in the body of the argument. (In contrast to the work of Host-Kra and Ziegler, no nilsystems appear in the proof.)