AFTD Auto-Formalizing Theoretical Domains

cutSeparation_eq_sum

theoremverified

Express cutSeparation as a sum of real indicator functions over sessions k in K.

Statement

theorem cutSeparation_eq_sum
    {V : Type} [DecidableEq V] {K : Type} [Fintype K]
    (sess : UnicastSessions V K) (S : Finset V) :
    (cutSeparation sess S : ℝ) =
      ∑ k : K, if (sess.src k ∈ S) ≠ (sess.tgt k ∈ S) then (1 : ℝ) else 0
Source
step towards undirected_binary_linear_unicast_advantage
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • cutSeparationThe number of sessions (out of the unicast session set sess) with exactly one endpoint in the vertex set S, i.e. the number of sessions…
  • 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 proof unfolds the definition of `cutSeparation` as the cardinality of the subset of sessions separated by the cut S, expresses this cardinality as a sum of 1s, and converts the sum over the filtered set to a sum of indicator functions over all sessions in K. Finally, it pushes the coercion from the natural numbers to the real numbers into the sum.

  1. The cut separation is expressed as the natural-number sum over all sessions of an indicator function that is 1 when the session endpoints are separated by S and 0 otherwise.

    By definition, `cutSeparation sess S` is the cardinality of the subset of sessions whose source and target do not both lie on the same side of S. We rewrite this cardinality as a sum of 1s over the subset using `Finset.card_eq_sum_ones`, and then rewrite the sum over the filtered subset as a sum over all of K using `Finset.sum_filter`, inserting a conditional that yields 1 if the session is separated and 0 otherwise.

    lines 7–9

    uses Finset.card_eq_sum_ones, Finset.sum_filter

      simp only [cutSeparation]
      rw [Finset.card_eq_sum_ones]
      rw [Finset.sum_filter]
  2. The equality holds for the sum of real indicators. automation

    The simplification tactic distributes the natural-to-real coercion through the finite sum and the if-then-else branch, turning the integer 1 and 0 into the real numbers 1 and 0.

    line 10

      simp
Finset.card_eq_sum_ones
The cardinality of a finite set is the sum of 1 over all its elements.
Finset.sum_filter
The sum of a function over a filtered subset equals the sum over the whole set with an indicator function that is 0 outside the subset.

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

/-- Express cutSeparation as a sum of real indicator functions over sessions k in K. -/theorem cutSeparation_eq_sum    {V : Type} [DecidableEq V] {K : Type} [Fintype K]    (sess : UnicastSessions V K) (S : Finset V) :    (cutSeparation sess S : ℝ) =      ∑ k : K, if (sess.src k ∈ S) ≠ (sess.tgt k ∈ S) then (1 : ℝ) else 0 := by  simp only [cutSeparation]  rw [Finset.card_eq_sum_ones]  rw [Finset.sum_filter]  simp
See it in the graphDiscuss this resultChallenge it