Theorem 2, p. 3 — if on , is -sos on for all
ProvedSphereSOS.Rate.theorem_2For every there are constants and , depending only on , with the following property. Let and let be a matrix polynomial, homogeneous of degree , with , such that is symmetric for every and
If , then
This is the main theorem: the sum-of-squares hierarchy on the sphere converges at the rate once , uniformly in the size of the matrices. The scalar case () gives Theorem 1.
Formalization Note The constants are chosen before , , and , so they are independent of the dimension and of the matrix size. is the positive semidefinite order, imposed on the sphere only. No assumption is added: for the statement is elementary and true. If , is admitted and Lean reads as ; the conclusion then claims is -sos, which fails in general, so this gives a prover nothing.
import Mathlib import Definitions.Def_SphereSOS_Rate_Setting
namespace SphereSOS.Rate
theorem theorem_2 :
∀ n : ℕ, ∃ C C' : ℝ, ∀ (d k ℓ : ℕ)
(F : Matrix (Fin k) (Fin k) (MvPolynomial (Fin d) ℝ)),
n ≤ d →
(∀ a b, (F a b).IsHomogeneous (2 * n)) →
(∀ x, (evalM x F).IsSymm) →
(∀ x ∈ sphere d,
(evalM x F).PosSemidef ∧ (1 - evalM x F).PosSemidef) →
C * (d : ℝ) ≤ (ℓ : ℝ) →
IsSosOnSphere ℓ
(F + (C' * ((d : ℝ) / (ℓ : ℝ)) ^ 2) •
(1 : Matrix (Fin k) (Fin k) (MvPolynomial (Fin d) ℝ))) := by sorry
end SphereSOS.Rate
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.