condorcet_strict_half_separator_acyclic_cover_closed_walk
If a finite relation has a nonnegative real strict-half acyclic separator, then every positive finite family of induced acyclic sets admits a nonempty closed directed walk whose total membership count in the family, doubled, is strictly less than walk length times family size. Vertices may repeat. No S3 assumption is used.
Statement
theorem condorcet_strict_half_separator_acyclic_cover_closed_walk (m n : ℕ) (hn : 0 < n) (R : Fin m → Fin m → Prop) (U : Fin n → Finset (Fin m)) (hU : ∀ v, WellFounded (fun a b : {a : Fin m // a ∈ U v} => R a.val b.val)) (hsep : ∃ w : Fin m → ℝ, (∀ a, 0 ≤ w a) ∧ ∀ A : Finset (Fin m), WellFounded (fun a b : {a : Fin m // a ∈ A} => R a.val b.val) → 2 * (∑ a ∈ A, w a) < ∑ a, w a) : ∃ l : ℕ, 0 < l ∧ ∃ v : ℕ → Fin m, v l = v 0 ∧ (∀ i < l, R (v i) (v (i+1))) ∧ 2 * (∑ i ∈ range l, (univ.filter fun j => v i ∈ U j).card) < l*n
- Source
- IN-380, OP-19 campaign session8, 2026-10-30. Supporting reduction from the proved strict-half circulation bridge. Scratch ClosedWalk.lean passed trusted-axiom checking. Standard finite matching and orbit averaging; no research novelty or new election bound is claimed.
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- condorcet_finite_strict_separator_integer_weightsFor any family C of subsets of a finite vertex set, if nonnegative real weights put every member of C strictly below half the total…
- condorcet_integer_acyclic_separator_neighbor_massIf a finite directed relation has a nonnegative integer strict-half separator of its induced acyclic sets, it has such a separator w for…
- condorcet_integer_neighbor_mass_clone_permutationFinite weighted neighborhood inequalities imply an arrow-supported permutation on the finite set containing w(a) clones of every vertex a.…
- condorcet_permutation_negative_closed_walkFor a permutation of a finite type and real costs with strictly negative total, some point has a nonempty periodic orbit segment of…
- Used by 1
- condorcet_dimension_le_three_iff_acyclic_cover_closed_walkThe universal strict Condorcet bound three is equivalent to the following statement: on every finite S3 directed relation, every positive…
The proof, explained
The proof uses a vertex-cloning technique combined with Hall's marriage theorem and cycle decomposition of permutations. First, the real strict-half separator is discretized to integer weights satisfying Hall's condition on out-neighborhoods, yielding a permutation e on a cloned vertex set V whose steps follow edges of the relation R. Summing the strict separator inequality across the family of acyclic sets shows that the average cost c(x) = 2*z(x.1) - n across all cloned vertices is strictly negative. By permutation cycle decomposition, e must have a cycle with strictly negative total cost, and projecting this cycle back to the original graph gives the desired closed directed walk.
There exist integer weights w satisfying both the strict-half acyclic separator condition and Hall's neighborhood condition, yielding a permutation e on the cloned vertices that follows directed edges of R.
We unpack the given nonnegative real strict-half separator w₀. By condorcet_finite_strict_separator_integer_weights, there exist integer weights w₁ satisfying the same strict-half property for all acyclic induced subgraphs. Applying condorcet_integer_acyclic_separator_neighbor_mass, we obtain integer weights w that maintain the strict-half property for acyclic sets while satisfying Hall's condition that any set's total weight is bounded by that of its out-neighborhood. Then condorcet_integer_neighbor_mass_clone_permutation produces a permutation e of the cloned vertex set V = Σ a, Fin (w a) such that for every clone x, R x.1 (e x).1 holds.
uses
condorcet_finite_strict_separator_integer_weights,condorcet_integer_acyclic_separator_neighbor_mass,condorcet_integer_neighbor_mass_clone_permutationclassical obtain ⟨w₀,hw₀,hsep₀⟩ := hsep obtain ⟨w₁,hw₁⟩ := condorcet_finite_strict_separator_integer_weights m (fun A => WellFounded (fun a b : {a : Fin m // a ∈ A} => R a.val b.val)) w₀ hw₀ hsep₀ obtain ⟨w,hw,hHall⟩ := condorcet_integer_acyclic_separator_neighbor_mass m R w₁ hw₁ obtain ⟨e,he⟩ := condorcet_integer_neighbor_mass_clone_permutation m R w hHall
Define the cloned vertex type V, the family membership counts z, and the vertex cost function c.
We define V as the type of pairs (a, k) where a is an original vertex and k < w(a), effectively duplicating each vertex a by its integer weight w(a). For each vertex a, z(a) is defined as the number of acyclic sets U_j containing a. Each cloned vertex x in V is assigned cost c(x) = 2*z(x.1) - n.
let V := Σ a : Fin m, Fin (w a) let z : Fin m → ℝ := fun a => ((univ.filter fun j => a ∈ U j).card : ℝ) let c : V → ℝ := fun x => 2*z x.1 - n
The sum over j of the doubled weights of U_j is strictly less than the total weight summed n times: ∑ j, 2 * ∑ a ∈ U j, w a < ∑ j, ∑ a, w a.
By hypothesis, each set U_j induces an acyclic subgraph under R. Since w is a strict-half separator, 2 * ∑ a ∈ U_j, w a < ∑ a, w a holds for each j. Since n > 0, the family is nonempty (witnessed by index 0). Summing these strict inequalities over all j in Fin n using sum_lt_sum yields a strict inequality between the sums.
uses
sum_lt_sum,mem_univhave hstrict : (∑ j : Fin n, 2 * (∑ a ∈ U j, (w a : ℝ))) < ∑ _j : Fin n, ∑ a, (w a : ℝ) := by apply sum_lt_sum · intro j hj exact_mod_cast (hw (U j) (hU j)).le · refine ⟨⟨0,hn⟩,mem_univ _,?_⟩ exact_mod_cast hw (U ⟨0,hn⟩) (hU ⟨0,hn⟩)
The weighted sum of membership counts satisfies ∑ a, w a * (2 * z a) < n * ∑ a, w a.
We interchange the order of summation. Each sum over U_j is rewritten via Fintype.sum_ite_mem using an indicator function. Commuting the sums with sum_comm and factoring out w(a), the inner sum over j counts the number of sets U_j containing a, which is by definition z(a). Substituting this equality into the previous step and simplifying the constant outer sum over Fin n yields ∑ a, w a * (2 * z a) < n * ∑ a, w a.
uses
sum_congr,Fintype.sum_ite_mem,mul_sum,sum_comm,sum_filter,sum_const,card_univ,Fintype.card_fin,nsmul_eq_mulhave hswap : (∑ j : Fin n, 2 * (∑ a ∈ U j, (w a : ℝ))) = ∑ a, (w a : ℝ) * (2*z a) := by have hconvert : (∑ j : Fin n, ∑ a ∈ U j, (w a : ℝ)) = ∑ j : Fin n, ∑ a : Fin m, if a ∈ U j then (w a : ℝ) else 0 := by apply sum_congr rfl intro j hj exact (Fintype.sum_ite_mem (U j) (fun a => (w a : ℝ))).symm rw [← mul_sum,hconvert,sum_comm,mul_sum] apply sum_congr rfl intro a ha simp [z,← sum_filter] ring rw [hswap] at hstrict simp only [sum_const,card_univ,Fintype.card_fin,nsmul_eq_mul] at hstrict
The total cost over all cloned vertices is strictly negative: ∑ x ∈ V, c x < 0.
Using Fintype.sum_sigma, the sum over V splits into an outer sum over vertices a and an inner sum over the w(a) copies of a. Since c(x) = 2*z(x.1) - n depends only on the original vertex, summing over the fiber multiplies the cost by w(a). Distributing and regrouping shows ∑ x ∈ V, c x = ∑ a, w a * (2 * z a) - n * ∑ a, w a. Since the first term is strictly smaller than the second, linear arithmetic concludes that the total sum is strictly negative.
uses
Fintype.sum_sigma,sum_const,card_univ,Fintype.card_fin,nsmul_eq_mul,mul_sub,sum_sub_distrib,sum_mulhave hc : (∑ x : V, c x) < 0 := by have heq : (∑ x : V, c x) = (∑ a, (w a : ℝ) * (2*z a)) - (n : ℝ) * ∑ a, (w a : ℝ) := by rw [Fintype.sum_sigma] simp only [c,sum_const,card_univ,Fintype.card_fin,nsmul_eq_mul,mul_sub] rw [sum_sub_distrib,← sum_mul] ring rw [heq] linarith
There exists a cycle of the permutation e of positive length l starting at some x ∈ V with strictly negative total cost: (e^l) x = x and ∑ i ∈ range l, c ((e^i) x) < 0.
By condorcet_permutation_negative_closed_walk, whenever a cost function on a finite domain has a strictly negative sum, any permutation on that domain must contain a cycle whose orbit has strictly negative total cost.
uses
condorcet_permutation_negative_closed_walkobtain ⟨l,hl,x,hclose,hneg⟩ := condorcet_permutation_negative_closed_walk e c hcThe vertex projection of the cycle v(i) = ((e^i) x).1 forms a closed walk of length l > 0 with v(l) = v(0).
We define the walk v : ℕ → Fin m by projecting each cloned vertex (e^i) x to its original vertex in Fin m. Since (e^l) x = x and (e^0) x = x, projecting with Sigma.fst gives v(l) = v(0).
uses
pow_zero,Equiv.Perm.one_apply,congrArg,Sigma.fstlet v : ℕ → Fin m := fun i => ((e^i) x).1 refine ⟨l,hl,v,?_,?_,?_⟩ · simpa only [v,pow_zero,Equiv.Perm.one_apply] using congrArg Sigma.fst hclose
For every step i < l, R (v i) (v (i+1)) holds.
For any step i, (e^(i+1)) x = e ((e^i) x). The clone permutation e satisfies R y.1 (e y).1 for every cloned vertex y. Applying this to y = (e^i) x shows that R (v i) (v (i+1)) holds along every step of the walk.
uses
pow_succ',Equiv.Perm.mul_apply· intro i hi have h := he ((e^i) x) simpa only [v,pow_succ',Equiv.Perm.mul_apply] using h
The walk satisfies the strict count bound: 2 * (∑ i ∈ range l, card {j | v i ∈ U j}) < l * n.
The negative-cost condition along the cycle states that ∑ i ∈ range l, (2 * z(v i) - n) < 0. Distributing the sum gives 2 * (∑ i ∈ range l, z(v i)) - l * n < 0, so 2 * (∑ i ∈ range l, z(v i)) < l * n. Unfolding the definition of z and casting from ℝ to ℕ establishes the desired inequality.
uses
sum_sub_distrib,mul_sum,sum_const,card_range,nsmul_eq_mul· have hlt : 2 * (∑ i ∈ range l, (z (v i))) < (l : ℝ)*n := by change (∑ i ∈ range l, (2*z (v i) - n)) < 0 at hneg simp only [sum_sub_distrib,← mul_sum,sum_const,card_range,nsmul_eq_mul] at hneg linarith dsimp only [z] at hlt exact_mod_cast hlt
condorcet_finite_strict_separator_integer_weights- A finite system with a nonnegative real strict-half separator also admits an integer-valued strict-half separator.
condorcet_integer_acyclic_separator_neighbor_mass- An integer strict-half acyclic separator can be modified to another integer acyclic separator whose weights satisfy Hall's neighborhood condition: the total weight of any subset is at most that of its out-neighborhood.
condorcet_integer_neighbor_mass_clone_permutation- If integer weights satisfy Hall's neighborhood condition, there is a permutation of the cloned vertex set where each copy maps to a copy of an out-neighbor.
sum_lt_sum- A sum of terms that are each bounded by another, with at least one strict inequality, is strictly less than the other sum.
mem_univ- Every element of a finite type belongs to the universal finset univ.
sum_congr- Two sums over equal finsets with pointwise equal summands are equal.
Fintype.sum_ite_mem- Summing over the whole universe with an indicator function for a subset equals the sum over that subset.
mul_sum- A constant factor outside a finite sum distributes over all terms.
sum_comm- The order of summation in a double finite sum can be interchanged.
sum_filter- Summing over elements filtered by a predicate equals summing with an if-then-else indicator over the original set.
sum_const- Summing a constant over a finset yields the cardinality of the finset times the constant.
card_univ- The cardinality of univ for a finite type equals the cardinality of the type.
Fintype.card_fin- The cardinality of Fin n is n.
nsmul_eq_mul- Natural number scalar multiplication equals algebraic multiplication by the integer or real cast.
Fintype.sum_sigma- A sum over a dependent sum (sigma type) can be evaluated as an iterated sum over base and fiber.
mul_sub- Multiplication distributes over subtraction from the left.
sum_sub_distrib- The sum of termwise differences is the difference of the sums.
sum_mul- A constant factor after a finite sum distributes over all terms.
condorcet_permutation_negative_closed_walk- If the sum of a cost function over a finite set is strictly negative, any permutation of that set contains a cycle whose total cost along the orbit is strictly negative.
pow_zero- The zeroth power of an element in a group or monoid is the identity.
Equiv.Perm.one_apply- The identity permutation maps every element to itself.
congrArg- Applying a function to equal arguments produces equal results.
Sigma.fst- The projection function extracting the first component of a dependent pair.
pow_succ'- The (n+1)-th power of a monoid element is the element multiplied by its n-th power.
Equiv.Perm.mul_apply- The composition of permutations evaluated at an element is the application of the first to the result of the second.
card_range- The cardinality of the range {0, ..., n - 1} is n.
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_strict_half_separator_acyclic_cover_closed_walk (m n : ℕ) (hn : 0 < n) (R : Fin m → Fin m → Prop) (U : Fin n → Finset (Fin m)) (hU : ∀ v, WellFounded (fun a b : {a : Fin m // a ∈ U v} => R a.val b.val)) (hsep : ∃ w : Fin m → ℝ, (∀ a, 0 ≤ w a) ∧ ∀ A : Finset (Fin m), WellFounded (fun a b : {a : Fin m // a ∈ A} => R a.val b.val) → 2 * (∑ a ∈ A, w a) < ∑ a, w a) : ∃ l : ℕ, 0 < l ∧ ∃ v : ℕ → Fin m, v l = v 0 ∧ (∀ i < l, R (v i) (v (i+1))) ∧ 2 * (∑ i ∈ range l, (univ.filter fun j => v i ∈ U j).card) < l*n := by classical obtain ⟨w₀,hw₀,hsep₀⟩ := hsep obtain ⟨w₁,hw₁⟩ := condorcet_finite_strict_separator_integer_weights m (fun A => WellFounded (fun a b : {a : Fin m // a ∈ A} => R a.val b.val)) w₀ hw₀ hsep₀ obtain ⟨w,hw,hHall⟩ := condorcet_integer_acyclic_separator_neighbor_mass m R w₁ hw₁ obtain ⟨e,he⟩ := condorcet_integer_neighbor_mass_clone_permutation m R w hHall let V := Σ a : Fin m, Fin (w a) let z : Fin m → ℝ := fun a => ((univ.filter fun j => a ∈ U j).card : ℝ) let c : V → ℝ := fun x => 2*z x.1 - n have hstrict : (∑ j : Fin n, 2 * (∑ a ∈ U j, (w a : ℝ))) < ∑ _j : Fin n, ∑ a, (w a : ℝ) := by apply sum_lt_sum · intro j hj exact_mod_cast (hw (U j) (hU j)).le · refine ⟨⟨0,hn⟩,mem_univ _,?_⟩ exact_mod_cast hw (U ⟨0,hn⟩) (hU ⟨0,hn⟩) have hswap : (∑ j : Fin n, 2 * (∑ a ∈ U j, (w a : ℝ))) = ∑ a, (w a : ℝ) * (2*z a) := by have hconvert : (∑ j : Fin n, ∑ a ∈ U j, (w a : ℝ)) = ∑ j : Fin n, ∑ a : Fin m, if a ∈ U j then (w a : ℝ) else 0 := by apply sum_congr rfl intro j hj exact (Fintype.sum_ite_mem (U j) (fun a => (w a : ℝ))).symm rw [← mul_sum,hconvert,sum_comm,mul_sum] apply sum_congr rfl intro a ha simp [z,← sum_filter] ring rw [hswap] at hstrict simp only [sum_const,card_univ,Fintype.card_fin,nsmul_eq_mul] at hstrict have hc : (∑ x : V, c x) < 0 := by have heq : (∑ x : V, c x) = (∑ a, (w a : ℝ) * (2*z a)) - (n : ℝ) * ∑ a, (w a : ℝ) := by rw [Fintype.sum_sigma] simp only [c,sum_const,card_univ,Fintype.card_fin,nsmul_eq_mul,mul_sub] rw [sum_sub_distrib,← sum_mul] ring rw [heq] linarith obtain ⟨l,hl,x,hclose,hneg⟩ := condorcet_permutation_negative_closed_walk e c hc let v : ℕ → Fin m := fun i => ((e^i) x).1 refine ⟨l,hl,v,?_,?_,?_⟩ · simpa only [v,pow_zero,Equiv.Perm.one_apply] using congrArg Sigma.fst hclose · intro i hi have h := he ((e^i) x) simpa only [v,pow_succ',Equiv.Perm.mul_apply] using h · have hlt : 2 * (∑ i ∈ range l, (z (v i))) < (l : ℝ)*n := by change (∑ i ∈ range l, (2*z (v i) - n)) < 0 at hneg simp only [sum_sub_distrib,← mul_sum,sum_const,card_range,nsmul_eq_mul] at hneg linarith dsimp only [z] at hlt exact_mod_cast hlt