flow_rate_mul_two_le_sum_cap_mul_dist
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
- flow_rate_lt_of_strict_metric_boundIf a fractional multicommodity flow supports common rate r on net with sessions sess, and d is a nonnegative, symmetric,…
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.
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.
open Finset in obtain ⟨f, hf⟩ := h
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)$.
uses
sum_add_distribhave 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]
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))$.
uses
sub_mul,sum_sub_distrib,sum_mul,sum_comm,mul_subhave 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]
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)$.
uses
sum_neg_distrib,sum_le_sumhave 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
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`.
uses
mul_sum,sum_le_sumhave 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
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`.
uses
sum_commhave 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]
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)$.
uses
sum_comm,sum_congr,sum_add_distrib,add_mul,sum_mulhave 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]
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.
uses
sum_le_sumhave 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
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)$.
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$.
- The network capacity is defined on unordered pairs `s(u, v)`. The right-hand side sums over all ordered pairs $(u, v) \in V \times V$, effectively counting each undirected edge $\{u, v\}$ twice (once as $(u, v)$ and once as $(v, u)$), which balances the factor of 2 on the left-hand side.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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