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

My lectures are devoted to the *correspondence principle* between finite dynamical systems and infinite dynamical systems, that allows one to convert certain statements about the former to logically equivalent statements about the latter. (I will be vague here about what “dynamical system” means; very broadly, just about anything with a group action could qualify here.) A little more specifically, the correspondence principle equates four types of results, which we informally describe as follows:

- Local quantitative results for concrete finite systems.
- Local qualitative results for concrete infinite systems.
- Continuous quantitative results for abstract finite systems.
- Continuous qualitative results for abstract infinite systems.

(The meaning of these terms should become clearer once we give some specific examples.)

There are many contexts in which this principle shows up (e.g. in Ramsey theory, recurrence theory, graph theory, group theory, etc.) but the basic ingredients are always the same. Namely, the correspondence between Type 1 and Type 2 (or Type 3 and Type 4) arises from a *weak sequential compactness property*, which, roughly speaking asserts that given any sequence of (increasingly large) finite systems, there exists a subsequence of such systems which converges (in a suitably “weak” sense) to an infinite system. [We will define these terms more precisely in concrete situations later.] More informally, any “sufficiently large” finite system can be “approximated” in some weak sense by an infinite system. (One can make this informal statement more rigorous using nonstandard analysis and/or ultrafilters, but we will not take such an approach here.) Because of this, we obtain a *correspondence principle*: any *qualitative* statement about infinite systems (e.g. that a certain quantity is always strictly positive) is equivalent to a *quantitative *statement about sufficiently large finite systems (e.g. a certain quantity is always uniformly bounded from below). This principle forms a crucial bridge between finitary (or quantitative) mathematics and infinitary (or qualitative) mathematics; in particular, by taking advantage of this principle, tools from one type of mathematics can be used to prove results in the other. (See my previous post on soft analysis and hard analysis for further discussion.)

In addition to the use of compactness, the other key pillar of the correspondence principle is that of *abstraction* – the ability to generalise from a concrete system (on a very explicit space, e.g. the infinite cube ) to an more general abstract setting (e.g. an abstract dynamical system, measure-preserving system, group, etc.) One of the reasons for doing this is that there are various maneuvres one can do in the abstract setting (e.g. passing from a system to a subsystem, a factor, or an extension, or by reasoning by analogy from other special systems that are different from the original concrete system) which can be quite difficult to execute or motivate if one stays within the confines of a single concrete setting.

We now turn to several specific examples of this principle in various contexts. We begin with the more “combinatorial” or “non-ergodic theoretical” instances of this principle, in which there is no underlying probability measure involved; these situations are simpler than the ergodic-theoretic ones, but already illustrate many of the key features of this principle in action.

**1. The correspondence principle in Ramsey theory**

We begin with the classical correspondence principle that connects Ramsey results about finite colourings, to Ramsey results about infinite colourings, or (equivalently) about the topological dynamics of covers of open sets. We illustrate this by demonstrating the equivalence of three statements. The first two are as follows:

Theorem 1.(van der Waerden theorem, Type 2 formulation) Suppose the integers are coloured by finitely many colours. Then there exist arbitrarily long monochromatic arithmetic progressions.

Theorem 2.(van der Waerden theorem, Type 1 formulation) For every c and k there exists N such that whenever is coloured by c colours, there exists a monochromatic arithmetic progression of length k.

It is easy to see that Theorem 2 implies Theorem 1. Conversely, to deduce Theorem 2 from Theorem 1 we use the correspondence principle as follows. Assume for contradiction that Theorem 1 was true, but Theorem 2 was false. Untangling the quantifiers, this means that there exist positive integers k, c, a sequence going to infinity, and colourings of into c colours, none of which contain any monochromatic arithmetic progressions of length k.

By shifting the sets and redefining a little, we can replace by . This sequence of colourings on the increasingly large sets . One can now extract a subsequence of such colourings on finite sets of integers that converge *pointwise* or *weakly* to a colouring on the whole set of integers by the usual “Arzelà-Ascoli diagonalisation trick”. Indeed, by passing to an initial subsequence (and using the infinite pigeonhole principle), one can ensure that all of these colourings eventually become a constant colour at 0; refining to another subsequence, we can ensure it is a constant colour at 1; then at -1, 2, -2, and so forth. Taking a diagonal subsequence of these sequences, we obtain a final subsequence of finite colourings that converges pointwise to an infinite limit colouring. By Theorem 1, this limit colouring contains an monochromatic arithmetic progression of length k. Now note that the property of being monochromatic at this progression is a *local* one: one only needs to inspect the colour of finitely many of the integers in order to verify this property. Because of this, this property of the infinite limit colouring will also be shared by the finite colourings that are sufficiently far along the converging sequence. But we assumed at the very beginning that none of these finite colourings have a monochromatic arithmetic progression of length k, a contradiction, and the claim follows.

The above argument has all the basic ingredients of the correspondence principle in action: a proof by contradiction, use of weak compactness to extract an infinite limiting object, application of the infinitary result to that object, and checking that the conclusion of that result is sufficiently “finitary”, “local”, or “continuous” that it extends back to some of the finitary sequence, leading to the desired contradiction. [It is essential that one manages to reduce to purely local properties before passing from the converging sequence to the limit, or vice versa, since non-local properties are usually not preserved by the limit. For instance, consider the colouring of which colours every integer between -N/2 and N/2 blue, and all the rest red. Then this converges weakly to the all-blue colouring, and clearly the (non-local) property of containing at least one red element is not preserved by the limit.]

A key disadvantage of the use of the correspondence principle, though, is that it is quite difficult to extract specific quantitative bounds from any argument that uses this principle; for instance, while one can eventually “proof mine” the above argument (combined with some standard proof of Theorem 1) to eventually get a bound on N in terms of k and d, such a bound is extremely poor (of Ackermann function type).

Theorem 1 can be reformulated in a more abstract form:

Theorem 3.(van der Waerden theorem, Type 4 version) Let X be a compact space, let be a homeomorphism, and let be an open cover of X. Then for any k there exists a positive integer n and an open set in the cover such that is non-empty.

The deduction of Theorem 3 from Theorem 1 is easy, after using the compactness to refine the open cover to a finite subcover, picking a point in X, and then colouring each integer n by the index of the first open set that contains . The converse deduction of Theorem 1 from Theorem 3 is the one which shows the “dynamical” aspect of this theorem: we can encode a colouring of the integers as a point in the infinite product space , where is the unique class such that (indeed, one can think of this product space as the space of all c-colourings of the integers). The infinite product space is compact with the product (or weak) topology used earlier, thus a sequence of colourings converge to a limit iff they converge locally (or pointwise). This space also comes with the standard shift (corresponding to right shift on the space of colourings). If we let X be the closure of the orbit , and let be the open cover , it is straightforward to show that Theorem 3 implies Theorem 1.

**2. The correspondence principle for finitely generated groups**

The combinatorial correspondence used above for colourings can also be applied to other situations, such as that of finitely generated groups. Recall that if G is a group generated by a finite set S, we say that G has polynomial growth if there exists constants K, d such that the ball of radius r (i.e. the set of words in S of length at most r) has cardinality at most . Such groups were classified by a well-known theorem of Gromov:

Theorem 4.(Gromov’s theorem on polynomial growth, Type 4 version) Let G be a finitely generated group of polynomial growth. Then G is virtually nilpotent (i.e. it has a finite index subgroup that is nilpotent).

As observed in Gromov’s original paper, this result is equivalent to a finitary version:

Theorem 5.(Gromov’s theorem on polynomial growth, Type 3) For every integers s, K, d, there exists R such that any finitely generated group with s generators, such that has cardinality at most for all , is virtually nilpotent.

It is clear that Theorem 5 implies Theorem 4; for the converse implication, we use the correspondence principle. We sketch the details as follows. First, we make things more concrete (i.e. move from Type 3 and Type 4 to Type 1 and Type 2 respectively) by observing that every group G on s generators can be viewed as a quotient of the (nonabelian) free group on s generators by some normal subgroup .

Suppose for contradiction that Theorem 5 failed in this concrete setting; then there exists s, K, d, a sequence going to infinity, and a sequence of groups such that each obeys the volume condition for all .

The next step, as before, is to exploit weak sequential compactness and extract a subsequence of groups that “converge” to some limit , in the “weak” or “pointwise” sense that converges pointwise (or locally) to (much as with the convergence of colourings in the previous setting). The Arzelà-Ascoli argument as before shows that we can find a subsequence of which do converge pointwise to some limit object ; one can check that the property of being a normal subgroup is sufficiently “local” that it is preserved under limits, thus is a normal subgroup of and so G is well-defined as a group. (One way to view this convergence is that algebraic identity obeyed by the generators of G, is eventually obeyed by the groups sufficiently far along the convergent subsequence, and conversely.)

As volume growth is a local condition (involving only words of bounded length for any fixed r), we then easily conclude that G is of polynomial growth, and thus by Theorem 4 is virtually nilpotent. Some nilpotent algebra reveals that every virtually nilpotent group is finitely presented, so in particular there are a finite list of relations among the generators which guarantee this virtual nilpotency property. Such properties are local enough that they must then persist to groups sufficiently far along the subsequence, contradicting Theorem 5.

A slight modification of the above argument also reveals that the step and index of the nilpotent subgroup of G can be bounded by some constant depending only on K, d, s; this gives Theorem 5 meaningful content even when G is finite (in contrast to Theorem 4, which is trivial for finite groups). On the other hand, no explicit bound for this constant (or for R) in terms of s, K, d is currently known, though presumably some such bound can eventually be extracted from the above argument and the existing proofs of Gromov’s theorem by proof mining techniques.

**3. The correspondence principle for dense sets of integers**

Now we turn to the more “ergodic” variants of the correspondence principle, starting with the fundamental *Furstenberg correspondence principle* connecting combinatorial number theory with ergodic theory. We will illustrate this with the classic example of Szemerédi’s theorem.

There are many finitary versions of Szemerédi’s theorem. Here is one:

Theorem 6.(Szemerédi’s theorem, Type 1 version) Let and . Then there exists a positive integer such that every subset A of with contains at least one k-term arithmetic progression.

The standard “Type 2” formulation of this theorem is the assertion that any subset of the integers of positive upper density has arbitrarily long arithmetic progressions. While this statement is indeed easily shown to be equivalent to Theorem 6, the Furstenberg correspondence principle instead connects this formulation to a rather different one, in which the deterministic infinite set is replaced by a random one. Recall that a random subset of integers is a random variable A taking values in the power set of the integers (or more formally, with a distribution that is a Borel probability measure on with the product topology), and so in particular the probabilities of any *cylinder events *such as

that involve only finitely many of the elements of A, are well-defined as numbers between 0 and 1. The Carathéodory extension theorem (combined with some topological properties of ) shows, conversely, that any assignment of numbers between 0 and 1 to each cylinder set, which obeys various compatibility conditions such as

can be shown to give rise to a well-defined random set A.

We say that a random set A of integers is *stationary* if for every integer h, the shifted set A+h has the same probability distribution as A. In terms of cylinder events, this is equivalent to a collection of assertions such as

and so forth. One can then equate Theorem 6 with

Theorem 7.(Szemerédi’s theorem, Type 2 version) Let A be a stationary random infinite set of integers such that (which, by stationarity, implies that for all n), and let . Then, with positive probability, A contains a k-term arithmetic progression for each k.

It is not difficult to show that Theorem 6 implies Theorem 7. We briefly sketch the converse implication, which goes through the usual compactness-and-contradiction method. Suppose for contradiction that Theorem 7 is true, but Theorem 6 fails. Then we can find k and , a sequence of going to infinity, and sets with with no k-term arithmetic progressions.

We now need to extract a stationary random infinite set A of integers as a limit of the deterministic finite sets . The way one does that is by randomly translating each of the . More precisely, let denote the random finite set , where is chosen from uniformly at random. The probability distribution of is a discrete probability measure on which is “almost stationary” in the sense that (say) has a distribution very close to ; for instance probabilities such as and can easily be seen to differ only by . Also, the fact that equates to the assertion that .

By using the same type of Arzelà-Ascoli argument as before, we can show that some subsequence of the random variables converge *weakly* to a limit in the sense that the cylinder probabilities of converge to those of B along this subsequence; thus for instance

.

(To get from the cylinder probabilities back to a random variable, one uses the Carathéodory extension theorem. Weak convergence (or more precisely, weak-* convergence) of measures is also known as vague convergence, or convergence in distribution.)

Since the are approximately stationary, one can show that is exactly stationary. Since is bounded uniformly away from zero, one can show that is positive. Thus, we can apply Theorem 7 to show that B contains a k-term arithmetic progression with positive probability. Since there are only countably many k-term arithmetic progressions, the countable pigeonhole principle then tells us that there exists some k-term arithmetic progression which lies in B with positive probability. This is a “local” property on B. By weak convergence, this means that this same is true for for n sufficiently far along this subsequence; in particular, the corresponding deterministic sets contain k-term arithmetic progressions, a contradiction. Thus Theorem 7 does imply Theorem 6.

Much as Theorem 1 is equivalent to Theorem 4, Theorem 7 can be reformulated in a more abstract manner, known as the *Furstenberg recurrence theorem*:

Theorem 8.(Szemerédi’s theorem, Type 4 version) Let be a probability space with a measure-preserving bimeasurable map (thus T is invertible, and are measurable and measure-preserving), and let have positive measure . Then there exists such that .

We leave the equivalence of Theorem 8 with Theorems 6,7 as an exercise.

**4. The correspondence principle for dense sets of integers II.
**

The deduction of Theorem 6 from Theorem 7, gives that the set A appearing in Theorem 6 has at least one k-term arithmetic progression, but if one inspects the argument more carefully, one sees that in fact one has a stronger statement that if N is large enough, there exists some such that A contains at least k-term arithmetic progressions of step r. We leave this derivation as an exercise.

It is possible however to find even more progressions in the set A:

Theorem 8′.(Szemerédi’s theorem, Varnavides-type version) Let and . Then there exists a positive integer and such that for every and every subset A of with contains at least k-term arithmetic progressions.

This can be obtained from Theorem 7 by repeating the derivation of Theorem 6 with two additional twists. Firstly, it is not difficult to modify the appearing in this derivation to be prime (for instance, by appealing to Bertrand’s postulate). This allows us to identify with the finite field , giving us the ability to *dilate* within this set as well as translate. For technical reasons it is also convenient to restrict to lie in the bottom half of this set, which is also easy to arrange. We then argue as before, but with the randomly translated set replaced by the randomly translated *and* dilated set , where h and r are independently chosen at random from this finite field. If one does this, one finds that probabilities such as are essentially equal to the number of k-term arithmetic progressions in , divided by (the restriction of to the bottom half of is necessary to avoid certain “wraparound” issues). If one then repeats the previous arguments one can establish Theorem 8′ from Theorem 7.

This type of argument was implicitly first introduced by Varnavides. Basically, this argument exploits the *affine invariance* (i.e. invariance) of the space of arithmetic progressions, as opposed to mere *translation invariance* (i.e. invariance).

One can rephrase Theorem 8 in a quantitative ergodic formulation, essentially due to Bergelson, Host, McCutcheon, and Parreau:

Theorem 9.(Szemerédi’s theorem, Type 3 version) Let and . Then there exists such that for every measure-preserving system and any measurable set A with , we have .

**5. The correspondence principle for sparse sets of integers**

It is possible to squeeze even more finitary results out of Theorem 7 than was done in the previous two sections. In particular, one has the following relative version of Szemerédi’s theorem:

Theorem 10.(Relative Szemerédi theorem) Let and . Let N be a sufficiently large integer, and let R be a “sufficiently pseudorandom” subset of . Then every subset A of R with contains one k-term arithmetic progression.

I did not define above what “sufficiently pseudorandom” meant as it is somewhat technical, but very roughly speaking it is a package of approximate independence conditions which include things like

, (1)

where is the normalised indicator function of R, and all arithmetic operations are taking place in the cyclic group .

The point of Theorem 10 is that it allows one to detect arithmetic progressions inside quite sparse sets of integers (typically, R will have size about , so A and R would be logarithmically sparse). In particular, a relative Szemerédi theorem similar to this one (but somewhat stronger) was a key ingredient in my result with Ben Green that the primes contain arbitrarily long arithmetic progressions. (Theorem 10 is unfortunately insufficient for this task, because the amount of pseudorandomness needed here depends on ; the relative Szemerédi’s theorem developed in my paper with Ben only needs a number of pseudorandomness conditions that depend on k but – crucially – not on .)

The derivation of Theorem 10 from Theorem 7 is discussed in this unpublished note of mine. We sketch the main ideas here. Once again, we argue by contradiction. If Theorem 10 failed, then one can find k and , a sequence going to infinity, a sequence of “increasingly pseudorandom” subsets of , and sets with such that none of the contain k-term arithmetic progressions.

As before, it is not difficult to ensure to be prime, and that lives in the bottom half of . We then create the random translated and dilated set as before; note that still has no k-term arithmetic progressions (except in the degenerate case r=0, but this case is extremely rare and becomes irrelevant in the limit). We can also randomly translated and dilate by the same parameters to obtain a random set ; thus is a relatively dense subset of the random (and potentially quite sparse) set .

In the previous two sections, we looked at the (Borel) probability measure on the power set formed by the distribution of , which can be viewed as a collection of cylinder statistics such as

where is the cylinder set . In order for these statistics to actually arise from a Borel probability measure, these statistics have to be numbers lying between 0 and 1, and they have to obey compatibility conditions such as

and also

.

Conversely, any set of non-negative numbers obeying these properties will give a Borel probability measure, thanks to the Carathéodory extension theorem.

In the sparse case, this approach does not work, because degenerates in the limit if is sparse. For instance, because is so sparse, the probability can go to zero; indeed, we expect this quantity to look like . To fix this we do two things. Firstly, we replace the absolute complement that implicitly appears above by the relative complement . Secondly, we introduce the normalising factor , so for instance the cylinder set will now be assigned the normalised weight

and similarly for other cylinder sets. Perhaps more suggestively, we have

where and .

This gives us a non-negative number assigned to every cylinder set, but unfortunately these numbers do not obey the compatibility conditions required to make these numbers arise from a probability measure. However, if one assumes enough pseudorandomness conditions such as (1), one can show that the compatibility conditions are satisfied approximately, thus for instance

or equivalently

These conditions can be checked using a large number of applications of the Cauchy-Schwarz inequality, which we omit here. Thus, is not a true probability measure, but is some sort of approximate “virtual probability measure”. It turns out that these virtual probability measures enjoy the same crucial weak compactness property as actual probability measures, and one can repeat all the previous arguments to deduce Theorem 10 from Theorem 7.

**6. The correspondence principle for graphs**

In the previous three sections we considered the correspondence principle in the integers . It is not difficult to replace the integers with other amenable groups, such as for some fixed d. Now we discuss a somewhat different-looking instance of the correspondence principle, coming from graph theory, in which the underlying group is now the (small) permutation group consisting of those permutations which permute only finitely many elements. (It is convenient to work with this group, rather than the entire group of permutations, as it is countable.) We illustrate the graph correspondence principle with the following old result of Ruzsa and Szemerédi:

Theorem 11.(Triangle removal lemma, Type 3 version) For every there exists and such that for any be a graph on N vertices for some which has at most triangles, one can remove at most edges from the graph to make the graph triangle free.

We will not discuss why this theorem is of interest, other than to mention in passing that it actually implies the k=3 case of Szemerédi’s theorem. (See also my previous blog posts on related topics.) It turns out that this result can be deduced from some infinitary versions of this lemma. Here is one instance:

Theorem 12.(Triangle removal lemma, Type 2 version) Let G be a random graph on the integers which isexchangeablein the sense that any permutation of G has the same distribution as G. (This is the analogue of stationarity in this setting.) Suppose that G is almost surely triangle free, and let . Then there exists a continuous function F from the space of graphs on (with the product topology) to the space of graphs on , which is equivariant with respect to permutations of , such that issurely(not just almost surely) a subgraph of G which is triangle free, and such that .

Theorem 13.(Triangle removal lemma, Type 3 version) Let be a probability space with a measure-preserving action of , and let be three measurable sets which are invariant under the stabiliser of , , and respectively. Suppose that has measure zero. Then one can find subsets respectively of , which remain invariant under the stabilisers of , , and respectively, such that is empty (and not just measure zero).

The proofs that Theorem 12 and Theorem 13 imply Theorem 11 are somewhat technical, but in the same spirit as the previous applications of the correspondence principle; see this paper (or these blog posts) and this paper respectively for details. In fact they prove slightly stronger statements than Theorem 11, in that they give a bit more information as to how the triangle-free graph G’ is obtained from the nearly triangle-free graph G. The same methods also apply to hypergraphs without much further difficulty, as is done in the above papers, but we will not discuss the details here.

**7. The correspondence principle over finite fields**

The correspondence principle can also be applied quite effectively to the finite field setting, which is a dyadic model for the integer setting. In particular, Tamar Ziegler and I have very recently shown the equivalence of the following two results:

Theorem 14.(Inverse Gowers conjecture for finite fields, Type 1 version) Let F be a finite field, let , let , and let be a function on some vector space bounded in magnitude by 1, and such that the Gowers normis larger than , where . Then there exists a function which is a

phase polynomial of degree at most kin the sense that for all (or equivalently, that ), such that we have the correlation for some independent of n.

Theorem 15.(Inverse Gowers conjecture for finite fields, Type 4 version) Let be a probability space, let F be a finite field, and let be a measure-preserving action of the infinite group . Let be such that the Gowers-Host-Kra seminormis positive, where . Then there exists which is a phase polynomial in the sense that a.e., and which correlates with f in the sense that .

In a forthcoming paper of Bergelson, Ziegler, and myself (which I hope to discuss here on this blog in the near future), Theorem 15 was established, which by the correspondence principle alluded to above, implies Theorem 14. (See my previous blog post for some discussion of Theorem 14, which had been conjectured for a few years. Interestingly, this result also holds in the low characteristic case, for which (as discussed in that post) the conjecture was believed to fail. The issue here is a little subtle: counterexamples are known if the phase polynomial is constrained to be an root of unity, but with the above results we now know that these counterexamples are no longer present when the phase polynomial is allowed to range freely in .)

I will try to discuss these things in more detail in a later post, but very roughly speaking the reason why the correspondence principle is more effective here than on the integers is because the vector space enjoys a massively transitive action of the general linear group that mixes things around in a manner much stronger than even the affine action mentioned earlier (which is basically 2-transitive but not k-transitive for any higher k).

**8. The correspondence principle for convergence of ergodic averages**

My final instance of the correspondence principle goes in the opposite direction from previous instances. In the preceding seven instances, the interesting aspect of the principle was that one could use a qualitative result about infinite systems to deduce a quantitative result about finite systems. Here, we will do the reverse: we show how a result about infinite systems can be deduced from one from a finite system. We will illustrate this with a very simple result from ergodic theory, the mean ergodic theorem:

Theorem 16(Mean ergodic theorem, Type 4 version) Let be a measure-preserving system, and let . Let be the averaging operators . Then is a convergent sequence in as .

This is of course a well-known result with many short and elegant proofs; the proof method that we sketch here (essentially due to Avigad, Gerhardy, and Towsner) is lengthier and messier than the purely infinitary proofs, but can be extended to some situations in which it had been difficult to proceed in an infinitary manner (in particular on my result on convergence for multiple commuting transformations, as discussed in this post of mine).

The basic problem with finitising this theorem is that there is no uniform rate of convergence in the mean ergodic theorem: given any , we know that the averages eventually lie within of their limit for N large enough, but it is known that the N we need for this is not uniform in the choice of the system or the function f, and can indeed by arbitrarily large for given even after fixing the size of f. So a “naive” finitisation does not work, much as a naive finitisation of the infinite convergence principle (every bounded monotone sequence converges), as discussed in this post.

The resolution is in fact very similar to that discussed in the above-mentioned post. Observe that if is any sequence in a complete metric space (e.g. the real line, or ), the statement that “” converges”, or equivalently that “ is Cauchy“, is equivalent to

For every , there exists n such that for all sufficiently large m, ,

which is in turn equivalent to

For every there exists such that for every that grows faster than in the sense that for all n, one has for some n.

The point here is that once the function F is selected, one only has to verify the closeness of a single pair of elements in the sequence, rather than infinitely many. This makes it easier to finitise the convergence statement effectively. Indeed, Theorem 16 is easily seen (by another compactness and contradiction argument) to be equivalent to

Theorem 17(Mean ergodic theorem, Type 3 version) For every and every sufficiently rapid F (i.e. F grows faster than some depending on ) there exists N such that for every measure-preserving system and every with , we have for some .

Note that this theorem is quantitative in the sense that N depends only on and F, and not on the underlying system; indeed one can give an explicit value for N, arising from iterating F about times. This result is essentially proven as Corollary 2 of my 254A lecture notes on this topic.

## 32 comments

Comments feed for this article

31 August, 2008 at 9:25 am

gowersTerry, that’s great news and I look forward to hearing more about it. For now, let me say congratulations and also make the stupid remark that you seem to have forgotten a “latex” in your statement of Theorem 15.

There’s a sort of intermediate reformulation of Szemeredi’s theorem that I like (and that you of course know well), which serves a bridge between the finitary statement and the ergodic one. It’s that if is a function on that takes values in and has average then there’s a constant that depends on only such that the average value of is bounded below by . It’s easily seen to be equivalent to the Varnavides version and I find it the most natural one to think about from an analytic-but-finite point of view.

31 August, 2008 at 8:56 pm

Anthony QuasTheorem 12 should include something about the triangle-freeness of the graph, right?

31 August, 2008 at 9:44 pm

Terence TaoDear Tim and Anthony: thanks for the corrections! Tim, you are of course right that the finitary versions of Szemeredi’s theorem are best phrased using functions instead of sets (and the infinitary versions can be formulated that way also), but the correspondence principle is a little bit trickier to pull off in that setting (though not by too much) so I avoided it in my lectures.

1 September, 2008 at 2:55 am

SeanHere are some possible typos:

– In the ‘approximate independence conditions’ stated after Theorem 10, the definition of is not typesetting.

– Should the G’ in Theorem 12 equal F(G)?

1 September, 2008 at 8:29 am

Terence TaoDear Sean: thanks for the corrections!

1 September, 2008 at 9:36 am

IndianREQUEST

Dear Prof Terence Tao, I was waiting for a reply to this query , I surmise you might have overlooked this query, it’s an important query that plays a pivotal role in solving intricate problems.

QUERY

Hello Mr Tao, I would like to know if imagination plays a comprehensive role in solving intricate problems, if so do you possess vivid powers of imagination? How do you approach a convoluted problem? Do you apply “Imagination” , other “tricks” ,etc, in arriving at a solution, please answer this query, I thank you in advance.

Prof Terence Tao, I humbly request you to answer this query, I am requesting you, please, I will be grateful to you, i apologize for posting this query over here, I thank you.

2 September, 2008 at 9:30 am

Terence TaoDear Indian,

I think each mathematician has his or her own way to make progress, but I personally do not think of myself as particularly imaginative, and in fact imagination does not play much of a role in my own mathematics; to me, other attributes, such as having insight, intuition, knowledge, clarity of thought, concentration, appreciation of the “big picture”, and immersion in a problem, are significantly more important. While one does of course have to come up with new ideas (as well as applying, refining, clarifying, or modifying existing technology, of course) when solving any genuinely non-trivial problem, I find that such ideas tend to be found naturally – without the need for any wildly creative or imaginative leap of faith – after one has thought about the problem long enough, isolated the main difficulties, found the key test cases or model problems, understood the key counterexamples, grasped the strengths and weaknesses of existing methods, and so forth. Such new ideas may

appearto come “out of the blue” to outside observers who have not spent quite as much time being immersed in the problem, but they are usually in fact closely connected to the context that one is working in.It does happen from time to time that a truly original idea causes an important breakthrough in a field, but in the majority of cases (particularly in mature fields), mathematical progress is usually based primarily on existing technology, and to organic refinements and modifications to that technology, as these are, after all, tried and tested ideas that are proven to work. Most new ideas in fact end up not being particularly effective, especially if they are not guided by the existing body of results, intuition, heuristics, etc., although often the

reasonfor the failure of these ideas tends to be rather instructive.3 September, 2008 at 6:12 am

philippdear prof. tao,

right at the end of 1. it should be “Theorem 3 implies Theorem 1” and not vice versa.

best regards,

philipp

5 September, 2008 at 7:49 pm

Terence TaoDear philipp: thanks for the correction.

5 September, 2008 at 8:53 pm

AnonymousDr. Tao,

I’m a bit confused about how your new result on the inverse Gower’s conjecture reconciles with the previously discussed “counterexample.” Did the formulation of the statement change in low characteristic, or is the counterexample, in fact, not a counterexample?

8 September, 2008 at 9:40 am

Terence TaoDear anonymous:

It turns out that there are two formulations of the Gowers inverse conjecture in finite fields, one in which polynomials are constrained to lie in p^th roots of unity, and the other in which polynomials are allowed to range freely in the unit circle. For high characteristic (p >= k) some simple algebra shows that the two formulations are equivalent. But in low characteristic, there exist polynomials that do not take values in p^th roots of unity (even after multiplying by constants). For instance, the function that maps 0 to 1 and 1 to i is a quadratic phase polynomial from F_2 to S^1 which does not take values in the second roots of unity {-1,1}.

The first formulation of the Gowers inverse conjecture fails in low characteristic, but our result (which we are still checking and polishing, but should be ready for uploading soon) shows that the second formulation continues to hold in this case.

1 November, 2008 at 11:05 am

The inverse conjecture for the Gowers norm over finite fields via the correspondence principle « What’s new[…] principle“, submitted to Analysis & PDE. As announced a few months ago in this blog post, this paper establishes (most of) the inverse conjecture for the Gowers norm from an ergodic theory […]

7 March, 2009 at 9:34 am

Infinite fields, finite fields, and the Ax-Grothendieck theorem « What’s new[…] correspondence Serre discusses is slightly different from the one I discuss for instance in here or here, although there seems to be a common theme of “compactness” (or of model theory) tying […]

10 April, 2009 at 9:24 pm

The completeness and compactness theorems of first-order logic « What’s new[…] as the elementary limits of sequences of finite fields. I recently discovered that other several correspondence principles between finitary and infinitary objects, such as the Furstenberg correspondence principle between […]

8 May, 2009 at 8:14 pm

Szemeredi’s regularity lemma via the correspondence principle « What’s new[…] through a graph-theoretic version of the Furstenberg correspondence principle (mentioned briefly in this earlier post of mine). While this approach superficially looks quite different from the combinatorial approach, it in […]

22 August, 2009 at 11:50 am

GILA 1: van der Waerden and all that « Portrait of the Mathematician[…] be seen to be equivalent to the infinitary version stated earlier in the post, by what Terry Tao calls the Arzela-Ascoli trick. The key is to proceed by induction on k; fix some k and assume the theorem […]

23 October, 2009 at 11:46 am

A finitary version of Gromov’s polynomial growth theorem « What’s new[…] subgroup of , and the step of that subgroup). However, a compactness argument (sketched in this previous blog post) shows that some such relationship must exist; indeed, if one has (1) for all for some […]

14 December, 2009 at 3:38 pm

Approximate bases, sunflowers, and nonstandard analysis « What’s new[…] theorems to each other without a significant increase in effort. (This is closely related to various correspondence principles between combinatorics and parts of infinitary mathematics, such as ergodic theory; see also my post […]

30 January, 2010 at 7:07 pm

Ultralimit analysis, and quantitative algebraic geometry « What’s new[…] analysis, ultrafilters, ultralimit analysis | by Terence Tao I have blogged a number of times in the past about the relationship between finitary (or “hard”, or […]

10 February, 2010 at 10:56 pm

245A, Notes 5: Free probability « What’s new[…] up in the application of ergodic theory to combinatorics via the correspondence principle; see this previous blog post for further […]

19 March, 2010 at 9:53 pm

A computational perspective on set theory « What’s new[…] only finitely many points or numbers, etc.); I have explored this theme in a number of previous blog posts. So, one may ask: what is the finitary analogue of statements such as Cantor’s theorem […]

27 November, 2010 at 12:07 am

Nonstandard analysis as a completion of standard analysis « What’s new[…] theorem for ultrapowers to establish various versions of the correspondence principle, as discussed previously on this blog. A simple example occurs when demonstrating the equivalence of colouring theorems, […]

23 January, 2011 at 7:13 am

The Peter-Weyl theorem, and non-abelian Fourier analysis on compact groups « What’s new[…] a crucial role in Gromov’s proof of his theorem on groups of polynomial growth (discussed previously on this blog), and in a more recent paper of Hrushovski on approximate groups (also discussed […]

30 January, 2011 at 8:59 pm

A topological proof of Van der Waerden’s Theorem | YAMB[…] 2. We now present a standard compactness argument, explored in great detail by Terence Tao in his blog, to derive the other […]

8 July, 2012 at 8:48 am

RexIn the statement of Theorem 8′, I assume you want to add that

[Corrected, thanks – T.]27 March, 2013 at 7:33 pm

An informal version of the Furstenberg correspondence principle | What's new[…] the string , 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 […]

5 March, 2017 at 10:38 am

Furstenberg limits of the Liouville function | What's new[…] correspondence principle is discussed in these previous blog posts. One way to establish the principle is by introducing a Banach limit that extends the usual limit […]

9 May, 2018 at 12:51 pm

ahartelI have a question regarding the proof that Theorem 1 implies Theorem 2. I’m not sure if anybody will read my question at all given the fact that this post is almost 10 years old, but I’ll try anyway.

But let me first express my gratitude to you for writing this blog and for exposing so much of your mathematical thinking. I think you serve the discipline invaluably in writing this blog and being so open with your ideas.

But back to my question: While thinking about the proof that the infinitary vdW impies the finitary vdW (Theorem 2) I was wondering if the diagonalization trick is even necessary. After all, we’re interested in a finite section of the “limit coloring” of all integers, a finite section that only just contains our k-term AP. Now we want to make sure that there also exist finite colorings with the same colors in that section in order to complete the contradiction.

So in order to construct the “pre-infinite” coloring with the k-term AP we might start by picking a subsequence along one position (say 17). We then proceed along all positions of our finite section and get “thinner and thinner” subsequences for the other positions. Since we only “thin out” finitely often we should be fine and end up with stable colors (for some N) all along the section. Contradiction complete, proof complete. So I don’t understand why we need to add finitely many elements to each sub-sub-sequence by picking the diagonalized subsequence globally. I would be very thankfull if someone could help me improve my understanding.

10 May, 2018 at 5:00 pm

Terence TaoI’m not sure I follow your argument – it would help if you would give names to all the colorings etc. you are discussing – but one can’t apply the infinitary van der Waerden theorem unless one has an infinite coloring; merely being able to color a finite portion of the integers doesn’t immediately yield any conclusion. (One could add dummy colors to all the integers outside this finite portion, but then the monochromatic AP provided by the infinitary van der Waerden theorem might reside partially or fully in the dummy region, and again one does not obtain any useful conclusion.)

13 May, 2018 at 11:27 am

ahartelThank you for taking the time to read and answer my question. Your reply was very helpful indeed. Of course you can only apply Thm. 1 once you’ve obtained a coloring of all the integers.

And also, next time I’ll try to be more precise in naming my objects.

14 May, 2018 at 12:52 pm

Finitary versions of theorems – Write down what you’ve done[…] https://terrytao.wordpress.com/2008/08/30/the-correspondence-principle-and-finitary-ergodic-theory/ […]

14 June, 2019 at 2:34 pm

Abstracting induction on scales arguments | What's new[…] In this post I would like to observe that one can clean up and made more systematic this final step (iii) by passing to upper exponents (12) to eliminate the role of the parameter (and also “tropicalising” all the estimates), and then taking similar limit superiors to eliminate some other less important parameters, until one is left with a simple linear programming problem (which, among other things, could be amenable to computer-assisted proving techniques). This method is analogous to that of passing to a simpler asymptotic limit object in many other areas of mathematics (for instance using the Furstenberg correspondence principle to pass from a combinatorial problem to an ergodic theory problem, as discussed in this previous post). […]