Monthly Archive

You are currently browsing the monthly archive for January, 2007.

Conquering Hearts, Minds, and Bumpers

January 29, 2007 in politics | 9 comments

In Baghdad.

The Multi-dimensional Polynomial van der Waerden Theorem

January 26, 2007 in math | Tags: Bill Gasarch | Leave a comment

[This is the second part of Bill Gasarch's guest post on "polynomial" versions of van der Waerden's theorem. -- Luca]

This is a the second of two Guest Postings on the Polynomial VDW Theorem. This one is on the Multi-dimensional Poly VDW Theorem.

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) and I had in my first posting.

VDW:
For all ${c,k\in N}$ , for any ${c}$ -coloring ${COL:Z \rightarrow [c]}$ there exists ${a,d\in Z}$ , ${d\ne 0}$ , such that

${COL(a) = COL(a+d) = COL(a+2d) = \cdots = COL(a+(k-1)d).}$

What would a multidimensional version of VDW look like? What would a multidimensional version of Poly VDW look like? Before stating that, we give corollaries to both to provide the flavor.

Corollary of Two-dimensional VDW:
For all ${c}$ , for any ${c}$ -coloring ${COL: Z\times Z\rightarrow [c]}$ , there exists a square with all corners the same color. (Formally there exists ${a,b,d}$ , ${d\ne 0}$ , such that

${COL(a,b)=COL(a+d,b)=COL(a,b+d)=COL(a+d,b+d).}$

Think of this as

${COL((a,b)+d(0,0))=COL((a,b)+d(1,0))=}$
${COL((a,b)+d(0,1))=COL((a,b)+d(1,1)).}$ )

Corollary of Two-dimensional Poly VDW:
For all ${c}$ , for any ${c}$ -coloring ${COL: Z\times Z\rightarrow [c]}$ , there exists a rectangle with all corners the same color where the side is the square of its length. (Formally there exists ${a,b,d}$ , ${d\ne 0}$ , such that
${COL(a,b)=COL(a+d,b)=COL(a,b+d^2)=COL(a+d,b+d^2).}$
Think of this as
${COL((a,b)+(0,0))=COL((a,b)+d(1,0))=}$
${COL((a,b)+d^2(0,1))=COL((a,b)+d(1,0)+d^2(0,1)).}$ )

In the full Multidimensional theorems the set ${\{ (0,0), (0,1), (1,0), (1,1) \}}$ will be replaced by an arbitrary finite set.

Multidimensional VDW:
Let ${e\in N}$ . Let ${F=\{\overline f_1, \overline f_2, \ldots, \overline f_k\}}$ be a finite set of points in ${Z^e}$ (e.g., ${(0,0)}$ , ${(0,1)}$ , ${(1,0)}$ , ${(1,1)}$ for the square case in the corollary to Multidim VDW). For all ${c}$ , for any ${c}$ -coloring ${COL: Z^e\rightarrow [c]}$ , there exists ${\overline a\in Z^e}$ , ${d\in N}$ , ${d\ne0}$ , such that
${COL(\overline a + d\overline f_1)= COL(\overline a + d\overline f_2) = \cdots =COL(\overline a + d\overline f_k).}$

This was proven by Furstenberg and Weiss (Topological dynamics and combinatorial number theory, Journal d’Analyse Mathematique, Vol. 34, 61–85, 1978); however, it was later observed that it follows from the (ordinary) Hales-Jewitt Theorem.

Furstenberg and Katznelson also proved a density version of the Multidimensional VDW Theorem (An ergodic Szemeredi’s theorem for commuting transformations, Journal d’Analyse Mathematique, Vol. 34, 275–291, 1978). Roughly speaking, if ${A\subseteq Z^d}$ is dense enough then there exists ${\overline a\in Z^e}$ , ${d\in N}$ , ${d\ne 0}$ such that ${\{ \overline a+d\overline f \mid f\in F \}\subseteq A}$ .

Consider the functions

${\overline a + d\overline f_1, \overline a + d\overline f_2, \cdots, \overline a + d\overline f_k.}$

One may consider replacing these functions with a more complicated function of ${d}$ and ${\overline f_1, \ldots, \overline f_k}$ . This leads to the following theorem.

Multidimensional Poly VDW:
Let ${e,r\in n}$ . Let ${p: Z^r \rightarrow Z^e}$ . Let ${F=\{\overline f_1, \overline f_2, \ldots, \overline f_s\}}$ be a finite set of points in ${Z^r}$ . Let ${f_i = (f_{i1},\ldots,f_{ir}).}$ For all ${c}$ , for any ${c}$ -coloring ${COL: Z^e\rightarrow [c]}$ , there exists ${\overline a\in Z^e}$ , ${d\in Z^r}$ , ${d=(d_1,\ldots,d_r)}$ , ${d\ne \overline 0}$ , such that

${COL(\overline a + P(d_1f_{11},d_2f_{12},\ldots,d_rf_{1r}))= COL(\overline a + P(d_1f_{21},d_2f_{22},\ldots,d_rf_{2r}))}$
${=COL(\overline a + P(d_1f_{31},d_2f_{r2},\ldots,d_rf_{3r}))}$
${\vdots}$
${COL(\overline a + P(d_1f_{s1},d_2f_{r2},\ldots,d_rf_{sr}))}$

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 1996, Vol. 9, 725–753.

They actually proved a density version.

There is an alternative proof 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 Multi-dimensional Poly VDW Theorem from Poly HJ. (This part was elementary.)

There is a purely combinatorial proof of the Multi-dimensional Poly VDW Theorem, though it is not stated in the literature:

Walters has a combinatorial proof of Poly HJ in the paper of his mentioned in my last post.
As noted above, Bergelson and Leibman showed how to get from the Poly HJ theorem to the Multi-dimensional Poly VDW theorem.

Putting all this together there is an elementary proof of the Multi-dimensional Poly VDW theorem. There is a general version as well, similar to the Gen Poly VDW from
my last post, but I won’t state it here.

These types of theorems have been generalized in Polynomial Szemeredi theorems for countable modules over integral domains and finite fields by Bergelson, Leibman, and McCutcheon, Journal d’Analyse Mathematique, Vol 95, 243–296, 2005.

There has also been some work on restricting what ${d}$ or ${\overline d}$ could be in the above theorems. We state the easiest of such theorems. It is derivable from the (ordinary) Hales-Jewitt theorem.

VDW’s with ${d}$ restricted:
Let ${C\subseteq N}$ . Let ${D}$ be the set of all sums of distinct elements of ${C}$ . For all ${c,k\in N}$ , for any ${c}$ -coloring ${COL:Z \rightarrow [c]}$ there exists ${a\in Z}$ , ${d\in D}$ , ${d\ne 0}$ , such that

${COL(a) = COL(a+d) = COL(a+2d) = \cdots = COL(a+(k-1)d).}$

More complicated versions of this for multidimensional polynomials were proven by Bergelson and McCutcheon (An Ergodic IP Polynomial Szemeredi Theorem by Bergelson and McCutcheon. Memoirs of the American Math Society, Vol 46, 2000.

Open Problems:

Consider the one-dimensional VDW theorem over the reals. Is there an easy analytic proof of this, or of some subcases of it?
If we allow polynomials with constant term what happens. More concretely: For all finite sets , determine such that:
- For any ${c}$ -coloring ${COL:Z\rightarrow [c]}$ there exists ${a,d\in Z}$ , ${d\ne 0}$ , such that ${\{ a+p(d) \mid p\in F\}}$ is monochromatic.
- There exists a ${c+1}$ -coloring ${COL:Z\rightarrow [c]}$ such that for all ${a,d\in Z}$ , ${d\ne 0}$ , ${\{ a+p(d) \mid p\in F\}}$ is not monochromatic.
Everything I’ve mentioned above except the Poly HJ theorem has a density analoge that is difficult to proof. Find easier proofs. This is not well defined since it depends on how you define `easier’. Combinatorial may be one definition, but those can be rough too.

I would like to thank Alexander Leibman for his help in preparing this post.

But most disturbingly …

January 25, 2007 in food, teaching | Tags: Chopsticks | 8 comments

My new hero is the student in a class of mine who sent me the following email:

There is always a student who shows up 10 minutes late to each of the (…) lectures, carrying a box of takeout food. He proceeds to noisily eat it while you lecture. This is highly distracting [as well as disturbing; this guy doesn't know how to use chopsticks], especially for those of us who chose to follow the rules. Please take some action as to inform students that eating in class is disrespectful not only to you, but distracting to other students who are trying to take notes. Thanks.

See, eating noisily during class is annoying enough. But not knowing how to use chopsticks? That’s disturbing!

The Polynomial van der Waerden Theorem

January 19, 2007 in math | Tags: Bill Gasarch | 5 comments

[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 ${c,k\in N}$ , for any ${c}$ -coloring ${COL:Z \rightarrow [c]}$ , there exists ${a,d\in Z}$ , ${d\ne 0}$ , such that

${COL(a) = COL(a+d) = COL(a+2d) = \cdots = COL(a+(k-1)d).}$

The original proof ofVDW’s Theorem was an induction on the following ordering ${\omega^2}$ on ${(k,c)}$

${(1,1)<(1,2)<\cdots<(2,1)<(2,2)<\cdots<(3,1)<(3,2)<\cdots.}$

For example the proof of ${(4,2)}$ depends on the theorem being true for ${(3,L)}$ where ${L}$ 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

${a, a+d, a+2d, \ldots, a+(k-1)d.}$

One may consider replacing ${d, 2d, 3d, \ldots, (k-1)d}$ with polynomials in ${d}$ . This leads to the following theorem.

Poly VDW:
For all ${c\in N}$ , for all ${p_1,\ldots,p_k \in Z[x]}$ such that ${(\forall i)[p_i(0)=0]}$ , for any ${c}$ -coloring ${COL:Z\rightarrow [c]}$ there exists ${a,d\in Z}$ , ${d\ne 0}$ , such that

${COL(a) = COL(a+p_1(d)) = COL(a+p_2(d)) = \cdots = COL(a+p_k(d)).}$

The condition ${(\forall i)[p_i(0)=0]}$ is needed since if the ${p_i}$ ’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 ${p_1,\ldots,p_k \in Z[x]}$ such that ${(\forall i)[p_i(0)=0]}$ , for all sets ${A\subseteq Z}$ of positive density, there exists ${a,d\in Z}$ , ${d\ne 0}$ , such that

${a, a+p_1(d), a+p_2(d),\ldots, a+p_k(d)\in A. }$

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 ${\omega^\omega}$ ordering as follows.

For every finite set ${F\subseteq Z[x]}$ such that ${(\forall p\in F)[p(0)=0]}$ we associate a tuple ${(n_e,\ldots,n_1)}$ where the largest degree polynomial in ${F}$ is degree ${e}$ , and, for all ${i}$ , ${1\le i\le e}$ , ${n_i}$ is the number of different coefficients of ${x^i}$ that occur in polynomials of degree ${i}$ in ${F}$ .

Let ${PVDW(n_e,\ldots,n_1)}$ mean that Poly VDW holds for all sets of polys ${F}$ of type ${(n_e,\ldots,n_1)}$ . The ordinary VDW theorem can be viewed as ${\bigwedge_{i=1}^\infty PDVW(i)}$ .

The Poly VDW is proven by induction on the following ${\omega^\omega}$ -ordering. Let ${\sigma, \tau \in N^*}$ .

If ${|\sigma| < |\tau|}$ then ${\sigma \preceq \tau}$ .
If ${|\sigma|=|\tau|}$ then order lexicographically. (e.g., ${(2,3,4,999,10^{100}) < (2,3,5,1,0,0)}$ )

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

Gen Poly VDW:
Let ${R}$ any infinite commutative ring. For all ${c\in N}$ , for all ${p_1,\ldots,p_k \in R[x]}$ such that ${(\forall i)[p_i(0)=0]}$ , for any ${c}$ -coloring ${COL: R\rightarrow [c]}$ there exists ${a,d\in R}$ , ${d\ne 0}$ , such that

${COL(a) = COL(a+p_1(d)) = COL(a+p_2(d)) = \cdots = COL(a+p_k(d)).}$

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 ${p_1,\ldots, p_k \in Z[x]}$ such that ${(\forall i)[p_i(0)=0]}$ , there exists ${a,d\in Z}$ , ${d\ne 0}$ , such that

${a, a+p_1(d), a+p_2(d), \cdots a+p_k(d)}$ 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 ${COL}$ be a 3-coloring of ${\{1,\ldots,2006\}}$ . Show that there exists ${x,y}$ such that ${COL(x)=COL(y)}$ and ${|x-y|}$ 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.

iWant

January 18, 2007 in technology | Tags: Apple | 4 comments

The new Prada phone looks good, and it comes with its own Prada leather case, but I’ll wait for the iPhone (or whatever it will be called), which is conveniently coming out just before my birthday.

What I am really looking forward to, however, is the iCar. It will cost $50,000, it will do 10 miles to the gallon, of a special gasoline sold only at Apple gas stations, and if there is a small mechanical problem you will have to ship it to Cupertino, where they will replace the whole engine for a convenient $10,000 fee. But, as the first car without a steering wheel, it will be so cool!

January 10, 2007 in China | Leave a comment

For the last few days Hong Kong has been swept by a cold wave, and one could see people wearing scarves, down jacket, fur-lined coats and so on, and everybody was complaining about the cold. Highs were in the 60s, and lows in the 50s. The fur-lined coats, by the way, are a cheat: the fur is only on the border of the hood and near the zipper, were it can be seen, but not on the inside of the coat.

Public transportation is fantastic. I love the double-decker buses for at least two reasons: it’s nice to sit upstairs and look around, and they make me feel tall (the ceiling is just a few inches above my head). A single payment card is accepted by the several different companies that run buses, ferries, subway and trains; in fact, the card is also accepted by vending machines, convenience stores and many retail stores. It’s as if in San Francisco one could shop at the Gap and pay with a Bart card.

Hong Kong is crowded, in a most enjoyable way. Not unlike Manhattan, here apartments are very small, so people spend most of their time, and do most of their socializing, outside. Plus, people seem to like to stay up until late. The result is that everywhere there are huge crowds of people who are out and about. After three months in LA, it’s a great change of pace. The Chinese University is in the New Territories, which are as out of the way from the center as it sounds. If Hong Kong island is Manhattan, and Kowloon is Brooklyn, here we may as well be in Long Island. And, yet, the mall here in Sha Tin is open until 10pm or later, and it is lively until then every night.

I cannot decide if this is an expensive or a cheap city. Restaurants can be very cheap, but the cover charges in clubs and the cost of drinks in bars are a real scandal. Something should be done about it; perhaps someone should write angrily about such things on the internet.

The earthquake in Taiwan broke a major internet cable, and internet traffic has been slow in the south of China and here as well, so I could not post daily food updates. I apologizes to the countless disappointed readers (so far, Cantonese, dim sum, seafood, dim sum, hot pot, Shanghainese, Vietnamese, Western, Pekinese, dim sum, Cantonese).

The Auspicious Start

January 3, 2007 in China | 5 comments

Two days into 2007 and…

Recommendation letters: sent
Getting organized for new courses: done and done
Referee reports: [cough] [cough]
Bags: packed
Talks: prepared
For the 14+ hour flight: got a few books

And how considerate that they would time the Italian Cultural Festival to coincide with my visit, even at the cost of moving the Befana to January 12.

Monthly Archive

Conquering Hearts, Minds, and Bumpers

The Multi-dimensional Polynomial van der Waerden Theorem

But most disturbingly …

The Polynomial van der Waerden Theorem

iWant

The Auspicious Start

Recent Comments

math

non-theory

theory

Archives

a

Tags

Top Posts