condorcet_polynomial_potential_dual_bound
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
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- LinearOrder.toTotalPreorderEvery
- Used by 1
- condorcet_cubic_subset_potential_residue_barrierFor candidates indexed modulo19, orient a to b when b-a is one of the nine nonzero quadratic residues. Consider any finite family of…
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.
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.
uses
sum_sub_distrib,sum_congr,subset_trans,erase_subsetclassical 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]
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.
uses
mul_sum,sum_comm,sum_mul,sum_congrhave 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
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.
uses
mul_sum,sum_comm,sum_le_sum,mul_le_mul_of_nonneg_right,Nat.cast_nonneg,sum_mul,sum_congrhave 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
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.
uses
sum_le_sum,mul_le_mul_of_nonneg_left,Nat.cast_nonnegcalc (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
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_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