Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

On the hereditary discrepancy of homogeneous arithmetic progressions


Authors: Aleksandar Nikolov and Kunal Talwar
Journal: Proc. Amer. Math. Soc. 143 (2015), 2857-2863
MSC (2010): Primary 11K38; Secondary 11B25
DOI: https://doi.org/10.1090/S0002-9939-2015-12545-2
Published electronically: February 27, 2015
MathSciNet review: 3336610
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] Multiple Authors, Erdős discrepancy problem: Polymath wiki, http://michaelnielsen.org/polymath1/index.php?title=The_Erd%C5%91s_discrepancy_problem.
  • [2] 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 (2002f:11097), https://doi.org/10.1007/s00454-001-0014-2
  • [3] 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 (2003b:68190), https://doi.org/10.1145/336154.336179
  • [4] Paul Erdős, Some unsolved problems, Michigan Math. J. 4 (1957), 291-300. MR 0098702 (20 #5157)
  • [5] Steven Finch, Two-colorings of positive integers, http://www.people.fas.harvard.edu/~sfinch/csolve/ec.pdf.
  • [6] Gil Kalai, Erdős discrepancy problem 22, http://gowers.wordpress.com/2012/08/22/edp22-first-guest-post-from-gil-kalai/, 09 2012.
  • [7] 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 (2011i:94095)
  • [8] Boris Konev and Alexei Lisitsa, A sat attack on the erdős discrepancy conjecture, CoRR abs/1402.2184 (2014).
  • [9] 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 (88b:05036), https://doi.org/10.1016/S0195-6698(86)80041-5
  • [10] 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, https://doi.org/10.1145/2213977.2214090
  • [11] Mark Rudelson, Row products of random matrices, Adv. Math. 231 (2012), no. 6, 3199-3231. MR 2980497, https://doi.org/10.1016/j.aim.2012.08.010

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 11K38, 11B25

Retrieve articles in all journals with MSC (2010): 11K38, 11B25


Additional Information

Aleksandar Nikolov
Affiliation: Department of Computer Science, Rutgers University, Piscataway, New Jersey 08854
Address at time of publication: Microsoft Research, Redmond, Washington 98052
Email: alenik@microsoft.com

Kunal Talwar
Affiliation: Microsoft Research, Mountain View, California 94043
Address at time of publication: Google, Mountain View, California 94043
Email: kunal@kunaltalwar.org

DOI: https://doi.org/10.1090/S0002-9939-2015-12545-2
Received by editor(s): September 23, 2013
Received by editor(s) in revised form: March 27, 2014
Published electronically: February 27, 2015
Communicated by: Harm Derksen
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society