Paper 2026/2123

Two Standard Deviations Are Necessary for the Kadison-Singer Problem

Abstract

Let $C_0$ be the least constant such that, for every finite family of vectors $u_1,\ldots,u_n\in\mathbb C^d$ and independent finitely supported real random variables $\xi_i$, there are values $\varepsilon_i\in\operatorname{supp}(\xi_i)$ satisfying $\|\sum_{i=1}^n(\varepsilon_i-\mathbb{E}[\xi_i])u_i u_i^*\| \leq C_0\|\sum_{i=1}^n\mathrm{Var}[\xi_i](u_i u_i^*)^2\|^{1/2},$ where $\|\cdot\|$ denotes the operator norm. This rank-one matrix discrepancy formulation generalizes the signing formulation of the Kadison--Singer problem [KS59], resolved by Marcus, Spielman, and Srivastava [MSS15b]. Let $C_1$ be the least constant such that, for every $\epsilon>0$ and every finite family in $\mathbb C^d$, in every dimension $d$, satisfying $\sum_{i=1}^n u_i u_i^*=I$ and $\max_{i\in[n]}\|u_i\|^2\leq\epsilon$, there are signs $\varepsilon_1,\ldots,\varepsilon_n\in\{-1,1\}$ such that $\|\sum_{i=1}^n\varepsilon_i u_i u_i^*\|\leq C_1\sqrt\epsilon.$ Taking the $\xi_i$ to be independent symmetric signs gives $C_1\leq C_0$, since $\|\sum_{i=1}^n(u_i u_i^*)^2\|\leq\epsilon$ under these hypotheses. The general formulation allows arbitrary finite real supports and does not require $\sum_{i=1}^n u_i u_i^*=I$. Kyng, Luh, and Song [KLS20] proved $C_0\leq4$. We prove $2\leq C_1\leq C_0\leq2.176$. This improves the bounds $\sqrt2\leq C_0\leq3$ of Xie, Xu, and Zhu [XXZ21]. We conjecture that the optimal constant is $C_0=2$.