2007/03/05 by Nils Hebbinghaus, Hebbinghaus, Nils
Mathematics · #11K38 #Advanced Mathematical Identities #Analytic Number Theory Research #FOS: Mathematics #Mathematical Approximation and Integration #Number Theory (math.NT)
paper · pdf · doi:10.48550/arxiv.math/0703108
openalex publication_date 2007/03/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Estimating the discrepancy of the hypergraph of all arithmetic progressions in the set [N]=\1,2,\hdots,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+\hdots+Ak in [N], where the Ai are arithmetic progressions. For this hypergraph Hebbinghaus (2004) proved a lower bound of Ω(Nk/(2k+2)). Note that the probabilistic method gives an upper bound of order O((Nlog N)1/2) for all fixed k. Přívětivý improved the lower bound for all k≥ 3 to Ω(N1/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 his 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.