*[Bill Gasarch, known online for his frequent contributions to the Complexity Blog and for his liberal USE of capital LETTERS, has been reading about the “polynomial” and “multi-dimensional” versions of van der Waerden’s theorem (the original theorem being “linear” and “one-dimensional”) and he is going to tell us about it. Enjoy. — Luca]*

Guest Posting by William Gasarch (gasarch@cs.umd.edu)

This is a one of two Guest Posting on the Polynomial van der Waerden Theorem (henceforth Poly VDW). This posting is on the one-dimensional Poly VDW; however,my next posting will be on the Multidimensional Poly VDW. Throughout this posting `Poly VDW’ means `One Dimensional Poly VDW’

Our starting point is VDW’s theorem, which is the same starting point Luca had in his postings on Szemeredi’s theorem. (here, here, here, here, and here.) But I go in a different direction.

**VDW’s:**

For all , for any -coloring , there exists , , such that

The original proof ofVDW’s Theorem was an induction on the following ordering on

For example the proof of depends on the theorem being true for where is very large. Shelah (Primitive recursive bounds for van der Waerden numbers, Journal of the American Math Society, Vol 1, 1-15, 1988) has a proof that avoids this type of induction and hence yields a much slower growth rate for the VDW numbers (which we are not discussing here).

Consider the functions

One may consider replacing with polynomials in . This leads to the following theorem.

**Poly VDW:**

For all , for all such that , for any -coloring there exists , , such that

The condition is needed since if the ‘s were constants the theorem would be false. It is an open problem to look at particular sets of polys with constant term.

This was first proven by Bergelson and Leibman (Polynomial extensions of van der Waerden’s and Szemeredi’s theorems, Journal of the American Math Society, Vol. 9, 1996, 725–753.)

The proof uses ergodic (non-elementary) techniques. They actually proved a density version.

**Density Poly VDW:**

For all such that , for all sets of positive density, there exists , , such that

Walters has a purely combinatorial proof of the Poly VDW Theorem (Combinatorial Proofs of the Polynomial van der Waerden Theorem and the Polynomial Hales-Jewitt Theorem Journal of the London Math Society, Vol 61, 2000, 1-12.)

The proof used an ordering as follows.

For every finite set such that we associate a tuple where the largest degree polynomial in is degree , and, for all , , is the number of different coefficients of that occur in polynomials of degree in .

Let mean that Poly VDW holds for all sets of polys of type . The ordinary VDW theorem can be viewed as .

The Poly VDW is proven by induction on the following -ordering. Let .

- If then .
- If then order lexicographically. (e.g., )

Having stated the Poly VDW one can now state a version of VDW over any infinite Commutative Ring (think Reals).

**Gen Poly VDW:**

Let any infinite commutative ring. For all , for all such that , for any -coloring there exists , , such that

This was proven by by Bergelson and Liebman (Set-polynomials and Polynomial extension of the Hales-Jewett Theorem, Annals of Math, Vol. 150, 1999, 33-75.}

The proof is in two steps

- Prove the Poly Hales-Jewett Theorem (henceforth Poly HJ). (This proof is not elementary.)
- Prove Gen Poly VDW from Poly HJ.

(This part was elementary.)

There is a purely combinatorial proof of the Gen Poly VDW theorem, though it is not stated in the literature:

- Walters has a combinatorial proof of the Poly Hales Jewitt Theorem in the paper of his mentioned above.
- As noted above, Bergelson and Leibman showed how to get from the Poly HJ Theorem to the Gen Poly VDW Theorem.

**Coda 1:**

Green and Tao proved that the set of primes has arbitrarily long arithmetic progressions.

More recently, Tao and Ziegler: have shown the following:

For any such that , there exists , , such that

are all prime

**Coda 2:**

The Maryland Math Olympiad is in two parts. Part I is 25 multiple choice questions (but some are quite hard). If you do well on part I then you can take part II which is 5 problems that need proof. We try to number the problems in order of difficulty. I placed the following problem on the 2006 High School Maryland Math Olympiad, as problem 5:

*Let be a 3-coloring of . Show that there exists such that and is a square.*

Of the 240 students who took the exam around 180 tried this one. Of those 5 got it right and 10 got partial credit. The proof I had in mind (which is the one the students used who got it right) is not a scaled down version of the proof of the poly VDW. I leave it to the reader to see if they can prove this.

## 5 comments

Comments feed for this article

January 19, 2007 at 11:02 pm

D. EppsteinWas that the exact wording of the Olympiad problem? Because as stated it is trivially solved by letting y=x.

January 19, 2007 at 11:50 pm

GASARCHAH- the exact wording did not allow x=y.

It was

“Each positive integer is assigned one

of three colors. Show that there exist

distinct integers x,y such that x and y

have the same color and |x-y| is a perfect

square.”

At the last minute the committee took out

the 2006 stuff- I prefer it with

3-coloring {1,…,2006}.

THANKS for the opp to clarify

January 20, 2007 at 6:37 pm

Anonymous{ 0, 9, 25, 34, 50, 59, 75, 84, 100, 109, 125, 134, 150, 159, 175, 184, 200, 209, 225 }

seems enough …

January 21, 2007 at 12:00 am

eladIs the following generalization true for every k?

“Each positive integer is assigned one

of k colors. Show that there exist

distinct integers x,y such that x and y

have the same color and |x-y| is a perfect

square.”

January 22, 2007 at 4:17 am

GASARCH(Bill G here in case it accidentally

says that I am anonymous)

YES the theorem is true for

any k. That is, if you

k-color N YES there will be

x,y different |x-y| a square,

x,y same color. This is easy

corollary of poly vdw theorem

in the posting. BUT there is a

GOOD question here: is there

a HS-level proof of this for

k=4? general k? I have not been

able to find one. (Most HS student

do not know the poly vdw theorem

and the proof is not something

they could come up with.)

SO-if someone can come up with

a HS level proof of k=4 case,

I would be very interested.

bill g.