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?)


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