Discrepancy of Sums of two Arithmetic Progressions

Estimating the discrepancy of the hypergraph of all arithmetic progressions in the set [N]={1,2,…,N} was one of the famous open problems in combinatorial discrepancy theory for a long time. An extension of this classical hypergraph is the hypergraph of sums of k (k⩾1 fixed) arithmetic progressions. The hyperedges of this hypergraph are of the form A1+A2+⋯+Ak in [N], where the Ai are arithmetic progressions. The case k=2 (hypergraph of sums of two arithmetic progressions) is the only case with a large gap between the known upper and lower bound. We bridge this gap (up to a logarithmic factor) by proving a lower bound of order Ω(N1/2) for the discrepancy of the hypergraph of sums of two arithmetic progressions.