On The Hereditary Discrepancy of Homogeneous Arithmetic Progressions

2013/09/24 by Nikolov, Aleksandar, Talwar, Kunal
#11K38 #Combinatorics (math.CO) #FOS: Mathematics #Number Theory (math.NT)

paper · doi:10.48550/arxiv.1309.6034

Abstract

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

Related

• Discrepancy of Arithmetic Progressions in Boxes and Convex Bodies
• On the Gap between Hereditary Discrepancy and the Determinant Lower Bound
• The determinant bound for discrepancy is almost tight
• A Tighter Relation Between Hereditary Discrepancy and Determinant Lower Bound
• Discrepancy of Sums of two Arithmetic Progressions