Discrepancy in generalized arithmetic progressions (Q1039432): Difference between revisions

Sumsets of \(k\) arithmetic progressions \(A_{1}\dots A_{k}\) are called \(k\)-arithmetic progressions. The authors consider the (combinatorial) discrepancy \(D_{k}(N)\) of the set \[ \{P\cap\{1,\dots,N\}: P\;\text{is a}\;k\text{-arithmetic progression}\}. \] Extending K. Roth's lower bound for arithmetic sequences to \(k\)-arithmetic sequences the authors show \(D_{k}(N)=\Omega(N^{\frac{1}{2}})\) (for all \(k\geq 2\)), which is best possible up to a (possible) logarithmic factor. The case \(k\geq 3\) was already known due to Přívětivý (2006), the result also holds for multicolor versions of discrepancies.