**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).

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.

ReplyDeleteAH- I mean the LENGTH of the sequence is \ge its

ReplyDeleteleast element.

Sorry about that.

What is k in the statement of VDW's theorem? If I'm not mistaken it's the length of the arithmetic progression.

ReplyDeleteSo then the k in the LVDW theorem has a different meaning than the k of the VDW theorem?

Anonymous 3: Yes, the statement of VDW's theorem should say "there exists a monochromatic arithmetic progression of length k."

ReplyDeleteIn 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.