Computational Complexity

Monday, January 12, 2009

 
A Complete History of the LVDW conjecture

Posted by GASARCH

When you first make a conjecture you don't know if it will be important or interesting or both or neither. In the case below it was solved quickly, the answer was not interesting, and I doubt anymore will come of it. But, I did get a blog posting and some nice exercises for a class out of it.

Recall: VDW theorem is the following

For all k, for all c, for all c-colorings of N (the naturals) there exists a monochromatic arithmetic progression.

I was looking at a variant of this:

Definition: An arithmetic sequence is large if it is at least as long as its least element. The following are large arithmetic sequences: (1), (2, 10), (4,5,6,7). The following is NOT large arithmetic sequences: (100,102,104,...,118).

Note that for any c-coloring of N there is (trivially) a large monochromatic AP: just take (1). But what if we start coloring the naturals starting at k?

LVDW CONJECTURE: for all k, for all c, for all coloring c-colorings of (k,k+1,k+2,...) there exists a large monochromatic AP.

Why do I care? There is a Large Ramsey Theorem which is similar and is true. It is proven from the infinite Ramsey Theorem. It is of interest because this theorem is not provable in Peano Arithmetic (the associated functions grow faster than any function definable in PA). This leads to the following questions: I was hoping that LVDW CONJECTURE was true but ind of PA.

Alas, Andy Parrish (was Brilliant ugrad at UMCP in CS, is now brilliant grad at UCSD in math) proved LVDW CONJECTURE false. I leave it as an exercise.

There is a question that remains, though it just be equivalent to getting bounds on VDW numbers.

Definition: Let g:N &rarr N An arithmetic sequence is g-large if it is larger than g of its least element.

For which sequences of functions f_c is the following true: for all k, for all c, for all coloring c-colorings of (k,k+1,k+2,...) there exists a f_c-large monochromatic AP.

We know there is such a sequence by the ordinary VDW theorem (exercise).

9:47 AM # 4 comments

1.  Anonymous says:  
   
   Definitional question: What does it mean for an arithmetic sequence to be larger than its least element? For example, under the interpretations of that definition that I'm imagining, I don't see why (4,5,6,7) would be large.
   

   10:53 AM, January 12, 2009

2.  GASARCH says:  
   
   AH- I mean the LENGTH of the sequence is \ge its
   least element.
   
   Sorry about that.
   

   12:10 PM, January 12, 2009

3.  Anonymous says:  
   
   What is k in the statement of VDW's theorem? If I'm not mistaken it's the length of the arithmetic progression.
   
   So then the k in the LVDW theorem has a different meaning than the k of the VDW theorem?
   

   7:58 AM, January 13, 2009

4.  Andy Parrish says:  
   
   Anonymous 3: Yes, the statement of VDW's theorem should say "there exists a monochromatic arithmetic progression of length k."
   
   In the statement of the (false) LVDW conjecture, we color the numbers beginning at k and look for a "large" AP. But the k here and the k in VDW are not entirely different. Any large AP would have to have at least k elements (since a large AP beginning at m needs to have m terms, and m >= k.
   

   7:45 PM, January 14, 2009

Comment Feeds: This Post All