Progressions in every two-coloration of Zn

AbstractFor each positive integer n, G(n) is defined to be the largest integer k such that no matter how Zn is two-colored, some progression a, a + d, a + 2d, …, a + (k − 1)d of k distinct elements of Zn will appear in one color. Our main theorem shows constructively that if Zn can be two-colored in such a way that the longest monochrome progression has m distinct terms mod n and any monochrome progression of k distinct terms with common difference d ≢ 0 (mod n) has the property that kd ≢ 0 (mod n), then G(rn) ⩽ m for 1 ⩽ r ⩽ m and G(rn) ⩽ r for r > m. One lower bound on G(n) says G(rn) ⩾ G(n) for r ⩾ 1 and n ⩾ 1. Two main results with corollaries, a “quadratic-residue coloration” on Zp for p a prime, and the van der Waerden numbers W(k) for 2 ⩽ k ⩽ 5, together with a computer search, have been used to determine the exact value of G(n) for 1 ⩽ n ⩽ 53, for all primes up to 71, and for a few more cases, the highest of which is G(695) = 5 which guarantees that W(6) ⩾ 696