Technical, Research Report @TechReport Technischer-, Forschungsbericht

 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Goto entry point

 Author, Editor
 Author(s): Hebbinghaus, Nils dblp
 Editor(s):
 BibTeX Citekey*: Hebbinghaus2007 Language: English

 Title, Institution
 Title*: Discrepancy of Sums of two Arithmetic Progressions Institution*: Cornell University (ArXiv) Publishers or Institutions Address*: ArXiv Type: ArXiv

 No, Year, pp.,
 Number*: math.NT/0703108 Pages*: 15 Month: March VG Wort Pages*: Year*: 2007 ISBN/ISSN: DOI:

 Note: (LaTeX) 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. Categories / Keywords: Discrepancy Theory, Arithmetic Progressions, Fourier Analysis Copyright Message: HyperLinks / References / URLs: arXiv:math/0703108v1 Personal Comments: File Upload: Download Access Level: Public

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:
@TECHREPORT{Hebbinghaus2007,
AUTHOR = {Hebbinghaus, Nils},
TITLE = {Discrepancy of Sums of two Arithmetic Progressions},
YEAR = {2007},
TYPE = {ArXiv},
INSTITUTION = {Cornell University (ArXiv)},
NUMBER = {math.NT/0703108},
PAGES = {15},