Discrepancy in arithmetic progressions

Jiří Matoušek, Joel Spencer

Research output: Contribution to journalArticlepeer-review


It is proven that there is a two-coloring of the first n integers for which all arithmetic progressions have discrepancy less than const.n1/4. This shows that a 1964 result of K. F. Roth is, up to constants, best possible.

Original languageEnglish (US)
Pages (from-to)195-204
Number of pages10
JournalJournal of the American Mathematical Society
Issue number1
StatePublished - Jan 1996

ASJC Scopus subject areas

  • General Mathematics
  • Applied Mathematics


Dive into the research topics of 'Discrepancy in arithmetic progressions'. Together they form a unique fingerprint.

Cite this