AFTD Auto-Formalizing Theoretical Domains

graph_wasserstein_dist_comm

theoremverified

The Wasserstein distance is symmetric: W(μ, ν) = W(ν, μ).

Statement

theorem graph_wasserstein_dist_comm {V : Type*} [Fintype V] (G : SimpleGraph V)
    (μ ν : V → ℝ) : graph_wasserstein_dist G μ ν = graph_wasserstein_dist G ν μ
Source
Helper for the refutation of OP-165 (arXiv:2610.10559, after Theorem 1.4).
Verified
10 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • graph_wasserstein_distThe Wasserstein distance W(μ, ν) between two measures on the vertices of a finite graph: the infimum, over all transport plans π ≥ 0 with…
Used by 2

The proof, explained

The Wasserstein distance W(μ, ν) is the infimum of transport costs ∑ a, ∑ b, d(a, b) π(a, b) over all couplings π with marginals μ and ν. The proof shows symmetry by proving that the sets of achievable transport costs for (μ, ν) and (ν, μ) are identical. For any coupling π, its transpose π'(a, b) = π(b, a) is a valid coupling for the swapped marginals with the exact same cost, since the graph distance is symmetric and the order of finite summation can be exchanged.

  1. The equality of Wasserstein distances reduces to showing that a transport cost c is achievable between μ and ν if and only if it is achievable between ν and μ.

    Unfolding the definition of the Wasserstein distance expresses each side as the infimum of the set of costs achievable by valid couplings. Congruence reduces equality of infima to equality of the underlying sets, which by set extensionality reduces to proving a bi-implication for any given cost c.

    lines 3–6

      unfold graph_wasserstein_dist
      congr 1
      ext c
      constructor
  2. Any transport cost achievable between μ and ν is also achievable between ν and μ.

    Given a coupling π from μ to ν with cost c, consider the transposed coupling π'(a, b) = π(b, a). Transposing π swaps the row and column marginals, making π' a valid coupling from ν to μ. Exchanging the order of summation via Finset.sum_comm and using the symmetry of the graph metric via SimpleGraph.dist_comm shows that the transport cost of π' is identically c.

    lines 7–10

    uses Finset.sum_comm, SimpleGraph.dist_comm

      · rintro ⟨π, h0, h1, h2, rfl⟩
        refine ⟨fun a b => π b a, fun a b => h0 b a, h2, h1, ?_⟩
        rw [Finset.sum_comm]
        simp_rw [SimpleGraph.dist_comm]
  3. Conversely, any transport cost achievable between ν and μ is also achievable between μ and ν.

    By symmetry, given a coupling π from ν to μ, its transpose π'(a, b) = π(b, a) is a valid coupling from μ to ν achieving the same cost, again verified using Finset.sum_comm and SimpleGraph.dist_comm.

    lines 11–14

    uses Finset.sum_comm, SimpleGraph.dist_comm

      · rintro ⟨π, h0, h1, h2, rfl⟩
        refine ⟨fun a b => π b a, fun a b => h0 b a, h2, h1, ?_⟩
        rw [Finset.sum_comm]
        simp_rw [SimpleGraph.dist_comm]
Finset.sum_comm
In a finite double sum, the order of summation can be exchanged: ∑ x ∈ s, ∑ y ∈ t, f(x, y) = ∑ y ∈ t, ∑ x ∈ s, f(x, y).
SimpleGraph.dist_comm
The shortest-path distance between vertices in a simple graph is symmetric: d(u, v) = d(v, u).

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

theorem graph_wasserstein_dist_comm {V : Type*} [Fintype V] (G : SimpleGraph V)    (μ ν : V → ℝ) : graph_wasserstein_dist G μ ν = graph_wasserstein_dist G ν μ := by  unfold graph_wasserstein_dist  congr 1  ext c  constructor  · rintro ⟨π, h0, h1, h2, rfl⟩    refine ⟨fun a b => π b a, fun a b => h0 b a, h2, h1, ?_⟩    rw [Finset.sum_comm]    simp_rw [SimpleGraph.dist_comm]  · rintro ⟨π, h0, h1, h2, rfl⟩    refine ⟨fun a b => π b a, fun a b => h0 b a, h2, h1, ?_⟩    rw [Finset.sum_comm]    simp_rw [SimpleGraph.dist_comm]
See it in the graphDiscuss this resultChallenge it