# Density in van der Waerden's theorem

Color the positive integers using just two colors. By van der Waerden's theorem, we can find a $k$-term arithmetic progression as long as we consider a long interval.

I imagine it is possible to find a $k$-term arithmetic progression so that the terms in the progression have minimal gaps by possibly taking an even longer interval (of some fixed size depending only on $k$). If so, how do these minimal gaps behave as a function of $k$?

-
Can you clarify what you mean by "minimal gaps"? I imagine it might be possible, for every integer $G$, to construct a two-coloring of an arbitrarily long interval that has no $k$-term progression with gaps less than $G$. – Greg Martin Jan 14 '12 at 6:03
As I understand the minimal gap is this: given a coloring $c$ and $k$, $g_c(k)$ is the minimal step of a $k$-term monochromatic arithmetic progression. Question: what can be the growth of $g_c(k)$ (for a given $c$). In particular, what can be the maximal possible growth? One upper bound is given by the van der Waerden proof (and does not depend on $c$), for example, but that does not seem to be optimal. For example, I am not even sure that $g_c(k)$ cannot always have a linear upper bound (depending on $c$). Of course the OP may have a different question in mind. – Mark Sapir Jan 14 '12 at 8:24
Mark, that is exactly what I had in mind (in the case when we restrict ourselves to only 2 colors). So by "gap" I meant the distance between term consecutive terms in the arithmetic progression. To give a few concrete examples: if k=2 then the worst minimum gap (for an arbitrary coloring) is eventually 2, since the worse case is "color even numbers one color, and color odd numberss the other color." So the spacing in the smallest arithmetic progression is 2. (Note: In any other coloring the minimum gap in a 2-term arithmetic progression is 1.) – Pace Nielsen Jan 17 '12 at 19:28
It is not hard to see that $g(k)=max_c \{g_c(k)\}$ is bounded below by a linear function in $k$. Just consider the coloring where we take $k−1$ terms of one color, followed by $k−1$ terms in the other color, etc.... This proves that $g(k)≥2k-2$. – Pace Nielsen Jan 17 '12 at 19:43
It's not quite the same problem, but you may want to take a look at "Finite Analogs of Szemeredi's Theorem" by Raff and Zeilberger (math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/szemeredi.html ), where they look at questions along the lines of "How dense can a set be and still avoid progressions of length $k$ having difference at most $D$". – Kevin P. Costello Jan 28 '12 at 4:14

I believe Gowers bound beats that. But my question isn't about the size of the van der Waerden numbers, but rather about the gap sizes in the "densest" length $k$ arithmetic progression under that coloring. – Pace Nielsen Jan 13 '12 at 21:47