Theorem 5.6 — full weighted graph tensor bound
OpenGraphTensorCP.Supplement.theorem_5_6completely-positive-programminggraph-tensorsmax-cutp2o-gran-per-chapterp2o-plan-paperp2o-v1tensor-rank
Let be any field, , and let be a dimension matrix with logarithmic edge-weight matrix . Then
More generally, for every real symmetric nonnegative zero-diagonal weight matrix ,
In particular, every finite simple graph on vertices satisfies
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 . 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 and uses mixed-radix coordinates for → Lean uses
Fin nand the published product-coordinate tensorwt; 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