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:
-
This can be proven from the Hales-Jewitt theorem.
(Advantage: automatically get out the full
Gallai-Witt theorem with this approach.)
-
This can be proven from the Gallai-Witt theorem trivially.
-
This can be proven by using VDW theorem on the diagonal.
-
This can be proven by using VDW theorem on the side.
-
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.
-
Is there a proof either from scratch, from poly vdw, or from Ordinary HJ?
If so then please comment.
-
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.)
Very neat problem...rjlipton
ReplyDeleteI 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
ReplyDeleteHi Bill,
ReplyDeleteNice problems... in both, do you mean axis-parallel?
YES in both problems I DO mean
ReplyDeleteaxis-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.
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.
ReplyDeletesatisfy 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 ...
ReplyDeleteAndy Parrish is, of course,
ReplyDeletecorrect--- solving the
non-ness-axis-parallel may lead to insights for the problem I am asking about.
OKAY- SOMEONE- please solve.
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?
ReplyDeletenever mind, I found the information from Bill's post here: http://lucatrevisan.wordpress.com/2007/01/26/the-multi-dimensional-polynomial-van-der-waerden-theorem/
ReplyDeleteI love this problem!