Path-strengthened semidefinite value
DefinitionGraphTensorCP_Supplement_uSDPDeltagraph-tensorsmax-cutp2o-gran-per-chapterp2o-plan-paperp2o-v1semidefinite-programmingtensor-rank
For a symmetric nonnegative zero-diagonal weight matrix , define the path-strengthened semidefinite value by
where the last inequalities range over all distinct triples . It is the semidefinite analogue of : positive-semidefinite feasibility replaces copositivity while retaining every path inequality.
Formalization Note Entrywise nonnegativity of is not added because the correlation-matrix constraint implies it. The maximum is represented by a real supremum; the paper proves that the feasible set is nonempty and compact.
Definition code
import Mathlib
namespace GraphTensorCP
namespace Supplement
/-- Feasibility for the **path-strengthened semidefinite program** (Zhou,
*Asymptotic Rank of Weighted Graph Tensors via Completely Positive Covers*,
arXiv:2610.34273 (version of 2026-11-03), Definition 5.11, p.52): `P` is symmetric and
zero-diagonal, `J - 2P` is positive semidefinite, and all path inequalities
`P_ij ≤ P_ik + P_kj` hold for distinct `i,j,k`.
**Formalization Note.** `J` is the all-one matrix including its diagonal. The paper observes that
entrywise nonnegativity of `P` follows from the correlation-matrix constraint, so it is not added
as a separate condition. -/
def IsPathSDPFeasible {n : ℕ} (P : Matrix (Fin n) (Fin n) ℝ) : Prop :=
P.IsSymm ∧ (∀ i, P i i = 0) ∧
(Matrix.of (fun _ _ => (1 : ℝ)) - (2 : ℝ) • P).PosSemidef ∧
∀ i j k, i ≠ j → j ≠ k → i ≠ k → P i j ≤ P i k + P k j
/-- The **path-strengthened semidefinite value** `U^Δ_SDP(W)` (Zhou,
arXiv:2610.34273 (version of 2026-11-03), Definition 5.11, p.52): the maximum of
`Σ_{i<j} W_ij P_ij` over `IsPathSDPFeasible P`.
**Formalization Note.** The maximum is represented by `sSup`; the paper proves the feasible set
is nonempty and compact, so it is attained. This differs from the published `uCPDelta` only by
positive-semidefinite rather than copositive feasibility. -/
noncomputable def uSDPDelta {n : ℕ} (W : Matrix (Fin n) (Fin n) ℝ) : ℝ :=
sSup {v : ℝ | ∃ P : Matrix (Fin n) (Fin n) ℝ, IsPathSDPFeasible P ∧
v = ∑ i, ∑ j, if i < j then W i j * P i j else 0}
end Supplement
end GraphTensorCP
Source
Zhou, Asymptotic Rank of Weighted Graph Tensors via Completely Positive Covers, arXiv:2610.34273 (version of 2026-11-03), Definition 5.11, p.52