4
$\begingroup$

I have the following statement which is claimed to be a version of Van der Waerden's theorem:

For any finite partition of $\mathbb{N}$, one of the cells contains affine images of every finite set.

This statement is taken from the book Elemental methods in ergodic ramsey theory.

The affine version of the Van der Waerden's theorem I had understood before was:

For any finite partition of $\mathbb{N}$ and any finite subset of $\mathbb{N}$, one of the cells contains an affine image of it.

My first question is, isn't this what the book actually means, because it's not quite clear to me how the two statements are linked? My second question is, how to show that the above affine version is equivalent to the statement obtained by replacing $\mathbb{N}$ by $\mathbb{Z}$?

Thanks for your time.

2 Answers 2

1

For the second question, first note that a finite subset doesn't care whether it belongs to $\mathbb Z$ or $\mathbb N$ (every finite subset of $\mathbb Z$ is affinely equivalent to a finite subset of $\mathbb N$).

By Stefan's answer, it is enough to show the equivalence for arithmetic progressions.

Take any finite partition of $\mathbb N$, and extend it to $\mathbb Z$ by putting $-x$ in the same cell as $x \in \mathbb N$ (give $0$ its own unique cell). Now suppose some cell of $\mathbb Z$ contains a progression $P$ of length $2r$. Then either $P$ or $-P$ has a majority of positive numbers, giving a progression of length at least $r$ contained entirely in $\mathbb N$. Thus the original partition of $\mathbb N$ had a cell with a progression of length $r$.

The above argument shows that (statement with $\mathbb Z$) implies (statement with $\mathbb N$). The converse direction is trivial, since any finite partition of $\mathbb Z$ induces a finite partition of $\mathbb N$ in the obvious way.

3

Note that an arithmetic progression of length $n$ is the same as an affine image of $\{1,\dots,n\}$.
If $F$ is a finite subset of $\mathbb N$, then every arithmetic progression of length $\max F$ contains an affine image of $F$.

It follows that we only have to worry about arbitrarily long arithmetic progressions instead of affine images of finite sets.

Now, if for each $n$ there is a cell of the finite partition of $\mathbb N$ that contains an arithmetic progression of length $n$, then, by the finiteness of the partition, one cell of the partition is good for infinitely many $n$. This cell now contains arbitrarily long arithmetic progressions and therefore affine images of all finite sets.

  • 1
    Could you elaborate on your statement: " by the finiteness of the partition, one cell of the partition is good for infinitely many $n$." Am I correct in assuming that any infinite cell would be good enough?2012-07-09
  • 1
    If your partition had infinitely many cells, it might happen that the $n$-th cell contains arithmetic progressions of length $n$, but not longer. In this case you cannot conclude that there is one cell with arbitrarily long arithmetic progressions. But if there are only finitely many cells and for each $n$ there is a cell that has an arithmetic progression of size $n$, then there is one cell that works for infinitely many $n$. This is just the pigeon hole principle.2012-07-10
  • 0
    okay, thanks. Any idea about the second question?2012-07-12