On the hereditary discrepancy of homogeneous arithmetic progressions

Nikolov, Aleksandar; Talwar, Kunal

doi:10.1090/S0002-9939-2015-12545-2

On the hereditary discrepancy of homogeneous arithmetic progressions
HTML articles powered by AMS MathViewer

by Aleksandar Nikolov and Kunal Talwar PDF

Proc. Amer. Math. Soc. 143 (2015), 2857-2863 Request permission

Abstract:

We show that the hereditary discrepancy of homogeneous arithmetic progressions is bounded from below by $n^{1/O(\log \log n)}$. This bound is tight up to a constant in the exponent. Our lower bound goes via an exponential lower bound on the discrepancy of set systems of subcubes of the boolean cube $\{0, 1\}^d$.

References

Multiple Authors, Erdős discrepancy problem: Polymath wiki, http://michaelnielsen.org/polymath1/index.php?title=The\_Erd\%C5\%91s\_discrepancy\_problem.
B. Chazelle and A. Lvov, The discrepancy of boxes in higher dimension, Discrete Comput. Geom. 25 (2001), no. 4, 519–524. The Micha Sharir birthday issue. MR 1838418, DOI 10.1007/s00454-001-0014-2
B. Chazelle and A. Lvov, A trace bound for the hereditary discrepancy, Discrete Comput. Geom. 26 (2001), no. 2, 221–231. ACM Symposium on Computational Geometry (Hong Kong, 2000). MR 1843438, DOI 10.1145/336154.336179
Paul Erdős, Some unsolved problems, Michigan Math. J. 4 (1957), 291–300. MR 98702
Steven Finch, Two-colorings of positive integers, http://www.people.fas.harvard.edu/~sfinch/csolve/ec.pdf.
Gil Kalai, Erdős discrepancy problem 22, http://gowers.wordpress.com/2012/08/22/edp22-first-guest-post-from-gil-kalai/, 09 2012.
Shiva Prasad Kasiviswanathan, Mark Rudelson, Adam Smith, and Jonathan Ullman, The price of privately releasing contingency tables and the spectra of random matrices with correlated rows, STOC’10—Proceedings of the 2010 ACM International Symposium on Theory of Computing, ACM, New York, 2010, pp. 775–784. MR 2743327
Boris Konev and Alexei Lisitsa, A sat attack on the erdős discrepancy conjecture, CoRR abs/1402.2184 (2014).
L. Lovász, J. Spencer, and K. Vesztergombi, Discrepancy of set-systems and matrices, European J. Combin. 7 (1986), no. 2, 151–160. MR 856328, DOI 10.1016/S0195-6698(86)80041-5
S. Muthukrishnan and Aleksandar Nikolov, Optimal private halfspace counting via discrepancy, STOC’12—Proceedings of the 2012 ACM Symposium on Theory of Computing, ACM, New York, 2012, pp. 1285–1292. MR 2961660, DOI 10.1145/2213977.2214090
Mark Rudelson, Row products of random matrices, Adv. Math. 231 (2012), no. 6, 3199–3231. MR 2980497, DOI 10.1016/j.aim.2012.08.010