PreprintarXiv licencearXiv
A Proof of the Matrix Spencer Conjecture
Abstract
We develop a novel approach to matrix discrepancy based on matrix small-ball estimates. Specifically, we use a determinantal weight (obtained from the log-barrier) to scale the small-ball probability into a partition function of a tilt of the Gaussian measure. We then employ matrix-weighted Poincaré inequalities to compare this partition function to that of a pinched or diagonal part of the matrix, obtaining \emph{dimension-free} constants. Our technique yields a hereditary small-ball estimate for Gaussian series that should be of independent interest. As the main application, we resolve the Matrix Spencer conjecture: for symmetric n× n matrices A1,…,An with |Ai|≤1, one can efficiently find a coloring x∈{±1}n with |∑i=1n xiAi|=O(√n).
Related
- A simpler proof of the Matrix Spencer Theorem
- Matrix Spencer: Eight Standard Deviations Suffice and an Almost-Linear Time Algorithm for Dense Input
- A proof of the Stanley-Stembridge conjecture
- A streamlined proof of the Kakeya set conjecture in R3
- A proof of Alexander’s Conjecture on an Inequality of Cassels
BibTeX
@misc{akbas2026proof,
title = {{A Proof of the Matrix Spencer Conjecture}},
author = {Emrullah Akbas and Suvrit Sra},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.28816},
eprint = {2608.28816},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.28816},
}
RIS
TY - UNPB
TI - A Proof of the Matrix Spencer Conjecture
AU - Emrullah Akbas
AU - Suvrit Sra
PY - 2026
DA - 2026/08/28
PB - arXiv
DO - 10.48550/arxiv.2608.28816
UR - https://arxiv.org/abs/2608.28816
AB - We develop a novel approach to matrix discrepancy based on matrix small-ball estimates. Specifically, we use a determinantal weight (obtained from the log-barrier) to scale the small-ball probability into a partition function of a tilt of the Gaussian measure. We then employ matrix-weighted Poincaré inequalities to compare this partition function to that of a pinched or diagonal part of the matrix, obtaining \emph{dimension-free} constants. Our technique yields a hereditary small-ball estimate for Gaussian series that should be of independent interest. As the main application, we resolve the Matrix Spencer conjecture: for symmetric n× n matrices A_1,…,A_n with |A_i|≤1, one can efficiently find a coloring x∈{±1}^n with |∑_i=1^n x_iA_i|=O(√n).
ER -