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: 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

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?)

  • 1 N. Alon and J. Spencer, The probabilistic method, Wiley, New York, 1992.MR 93h:60002
  • 2 J. Beck, Roth's estimate on the discrepancy of integer sequences is nearly sharp, Combinatorica 1 (1981), 319--325.MR 83i:05040
  • 3 P. Erdos and J. Spencer, Probabilistic methods in combinatorics, Academic Press, New York, 1974.MR 52:2895
  • 4 D. Kleitman, On a combinatorial problem of Erdos, J. Combin. Theory 1 (1966), 209--214. MR 34:78
  • 5 J. Spencer, Six standard deviations suffice, Trans. Amer. Math. Soc. 289 (1985), 679--706.MR 86k:05004
  • 6 J. Matousek, Tight upper bounds for the discrepancy of halfspaces, Discrete Comput. Geom. (to appear).
  • 7 K. F. Roth, Remark concerning integer sequences, Acta Arith. 9 (1964), 257--260.MR 29:5806

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

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