Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Proved
TensorNP.SpectralNorm.theorem_6_5_core

by mikedeng1 · Oct 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

clique-numbercomputational-complexityp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1singular-valuespectral-normtensor

Let GGG be a simple graph on v≥1v\ge1v≥1 vertices with clique number ω=ω(G)\omega=\omega(G)ω=ω(G), and enumerate its eee edges in any order. For each positive integer lll let Al∈Qv×v×(l+2e)\mathcal A_l\in\mathbb Q^{v\times v\times(l+2e)}Al​∈Qv×v×(l+2e) be the tensor whose entry aijka_{ijk}aijk​ is the coefficient of uivjwku_iv_jw_kui​vj​wk​ in the multilinear form

∑i=1l(u⊤1lIv)wi+∑k=1e(u⊤Ekv)wl+k+∑k=1e(u⊤Ekv)we+l+k,\sum_{i=1}^l\Big(\mathbf u^\top\tfrac1lI\mathbf v\Big)w_i+\sum_{k=1}^e(\mathbf u^\top E_k\mathbf v)w_{l+k}+\sum_{k=1}^e(\mathbf u^\top E_k\mathbf v)w_{e+l+k},i=1∑l​(u⊤l1​Iv)wi​+k=1∑e​(u⊤Ek​v)wl+k​+k=1∑e​(u⊤Ek​v)we+l+k​,

with Ek=12Eikjk+12EjkikE_k=\frac12E_{i_kj_k}+\frac12E_{j_ki_k}Ek​=21​Eik​jk​​+21​Ejk​ik​​ for the kkk-th edge {ik,jk}\{i_k,j_k\}{ik​,jk​}. Regarding Al\mathcal A_lAl​ as a real tensor:

  1. for every l≥1l\ge1l≥1, ∥Al∥2,2,2=1\|\mathcal A_l\|_{2,2,2}=1∥Al​∥2,2,2​=1 if and only if l=ωl=\omegal=ω;
  2. 111 is a unit ℓ2\ell^2ℓ2-singular value of Aω\mathcal A_\omegaAω​;
  3. for every l>ωl>\omegal>ω, 111 is not a unit ℓ2\ell^2ℓ2-singular value of Al\mathcal A_lAl​;
  4. hence ω\omegaω is the largest l∈{1,…,v}l\in\{1,\dots,v\}l∈{1,…,v} for which 111 is a unit ℓ2\ell^2ℓ2-singular value of Al\mathcal A_lAl​.

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, σ=1\sigma=1σ=1) and to the spectral norm problem (Theorem 1.10, σ=1\sigma=1σ=1): querying an oracle for l=1,…,vl=1,\dots,vl=1,…,v determines ω(G)\omega(G)ω(G). A general fixed 0≠σ∈Q0\neq\sigma\in\mathbb Q0=σ∈Q is handled by scaling Al\mathcal A_lAl​ by σ\sigmaσ.

Formalization Note This is not an NP-hardness statement. The polynomial size of Al\mathcal A_lAl​, the vvv-query procedure and the NP-completeness of deciding ω(G)≥l\omega(G)\ge lω(G)≥l (Karp 1972, cited by the paper) are not formalized, and neither is the scaling to general σ\sigmaσ. Singular values are taken with unit singular vectors (Definition 6.1 has no normalization; unnormalized, every nonzero number would be a singular value of Al\mathcal A_lAl​ and clause 3 would be false). The paper does not claim, and this statement does not assert, that 111 fails to be a singular value of Al\mathcal A_lAl​ for l<ωl<\omegal<ω. 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 w\mathbf ww uses the index we+l+kw_{e+l+k}we+l+k​ of the proof of Lemma 6.11 (its statement prints wm+l+kw_{m+l+k}wm+l+k​).

Preamble
import Mathlib
import Definitions.Def_TensorNP_SpectralNorm_Tensor
import Definitions.Def_TensorNP_SpectralNorm_CliqueTensor
Formal statement
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
Source
Hillar & Lim, Most Tensor Problems Are NP-Hard, J. ACM 60(6) (2013), Art. 45 (final version, arXiv:0911.1393v5), p. 0:22, Theorem 6.5; p. 0:9, Theorem 1.10; p. 0:24, proofs of Theorems 6.5 and 1.10
Human review
  • Endorsed by Shuze Chen · Oct 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 8, 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