Grid arithmetic progression discrepancy tightness

Conjecture (Section 7) · arXiv:2110.15429

arXiv Conjecture medium confidence— first stated 2021-10-28

Authors: Jacob Fox, Max Wenqiang Xu, Yunkun Zhou

Status partial high confidence

The conjecture that the lower bound in Theorem 1.3 is tight up to a constant factor (i.e., no logarithmic factor) remains open. Li and Nikolov (2025, arXiv:2504.12598) improved the upper bound gap from a factor of log|Omega_N|/(log log|Omega_N|) to sqrt(log|Omega_N|), using factorization norms, but explicitly state that removing this final sqrt(log) factor is beyond their methods. The conjecture itself is restated as open in that paper.

Cited literature (1)

partial Discrepancy of Arithmetic Progressions in Boxes and Convex Bodies (2025)

Lily Li, Aleksandar Nikolov · arXiv preprint · arXiv:2504.12598

Improves the upper bound for disc(A_N) from a log|Omega_N|/(log log|Omega_N|) factor above the conjectured tight bound to a sqrt(log|Omega_N|) factor, via factorization norms; the tight constant-factor conjecture remains explicitly open.

Reviewer notes. The source paper was published in Mathematika (2024). The main open question is whether the sqrt(log) gap in arXiv:2504.12598 can be removed to match the lower bound by a constant depending only on d.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. The lower bound for the discrepancy of arithmetic progressions in grids given in Theorem 1.3 is tight up to the constant factor, i.e., for any positive integer $d$ and $N = (N_1, \ldots, N_d)$ with $N_1 \cdots N_d \geq 3$, $$\mathrm{disc}(\mathcal{A}_N) = \Theta_d\!\left(\max_{I \subseteq [d]} \left(\prod_{i \in I} N_i\right)^{\frac{1}{2|I|+2}}\right).$$

Context

Theorem 1.3 establishes matching lower and upper bounds for the discrepancy of arithmetic progressions in general grids of differing side lengths, but the upper bound carries an extra sub-logarithmic factor $\frac{\log(N_1 \cdots N_d)}{\log\log(N_1 \cdots N_d)}$ relative to the lower bound. The authors conjecture in their concluding remarks (Section 7) that this gap is an artifact of the proof and the lower bound is in fact tight up to a constant depending only on $d$.

Notes. Section 7 is not reproduced in the PDF extraction; the conjecture is described by reference in the paper's organization paragraph. The statement above is reconstructed from Theorem 1.3 and the prose description 'a conjecture that the lower bound for the discrepancy for grids in Theorem 1.3 is tight up to the constant factor'.

Source paper

Discrepancy of arithmetic progressions in grids
Jacob Fox, Max Wenqiang Xu, Yunkun Zhou · 2021-10-28
https://arxiv.org/abs/2110.15429 PDF source