Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Corollary 3.5, duality step — no PSD A satisfies all J_{i,j} iff a PSD Q and a nonnegative combination of the J_{i,j} give a contradiction

Proved
GeometryOfGraphs.EuclidDist.duality_alternative

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

dualityp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1semidefinite-programmingtheorem-of-alternatives

Let (X,d)(X,d)(X,d) be a finite semi-metric space and c≥1c \ge 1c≥1. For i,j∈Xi,j \in Xi,j∈X consider the pair of inequalities in the unknown matrix A=(ai,j)A=(a_{i,j})A=(ai,j​)

Ji,j:c2di,j2  ≥  ai,i+aj,j−2ai,j  ≥  di,j2.J_{i,j}:\qquad c^2 d_{i,j}^2 \;\ge\; a_{i,i}+a_{j,j}-2a_{i,j} \;\ge\; d_{i,j}^2 .Ji,j​:c2di,j2​≥ai,i​+aj,j​−2ai,j​≥di,j2​.

Then no real positive semidefinite matrix AAA satisfies every Ji,jJ_{i,j}Ji,j​ if and only if there exist a real positive semidefinite matrix Q=(qi,j)Q=(q_{i,j})Q=(qi,j​) and nonnegative multipliers λi,j,μi,j≥0\lambda_{i,j}, \mu_{i,j} \ge 0λi,j​,μi,j​≥0 such that, for every matrix AAA,

∑i,jqi,j ai,j  +  ∑i,j(λi,j(c2di,j2−(ai,i+aj,j−2ai,j))+μi,j((ai,i+aj,j−2ai,j)−di,j2))  =  ∑i,j(λi,jc2di,j2−μi,jdi,j2),\sum_{i,j} q_{i,j}\,a_{i,j} \;+\; \sum_{i,j}\Big(\lambda_{i,j}\big(c^2d_{i,j}^2-(a_{i,i}+a_{j,j}-2a_{i,j})\big) + \mu_{i,j}\big((a_{i,i}+a_{j,j}-2a_{i,j})-d_{i,j}^2\big)\Big) \;=\; \sum_{i,j}\big(\lambda_{i,j}c^2d_{i,j}^2-\mu_{i,j}d_{i,j}^2\big),i,j∑​qi,j​ai,j​+i,j∑​(λi,j​(c2di,j2​−(ai,i​+aj,j​−2ai,j​))+μi,j​((ai,i​+aj,j​−2ai,j​)−di,j2​))=i,j∑​(λi,j​c2di,j2​−μi,j​di,j2​),

and the constant on the right is negative:

∑i,j(λi,jc2di,j2−μi,jdi,j2)  <  0.\sum_{i,j}\big(\lambda_{i,j}c^2d_{i,j}^2-\mu_{i,j}d_{i,j}^2\big) \;<\; 0 .i,j∑​(λi,j​c2di,j2​−μi,j​di,j2​)<0.

This is the theorem of alternatives invoked on pp. 224–225 in the proof of Corollary 3.5: "the conclusion of the Corollary is incorrect, i.e., no such matrix AAA exists, iff there is a matrix Q∈PSDQ\in PSDQ∈PSD such that the inequality ∑i,jai,jqi,j≥0\sum_{i,j} a_{i,j}q_{i,j}\ge 0∑i,j​ai,j​qi,j​≥0 contradicts some nonnegative combination of the inequalities Ji,jJ_{i,j}Ji,j​." The identity says that adding ∑i,jqi,jai,j≥0\sum_{i,j}q_{i,j}a_{i,j} \ge 0∑i,j​qi,j​ai,j​≥0 to λi,j\lambda_{i,j}λi,j​ times the left part and μi,j\mu_{i,j}μi,j​ times the right part of each Ji,jJ_{i,j}Ji,j​ eliminates every aaa-term, and the negative constant is the contradiction 0≤(negative number)0 \le (\text{negative number})0≤(negative number).

Formalization Note "Contradicts some nonnegative combination" is made precise as the exact cancellation identity above (holding for all matrices AAA, an identity of linear forms) together with a negative constant term; λ\lambdaλ and μ\muμ are written lam and mu. Pairs (i,j)(i,j)(i,j) are ordered and include i=ji=ji=j. The number 111 multiplying ∑qi,jai,j\sum q_{i,j}a_{i,j}∑qi,j​ai,j​ loses no generality, since QQQ can be rescaled.

Preamble
import Mathlib
import Definitions.Def_GeometryOfGraphs_EuclidDist_EuclideanDistortion
Formal statement
namespace GeometryOfGraphs.EuclidDist

/-- Proof of Corollary 3.5, duality step (pp. 224–225): no positive semidefinite `A` satisfies the
inequalities `J_ij : c^2 d_ij^2 ≥ a_ii + a_jj - 2 a_ij ≥ d_ij^2` iff there are a positive
semidefinite `Q` and nonnegative multipliers `lam, mu` such that adding
`∑ a_ij q_ij ≥ 0` to the combination `∑ lam_ij (upper J_ij) + mu_ij (lower J_ij)` cancels every
`a`-term and leaves a negative constant on the right, i.e. a contradiction. -/
theorem duality_alternative {X : Type*} [Fintype X] [DecidableEq X]
    (d : X → X → ℝ) (hd : GeometryOfGraphs.FlowCut.IsPseudometric d) (c : ℝ) (hc : 1 ≤ c) :
    (¬ ∃ A : Matrix X X ℝ, A.PosSemidef ∧
        ∀ i j, d i j ^ 2 ≤ A i i + A j j - 2 * A i j ∧
          A i i + A j j - 2 * A i j ≤ c ^ 2 * d i j ^ 2) ↔
      ∃ Q : Matrix X X ℝ, Q.PosSemidef ∧
        ∃ lam mu : X → X → ℝ, (∀ i j, 0 ≤ lam i j) ∧ (∀ i j, 0 ≤ mu i j) ∧
          (∀ A : Matrix X X ℝ,
            (∑ i, ∑ j, Q i j * A i j) +
              ∑ i, ∑ j, (lam i j * (c ^ 2 * d i j ^ 2 - (A i i + A j j - 2 * A i j)) +
                mu i j * ((A i i + A j j - 2 * A i j) - d i j ^ 2)) =
            ∑ i, ∑ j, (lam i j * (c ^ 2 * d i j ^ 2) - mu i j * d i j ^ 2)) ∧
          ∑ i, ∑ j, (lam i j * (c ^ 2 * d i j ^ 2) - mu i j * d i j ^ 2) < 0 := by sorry

end GeometryOfGraphs.EuclidDist
Source
N. Linial, E. London, Y. Rabinovich, The geometry of graphs and some of its algorithmic applications, Combinatorica 15 (1995), pp. 224–225, proof of Corollary 3.5 (paragraph after Proposition 3.6, inequalities J_{i,j})
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

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