OpenAlex ·

Boolean Small-Ball Inequalities for Discrepancy Theory

Emrullah Akbas and Suvrit Sra

Published
Source
OpenAlex
Published in
arXiv (Cornell University)
DOI
10.48550/arxiv.2609.20785
Original
Read it at the publisher
Topics
CombinatoricsNumerical AnalysisProbabilityStatistics Theory

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.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

Read it on ReadSearch

Each opens after you create an account, and brings you back to this paper.

Already a reader? Sign in

All new papers in Combinatorics

Get the few papers worth your time in Combinatorics every morning.

ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.

Papers belong to their authors and publishers; every page here links to the original. All research topics