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:









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, Abstract, ©

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},
ADDRESS = {ArXiv},
MONTH = {March},
}


Entry last modified by Christine Kiesel, 02/28/2008
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Nils Hebbinghaus
Created
03/06/2007 04:37:47 PM
Revisions
3.
2.
1.
0.
Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel
Nils Hebbinghaus
Edit Dates
28.06.2007 12:54:44
28.06.2007 12:46:38
28.06.2007 12:38:40
03/06/2007 04:37:47 PM
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
Sums2APs_final.pdf