PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Tarun Kathuria

arXiv:2609.18913v1cs.DSmath.FA

TL;DR

Weaver’s discrepancy formulation asks for signs making a matrix sum small and is connected to the Kadison–Singer conjecture. This paper constructs a full signing with a deterministic walk and proves a discrepancy bound below 35δ.

  • Problem

    The paper studies finding signs that make the matrix sum small in Weaver’s discrepancy formulation, which is connected to the Kadison–Singer conjecture.

    Source: §1 · p. 1

  • Method

    A deterministic algorithm constructs the signs by walking inside the coefficient cube, with polynomial runtime in the real-arithmetic model.

    Source: §1 · pp. 1–2

  • Results

    The deterministic walk returns a full signing with discrepancy less than 35δ and runs in time polynomial in n,m in Model 8.1.

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

  • Takeaways & Limitations

    The work gives an algorithmic signing construction for the finite-dimensional discrepancy formulation connected to Kadison–Singer.

    Source: §1 · p. 1

    The runtime bound is for the real-arithmetic model; no binary-encoding bound is asserted.

    Source: §8 · p. 21

Abstract

from arXiv · show

\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\sqrt\varepsilon$. 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.

1 Introduction

The paper constructs signs for Weaver’s discrepancy problem with a deterministic polynomial-time walk in the real-arithmetic model. It analyzes the walk through a spectral potential and the response of a regularized variational problem, while distinguishing its guarantee and computational model from related results.

1 Introduction

  • The walk constructs a signing for the two-part matrix partition problem and runs in time polynomial in n and m in the real-arithmetic model.The signing partitions the labels into positive and negative sets.Source: §1 · pp. 1–2

1.1 The idea of the walk

  • When coordinate tests fail, the walk uses a low-curvature direction orthogonal to the current coefficient vector and chooses the better of its two signs.Both candidate steps increase the squared distance from the origin by the same amount; the proof account controls spectral drift, rounding cost, and remaining distance to a vertex.Source: §1.1 · p. 2

1.2 Free interpolation and variational stability

  • A regularized min–max problem yields a linearized KKT system for the optimizer’s response, whose analysis is related to matrix Dyson equation stability.The system includes a density regularizer and trace constraint; a joint-kernel projection is used where direct inversion is inadequate.Source: §1.2 · pp. 2–3

1.3 Related discrepancy results

  • The paper distinguishes its coarse-constant local walk in the real-arithmetic model from related discrepancy guarantees and computational models.It also points to higher-rank Kadison–Singer and spectrally thin trees as upcoming work, and says Lean formalizations of the main discrepancy theorems are complete and will be released shortly.Source: §1.3 · p. 3

2 The potential and the local walk

The potential couples the signed discrepancy center to a source map that vanishes at the cube’s faces, while a density regularizer smooths the spectral maximum. The walk uses outward coordinate steps when affordable and otherwise chooses a low-curvature direction orthogonal to the current coefficient vector.

2.1 State, source, and scales

  • The potential combines the signed center, a source determined by the live coefficients, and a density regularizer; it dominates the discrepancy norm and starts at ℱ(0) ≤ 34δ.At a vertex the source vanishes; the profile is positive on live coordinates and has negative second derivative.Source: §2.1 · pp. 3–4

2.2 The algorithm

  • The walk first tests short outward coordinate moves, then uses a low-curvature direction orthogonal to the live coefficient vector and chooses its better sign.Each curvature move increases the squared coefficient norm by exactly h^2; the walk rounds coordinates near endpoints and returns a full signing.Source: §2.2 · p. 5

2.3 Why a covariance map belongs in the potential

  • The source map retains atom-direction information across both signs, matching the operator-valued covariance in the free model rather than only its value at the identity.The variational potential analyzes the optimizer’s response as the center and source evolve; covariance alone does not imply the free model’s higher-order structure.Source: §2.3 · pp. 5–6

2.4 The scalar example and the choice of profile

  • In the scalar example, holding transport fixed makes the outward certificate explicit: ℓ_i q_i ≥ 1 makes both diagonal entries nonpositive and certifies the step.The quadratic profile supplies uniform negative second derivative, while the smoothed absolute-value term gives a substantial finite secant even at zero; 1 − z^2 has secant a there.Source: §2.4 · p. 6

3 A density potential with a shared source

The shared-source density potential is continuous across cube faces and uses a transport variational formula to expose how its optimizing density responds. Its potential bounds and density floor provide control across the cube, while the walk’s initial value is smaller than the uniform bound.

3 A density potential with a shared source

  • The potential is continuous on the closed cube, including faces where the source support changes.The source profile is smooth, positive in the interior, and zero at ±1.Source: §3 · pp. 6–7

3.1 Transport and the optimizing density

  • The fidelity transport identity replaces a square-root term with an optimization over a positive matrix, enabling finite-step comparisons and differentiation of the optimizer’s stationarity equation.On each open live face, the maximizing density is unique, positive definite, and smooth in the coefficients.Source: §3.1 · p. 8

3.2 The size of the potential and its optimizing density

  • Every optimizing density has an explicit positive lower eigenvalue bound independent of the least positive source eigenvalue.The potential has a uniform bound of 1 + 34δ, while the walk starts at ℱ(0) ≤ 34δ; the smaller initial value supports the discrepancy guarantee.Source: §3.2 · p. 10

4 Local outward comparison

The local outward comparison uses a uniform profile secant and the current optimizing transport to certify finite coordinate steps. If candidate tests fail, the resulting probe bounds feed the curvature argument.

4 Local outward comparison

  • The outward secant is at least |c′(x_i)| and has a uniform lower bound for a coordinate with margin at least a.The smoothed profile makes the finite-step bound hold uniformly, including at zero.Source: §4 · p. 10
  • Holding the old optimizing transport fixed gives an upper bound on the new potential, and ℓ_i q_i ≥ 1 certifies the outward step.The old density maximizes the fixed-transport objective at the current state, so the comparison applies to the full finite step.Source: §4 · pp. 10–11
  • If every candidate increases the potential, each nonzero live label satisfies ℓ_i q_i < 1, bounding the transport probes used in the curvature argument.These probe bounds control the optimizer’s transport without computing it in the algorithm.Source: §4 · p. 11

5 Differentiating the optimized potential

The section differentiates the optimized potential by tracking the coupled response of its maximizing density and minimizing transport. The resulting Hessian formula separates direct source curvature from the cost of reoptimization.

5.1 Linearizing the density and transport equations

  • The stability analysis follows the matrix Dyson equation viewpoint, but the coupled system retains a matrix-valued regularizer and trace constraint.The regularizer generally cannot be absorbed into a scalar spectral parameter.Source: §5.1 · p. 11
  • Differentiating density stationarity and transport normalization on a fixed open live face yields a unique linearized KKT system for the optimizer derivatives.The density variation is full-space, while transport is restricted to the source support.Source: §5.1 · pp. 11–12

5.2 Eliminating the transport and identifying the response

  • The regularizer makes the full response operator invertible, but its inverse can reflect small source eigenvalues.Section 6 bounds the needed response quadratic form in changed coordinates instead of estimating that inverse separately.Source: §5.2 · p. 13
  • The joint Hessian formula separates favorable direct source curvature from an optimized response that could overwhelm it.Its maximizing variation is the full optimizer derivative.Source: §5.2 · p. 13

6 A general curvature estimate for concave scalar weights

The section bounds reoptimization curvature for concave scalar source weights. Balanced coordinates and averaging over compatible responses yield a negative-curvature direction orthogonal to the current coefficient vector.

6 A general curvature estimate for concave scalar weights

  • Failed outward tests bound transport probes, allowing source negative curvature to survive density reoptimization and yield a direction orthogonal to the current coefficient vector.The proof balances the transport equation, then averages over compatible coefficient and transport responses.Source: §6 · p. 14, §6.2 · p. 18

6.1 Balanced variables and the joint density response

  • Balanced-source identities bound the fixed-point operators and their Gram-type matrices, including T R T ⪯ Γ and T_J R T_J ⪯ Γ.These inequalities support the response bound in balanced coordinates.Source: §6.1 · p. 15
  • Legal coefficient-response pairs are an analytic device for proving low curvature; the implemented algorithm instead obtains a direction from the Hessian.The response bound avoids estimating the inverse of Λ, which has a kernel.Source: §6.1 · p. 16

6.2 Averaging over compatible directions

  • Averaging over compatible directions shows that the raw Hessian on the live part of x⊥ has a negative eigenvalue.The resulting direction is physical and orthogonal to x, so either sign can increase squared coefficient norm.Source: §6.2 · p. 18

7 Small movements and deterministic finite completion

The section turns the curvature alternative into a finite deterministic walk, controlling spectral cost while making progress toward a hypercube vertex. Its signing guarantee is discrepancy less than 35δ.

7.1 Boundary rounding and its total cost

  • Rounding a coordinate near the boundary removes its source weight while leaving the final signed atom in the center H(x).Rounding is applied before movement and after each subsequent movement.Source: §7.1 · p. 19, §7.4 · p. 20

7.2 Choosing a sign by potential value

  • Choosing the sign with the smaller reported potential value controls spectral cost by comparing the two symmetric candidate movements.With approximate candidate values, the bound incurs an additional 2ν.Source: §7.2 · pp. 19–20

7.3 Progress for every movement

  • A unit movement direction orthogonal to x decreases the squared-norm deficit by exactly h² for either sign.Boundary rounding cannot increase that deficit.Source: §7.3 · p. 20

7.4 Finite completion and spectral control

  • Every qualifying walk completes before its movement horizon because each nonterminal movement increases squared norm by at least h².The stated horizon is ⌈16n/h²⌉ movements.Source: §7.4 · p. 20
  • Discrepancy less than 35δ is guaranteed for a full signing returned by a walk satisfying the stated properties.The walk completes in finite time while maintaining its spectral account.Source: §7.4 · p. 20

7.5 Existence without computational assumptions

  • For each fixed input, exact local choices yield the walk and signing without assuming the computational model.The existence argument uses a finite uniform fourth-derivative bound on relevant segments.Source: §7.5 · p. 21

8 The exact semidefinite value problem

The section represents the potential as a finite semidefinite program (SDP), making it a value that the algorithm can query. It also derives an equal-valued dual, including for singular sources.

8 The exact semidefinite value problem

  • The runtime is polynomial in the stated real-arithmetic model, with no binary-encoding bound asserted.The model assumes a deterministic additive-value SDP solver and an exact eigendecomposition primitive.Source: §8 · p. 21
  • The actual potential equals an SDP optimum over D × D matrices, with a direct real formulation using 4D² − 1 affine variables and a block-diagonal pencil of order 10D.The primal identities establish equality with the potential, including singular densities.Source: §8 · p. 22

8.1 A dual derived from the same variational identities

  • The semidefinite dual and transport infimum have the same value as the potential, even for singular sources.For singular sources, equality is established by approximating dual tuples; an attaining dual tuple need not exist.Source: §8.1 · pp. 23–24

9 The finite value-query walk

The finite walk uses potential-value queries to choose affordable outward steps or, when those fail, a low-curvature direction orthogonal to the live coefficients. Finite differences and a tangent frame make that choice implementable, and the verified walk completes with the stated discrepancy bound.

9 The finite value-query walk

  • Value tolerances control outward-move cost and preserve curvature hypotheses when tests fail; finite differences approximate the raw Hessian on the orthogonal space.The derivative bounds used for the stencils and movement segments apply at prepared states along live directions with |b_i|≤2.Source: §9 · p. 24

9.1 Local tests imply constrained curvature

  • An accepted local outward move increases the actual potential by at most βh²/2; rejecting every candidate implies negative curvature on the live part of x⊥.The local potential values are queried to accuracy βh²/8.Source: §9.1 · p. 24

9.2 Computing the tangent frame

  • The tangent frame is an orthonormal basis of the live coefficient vector’s orthogonal complement and is computable with polynomially many scalar operations, comparisons, and square roots.Its construction requires no spectral decomposition.Source: §9.2 · p. 25

9.3 Finite differences and direction selection

  • When all outward tests fail, value stencils and a tangent frame yield a unit live direction orthogonal to the coefficients with curvature below β/2.An alternative is to obtain curvature by differentiating the stationarity equations and solving for first responses; no second derivatives of the optimizers are needed.Source: §9.3 · p. 25

9.4 Verification of the full walk

  • The walk completes and returns discrepancy less than 35δ≤35√ε, with its arithmetic bound supplied by Theorem D.2.Outward steps and physical curvature steps have coordinate magnitudes at most ρ/16; each final rounding is within distance ρ of its endpoint.Source: §9.4 · p. 26

10 AI Usage

The paper records the AI tools used in developing its approach, SDP representation, proof strategies, and Lean formalizations. Its appendix collects standard matrix and analytic facts, including fidelity formulas and tools used in subsequent arguments.

10 AI Usage

  • Gemini contributed the semidefinite representation of the Tsallis–1/2 regularized potential, while ChatGPT and GPT 6 Astra Ultra assisted with proof strategies and Lean formalizations.The author says the operator-valued K-transform approach or regularizer variants were conceived in 2022–2023; GPT 6 Astra Ultra was used for Matrix Spencer and Weaver/Kadison–Singer formalizations.Source: §10 · p. 26

A Standard matrix and analytic facts

  • The appendix states finite-dimensional matrix and fidelity facts and notes that its use of them requires no quantum-mechanics background.The paper uses the unsquared quantity for fidelity; the stated formulas are attributed to [24, Theorems 3.17 and 3.19, equation (3.110)].Source: A Standard matrix and analytic facts · p. 27, §A.1 · p. 27

A.1 Positive matrices and fidelity

  • For positive semidefinite matrices, the appendix gives standard fidelity formulas, including a unique minimizer characterized by ZQZ=P for positive definite inputs.For singular inputs, the infimum need not be attained; the formulas are cited as [24, Theorems 3.17 and 3.19, equation (3.110)].Source: §A.1 · p. 27

A.2 Implicit differentiation and complex extensions

  • The appendix states the smooth implicit function theorem and says it is applied to real coordinates on Hermitian matrix space after invertibility of the stationarity system is checked.The derivative equation follows by differentiating the implicit solution identity; the theorem is cited as [10, Appendix B].Source: §A.2 · p. 28
  • The appendix uses the principal matrix square root’s holomorphic dependence and Cauchy’s estimate to bound derivatives on complex lines through matrix-valued parameter spaces.The square-root spectral condition is checked for each complex perturbation; the function bounded in the Cauchy estimate is scalar.Source: §A.2 · p. 28

B Quantitative regularity of the optimized value

The section establishes quantitative derivative control for the optimized potential by extending the joint objective to a complex neighborhood and controlling changes in its optimizing density. The resulting bounds cover second through fourth derivatives along prepared states and live directions.

B Quantitative regularity of the optimized value

  • Relative perturbations of the source give a complex neighborhood independent of its smallest positive eigenvalue, while derivative bounds may still grow as ζ shrinks.The paper controls the effect of those growing derivatives together with the changing density rather than assuming a constant bound.Source: B Quantitative regularity of the… · pp. 28–29
  • A joint complex extension of the objective exists on a neighborhood in coefficient and full-matrix variables, with bounded absolute value and mixed derivatives of orders two through four.The square-root spectral hypothesis is verified through numerical-range bounds; the extension agrees with the real objective at real inputs.Source: B Quantitative regularity of the… · pp. 29–30
  • The optimized potential’s second through fourth derivatives are bounded by M along live directions with |b_i|≤2 for |t|≤ρ/16 at prepared states.The density change is controlled using coercivity, while fidelity concavity only increases that coercivity.Source: B Quantitative regularity of the… · pp. 30–31

C Scalar realization and interior bounds for the SDP

The appendix gives a scalar SDP realization with polynomial interior bounds and accounts for the arithmetic work of the walk. The realization and stated bounds avoid dependence on an inverse source eigenvalue.

C Scalar realization and interior bounds for the SDP

  • The source-perturbed SDP has a reciprocal inner-radius bound polynomial in D and reciprocal value accuracy, without a source inverse-eigenvalue parameter.The stated polynomial inner-radius bound also supports a strictly feasible realization.Source: C Scalar realization and interior… · p. 31
  • The SDP’s coefficients can be materialized from the vectors, x, and θ with polynomially many real arithmetic operations, using no source inverse.The construction uses finite sums and scalar square roots for c(x_i).Source: C Scalar realization and interior… · pp. 31–32

D Polynomial parameters and arithmetic work

D.1 Work of the tangent frame and spectral calls

For a fixed solver in Model 8.1, the arithmetic work is polynomial in n and m. The section also identifies the finite-dimensional potential with a soft spectral edge of a free semicircular perturbation.

D.1 Work of the tangent frame and spectral calls

  • Each iteration’s spectral direction uses two matrix multiplications and one exact eigendecomposition, for polynomial work in n.There are at most T spectral calls, and the final coefficient array is returned directly.Source: §D.1 · p. 32
  • A polynomial in n and m bounds Algorithm 1’s arithmetic work for a fixed solver in Model 8.1.The algorithm follows a deterministic sequence of states and stops at a vertex.Source: §D.1 · pp. 32–33
  • At most T movements and n boundary roundings are needed, with polynomially many value and Hessian calls per iteration.Each queried state stays in the cube with frozen coordinates fixed; the scalar SDP arrays have size at most L_m = 6400m^4 + 16m^2 + 2.Source: §D.1 · p. 33

E The marginal soft edge of a free semicircular operator

  • The finite-dimensional potential is identified with a soft spectral edge of an operator-valued semicircular perturbation.Lehner’s variational formula eliminates the free operator, while the regularizer remains on the matrix marginal of the test state.Source: E The marginal soft edge of a free… · p. 33

E.1 The free operator and the marginal soft edge

This section relates a free semicircular perturbation’s upper spectral edge to finite-dimensional variational optimization. It derives Lehner’s formula, connects its resolvent equation to the matrix Dyson equation, and establishes the regularized marginal duality.

E.1 The free operator and the marginal soft edge

  • The free operator is built on full Fock space from creation operators whose semicircular family has a finite-dimensional matrix marginal.The regularized joint-state formulation uses the Tsallis–1/2 entropy of that marginal.Source: §E.1 · pp. 33–34
  • Theorem E.1 gives an exact marginal-edge identity, including states with singular or zero source.The regularization error in the lower bound depends only on the finite matrix dimension, despite the infinite-dimensional auxiliary space.Source: §E.1 · p. 34

E.2 Lehner’s formula and the matrix Dyson equation

  • Lehner’s upper-edge formula is extended to every Hermitian center, and its finite-dimensional infimum is equivalent to an SDP.The block-positivity reformulation yields an affine matrix inequality in the scalar and positive definite transport variable.Source: §E.2 · p. 34
  • A Fock-space Schur complement derives the resolvent equation for the free operator, identified as the matrix Dyson equation outside the upper spectrum.The regularized optimization selects a different transport through its density stationarity equation.Source: §E.2 · pp. 34–35

E.3 Marginal duality and the regularized transport

  • The marginal duality identifies the regularized free-edge expression with the implemented potential, including the singular-source case.The transport infimum and joint-state supremum need not be attained, although the density maximum defining F(x) is attained.Source: §E.1 · p. 34, §E.3 · p. 36
  • The variational transport adds a density regularizer and trace-one constraint to the ordinary resolvent equation, making its response a regularized stability problem.The paper relates this analysis structurally to linearized Dyson equations near edges while specifying that its operators and estimates are particular to the density potential.Source: §E.3 · p. 36
Loading 2609.18913v1…