Discrepancy in generalized arithmetic progressions

Estimating the discrepancy of the set of all arithmetic progressions in the first NN 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χmaxA|∑x∈Aχ(x)|=Θ(N1/4)D(N)=minχmaxA|∑x∈Aχ(x)|=Θ(N1/4), where the minimum is taken over all colorings χ:[N]→{−1,1}χ:[N]→{−1,1} and the maximum over all arithmetic progressions in [N]={0,…,N−1}[N]={0,…,N−1}.Sumsets of kk arithmetic progressions, A1+⋯+AkA1+⋯+Ak, are called kk-arithmetic progressions and they are important objects in additive combinatorics. We define Dk(N)Dk(N) as the discrepancy of the set {P∩[N]:P is a k-arithmetic progression}{P∩[N]:P is a k-arithmetic progression}. The second author proved that Dk(N)=Ω(Nk/(2k+2))Dk(N)=Ω(Nk/(2k+2)) and Přívětivý improved it to Ω(N1/2)Ω(N1/2) for all k≥3k≥3. Since the probabilistic argument gives Dk(N)=O((NlogN)1/2)Dk(N)=O((NlogN)1/2) for all fixed kk, the case k=2k=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 Dk(N)=Ω(N1/2)Dk(N)=Ω(N1/2) for all k≥2k≥2.Indeed we prove the multicolor version of this result.