From: troy257@aol.com (Troy257)
Newsgroups: sci.math.research
Subject: Re: Integer-colouring problem
Date: Wed, 18 Feb 1998 09:08:30 -0500

This is a variation of a problem of Van der Waerden.  In the twenties, Van der
Waerden proved that  for any k and p, there is some N such that every
k-coloring of 1..N contains a monochromatic arithmetic progression of length p.
 Of course, this arithmetic progression doesn't have to be of the form n, 2n,
..., it could be of the form n + q, 2n+q, 3n+q, ... for some q.

The problem with Van der Waerden's proof (and all subsequent proofs) is that
the best upper bounds on the value of are astronomically large-- much much
worse than exponential.  It seems likely that Van der Waerden's approach can be
modified to handle your additional demand that the progressions actually be
multiples of a single integer (and your restriction that k = p), though the
bounds on N may be even larger.

This problem is discussed at length in a book called Ramsey Theory by Ron
Graham et al, and in an article in Scientific American some time about 1990,
Graham gives a nice introduction to the problem and offers $5000 (if memory
serves) for an improved proof.  

I don't believe anyone ever won the $5000, though I'm not sure.  This fact,
combined with the fact that mathematical royalty like Graham and Erdos beat
their heads against the problem unsuccessfully, should give some idea just how
difficult the problem is.  On the other hand, the problem is so intuitive and
simple to state, you never know, there just may be some clever approach out
there waiting to be discovered.

Good Luck.