Discrepancy in arithmetic progressions

Matoušek, Jiří; Spencer, Joel

doi:10.1090/S0894-0347-96-00175-0

Discrepancy in arithmetic progressions
HTML articles powered by AMS MathViewer

by Jiří Matoušek and Joel Spencer PDF

J. Amer. Math. Soc. 9 (1996), 195-204 Request permission

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

Noga 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
József Beck, Roth’s estimate of the discrepancy of integer sequences is nearly sharp, Combinatorica 1 (1981), no. 4, 319–325. MR 647981, DOI 10.1007/BF02579452
Paul Erdős and Joel Spencer, Probabilistic methods in combinatorics, Probability and Mathematical Statistics, Vol. 17, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1974. MR 0382007
Daniel J. Kleitman, On a combinatorial conjecture of Erdős, J. Combinatorial Theory 1 (1966), 209–214. MR 200179, DOI 10.1016/S0021-9800(66)80027-3
Joel Spencer, Six standard deviations suffice, Trans. Amer. Math. Soc. 289 (1985), no. 2, 679–706. MR 784009, DOI 10.1090/S0002-9947-1985-0784009-0
J. Matoušek, 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 168545, DOI 10.4064/aa-9-3-257-260