On the hereditary discrepancy of homogeneous arithmetic progressions

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$.

Locations

• Proceedings of the American Mathematical Society - View
• arXiv (Cornell University) - View - PDF