Discrepancy of Sums of two Arithmetic Progressions

Details Discrepancy of Sums of two Arithmetic Progressions Discrepancy of Sums of two Arithmetic Progressions

2007-03-05

arxiv.org/abs/math/0703108v1

Mathematics

Number Theory

15 pages, 0 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Discrepancy of Sums of two Arithmetic Progressions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Discrepancy of Sums of two Arithmetic Progressions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Discrepancy of Sums of two Arithmetic Progressions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-113920