*Ramsey Theory on the Integers*by Bruce M. Landman and Aaron Robertson.

The second chapter of the book is devoted to Van der Waerden's theorem, which states that given positive integers k and r, there is some positive integer N such that if integers {1, ..., N} are colored in r colors, there will exist a k-term arithmetic progression in which all the elements are the same color. We let w(k,r) be the smallest such N. For example, w(2,3) = 9. There is a way to color {1, ..., 8} so that there is no three-term monochromatic arithmetic progression, namely

1 2 3 4 5 6 7 8

That's 1, 4, 5, and 8 red, and 2, 3, 6, and 7 blue.) But there's no way to color {1, ..., 9} so that there's no three-term arithmetic progression; the proof of this is basically by trial and error.

A couple months ago, Mark Dominus wrote about some programs that he wrote a while back to try to search for "good" colorings; it's interesting from a programming point of view. As far as I know, there is no

*fast*way to do this; as a result, very few values of w(k,r) are known. (w(2,r) = r+1 trivially; according to Landman and Robertson, the only other known values are w(3,2) = 9, w(3,3) = 27, w(4,2) = 35, w(3,4) = 76, w(5,2) = 178.)

It turns out that we can generalize this question by replacing "arithmetic progressions" with various other families of sets. I was surprised to see how many generalizations of arithmetic progressed there are:

**Quasi-progressions**: these are sequences {x_{1}, ..., x_{k}} where x_{i}- x_{i-1}is between d and d+n, for some small n. (Obviously any increasing sequence is a quasi-progression for large enough n.**Generalized quasi-progressions**are like quasi-progressions, but n above is replaced by some*function*δ(i).**Descending waves**, which satisfy x_{i}- x_{i-1}≤ x_{i-1}- x_{i-2}.**Semi-progressions**, which are*subsets*of arithmetic progressions.**Iterated polynomial sequences**: sequences of the form {x_{1}, ..., x_{k}} where x_{i+1}= p(x_{i}) for some polynomial p and the x_{i}form an increasing sequence. The case of arithmetic progressions is the case f(x) = x+d.**Solutions to a linear recurrence relation**: sequences where x_{k}= c_{1}x_{k-1}+ ... + c_{n}x_{k-n}, where we specify x_{1}... x_{n}to get the recurrence started. Arithmetic progressions are just the case x_{k}= 2x_{k-1}- x_{k-2}.

One conspicuously absent generalization of arithmetic progressions are sequences in which the gaps x

_{i}- x

_{i-1}are chosen from some set which isn't an interval -- for example, sequences in which x

_{i}- x

_{i-1}is always 2 or 5. (I chose those numbers at random.) I'm not an expert in this subject, so I don't know if this is because such results don't exist, because they turn out to be uninteresting, or because the authors wanted to keep the book to a reasonable length.

Still, who would have thought there were this many ways of thinking of such a simple object as an arithmetic progression?

## 1 comment:

Still, who would have thought there were this many ways of thinking of such a simple object as an arithmetic progression?No variety of interpretation and variation has surprised me after realizing that I've been doing group cohomology ever since I was doing place-value arithmetic (before you were born, incidentally.. happy birthday).

Post a Comment