AFTD Auto-Formalizing Theoretical Domains

flow_session_cut_demand_eq

theoremverified

Summing the session demand indicators over a cut S yields r if src ∈ S and tgt ∉ S, -r if src ∉ S and tgt ∈ S, and 0 otherwise.

Statement

theorem flow_session_cut_demand_eq
    {V : Type} [Fintype V] [DecidableEq V] {K : Type} [Fintype K]
    (sess : UnicastSessions V K) (r : ℝ) (k : K) (S : Finset V) :
    ∑ v ∈ S, (if v = sess.src k then r else if v = sess.tgt k then -r else 0) =
      if sess.src k ∈ S ∧ sess.tgt k ∉ S then r
      else if sess.src k ∉ S ∧ sess.tgt k ∈ S then -r
      else 0
Source
step towards undirected_binary_linear_unicast_advantage
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • 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
  • flow_rate_mul_sep_le_cut_capacityIf a fractional multicommodity flow supports the common rate r, then for every vertex set S, r times the number of sessions crossing S is…

The proof, explained

The theorem computes the net demand of a unicast session across a cut $S$, where the source contributes $r$ and the target contributes $-r$. Because the source and target of any session are distinct, the summand splits into the sum of two separate single-vertex indicator functions. Evaluating each sum over $S$ leaves a sum of two conditionals, which simplifies across the four membership cases for the source and target to the required cut demand formula.

  1. The sum decomposes into two separate sums: one for the source vertex demand and one for the target vertex demand.

    We establish the lemma `hsplit`. Rewriting in reverse with `Finset.sum_add_distrib` merges the two sums into one. By `Finset.sum_congr`, it suffices to check pointwise equality of the summands for each $v \in S$. We split into cases on whether $v = \text{sess.src } k$: if so, since the source and target are distinct (`sess.src_ne_tgt`), $v \neq \text{sess.tgt } k$, so both the original summand and the sum of indicators equal $r$; if $v \neq \text{sess.src } k$, the source indicator is zero and both sides reduce to $-r$ when $v = \text{sess.tgt } k$ and $0$ otherwise.

    lines 9–18

    uses Finset.sum_add_distrib, Finset.sum_congr, sess.src_ne_tgt

      have hsplit :
          (∑ v ∈ S, (if v = sess.src k then r else if v = sess.tgt k then -r else 0))
            = (∑ v ∈ S, (if v = sess.src k then r else 0))
              + (∑ v ∈ S, (if v = sess.tgt k then -r else 0)) := by
        rw [← Finset.sum_add_distrib]
        apply Finset.sum_congr rfl
        intro v hv
        by_cases hvs : v = sess.src k
        · simp [hvs, sess.src_ne_tgt k]
        · simp [hvs]
  2. The sum evaluates to $(\text{if } \text{sess.src } k \in S \text{ then } r \text{ else } 0) + (\text{if } \text{sess.tgt } k \in S \text{ then } -r \text{ else } 0)$.

    Rewriting with `hsplit` replaces the original sum with the two separate indicator sums. Applying `Finset.sum_ite_eq'` to each sum evaluates the summation over $S$: an indicator concentrated at a single point equals the value ($r$ or $-r$) if that point belongs to $S$, and $0$ if it does not.

    line 19

    uses Finset.sum_ite_eq'

      rw [hsplit, Finset.sum_ite_eq', Finset.sum_ite_eq']
  3. The evaluated sum equals the conditional session cut demand formula.

    We split into cases based on whether $\text{sess.src } k \in S$ and whether $\text{sess.tgt } k \in S$. In all four cases, arithmetic and propositional simplification verify the equality: when both vertices are in $S$, $r + (-r) = 0$; when only the source is in $S$, the sum is $r$; when only the target is in $S$, the sum is $-r$; and when neither is in $S$, $0 + 0 = 0$.

    lines 20–21

      by_cases hsrc : sess.src k ∈ S <;> by_cases htgt : sess.tgt k ∈ S <;>
        simp [hsrc, htgt]
Finset.sum_add_distrib
The sum over a finite set distributes over addition: $\sum_{x \in s} (f(x) + g(x)) = \sum_{x \in s} f(x) + \sum_{x \in s} g(x)$.
Finset.sum_congr
Two sums over equal finite sets are equal if their summands agree on every element of the set.
Finset.sum_ite_eq'
Summing an indicator function that is $b(x)$ when $x = a$ and $0$ otherwise over a finite set $s$ yields $b(a)$ if $a \in s$, and $0$ if $a \notin s$.
sess.src_ne_tgt
For any session $k$, its source vertex is distinct from its target vertex: $\text{sess.src } k \neq \text{sess.tgt } k$.

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

/-- Summing the session demand indicators over a cut S yields r if src ∈ S and tgt ∉ S, -r if src ∉ S and tgt ∈ S, and 0 otherwise. -/theorem flow_session_cut_demand_eq    {V : Type} [Fintype V] [DecidableEq V] {K : Type} [Fintype K]    (sess : UnicastSessions V K) (r : ℝ) (k : K) (S : Finset V) :    ∑ v ∈ S, (if v = sess.src k then r else if v = sess.tgt k then -r else 0) =      if sess.src k ∈ S ∧ sess.tgt k ∉ S then r      else if sess.src k ∉ S ∧ sess.tgt k ∈ S then -r      else 0 := by  have hsplit :      (∑ v ∈ S, (if v = sess.src k then r else if v = sess.tgt k then -r else 0))        = (∑ v ∈ S, (if v = sess.src k then r else 0))          + (∑ v ∈ S, (if v = sess.tgt k then -r else 0)) := by    rw [← Finset.sum_add_distrib]    apply Finset.sum_congr rfl    intro v hv    by_cases hvs : v = sess.src k    · simp [hvs, sess.src_ne_tgt k]    · simp [hvs]  rw [hsplit, Finset.sum_ite_eq', Finset.sum_ite_eq']  by_cases hsrc : sess.src k ∈ S <;> by_cases htgt : sess.tgt k ∈ S <;>    simp [hsrc, htgt]
See it in the graphDiscuss this resultChallenge it