Progressions in every two-coloration of Zn

H. Y. Song, H. Taylor, S. W. Golomb

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


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

Original languageEnglish
Pages (from-to)211-221
Number of pages11
JournalJournal of Combinatorial Theory, Series A
Issue number2
Publication statusPublished - 1992 Nov

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Progressions in every two-coloration of Zn'. Together they form a unique fingerprint.

Cite this