MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

Define a length $k$ arithmetic progression in $\mathbb{Z}_p$ to be a set of the form $\{ax+b : x \in [k]\}$ with $a \in \mathbb{Z}_p^*$ and $b \in \mathbb{Z}_p$. Let $HJ(k, c)$ be the Hales-Jewett number for length $k$ hypercubes and $c$ colors. If $p > HJ=HJ(k, c)$ then every $c$-coloring of $\mathbb{Z}_p$ contains a monochromatic length $k$ arithmetic progression: On the cube $[k]^{HJ}$ color the coordinate $(a_1, \ldots, a_{HJ})$ the same color as $a_1 + \ldots + a_{HJ}$. Monochromatic combinatorial lines correspond to monochromatic arithmetic progressions.

My question is, is there a proof that produces better bounds? Is there any way to take advantage of the structure of $\mathbb{Z}_p$? And has someone studied this problem before?

share|cite|improve this question
I think it's known to be essentially equivalent: you can just put all the points in $\lbrace 0,\ldots,(p-1)/2\rbrace$ and the arithmetic progressions are the same as the ones in $\mathbb Z$. – Anthony Quas Feb 15 '13 at 6:57
You mean $\mathbb{Z}/p\mathbb{Z}$? Or really $\mathbb{Z}_p$? – Vladimir Dotsenko Feb 15 '13 at 17:07
@Vladimir Dotsenko: now, while personally I prefer your usage, for a request like yours I'd say to avoid potential endless confusion one should that you mean the p-adic integers with the latter – quid Feb 15 '13 at 17:58
@quid: agreed.... – Vladimir Dotsenko Feb 19 '13 at 16:32
up vote 1 down vote accepted

A question that received a lot of attention over the last years are quantitative refinements of Szemerédi's theorem, a generalisation of van der Waerden's Theorem asserting that fixing any positive density $d$ one will find arithemetic progressions in a set of that density provided the initial segment of integers one considers is large enough. (If one has $c$ colors one is certainly guaranteed a set of density $1/c$ with all elements the same color.)

Now, it is known that one even can let the density go to zero (sufficiently slowly depending on the size of the initial segment). How slowly is not quite clear, and this is what these quantitiative refinemenets are about. See also for a conjecture regarding this.

For (recent) contributions on this see, e.g.,

  1. a paper giving much better bounds in general ($k$ arbitrary) than known before, by Gowers for the general case

  2. the to my knowledge currently best bounds for $k=4$ by Green and Tao

  3. the to my knowledge currently best bounds for $k=3$ by Sanders

A feature these three papers share is that they take a Fourier analytic approach to the problem. And for this it is advantageous to work over a finite (prime) cyclic group rather then over the integers. Note that while all three papers phrase the main relsult for integers, for the proof they actually pass to a finite (prime) cyclic group.

I am not sure this answer is exactly what you are looking for, as while the problem is in some sense essentially the same it might (or might not) be the case that you are looking for results of a somewhat different flavor (say, less 'asymptotic').

In any case, working over a prime cyclic group certainly has some advantage and the problem in this context was considered a lot; indeed many of the recent works in this context even if at first glance for integers in the end are results for (prime) cyclic groups. Yet, there is not a huge difference in the bounds in the end for the reason Anthony Quas mentioned.

share|cite|improve this answer

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.