Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] An application of VDW theorem to Number Theory- is...

Expand Messages
  • GASARCH
    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
    Message 1 of 1 , Aug 21, 2009
    • 0 Attachment
      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.

      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
    Your message has been successfully submitted and would be delivered to recipients shortly.