AFTD Auto-Formalizing Theoretical Domains

condorcet_integer_circulation_of_neighbor_mass

theoremverified

For any finite directed relation and natural-number vertex weights w, assume every vertex set S has weight at most its outgoing neighborhood. Then there are natural-number edge multiplicities f, zero off the relation, whose row sums and column sums both equal w. This includes the zero-weight and loop cases.

Statement

theorem condorcet_integer_circulation_of_neighbor_mass
    (m : ℕ) (R : Fin m → Fin m → Prop) [DecidableRel R] (w : Fin m → ℕ)
    (hHall : ∀ S : Finset (Fin m),
      (∑ a ∈ S, w a) ≤ ∑ b ∈ univ.filter (fun b => ∃ a ∈ S, R a b), w b) :
    ∃ f : Fin m → Fin m → ℕ,
      (∀ a b, ¬ R a b → f a b = 0) ∧
      (∀ a, ∑ b, f a b = w a) ∧ (∀ b, ∑ a, f a b = w b)
Source
IN-380, OP-19 campaign session 8, 2026-10-30. Self-contained helper for the strict-half acyclic-separation route. The general unrestricted one-child equality was refuted in IN-372; this work repairs only the strict-half existence reduction. Standard finite matching, rational density, and circulation weak duality are used. No new election bound or research novelty is claimed. See lean/AFTD/Scratch/In380Oct30/HalfThresholdDerivation.txt.
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

The proof reduces the integer circulation problem with vertex weights to Hall's Marriage Theorem on an expanded vertex set. Each vertex a is replaced by w(a) identical clones, forming a finite set V = Σ a, Fin (w a). The hypothesis that every vertex subset has weight at most its out-neighborhood implies Hall's marriage condition for every subset of clones in V. Hall's theorem then provides an injective mapping from V to V along edges of R, which is necessarily a bijection because V is finite. Finally, the circulation f(a, b) is defined as the number of clones of a mapped to clones of b under this permutation, which directly satisfies the zero-support, row-sum, and column-sum requirements.

  1. Expand each vertex a into w(a) distinct clones, forming the finite type V = Σ a : Fin m, Fin (w a).

    We enable classical logic and define the cloned vertex set V as the dependent sum Σ a : Fin m, Fin (w a), where each vertex a is represented by w(a) copies (a, i) indexed by i < w(a).

    lines 13–14

      classical
      let V := Σ a : Fin m, Fin (w a)
  2. For any vertex subset S ⊆ Fin m, the number of clones belonging to vertices in S is ∑ a ∈ S, w a.

    We rewrite the cardinality of the filtered set of clones as the sum of 1 over all elements, rewrite the sum over the sigma type into an iterated sum via Fintype.sum_sigma, and rewrite the indicator sum over Fin m into a sum over S using Fintype.sum_ite_mem. For each vertex a, summing 1 over the w(a) clones yields w(a) if a ∈ S and 0 otherwise.

    lines 15–23

    uses card_eq_sum_ones, sum_filter, Fintype.sum_sigma, Fintype.sum_ite_mem, sum_congr

      have hcard (S : Finset (Fin m)) :
          (univ.filter (fun x : V => x.1 ∈ S)).card = ∑ a ∈ S, w a := by
        rw [card_eq_sum_ones,sum_filter]
        change (∑ x : (Σ a : Fin m, Fin (w a)), if x.1 ∈ S then 1 else 0) = _
        rw [Fintype.sum_sigma]
        rw [← Fintype.sum_ite_mem S w]
        apply sum_congr rfl
        intro a ha
        by_cases h : a ∈ S <;> simp [h]
  3. Hall's marriage condition holds for the cloned graph: every subset of clones B ⊆ V has at least as many neighbors as its size, |B| ≤ |⋃_{x ∈ B} neighbors(x)|.

    We define the neighbors of a clone x = (a, i) to be all clones y = (b, j) such that R a b. Given a subset B ⊆ V, let S be the projection of B onto Fin m and let N be the out-neighborhood of S under R. Then B is a subset of the clones over S, so |B| ≤ ∑ a ∈ S, w a by monotonicity (card_le_card) and the previous lemma (hcard). Furthermore, the union of the neighborhoods of all clones in B equals the set of all clones over N, which has size ∑ b ∈ N, w b by hcard. Hall's condition on the weights (hHall) ensures ∑ a ∈ S, w a ≤ ∑ b ∈ N, w b, establishing the inequality.

    lines 24–44

    uses mem_filter, mem_univ, mem_image, mem_biUnion, card_le_card

      let neighbors : V → Finset V := fun x => univ.filter (fun y => R x.1 y.1)
      have hclones : ∀ B : Finset V, B.card ≤ (B.biUnion neighbors).card := by
        intro B
        let S := B.image Sigma.fst
        let N := univ.filter (fun b => ∃ a ∈ S, R a b)
        have hB : B ⊆ univ.filter (fun x : V => x.1 ∈ S) := by
          intro x hx
          exact mem_filter.mpr ⟨mem_univ _,mem_image.mpr ⟨x,hx,rfl⟩⟩
        have hN : B.biUnion neighbors = univ.filter (fun y : V => y.1 ∈ N) := by
          ext y
          simp only [mem_biUnion,neighbors,mem_filter,mem_univ,true_and,N,S,mem_image]
          constructor
          · rintro ⟨x,hx,hxy⟩
            exact ⟨x.1,⟨x,hx,rfl⟩,hxy⟩
          · rintro ⟨a,⟨x,hx,rfl⟩,hay⟩
            exact ⟨x,hx,hay⟩
        calc
          B.card ≤ (univ.filter (fun x : V => x.1 ∈ S)).card := card_le_card hB
          _ = ∑ a ∈ S, w a := hcard S
          _ ≤ ∑ a ∈ N, w a := hHall S
          _ = (B.biUnion neighbors).card := by rw [hN,hcard]
  4. Hall's theorem yields a permutation e : V ≃ V along edges of R, from which we define the candidate circulation f.

    By Hall's Marriage Theorem (all_card_le_biUnion_card_iff_existsInjective'), there exists an injective function g : V → V with g(x) ∈ neighbors(x) for all x. Because V is finite, g is automatically bijective (bijective_of_finite), yielding an equivalence e : V ≃ V via Equiv.ofBijective. We then define f(a, b) to be the number of clones x ∈ V with x.1 = a and (e(x)).1 = b, and refine the goal into the three required conditions.

    lines 45–50

    uses all_card_le_biUnion_card_iff_existsInjective', bijective_of_finite, Equiv.ofBijective

      obtain ⟨g,hginj,hg⟩ := (all_card_le_biUnion_card_iff_existsInjective' neighbors).mp hclones
      have hgbij : Function.Bijective g := hginj.bijective_of_finite
      let e : V ≃ V := Equiv.ofBijective g hgbij
      let f : Fin m → Fin m → ℕ := fun a b =>
        (univ.filter (fun x : V => x.1 = a ∧ (e x).1 = b)).card
      refine ⟨f,?_,?_,?_⟩
  5. The circulation f vanishes off the relation: if ¬ R a b, then f(a, b) = 0.

    By card_eq_zero and eq_empty_iff_forall_notMem, it suffices to show that no clone x has x.1 = a and (e(x)).1 = b. If such a clone x existed, then since e(x) is a neighbor of x, we would have R x.1 (e(x)).1, which means R a b, contradicting ¬ R a b.

    lines 51–58

    uses card_eq_zero, eq_empty_iff_forall_notMem, mem_filter

      · intro a b hab
        apply card_eq_zero.mpr
        apply eq_empty_iff_forall_notMem.mpr
        intro x hx
        obtain ⟨_,ha,hb⟩ := mem_filter.mp hx
        have h := (mem_filter.mp (hg x)).2
        change R x.1 (e x).1 at h
        exact hab (ha ▸ hb ▸ h)
  6. For every vertex a, the row sum ∑ b, f(a, b) equals w(a).

    Summing f(a, b) over all b ∈ Fin m partitions the set of clones of a fiberwise according to their image under e. By sum_card_fiberwise_eq_card_filter, this sum equals the total number of clones of a, which is w(a) by hcard on the singleton {a}.

    lines 59–65

    uses sum_card_fiberwise_eq_card_filter, filter_filter

      · intro a
        have h := sum_card_fiberwise_eq_card_filter
          (univ.filter (fun x : V => x.1 = a)) univ (fun x : V => (e x).1)
        have heq : (∑ b, f a b) = (univ.filter (fun x : V => x.1 = a)).card := by
          simpa [f,filter_filter] using h
        rw [heq]
        simpa using hcard {a}
  7. For every vertex b, the column sum ∑ a, f(a, b) equals w(b).

    Summing f(a, b) over all a ∈ Fin m partitions the preimage fiber {x ∈ V | (e(x)).1 = b} according to x.1. By sum_card_fiberwise_eq_card_filter, this sum equals the size of that fiber. Since e is an equivalence, re-indexing via e.sum_comp shows that this cardinality equals the number of clones with target b, which is w(b) by hcard on {b}.

    lines 66–74

    uses sum_card_fiberwise_eq_card_filter, filter_filter, and_comm, card_eq_sum_ones, sum_filter, e.sum_comp

      · intro b
        have h := sum_card_fiberwise_eq_card_filter
          (univ.filter (fun x : V => (e x).1 = b)) univ (fun x : V => x.1)
        have heq : (∑ a, f a b) = (univ.filter (fun x : V => (e x).1 = b)).card := by
          simpa [f,filter_filter,and_comm] using h
        rw [heq,card_eq_sum_ones,sum_filter]
        rw [e.sum_comp (fun y : V => if y.1 = b then (1 : ℕ) else 0)]
        rw [← sum_filter,← card_eq_sum_ones]
        simpa using hcard {b}
card_eq_sum_ones
The cardinality of a finite set equals the sum of 1 over all of its elements.
sum_filter
Summing a function over elements satisfying a predicate equals summing the conditional expression (if the predicate holds then the function value else zero) over all elements.
Fintype.sum_sigma
A sum over a dependent pair type Σ x, y(x) can be rewritten as the iterated sum ∑ x, ∑ y, f(x, y).
Fintype.sum_ite_mem
The sum of an indicator function (if i ∈ s then f(i) else 0) over all elements of a finite type equals the sum of f(i) over the subset s.
sum_congr
Two finite sums are equal if their index sets are equal and their summands agree on every element of the index set.
mem_filter
An element belongs to a filtered set {x ∈ s | p(x)} if and only if it belongs to s and satisfies p.
mem_univ
Every element of a finite type belongs to the universal finset univ.
mem_image
An element y belongs to the image f(s) if and only if y = f(x) for some x ∈ s.
mem_biUnion
An element belongs to a union ⋃_{x ∈ s} t(x) if and only if it belongs to t(x) for some x ∈ s.
card_le_card
If s ⊆ t for finite sets, then the cardinality of s is at most the cardinality of t.
all_card_le_biUnion_card_iff_existsInjective'
Hall's Marriage Theorem: every subset of a finite index type has union of candidates at least as large as the subset if and only if there exists an injective system of distinct representatives.
bijective_of_finite
An injective map from a finite type to itself is bijective.
Equiv.ofBijective
A bijective function between types induces an equivalence (bijection).
card_eq_zero
A finite set has cardinality zero if and only if it is empty.
eq_empty_iff_forall_notMem
A set is empty if and only if it contains no elements.
sum_card_fiberwise_eq_card_filter
Summing the cardinalities of the fibers of a function over a target set equals the cardinality of the preimage of that target set.
filter_filter
Filtering a set successively by two predicates is equivalent to filtering once by their conjunction.
and_comm
Logical conjunction is commutative: p ∧ q ↔ q ∧ p.
e.sum_comp
Summing a function composed with an equivalence e over the domain equals summing the function directly over the codomain.

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

open Finsetopen scoped BigOperatorsset_option maxHeartbeats 4000000set_option maxRecDepth 10000theorem condorcet_integer_circulation_of_neighbor_mass    (m : ℕ) (R : Fin m → Fin m → Prop) [DecidableRel R] (w : Fin m → ℕ)    (hHall : ∀ S : Finset (Fin m),      (∑ a ∈ S, w a) ≤ ∑ b ∈ univ.filter (fun b => ∃ a ∈ S, R a b), w b) :    ∃ f : Fin m → Fin m → ℕ,      (∀ a b, ¬ R a b → f a b = 0) ∧      (∀ a, ∑ b, f a b = w a) ∧ (∀ b, ∑ a, f a b = w b) := by  classical  let V := Σ a : Fin m, Fin (w a)  have hcard (S : Finset (Fin m)) :      (univ.filter (fun x : V => x.1 ∈ S)).card = ∑ a ∈ S, w a := by    rw [card_eq_sum_ones,sum_filter]    change (∑ x : (Σ a : Fin m, Fin (w a)), if x.1 ∈ S then 1 else 0) = _    rw [Fintype.sum_sigma]    rw [← Fintype.sum_ite_mem S w]    apply sum_congr rfl    intro a ha    by_cases h : a ∈ S <;> simp [h]  let neighbors : V → Finset V := fun x => univ.filter (fun y => R x.1 y.1)  have hclones : ∀ B : Finset V, B.card ≤ (B.biUnion neighbors).card := by    intro B    let S := B.image Sigma.fst    let N := univ.filter (fun b => ∃ a ∈ S, R a b)    have hB : B ⊆ univ.filter (fun x : V => x.1 ∈ S) := by      intro x hx      exact mem_filter.mpr ⟨mem_univ _,mem_image.mpr ⟨x,hx,rfl⟩⟩    have hN : B.biUnion neighbors = univ.filter (fun y : V => y.1 ∈ N) := by      ext y      simp only [mem_biUnion,neighbors,mem_filter,mem_univ,true_and,N,S,mem_image]      constructor      · rintro ⟨x,hx,hxy⟩        exact ⟨x.1,⟨x,hx,rfl⟩,hxy⟩      · rintro ⟨a,⟨x,hx,rfl⟩,hay⟩        exact ⟨x,hx,hay⟩    calc      B.card ≤ (univ.filter (fun x : V => x.1 ∈ S)).card := card_le_card hB      _ = ∑ a ∈ S, w a := hcard S      _ ≤ ∑ a ∈ N, w a := hHall S      _ = (B.biUnion neighbors).card := by rw [hN,hcard]  obtain ⟨g,hginj,hg⟩ := (all_card_le_biUnion_card_iff_existsInjective' neighbors).mp hclones  have hgbij : Function.Bijective g := hginj.bijective_of_finite  let e : V ≃ V := Equiv.ofBijective g hgbij  let f : Fin m → Fin m → ℕ := fun a b =>    (univ.filter (fun x : V => x.1 = a ∧ (e x).1 = b)).card  refine ⟨f,?_,?_,?_⟩  · intro a b hab    apply card_eq_zero.mpr    apply eq_empty_iff_forall_notMem.mpr    intro x hx    obtain ⟨_,ha,hb⟩ := mem_filter.mp hx    have h := (mem_filter.mp (hg x)).2    change R x.1 (e x).1 at h    exact hab (ha ▸ hb ▸ h)  · intro a    have h := sum_card_fiberwise_eq_card_filter      (univ.filter (fun x : V => x.1 = a)) univ (fun x : V => (e x).1)    have heq : (∑ b, f a b) = (univ.filter (fun x : V => x.1 = a)).card := by      simpa [f,filter_filter] using h    rw [heq]    simpa using hcard {a}  · intro b    have h := sum_card_fiberwise_eq_card_filter      (univ.filter (fun x : V => (e x).1 = b)) univ (fun x : V => x.1)    have heq : (∑ a, f a b) = (univ.filter (fun x : V => (e x).1 = b)).card := by      simpa [f,filter_filter,and_comm] using h    rw [heq,card_eq_sum_ones,sum_filter]    rw [e.sum_comp (fun y : V => if y.1 = b then (1 : ℕ) else 0)]    rw [← sum_filter,← card_eq_sum_ones]    simpa using hcard {b}
See it in the graphDiscuss this resultChallenge it