Boolean Small-Ball Inequalities for Discrepancy Theory

Abstract

We prove new small-ball inequalities for boolean matrix-series. The leading example is ${\mathbb{E}}_s[\text{det}(I-S^2{)}^{\beta }{1}_{\{\Vert S\Vert <1\}}]\ge e^{-O(\beta \tau )}$, which holds for boolean matrix-series $S={\sum }_i{s}_i{A}_i$ formed using symmetric matrices $A_1,\dots ,A_n$ and uniformly random signs $s\in \{\pm 1{\}}^n$. Specifically, this inequality holds for all $\beta \ge 1$ with $\tau ={\sum }_i\text{Tr}{A}_i^2$, as soon as the maximum of $(\text{Tr}{A}_i^2{)}_{i=1}^n$ and a certain variance term are bounded above by universal constants. The proof combines the Gaussian reciprocal estimate of (Akbas and Sra 2026), the directional-variation signing theorem of (Guo, Fang, and Lu 2026), and a replica argument that turns existence into a Gibbs law on good signings. Most notably, boolean small-ball delivers a new, interlacing-free proof of Kadison-Singer (most general case); it also recovers Matrix Spencer and Komlós as quick corollaries, while yielding more than six almost immediate proofs of an assortment of discrepancy theoretic problems.

37 pages, comments welcome