In this lecture, we use topological dynamics methods to prove some other Ramsey-type theorems, and more specifically the polynomial van der Waerden theorem, the hypergraph Ramsey theorem, Hindman’s theorem, and the Hales-Jewett theorem. In proving these statements, I have decided to focus on the ultrafilter-based proofs, rather than the combinatorial or topological proofs, though of course these styles of proof are also available for each of the above theorems.

— The polynomial van der Waerden theorem —

We first prove a significant generalisation of van der Waerden’s theorem (Theorem 2 from the previous lecture):

Theorem 1(Polynomial van der Waerden theorem). Let be a tuple of be integer-valued polynomials ) (ortuplefor short) with . Then whenever the integers are finitely coloured, one of the colour classes will contain a pattern of the form for some and .

This result is due to Bergelson and Leibman, who proved it using “epsilon and delta” topological dynamical methods. A combinatorial proof was only obtained rather recently by Walters. In these notes, I will translate the Bergelson-Leibman argument to the ultrafilter setting.

Note that the case recovers the ordinary van der Waerden theorem. But the result is significantly stronger; it implies for instance that one of the colour classes contains arbitrarily many shifted geometric progressions , which does not obviously follow from the van der Waerden theorem. The result here only claims a single monochromatic pattern , but it is not hard to amplify this theorem to show that at least one colour class contains infinitely many such patterns.

**Remark 1**. The theorem can fail if the hypothesis is dropped; consider for instance the case , , , and with the integers partitioned (or coloured) into the odd and even integers. More generally, the theorem fails whenever there exists a modulus N such that the polynomials are never simultaneously equal modulo N. This turns out to be the only obstruction; this is a somewhat difficult recent result of Bergelson, Leibman, and Lesigne.

**Exercise 1**. Show that the polynomial has a root modulo N for every positive integer N, but has no root in the integers. Thus we see that the Bergelson-Leibman-Lesigne result is stronger than the polynomial van der Waerden theorem; it does not seem possible to directly use the latter to conclude that in every finite colouring of the integers, one of the classes contains the pattern .

Here are the topological dynamics and ultrafilter versions of the above theorem.

Theorem 2(Polynomial van der Waerden theorem, topological dynamics version). Let be a tuple with . Let be an open cover of a topological dynamical system . Then there exists a set in this cover such that for at least one .

Theorem 3(Polynomial van der Waerden theorem, ultrafilter version). Let be a tuple with , and let be a minimal ultrafilter. Then there exists such thatfor all . (1)

**Exercise 2**. Show that Theorem 1 and Theorem 2 are equivalent, and that Theorem 3 implies Theorem 2 (or Theorem 1). [For the converse implication, see Exercise 21.]

As in the previous lecture, we shall prove this proposition by induction. However, the induction will be more complicated than just inducting on the number k of polynomials involved, or on the degree of these polynomials, but will instead involve a more complicated measure of the “complexity” of the polynomials being measured. Let us say that a tuple *obeys the vdW property* if the conclusion of Theorem 3 is true for this tuple. Thus for instance, from Proposition 1 from the previous lecture we know that any tuple of *linear *polynomials which vanish at the origin will obey the vdW property.

Our goal is to show that every tuple of polynomials which simultaneously vanish at the origin has the vdW property. The strategy will be to reduce from any given tuple to a collection of “simpler” tuples. We first begin with an easy observation, that one can always shift one of the polynomials to be zero:

Lemma 1. (Translation invariance) Let Q be any integer-valued polynomial. Then a tuple obeys the vdW property if and only if has the vdW property.

**Proof**. Let be minimal. If has the vdW property, then we can find such that

for all . (2)

If we then define one easily verifies that (1) holds (with q replaced by q’), and the claim holds. The converse implication is similar.

Now we come to the key inductive step.

Lemma 2(Inductive step). Let be a tuple with , and let Q be another integer-valued polynomial. Suppose that for every finite set of integers , the tuple has the vdW property. Then also has the vdW property.

**Proof**. This will be a reprise of the proof of Proposition 1 from the previous lecture. Given any finite number of pairs with , we see from hypothesis that there exists (depending on these pairs) such that

(3)

for all and .

Now, for every and , consider the expression defined by

, (4)

where are defined recursively as above and

(5).

From (3) we see that

(6)

for all and , and thus

(7)

in this case. For i=0, we have the slightly different identity

. (7′)

We let be arbitrary, and set . By the minimality of p, we can find such that . We thus have

(8)

for all . If one then sets

(9)

where and , one easily verifies (1) as required.

Let’s see how this lemma is used in practice. Suppose we wish to show that the tuple has the vdW property (where we use r to denote the independent variable). Applying Lemma 2 with , we reduce to showing that the tuples have the vdW property for all finite collections of integers. But observe that all the polynomials in these tuples are linear polynomials that vanish at the origin. By the ordinary van der Waerden theorem, these tuples all have the vdW property, and so has the vdW property also.

A similar argument shows that the tuple has the vdW property whenever are linear polynomials that vanish at the origin. Applying Lemma 1, we see that obeys the vdW property when is also linear and vanishing at the origin.

Now, let us consider a tuple where is also a linear polynomial that vanishes at the origin. The vdW property for this tuple follows from the previously established vdW properties by first applying Lemma 1 to reduce to the case , and then applying Lemma 2 with . Continuing in this fashion, we see that a tuple will also obey the vdW property for any linear that vanish at the origin, for any k and l.

Now the vdW property for the tuple follows from the previously established cases and Lemma 2 with .

**Remark 2.** It is possible to continue this inductive procedure (known as *PET induction;* the PET stands, variously, for “polynomial ergodic theorem” or “polynomial exhaustion theorem”); this is carried out in Exercise 3 below.

**Exercise 3. ** Define the *top order monomial* of a non-zero polynomial with to be . Define the top order monomials of a tuple to be the set of top order monomials of the , not counting multiplicity; for instance, the top order monomials of are . Define the *weight vector* of a tuple relative to one of its members to be the infinite vector , where each denotes the number of monomials of degree d in the top order monomials of . Thus for instance, the tuple has weight vector with respect to 0, but weight vector with respect to (say) . Let us say that one weight vector is larger than another if there exists such that and for all .

- Show that the space of all weight vectors is a well-ordered set.
- Show that if is a tuple with , has the least degree of all the , and are integers with , then the weight vector of with respect to is strictly smaller than the weight vector of with respect to .
- Using 1., 2., Lemma 1, and Lemma 2, deduce Theorem 3.

**Exercise 4.** Find a direct proof of Theorem 2 analogous to the “epsilon and delta” proof of Theorem 4 from the previous lecture. (You can look up the paper of Bergelson and Leibman if you’re stuck.)

**Exercise 5**. Let be vector-valued polynomials (thus each of the d components of each of the is a polynomial) which all vanish at the origin. Show that if is finitely coloured, then one of the colour classes contains a pattern of the form for some and .

**Exercise 6**. Show that for any polynomial sequence taking values in a torus, there exists integers such that converges to . (One can also tweak the argument to make the converge to positive infinity, by the “doubling up” trick of replacing P(n) with (P(n),P(-n)).) On the other hand, show that this claim can fail with exponential sequences such as for certain values of . Thus we see that polynomials have better recurrence properties than exponentials.

— Ramsey’s theorem —

Given any finite palette K of colours, a vertex set V, and an integer , define a *K-coloured hypergraph* G = (V,E) of order k on V to be a function , where denotes the k-element subsets of V. Thus for instance a hypergraph of order 1 is a vertex colouring, a hypergraph of order 2 is an edge-coloured complete graph, and so forth. We say that a hypergraph G is *monochromatic* if the edge colouring function E is constant. If W is a subset of V, we refer to the hypergraph as a *subhypergraph* of G.

We will now prove the following result:

Theorem 4(Hypergraph Ramsey theorem). Let K be a finite set, let , and let G = (V,E) be a K-coloured hypergraph of order k on a countably infinite vertex set V. Then G contains arbitrarily large finite monochromatic subhypergraphs.

**Remark 3.** There is a stronger statement known, namely that G contains an infinitely large monochromatic subhypergraph, but we will not prove this statement, known as the *infinite hypergraph Ramsey theorem*. In the case k=1, these statements are the pigeonhole principle and infinite pigeonhole principle respectively, and are compared in my article on hard and soft analysis.

**Exercise 7.** Show that Theorem 4 implies a finitary analogue: given any finite K and positive integers k, m, there exists N such that every K-coloured hyeprgraph of order k on contains a monochromatic subhypergraph on m vertices. (*Hint*: as in Exercise 3 from the previous lecture [note – exercises have been renumbered recently], one should use a compactness and contradiction argument as in my article on hard and soft analysis.)

It is not immediately obvious, but Theorem 4 is a statement about a topological dynamical system, albeit one in which the underlying group is not the integers , but rather the symmetric group , defined as the group of bijections from V to itself which are the identity outside of a finite set. More precisely, we have

Theorem 5. (Hypergraph Ramsey theorem, topological dynamics version) Let V be a countably infinite set, and let W be a finite subset of V, thus is a subgroup of . Let be a -topological dynamical system, thus is compact metrisable and is an action of on X via homeomorphisms. Let be an open cover of X, such that each is -invariant. Then there exists an element of this cover such that for every finite set there exists a group element such that (i.e. there exists such that for all ).

This claim should be compared with Theorem 2 of this lecture, or Theorem 1 of the previous lecture.

**Exercise 8**. Show that Theorem 4 and Theorem 5 are equivalent. (*Hint*: At some point, you will need the use the fact that the quotient space is isomorphic to .)

As before, though, we shall only illustrate the ultrafilter approach to Ramsey’s theorem, leaving the other approaches to exercises. Here, we will not work on the compactified integers , but rather on the compactified permutations . (We will view here as a discrete group; one could also give this group the topology inherited from the product topology on , leading to a slightly coarser (and thus less powerful) compactification, though one which is still sufficient for the arguments here.) This is a semigroup with the usual multiplication law

. (10)

Let us say that is *minimal* if is a minimal left-ideal of . One can show (by repeating Exercise 10 from Lecture 3) that every left ideal contains at least one minimal element; in particular, minimal elements exist.

Note that if W is a k-element subset of V, then there is an image map which maps a permutation to its inverse image of W. We can compactify this to a map . (Caution: is *not* the same thing as , for instance the latter is not even compact.) We can now formulate the ultrafilter version of Ramsey’s theorem:

Theorem 6. (Hypergraph Ramsey theorem, ultrafilter version) Let V be countably infinite, and let be minimal. Then for every finite set W, is constant on , thus for all .

This result should be compared with Proposition 1 from the previous lecture (or Theorem 3 from this lecture).

**Exercise 9**. Show that Theorem 6 implies both Theorem 4 and Theorem 5.

**Proof of Theorem 6.** By relabeling we may assume and for some k.

Given any integers , let denote the permutation that swaps j with for all , but leaves all other integers unchanged. We select some non-principal ultrafilter and define the sequence by the formula

(11)

(Note that the condition will be asymptotically true thanks to the choice of limits here.)

Let , and let be the a permutation which is the identity outside of . Then we have the identity

(12)

for every , where are the elements of in order. Taking limits as , and then inserting the resulting formula into (11), we conclude (after discarding the trivial limits and relabeling the rest) that

(13)

and in particular that is independent of (if is the identity outside of . Now let , then we have independent of p’ for all . Taking limits we conclude that is constant on . But from construction we see that p’ lies in the closed minimal ideal , thus . The claim follows.

**Exercise 10**. Establish Theorem 4 directly by a combinatorial argument without recourse to topological dynamics or ultrafilters. (If you are stuck, I recommend reading the classic text of Graham, Rothschild, and Spencer.)

**Exercise 11**. Establish Theorem 5 directly by a topological dynamics argument, using combinatorial arguments for the k=1 case but then proceeding by induction afterwards (as in the proof of Theorem 4 from the previous lecture).

**Remark 4**. More generally, one can interpret the theory of graphs and hypergraphs on a vertex set V through the lens of dynamics of actions; I learned this perspective from Balazs Szegedy, and it underlies my paper on the hypergraph correspondence principle, as well as my more recent paper with Tim Austin on hypergraph property testing.

— Idempotent ultrafilters and Hindman’s theorem —

Thus far, we have been using ultrafilter technology rather lightly, and indeed all of the arguments so far can be converted relatively easily to the topological dynamics formalism, or even a purely combinatorial formalism, with only a moderate amount of effort. But now we will exploit some deeper properties of ultrafilters, which are more difficult to replicate in other settings. In particular, we introduce the notion of an idempotent ultrafilter.

Definition 1. Let be a discrete semigroup, and let be given the usual semigroup operation . An element isidempotentif . (We of course define idempotence analogously if the group operation on S is denoted by + instead of .)

Of course, 0 is idempotent, but the remarkable fact is that many other idempotents exist as well. The key tool for creating this is

Lemma 3(Ellis-Nakamura lemma). Let S be a discrete semigroup, and let K be a compact non-empty sub-semigroup of . Then K contains at least one idempotent.

**Proof**: A simple application of Zorn’s lemma shows that K contains a compact non-empty sub-semigroup K’ which is minimal with respect to set inclusion. We claim that every element of K’ is idempotent. To see this, let p be an arbitrary element of K’. Then observe that K’p is a compact non-empty sub-semigroup of K’ and must therefore be equal to K’; in particular, . (Note that semigroups need not contain an identity.) In particular, the stabiliser is non-empty. But one easily observes that this stabiliser is also a compact sub-semigroup of K’, and so K”=K’. In particular, p must stabilise itself, i.e. it is idempotent.

**Remark 5.** *A posteriori*, this results shows that the minimal non-empty sub-semigroups K’ are in fact just the singleton sets consisting of idempotents. Of course, one cannot see this without first deriving all of Lemma 3.

Idempotence turns out to be particularly powerful when combined with minimality, and to this end we observe the following corollary of the above lemma:

Corollary 4. Let S be a discrete semigroup. For every , there exists which is both minimal and idempotent.

**Proof.** By Exercise 10 from Lecture 3, there exists which is minimal. It is then easy to see that every element of is minimal. Since is a compact non-empty sub-semigroup of , the claim now follows from Lemma 3.

**Remark 6.** Somewhat amusingly, minimal idempotent ultrafilters require *three* distinct applications of Zorn’s lemma to construct: one to define the compactified space , one to locate a minimal left-ideal, and one to locate an idempotent inside that ideal! It seems particularly challenging therefore to define civilised substitutes for this tool which do not explicitly use the axiom of choice.

What can we do with minimal idempotent ultrafilters? One particularly striking example is *Hindman’s theorem*. Given any set A of positive integers, define FS(A) to be the set of all finite sums from A, where B ranges over all finite non-empty subsets of A. (For instance, if are the powers of 2, then .)

Theorem 7(Hindman’s theorem) Suppose that the natural numbers are finitely coloured. Then one of the colour classes contains a set of the form FS(A) for some infinite set A.

**Remark 7**. Theorem 7 implies *Folkman’s theorem*, which has the same hypothesis but concludes that one of the colour classes contains sets of the form FS(A) for arbitrarily large but finite sets A. It does not seem possible to easily deduce Hindman’s theorem from Folkman’s theorem.

**Exercise 12.** Folkman’s theorem in turn implies *Schur’s theorem*, which asserts that if the natural numbers are finitely coloured, one of the colour classes contains a set of the form for some x, y (compare with the k=3 case of van der Waerden’s theorem). Using the Cayley graph construction, deduce Schur’s theorem from Ramsey’s theorem (the k=2 case of Theorem 4). Thus we see that there are some connections between the various Ramsey-type theorems discussed here.

**Proof of Theorem 7.** By Corollary 4, we can find a minimal idempotent element p in ; note that as no element of is minimal (cf. Exercise 7 from Lecture 3), we know that . Let denote the given colouring function, then is a colour in . Since

(14)

and

(15)

we may find a positive integer such that . Now from (14), (15) and the similar calculations

(16)

and

(17)

we can find an integer such that , thus for all . Continuing inductively in this fashion, one can find such that for all and all k. If we set , the claim follows.

**Remark 8.** Purely combinatorial (and quite succinct) proofs of Hindman’s theorem exist – see for instance the one in the text by Graham, Rothschild, and Spencer – but they generally rely on some *ad hoc* trickery. Here, the trickery has been encapsulated into the existence of minimal idempotent ultrafilters, which can be reused in other contexts (for instance, we will use it to prove the Hales-Jewett theorem below).

**Exercise 13**. Define an IP-set to be a set of positive integers which contains a subset of the form FS(A) for some infinite A. Show that if an IP-set S is finitely coloured, then one of its colour classes is also an IP-set. (*Hint*: S contains FS(A) for some infinite . Show that the set is a compact non-empty semigroup and thus contains a minimal idempotent ultrafilter p. Use this p to repeat the proof of Theorem 7.)

— The Hales-Jewett theorem —

Given a finite alphabet A, let be the free semigroup generated by A, i.e. the set of all finite non-empty words using the alphabet A, with concatenation as the group operation. (E.g. if , then contains words such as abc and cbb, with .) If we add another letter * to A (the “wildcard” letter), we create a larger semigroup (e.g. containing words such as ab**c*). We of course assume that * was not already present in A. Given any letter , we have a semigroup homomorphism which substitutes every occurrence of the wildcard * with x and leaves all other letters unchanged. (For instance, .) Define a *combinatorial line* in to be any set of the form for some . For instance, if , then is a combinatorial line, generated by the word .

We shall prove the following fundamental theorem.

Theorem 8(Hales-Jewett theorem). Let A be a finite alphabet. If is finitely coloured, then one of the colour classes contains a combinatorial line.

**Exercise 14**. Show that the Hales-Jewett theorem has the following equivalent formulation: for every finite alphabet A and any there exists N such that if is partitioned into m classes, then one of the classes contains a combinatorial line.

**Exercise 15.** Assume the Hales-Jewett theorem. In this exercise we compare the strength of this theorem against other Ramsey-type theorems.

- Deduce van der Waerden’s theorem (Theorem 2 from the previous lecture.)
*Hint*: the base k representation of the non-negative natural numbers provides a map from to . - Deduce the multidimensional van der Waerden’s theorem of Gallai (Exercise 7 from the previous lecture.)
- Deduce the
*syndetic van der Waerden theorem*of Furstenberg: if the integers are finitely coloured and k is a positive integer, then there are infinitely many monochromatic arithmetic progressions of length k, and furthermore the set of all the step sizes r which appear in such progressions is syndetic. (Hint: argue by contradiction, assuming that the set of all step sizes has arbitrarily long gaps, and use the Hales-Jewett theorem in a manner adapted to these gaps.) For an additional challenge, show that there exists a*single*colour class whose progressions of length k have spacings in a syndetic set for every k. - Deduce the
*IP-van der Waerden theorem*: If the integers are finitely coloured, k is a positive integer, and S is an IP-set (see Exercise 13), show that there are infinitely many monochromatic arithmetic progressions of length k whose step size lies in S. (For an additional challenge, show that one of the colour classes has the property that for every k, the spacings of the k-term progressions in that class forms an*-set*, i.e. it has non-empty intersection with every IP-set. There is an even stronger topological dynamics version of this statement, due to Furstenberg and Weiss, which I will not describe here.) - For any , define a
*d-dimensional combinatorial subspace*of to be a set of the form , where is a word containing at least one copy of each of the d wildcards , and is the homomorphism that substitutes each wildcard with . Show that if is finitely coloured, then one of the colour classes contains arbitrarily high-dimensional combinatorial subspaces. - Let F be a finite field. If the vector space (the inverse limit of the finite vector spaces ) is finitely coloured, show that one of the colour classes contains arbitrarily high-dimensional affine subspaces over F. (This
*geometric Ramsey theorem*is due to Graham, Leeb, and Rothschild.)

We now give an ultrafilter-based proof of the Hales-Jewett theorem due to Blass. As usual, the first step is to obtain a statement involving ultrafilters rather than colourings:

Proposition 1. (Hales-Jewett theorem, ultrafilter version) Let A be a finite alphabet, and let p be a minimal idempotent element of the semigroup . Then there exists such that for all .

**Exercise 16**. Deduce Theorem 8 from Proposition 1.

To prove Proposition 1, we need a variant of Corollary 4. If is a discrete semigroup and p and q are two idempotents in , let us write if we have .

**Exercise 17**. Show that is a partial ordering on the idempotents of , and that an idempotent is minimal in if and only if it is minimal with respect to .

Lemma 4. Let S be a discrete semigroup, and let p be an idempotent in . Then there exists a minimal idempotent q in such that .

**Proof of Lemma 4**. By Exercise 10 from Lecture 3 (generalised to arbitrary discrete semigroups S), contains a minimal left-ideal . By Lemma 3, contains an idempotent s. Since and p is idempotent, we conclude sp=s. If we then set , we easily check that q is idempotent, that , and (since q lies in the minimal left-ideal ) it is minimal. The claim follows.

**Proof of Proposition 1**. Since p is an idempotent element of , it is also an idempotent element of . However, it is not minimal in that semigroup; for instance, does not contain p, since and are disconnected from each other. However, by Lemma 4, we can find a minimal idempotent q in such that . By the above discussion, q is not equal to p; since p is minimal in , we see that q must lie outside of .

Now let . Since is a homomorphism,

is also a homomorphism (why?). Since q is idempotent and (note that these are both purely *algebraic* statements), we conclude that is idempotent and . But is minimal in , hence by Exercise 17, we have . The claim follows.

**Exercise 18**. Adapt the above proof to give an alternate proof of the ultrafilter version of van der Waerden’s theorem (Proposition 1 from the previous lecture) which relies on idempotence rather than on induction on k. (If you are stuck, read the proof of Proposition 1.55 of Glasner’s book.)

**Remark 9.** Several of the above Ramsey-type theorems can be unified. For instance, the polynomial van der Waerden theorem and the Hales-Jewett theorem have been unified into the polynomial Hales-Jewett theorem of Bergelson and Leibman (see also the more recent paper of Walters on this topic). This type of Ramsey theory is still an active subject, and we do not yet have a comprehensive and systematic theory (or a “universal” Ramsey theorem) that encompasses all known examples.

**Exercise 19.** Let X be an at most countable set (with the discrete topology), and let be a family of subsets of X. Show that the following two statements are equivalent:

- Whenever X is finitely coloured, one of the colour classes contains a subset in .
- There exists such that every neighbourhood of p contains a subset in .

**Exercise 20. ** Let X, Y be at most countable sets with the discrete topology, and let be a finite collection of functions. Show that the following two statements are equivalent:

- Whenever X is finitely coloured, one of the colour classes contains a set for some .
- There exists such that .

(*Hint*: look at the closure of in $(\beta X)^k$.) ** **

**Exercise 21.** Using the previous exercise, deduce Theorem 3 from Theorem 1, and deduce Theorem 6 from Theorem 4.

[*Update*, Jan 24: extra factors added to the polynomial in Exercise 1 to sidestep issues at 2 and 3.]

[*Update*, Jan 30: remarks added and renumbered.]

[*Update*, Feb 1: More exercises added.]

[*Update*, Mar 21: Various corrections.]

[*Update*, Mar 25: Statement of Theorem 5 repaired.]

[*Update*, Mar 31 2009: Proof of Proposition 1 expanded.]

## 46 comments

Comments feed for this article

24 January, 2008 at 1:30 pm

YuryDear Prof. Tao,

the polynomial from Exercise 1 has no roots in case N=8.

24 January, 2008 at 2:29 pm

Terence TaoAh yes, the joys of low characteristic :-) . Easily fixed, of course, by throwing some non-quadratic polynomial such as into the mix, and I guess as well to deal with the obstructions at 3 also.

27 January, 2008 at 12:15 am

254A, Lecture 6: Isometric systems and isometric extensions « What’s new[…] recurrence theorems we have already encountered (e.g. Corollary 1 from Lecture 4, or Theorem 1 from Lecture 5) do not seem to directly establish this result, instead giving the weaker result that every element […]

7 February, 2008 at 10:19 pm

AnonymousDear Prof;

Don’t we need some condition of left continuity on our group S, for the proof of lemma 3 and corollary 4.

9 February, 2008 at 8:01 pm

254A, Lecture 7: Structural theory of topological dynamical systems « What’s new[…] on X forms a group, known as the Ellis group of X. (Hint: use part 3, together with Lemma 3 from Lecture 5.) Show that G is a compact subset of (with the product topology), and that G acts transitively […]

10 February, 2008 at 12:38 pm

254A, Lecture 10: The Furstenberg correspondence principle « What’s new[…] is also a polynomial version of these theorems (cf. Theorem 1 from Lecture 5), which we will also state in general […]

12 February, 2008 at 9:51 am

254A, Lecture 11: Compact systems « What’s new[…] strength of the results, one needs the syndetic van der Waerden theorem, see Exercise 15.3 from Lecture 5, or else apply the Varnavides averaging trick from the previous lecture). We leave the details to […]

28 February, 2008 at 3:51 am

NilaySir

In the topological dynamics version of Hypergraph Ramsey theorem can you explain how the transformation function T behaves? I am unable to understand the notation

28 February, 2008 at 9:34 am

NilaySir

I think the notation generates a different transformation for each . For any .

1 March, 2008 at 9:23 pm

254A, Lecture 12: Weakly mixing systems « What’s new[…] is non-constant. (Hint: you will need the “PET induction” machinery from Exercise 3 of Lecture 5. This result was first established by […]

17 March, 2008 at 2:14 am

liuxiaochuanDear professor：

Here are several corrections:

1,I think after (2), the definition of q’ should be

2,About (3),

, where” = p ” fail to show up. But I saw your latex code is right, I don’t know why this happens.

3,About (4),

… , the bth sub should be . The same problem happens to (9).

4, before (4) and After (7′), the definition of p’ : = +, not ?

Liu

17 March, 2008 at 8:28 am

liuxiaochuanDear professor:

I don’t understand the definition of . Could you explain a little more about it? Is still a homeomorphism on X or not? what is the image of, say, for a ?

Liu

21 March, 2008 at 1:18 pm

Terence TaoDear Liu,

An action T of a group G on a space X is a collection of maps for each group element which preserve the group operations, thus is the identity, inverts , and is the composition of and . See

http://en.wikipedia.org/wiki/Group_action

In this case, X is a topological space, and so we would require our actions to preserve this topological structure, i.e. to be homeomorphisms.

Thanks for the corrections!

22 March, 2008 at 5:15 am

liuxiaochuanDear Professor:

In theorem 5, I wonder if you mean that “ is an open cover of X, such that is – invariant”. If not, that must be my

misunderstanding.

Liu

22 March, 2008 at 2:30 pm

Terence TaoDear Liu: Thanks for the correction!

23 March, 2008 at 7:56 am

liuxiaochuanDear Professor:

I am stuck when I try to prove theorem 4 from theorem 5. When I

consider the subsystem I can’t

find the proper open cover which is -invariant. Please

help me out.

Liu

24 March, 2008 at 7:56 am

Terence TaoDear Liu:

Let’s set and for concreteness. Then the relevant space X should be the space of K-coloured hypergraphs of order k on V (with the obvious action of ), and each for should be the clopen set of hypergraphs in X which assign the colour to the edge .

25 March, 2008 at 9:07 pm

liuxiaochuanDear professor：

I think the conclusion of theorem 5 should be , because only in this case, I can finish the exercises.

Liu

25 March, 2008 at 9:24 pm

Terence TaoAh, I see what happened. It should actually be (though the other formulation you propose is of course equivalent).

30 March, 2009 at 6:52 pm

AnonymousDear professor：

I think in the proof of the proposition 1, it is better to point out that \beta( A^{<\omega} ) does not have an minimal element of \beta (A \cup \{*\})^{<\omega}. So the selected q is not in \beta( A^{<\omega} ).

31 March, 2009 at 4:22 am

Terence TaoThanks, I’ve added a few sentences to this effect.

17 July, 2009 at 7:24 am

liuxiaochuanDear Professor Tao:

In exercise 3 part 2, I am wondering whether or not the degree of the top order monomial of should be asked to have the lowest.

17 July, 2009 at 8:13 am

Terence TaoAh, there was a typo: should have been .

17 July, 2009 at 10:13 am

liuxiaochuanDear professor Tao:

I’m even more confused, to use lemma 2 in the third step, isn’t the correct one in part 2?

17 July, 2009 at 11:19 am

Terence TaoSorry about that; I’ve reverted it. The exercise as originally stated appears to me to be correct, without modification.

18 July, 2009 at 1:46 am

the “epsilon and delta” proof of polynomial Van Der Waerdon theorem « Liu Xiaochuan’s Weblog[…] lecture notes of ergodic theory. I write it separately because it’s a little lengthy. Here is the lecture notes. It is very interesting to contrast this proof with the proof of Hales-Jewett […]

19 July, 2009 at 4:22 am

Several Ramsey-type theorems « Liu Xiaochuan’s Weblog[…] theorem. I wrote a post on the combinatorial proof of this theorem.These are also exercises of Professor Tao’s lecture on ergodic […]

19 July, 2009 at 6:19 am

liuxiaochuanDear Professor Tao:

In the part 4 of exercise 15, I believe the conclusion should be ‘there are infinitely many monochromatic arithmetic progressions ‘of length k’ whose step size lies in S’, with ‘of length k’ missing.

Also, I can’t work out the additional challenge, could you give me a hint?

20 July, 2009 at 5:21 am

Terence TaoThanks for the correction! The additional challenge in 15.4 is proven similarly to the additional challenge in 15.3, i.e. by applying the infinite pigeonhole principle to get a single colour class that works for infinitely many k.

20 July, 2009 at 10:36 am

liuxiaochuanDear Professor Tao:

But I got stuck when trying to prove even one k for a single class. I know from 15.4 that the spacings of arithmetic progressions of length k form a IP*set A. But I can’t figure out why one of the color classes in A should also be an IP*set.

21 July, 2009 at 5:53 pm

Terence TaoThe following model problem might get you started: show that if is finitely coloured, then one of the colour classes contains arbitrarily long arithmetic progressions in the vertical direction, and also arbitrarily long arithmetic progressions in the horizontal direction.

Now, do the same thing for , with the countably infinite number of directions.

An IP set is sort of a less structured version of .

22 July, 2009 at 11:52 pm

liuxiaochuanThere are essentially countably many different IP-sets in ,right?

20 July, 2009 at 10:43 am

liuxiaochuanAlso, about the exercise 3.2, if then the weight vector of with respect to should be and the weight vector of with respect to is also , not strictly smaller than the former one.

21 July, 2009 at 6:16 pm

Terence TaoAh, I see the problem now. Your earlier fix (requiring P_1 to have minimal degree) was the correct one.

29 July, 2009 at 3:42 am

陶哲轩遍历论习题解答：第五讲 « Liu Xiaochuan’s Weblog[…] (注：遍历论为陶哲轩教授于08年年初的一门课程，我尝试将所有习题做出来，这是第五讲的二十一个习题。这里是这门课程的主页，这里是本讲的链接。有一些题目我花费的时间比较多，我将所需要的知识补充在另外的帖子中。关于ultrafilter, 我写过一个帖子.习题一中涉及到一点数论知识，尤其关于二次剩余的知识。我写过一个帖子是关于Hales-Jewett定理的归纳法证明.习题4的解答比较长，我另写了一个帖子。该过程是参考了上一讲中定理四的证明。注意这个证明方法与前述Hales-Jewett定理的归纳证明的异同。仍有几个问题没有完成，我会慢慢补上。) […]

2 August, 2009 at 7:41 am

liuxiaochuanDear Professor Tao:

I still have trouble understanding exercise 3 and ‘PET’ induction method. Lemma 2 enssures the conclusion based on a previously fixed Q and arbitririly chosed . But in exercise 3.2, , which depends on . I got a little confused here.

3 August, 2009 at 1:04 am

liuxiaochuanIt seems OK if we just take as in exercise 3.2.

3 August, 2009 at 5:53 am

Terence TaoFair enough (though, in view of Lemma 1, one could also permit Q to vary with the if one wished.)

7 August, 2009 at 6:52 am

liuxiaochuanDear Professor Tao:

I failed when doing exercise 11. Could you give one more hint, besides the fact that it is similar with the proof of Theorem 4 from the previous lecture.

23 May, 2010 at 8:38 pm

Solutions to Ergodic Theory: Lecture ten « Xiaochuan Liu's Weblog[…] Theorem 9: (IP Szemerédi theorem) Let A be a set of integers of positive upper density, let , and let be infinite. Then A contains an arithmetic progression of length k in which r lies in FS(B), the set of finite sums of B (cf. Hindman’s theorem from Lecture 5). […]

18 June, 2010 at 2:53 am

Solutions to Ergodic Theory：Lecture twelve « Xiaochuan Liu's Weblog[…] is non-constant. (Hint: you will need the “PET induction” machinery from Exercise 3 of Lecture 5. This result was first established by […]

20 June, 2010 at 5:41 pm

Solutions to Ergodic Theory：Lecture Seven « Xiaochuan Liu's Weblog[…] see G is a group, we firstly take a minimal subsystem of X, we have from Ellis-Nakamura lemma from lecture 5 the existence of the identity, i.e. we take the whole equivalence class imdepotent elements as the […]

14 August, 2012 at 1:37 am

Siming TuDear Prof. Tao,

In Lemma 3, Ellis-Nakamura lemma should be Ellis–Numakura lemma. see

http://en.wikipedia.org/wiki/Ellis-Numakura_lemma

[Corrected, thanks – T.]15 September, 2014 at 12:09 am

Boaz TsabanDear Terry, in Remark 1 you take .

Wouldn’t also work, and look more natural?

15 September, 2014 at 6:46 am

Terence TaoThat would also be a counterexample, but a rather degenerate one; the counterexample I selected was intended to resemble the standard Szemeredi example , to illustrate that non-degenerate averaging in r is not sufficient by itself to obtain recurrence.

14 August, 2015 at 8:48 am

AnonymousDear professor Tao,

Is there an ultrafilter version of the “polynomial” Hales-Jewett theorem?

This theorem (as formulated in the paper of Walters you linked) is about (sequences of) multi-dimensional arrays with the same length at each dimension, instead of just one dimensional sequences, so there is no natural semigroup operation analogous to concatenation (that I can see).