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.

  • 0
    okay, thanks. Any idea about the second question?2012-07-12