Discrepancy of Sums of two Arithmetic Progressions
| dc.creator | Hebbinghaus, Nils | |
| dc.date | 2007-03-05 | |
| dc.date.accessioned | 2026-07-07T07:50:13Z | |
| dc.date.available | 2026-07-07T07:50:13Z | |
| dc.description | 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\geq 1$ fixed) arithmetic progressions. The hyperedges of this hypergraph are of the form $A_{1}+A_{2}+\hdots+A_{k}$ in $[N]$, where the $A_{i}$ are arithmetic progressions. For this hypergraph Hebbinghaus (2004) proved a lower bound of $Ω(N^{k/(2k+2)})$. Note that the probabilistic method gives an upper bound of order $O((N\log N)^{1/2})$ for all fixed $k$. Přívětivý improved the lower bound for all $k\geq 3$ to $Ω(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 his gap (up to a logarithmic factor) by proving a lower bound of order $Ω(N^{1/2})$ for the discrepancy of the hypergraph of sums of two arithmetic progressions. | |
| dc.description | 15 pages, 0 figures | |
| dc.identifier | https://arxiv.org/abs/math/0703108 | |
| dc.identifier | http://arxiv.org/abs/math/0703108 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/125088 | |
| dc.subject | Number Theory | |
| dc.subject | 11K38 | |
| dc.title | Discrepancy of Sums of two Arithmetic Progressions | |
| dc.type | text |