flow_supports_rate_scaled_capacities
Fractional multicommodity flow feasibility is homogeneous of degree one in (flow, rate, capacities): for T > 0, a flow of common rate T*r on the network with capacities T * cap is the same object as a flow of rate r on the network with capacities cap (multiply the flow by T in one direction, divide by it in the other). Both the capacity inequalities and the conservation equations are linear, which is the whole content.
Statement
theorem flow_supports_rate_scaled_capacities {V : Type} [Fintype V] [DecidableEq V] {K : Type} [Fintype K] [DecidableEq K] (net : CapacitatedNetwork V) (sess : UnicastSessions V K) {T : ℕ} (hT : 0 < T) (r : ℝ) : (∃ net' : CapacitatedNetwork V, (∀ e : Sym2 V, net'.cap e = (T : ℝ) * net.cap e) ∧ FlowSupportsRate net' sess ((T : ℝ) * r)) ↔ FlowSupportsRate net sess r
- Source
- step towards single_slot_binary_linear_coding_advantage
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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…
- 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,…
- Used by 1
- single_slot_advantage_of_multislot_advantageAny multi-slot coding advantage yields a one-slot coding advantage: if on some instance the code rate strictly exceeds every supported…
The proof, explained
The theorem establishes degree-one homogeneity of multicommodity flow feasibility under simultaneous scaling of capacities, flow, and session rate by an integer factor T > 0. In the forward direction, dividing a valid flow on the scaled network by T distributes over sums and differences, preserving nonnegativity, capacity bounds, and conservation equations at rate r. Conversely, scaling a valid flow of rate r by T satisfies the capacity constraints and conservation laws for rate T * r on the explicitly constructed scaled network.
The integer scaling factor T is strictly positive and nonzero as a real number.
Casting the natural number hypothesis 0 < T to the real numbers gives T > 0, from which T ≠ 0 follows immediately by `ne_of_gt`.
uses
ne_of_gthave hTpos : (0 : ℝ) < (T : ℝ) := by exact_mod_cast hT have hTne : (T : ℝ) ≠ 0 := ne_of_gt hTpos
In the forward direction, assuming a valid flow f of rate T * r on the scaled network, the candidate scaled flow f / T is well-defined and nonnegative.
We split the equivalence into both directions (`constructor`). Assuming a network net' with capacities T * cap and a flow f supporting rate T * r, we propose f / T as the flow on the original network. Since f ≥ 0 and T > 0, each component f(k, u, v) / T is nonnegative by `div_nonneg`.
uses
div_nonneg,le_of_ltconstructor · rintro ⟨net', hcap, f, h1, h2, h3⟩ refine ⟨fun k u v => f k u v / (T : ℝ), ?_, ?_, ?_⟩ · intro k u v exact div_nonneg (h1 k u v) (le_of_lt hTpos)
The candidate flow f / T satisfies the edge capacity constraints on the original network net.
For distinct vertices u and v, division by T is factored out of the commodity sum using `add_div`, `Finset.sum_congr`, and `Finset.sum_div`. Clearing the division via `div_le_iff₀` reduces the capacity bound to ∑_k (f_k(u,v) + f_k(v,u)) ≤ net.cap(u,v) * T, which holds because the sum is at most net'.cap(u,v) = T * net.cap(u,v).
uses
Finset.sum_congr,add_div,Finset.sum_div,div_le_iff₀· intro u v huv have e1 : ∑ k, (f k u v / (T:ℝ) + f k v u / (T:ℝ)) = (∑ k, (f k u v + f k v u)) / (T:ℝ) := by have step1 : ∑ k, (f k u v / (T:ℝ) + f k v u / (T:ℝ)) = ∑ k, ((f k u v + f k v u) / (T:ℝ)) := by apply Finset.sum_congr rfl; intro k _; rw [← add_div] rw [step1, ← Finset.sum_div] rw [e1, div_le_iff₀ hTpos] calc ∑ k, (f k u v + f k v u) ≤ net'.cap s(u,v) := h2 u v huv _ = (T:ℝ) * net.cap s(u,v) := hcap s(u,v) _ = net.cap s(u,v) * (T:ℝ) := by ring
The candidate flow f / T satisfies flow conservation for rate r at all vertices.
Division by T is factored out of the outgoing and incoming sums via `Finset.sum_div`, and combined across subtraction by `sub_div`. By flow conservation for f, the net outflow is T * r at the source, -(T * r) at the target, and 0 elsewhere. A case split (`split_ifs`) followed by division by T ≠ 0 (`div_eq_iff`) reduces these three cases to r, -r, and 0 respectively.
uses
Finset.sum_div,sub_div,div_eq_iff· intro k v have e1 : ∑ w, f k v w / (T:ℝ) = (∑ w, f k v w) / (T:ℝ) := by rw [Finset.sum_div] have e2 : ∑ u, f k u v / (T:ℝ) = (∑ u, f k u v) / (T:ℝ) := by rw [Finset.sum_div] rw [e1, e2, ← sub_div, h3 k v] split_ifs with hv1 hv2 · rw [div_eq_iff hTne]; ring · rw [div_eq_iff hTne]; ring · simp
In the backward direction, given a valid flow g of rate r on net, there exists a valid network net' with capacities T * cap.
We define net' with the same underlying graph and edge capacities net'.cap(e) = T * net.cap(e). The network axioms hold: capacities on edges are positive by `mul_pos` because T > 0 and net.cap(e) > 0, and vanish off edges by `mul_zero` because T * 0 = 0. By definition, net'.cap matches T * net.cap everywhere.
uses
mul_pos,mul_zero· rintro ⟨g, h1, h2, h3⟩ let net' : CapacitatedNetwork V := { G := net.G decAdj := net.decAdj cap := fun e => (T:ℝ) * net.cap e cap_pos := by intro e he; exact mul_pos hTpos (net.cap_pos e he) cap_zero := by intro e he; rw [net.cap_zero e he, mul_zero] } refine ⟨net', ?_, ?_⟩ · intro e; rflThe candidate scaled flow T * g is nonnegative.
We propose T * g as the flow supporting rate T * r on net'. Since T ≥ 0 and g ≥ 0, each component T * g(k, u, v) is nonnegative by `mul_nonneg`.
uses
mul_nonneg,le_of_lt· refine ⟨fun k u v => (T:ℝ) * g k u v, ?_, ?_, ?_⟩ · intro k u v exact mul_nonneg (le_of_lt hTpos) (h1 k u v)
The scaled flow T * g satisfies the capacity constraints on net'.
Factoring T out of the sum of forward and reverse flows across all commodities using `Finset.mul_sum` yields T * ∑_k (g_k(u,v) + g_k(v,u)). Multiplying the capacity bound of g by T ≥ 0 via `mul_le_mul_of_nonneg_left` shows this is bounded by T * net.cap(u,v) = net'.cap(u,v).
uses
Finset.mul_sum,Finset.sum_congr,mul_le_mul_of_nonneg_left,le_of_lt· intro u v huv have hcap' : net'.cap s(u,v) = (T:ℝ) * net.cap s(u,v) := rfl rw [hcap'] have e1 : ∑ k, ((T:ℝ) * g k u v + (T:ℝ) * g k v u) = (T:ℝ) * ∑ k, (g k u v + g k v u) := by rw [Finset.mul_sum] apply Finset.sum_congr rfl; intro k _; ring rw [e1] exact mul_le_mul_of_nonneg_left (h2 u v huv) (le_of_lt hTpos)
The scaled flow T * g satisfies flow conservation for rate T * r on net'.
Factoring T out of both the outgoing and incoming sums via `Finset.mul_sum`, and across the difference via `mul_sub`, factors the net divergence as T times the net divergence of g. Substituting the conservation equation for g and case splitting (`split_ifs`) yields T * r at the source, -(T * r) at the target, and 0 at intermediate nodes.
uses
Finset.mul_sum,mul_sub· intro k v have e1 : ∑ w, (T:ℝ) * g k v w = (T:ℝ) * ∑ w, g k v w := by rw [Finset.mul_sum] have e2 : ∑ u, (T:ℝ) * g k u v = (T:ℝ) * ∑ u, g k u v := by rw [Finset.mul_sum] rw [e1, e2, ← mul_sub, h3 k v] split_ifs <;> ring
ne_of_gt- If b < a, then a ≠ b.
div_nonneg- If a ≥ 0 and b ≥ 0, then a / b ≥ 0.
le_of_lt- If a < b, then a ≤ b.
Finset.sum_congr- If two finite index sets are equal and the summands agree pointwise, the two finite sums are equal.
add_div- (a + b) / c = a / c + b / c in a division semiring.
Finset.sum_div- Factoring division out of a finite sum: (∑ i ∈ s, f i) / a = ∑ i ∈ s, (f i / a).
div_le_iff₀- For c > 0, b / c ≤ a ↔ b ≤ a * c.
sub_div- (a - b) / c = a / c - b / c in a division ring.
div_eq_iff- For b ≠ 0, a / b = c ↔ a = c * b.
mul_pos- If a > 0 and b > 0, then a * b > 0.
mul_zero- a * 0 = 0 in a structure with zero multiplication.
mul_nonneg- If a ≥ 0 and b ≥ 0, then a * b ≥ 0.
Finset.mul_sum- Distributing multiplication across a finite sum: a * ∑ i ∈ s, f i = ∑ i ∈ s, a * f i.
mul_le_mul_of_nonneg_left- If b ≤ c and a ≥ 0, then a * b ≤ a * c.
mul_sub- Distributivity of multiplication over subtraction: a * (b - c) = a * b - a * c.
- In Lean, a `CapacitatedNetwork` bundles the graph together with proofs that capacities are strictly positive on edges and zero off edges; in the backward direction, these properties must be explicitly re-verified for the scaled capacities.
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.
/-- Flow feasibility is homogeneous of degree one: rate T*r on capacities T * cap is rate r on capacities cap. -/theorem flow_supports_rate_scaled_capacities {V : Type} [Fintype V] [DecidableEq V] {K : Type} [Fintype K] [DecidableEq K] (net : CapacitatedNetwork V) (sess : UnicastSessions V K) {T : ℕ} (hT : 0 < T) (r : ℝ) : (∃ net' : CapacitatedNetwork V, (∀ e : Sym2 V, net'.cap e = (T : ℝ) * net.cap e) ∧ FlowSupportsRate net' sess ((T : ℝ) * r)) ↔ FlowSupportsRate net sess r := by have hTpos : (0 : ℝ) < (T : ℝ) := by exact_mod_cast hT have hTne : (T : ℝ) ≠ 0 := ne_of_gt hTpos constructor · rintro ⟨net', hcap, f, h1, h2, h3⟩ refine ⟨fun k u v => f k u v / (T : ℝ), ?_, ?_, ?_⟩ · intro k u v exact div_nonneg (h1 k u v) (le_of_lt hTpos) · intro u v huv have e1 : ∑ k, (f k u v / (T:ℝ) + f k v u / (T:ℝ)) = (∑ k, (f k u v + f k v u)) / (T:ℝ) := by have step1 : ∑ k, (f k u v / (T:ℝ) + f k v u / (T:ℝ)) = ∑ k, ((f k u v + f k v u) / (T:ℝ)) := by apply Finset.sum_congr rfl; intro k _; rw [← add_div] rw [step1, ← Finset.sum_div] rw [e1, div_le_iff₀ hTpos] calc ∑ k, (f k u v + f k v u) ≤ net'.cap s(u,v) := h2 u v huv _ = (T:ℝ) * net.cap s(u,v) := hcap s(u,v) _ = net.cap s(u,v) * (T:ℝ) := by ring · intro k v have e1 : ∑ w, f k v w / (T:ℝ) = (∑ w, f k v w) / (T:ℝ) := by rw [Finset.sum_div] have e2 : ∑ u, f k u v / (T:ℝ) = (∑ u, f k u v) / (T:ℝ) := by rw [Finset.sum_div] rw [e1, e2, ← sub_div, h3 k v] split_ifs with hv1 hv2 · rw [div_eq_iff hTne]; ring · rw [div_eq_iff hTne]; ring · simp · rintro ⟨g, h1, h2, h3⟩ let net' : CapacitatedNetwork V := { G := net.G decAdj := net.decAdj cap := fun e => (T:ℝ) * net.cap e cap_pos := by intro e he; exact mul_pos hTpos (net.cap_pos e he) cap_zero := by intro e he; rw [net.cap_zero e he, mul_zero] } refine ⟨net', ?_, ?_⟩ · intro e; rfl · refine ⟨fun k u v => (T:ℝ) * g k u v, ?_, ?_, ?_⟩ · intro k u v exact mul_nonneg (le_of_lt hTpos) (h1 k u v) · intro u v huv have hcap' : net'.cap s(u,v) = (T:ℝ) * net.cap s(u,v) := rfl rw [hcap'] have e1 : ∑ k, ((T:ℝ) * g k u v + (T:ℝ) * g k v u) = (T:ℝ) * ∑ k, (g k u v + g k v u) := by rw [Finset.mul_sum] apply Finset.sum_congr rfl; intro k _; ring rw [e1] exact mul_le_mul_of_nonneg_left (h2 u v huv) (le_of_lt hTpos) · intro k v have e1 : ∑ w, (T:ℝ) * g k v w = (T:ℝ) * ∑ w, g k v w := by rw [Finset.mul_sum] have e2 : ∑ u, (T:ℝ) * g k u v = (T:ℝ) * ∑ u, g k u v := by rw [Finset.mul_sum] rw [e1, e2, ← mul_sub, h3 k v] split_ifs <;> ring