Friday, August 21, 2009

An application of VDW theorem to Number Theory- is there a better proof?

I present what may have been the first Application of van der Waerden's Theorem. I also ask the question: Is there an alternative proof? This would be interesting since the hope is that an alternative proof would have better bounds.

Notation: [W] is the set {1,...,W}, QR means Quadratic Residue (square root mod p, where p will be understood), QNR means NOT a Quadratic Residue.

VDW Theorem: For all k, for all c, there exists W such that for all c-colorings of [W] there exists a,d (d &ge 1) such that a, a+d, ..., a+(k-1)d are all the same color.
One might wonder- can we also have d be that color? How about a multiple of d? OKAY, you might not wonder that, but the answer is YES and we need this extension of VDW for our application:
Extension of VDW Theorem: For all k, for all s, for all c, there exists W such that for all c-colorings of [W] there exists a,d (d &ge 1) such that a, a+d, ..., a+(k-1)d, sd are all the same color.
See this excerpt from my book for a proof. (We only need the s=1 case, but this version with general s is no harder and is used in a proof of Rado's theorem.)

Before presenting the theorem duh jour and its proof we quote Karen Johannson's excellent Masters Thesis Variations on a theorem by van der Waerden (2007 from The University of Manitoba, Dept of Mathematics)
Historically, the first application of van der Waerden's theorem may be due to Brauer who proved a conjecture of Schur about quadratic residues. Brauer used a generalization of van der Waerden's theorem, which he attributed to Schur. The following theorem is a further generalization of Brauer's result. The proof is now folklore and I have been unable to locate the original source. The details appear, for example, in (she gives ref to TO GRS book on RAMSEY THEORY, page 70). (She then gives the statement and proof of what I called above Extension of VDW. I suspect that Brauer only proved the s=1 case since that is all he needed.)
We won't restate or prove Extension of VDW, but we give the theorem on QR's that uses it.
Theorem: For all k there exists p0 such that, for all primes p > p0 there are k consecutive QR in Zp (the integers mod p).
Proof: Let p0=W(2k+1,2). Let p > p0. Color [p] as follows:

COL(x) = 1 if x is a QR mod p, 0 otherwise.

By The Extended VDW theorem, with s=1, there is a, d such that
a, a+d, a+2d, ..., a+2kd, d
are either all QR or all QNR. Let d-1 be the inverse of d mod p. Since the product of two QR'is a a QR and the product of two QNR's is a QR (that is not a typo- it really is true) we have that
ad-1, ad-1+dd-1, ad-1+2dd-1,..., ad-1+2kdd-1 = ad-1, ad-1+1, ad-1+2, ..., ad-1+2k
are all QR. Note that the addition is mod p so it may be the case that we have something like
p-4, p-3, p-2, p-1, 0, 1, 2, 3, ...
Since there are 2k of these elements, there must be k truly consecutive.


Note that the bound, W(2k+1,2) is quite large. A proof that avoids VDW would hopefully yield a better bound. Is there one?

The same theorem for QNR's is also true with a proof that uses VDW's theorem. I leave that for you to figure out.


  1. Here's a problem that I don't see a way around:

    What if d is a multiple of p? (For example, if you treat 0 as a quadratic residue, all multiples of p will be an infinite arithmetic progression.)

    Then d inverse mod p doesn't exist and you don't get anything.

  2. Boris, Thanks for your question.

    Recall that in VDW or extended VDW we get
    that if we c-color
    [W] we get a monochromatic
    k-AP. That entire k-AP is
    contained in [W]. Hence we
    have to have d &le W, and in
    particular we cannot have
    that W divides d.

    So when we 2-color [p]
    and use VDW the d that we
    get is such that d&le p
    and hence p cannot divide d.

    bill g

  3. Wow, I feel incredibly stupid! Thank you, Bill, for correcting my misunderstanding.

    My excuse: I was using the infinitary version of van der Waerden's theorem, and as such was coloring all of the integers. I don't know why I was doing that, considering your proof is very clear that you are using the version with bounds, and that you're coloring [p], not Z.

  4. It feels like there should be some sort of argument making use of the fact that the Quadratic Residues are in a certain sense pseudorandom.

    For example, if the appropriate Gowers norm of the set of residues is small, then we know that there should be approximately the same number of progressions in the residues as there are in a random set of density 1/2, which would be enough once p becomes much larger than 2^(2k).

    Is there a known estimate along those lines?

  5. One can look at the affine curve defined by x_1^2 + 1 = x_2^2 + 2 = x_3^2 + 3 = ... = x_k^2 + k modulo p, and then apply the Riemann hypothesis for curves (Weil) to it. If some things about irreducibility check out, then this should actually give an asymptotic on the number of solutions modulo p (about p/2^k?), not only their existence.

  6. The set QR has very small fourier coefficients (this is the gauss sum). This implies the result, with (1/2^k) density.

  7. Does the proof via density give better bounds then the proof via VDW?

  8. According to my colleague's calculations, the proof via the Riemann Hypothesis for curves (proven by Weil around 1940) gives a bound of k^2 * 4^(k+1) at worst, but this can likely be marginally improved.

  9. Boris, if you or someone writes this up, please send it to me--- I am both interested in when Ramsey Theory is used to proof something AND when it is no longer needed.
    I would post a writeup of what I put on the blog AND your write up both on my

    bill g.

  10. Very cool application of VDW! I wonder if there is a compilation of surprising uses of VDW (or maybe Ramsey Theory) in atypical areas. I know a lot of topological proofs that use VDW but this is the first NT one I have seen. Again, very cool!