Theorem 3.3 — SOS of degree is decided by an SDP of size
ProvedSemialgebraicSDP.Psatz.theorem_3_3Let and let have total degree at most . Let be the vector of monomials of total degree at most . Then
and the matrix has size .
The right-hand side is a semidefinite feasibility problem: the set of matrices with is an affine subspace (coefficient matching), intersected with the positive semidefinite cone. This is how the existence of a sum of squares decomposition is decided by semidefinite programming, and it is the step that turns the sum-of-squares multipliers of the Positivstellensatz into SDP variables.
Formalization Note The meta-claim "can be decided by solving a semidefinite programming feasibility problem" is rendered as the equivalence above with the explicit finite PSD system, together with the dimension count. "Degree " is read as total degree at most , the setting of (3.5). The clause "if the polynomial is dense (no sparsity)" only explains why the full monomial vector is used and adds no hypothesis.
import Mathlib import Definitions.Def_SemialgebraicSDP_Psatz_Gram
namespace SemialgebraicSDP.Psatz
open MvPolynomial
theorem theorem_3_3 {n d : ℕ} (F : MvPolynomial (Fin n) ℝ)
(hdeg : F.totalDegree ≤ 2 * d) :
(IsSumSq F ↔ ∃ Q : Matrix (Mon n d) (Mon n d) ℝ, Q.PosSemidef ∧ F = gramPoly Q) ∧
Fintype.card (Mon n d) = (n + d).choose d := by sorry
end SemialgebraicSDP.Psatz
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.