Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§3, pp.4–5 — the matrix (4) has a nonnegative factorization of size xc⁡(Q)\operatorname{xc}(Q)xc(Q) (corrected: n≥2n\ge2n≥2)

Proved
PSDPolyApprox.slack_submatrix_factorization

by iris · Oct 31, 2026 · Mathlib 0df444a (Lean v4.33.1)

extension-complexityhypercontractivityp2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-v1polyhedral-approximationpositive-semidefinite-cone

Let n≥2n\ge2n≥2, 0<ϵ<10<\epsilon<10<ϵ<1, and let QQQ be a polytope with

(1−ϵ)(D−1nIn)⊆Q⊆D−1nIn.(1-\epsilon)\Bigl(\mathcal D-\tfrac1nI_n\Bigr)\subseteq Q\subseteq\mathcal D-\tfrac1nI_n .(1−ϵ)(D−n1​In​)⊆Q⊆D−n1​In​.

Then the 2n×2n2^n\times2^n2n×2n matrix (4),

Mϵ(x,y)=(1−ϵ)1n(xTy)2+ϵ(x,y∈{−1,1}n),M_\epsilon(x,y)=(1-\epsilon)\frac1n(x^{\mathsf T}y)^2+\epsilon\qquad(x,y\in\{-1,1\}^n),Mϵ​(x,y)=(1−ϵ)n1​(xTy)2+ϵ(x,y∈{−1,1}n),

can be written as a sum of xc⁡(Q)\operatorname{xc}(Q)xc(Q) entrywise nonnegative rank-one matrices; that is, rank⁡+(Mϵ)≤xc⁡(Q)\operatorname{rank}_+(M_\epsilon)\le\operatorname{xc}(Q)rank+​(Mϵ​)≤xc(Q).

This is the step of the proof that turns a small polytope between (1−ϵ)C(1-\epsilon)C(1−ϵ)C and CCC, C=D−1nInC=\mathcal D-\frac1nI_nC=D−n1​In​, into a small nonnegative factorization: the rows of MϵM_\epsilonMϵ​ are the points (1−ϵ)(1nxxT−1nIn)(1-\epsilon)(\frac1nxx^{\mathsf T}-\frac1nI_n)(1−ϵ)(n1​xxT−n1​In​) of (1−ϵ)C(1-\epsilon)C(1−ϵ)C, the columns are the valid inequalities ⟨In−yyT,X⟩≤1\langle I_n-yy^{\mathsf T},X\rangle\le1⟨In​−yyT,X⟩≤1 of CCC, and the entries are the slacks.

Differences from the source:

  • correction: the hypercube submatrix (4) of the slack matrix of ((1 − ǫ)C, C) has nonnegative rank at most xc(Q), for every n → the same for n ≥ 2; reason: at n = 1, C = {0}, so Q = {0} has xc(Q) = 0, while (4) is the nonzero all-ones 2 × 2 matrix
  • reading: "we are thus led to study the nonnegative rank of" (3) and its submatrix (4), via Theorem 4 → an explicit statement that (4) has a nonnegative factorization of size xc(Q); reason: this is the inequality the text uses; it is stated separately because C is not full-dimensional in ℝ^{n×n}, so Theorem 4 does not apply verbatim
  • encoding: rows and columns indexed by {−1/√n, +1/√n}^n → rows and columns indexed by {−1, 1}^n with the entry (1 − ǫ)(1/n)(xᵀy)² + ǫ; reason: the paper's own rescaling in (4)
  • encoding: sets of n × n matrices → their images in ℝ^{n×n} under the flattening Matrix.vec; reason: vec is a linear isomorphism carrying the trace inner product to the dot product; extension complexity is invariant under it (equations are free)
  • encoding: extension complexity = smallest number of facets of a polytope whose linear image is P (Definition 1) → smallest number of inequalities of an extended formulation of P (ExtensionComplexity.TSP.extensionComplexity); reason: the two minima coincide for polytopes of dimension ≥ 1 (Fiorini et al., J. ACM 2015, Theorem 3, published as ExtensionComplexity.TSP.yannakakis_factorization), and every polytope in this statement has dimension ≥ 1
Preamble
import Mathlib
import Definitions.Def_ExtensionComplexity_TSP_Polytope
import Definitions.Def_ExtensionComplexity_TSP_extensionComplexity
import Definitions.Def_ExtensionComplexity_TSP_SlackMatrix
import Definitions.Def_PSDPolyApprox_shiftedDensity
import Definitions.Def_PSDPolyApprox_slackSubmatrix

open ExtensionComplexity.TSP
open scoped Pointwise
Formal statement
namespace PSDPolyApprox

/-- **The matrix (4) has a nonnegative factorization of size `xc(Q)`.**
Fawzi, arXiv:1811.09649v1, §3, pp.4–5: "By checking that
1 − ⟨(1 − ǫ)(xxT − 1/n In), In − nyyT⟩ = (1 − ǫ)n(xT y)2 + ǫ we are thus led to study the
nonnegative rank of the following infinite matrix … It will be enough for us to consider the
submatrix indexed by elements of the hypercube {−1/√n, +1/√n}n" — the matrix (4).

For `n ≥ 2`, `0 < ε < 1` and a polytope `Q` with `(1 − ε)(D − (1/n)Iₙ) ⊆ Q ⊆ D − (1/n)Iₙ`, the
`2ⁿ × 2ⁿ` matrix `(x, y) ↦ (1 − ε)(1/n)(xᵀy)² + ε` has a nonnegative factorization with
`xc(Q)` rank-one terms, i.e. `rank₊ ≤ xc(Q)`.

**Formalization Note.** This is the "rank₊ ≤ xc" half of Theorem 4 for the pair
`((1 − ε)C, C)`, `C = D − (1/n)Iₙ`, restricted to the hypercube rows and columns; it is a separate
statement because `C` is not full-dimensional in `ℝ^{n×n}`. `n ≥ 2` is needed: at `n = 1`,
`Q = {0}` has `xc = 0` while the matrix is the nonzero all-ones `2 × 2` matrix. -/
theorem slack_submatrix_factorization (n : ℕ) (hn : 2 ≤ n) (ε : ℝ) (hε0 : 0 < ε) (hε1 : ε < 1)
    (Q : Set (Fin n × Fin n → ℝ)) (hQ : IsPolytope Q)
    (hin : (1 - ε) • shiftedDensity n ((n : ℝ)⁻¹ • (1 : Matrix (Fin n) (Fin n) ℝ)) ⊆ Q)
    (hout : Q ⊆ shiftedDensity n ((n : ℝ)⁻¹ • (1 : Matrix (Fin n) (Fin n) ℝ))) :
    HasNonnegFactorization (slackSubmatrix ε n) (extensionComplexity Q) := by sorry

end PSDPolyApprox
Source
Fawzi, On polyhedral approximations of the positive semidefinite cone, arXiv:1811.09649v1, §3, pp.4–5, the slack-matrix computation and equation (4)
Human review
  • Endorsed by Shuze Chen · Oct 31, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Oct 31, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me