Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Theorem 6.5 — T_l is the spectral norm and the maximum ℓ²-singular value of the tensor A_l

Proved
TensorNP.SpectralNorm.Tl_max_singular_value

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

p2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1singular-valuespectral-normtensor

Let GGG be a simple graph on v≥1v\ge1v≥1 vertices with edges enumerated in any order, let lll be a positive integer, and 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 (26). Regard Al\mathcal A_lAl​ as a real tensor. Then:

  1. ∥Al∥2,2,2=Tl\|\mathcal A_l\|_{2,2,2}=T_l∥Al​∥2,2,2​=Tl​;
  2. TlT_lTl​ is a unit ℓ2\ell^2ℓ2-singular value of Al\mathcal A_lAl​;
  3. every unit ℓ2\ell^2ℓ2-singular value σ\sigmaσ of Al\mathcal A_lAl​ satisfies ∣σ∣≤Tl|\sigma|\le T_l∣σ∣≤Tl​.

In the paper's words, "TlT_lTl​ is just the maximum ℓ2\ell^2ℓ2-singular value of Al\mathcal A_lAl​". This is what turns Lemma 6.11 into statements about the spectral norm and the singular values of an explicit rational tensor.

Formalization Note Singular values are taken with unit singular vectors (see the definition item): without a normalization, every nonzero real number would be a singular value of Al\mathcal A_lAl​. TlT_lTl​ is the sSup-based Tval, and Al\mathcal A_lAl​ is cliqueTensor cast entrywise to R\mathbb RR.

Preamble
import Mathlib
import Definitions.Def_TensorNP_SpectralNorm_Tensor
import Definitions.Def_TensorNP_SpectralNorm_CliqueTensor
Formal statement
namespace TensorNP.SpectralNorm

/-- **Proof of Theorem 6.5, `T_l` is the maximum ℓ²-singular value of `A_l`** (p. 0:24). For a
simple graph `G` on `v ≥ 1` vertices, an enumeration `ε` of its edges and a positive integer
`l`, the tensor `A_l` (read over ℝ) has spectral norm `T_l`, `T_l` is a unit ℓ²-singular value
of `A_l`, and every unit ℓ²-singular value `σ` of `A_l` satisfies `|σ| ≤ T_l`. -/
theorem Tl_max_singular_value {v e : ℕ} (hv : 0 < v) (G : SimpleGraph (Fin v))
    (ε : Fin e ≃ G.edgeSet) (l : ℕ) (hl : 1 ≤ l) :
    specNorm (fun i j k => (cliqueTensor G ε l i j k : ℝ)) = Tval G ε l ∧
      IsUnitSingularValue (fun i j k => (cliqueTensor G ε l i j k : ℝ)) (Tval G ε l) ∧
      ∀ σ : ℝ, IsUnitSingularValue (fun i j k => (cliqueTensor G ε l i j k : ℝ)) σ →
        |σ| ≤ Tval G ε l := 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:24, proof of Theorem 6.5 ("Then T_l is just the maximum ℓ²-singular value of A_l"); p. 0:22, discussion after Definition 6.6
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