condorcet_dimension_le_three_iff_acyclic_cover_closed_walk
The universal strict Condorcet bound three is equivalent to the following statement: on every finite S3 directed relation, every positive finite family of induced acyclic subsets admits a nonempty closed directed walk whose average membership count is strictly below half the family size. Walks may repeat vertices. This is an equivalent formulation, not a proof of the S3 walk-existence assertion.
Statement
theorem condorcet_dimension_le_three_iff_acyclic_cover_closed_walk : (∀ (n m : ℕ) (P : Fin n → Equiv.Perm (Fin m)), 0 < n → ∃ S : Finset (Fin m), S.card ≤ 3 ∧ is_condorcet_winning_set P S) ↔ (∀ (m n : ℕ) (R : Fin m → Fin m → Prop) (U : Fin n → Finset (Fin m)), 0 < n → (∀ J : Finset (Fin m), J.card ≤ 3 → ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b) → (∀ j, WellFounded (fun a b : {a : Fin m // a ∈ U j} => R a.val b.val)) → ∃ 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 3
- condorcet_strict_half_separator_acyclic_cover_closed_walkIf a finite relation has a nonnegative real strict-half acyclic separator, then every positive finite family of induced acyclic sets…
- condorcet_dimension_le_three_iff_acyclic_weight_separationThe following two universal statements are equivalent. First, every finite election with a positive number of voters and strict rankings…
- is_condorcet_winning_setWith n voters holding strict rankings of m candidates, S is a Condorcet winning set if for every candidate a ∉ S, strictly fewer than n/2…
The proof, explained
The theorem shows that the universal Condorcet dimension bound of 3 is equivalent to the assertion that on any finite S3 relation, every finite family of acyclic subsets admits a closed directed walk whose average membership in the family is strictly less than 1/2. The equivalence is mediated by vertex weight separation: Condorcet dimension at most 3 is known to be equivalent to the existence of a non-negative weighting strictly separating every acyclic set to less than half the total weight. For the forward direction, such a separating weight directly guarantees the light closed walk. For the reverse direction, linear programming duality shows that the absence of a separating weight would produce an acyclic half-cover, which would force every closed walk to have average membership at least 1/2, contradicting the walk hypothesis.
The equivalence is split into the forward and reverse implications under classical logic.
We enable classical reasoning (`classical`) and split the `↔` goal into two implications using `constructor`.
classical constructorThe Condorcet dimension bound of 3 implies that every S3 relation and family of acyclic subsets admits the required closed directed walk.
Assuming the Condorcet dimension bound (`hmain`), the forward direction of `condorcet_dimension_le_three_iff_acyclic_weight_separation.mp` provides a non-negative vertex weight strictly separating all acyclic subsets to less than half the total weight. Supplying this weight to `condorcet_strict_half_separator_acyclic_cover_closed_walk` produces a nonempty closed directed walk whose average membership in the acyclic family is strictly below 1/2.
uses
condorcet_strict_half_separator_acyclic_cover_closed_walk,condorcet_dimension_le_three_iff_acyclic_weight_separation.mp· intro hmain m n R U hn hroot hU exact condorcet_strict_half_separator_acyclic_cover_closed_walk m n hn R U hU (condorcet_dimension_le_three_iff_acyclic_weight_separation.mp hmain m R hroot)
To deduce the Condorcet dimension bound from the walk property, it suffices to derive a contradiction from the existence of an acyclic half-cover.
Assuming the walk hypothesis (`hwalk`), by `condorcet_dimension_le_three_iff_acyclic_weight_separation.mpr` it suffices to construct a strictly separating weight function for any S3 relation R. By linear programming duality (`condorcet_half_cover_acyclic_half_cover_duality`), such a weight exists if and only if no acyclic half-cover exists. We assume for contradiction that there exists a positive number n of acyclic subsets U_j covering every vertex at least n/2 times (`hhalf`).
uses
condorcet_dimension_le_three_iff_acyclic_weight_separation.mpr,condorcet_half_cover_acyclic_half_cover_duality· intro hwalk apply condorcet_dimension_le_three_iff_acyclic_weight_separation.mpr intro m R hroot apply (condorcet_half_cover_acyclic_half_cover_duality m R).mp rintro ⟨n,U,hn,hU,hhalf⟩
The walk hypothesis yields a closed directed walk whose total membership count is strictly less than l * n / 2.
Applying the assumed walk property `hwalk` to the relation R and the acyclic family U produces a closed directed walk v of length l > 0 along edges of R such that 2 * ∑_{i=0}^{l-1} |{j | v_i ∈ U_j}| < l * n.
obtain ⟨l,hl,v,hclose,hedges,hlt⟩ := hwalk m n R U hn hroot hUThe half-cover condition implies that the total membership count along the walk is at least l * n / 2.
Because each vertex along the walk is covered at least n/2 times (n ≤ 2 * |{j | v_i ∈ U_j}| by `hhalf`), summing this bound over the l steps of the walk (`sum_le_sum`) and factoring out 2 via distributivity (`mul_sum`) yields l * n ≤ 2 * ∑_{i=0}^{l-1} |{j | v_i ∈ U_j}|.
uses
sum_le_sum,mul_sumhave hle : l*n ≤ 2 * (∑ i ∈ range l, (univ.filter fun j => v i ∈ U j).card) := by calc l*n = ∑ i ∈ range l, n := by simp _ ≤ ∑ i ∈ range l, 2 * (univ.filter fun j => v i ∈ U j).card := sum_le_sum (fun i hi => hhalf (v i)) _ = _ := by rw [mul_sum]
The upper and lower bounds on the total membership count contradict each other, concluding the proof. automation
Linear integer arithmetic (`omega`) detects the contradiction between 2 * ∑_{i=0}^{l-1} |{j | v_i ∈ U_j}| < l * n (`hlt`) and l * n ≤ 2 * ∑_{i=0}^{l-1} |{j | v_i ∈ U_j}| (`hle`), closing the goal with False.
omega
condorcet_strict_half_separator_acyclic_cover_closed_walk- Given a finite relation R on m vertices, a family of n > 0 acyclic subsets, and a non-negative vertex weighting strictly separating each acyclic set to less than half the total weight, there exists a nonempty closed directed walk whose vertices belong on average to strictly less than half the sets in the family.
condorcet_dimension_le_three_iff_acyclic_weight_separation.mp- If every profile of linear orders has a Condorcet winning set of size at most 3, then every S3 relation (every subset of size at most 3 has an external dominator) admits a non-negative vertex weighting giving each acyclic subset strictly less than half the total weight.
condorcet_dimension_le_three_iff_acyclic_weight_separation.mpr- If every S3 relation admits a non-negative vertex weighting strictly separating every acyclic subset to less than half the total weight, then the universal Condorcet dimension is at most 3.
condorcet_half_cover_acyclic_half_cover_duality- A finite relation admits a non-negative vertex weight strictly separating all acyclic subsets to less than half the total weight if and only if there does not exist an acyclic half-cover (a finite collection of acyclic subsets covering every vertex at least half the time).
sum_le_sum- If f(i) ≤ g(i) for all elements i in a finite set s, then ∑_{i ∈ s} f(i) ≤ ∑_{i ∈ s} g(i).
mul_sum- Multiplication distributes over finite sums: a * ∑_{i ∈ s} f(i) = ∑_{i ∈ s} a * f(i).
- The proof is a bridge between two deeper structural theorems in the development: `condorcet_dimension_le_three_iff_acyclic_weight_separation`, which relates Condorcet dimension to the existence of strictly separating vertex weights, and `condorcet_half_cover_acyclic_half_cover_duality`, a Farkas-type duality theorem between separating weights and acyclic half-covers.
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_dimension_le_three_iff_acyclic_cover_closed_walk : (∀ (n m : ℕ) (P : Fin n → Equiv.Perm (Fin m)), 0 < n → ∃ S : Finset (Fin m), S.card ≤ 3 ∧ is_condorcet_winning_set P S) ↔ (∀ (m n : ℕ) (R : Fin m → Fin m → Prop) (U : Fin n → Finset (Fin m)), 0 < n → (∀ J : Finset (Fin m), J.card ≤ 3 → ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b) → (∀ j, WellFounded (fun a b : {a : Fin m // a ∈ U j} => R a.val b.val)) → ∃ 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 constructor · intro hmain m n R U hn hroot hU exact condorcet_strict_half_separator_acyclic_cover_closed_walk m n hn R U hU (condorcet_dimension_le_three_iff_acyclic_weight_separation.mp hmain m R hroot) · intro hwalk apply condorcet_dimension_le_three_iff_acyclic_weight_separation.mpr intro m R hroot apply (condorcet_half_cover_acyclic_half_cover_duality m R).mp rintro ⟨n,U,hn,hU,hhalf⟩ obtain ⟨l,hl,v,hclose,hedges,hlt⟩ := hwalk m n R U hn hroot hU have hle : l*n ≤ 2 * (∑ i ∈ range l, (univ.filter fun j => v i ∈ U j).card) := by calc l*n = ∑ i ∈ range l, n := by simp _ ≤ ∑ i ∈ range l, 2 * (univ.filter fun j => v i ∈ U j).card := sum_le_sum (fun i hi => hhalf (v i)) _ = _ := by rw [mul_sum] omega