Song, Zhang prove Matrix Spencer conjecture with 8√n bound

Zhao Song and Lichen Zhang have settled the Matrix Spencer conjecture, showing in a new arxiv preprint posted 14 September that for any n symmetric matrices A₁…Aₙ in ℝⁿˣⁿ with operator norm at most 1, a choice of ±1 signs exists such that the signed sum has spectral norm below 8√n. Random signs alone had only ever delivered the matrix-concentration bound O(√(n log n)).

Before this paper, the abstract notes, "the conjecture was known only under rank, block-diagonal, or Frobenius-norm restrictions." The authors also give a randomized constructive algorithm that finds a signing of discrepancy below 12√n with failure probability at most p using n^{3+o(1)} polylog(1/p) arithmetic operations, which the paper says "matches the size n^3 of the dense input up to subpolynomial factors."

The existence proof is a partial-coloring argument built around what the authors describe as "a hereditary Gaussian small-ball bound for the spectral body," proved by interpolating a log-partition function from a diagonal to a noncommutative model under a matrix-weighted Poincaré inequality. Pushing the constant below 8 required closing two sources of slack that a standard partial-coloring proof leaves open, one from the union bound turning Gaussian measure into signs and one from proving the small-ball estimate at too large a radius. The authors close them with "a lossless coding of Gaussian measure into signs" and "smooth spectral barriers with certified coefficients." Two researchers we track posted the link the same day.

On the algorithm side, the abstract says the method projects Gaussian points onto a smoothed spectral body whose derivatives are traces against a single Gibbs matrix, and that "Four successively cheaper ways of maintaining that matrix bring the running time down to n^{3+o(1)}."