Discrepancy in arithmetic progressions
Jirí Matousek and Joel Spencer
J. Amer. Math. Soc. 9 (1996), 195-204
Primary 11B25, 11N37
Full-text PDF Free Access
Similar Articles |
Abstract: It is proven that there is a two-coloring of the first integers for which all arithmetic progressions have discrepancy less than . This shows that a 1964 result of K. F. Roth is, up to constants, best possible.
Alon and Joel
H. Spencer, The probabilistic method, Wiley-Interscience
Series in Discrete Mathematics and Optimization, John Wiley & Sons
Inc., New York, 1992. With an appendix by Paul Erdős; A
Wiley-Interscience Publication. MR 1140703
Beck, Roth’s estimate of the discrepancy of integer sequences
is nearly sharp, Combinatorica 1 (1981), no. 4,
647981 (83i:05040), http://dx.doi.org/10.1007/BF02579452
Erdős and Joel
Spencer, Probabilistic methods in combinatorics, Academic
Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New
York-London, 1974. Probability and Mathematical Statistics, Vol. 17. MR 0382007
J. Kleitman, On a combinatorial conjecture of Erdős, J.
Combinatorial Theory 1 (1966), 209–214. MR 0200179
Spencer, Six standard deviations
suffice, Trans. Amer. Math. Soc.
289 (1985), no. 2,
784009 (86k:05004), http://dx.doi.org/10.1090/S0002-9947-1985-0784009-0
J. Matousek, Tight upper bounds for the discrepancy of halfspaces, Discrete Comput. Geom. (to appear).
F. Roth, Remark concerning integer sequences, Acta Arith.
9 (1964), 257–260. MR 0168545
- N. Alon and J. Spencer, The probabilistic method, Wiley, New York, 1992.MR 93h:60002
- J. Beck, Roth's estimate on the discrepancy of integer sequences is nearly sharp, Combinatorica 1 (1981), 319--325.MR 83i:05040
- P. Erdos and J. Spencer, Probabilistic methods in combinatorics, Academic Press, New York, 1974.MR 52:2895
- D. Kleitman, On a combinatorial problem of Erdos, J. Combin. Theory 1 (1966), 209--214. MR 34:78
- J. Spencer, Six standard deviations suffice, Trans. Amer. Math. Soc. 289 (1985), 679--706.MR 86k:05004
- J. Matousek, Tight upper bounds for the discrepancy of halfspaces, Discrete Comput. Geom. (to appear).
- 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):
Retrieve articles in all journals
with MSC (1991):
Department of Applied Mathematics, Charles University, Malostranské nám. 25, 118 00 Praha 1, Czech Republic
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
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
© Copyright 1996 American Mathematical Society