Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 1 down vote accepted
+50

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.

share|improve this answer

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.

share|improve this answer
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? –  Shahab Jul 9 '12 at 13: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. –  Stefan Geschke Jul 10 '12 at 5:43
    
okay, thanks. Any idea about the second question? –  Shahab Jul 12 '12 at 7:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.