Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Journal of the American Mathematical Society
Journal of the American Mathematical Society
ISSN 1088-6834(online) ISSN 0894-0347(print)

 

Discrepancy in arithmetic progressions


Authors: Jirí Matousek 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 $\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

Jirí Matousek
Affiliation: Department of Applied Mathematics, Charles University, Malostranské nám. 25, 118 00 Praha 1, Czech Republic
Email: matousek@kam.mff.cuni.cz

Joel Spencer
Affiliation: Courant Institute of Mathematical Sciences, 251 Mercer Street, New York, New York 10012
Email: spencer@cs.nyu.edu

DOI: http://dx.doi.org/10.1090/S0894-0347-96-00175-0
PII: S 0894-0347(96)00175-0
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