Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)



Discrepancy in arithmetic progressions

Authors: Jiří Matoušek and Joel Spencer
Journal: J. Amer. Math. Soc. 9 (1996), 195-204
MSC (1991): Primary 11B25, 11N37
MathSciNet review: 1311824
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (1991): 11B25, 11N37

Retrieve articles in all journals with MSC (1991): 11B25, 11N37

Additional Information

Jiří Matoušek
Affiliation: Department of Applied Mathematics, Charles University, Malostranské nám. 25, 118 00 Praha 1, Czech Republic

Joel Spencer
Affiliation: Courant Institute of Mathematical Sciences, 251 Mercer Street, New York, New York 10012

Received by editor(s): February 18, 1994
Received by editor(s) in revised form: December 29, 1994
Additional Notes: The first author was supported by Charles University grant No. 351 and Czech Republic Grant GAČR 201/93/2167. Part of this research was done during a visit to Princeton University supported by DIMACS
Article copyright: © Copyright 1996 American Mathematical Society