Discrepancy of arithmetic progressions in higher dimensions (Q5960988): Difference between revisions

The author extends results of \textit{K. F. Roth} [Acta Arith. 9, 257-260 (1964; Zbl 0125.29601)] and \textit{J. Beck} [Combinatorica 1, 319-325 (1981; Zbl 0491.10046)] on nearly sharp bounds for the discrepancy of arithmetic progressions in \([0,N]\) to higher dimensions: Let \[ \text{disc}{\mathcal (H)}:= \min\max\left|\sum_{k=0}^r f(\underline a+k\cdot \underline b)\right|, \] where the maximum extends over all \(\underline a,\underline b\in{\mathbb N}^d\), \(r\in {\mathbb N}\) s.t. \(\underline a+r\cdot\underline b\in[0,N]^d\) and the minimum over all functions \(f\) on \([0,N]^d\) takes values in \(\{-1,1\}\). Then \[ cN^{d\over{2d+2}}\leq\text{disc}(\mathcal H)\leq cN^{d\over{2d+2}}(\log N)^{5/2}. \] Dicrepancy estimates for certain random hypergraphs and lines on an \(N\times N\) lattice are derived.