AFTD Auto-Formalizing Theoretical Domains

flow_supports_rate_scaled_capacities

theoremverified

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

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.

  1. 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`.

    lines 7–8

    uses ne_of_gt

      have hTpos : (0 : ℝ) < (T : ℝ) := by exact_mod_cast hT
      have hTne : (T : ℝ) ≠ 0 := ne_of_gt hTpos
  2. 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`.

    lines 9–13

    uses div_nonneg, le_of_lt

      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)
  3. 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).

    lines 14–24

    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
  4. 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.

    lines 25–32

    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
  5. 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.

    lines 33–41

    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; rfl
  6. The 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`.

    lines 42–44

    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)
  7. 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).

    lines 45–53

    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)
  8. 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.

    lines 54–58

    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.

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

/-- 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
See it in the graphDiscuss this resultChallenge it