Boolean Small-Ball Inequalities for Discrepancy Theory

Source abstract

We prove new small-ball inequalities for boolean matrix-series. The leading example is $\mathbb E_s[{\text{det}(I-S^2)^β\,\mathbf 1_{\{\|S\|<1\}}}]\ge e^{-O(βτ)}$, which holds for boolean matrix-series $S=\sum_i s_iA_i$ formed using symmetric matrices $A_1,\dots,A_n$ and uniformly random signs $s\in\{\pm1\}^n$. Specifically, this inequality holds for all $β\ge1$ with $τ=\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.