12
$\begingroup$

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$?

Improve this question
$\endgroup$
5
  • $\begingroup$ 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$. $\endgroup$
    – Greg Martin
    Commented Jan 14, 2012 at 6:03
  • 1
    $\begingroup$ 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. $\endgroup$
    – user6976
    Commented Jan 14, 2012 at 8:24
  • $\begingroup$ 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.) $\endgroup$
    – Pace Nielsen
    Commented Jan 17, 2012 at 19:28
  • $\begingroup$ 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$. $\endgroup$
    – Pace Nielsen
    Commented Jan 17, 2012 at 19:43
  • $\begingroup$ 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$". $\endgroup$
    – Kevin P. Costello
    Commented Jan 28, 2012 at 4:14

2 Answers 2

Reset to default
6
$\begingroup$

They grow very fast. Denote by N(l) the largest integer such that we can color the numbers with two colors from 1 to N(l) without an l-long arithmetic progression. Now if you use this coloring for (k-1)/2-long sequences and put such colorings after each other, then any k-long arithmetic progression will be longer than N((k-1)/2), which means that even its difference will be at least N((k-1)/2)/k, which is HUGE.

Improve this answer
$\endgroup$
0
0
$\begingroup$

I believe this question is discussed at great length in Graham Rothschild's/Spencer's "Ramsey Thory" book (page 68 and on), and cannot really be done justice here. The bounds are very, very, very large (recursively computable is about as much as one can say).

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ 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. $\endgroup$
    – Pace Nielsen
    Commented Jan 13, 2012 at 21:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .