You are currently browsing the tag archive for the ‘multiple recurrence’ tag.

Vitaly Bergelson, Tamar Ziegler, and I have just uploaded to the arXiv our joint paper “Multiple recurrence and convergence results associated to -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 is a measure-preserving -system (which, in this post, means that is a probability space and is measure-preserving and invertible, thus giving an action of the integers), and are functions, and is ergodic (which means that contains no -invariant functions other than the constants (up to almost everywhere equivalence, of course)), then the average

converges as to the expression

see e.g. this previous blog post. Informally, one can interpret this limit formula as an equidistribution result: if is drawn at random from (using the probability measure ), and is drawn at random from for some large , then the pair becomes uniformly distributed in the product space (using product measure ) in the limit as .

If we allow to be non-ergodic, then we still have a limit formula, but it is a bit more complicated. Let be the -invariant measurable sets in ; the -system can then be viewed as a *factor* of the original system , which is equivalent (in the sense of measure-preserving systems) to a trivial system (known as the *invariant factor*) in which the shift is trivial. There is then a projection map to the invariant factor which is a factor map, and the average (1) converges in the limit to the expression

where is the pushforward map associated to the map ; see e.g. this previous blog post. We can interpret this as an equidistribution result. If is a pair as before, then we no longer expect complete equidistribution in in the non-ergodic, because there are now non-trivial constraints relating with ; indeed, for any -invariant function , we have the constraint ; putting all these constraints together we see that (for almost every , at least). The limit (2) can be viewed as an assertion that this constraint are in some sense the “only” constraints between and , and that the pair 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

for three functions ; this is analogous to the combinatorial task of counting length three progressions in various sets. For simplicity we assume the system to be ergodic. Naively one might expect this limit to then converge to

which would roughly speaking correspond to an assertion that the triplet is asymptotically equidistributed in . 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 , . The key obstruction here is that of *eigenfunctions* of the shift , that is to say non-trivial functions that obey the eigenfunction equation almost everywhere for some constant (or -invariant) . Each such eigenfunction generates a constraint

tying together , , and . However, it turns out that these are in some sense the *only* constraints on that are relevant for the limit (3). More precisely, if one sets to be the sub-algebra of generated by the eigenfunctions of , then it turns out that the factor is isomorphic to a shift system known as the *Kronecker factor*, for some compact abelian group and some (irrational) shift ; the factor map pushes eigenfunctions forward to (affine) characters on . It is then known that the limit of (3) is

where is the closed subgroup

and is the Haar probability measure on ; see this previous blog post. The equation defining 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 is non-negative and not identically vanishing.

If one considers a quadruple average

(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* , which obey an eigenfunction equation in which is no longer constant, but is now a linear eigenfunction. For such functions, behaves quadratically in , and one can compute the existence of a constraint

between , , , and 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 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 -systems, but one can adapt much of the theory to measure-preserving -systems for other discrete countable abelian groups , in which one now has a family of shifts indexed by rather than a single shift, obeying the compatibility relation . The role of the intervals in this more general setting is replaced by that of Folner sequences. For arbitrary countable abelian , the theory for double averages (1) and triple limits (3) is essentially identical to the -system case. But when one turns to quadruple and higher limits, the situation becomes more complicated (and, for arbitrary , still not fully understood). However one model case which is now well understood is the finite field case when is an infinite-dimensional vector space over a finite field (with the finite subspaces 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 is drawn at random from a -system and drawn randomly from a large subspace of , then the only constraints between 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 -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 -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 in an ergodic -system and any , one has

for a syndetic set of , where are distinct residue classes. It turns out that Khintchine-type theorems always hold for (and for ergodicity is not required), and for it holds whenever 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 we could show that the Khintchine property failed for generic choices of , 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.

Tim Austin, Tanja Eisner, and I have just uploaded to the arXiv our joint paper Nonconventional ergodic averages and multiple recurrence for von Neumann dynamical systems, submitted to Pacific Journal of Mathematics. This project started with the observation that the multiple recurrence theorem of Furstenberg (and the related multiple convergence theorem of Host and Kra) could be interpreted in the language of dynamical systems of commutative finite von Neumann algebras, which naturally raised the question of the extent to which the results hold in the noncommutative setting. The short answer is “yes for small averages, but not for long ones”.

The Furstenberg multiple recurrence theorem can be phrased as follows: if is a probability space with a measure-preserving shift (which naturally induces an isomorphism by setting ), is non-negative with positive trace , and is an integer, then one has

In particular, for all in a set of positive upper density. This result is famously equivalent to Szemerédi’s theorem on arithmetic progressions.

The Host-Kra multiple convergence theorem makes the related assertion that if , then the scalar averages

converge to a limit as ; *a fortiori*, the function averages

converge in (say) norm.

The space is a commutative example of a von Neumann algebra: an algebra of bounded linear operators on a complex Hilbert space which is closed under the weak operator topology, and under taking adjoints. Indeed, one can take to be , and identify each element of with the multiplier operator . The operation is then a *finite trace* for this algebra, i.e. a linear map from the algebra to the scalars such that , , and , with equality iff . The shift is then an automorphism of this algebra (preserving shift and conjugation).

We can generalise this situation to the noncommutative setting. Define a *von Neumann dynamical system* to be a von Neumann algebra with a finite trace and an automorphism . In addition to the commutative examples generated by measure-preserving systems, we give three other examples here:

- (Matrices) is the algebra of complex matrices, with trace and shift , where is a fixed unitary matrix.
- (Group algebras) is the closure of the
*group algebra*of a discrete group (i.e. the algebra of finite formal complex combinations of group elements), which acts on the Hilbert space by convolution (identifying each group element with its Kronecker delta function). A trace is given by , where is the Kronecker delta at the identity. Any automorphism of the group induces a shift . - (Noncommutative torus) is the von Neumann algebra acting on generated by the multiplier operator and the shifted multiplier operator , where is fixed. A trace is given by , where is the constant function.

Inspired by noncommutative generalisations of other results in commutative analysis, one can then ask the following questions, for a fixed and for a fixed von Neumann dynamical system :

- (Recurrence on average) Whenever is non-negative with positive trace, is it true that
- (Recurrence on a dense set) Whenever is non-negative with positive trace, is it true thatfor all in a set of positive upper density?
- (Weak convergence) With , is it true thatconverges?
- (Strong convergence) With , is it true thatconverges in using the Hilbert-Schmidt norm ?

Note that strong convergence automatically implies weak convergence, and recurrence on average automatically implies recurrence on a dense set.

For , all four questions can trivially be answered “yes”. For , the answer to the above four questions is also “yes”, thanks to the von Neumann ergodic theorem for unitary operators. For , we were able to establish a positive answer to the “recurrence on a dense set”, “weak convergence”, and “strong convergence” results assuming that is ergodic. For general , we have a positive answer to all four questions under the assumption that is *asymptotically abelian*, which roughly speaking means that the commutators converges to zero (in an appropriate weak sense) as . Both of these proofs adapt the usual ergodic theory arguments; the latter result generalises some earlier work of Niculescu-Stroh-Zsido, Duvenhage, and Beyers-Duvenhage-Stroh. For the result, a key observation is that the van der Corput lemma can be used to control triple averages without requiring any commutativity; the “generalised von Neumann” trick of using multiple applications of the van der Corput trick to control higher averages, however, relies much more strongly on commutativity.

In most other situations we have counterexamples to all of these questions. In particular:

- For , recurrence on average can fail on an ergodic system; indeed, one can even make the average
*negative*. This example is ultimately based on a Behrend example construction and a von Neumann algebra construction known as the*crossed product*. - For , recurrence on a dense set can also fail if the ergodicity hypothesis is dropped. This also uses the Behrend example and the crossed product construction.
- For , weak and strong convergence can fail even assuming ergodicity. This uses a group theoretic construction, which amusingly was inspired by Grothendieck’s interpretation of a group as a sheaf of flat connections, which I blogged about recently, and which I will discuss below the fold.
- For , recurrence on a dense set fails even with the ergodicity hypothesis. This uses a fancier version of the Behrend example due to Ruzsa in this paper of Bergelson, Host, and Kra. This example only applies for ; we do not know for whether recurrence on a dense set holds for ergodic systems.

In Lecture 11, we studied *compact* measure-preserving systems – those systems in which every function was almost periodic, which meant that their orbit was precompact in the topology. Among other things, we were able to easily establish the Furstenberg recurrence theorem (Theorem 1 from Lecture 11) for such systems.

In this lecture, we generalise these results to a “relative” or “conditional” setting, in which we study systems which are compact relative to some factor of . Such systems are to compact systems as isometric extensions are to isometric systems in topological dynamics. The main result we establish here is that the Furstenberg recurrence theorem holds for such compact extensions whenever the theorem holds for the base. The proof is essentially the same as in the compact case; the main new trick is to not to work in the Hilbert spaces over the complex numbers, but rather in the Hilbert module over the (commutative) von Neumann algebra . (Modules are to rings as vector spaces are to fields.) Because of the compact nature of the extension, it turns out that results from topological dynamics (and in particular, van der Waerden’s theorem) can be exploited to good effect in this argument.

[Note: this operator-algebraic approach is not the only way to understand these extensions; one can also proceed by disintegrating into fibre measures for almost every and working fibre by fibre. We will discuss the connection between the two approaches below.]

The primary objective of this lecture and the next few will be to give a proof of the Furstenberg recurrence theorem (Theorem 2 from the previous lecture). Along the way we will develop a structural theory for measure-preserving systems.

The basic strategy of Furstenberg’s proof is to first prove the recurrence theorems for very simple systems – either those with “almost periodic” (or *compact*) dynamics or with “weakly mixing” dynamics. These cases are quite easy, but don’t manage to cover all the cases. To go further, we need to consider various combinations of these systems. For instance, by viewing a general system as an extension of the maximal compact factor, we will be able to prove Roth’s theorem (which is equivalent to the k=3 form of the Furstenberg recurrence theorem). To handle the general case, we need to consider compact extensions of compact factors, compact extensions of compact extensions of compact factors, etc., as well as weakly mixing extensions of all the previously mentioned factors.

In this lecture, we will consider those measure-preserving systems which are *compact* or *almost periodic*. These systems are analogous to the equicontinuous or isometric systems in topological dynamics discussed in Lecture 6, and as with those systems, we will be able to characterise such systems (or more precisely, the ergodic ones) algebraically as Kronecker systems, though this is not strictly necessary for the proof of the recurrence theorem.

In this lecture, we describe the simple but fundamental *Furstenberg correspondence principle* which connects the “soft analysis” subject of ergodic theory (in particular, recurrence theorems) with the “hard analysis” subject of combinatorial number theory (or more generally with results of “density Ramsey theory” type). Rather than try to set up the most general and abstract version of this principle, we shall instead study the canonical example of this principle in action, namely the equating of the *Furstenberg multiple recurrence theorem* with Szemerédi’s theorem on arithmetic progressions.

Read the rest of this entry »

In the previous lecture, we established single recurrence properties for both open sets and for sequences inside a topological dynamical system . In this lecture, we generalise these results to multiple recurrence. More precisely, we shall show

Theorem 1. (Multiple recurrence in open covers) Let be a topological dynamical system, and let be an open cover of X. Then there exists such that for every , we have for infinitely many r.

Note that this theorem includes Theorem 1 from the previous lecture as the special case . This theorem is also equivalent to the following well-known combinatorial result:

Theorem 2. (van der Waerden’s theorem) Suppose the integers are finitely coloured. Then one of the colour classes contains arbitrarily long arithmetic progressions.

**Exercise 1**. Show that Theorem 1 and Theorem 2 are equivalent.

**Exercise 2**. Show that Theorem 2 fails if “arbitrarily long” is replaced by “infinitely long”. Deduce that a similar strengthening of Theorem 1 also fails.

**Exercise 3**. Use Theorem 2 to deduce a finitary version: given any positive integers m and k, there exists an integer N such that whenever is coloured into m colour classes, one of the colour classes contains an arithmetic progression of length k. (Hint: use a “compactness and contradiction” argument, as in my article on hard and soft analysis.)

We also have a stronger version of Theorem 1:

Theorem 3. (Multiple Birkhoff recurrence theorem) Let be a topological dynamical system. Then for any there exists a point and a sequence of integers such that as for all .

These results already have some application to equidistribution of explicit sequences. Here is a simple example (which is also a consequence of Weyl’s equidistribution theorem):

Corollary 1. Let be a real number. Then there exists a sequence of integers such that as .

**Proof**. Consider the skew shift system with . By Theorem 3, there exists and a sequence such that and both convege to . If we then use the easily verified identity

(1)

we obtain the claim.

**Exercise 4.** Use Theorem 1 or Theorem 2 in place of Theorem 3 to give an alternate derivation of Corollary 1.

As in the previous lecture, we will give both a traditional topological proof and an ultrafilter-based proof of Theorem 1 and Theorem 3; the reader is invited to see how the various proofs are ultimately equivalent to each other.

## Recent Comments