*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.**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.

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 p_{0}such that, for all primes p > p_{0}there are k consecutive QR in Z_{p}(the integers mod p).**Proof**: Let p_{0}=W(2k+1,2). Let p > p_{0}. 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 thata, 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 thatad

are all QR. Note that the addition is mod p so it may be the case that we have something like^{-1}, ad^{-1}+dd^{-1}, ad^{-1}+2dd^{-1},..., ad^{-1}+2kdd^{-1}= ad^{-1}, ad^{-1}+1, ad^{-1}+2, ..., ad^{-1}+2kp-4, p-3, p-2, p-1, 0, 1, 2, 3, ...

Since there are 2k of these elements, there must be k truly consecutive.

**END OF PROOF**

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.

--

Posted By GASARCH to Computational Complexity at 8/21/2009 12:48:00 PM