English

User Manual Privacy Policy Disclaimer Contact us

# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Discrepancy of Sums of two Arithmetic Progressions

##### MPS-Authors
/persons/resource/persons44598

Hebbinghaus,  Nils
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

##### Locator
There are no locators available
##### 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.