Nils Hebbinghaus:

Discrepancy of Sums of Arithmetic Progressions

Let $N$ be a positive integer, $[N]:=\{0,1,2,\hdots, N-1\}$ and ${\mathcal H}_{N}=([N],{\mathcal E}_{N})$ the hypergraph of all arithmetic progressions in $[N]$. This means that ${\mathcal E}_{N}$ contains all sets of the form $\{\{a+k\delta\mid k\in[L]\}\mid a\in[N],\delta,L\in\mathbb{N}\}$ in $[N]$. In the year 1964 Roth proved the lower bound $\disc({\mathcal H}_{N})=\Omega(N^{1/4})$. It was a long standing open problem to determine the right order of the discrepancy of ${\mathcal H}_{N}$. Finally, in the year 1996, Matou\v{s}ek and Spencer gave the upper bound $\disc({\mathcal H}_{N})=O(N^{1/4})$ and thus solved this classical discrepancy problem. We are interested in the discrepancy of the related hypergraph ${\mathcal H}_{N,k}=([N],{\mathcal E}_{N,k})$, where ${\mathcal E}_{N,k}$ consists of all sums of $k$ arithmetic progressions for a positive integer $k$. Let ${\mathcal A}$ be the set of all arithmetic progressions in $\mathbb{Z}$. The set of hyperedges is ${\mathcal E}_{N,k}:=\{(A_{1}+A_{2}+\hdots A_{k})\cap [N]\mid A_{i}\in{\mathcal A}\}$. We prove the lower bound $\disc({\mathcal H}_{N,k})=\Omega(N^{k/(2k+2)})$. Note that our result gives back Roth's lower bound in the case $k=1$.

Mathematics Subject Classification (1991): 11K38

Keywords: Discrepancy, arithmetic progressions, Fourier analysis

Mail an Jens Burmeister

[Thu Feb 19 18:56:36 2009]

Impressum