AFTD Auto-Formalizing Theoretical Domains

condorcet_balanced_top_implies_six_le_candidates

theoremverified

If every three-candidate set contains the top choice of at most half of the voters (and there is at least one voter and at least four candidates), then the election has at least six candidates: the balanced regime is impossible below six candidates.

Statement

theorem condorcet_balanced_top_implies_six_le_candidates (n m : ℕ) (P : Fin n → Equiv.Perm (Fin m))
    (hn : 0 < n) (hm : 4 ≤ m)
    (hbal : ∀ S : Finset (Fin m), S.card = 3 →
      2 * (Finset.univ.filter fun v => (P v).symm ⟨0, by omega⟩ ∈ S).card ≤ n) :
    6 ≤ m
Source
step towards condorcet_dimension_le_three
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

The proof proceeds by double counting and contradiction. The balanced condition implies that every 3-candidate subset contains the top choice of at most half of the voters, giving an upper bound on the sum of the voter counts over all triples. Conversely, counting by voter reveals that each voter's top choice appears in exactly ((m - 1).choose 2) triples, so the sum equals n * ((m - 1).choose 2). Combining the two gives the inequality 2 * ((m - 1).choose 2) ≤ m.choose 3, which fails by direct arithmetic computation when m = 4 or m = 5, forcing m ≥ 6.

  1. Candidate 0 is valid, and we define each voter's top choice, the count of voters with top choice in a set S, and the collection T of all 3-candidate subsets.

    In both the theorem hypothesis hbal (line 5) and the proof (line 7), candidate 0 is verified to be in Fin m using linear arithmetic (omega) since m ≥ 4 > 0. For each voter v, top(v) is defined as (P v)⁻¹(0). For any candidate subset S, cnt(S) counts the voters whose top choice is in S. Finally, T is defined as the set of all 3-candidate subsets of the candidates.

    lines 5–9

          2 * (Finset.univ.filter fun v => (P v).symm ⟨0, by omega⟩ ∈ S).card ≤ n) :
        6 ≤ m := by
      let top : Fin n → Fin m := fun v => (P v).symm ⟨0, by omega⟩
      let cnt : Finset (Fin m) → ℕ := fun S => (Finset.univ.filter fun v => top v ∈ S).card
      let T : Finset (Finset (Fin m)) := (Finset.univ : Finset (Fin m)).powersetCard 3
  2. For each voter v, exactly ((m - 1).choose 2) triples in T contain top(v).

    Any 3-element subset containing top(v) is formed by choosing 2 additional candidates from the remaining m - 1 candidates. This is established by specializing Finset.card_filter_powersetCard_subset to the singleton {top(v)} within the universe of m candidates, rewritten via Finset.singleton_subset_iff.

    lines 10–12

    uses Finset.card_filter_powersetCard_subset, Finset.singleton_subset_iff

      have hfiber (v : Fin n) : (T.filter fun S => top v ∈ S).card = (m - 1).choose 2 := by
        have h := Finset.card_filter_powersetCard_subset ({top v} : Finset (Fin m)) (Finset.univ : Finset (Fin m)) 3 (by simp) (by simp)
        simpa [T, Finset.singleton_subset_iff] using h
  3. The sum of cnt(S) over all triples S ∈ T equals n * ((m - 1).choose 2).

    We count voter-triple pairs in two ways. Express cnt(S) as a sum of 0-1 indicators via Finset.card_filter, then exchange the sums over triples S ∈ T and voters v using Finset.sum_comm. For each voter, the inner sum over S ∈ T counts triples containing top(v) via Finset.sum_boole, which equals ((m - 1).choose 2) by hfiber. Summing this constant over all n voters yields n * ((m - 1).choose 2).

    lines 13–26

    uses Finset.card_filter, Finset.sum_comm, Finset.sum_boole

      have hsum : ∑ S ∈ T, cnt S = n * ((m - 1).choose 2) := by
        calc
          ∑ S ∈ T, cnt S
              = ∑ S ∈ T, ∑ v ∈ (Finset.univ : Finset (Fin n)), if top v ∈ S then 1 else 0 := by
                  simp only [cnt, Finset.card_filter]
          _ = ∑ v ∈ (Finset.univ : Finset (Fin n)), ∑ S ∈ T, if top v ∈ S then 1 else 0 := by
                  rw [Finset.sum_comm]
          _ = ∑ v ∈ (Finset.univ : Finset (Fin n)), (T.filter fun S => top v ∈ S).card := by
                  simp only [Finset.sum_boole]
                  rfl
          _ = ∑ v ∈ (Finset.univ : Finset (Fin n)), (m - 1).choose 2 := by
                  simp [hfiber]
          _ = n * ((m - 1).choose 2) := by
                  simp
  4. 2 * ∑ S ∈ T, cnt(S) ≤ n * |T|.

    Distribute the factor of 2 inside the sum over T using Finset.mul_sum. Since each S ∈ T has cardinality 3, the balanced assumption hbal guarantees that 2 * cnt(S) ≤ n for every triple S. Summing these inequalities with Finset.sum_le_sum gives at most |T| * n, which equals n * |T| by Nat.mul_comm.

    lines 27–37

    uses Finset.mul_sum, Finset.sum_le_sum, Nat.mul_comm

      have hle : 2 * ∑ S ∈ T, cnt S ≤ n * T.card := by
        calc
          2 * ∑ S ∈ T, cnt S = ∑ S ∈ T, 2 * cnt S := by
            rw [Finset.mul_sum]
          _ ≤ ∑ S ∈ T, n := by
            apply Finset.sum_le_sum
            intro S hS
            have hScard : S.card = 3 := by simpa [T] using hS
            exact hbal S hScard
          _ = T.card * n := by simp
          _ = n * T.card := by rw [Nat.mul_comm]
  5. The total number of triples is |T| = m.choose 3.

    The number of 3-element subsets of an m-element set is given directly by Finset.card_powersetCard as m.choose 3.

    lines 38–39

    uses Finset.card_powersetCard

      have hcardT : T.card = m.choose 3 := by
        simp [T, Finset.card_powersetCard]
  6. 2 * (n * ((m - 1).choose 2)) ≤ n * (m.choose 3).

    Substitute the double-counting formula ∑ S ∈ T, cnt(S) = n * ((m - 1).choose 2) and the cardinality |T| = m.choose 3 into the upper bound 2 * ∑ S ∈ T, cnt(S) ≤ n * |T|.

    lines 40–44

      have hineq : 2 * (n * ((m - 1).choose 2)) ≤ n * m.choose 3 := by
        calc
          2 * (n * ((m - 1).choose 2)) = 2 * ∑ S ∈ T, cnt S := by rw [hsum]
          _ ≤ n * T.card := hle
          _ = n * m.choose 3 := by rw [hcardT]
  7. 2 * ((m - 1).choose 2) ≤ m.choose 3.

    Because the number of voters n is strictly positive (hn), we can cancel the factor of n from the left of the inequality 2 * (n * ((m - 1).choose 2)) ≤ n * (m.choose 3) using Nat.le_of_mul_le_mul_left.

    lines 45–49

    uses Nat.le_of_mul_le_mul_left

      have hchoose : 2 * ((m - 1).choose 2) ≤ m.choose 3 := by
        apply Nat.le_of_mul_le_mul_left _ hn
        calc
          n * (2 * ((m - 1).choose 2)) = 2 * (n * ((m - 1).choose 2)) := by ring
          _ ≤ n * m.choose 3 := hineq
  8. 6 ≤ m. automation

    Suppose for contradiction that m < 6. Since m ≥ 4, the only remaining possibilities are m = 4 and m = 5. In both cases, the inequality 2 * ((m - 1).choose 2) ≤ m.choose 3 is violated: for m = 4 it gives 6 ≤ 4, and for m = 5 it gives 12 ≤ 10. Evaluating the binomial coefficients (Nat.choose) closes each case and produces a contradiction.

    lines 50–52

    uses Nat.choose

      by_contra h6
      have hmlt : m < 6 := by omega
      interval_cases m <;> norm_num [Nat.choose] at hchoose
Finset.card_filter_powersetCard_subset
The number of n-element subsets of t containing a given subset s ⊆ t is ((|t| - |s|).choose (n - |s|)).
Finset.singleton_subset_iff
A singleton set {a} is a subset of s if and only if a ∈ s.
Finset.card_filter
The cardinality of a filtered subset equals the sum of its boolean indicator values over the whole set.
Finset.sum_comm
Swapping the order of summation in a finite double sum does not change the result.
Finset.sum_boole
The sum of an indicator condition over a finite set equals the cardinality of the subset satisfying the condition.
Finset.mul_sum
A scalar factor distributes over a finite sum: a * ∑ x ∈ s, f x = ∑ x ∈ s, a * f x.
Finset.sum_le_sum
If f(i) ≤ g(i) for all i in a finite set s, then ∑ i ∈ s, f(i) ≤ ∑ i ∈ s, g(i).
Nat.mul_comm
Multiplication of natural numbers is commutative: n * m = m * n.
Finset.card_powersetCard
The number of subsets of size n of a finite set s is (|s|.choose n).
Nat.le_of_mul_le_mul_left
A positive multiplier c can be cancelled from the left of an inequality: c * a ≤ c * b implies a ≤ b when c > 0.
Nat.choose
The binomial coefficient function on natural numbers.

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

/-- The balanced case of the Condorcet-dimension problem cannot occur with at most five candidates. -/theorem condorcet_balanced_top_implies_six_le_candidates (n m : ℕ) (P : Fin n → Equiv.Perm (Fin m))    (hn : 0 < n) (hm : 4 ≤ m)    (hbal : ∀ S : Finset (Fin m), S.card = 3 →      2 * (Finset.univ.filter fun v => (P v).symm ⟨0, by omega⟩ ∈ S).card ≤ n) :    6 ≤ m := by  let top : Fin n → Fin m := fun v => (P v).symm ⟨0, by omega⟩  let cnt : Finset (Fin m) → ℕ := fun S => (Finset.univ.filter fun v => top v ∈ S).card  let T : Finset (Finset (Fin m)) := (Finset.univ : Finset (Fin m)).powersetCard 3  have hfiber (v : Fin n) : (T.filter fun S => top v ∈ S).card = (m - 1).choose 2 := by    have h := Finset.card_filter_powersetCard_subset ({top v} : Finset (Fin m)) (Finset.univ : Finset (Fin m)) 3 (by simp) (by simp)    simpa [T, Finset.singleton_subset_iff] using h  have hsum : ∑ S ∈ T, cnt S = n * ((m - 1).choose 2) := by    calc      ∑ S ∈ T, cnt S          = ∑ S ∈ T, ∑ v ∈ (Finset.univ : Finset (Fin n)), if top v ∈ S then 1 else 0 := by              simp only [cnt, Finset.card_filter]      _ = ∑ v ∈ (Finset.univ : Finset (Fin n)), ∑ S ∈ T, if top v ∈ S then 1 else 0 := by              rw [Finset.sum_comm]      _ = ∑ v ∈ (Finset.univ : Finset (Fin n)), (T.filter fun S => top v ∈ S).card := by              simp only [Finset.sum_boole]              rfl      _ = ∑ v ∈ (Finset.univ : Finset (Fin n)), (m - 1).choose 2 := by              simp [hfiber]      _ = n * ((m - 1).choose 2) := by              simp  have hle : 2 * ∑ S ∈ T, cnt S ≤ n * T.card := by    calc      2 * ∑ S ∈ T, cnt S = ∑ S ∈ T, 2 * cnt S := by        rw [Finset.mul_sum]      _ ≤ ∑ S ∈ T, n := by        apply Finset.sum_le_sum        intro S hS        have hScard : S.card = 3 := by simpa [T] using hS        exact hbal S hScard      _ = T.card * n := by simp      _ = n * T.card := by rw [Nat.mul_comm]  have hcardT : T.card = m.choose 3 := by    simp [T, Finset.card_powersetCard]  have hineq : 2 * (n * ((m - 1).choose 2)) ≤ n * m.choose 3 := by    calc      2 * (n * ((m - 1).choose 2)) = 2 * ∑ S ∈ T, cnt S := by rw [hsum]      _ ≤ n * T.card := hle      _ = n * m.choose 3 := by rw [hcardT]  have hchoose : 2 * ((m - 1).choose 2) ≤ m.choose 3 := by    apply Nat.le_of_mul_le_mul_left _ hn    calc      n * (2 * ((m - 1).choose 2)) = 2 * (n * ((m - 1).choose 2)) := by ring      _ ≤ n * m.choose 3 := hineq  by_contra h6  have hmlt : m < 6 := by omega  interval_cases m <;> norm_num [Nat.choose] at hchoose
See it in the graphDiscuss this resultChallenge it