10 December 2007

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 {x1, ..., xk} where xi - xi-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 xi - xi-1 ≤ xi-1 - xi-2.

  • Semi-progressions, which are subsets of arithmetic progressions.

  • Iterated polynomial sequences: sequences of the form {x1, ..., xk} where xi+1 = p(xi) for some polynomial p and the xi form an increasing sequence. The case of arithmetic progressions is the case f(x) = x+d.

  • Solutions to a linear recurrence relation: sequences where xk = c1xk-1 + ... + cnxk-n, where we specify x1 ... xn to get the recurrence started. Arithmetic progressions are just the case xk = 2xk-1 - xk-2.

One conspicuously absent generalization of arithmetic progressions are sequences in which the gaps xi - xi-1 are chosen from some set which isn't an interval -- for example, sequences in which xi - xi-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:

John Armstrong said...

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