PaperlayerView exact revision on arXiv

Source-linked AI summary

A simpler proof of the Matrix Spencer Theorem

Nikhil Bansal, Yunbum Kook

arXiv:2609.16100v1math.COcs.DMmath.PR

TL;DR

Akbas and Sra’s Matrix Spencer theorem has a quite technical proof. This paper gives a shorter proof using a simpler potential and a recent matrix Brascamp–Lieb inequality, yielding a full ±1 assignment with O(d^1/2) discrepancy.

  • Problem

    The proof of Akbas and Sra’s Matrix Spencer theorem is quite technical.

    Source: §1 · p. 1

  • Method

    The paper gives a shorter analysis using a simpler potential and a recent matrix Brascamp–Lieb inequality, within the standard partial coloring method.

    Source: §1 · p. 1, §2 · p. 1

  • Results

    O(d^1/2) discrepancy yields a full ±1 assignment after O(log n) rounds of partial coloring.

    Source: §2 · p. 1

  • Takeaways & Limitations

    The simpler proof suffices for Theorem 1.1 and highlights the key ideas of [AS26], despite weaker intermediate results at some steps.

    Source: §1 · p. 1

    The Gaussian-volume argument gives only Eγn e^-L(X) ≥ exp(−Ω(d)), too weak when n ≪ d.

    Source: §2.1 · p. 2

Abstract

from arXiv · show

We give a simple exposition of the Matrix Spencer theorem due to Akbas and Sra [AS26].

1 Introduction

The section presents the Matrix Spencer theorem of Akbas and Sra [AS26], generalizing Spencer’s classical result [Spe85]. It motivates a substantially shorter proof using a simpler potential and a recent matrix Brascamp–Lieb inequality.

1 Introduction

  • Theorem 1.1 gives a sign choice for any collection of real symmetric d×d matrices with operator norm at most 1.The theorem’s bound on the signed sum is not fully specified in the supplied passage.Source: §1 · p. 1
  • The exposition replaces the technical proof of [AS26] with a substantially shorter analysis using a simpler potential and a recent matrix Brascamp–Lieb inequality.The proof gives weaker results at some intermediate steps but still suffices for Theorem 1.1.Source: §1 · p. 1
  • The authors report that their proof followed multiple iterations with GPT 6, while stating that the exposition is theirs and they take responsibility for its content and correctness.Source: §1 · p. 1

2 Partial Coloring

A Gaussian-volume argument yields partial colorings, while a modified barrier and interpolation control the volume bound. Repeating the partial coloring across geometrically shrinking active sets gives a full ±1 assignment with discrepancy O(d^1/2).

2 Partial Coloring

  • O(d^1/2) discrepancy follows by iterating partial colorings that assign a constant fraction of active coordinates each round, until all coordinates receive ±1 values.When n ≤ d active coordinates remain, the partial assignment has discrepancy O(d^1/3 n^1/6).Source: §2 · p. 1

2.1 Modified Logarithmic Barrier

  • The original log-barrier proxy yields only exp(−O(d)) Gaussian expectation, too weak when n ≪ d, so the proof reduces the quadratic weight and increases the higher-order weights.The modified potential uses s(X)=−log(I−X^2)−X^2 and parameters b=16√η and α=16/√η, where η=n/r^2.Source: §2.1 · p. 2

2.2 Interpolation

  • Along the interpolation X_t=tX, the proof tracks F(t)=log Eγn e^(−V(X_t)) and controls its derivative to obtain the required Gaussian-volume lower bound.The argument starts from F(0)=0 and aims to establish F(1)≥−n/10.Source: §2.2 · p. 2

2 Partial Coloring

  • The Gaussian-volume criterion converts sufficient measure of the symmetric convex set into a vector in {−1,0,1}^n with at least n/4 nonzeros.The argument applies the criterion to K={x:∥∑ᵢxᵢAᵢ∥≤r}.Source: §2.2 · p. 2, §2 · p. 2

2.2 Interpolation

  • The interpolation estimates give F(1)≥−n/10, establishing the Gaussian-volume bound used to conclude Theorem 1.1.The conclusion uses the chosen b and α and the specified value of η.Source: §2.2 · p. 3

2.3 Proving Moment Bounds via Matrix Brascamp–Lieb

  • The moment estimates use the matrix Brascamp–Lieb inequality with curvature lower bound κ_M=1/2 for the matrix density R dµ.The stated justification is that Gaussianity and convexity of V make µ sufficiently strongly log-concave.Source: §2.3 · p. 4

2.3.1 Bounding Second Moment

  • Bounding the largest eigenvalue of S_t gives 0 ⪯ S_t−I ⪯ 8t^2ηI, controlling the second moment Eµ[XRX].The proof applies matrix Brascamp–Lieb to Xz for a top eigenvector z of S_t.Source: §2.3.1 · p. 4

2.3.2 Bounding Fourth Moment

  • For the fourth moment, the proof applies matrix Brascamp–Lieb to X^2z_a over an eigenbasis of S and bounds the resulting trace terms.The displayed bound uses T1≤2n Tr(S−I).Source: §2.3.2 · pp. 4–5

A Matrix Brascamp–Lieb Inequality

This appendix recalls the standard Brascamp–Lieb inequality and its matrix counterpart, introduced by Cordero-Erausquin [CE19, Theorem 4].

A Matrix Brascamp–Lieb Inequality

A.1 Weighted Means, Variance, and Curvature

The section moves from scalar weighted inequalities to a matrix-weighted Brascamp–Lieb framework, defining curvature and identifying conditions for its use, including on convex domains.

Weighted Means, Variance, and Curvature

  • If ∇²ϕ ⪰ κI_n for κ > 0, the scalar variance satisfies a Poincaré bound by κ^-1 times the weighted gradient energy.Source: §A.1 · p. 6
  • The matrix extension replaces scalar density w with a smooth matrix weight M and defines a weighted mean for vector-valued functions.The matrix weight is defined on a nonempty, open, convex domain.Source: §A.1 · p. 6
  • The curvature operator Θ_M is introduced on block vectors, and for scalar weights M = e^-ϕ, −Θ_M reduces to ∇²ϕ.Source: §A.1 · p. 6
  • The section gives a symmetric block-matrix representation of −Θ_M in the G metric, with n × n blocks of size d × d.For Ω = R^n, it then considers applying the matrix Brascamp–Lieb inequality when −Θ_M is positive definite in that metric.Source: §A.1 · p. 6
  • A convex-domain matrix-weighted Poincaré inequality is stated under the condition K_M ⪰ κG, using a version proved in [AS26, Lemma 2.3].The text notes that convexity adds a favorable term in the Bochner argument behind the matrix Brascamp–Lieb inequality, a point [AS26] essentially confirms.Source: §A.1 · p. 6

B Curvature of the Barrier

The appendix computes the curvature contribution of the barrier by expressing the matrix-weighted curvature in terms of derivatives of the barrier and bounding the resulting terms.

B Curvature of the Barrier

  • The barrier setup uses R = (I − X)^-1 and M = ρR, with −log ρ = ∥g∥²/2 + V(X) + O(1).It sets E_i = R^1/2 D_i R^1/2.Source: B Curvature of the Barrier · p. 7
  • After dividing by ρ and conjugating each block by R^-1/2, the curvature matrix becomes I_nd + H ⊗ I_d − [E_jE_i]_i,j.The preceding calculation gives (K_R)_ij = −R D_j R D_i R.Source: B Curvature of the Barrier · p. 7
  • The proof splits E_i into D_i + Δ_i and handles [E_jE_i]_i,j through its D_iD_j, Δ_iΔ_j, and mixed terms.For the Δ_iΔ_j term, it invokes the block trace inequality [Lin16, Proposition 2.1].Source: B Curvature of the Barrier · pp. 7–8
  • The Hessian of Tr s(X) is computed by writing Tr s(X) = V_- + V_+ − Tr X² and differentiating V_- and V_+.In an eigenbasis of X, the comparison needed for the Δ-term reduces to p_a p_b + 2√(r_a r_b) ≥ 3, proved by AM-GM.Source: B Curvature of the Barrier · p. 8
  • The remaining T3 bound uses block Cauchy–Schwarz [AS26, Lemma 3.5] and Young’s inequality.Source: B Curvature of the Barrier · p. 8
Loading 2609.16100v1…