Theorems 6.5 and 1.10 (core) — ω(G) is the unique l with ‖A_l‖₂,₂,₂ = 1, and the largest l for which 1 is a singular value of A_l
ProvedTensorNP.SpectralNorm.theorem_6_5_coreLet be a simple graph on vertices with clique number , and enumerate its edges in any order. For each positive integer let be the tensor whose entry is the coefficient of in the multilinear form
with for the -th edge . Regarding as a real tensor:
- for every , if and only if ;
- is a unit -singular value of ;
- for every , is not a unit -singular value of ;
- hence is the largest for which is a unit -singular value of .
This is the mathematical core of the paper's polynomial-time Turing reductions from the clique number to the tensor singular value problem (Theorem 6.5, ) and to the spectral norm problem (Theorem 1.10, ): querying an oracle for determines . A general fixed is handled by scaling by .
Formalization Note This is not an NP-hardness statement. The polynomial size of , the -query procedure and the NP-completeness of deciding (Karp 1972, cited by the paper) are not formalized, and neither is the scaling to general . Singular values are taken with unit singular vectors (Definition 6.1 has no normalization; unnormalized, every nonzero number would be a singular value of and clause 3 would be false). The paper does not claim, and this statement does not assert, that fails to be a singular value of for . The tensor is defined for any enumeration ε : Fin e ≃ G.edgeSet of the edges and the statement holds for each one; the third block of uses the index of the proof of Lemma 6.11 (its statement prints ).
import Mathlib import Definitions.Def_TensorNP_SpectralNorm_Tensor import Definitions.Def_TensorNP_SpectralNorm_CliqueTensor
namespace TensorNP.SpectralNorm
/-- **Theorems 6.5 and 1.10, encoding-free core.** Let `G` be a simple graph on `v ≥ 1` vertices
with clique number `ω = ω(G)`, and `ε` any enumeration of its `e` edges. For the rational tensors
`A_l` (read over ℝ):
(a) for every `l ≥ 1`, `‖A_l‖_{2,2,2} = 1` iff `l = ω`;
(b) `1` is a unit ℓ²-singular value of `A_ω`;
(c) for every `l > ω`, `1` is not a unit ℓ²-singular value of `A_l`;
(d) hence `ω` is the largest `l ∈ {1, …, v}` for which `1` is a unit ℓ²-singular value of
`A_l`. -/
theorem theorem_6_5_core {v e : ℕ} (hv : 0 < v) (G : SimpleGraph (Fin v))
(ε : Fin e ≃ G.edgeSet) :
(∀ l : ℕ, 1 ≤ l →
(specNorm (fun i j k => (cliqueTensor G ε l i j k : ℝ)) = 1 ↔ l = G.cliqueNum)) ∧
IsUnitSingularValue (fun i j k => (cliqueTensor G ε G.cliqueNum i j k : ℝ)) 1 ∧
(∀ l : ℕ, G.cliqueNum < l →
¬ IsUnitSingularValue (fun i j k => (cliqueTensor G ε l i j k : ℝ)) 1) ∧
IsGreatest {l : ℕ | 1 ≤ l ∧ l ≤ v ∧
IsUnitSingularValue (fun i j k => (cliqueTensor G ε l i j k : ℝ)) 1}
G.cliqueNum := by sorry
end TensorNP.SpectralNorm
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.