6 ways of looking at an arithmetic sequence

Lately I've been reading 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₁, ..., 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₁, ..., 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₁x_k-1 + ... + c_nx_k-n, where we specify x₁ ... 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?