AFTD Auto-Formalizing Theoretical Domains

condorcet_polynomial_potential_dual_bound

theoremverified

Let a finite signed subset polynomial be a sum of monomials indexed by a specified finite support. Suppose weighted rooted removal sets have the same natural incidence K on every supported monomial, and cover every selected challenger claim at least B times. If the polynomial satisfies all weighted local removal inequalities, B times the total challenger weight is at most K times its full-set value. This is an abstract certificate verifier, not a winning-set existence statement.

Statement

theorem condorcet_polynomial_potential_dual_bound
    (C I J : Type*) [Fintype C] [DecidableEq C]
    [Fintype I] [Fintype J]
    (M : Finset (Finset C)) (c : Finset C → ℤ)
    (H : Finset C → ℤ)
    (hform : ∀ A, H A = ∑ T ∈ M, if T ⊆ A then c T else 0)
    (S : I → Finset C) (f : I → C) (w : I → ℕ)
    (A : J → Finset C) (a : J → C) (L : J → ℕ)
    (K B : ℕ) (ha : ∀ j, a j ∈ A j)
    (hinc : ∀ T ∈ M,
      (∑ j, if a j ∈ T ∧ T ⊆ A j then L j else 0) = K)
    (hcover : ∀ i,
      B ≤ ∑ j, if f i = a j ∧ S i ⊆ (A j).erase (a j) then L j else 0)
    (hstep : ∀ R : Finset C, ∀ b ∈ R,
      ((∑ i, if f i = b ∧ S i ⊆ R.erase b then w i else 0) : ℤ) +
        H (R.erase b) ≤ H R) :
    (B : ℤ) * (∑ i, (w i : ℤ)) ≤ (K : ℤ) * H univ
Source
IN-341 supporting verification step for OP-19. Extends the subset-potential route from IN-339. Strict convention: Condorcet winning sets, Social Choice and Welfare44(3):493-517 (2015), https://www.lamsade.dauphine.fr/~lang/papers/els15.pdf . Related selector formulation: arXiv:2604.19851v2. These are construction and verification helpers, with no new election dimension bound or research advance claimed.
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
Used by 1

The proof, explained

The theorem establishes the certificate bound B * ∑ i, w i ≤ K * H univ through linear programming duality on the potential polynomial H. First, the marginal drop H (A j) - H ((A j).erase (a j)) is shown to isolate the monomials containing the pivot element a j within A j. Summing these marginal drops weighted by L j evaluates to K * H univ because every monomial has uniform incidence K across the rooted removal sets. Meanwhile, the challenger coverage condition allows B * ∑ i, w i to be bounded above by the dual-weighted challenger sum. Finally, the local removal inequalities upper-bound this challenger sum by the marginal drops, completing the chain of inequalities.

  1. For each rooted removal set (A j, a j), the marginal difference H (A j) - H ((A j).erase (a j)) equals the sum of c T over all monomials T ∈ M that contain a j and are subsets of A j.

    Substituting the definition of H from hform into H (A j) - H ((A j).erase (a j)), subtraction is distributed over the sum with sum_sub_distrib. For each monomial T ∈ M, case analysis on whether T ⊆ A j and whether a j ∈ T shows that terms with a j ∉ T or T ⊈ A j cancel out (using subset_trans and erase_subset), leaving c T exactly when a j ∈ T and T ⊆ A j. Pointwise equality of terms is concluded via sum_congr.

    lines 23–43

    uses sum_sub_distrib, sum_congr, subset_trans, erase_subset

      classical
      have hmarg : ∀ j, H (A j) - H ((A j).erase (a j)) =
          ∑ T ∈ M, if a j ∈ T ∧ T ⊆ A j then c T else 0 := by
        intro j
        rw [hform, hform, ← sum_sub_distrib]
        apply sum_congr rfl
        intro T _
        by_cases hsub : T ⊆ A j
        · by_cases hmem : a j ∈ T
          · have hn : ¬ T ⊆ (A j).erase (a j) := by
              intro hh
              exact (mem_erase.mp (hh hmem)).1 rfl
            simp [hsub, hmem, hn]
          · have hs : T ⊆ (A j).erase (a j) := by
              intro b hb
              exact mem_erase.mpr ⟨by intro hh; subst b; exact hmem hb, hsub hb⟩
            simp [hsub, hmem, hs]
        · have hn : ¬ T ⊆ (A j).erase (a j) := by
            intro hh
            exact hsub (subset_trans hh (erase_subset _ _))
          simp [hsub, hn]
  2. The weighted sum over j of the marginal drops, ∑ j, L j * (H (A j) - H ((A j).erase (a j))), equals K * H univ.

    Rewriting each marginal difference with hmarg and distributing L j into the inner sum using mul_sum, we interchange the two sums over j and T ∈ M with sum_comm. By the uniform incidence hypothesis hinc and sum_mul, the sum of weights L j for a fixed monomial T is exactly K. Factoring out K leaves K * ∑ T ∈ M, c T, which matches K * H univ by hform since every monomial T is a subset of the full set univ.

    lines 44–59

    uses mul_sum, sum_comm, sum_mul, sum_congr

      have hsum : ∑ j, (L j : ℤ) * (H (A j) - H ((A j).erase (a j))) =
          (K : ℤ) * H univ := by
        simp_rw [hmarg, mul_sum]
        rw [sum_comm]
        have hterm : ∀ T ∈ M,
            (∑ j, (L j : ℤ) * (if a j ∈ T ∧ T ⊆ A j then c T else 0)) =
              (K : ℤ) * c T := by
          intro T hT
          have hc : (∑ j, if a j ∈ T ∧ T ⊆ A j then (L j : ℤ) else 0) = K := by
            exact_mod_cast hinc T hT
          rw [← hc, sum_mul]
          apply sum_congr rfl
          intro j _
          split_ifs <;> simp
        rw [sum_congr rfl hterm, ← mul_sum, hform]
        simp
  3. The total scaled challenger weight B * ∑ i, w i is bounded above by the dual-weighted sum of challenger weights across all rooted removal sets.

    Distributing B over the sum over i with mul_sum, the coverage hypothesis hcover guarantees B ≤ ∑ j, L j for the pairs (A j, a j) covering challenger i. Multiplying each inequality by the non-negative challenger weight w i (using Nat.cast_nonneg and mul_le_mul_of_nonneg_right) and summing over all challengers i with sum_le_sum, swapping the summation order using sum_comm and sum_mul yields the bound ∑ j, L j * (∑ i, w i) restricted to matching challengers.

    lines 60–76

    uses mul_sum, sum_comm, sum_le_sum, mul_le_mul_of_nonneg_right, Nat.cast_nonneg, sum_mul, sum_congr

      have hlower :
          (B : ℤ) * (∑ i, (w i : ℤ)) ≤
          ∑ j, (L j : ℤ) * ((∑ i,
            if f i = a j ∧ S i ⊆ (A j).erase (a j) then w i else 0) : ℤ) := by
        simp_rw [mul_sum]
        rw [sum_comm]
        apply sum_le_sum
        intro i _
        have hc : (B : ℤ) ≤ ∑ j,
            if f i = a j ∧ S i ⊆ (A j).erase (a j) then (L j : ℤ) else 0 := by
          exact_mod_cast hcover i
        have hh := mul_le_mul_of_nonneg_right hc (Nat.cast_nonneg (w i) : (0 : ℤ) ≤ w i)
        simp_rw [sum_mul] at hh
        convert hh using 1
        apply sum_congr rfl
        intro j _
        split_ifs <;> simp
  4. B * ∑ i, w i ≤ K * H univ holds.

    The theorem concludes by chaining three relations in a calc block: first, the lower bound hlower bounds B * ∑ i, w i by the dual-weighted challenger sum. Second, applying the local removal inequality hstep to each (A j, a j) shows the local challenger sum is at most the marginal difference H (A j) - H ((A j).erase (a j)); multiplying by the non-negative dual weight L j (via Nat.cast_nonneg and mul_le_mul_of_nonneg_left) and summing over j with sum_le_sum bounds the whole quantity by the weighted marginal sum. Third, this weighted sum equals K * H univ by hsum.

    lines 77–85

    uses sum_le_sum, mul_le_mul_of_nonneg_left, Nat.cast_nonneg

      calc
        (B : ℤ) * (∑ i, (w i : ℤ)) ≤ _ := hlower
        _ ≤ ∑ j, (L j : ℤ) * (H (A j) - H ((A j).erase (a j))) := by
          apply sum_le_sum
          intro j _
          apply mul_le_mul_of_nonneg_left _ (Nat.cast_nonneg (L j))
          have hh := hstep (A j) (a j) (ha j)
          linarith
        _ = (K : ℤ) * H univ := hsum
erase_subset
Erasing an element from a finite set produces a subset of the original set: s.erase a ⊆ s.
mul_le_mul_of_nonneg_left
Multiplying an inequality b ≤ c on the left by a non-negative element 0 ≤ a preserves the inequality: a * b ≤ a * c.
mul_le_mul_of_nonneg_right
Multiplying an inequality b ≤ c on the right by a non-negative element 0 ≤ a preserves the inequality: b * a ≤ c * a.
mul_sum
Left distributivity of multiplication over a finite sum: a * ∑ i ∈ s, f i = ∑ i ∈ s, a * f i.
Nat.cast_nonneg
The canonical coercion of any natural number into an ordered ring is non-negative: 0 ≤ (n : ℤ).
subset_trans
The subset relation is transitive: if a ⊆ b and b ⊆ c, then a ⊆ c.
sum_comm
The order of summation in a finite double sum can be swapped: ∑ x ∈ s, ∑ y ∈ t, f x y = ∑ y ∈ t, ∑ x ∈ s, f x y.
sum_congr
Two sums over the same finite set are equal if their terms agree pointwise on every element: (∀ x ∈ s, f x = g x) → ∑ x ∈ s, f x = ∑ x ∈ s, g x.
sum_le_sum
Termwise inequality implies inequality of sums: if f i ≤ g i for all i ∈ s, then ∑ i ∈ s, f i ≤ ∑ i ∈ s, g i.
sum_mul
Right distributivity of multiplication over a finite sum: (∑ i ∈ s, f i) * a = ∑ i ∈ s, f i * a.
sum_sub_distrib
Distributivity of subtraction over a finite sum: ∑ x ∈ s, (f x - g x) = ∑ x ∈ s, f x - ∑ x ∈ s, g x.

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_polynomial_potential_dual_bound    (C I J : Type*) [Fintype C] [DecidableEq C]    [Fintype I] [Fintype J]    (M : Finset (Finset C)) (c : Finset C → ℤ)    (H : Finset C → ℤ)    (hform : ∀ A, H A = ∑ T ∈ M, if T ⊆ A then c T else 0)    (S : I → Finset C) (f : I → C) (w : I → ℕ)    (A : J → Finset C) (a : J → C) (L : J → ℕ)    (K B : ℕ) (ha : ∀ j, a j ∈ A j)    (hinc : ∀ T ∈ M,      (∑ j, if a j ∈ T ∧ T ⊆ A j then L j else 0) = K)    (hcover : ∀ i,      B ≤ ∑ j, if f i = a j ∧ S i ⊆ (A j).erase (a j) then L j else 0)    (hstep : ∀ R : Finset C, ∀ b ∈ R,      ((∑ i, if f i = b ∧ S i ⊆ R.erase b then w i else 0) : ℤ) +        H (R.erase b) ≤ H R) :    (B : ℤ) * (∑ i, (w i : ℤ)) ≤ (K : ℤ) * H univ := by  classical  have hmarg : ∀ j, H (A j) - H ((A j).erase (a j)) =      ∑ T ∈ M, if a j ∈ T ∧ T ⊆ A j then c T else 0 := by    intro j    rw [hform, hform, ← sum_sub_distrib]    apply sum_congr rfl    intro T _    by_cases hsub : T ⊆ A j    · by_cases hmem : a j ∈ T      · have hn : ¬ T ⊆ (A j).erase (a j) := by          intro hh          exact (mem_erase.mp (hh hmem)).1 rfl        simp [hsub, hmem, hn]      · have hs : T ⊆ (A j).erase (a j) := by          intro b hb          exact mem_erase.mpr ⟨by intro hh; subst b; exact hmem hb, hsub hb⟩        simp [hsub, hmem, hs]    · have hn : ¬ T ⊆ (A j).erase (a j) := by        intro hh        exact hsub (subset_trans hh (erase_subset _ _))      simp [hsub, hn]  have hsum : ∑ j, (L j : ℤ) * (H (A j) - H ((A j).erase (a j))) =      (K : ℤ) * H univ := by    simp_rw [hmarg, mul_sum]    rw [sum_comm]    have hterm : ∀ T ∈ M,        (∑ j, (L j : ℤ) * (if a j ∈ T ∧ T ⊆ A j then c T else 0)) =          (K : ℤ) * c T := by      intro T hT      have hc : (∑ j, if a j ∈ T ∧ T ⊆ A j then (L j : ℤ) else 0) = K := by        exact_mod_cast hinc T hT      rw [← hc, sum_mul]      apply sum_congr rfl      intro j _      split_ifs <;> simp    rw [sum_congr rfl hterm, ← mul_sum, hform]    simp  have hlower :      (B : ℤ) * (∑ i, (w i : ℤ)) ≤      ∑ j, (L j : ℤ) * ((∑ i,        if f i = a j ∧ S i ⊆ (A j).erase (a j) then w i else 0) : ℤ) := by    simp_rw [mul_sum]    rw [sum_comm]    apply sum_le_sum    intro i _    have hc : (B : ℤ) ≤ ∑ j,        if f i = a j ∧ S i ⊆ (A j).erase (a j) then (L j : ℤ) else 0 := by      exact_mod_cast hcover i    have hh := mul_le_mul_of_nonneg_right hc (Nat.cast_nonneg (w i) : (0 : ℤ) ≤ w i)    simp_rw [sum_mul] at hh    convert hh using 1    apply sum_congr rfl    intro j _    split_ifs <;> simp  calc    (B : ℤ) * (∑ i, (w i : ℤ)) ≤ _ := hlower    _ ≤ ∑ j, (L j : ℤ) * (H (A j) - H ((A j).erase (a j))) := by      apply sum_le_sum      intro j _      apply mul_le_mul_of_nonneg_left _ (Nat.cast_nonneg (L j))      have hh := hstep (A j) (a j) (ha j)      linarith    _ = (K : ℤ) * H univ := hsum
See it in the graphDiscuss this resultChallenge it