Discrepancy of arithmetic progressions in higher dimensions

DOI10.1006/JNTH.2001.2704MaRDI QIDQ5960988zbMATH OpenOpenAlexFDO

Authors Benedek Valkó

Publication date 22 April 2002

Published in Journal of Number Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jnth.2001.2704

zbMATH Keywords

arithmetic progressiondiscrepancyhypergraphs

Mathematics Subject Classification ID

Irregularities of distribution, discrepancy (11K38)

Review text

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 NEWLINE\[NEWLINE\text{disc}{\mathcal (H)}:= \min\max\left|\sum_{k=0}^r f(\underline a+k\cdot \underline b)\right|,NEWLINE\]NEWLINE 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 NEWLINE\[NEWLINEcN^{d\over{2d+2}}\leq\text{disc}(\mathcal H)\leq cN^{d\over{2d+2}}(\log N)^{5/2}.NEWLINE\]NEWLINE Dicrepancy estimates for certain random hypergraphs and lines on an \(N\times N\) lattice are derived.

Recommendations

• Discrepancy of cartesian products of arithmetic progressions
• Discrepancy of Sums of Arithmetic Progressions
• Multicolor discrepancy of arithmetic progressions (extended abstract)
• Discrepancy in arithmetic progressions
• Discrepancy of Sums of two Arithmetic Progressions

Cites work

• Discrepancy in arithmetic progressions
• scientific article; zbMATH DE number 3613118 (Why is no real title available?)
• Remark concerning integer sequences
• Roth's estimate of the discrepancy of integer sequences is nearly sharp

Cited in

(16)

• Discrepancy in generalized arithmetic progressions
• ReLaTIve. An Ansi C90 software package for the Real Laplace Transform Inversion
• Explicit small sets with \(\varepsilon\)-discrepancy on Bohr sets
• The higher dimensional analogue of certain estimates of Roth and Sárközy
• Large discrepancy in homogeneous quasi-arithmetic progressions
• Limitations to equidistribution in arithmetic progressions
• Multicolor discrepancy of arithmetic progressions (extended abstract)
• Discrepancy of centered arithmetic progressions in \(\mathbb{Z}_p\) (extended abstract)
• Well-distributed 2-colorings of integers relative to long arithmetic progressions
• Discrepancy of Sums of Arithmetic Progressions
• Discrepancy of Sums of two Arithmetic Progressions
• A discrepancy problem: balancing infinite dimensional vectors
• Discrepancy in arithmetic progressions
• The discrepancy of boxes in higher dimension
• Discrepancy of arithmetic progressions in grids
• Discrepancy of arithmetic progressions in boxes and convex bodies

This page was built for publication: Discrepancy of arithmetic progressions in higher dimensions

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