AFTD Auto-Formalizing Theoretical Domains

flow_rate_mul_two_le_sum_cap_mul_dist

theoremverified

If a fractional multicommodity flow on net supports the common rate r, and d is a symmetric, nonnegative, triangle-satisfying function on V with d(u,u) = 0, then 2*r*(sum over sessions of d(src,tgt)) is at most the sum over all ordered pairs of vertices of cap({u,v})*d(u,v).

Statement

theorem flow_rate_mul_two_le_sum_cap_mul_dist
    {V : Type} [Fintype V] [DecidableEq V] {K : Type} [Fintype K] [DecidableEq K]
    (net : CapacitatedNetwork V) (sess : UnicastSessions V K) {r : ℝ}
    (h : FlowSupportsRate net sess r) (d : V → V → ℝ)
    (h_nonneg : ∀ u v, 0 ≤ d u v) (h_symm : ∀ u v, d u v = d v u)
    (h_diag : ∀ u, d u u = 0) (h_tri : ∀ u v w, d u v ≤ d u w + d w v) :
    2 * r * (∑ k, d (sess.src k) (sess.tgt k)) ≤ ∑ u, ∑ v, net.cap s(u, v) * d u v
Source
step towards undirected_binary_linear_unicast_advantage
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • CapacitatedNetworkAn undirected capacitated network on a finite vertex set V given by a simple graph G where each edge in G has strictly positive capacity…
  • UnicastSessionsA collection of unicast communication sessions indexed by a type K on an arbitrary vertex type V, consisting of a source map src : K → V,…
  • FlowSupportsRateA common rate r is supported by fractional multicommodity flow on a capacitated network net with unicast sessions sess if there exists a…
  • IsMulticommodityFlowGiven a capacitated network on a finite vertex type V with decidable equality, and unicast sessions indexed by a finite type K with…
Used by 1

The proof, explained

The theorem establishes the metric upper bound (metric potential method) on the common rate $r$ supported by a multicommodity flow: for any pseudometric $d$, $2r \sum_k d(s_k, t_k) \le \sum_{u, v} \text{cap}(\{u, v\}) d(u, v)$. For each individual commodity $k$, weighting the flow conservation equations by the distance from the source $s_k$ and reindexing shows that $-r \cdot d(s_k, t_k) = \sum_{v, w} f_k(v, w)(d(s_k, v) - d(s_k, w))$, which is at least $-\sum_{v, w} f_k(v, w) d(v, w)$ by the triangle inequality, proving $r \cdot d(s_k, t_k) \le \sum_{v, w} f_k(v, w) d(v, w)$. Summing over all sessions, symmetrizing the flow across pairs $\{v, w\}$ using the symmetry of $d$, and applying the edge capacity constraints yields the result.

  1. Let $f$ be a multicommodity flow supporting rate $r$ in the network.

    Unpack the hypothesis `FlowSupportsRate net sess r` to obtain the flow function $f$, which satisfies nonnegativity, the capacity constraints on each undirected edge, and the flow conservation equations with rate $r$ for each session.

    lines 9–10

      open Finset in
      obtain ⟨f, hf⟩ := h
  2. For each session $k$, the divergence weighted by distance to the source satisfies $\sum_v (\sum_w f_k(v, w) - \sum_u f_k(u, v)) d(s_k, v) = -r \cdot d(s_k, t_k)$.

    Fix a session $k$ with source $s = \text{sess.src}(k)$ and target $t = \text{sess.tgt}(k)$, where $s \ne t$. By flow conservation, the net divergence at vertex $v$ is $r$ if $v = s$, $-r$ if $v = t$, and $0$ otherwise. Weighting by $d(s, v)$ and summing over all vertices $v$, the term at $v = s$ vanishes because $d(s, s) = 0$, leaving only the term at $v = t$, which is $-r \cdot d(s, t)$.

    lines 11–26

    uses sum_add_distrib

      have h_single : ∀ k : K, r * d (sess.src k) (sess.tgt k) ≤ ∑ v, ∑ w, f k v w * d v w := by
        intro k
        have hdiv := hf.2.2 k
        have hnn := hf.1 k
        set s := sess.src k
        set t := sess.tgt k
        have hst : s ≠ t := sess.src_ne_tgt k
        have h_lhs : (∑ v, (∑ w, f k v w - ∑ u, f k u v) * d s v) = -r * d s t := by
          have h_split : ∀ v, (∑ w, f k v w - ∑ u, f k u v) * d s v =
              (if v = s then r * d s s else 0) + (if v = t then -r * d s t else 0) := by
            intro v
            rw [hdiv v]
            split_ifs <;> (try subst_vars) <;> (try contradiction) <;> ring
          simp_rw [h_split, sum_add_distrib]
          have hd_ss : d s s = 0 := h_diag s
          simp [hd_ss]
  3. The potential sum can be rewritten by summation by parts as $\sum_{v, w} f_k(v, w) (d(s_k, v) - d(s_k, w))$.

    Splitting the net divergence into outgoing flow $\sum_w f_k(v, w)$ and incoming flow $\sum_u f_k(u, v)$, the weighted sum becomes the difference of $\sum_{v, w} f_k(v, w) d(s, v)$ and $\sum_{v, u} f_k(u, v) d(s, v)$. Swapping the dummy summation indices in the incoming term yields $\sum_{v, w} f_k(v, w) d(s, w)$. Recombining gives $\sum_{v, w} f_k(v, w) (d(s, v) - d(s, w))$.

    lines 27–37

    uses sub_mul, sum_sub_distrib, sum_mul, sum_comm, mul_sub

        have h_geom : (∑ v, (∑ w, f k v w - ∑ u, f k u v) * d s v) = ∑ v, ∑ w, f k v w * (d s v - d s w) := by
          have h1 : (∑ v, (∑ w, f k v w - ∑ u, f k u v) * d s v) =
              (∑ v, (∑ w, f k v w) * d s v) - (∑ v, (∑ u, f k u v) * d s v) := by
            simp_rw [sub_mul, sum_sub_distrib]
          have h2 : (∑ v, (∑ u, f k u v) * d s v) = ∑ v, ∑ w, f k v w * d s w := by
            simp_rw [sum_mul]
            rw [sum_comm]
          have h3 : (∑ v, (∑ w, f k v w) * d s v) = ∑ v, ∑ w, f k v w * d s v := by
            simp_rw [sum_mul]
          rw [h1, h2, h3]
          simp_rw [← sum_sub_distrib, ← mul_sub]
  4. For each session $k$, the demand times distance is bounded by the flow cost: $r \cdot d(s_k, t_k) \le \sum_{v, w} f_k(v, w) d(v, w)$.

    By the triangle inequality $d(s, w) \le d(s, v) + d(v, w)$, the potential difference along any directed edge $(v, w)$ satisfies $d(s, v) - d(s, w) \ge -d(v, w)$. Since flow is nonnegative ($f_k(v, w) \ge 0$), multiplying by $f_k(v, w)$ and summing over all pairs $(v, w)$ preserves the inequality. Substituting the expressions from the preceding two steps gives $-r \cdot d(s, t) \ge -\sum_{v, w} f_k(v, w) d(v, w)$, which simplifies to $r \cdot d(s, t) \le \sum_{v, w} f_k(v, w) d(v, w)$.

    lines 38–52

    uses sum_neg_distrib, sum_le_sum

        have h_le : - ∑ v, ∑ w, f k v w * d v w ≤ ∑ v, ∑ w, f k v w * (d s v - d s w) := by
          rw [← sum_neg_distrib]
          apply sum_le_sum
          intro v _
          rw [← sum_neg_distrib]
          apply sum_le_sum
          intro w _
          have htri : - d v w ≤ d s v - d s w := by
            have := h_tri s w v
            linarith
          have h_nonneg_f : 0 ≤ f k v w := hnn v w
          nlinarith
        rw [← h_geom, h_lhs] at h_le
        linarith
    
  5. Summing over all sessions yields $r \sum_k d(s_k, t_k) \le \sum_k \sum_{v, w} f_k(v, w) d(v, w)$.

    Distribute multiplication by $r$ across the sum over sessions $k \in K$ using `mul_sum`, and apply the single-session bound term by term via `sum_le_sum`.

    lines 53–58

    uses mul_sum, sum_le_sum

      have h_sum_k : r * (∑ k, d (sess.src k) (sess.tgt k)) ≤ ∑ k, ∑ v, ∑ w, f k v w * d v w := by
        rw [mul_sum]
        apply sum_le_sum
        intro k _
        exact h_single k
    
  6. The summation order can be exchanged: $\sum_k \sum_{v, w} f_k(v, w) d(v, w) = \sum_{v, w} \sum_k f_k(v, w) d(v, w)$.

    Exchange the outer summation over sessions $k$ with the inner summations over vertices $v$ and $w$ by repeatedly applying `sum_comm`.

    lines 59–64

    uses sum_comm

      have h_comm : (∑ k, ∑ v, ∑ w, f k v w * d v w) = ∑ v, ∑ w, ∑ k, f k v w * d v w := by
        rw [sum_comm]
        congr 1
        ext v
        rw [sum_comm]
    
  7. Twice the total flow cost equals the sum over all ordered pairs $(v, w)$ of the bidirectional flow weighted by distance: $2 \sum_{v, w} \sum_k f_k(v, w) d(v, w) = \sum_{v, w} (\sum_k (f_k(v, w) + f_k(w, v))) d(v, w)$.

    Express twice the sum as the sum added to itself. In the second copy, swap the summation indices $v$ and $w$ using `sum_comm`, and replace $d(w, v)$ with $d(v, w)$ by the symmetry of $d$. Combining the two copies and factoring out $d(v, w)$ yields the total bidirectional flow $\sum_k (f_k(v, w) + f_k(w, v))$ on each pair $(v, w)$.

    lines 65–79

    uses sum_comm, sum_congr, sum_add_distrib, add_mul, sum_mul

      have h_pair : 2 * (∑ v, ∑ w, ∑ k, f k v w * d v w) =
          ∑ v, ∑ w, (∑ k, (f k v w + f k w v)) * d v w := by
        have h_two : 2 * (∑ v, ∑ w, ∑ k, f k v w * d v w) =
            (∑ v, ∑ w, ∑ k, f k v w * d v w) + (∑ v, ∑ w, ∑ k, f k v w * d v w) := by ring
        rw [h_two]
        have h_swap : (∑ v, ∑ w, ∑ k, f k v w * d v w) = ∑ v, ∑ w, ∑ k, f k w v * d v w := by
          rw [sum_comm]
          apply sum_congr rfl
          intro w _
          apply sum_congr rfl
          intro v _
          rw [h_symm w v]
        nth_rw 2 [h_swap]
        simp_rw [← sum_add_distrib, ← add_mul, ← sum_mul]
    
  8. The bidirectional flow cost is bounded by the network capacity: $\sum_{v, w} (\sum_k (f_k(v, w) + f_k(w, v))) d(v, w) \le \sum_{u, v} \text{cap}(\{u, v\}) d(u, v)$.

    Compare the sums term by term. If $u = v$, the distance $d(u, u) = 0$, so both sides are zero. If $u \ne v$, the multicommodity flow capacity constraint guarantees that $\sum_k (f_k(u, v) + f_k(v, u)) \le \text{cap}(\{u, v\})$. Since distances are nonnegative ($d(u, v) \ge 0$), multiplying by $d(u, v)$ preserves the inequality.

    lines 80–93

    uses sum_le_sum

      have h_cap_le : (∑ v, ∑ w, (∑ k, (f k v w + f k w v)) * d v w) ≤ ∑ u, ∑ v, net.cap s(u, v) * d u v := by
        apply sum_le_sum
        intro u _
        apply sum_le_sum
        intro v _
        by_cases huv : u = v
        · subst huv
          rw [h_diag u]
          ring_nf
          rfl
        · have hcap := hf.2.1 u v huv
          have hd := h_nonneg u v
          nlinarith
    
  9. Combining the chain of inequalities proves $2 r \sum_k d(s_k, t_k) \le \sum_{u, v} \text{cap}(\{u, v\}) d(u, v)$.

    Chain together the inequalities established in the previous steps: $2 r \sum_k d(s_k, t_k) = 2 (r \sum_k d(s_k, t_k)) \le 2 \sum_{k, v, w} f_k(v, w) d(v, w) = 2 \sum_{v, w, k} f_k(v, w) d(v, w) = \sum_{v, w} (\sum_k (f_k(v, w) + f_k(w, v))) d(v, w) \le \sum_{u, v} \text{cap}(\{u, v\}) d(u, v)$.

    lines 94–100

      calc
        2 * r * (∑ k, d (sess.src k) (sess.tgt k))
          = 2 * (r * ∑ k, d (sess.src k) (sess.tgt k)) := by ring
        _ ≤ 2 * (∑ k, ∑ v, ∑ w, f k v w * d v w) := by nlinarith
        _ = 2 * (∑ v, ∑ w, ∑ k, f k v w * d v w) := by rw [h_comm]
        _ = ∑ v, ∑ w, (∑ k, (f k v w + f k w v)) * d v w := h_pair
        _ ≤ ∑ u, ∑ v, net.cap s(u, v) * d u v := h_cap_le
sum_add_distrib
Distributing summation over addition: $\sum_{x \in s} (f(x) + g(x)) = \sum_{x \in s} f(x) + \sum_{x \in s} g(x)$.
sub_mul
Right distributivity of multiplication over subtraction: $(a - b) \cdot c = a \cdot c - b \cdot c$.
sum_sub_distrib
Distributing summation over subtraction: $\sum_{x \in s} (f(x) - g(x)) = \sum_{x \in s} f(x) - \sum_{x \in s} g(x)$.
sum_mul
Factoring a constant out of a finite sum on the right: $(\sum_{i \in s} f(i)) \cdot a = \sum_{i \in s} (f(i) \cdot a)$.
sum_comm
Fubini's theorem for finite sums: exchanging the order of summation $\sum_{x \in s} \sum_{y \in t} f(x, y) = \sum_{y \in t} \sum_{x \in s} f(x, y)$.
mul_sub
Left distributivity of multiplication over subtraction: $a \cdot (b - c) = a \cdot b - a \cdot c$.
sum_neg_distrib
Distributing summation over negation: $\sum_{x \in s} -f(x) = -\sum_{x \in s} f(x)$.
sum_le_sum
Monotonicity of finite sums: if $f(i) \le g(i)$ for all $i \in s$, then $\sum_{i \in s} f(i) \le \sum_{i \in s} g(i)$.
mul_sum
Factoring a constant out of a finite sum on the left: $a \cdot \sum_{i \in s} f(i) = \sum_{i \in s} (a \cdot f(i))$.
sum_congr
Congruence of finite sums: two sums are equal if their index sets are equal and their summands agree at every index.
add_mul
Right distributivity of multiplication over addition: $(a + b) \cdot c = a \cdot c + b \cdot c$.

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

/-- Metric (potential) upper bound on the common rate of a fractional multicommodity flow. -/theorem flow_rate_mul_two_le_sum_cap_mul_dist    {V : Type} [Fintype V] [DecidableEq V] {K : Type} [Fintype K] [DecidableEq K]    (net : CapacitatedNetwork V) (sess : UnicastSessions V K) {r : ℝ}    (h : FlowSupportsRate net sess r) (d : V → V → ℝ)    (h_nonneg : ∀ u v, 0 ≤ d u v) (h_symm : ∀ u v, d u v = d v u)    (h_diag : ∀ u, d u u = 0) (h_tri : ∀ u v w, d u v ≤ d u w + d w v) :    2 * r * (∑ k, d (sess.src k) (sess.tgt k)) ≤ ∑ u, ∑ v, net.cap s(u, v) * d u v := by  open Finset in  obtain ⟨f, hf⟩ := h  have h_single : ∀ k : K, r * d (sess.src k) (sess.tgt k) ≤ ∑ v, ∑ w, f k v w * d v w := by    intro k    have hdiv := hf.2.2 k    have hnn := hf.1 k    set s := sess.src k    set t := sess.tgt k    have hst : s ≠ t := sess.src_ne_tgt k    have h_lhs : (∑ v, (∑ w, f k v w - ∑ u, f k u v) * d s v) = -r * d s t := by      have h_split : ∀ v, (∑ w, f k v w - ∑ u, f k u v) * d s v =          (if v = s then r * d s s else 0) + (if v = t then -r * d s t else 0) := by        intro v        rw [hdiv v]        split_ifs <;> (try subst_vars) <;> (try contradiction) <;> ring      simp_rw [h_split, sum_add_distrib]      have hd_ss : d s s = 0 := h_diag s      simp [hd_ss]    have h_geom : (∑ v, (∑ w, f k v w - ∑ u, f k u v) * d s v) = ∑ v, ∑ w, f k v w * (d s v - d s w) := by      have h1 : (∑ v, (∑ w, f k v w - ∑ u, f k u v) * d s v) =          (∑ v, (∑ w, f k v w) * d s v) - (∑ v, (∑ u, f k u v) * d s v) := by        simp_rw [sub_mul, sum_sub_distrib]      have h2 : (∑ v, (∑ u, f k u v) * d s v) = ∑ v, ∑ w, f k v w * d s w := by        simp_rw [sum_mul]        rw [sum_comm]      have h3 : (∑ v, (∑ w, f k v w) * d s v) = ∑ v, ∑ w, f k v w * d s v := by        simp_rw [sum_mul]      rw [h1, h2, h3]      simp_rw [← sum_sub_distrib, ← mul_sub]    have h_le : - ∑ v, ∑ w, f k v w * d v w ≤ ∑ v, ∑ w, f k v w * (d s v - d s w) := by      rw [← sum_neg_distrib]      apply sum_le_sum      intro v _      rw [← sum_neg_distrib]      apply sum_le_sum      intro w _      have htri : - d v w ≤ d s v - d s w := by        have := h_tri s w v        linarith      have h_nonneg_f : 0 ≤ f k v w := hnn v w      nlinarith    rw [← h_geom, h_lhs] at h_le    linarith  have h_sum_k : r * (∑ k, d (sess.src k) (sess.tgt k)) ≤ ∑ k, ∑ v, ∑ w, f k v w * d v w := by    rw [mul_sum]    apply sum_le_sum    intro k _    exact h_single k  have h_comm : (∑ k, ∑ v, ∑ w, f k v w * d v w) = ∑ v, ∑ w, ∑ k, f k v w * d v w := by    rw [sum_comm]    congr 1    ext v    rw [sum_comm]  have h_pair : 2 * (∑ v, ∑ w, ∑ k, f k v w * d v w) =      ∑ v, ∑ w, (∑ k, (f k v w + f k w v)) * d v w := by    have h_two : 2 * (∑ v, ∑ w, ∑ k, f k v w * d v w) =        (∑ v, ∑ w, ∑ k, f k v w * d v w) + (∑ v, ∑ w, ∑ k, f k v w * d v w) := by ring    rw [h_two]    have h_swap : (∑ v, ∑ w, ∑ k, f k v w * d v w) = ∑ v, ∑ w, ∑ k, f k w v * d v w := by      rw [sum_comm]      apply sum_congr rfl      intro w _      apply sum_congr rfl      intro v _      rw [h_symm w v]    nth_rw 2 [h_swap]    simp_rw [← sum_add_distrib, ← add_mul, ← sum_mul]  have h_cap_le : (∑ v, ∑ w, (∑ k, (f k v w + f k w v)) * d v w) ≤ ∑ u, ∑ v, net.cap s(u, v) * d u v := by    apply sum_le_sum    intro u _    apply sum_le_sum    intro v _    by_cases huv : u = v    · subst huv      rw [h_diag u]      ring_nf      rfl    · have hcap := hf.2.1 u v huv      have hd := h_nonneg u v      nlinarith  calc    2 * r * (∑ k, d (sess.src k) (sess.tgt k))      = 2 * (r * ∑ k, d (sess.src k) (sess.tgt k)) := by ring    _ ≤ 2 * (∑ k, ∑ v, ∑ w, f k v w * d v w) := by nlinarith    _ = 2 * (∑ v, ∑ w, ∑ k, f k v w * d v w) := by rw [h_comm]    _ = ∑ v, ∑ w, (∑ k, (f k v w + f k w v)) * d v w := h_pair    _ ≤ ∑ u, ∑ v, net.cap s(u, v) * d u v := h_cap_le
See it in the graphDiscuss this resultChallenge it