Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
Addressing Spencer's foundational 1985 discrepancy theorem, this work dramatically tightens both sides of the matrix discrepancy constant for $A \in [-1,1]^{n \times n}$. By directly rounding the minimizer of an analytic potential function to a hypercube vertex, the authors establish an upper bound of $< 2.9992\sqrt{n} + 4$, proving that three standard deviations suffice. Concurrently, they deliver the first improvement over the 1978 Olson–Spencer $\sqrt{n}$ lower bound by proving an explicit lower bound of $> 1.0000002\sqrt{n}$ via perturbed Hadamard matrices.
Spencer's iconic "six standard deviations suffice" discrepancy bound is finally halved to strictly under three, while the 46-year-old $\sqrt{n}$ lower bound barrier is broken for the first time.
Spencer's 1985 ``six standard deviations suffice'' theorem shows that every $A \in [-1,1]^{n \times n}$ has a sign vector $x \in \{-1,1\}^n$ with $\|Ax\|_\infty \le 6\sqrt{n}$. We show the upper bound $\sqrt{3\operatorname{arsinh}(10)}\sqrt{n}+4 < 2.9992 \sqrt{n} + 4$ by directly rounding the minimizer of a potential function to a vertex of the cube. We also show that, for every power of two $n \ge 2^{50}$, there exists a matrix $A \in \{-1,1\}^{n \times n}$ such that $\|Ax\|_\infty >1.0000002\sqrt{n}$ for every choice of signs $x \in \{-1,1\}^n$. The construction simply replaces a $2^{-22}$ fraction of the columns of a Hadamard matrix with independent random sign vectors. This is the first improvement over the $\sqrt{n}$ lower bound of Olson and Spencer (1978), which uses a Hadamard matrix.