Discrepancy in generalized arithmetic progressions

Estimating the discrepancy of the set of all arithmetic progressions in the first N natural numbers was one of the famous open problems in combinatorial discrepancy theory for a long time, successfully solved by K. Roth (lower bound) and Beck (upper bound). They proved that D(N)=min_χmax_A|∑_xAχ(x)|=Θ(N^1/4), where the minimum is taken over all colorings χ:N]→{−1,1} and the maximum over all arithmetic progressions in N]={0,…,N−1}.Sumsets of k arithmetic progressions, A₁++A_k, are called k-arithmetic progressions and they are important objects in additive combinatorics. We define D_k(N) as the discrepancy of the set {P∩N]:P is a k-arithmetic progression}. The second author proved that D_k(N)=Ω(N^k/(2k+2)) and Přívětivý improved it to Ω(N^1/2) for all k≥3. Since the probabilistic argument gives D_k(N)=O((NlogN)^1/2) for all fixed k, the case k=2 remained the only case with a large gap between the known upper and lower bounds. We bridge this gap (up to a logarithmic factor) by proving that D_k(N)=Ω(N^1/2) for all k≥2.Indeed we prove the multicolor version of this result.