Journal of the American Mathematical Society

Author(s): Jirí Matousek; Joel Spencer
Journal: J. Amer. Math. Soc. 9 (1996), 195-204.
MSC (1991): Primary 11B25, 11N37
Retrieve article in: PDF DVI PostScript
This article is available free of charge

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.

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

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

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: 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 GACR 201/93/2167. Part of this research was done during a visit to Princeton University supported by DIMACS
Copyright of article: Copyright 1996, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN: 1088-6834(e) ISSN: 0894-0347(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS