Thursday, March 05, 2009

Seeking an EASIER proof of s x s^2 theorem

Consider the following theorem:
For any finite coloring of NxN there exists a square such that all corners are the same color.
There are several proofs of this:
  1. This can be proven from the Hales-Jewitt theorem. (Advantage: automatically get out the full Gallai-Witt theorem with this approach.)
  2. This can be proven from the Gallai-Witt theorem trivially.
  3. This can be proven by using VDW theorem on the diagonal.
  4. This can be proven by using VDW theorem on the side.
  5. This can be proven by directly. It has a VDW flavor to it but can be shown to HS students who have not seen VDW theorem (I've done it).
The following theorem can be proven from the polynomial Hales-Jewitt Theorem:
For any finite coloring of NxN there exists an s &ge 2 and an s by s2 rectangle such that all corners are the same color.
I have tried to prove this from scratch, from Poly vdw theorem, from Gallai-Witt, from ordinary Hales-Jewitt. Have not managed it.
  1. Is there a proof either from scratch, from poly vdw, or from Ordinary HJ? If so then please comment.
  2. Normally one asks for an elementary or (I prefer the phrase) purely combinatorial. Even so, I can't rephrase my question with this term since there is a purely combinatorial proof of Poly Hales-Jewitt. (See either Walters paper or the rough draft of the book on VDW stuff I am co-authoring with Andy Parrish pages 77-89.)


  1. I have a meeting in a minute-so this may be very half baked. Did you try using the polynomial method. Its likely you might be able to write down a polynomial for each prime p so that counts the number non-solutions mod p. Then, use Chevalley-Warning and Ax to get a contradiction....there will be too many non-solutions...dick

  2. Hi Bill,

    Nice problems... in both, do you mean axis-parallel?

  3. YES in both problems I DO mean
    axis-parallel. Though axis-not-necc parallel might be a good problem also.
    The axis-parallel problem proofs
    lead to VDW_type large bounds
    on things. the axis-not-necc-parallel
    might lead to much smaller numbres.

    But for now, lets solve THIS problem.

  4. Bill, that seems closed minded to demand first a solution to exactly the problem you asked. Doesn't math teach us that the best way to solve a problem is often to solve a different problem first and then get the desired result as a corollary? Perhaps there's a really neat way to force a rotated n by n^2 rectangle which we could generalize to get one parallel to the axes.

  5. satisfy condition В of Theorem В and. (ii) {pv2}v is bounded away from one. Proof: From condition (i) and Theorem B, Sx2lsx * 1. Now we can write sxs. 2„ 2 ...

  6. Andy Parrish is, of course,
    correct--- solving the
    non-ness-axis-parallel may lead to insights for the problem I am asking about.
    OKAY- SOMEONE- please solve.

  7. Bill - this is an interesting problem. Can you describe in your own language the intuition behind: 1) the direct proof of s x s, 2) the combinatorial extension of HJ to poly HJ?

  8. never mind, I found the information from Bill's post here:

    I love this problem!