AFTD Auto-Formalizing Theoretical Domains

condorcet_dimension_le_three_iff_acyclic_cover_closed_walk

theoremverified

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

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.

  1. 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`.

    lines 16–17

      classical
      constructor
  2. The 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.

    lines 18–20

    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)
  3. 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`).

    lines 21–25

    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⟩
  4. 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.

    line 26

        obtain ⟨l,hl,v,hclose,hedges,hlt⟩ := hwalk m n R U hn hroot hU
  5. The 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}|.

    lines 27–32

    uses sum_le_sum, mul_sum

        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]
  6. 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.

    line 33

        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).

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_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
See it in the graphDiscuss this resultChallenge it