condorcet_integer_circulation_of_neighbor_mass
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
- condorcet_strict_half_separator_iff_integer_circulationFor every finite directed relation, existence of nonnegative real weights putting every induced acyclic subset strictly below half their…
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.
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).
classical let V := Σ a : Fin m, Fin (w a)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.
uses
card_eq_sum_ones,sum_filter,Fintype.sum_sigma,Fintype.sum_ite_mem,sum_congrhave 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]
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.
uses
mem_filter,mem_univ,mem_image,mem_biUnion,card_le_cardlet 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]
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.
uses
all_card_le_biUnion_card_iff_existsInjective',bijective_of_finite,Equiv.ofBijectiveobtain ⟨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,?_,?_,?_⟩
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.
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)
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}.
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}
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}.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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}