Theorem 9.3 (core) — α(G) is the largest l ≤ v for which 2√(⅔(1 − 1/l)) is an ℓ²-eigenvalue of S_G
ProvedTensorNP.SymEigen.theorem_9_3_coreLet be a simple graph on vertices with stability number , let be its symmetric tensor from §9, and for let . Then is the greatest element of
Equivalently: (a) is an -eigenvalue of , and (b) for every with , is not.
This is the mathematical core of Hillar and Lim's proof that symmetric tensor eigenvalue over is NP-hard (Theorem 9.3): querying an oracle for Problem 9.1 with , the first "yes" occurs at , so at most queries compute the stability number, which is NP-hard (Karp 1972, via ).
Formalization Note Only the characterization is formalized. The oracle procedure, the polynomial size of , the input model with quadratic irrationalities (Remark 9.4), and the NP-completeness of the stability number are not. Eigenvalues are taken with a unit eigenvector; with the paper's bare condition , part (b) would be false by scaling.
import Mathlib import Definitions.Def_TensorNP_SymEigen_Defs import Definitions.Def_TensorNP_SymEigen_StabTensor
namespace TensorNP.SymEigen
theorem theorem_9_3_core {v : ℕ} (hv : 0 < v) (G : SimpleGraph (Fin v)) :
IsGreatest {l : ℕ | 1 ≤ l ∧ l ≤ v ∧ IsUnitL2Eigenvalue (stabTensor G) (lambdaL l)}
G.indepNum := by sorry
end TensorNP.SymEigen
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.