AFTD Auto-Formalizing Theoretical Domains

flow_supports_rate_mono

theoremverified

If a fractional multicommodity flow on net with sessions sess supports common rate r, then for any non-negative rate r' ≤ r, rate r' is also supported.

Statement

theorem flow_supports_rate_mono {V : Type} [Fintype V] [DecidableEq V] {K : Type} [Fintype K] [DecidableEq K]
    (net : CapacitatedNetwork V) (sess : UnicastSessions V K) {r r' : ℝ}
    (h_supp : FlowSupportsRate net sess r) (h_nonneg : 0 ≤ r') (h_le : r' ≤ r) :
    FlowSupportsRate net sess r'
Source
folklore
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • 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…
  • flow_supports_rate_zeroOn any capacitated network net with unicast sessions sess, the common rate zero is always supported by fractional multicommodity flow.

Read back from the Lean

For any finite types $V$ and $K$ with decidable equality, any capacitated network net on vertex type $V$, any collection of unicast sessions sess indexed by $K$, and any real numbers $r$ and $r'$: if the network supports the transmission rate $r$ for the sessions sess (h_supp), and $0 \le r'$ (h_nonneg), and $r' \le r$ (h_le), then the network also supports the transmission rate $r'$ for sess.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

Multicommodity flow rates are downward-closed: if a network supports rate r, any non-negative rate r' ≤ r is also supported. The proof branches on whether r' = 0, which is supported trivially by the zero flow. For r' > 0, scaling an existing flow for rate r by the ratio r' / r ∈ [0, 1] yields a valid multicommodity flow that is non-negative, satisfies all edge capacities, and meets the scaled source-sink divergence demands.

  1. If r' = 0, rate r' is supported by the network.

    We split into cases on whether r' = 0. When r' = 0, substituting r' = 0 into the goal reduces it to supporting rate 0, which holds directly by `flow_supports_rate_zero`.

    lines 6–8

    uses flow_supports_rate_zero

      by_cases hr' : r' = 0
      · subst hr'
        exact flow_supports_rate_zero net sess
  2. When r' ≠ 0, scaling an existing flow f for rate r by r' / r gives a well-defined candidate flow.

    Since r' ≥ 0 and r' ≠ 0, we have 0 < r' by `lt_of_le_of_ne` and `Ne.symm`. Transitivity with r' ≤ r gives 0 < r (`lt_of_lt_of_le`) and r ≠ 0 (`ne_of_gt`). Hence the scaling factor c = r' / r satisfies 0 ≤ r' / r by `div_nonneg` and r' / r ≤ 1 by `div_le_one_of_le₀` (using `le_of_lt`). We extract the flow f supporting rate r from the hypothesis, and propose the scaled flow (k, u, v) ↦ (r' / r) * f(k, u, v), which leaves non-negativity, capacity constraints, and divergence conservation to be verified.

    lines 9–15

    uses lt_of_le_of_ne, Ne.symm, lt_of_lt_of_le, ne_of_gt, div_nonneg, le_of_lt, div_le_one_of_le₀

      · obtain ⟨f, hf_nonneg, hf_cap, hf_div⟩ := h_supp
        have hr'_pos : 0 < r' := lt_of_le_of_ne h_nonneg (Ne.symm hr')
        have hr_pos : 0 < r := lt_of_lt_of_le hr'_pos h_le
        have hr_ne : r ≠ 0 := ne_of_gt hr_pos
        have hc_nonneg : 0 ≤ r' / r := div_nonneg h_nonneg (le_of_lt hr_pos)
        have hc_le_one : r' / r ≤ 1 := div_le_one_of_le₀ h_le (le_of_lt hr_pos)
        refine ⟨fun k u v => (r' / r) * f k u v, ?_, ?_, ?_⟩
  3. The scaled flow is non-negative everywhere.

    For each commodity k and pair of vertices u, v, the scaled flow value (r' / r) * f(k, u, v) is non-negative because both r' / r ≥ 0 and f(k, u, v) ≥ 0, by `mul_nonneg`.

    lines 16–17

    uses mul_nonneg

        · intro k u v
          exact mul_nonneg hc_nonneg (hf_nonneg k u v)
  4. The scaled flow respects the edge capacities.

    For any distinct vertices u ≠ v, we factor r' / r out of the bidirectional flow sum across commodities using `mul_add` and `Finset.mul_sum`. Since the original flow components are non-negative, the total unscaled bidirectional flow S is non-negative by `Finset.sum_nonneg` and `add_nonneg`. Since S is bounded by the edge capacity cap(u, v) and 0 ≤ r' / r ≤ 1, non-linear arithmetic (`nlinarith`) confirms that the scaled sum (r' / r) * S ≤ cap(u, v).

    lines 18–26

    uses mul_add, Finset.mul_sum, Finset.sum_nonneg, add_nonneg

        · intro u v huv
          have h_add : ∀ k, (r' / r) * f k u v + (r' / r) * f k v u = (r' / r) * (f k u v + f k v u) :=
            fun k => (mul_add (r' / r) (f k u v) (f k v u)).symm
          simp_rw [h_add]
          rw [← Finset.mul_sum]
          have hS : 0 ≤ ∑ k, (f k u v + f k v u) :=
            Finset.sum_nonneg (fun k _ => add_nonneg (hf_nonneg k u v) (hf_nonneg k v u))
          have hSC := hf_cap u v huv
          nlinarith
  5. The scaled flow satisfies the flow conservation and divergence requirements.

    For each commodity k and vertex v, factoring r' / r out of the outgoing and incoming flow sums using `Finset.mul_sum` and `mul_sub` expresses the net flow as r' / r times the divergence of f at v. Substituting the divergence condition of f, we split into three cases: at the source vertex src(k), the net flow is (r' / r) * r = r' by `div_mul_cancel₀`; at the target vertex tgt(k), it is (r' / r) * (-r) = -r' by `mul_neg` and `div_mul_cancel₀`; and at all other vertices, it is (r' / r) * 0 = 0 by `mul_zero`.

    lines 27–33

    uses Finset.mul_sum, mul_sub, div_mul_cancel₀, mul_neg, mul_zero

        · intro k v
          rw [← Finset.mul_sum, ← Finset.mul_sum, ← mul_sub]
          rw [hf_div k v]
          split_ifs with h1 h2
          · exact div_mul_cancel₀ r' hr_ne
          · rw [mul_neg, div_mul_cancel₀ r' hr_ne]
          · exact mul_zero (r' / r)
flow_supports_rate_zero
Rate 0 is always supported on any capacitated network and unicast session system (by the all-zero flow).
lt_of_le_of_ne
If a ≤ b and a ≠ b, then a < b.
Ne.symm
Inequality is symmetric: if a ≠ b, then b ≠ a.
lt_of_lt_of_le
Strict inequality is transitive with non-strict inequality: if a < b and b ≤ c, then a < c.
ne_of_gt
If b < a, then a ≠ b.
div_nonneg
The quotient of two non-negative elements in a linearly ordered field (or group with zero) is non-negative.
le_of_lt
A strict inequality a < b implies the non-strict inequality a ≤ b.
div_le_one_of_le₀
If a ≤ b and 0 ≤ b, then a / b ≤ 1.
mul_nonneg
The product of two non-negative elements is non-negative.
mul_add
Multiplication distributes over addition from the left: a * (b + c) = a * b + a * c.
Finset.mul_sum
A scalar factor can be factored out of a finite sum: a * ∑ i ∈ s, f i = ∑ i ∈ s, a * f i.
Finset.sum_nonneg
A finite sum of non-negative terms is non-negative.
add_nonneg
The sum of two non-negative numbers is non-negative.
mul_sub
Multiplication distributes over subtraction from the left: a * (b - c) = a * b - a * c.
div_mul_cancel₀
Multiplying a / b by b cancels when b ≠ 0: (a / b) * b = a.
mul_neg
Multiplication by a negation: a * -b = -(a * b).
mul_zero
Any element multiplied by zero is zero: a * 0 = 0.

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

/-- Multicommodity flow rates are downward-closed. -/theorem flow_supports_rate_mono {V : Type} [Fintype V] [DecidableEq V] {K : Type} [Fintype K] [DecidableEq K]    (net : CapacitatedNetwork V) (sess : UnicastSessions V K) {r r' : ℝ}    (h_supp : FlowSupportsRate net sess r) (h_nonneg : 0 ≤ r') (h_le : r' ≤ r) :    FlowSupportsRate net sess r' := by  by_cases hr' : r' = 0  · subst hr'    exact flow_supports_rate_zero net sess  · obtain ⟨f, hf_nonneg, hf_cap, hf_div⟩ := h_supp    have hr'_pos : 0 < r' := lt_of_le_of_ne h_nonneg (Ne.symm hr')    have hr_pos : 0 < r := lt_of_lt_of_le hr'_pos h_le    have hr_ne : r ≠ 0 := ne_of_gt hr_pos    have hc_nonneg : 0 ≤ r' / r := div_nonneg h_nonneg (le_of_lt hr_pos)    have hc_le_one : r' / r ≤ 1 := div_le_one_of_le₀ h_le (le_of_lt hr_pos)    refine ⟨fun k u v => (r' / r) * f k u v, ?_, ?_, ?_⟩    · intro k u v      exact mul_nonneg hc_nonneg (hf_nonneg k u v)    · intro u v huv      have h_add : ∀ k, (r' / r) * f k u v + (r' / r) * f k v u = (r' / r) * (f k u v + f k v u) :=        fun k => (mul_add (r' / r) (f k u v) (f k v u)).symm      simp_rw [h_add]      rw [← Finset.mul_sum]      have hS : 0 ≤ ∑ k, (f k u v + f k v u) :=        Finset.sum_nonneg (fun k _ => add_nonneg (hf_nonneg k u v) (hf_nonneg k v u))      have hSC := hf_cap u v huv      nlinarith    · intro k v      rw [← Finset.mul_sum, ← Finset.mul_sum, ← mul_sub]      rw [hf_div k v]      split_ifs with h1 h2      · exact div_mul_cancel₀ r' hr_ne      · rw [mul_neg, div_mul_cancel₀ r' hr_ne]      · exact mul_zero (r' / r)
See it in the graphDiscuss this resultChallenge it