Monday, February 23, 2009

Seeking the NON-Elementary proof of...

Consider the following:
Canonical VDW thm: For any k &isin N, for any coloring of N with an infinite number of colors, either
  1. there exists an arithmetic progression of length k where all of the elements are the SAME color, or (e.g, if k=5, 10 RED, 14 RED, 18 RED, 22 RED, 26 RED).
  2. there exists an arithmetic progression of length k where all of the elements are different colors (e.g, if k=5, 10 RED, 14 BLUE, 18 GREEN, 22 YELLOW, 26 PURPLE).
Henceforth I will refer to this as CVDW.

Szemeredi's Thm: Let k &isin N. If A &sube N has positive upper density (liminfn &rarr &infin |A &cap {1,...,n}|/n > 0) then A has an arithmetic sequence of length k.
(Henceforth SZ) I have seen the following statement in two papers and one book (I'll paraphrase.)
It is easy to see that SZ implies CVDW.
  1. I was unable to prove this. If someone out there can supply the easy proof please do so in the comments (my curiosity is far bigger than my ego).
  2. The first step of the proof is obvious: if some color has positive density then we are done. So assume that they all have 0 density. The seconds step MIGHT be to take the set
    { x | COL(x) ¬in {COL(1),...,COL(x-1)}
    and show that it has positive density. But I don't know how to prove that, or if its even true.
  3. If I assume that each color appears finitely often then I can prove there is a colorful k-AP using VDW thm. (I leave this to the reader.)
  4. There is an elementary proof by Promel and Rodl. (An elementary proof of the canonizing version of Gallai-Witt's thm, Journal of Combinatorial Theory A, Volume 42, Pages 144-149, 1986. I have not been able to find it online, so if someone knows an online version let me know.) They actually show (as the title indicates) an elementary proof of the Canonical Gallai-Witt thm (multidim VDW), which I won't go into here. I have written up just the elementary proof of CVDW here: writeup.
LATE EDIT (Feb 26, 2009): One of my readers send me an ONLINE version of the paper. It is now at originalpaper.


  1. The seconds step MIGHT be to take the set...and show that it has positive density. But I don't know how to prove that, or if its even true.

    It's not true. Consider the coloring: 1 1 2 1 2 3 1 2 3 4 1 2 3 4 5 ...

    The set you defined has density 0, and any individual color also has density 0.

  2. (As a note, "upper density" is a limsup.)

  3. If all densities are zero, it seems to work to pick the progression x,x+y,x+2y,... where x and y are uniformly random in the interval [1,K] for large enough K: as K -> infinity, w.h.p. the progression will have no repetition.

  4. This comment has been removed by the author.

  5. I believe I can give the proof. But first I'd like to observe: the previous suggestions seem to falter because Bill's assertion #3 is fishy: it's not even true that if every color class is finite, then there exists a rainbow/colorful 4-AP.

    To see this consider, e.g., the coloring in which the ith color takes up a block of length 5^i. Say a 4-AP begins in block i and has second element in block j > i. Then the common difference d for the 4-AP is (crudely) at most 2*5^j. It follows that whatever block k > j the third element falls into, the fourth element will also fall in block k.

    OK, so here's an alternative approach: use the *finitary* statement of Szemeredi's Thm, which follows from the infinite version by a well-known compactness argument (see Terry Tao's several posts on the subject). The finitary version says:

    For any k, eps > 0, there exists an N = N(k,eps) such that if S \subseteq [0, 1, 2,..., N - 1] has density at least
    eps in that interval, S contains a k-AP.

    So, here's my proof assuming the above: given k, let eps > 0 be chosen tiny compared to k (how tiny we need will become clear to the author later). Let N = N(k, eps). Let rho be a coloring. If there exists a color with density at least eps in [0, 1, ...N-1], we're done, so assume this is not the case.

    Pick a random pair (a, d) uniformly from [0, ... N - 1]^2, and define the set

    A = {a + jd (mod N)| j=0, 1, ... k - 1},
    a k-AP over Z_N.

    (Of course, we really want an integer progression... but things will work out.)

    Note that for distinct indices j, j', the random variables (a + jd), (a + j'd) (both mod N) are pairwise independent (PI). Let X_{j, j'} be the indicator variable for the event that these points have the same color in rho. Using PI we see that E[X_{j, j'}] <= 1/eps, so E[Sum X_{j, j'}] <= O(k^2/eps). So if eps = o(1/k^4) this is o(1/k^2), and with high probability the Z_N k-AP is colorful.

    We wanted an integer k-AP. But, one way to get this is just to have the event
    {a <= N/(2k) , d <= N/k} so that no 'wraparound' occurs. This occurs with probability
    ~ 1/(2k^2). So, with prob. (1 - o(1))/(2k) we succeed in finding a colorful integer k-AP.

  6. Sorry, last quantity should be
    (1 - o(1))/(2k^2).

  7. Also, I think I shouldn't have called Bill's #3 'fishy'. I guess what was meant is that if we *also* assume no monochromatic k-AP, then there exists a colorful k-AP. I can't argue with this.

  8. What does VDW mean?

  9. ANDY D- THANKS for the proof.
    Here is what I wonder--- is
    what they had in mind when various
    authors said it followed
    ``obviosul'' from Sz theorem?
    Not obvious to me, but it could be
    what they meant. ANy thoughts?
    easier proofs?

  10. Hi Bill,
    I couldn't say whether something like this proof was what the authors had in mind. By the standards of the field it probably counts as obvious, but I wouldn't use such language if I were trying to write a friendly & accessible survey.
    It's certainly possible there is a simpler reduction (and, e.g., mine could definitely be retooled to avoid modular arithmetic), but I don't see it. In particular, is the switch to the finitary version needed?