Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm revising a few past papers on Ramsey theory and I've come across a question which feels like it should be easy if it weren't so confusingly set up - I was hoping someone here could help me make some sense of it (perhaps not with a full answer necessarily but with an explanation of what to actually try and do, since this question is for revision purposes). The question is as follows:

Let $c$ be a colouring of $\mathbb{N}$ using (possibly) infinitely many colours, and let $m \in \mathbb{N}$. Given $x_1,...,x_m \in \mathbb{N}$, let $e(x_1,...,x_m)$ denote the equivalence relation $\sim$ on $\{1,...,m\}$ given by $i∼j \Longleftrightarrow c(x_i)=c(x_j)$, $1\leq i,j \leq m$, and define a (finite) colouring $c'$ of $\mathbb{N}^2$ by setting $c'(a,d)=e(a,a+d,a+2d,...,a+(m−1)d)$, $a,d \in \mathbb{N}^2$.

By applying Gallai’s theorem, deduce that there is an arithmetic progression of length m on which c is either constant or injective.

Firstly for anyone who isn't aware, Gallai's theorem states that whenever $\mathbb{N}^d$ is finitely coloured (any $d$), then for any finite $S \subset \mathbb{N}^d$ there exists a monochromatic homothetic copy of $S$, meaning a monochromatic $x_0 + \lambda S$ for some $\lambda$. So the question seems to want me to pick some $S$ in $\mathbb{N}^d$ for which a homothetic copy will correspond to a monochromatic arithmetic progression.

Normally you would use Van der Waerden's theorem for monochromatic arithmetic progressions (which you can clearly prove by applying Gallai's theorem to a series of consecutive points), but here you have infinitely many colours so that won't work. I should add that for finitely many colours, VdW is a trivial corollary of Gallai.

I guess what I'm having trouble with is the peculiar equivalence relation. We use it to induce a "colouring" on $\mathbb{N}^2$ where each "colour" is actually one of the possible equivalence relations, so each point in $\mathbb{N}^d$ corresponds to an arithmetic progression of length $m$. Considering the definition of the equivalence relation $e(x_i)$, it becomes clear that the result we want corresponds precisely to the case when this is one of the 2 trivial equivalence relations; everything is related ($c$ constant on the AP) or nothing is related ($c$ injective on the AP).

So, I think proving this would require only that we show some point in $\mathbb{N}^2$ has the "colour" of one of the 2 trivial equivalence relations. Presumably this is what we somehow need to do, via Gallai. However, I can't figure out how you're meant to actually apply the theorem. I tried applying it to the obvious sets of points in $\mathbb{N}^2$ which I could think of - a vertical/horizontal/diagonal line segment or a (filled) square, but having a homothetic copy of one of these in which all the equivalence relations are the same didn't get me to the solution. The result of this seems to be that you get many many "equivalence relation equivalences" (if you'll forgive the phrase), such as $c(a) = c(a + d)$ iff $c(a+\lambda) = c(a+ d + \lambda)$ iff... and lots more similar equivalences.

I thought maybe you could use these to show that there is some point in $\mathbb{N}^2$ for which the equivalence relation $e(x_1,x_2,\ldots,x_m)$ satisfies $c(x_1) = c(x_2)$ iff $c(x_2) = c(x_3)$ iff $\ldots$ $c(x_m) = c(x_1)$; if we could "loop back around" to the start of the equivalence relation again, then we could get something like the above: but that precisely says the relation is one of the two trivial relations (depending on whether or not $c(x_1) = c(x_2)$). I haven't been able to do something like this though I'm afraid; I'm unable to control the fact that the common difference $d$ you get from the point $(a,d)$ may be totally difference to any sort of "induced common difference" $\lambda$ you get from the fact points in the homothetic copy will be spaced $\lambda$ apart.

Am I anywhere close to doing the right thing? Or is there some clever trick I'm missing? This problem is meant to be doable in half an hour at most, and much of that time might be earmarked for figuring out what on earth the question is asking. Thanks all for your help!

share|cite|improve this question
up vote 1 down vote accepted

This exposition gives a proof. It uses a big square $[0,2M]^2$ and argues that in the homothetic copy $(a_0+D[0,2M])\times(d_0+D[0,2M])=:(a+D[-M,M])\times(d+D[-M,M])$ either the central progression corresponding to $(a,d)$ is injective or it contains two equal colours at $a+xd$ and $a+yd$, and in the latter case, the progressions corresponding to $(a+D(-xj),d+Dj)$ for $0\le j\lt m$ take the value $a+D(-xj)+x(d+Dj)=a+xd$, and since all the progressions induce the same equivalence relation, the colour at that point must be that of all the corresponding points $a+D(-xj)+y(d+Dj)=a+yd+jD(y-x)$, which form an arithmetic progression of length $m$. This works if $M=(m-1)^2$.

share|cite|improve this answer
Very interesting, many thanks again for your help Joriki. I should have guessed it should be called the "canonical" version of the thoerem, would have made finding that paper a little simpler. – Spyam May 11 '12 at 22:16

Your Answer


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.