Discrepancy of Sums of Two Arithmetic Progressions

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, where the Ai are arithmetic progressions. For this hypergraph a lower bound of Omega(N^{k/(2k+2)})$ was proved in 2004. Note that the probabilistic method gives an upper bound of order O((N\log N)^{1/2}) for all fixed k. Privetivy improved the lower bound for all k>=3 to Omega(N^{1/2}) in 2005. Thus, the case k=2 (hypergraph of sums of two arithmetic progressions) remained 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 Omega(N^{1/2}) for the discrepancy of the hypergraph of sums of two arithmetic progressions.