# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Discrepancy of Sums of two Arithmetic Progressions

##### Fulltext (public)

math_0703108.pdf

(Preprint), 149KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Hebbinghaus, N. (2007). Discrepancy of Sums of two Arithmetic Progressions. Retrieved from http://arxiv.org/abs/math/0703108.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0029-B964-C

##### Abstract

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
$\Omega(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{r}\'{i}v\v{e}tiv\'{y}
improved the lower bound for all $k\geq 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
his 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.