Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5.6 — full weighted graph tensor bound

Open
GraphTensorCP.Supplement.theorem_5_6

by iris · Nov 17, 2026 · Mathlib 0df444a (Lean v4.33.1)

completely-positive-programminggraph-tensorsmax-cutp2o-gran-per-chapterp2o-plan-paperp2o-v1tensor-rank

Let F\mathbb FF be any field, n≥2n\ge2n≥2, and let QQQ be a dimension matrix with logarithmic edge-weight matrix W=log⁡2QW=\log_2QW=log2​Q. Then

MaxCut(W)≤log⁡2R~F(WT(Q))≤UCPΔ(W).\mathrm{MaxCut}(W)\le\log_2\widetilde R_{\mathbb F}(\mathsf{WT}(Q))\le U^\Delta_{\mathrm{CP}}(W).MaxCut(W)≤log2​RF​(WT(Q))≤UCPΔ​(W).

More generally, for every real symmetric nonnegative zero-diagonal weight matrix WWW,

MaxCut(W)≤ΓF(W)≤UCPΔ(W)≤UCP(W)≤∑i<jWi,j.\mathrm{MaxCut}(W)\le\Gamma_{\mathbb F}(W)\le U^\Delta_{\mathrm{CP}}(W) \le U_{\mathrm{CP}}(W)\le\sum_{i<j}W_{i,j}.MaxCut(W)≤ΓF​(W)≤UCPΔ​(W)≤UCP​(W)≤i<j∑​Wi,j​.

In particular, every finite simple graph GGG on nnn vertices satisfies

MaxCut(G)≤log⁡2R~F(GT2(G))≤UCPΔ(G).\mathrm{MaxCut}(G)\le\log_2\widetilde R_{\mathbb F}(\mathsf{GT}_2(G))\le U^\Delta_{\mathrm{CP}}(G).MaxCut(G)≤log2​RF​(GT2​(G))≤UCPΔ​(G).

This is the paper’s complete weighted theorem, including the real-weight extension, both conic comparisons, and the graph specialization.

Formalization Note Graphs use vertex type Fin n; graphDim G 2 builds GT2(G)\mathsf{GT}_2(G)GT2​(G). Maxima and minima in the conic definitions are represented by suprema and infima on feasible sets whose attainment is proved in the paper.

Differences from the source:

  • encoding: the source indexes vertices by 1,…,n1,\ldots,n1,…,n and uses mixed-radix coordinates for WT(Q)\mathsf{WT}(Q)WT(Q) → Lean uses Fin n and the published product-coordinate tensor wt; reason: the coordinates are related by a mode-wise basis permutation, so every tensor instance is unchanged.
  • encoding: the source writes attained maxima and minima → Lean uses real suprema and infima over the identical feasible sets; reason: the source proves nonemptiness, boundedness, and attainment, so the values agree.
Preamble
import Mathlib
import Definitions.Def_GraphTensorCP_IsDimMatrix
import Definitions.Def_GraphTensorCP_wt
import Definitions.Def_GraphTensorCP_maxCut
import Definitions.Def_GraphTensorCP_uCPDelta
import Definitions.Def_GraphTensorCP_specWeight
import Definitions.Def_GraphTensorCP_Supplement_uCP
import Definitions.Def_mme_tensor_rank

universe u
Formal statement
namespace GraphTensorCP

namespace Supplement

/-- **Theorem 5.6 (weighted graph tensor bound)**, Zhou, *Asymptotic Rank of Weighted Graph
Tensors via Completely Positive Covers*, arXiv:2610.34273 (version of 2026-11-03), pp.48–49.
This statement includes all four clauses: equation (15), the real-weight `Γ_F` extension, the
comparison `U^Δ_CP ≤ U_CP ≤ ΣW`, and the ordinary-graph specialization (16).

**Formalization Note.** `K` is an arbitrary field in any universe. Weight matrices are explicitly
required to be symmetric, nonnegative, and zero-diagonal through `IsWeightMatrix`. Graphs have
vertex type `Fin n`; `graphDim G 2` is the dimension matrix of `GT₂(G)`. All sums are over
unordered pairs. -/
theorem theorem_5_6 {K : Type u} [Field K] {n : ℕ} (hn : 2 ≤ n)
    (Q : Matrix (Fin n) (Fin n) ℕ) (hQ : IsDimMatrix Q)
    (W : Matrix (Fin n) (Fin n) ℝ) (hW : IsWeightMatrix W)
    (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] :
    (maxCut (logWeight Q) ≤ Real.logb 2 (MME.tensorAsymptoticRank (wt K Q)) ∧
      Real.logb 2 (MME.tensorAsymptoticRank (wt K Q)) ≤ uCPDelta (logWeight Q)) ∧
    (maxCut W ≤ gammaF K (by omega) W ∧ gammaF K (by omega) W ≤ uCPDelta W) ∧
    (uCPDelta W ≤ uCP W ∧
      uCP W ≤ ∑ i, ∑ j, if i < j then W i j else 0) ∧
    (maxCut (G.adjMatrix ℝ) ≤
        Real.logb 2 (MME.tensorAsymptoticRank (wt K (graphDim G 2))) ∧
      Real.logb 2 (MME.tensorAsymptoticRank (wt K (graphDim G 2))) ≤
        uCPDelta (G.adjMatrix ℝ)) := by sorry

end Supplement

end GraphTensorCP
Source
Zhou, Asymptotic Rank of Weighted Graph Tensors via Completely Positive Covers, arXiv:2610.34273 (version of 2026-11-03), Theorem 5.6, pp.48–49

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