AFTD Auto-Formalizing Theoretical Domains

flow_rate_lt_of_strict_metric_bound

theoremverified

If a fractional multicommodity flow supports common rate r on net with sessions sess, and d is a nonnegative, symmetric, triangle-satisfying function on V with d(u,u) = 0 and positive total session length sum_k d(src k, tgt k), and the capacity-weighted total length is strictly less than 2*c times the total session length, then r < c.

Statement

theorem flow_rate_lt_of_strict_metric_bound
    {V : Type} [Fintype V] [DecidableEq V] {K : Type} [Fintype K] [DecidableEq K]
    (net : CapacitatedNetwork V) (sess : UnicastSessions V K) {r c : ℝ}
    (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)
    (hpos : 0 < ∑ k, d (sess.src k) (sess.tgt k))
    (hlt : ∑ u, ∑ v, net.cap s(u, v) * d u v < 2 * c * (∑ k, d (sess.src k) (sess.tgt k))) :
    r < c
Source
step towards undirected_binary_linear_unicast_advantage
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • flow_rate_mul_two_le_sum_cap_mul_distIf a fractional multicommodity flow on net supports the common rate r, and d is a symmetric, nonnegative, triangle-satisfying function on…
  • FlowSupportsRateA common rate r is supported by fractional multicommodity flow on a capacitated network net with unicast sessions sess if there exists a…
  • 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,…

The proof, explained

The theorem is proved by applying the metric inequality for multicommodity flows. First, the pseudometric properties of d guarantee that twice the flow rate times the total session distance is at most the capacity-weighted distance. Combining this upper bound with the strict assumption that the capacity-weighted distance is strictly less than 2 * c times the total session distance, and using the positivity of the total session distance, immediately yields r < c.

  1. 2 * r * ∑ k, d (sess.src k) (sess.tgt k) ≤ ∑ u, ∑ v, net.cap s(u, v) * d u v

    By flow_rate_mul_two_le_sum_cap_mul_dist, any pseudometric d (satisfying nonnegativity, symmetry, d(u,u) = 0, and the triangle inequality) yields an upper bound on the rate r: twice the rate times the sum of distances between session endpoints is at most the total capacity-weighted distance across all pairs of vertices.

    line 11

    uses flow_rate_mul_two_le_sum_cap_mul_dist

      have hmain := flow_rate_mul_two_le_sum_cap_mul_dist net sess h d h_nonneg h_symm h_diag h_tri
  2. r < c automation

    Chaining the metric bound 2 * r * D ≤ ∑ u, ∑ v, net.cap s(u, v) * d u v with the strict assumption ∑ u, ∑ v, net.cap s(u, v) * d u v < 2 * c * D yields 2 * r * D < 2 * c * D, where D = ∑ k, d (sess.src k) (sess.tgt k). Since D > 0 by assumption, nonlinear arithmetic concludes r < c.

    line 12

      nlinarith
flow_rate_mul_two_le_sum_cap_mul_dist
If a multicommodity flow supports rate r and d is a pseudometric (nonnegative, symmetric, vanishing on the diagonal, and satisfying the triangle inequality), then 2 * r * ∑ k, d (src k) (tgt k) ≤ ∑ u, ∑ v, cap(u, v) * d(u, v).

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

/-- A strict pseudometric certificate caps every fractional flow rate strictly below c. -/theorem flow_rate_lt_of_strict_metric_bound    {V : Type} [Fintype V] [DecidableEq V] {K : Type} [Fintype K] [DecidableEq K]    (net : CapacitatedNetwork V) (sess : UnicastSessions V K) {r c : ℝ}    (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)    (hpos : 0 < ∑ k, d (sess.src k) (sess.tgt k))    (hlt : ∑ u, ∑ v, net.cap s(u, v) * d u v < 2 * c * (∑ k, d (sess.src k) (sess.tgt k))) :    r < c := by  have hmain := flow_rate_mul_two_le_sum_cap_mul_dist net sess h d h_nonneg h_symm h_diag h_tri  nlinarith
See it in the graphDiscuss this resultChallenge it