Discrepancy of Sums of two Arithmetic Progressions

DOI10.1016/J.ENDM.2007.07.087MaRDI QIDQ3503517zbMATH OpenOpenAlexFDO

Authors Nils Hebbinghaus

Publication date 5 June 2008

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0703108

zbMATH Keywords

arithmetic progressionsdiscrepancydiscrete Fourier analysis

Mathematics Subject Classification ID

Hypergraphs (05C65) Arithmetic progressions (11B25) Irregularities of distribution, discrepancy (11K38)

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$ ($kgeq1$ 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((NlogN{)}^{1/2})$ for all fixed $k$. Pv{r}'{i}vv{e}tiv'{y} improved the lower bound for all $kgeq3$ 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.

Recommendations

• Discrepancy in generalized arithmetic progressions
• Discrepancy of Sums of Arithmetic Progressions
• Discrepancy of sums of three arithmetic progressions
• Discrepancy of arithmetic progressions in higher dimensions
• Discrepancy of centered arithmetic progressions in \(\mathbb{Z}_p\) (extended abstract)

Cites work

• Discrepancy in arithmetic progressions
• Discrepancy of arithmetic progressions in higher dimensions
• Discrepancy of cartesian products of arithmetic progressions
• Discrepancy of Sums of Arithmetic Progressions
• Discrepancy of sums of three arithmetic progressions
• Geometric discrepancy. An illustrated guide
• scientific article; zbMATH DE number 3482343 (Why is no real title available?)
• scientific article; zbMATH DE number 863495 (Why is no real title available?)
• Remark concerning integer sequences
• Roth's estimate of the discrepancy of integer sequences is nearly sharp
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(5)

• Discrepancy in generalized arithmetic progressions
• Discrepancy of Sums of Arithmetic Progressions
• Discrepancy one among homogeneous arithmetic progressions
• Discrepancy of arithmetic progressions in higher dimensions
• Discrepancy of sums of three arithmetic progressions

This page was built for publication: Discrepancy of Sums of two Arithmetic Progressions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3503517)