Discrepancy of arithmetic progressions in higher dimensions (Q5960988)

From MaRDI portal
Revision as of 12:27, 9 December 2024 by Import241208061232 (talk | contribs) (Normalize DOI.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article; zbMATH DE number 1731901
Language Label Description Also known as
English
Discrepancy of arithmetic progressions in higher dimensions
scientific article; zbMATH DE number 1731901

    Statements

    Discrepancy of arithmetic progressions in higher dimensions (English)
    0 references
    0 references
    22 April 2002
    0 references
    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.
    0 references
    discrepancy
    0 references
    arithmetic progression
    0 references
    hypergraphs
    0 references

    Identifiers