A Walk From Free Probability to Matrix Discrepancy II: Weaver's Problem and the Kadison-Singer Conjecture

Abstract

\cite{mss2015} proved Weaver's discrepancy result existentially, resolving the Kadison--Singer conjecture . Finding such signs efficiently for general inputs remained an open algorithmic question. In the real-arithmetic model, we give a deterministic algorithm running in polynomial time with discrepancy at most 35√ε. The algorithm walks from the origin of the hypercube to a vertex, fixing coordinates as they hit a face. Its potential measures a soft spectral edge of the discrepancy matrix perturbed by an operator-valued free semicircular element. The perturbation's covariance vanishes as the coefficients reach their endpoints. Inspired by the free interpolation approach of Bandeira, Boedihardjo, and van Handel \cite{bbvh2023}, we combine Lehner's variational formula \cite{lehner1999} with spectral Tsallis--1/2 regularization used in \cite{allenZhuLiaoOrecchia2015} and \cite{pesentivladu2026}. The resulting potential has a finite-dimensional SDP formulation, allowing the discrepancy and remaining covariance to be analyzed together. We analyze the optimizer's stability through the linearized Karush--Kuhn--Tucker (KKT) system of a regularized min--max problem, whose stationarity equations are related to the matrix Dyson equation \cite{erdos2019}. This gives the movement rule: either a coordinate can move toward its nearer endpoint at small spectral cost, or a low-curvature direction orthogonal to the current coefficient vector allows further progress. Choosing the better sign of this direction controls discrepancy while increasing the squared distance from the origin. Upcoming work \cite{kathuria2026higherRank} will address higher-rank Kadison-Singer and spectrally thin trees. Lean formalizations of our main discrepancy theorems have been completed and will be released shortly.

Rank-One Matrix Discrepancy and Algorithmic Kadison--Singer
Ekene Ezeunala, Haotian Jiang
arXiv15 Sep 2026PreprintarXiv licenceFull textAnalysis & PDEs Combinatorics & discrete mathematicsarXiv
The A-optimal design problem and the S-matrix conjecture
Teng Zhang
arXiv1 Sep 2026PreprintarXiv licenceFull textAnalysis & PDEsarXiv
The solution to Kadison's problem on orthonormal bases of unitaries for type II₁ factors
Yixin He, Quanyu Tang, Zongben Xu +1
arXiv21 Sep 2026PreprintarXiv licenceFull textAnalysis & PDEsarXiv
Fuglede--Kadison Determinants of Shifted Matrix Semicircles
Vladislav Kargin
arXiv10 Oct 2026PreprintCC BY 4.0Full textAnalysis & PDEs ProbabilityarXiv
Proof of a conjecture of Johnston on binary matrices with low discrepancy
Shalom Eliahou
HAL17 Sep 2026PreprintCC BY-NC-ND 4.0Full textGeneral mathematicsHAL

Cite

BibTeX RIS

BibTeX

@misc{kathuria2026walk,
  title = {{A Walk From Free Probability to Matrix Discrepancy II: Weaver's Problem and the Kadison-Singer Conjecture}},
  author = {Tarun Kathuria},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.18913},
  eprint = {2609.18913},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.18913},
}

RIS

TY  - UNPB
TI  - A Walk From Free Probability to Matrix Discrepancy II: Weaver's Problem and the Kadison-Singer Conjecture
AU  - Tarun Kathuria
PY  - 2026
DA  - 2026/09/16
PB  - arXiv
DO  - 10.48550/arxiv.2609.18913
UR  - https://arxiv.org/abs/2609.18913
AB  - \cite{mss2015} proved Weaver's discrepancy result existentially, resolving the Kadison--Singer conjecture . Finding such signs efficiently for general inputs remained an open algorithmic question. In the real-arithmetic model, we give a deterministic algorithm running in polynomial time with discrepancy at most 35√ε. The algorithm walks from the origin of the hypercube to a vertex, fixing coordinates as they hit a face. Its potential measures a soft spectral edge of the discrepancy matrix perturbed by an operator-valued free semicircular element. The perturbation's covariance vanishes as the coefficients reach their endpoints. Inspired by the free interpolation approach of Bandeira, Boedihardjo, and van Handel \cite{bbvh2023}, we combine Lehner's variational formula \cite{lehner1999} with spectral Tsallis--1/2 regularization used in \cite{allenZhuLiaoOrecchia2015} and \cite{pesentivladu2026}. The resulting potential has a finite-dimensional SDP formulation, allowing the discrepancy and remaining covariance to be analyzed together. We analyze the optimizer's stability through the linearized Karush--Kuhn--Tucker (KKT) system of a regularized min--max problem, whose stationarity equations are related to the matrix Dyson equation \cite{erdos2019}. This gives the movement rule: either a coordinate can move toward its nearer endpoint at small spectral cost, or a low-curvature direction orthogonal to the current coefficient vector allows further progress. Choosing the better sign of this direction controls discrepancy while increasing the squared distance from the origin. Upcoming work \cite{kathuria2026higherRank} will address higher-rank Kadison-Singer and spectrally thin trees. Lean formalizations of our main discrepancy theorems have been completed and will be released shortly.
ER  -

Abstract

Related

Cite