condorcet_quadratic_subset_potential_half_barrier
Let an integer-valued subset potential be represented by arbitrary integer vertex coefficients and ordered-pair coefficients with zero diagonal. For any outside-challenger selector and nonnegative integer claim weights, if all candidate-removal gain inequalities hold, the total claim weight is at most twice the full-set potential. Thus this quadratic representation cannot supply a strict half-weight ordering certificate. This limits a proof ansatz, not the winning-triple conjecture.
Statement
theorem condorcet_quadratic_subset_potential_half_barrier (m q : ℕ) (S : Fin q → Finset (Fin m)) (f : Fin q → Fin m) (w : Fin q → ℕ) (H : Finset (Fin m) → ℤ) (α : Fin m → ℤ) (β : Fin m → Fin m → ℤ) (hform : ∀ A, H A = (∑ a ∈ A, α a) + ∑ a ∈ A, ∑ b ∈ A, β a b) (hdiag : ∀ a, β a a = 0) (houtside : ∀ i, f i ∉ S i) (hstep : ∀ A : Finset (Fin m), ∀ a ∈ A, ((∑ i, if f i = a ∧ S i ⊆ A.erase a then w i else 0) : ℤ) + H (A.erase a) ≤ H A) : ((∑ i, w i) : ℤ) ≤ 2 * H univ
- Source
- IN-339 supporting method lemma for the uniform subset-potential route to OP-19. Strict winning-set convention from Condorcet winning sets, Social Choice and Welfare44(3):493-517 (2015); related selector formulation arXiv:2604.19851v2. No new election bound or research advance is asserted.
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- TotalPreorderA total preorder: a preorder where
The proof, explained
The proof bounds the total claim weight by twice the universe potential by summing the candidate-removal gain inequalities for the full set A = univ over all candidates a. First, specializing the inequality to singletons shows that each linear coefficient α(a) is nonnegative. Expanding H(univ) - H(univ \ {a}) isolates the linear contribution α(a) and the in- and out-degrees of a in β, while the assumption that f(i) is outside S(i) guarantees that each claim weight w(i) appears exactly once in the combined marginal gains across all candidates. Summing over all a and swapping indices in the double sum yields ∑_i w(i) ≤ ∑_a α(a) + 2 ∑_{a, b} β(a, b), which is at most 2 * H(univ) because ∑_a α(a) ≥ 0.
Each vertex potential coefficient is nonnegative: 0 ≤ α(a) for all a.
Fix an arbitrary candidate a. Applying the removal inequality hstep to the singleton A = {a} and element a gives (∑_{i : f(i)=a ∧ S(i) ⊆ ∅} w(i)) + H(∅) ≤ H({a}). Expanding H using the quadratic representation hform gives H(∅) = 0 and H({a}) = α(a) + β(a, a) = α(a), since β(a, a) = 0 by hdiag. Because all claim weights w(i) are nonnegative, the sum of weights is at least 0, which implies 0 ≤ α(a).
uses
erase_singleton,sum_empty,sum_singleton,add_zero,le_transclassical have hα : ∀ a, 0 ≤ α a := by intro a have hl := hstep {a} a (by simp) simp only [erase_singleton] at hl rw [hform ∅, hform {a}] at hl simp only [erase_singleton, sum_empty, sum_singleton, hdiag, add_zero] at hl exact le_trans (by positivity) hl
For every candidate a, the drop in potential when removing a from the full universe is H(univ) - H(univ \ {a}) = α(a) + ∑_b β(a, b) + ∑_b β(b, a).
Fix a candidate a. Using sum_erase_add, we decompose the universe sum into the element a and the punctured set univ \ {a}. For the linear term, ∑_x α(x) splits into α(a) + ∑_{x ≠ a} α(x). For the quadratic sum, splitting row a and column a isolates the a-th row sum ∑_b β(a, b) and column sum ∑_b β(b, a). Because the diagonal entry β(a, a) vanishes by hdiag, the remaining off-diagonal terms form exactly the quadratic sum of H(univ \ {a}). Linear arithmetic then verifies the identity.
uses
sum_erase_add,mem_univ,sum_add_distrib,sum_congrhave hfull : ∀ a : Fin m, H univ = H (univ.erase a) + α a + (∑ b, β a b) + ∑ b, β b a := by intro a have hαsum := sum_erase_add univ α (mem_univ a) have hrows := sum_erase_add univ (fun x => ∑ y, β x y) (mem_univ a) have hcols := sum_erase_add univ (fun x => β x a) (mem_univ a) have hinner : (∑ x ∈ univ.erase a, ∑ y, β x y) = (∑ x ∈ univ.erase a, ∑ y ∈ univ.erase a, β x y) + ∑ x ∈ univ.erase a, β x a := by rw [← sum_add_distrib] apply sum_congr rfl intro x _ exact (sum_erase_add univ (β x) (mem_univ a)).symm rw [hdiag] at hcols rw [hform univ, hform (univ.erase a)] linarith
Summing the marginal gain indicators at the universe over all candidates a yields the total claim weight ∑_i w(i).
Interchanging the order of summation using sum_comm places the outer sum over claims i and the inner sum over candidates a. Because f(i) ∉ S(i) by houtside, the set S(i) is always contained in univ \ {f(i)}. Thus, for each claim i, the condition f(i) = a ∧ S(i) ⊆ univ \ {a} is satisfied if and only if a = f(i). The inner sum over a then collapses to w(i), so summing across all i gives the total weight ∑_i w(i).
uses
sum_comm,sum_congr,mem_erase.mpr,mem_univ,and_true,if_true,eq_self_iff_true,false_and,if_falsehave hgains : (∑ a : Fin m, ((∑ i, if f i = a ∧ S i ⊆ (univ : Finset (Fin m)).erase a then w i else 0) : ℤ)) = ((∑ i, w i) : ℤ) := by rw [sum_comm] apply sum_congr rfl intro i _ have ht : S i ⊆ (univ : Finset (Fin m)).erase (f i) := by intro b hb exact mem_erase.mpr ⟨by intro heq; subst b; exact houtside i hb, mem_univ b⟩ have heq : ∀ a, (if f i = a ∧ S i ⊆ (univ : Finset (Fin m)).erase a then (w i : ℤ) else 0) = if f i = a then (w i : ℤ) else 0 := by intro a by_cases ha : f i = a · subst a simp only [ht, and_true, if_true, eq_self_iff_true] · simp only [ha, false_and, if_false] simp_rw [heq] simp
Summing the removal inequalities for A = univ over all a gives ∑_a (gain for a) ≤ ∑_a (α(a) + ∑_b β(a, b) + ∑_b β(b, a)).
For each candidate a, the removal inequality hstep applied to A = univ asserts that the gain for removing a plus H(univ \ {a}) is at most H(univ). Substituting the potential difference formula established in hfull into this inequality and applying sum_le_sum bounds the sum of gains by the sum of marginal drops.
uses
sum_le_sum,mem_univhave hsum : (∑ a : Fin m, ((∑ i, if f i = a ∧ S i ⊆ (univ : Finset (Fin m)).erase a then w i else 0) : ℤ)) ≤ (∑ a : Fin m, (α a + (∑ b, β a b) + (∑ b, β b a))) := by apply sum_le_sum intro a _ have hl := hstep univ a (mem_univ a) have he := hfull a linarith
The total claim weight is at most twice the full-set potential: ∑_i w(i) ≤ 2 * H(univ).
Rewriting the left-hand side of the summed inequality with hgains gives ∑_i w(i). On the right-hand side, distributing the sums and swapping the indices in the transposed quadratic sum ∑_a ∑_b β(b, a) to ∑_a ∑_b β(a, b) simplifies the expression to ∑_a α(a) + 2 ∑_{a, b} β(a, b). Since each α(a) ≥ 0, their sum is nonnegative by sum_nonneg, so ∑_a α(a) + 2 ∑_{a, b} β(a, b) ≤ 2 ∑_a α(a) + 2 ∑_{a, b} β(a, b) = 2 * H(univ), concluding the proof.
uses
sum_comm,sum_add_distrib,sum_nonnegrw [hgains] at hsum have hswap : (∑ a, ∑ b, β b a) = ∑ a, ∑ b, β a b := sum_comm simp only [sum_add_distrib] at hsum rw [hswap] at hsum have hnonneg : 0 ≤ ∑ a, α a := sum_nonneg (fun a _ => hα a) rw [hform univ] linarith
erase_singleton- removing an element a from the singleton {a} yields the empty set ∅
sum_empty- the sum of any function over the empty set is 0
sum_singleton- the sum of a function over a singleton {a} equals the function value at a
add_zero- adding 0 to an element leaves it unchanged (a + 0 = a)
le_trans- transitivity of inequality: if a ≤ b and b ≤ c then a ≤ c
sum_erase_add- for any element a in a finite set s, the sum over s \ {a} plus the term at a equals the sum over s
mem_univ- every element of a finite type belongs to the universal set univ
sum_add_distrib- the sum of a pointwise sum of functions equals the sum of the individual sums
sum_congr- if two sets are equal and two functions agree on every element of the set, their sums are equal
sum_comm- finite double sums can interchange their order of summation
mem_erase.mpr- if b ≠ a and b ∈ s, then b ∈ s \ {a}
and_true- p ∧ True is logically equivalent to p
if_true- an if-then-else with condition True evaluates to the first branch
eq_self_iff_true- equality of an element with itself is True
false_and- False ∧ p is logically equivalent to False
if_false- an if-then-else with condition False evaluates to the second branch
sum_le_sum- if f(x) ≤ g(x) for all x in a finite set, then the sum of f is at most the sum of g
sum_nonneg- a sum of nonnegative terms is nonnegative
- Routine linear integer arithmetic steps rearranging and canceling terms in expanded sums are closed by `linarith` (lines 39, 66, and 73).
- The nonnegativity of the sum of weights on line 23 is discharged automatically by `positivity`.
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_quadratic_subset_potential_half_barrier (m q : ℕ) (S : Fin q → Finset (Fin m)) (f : Fin q → Fin m) (w : Fin q → ℕ) (H : Finset (Fin m) → ℤ) (α : Fin m → ℤ) (β : Fin m → Fin m → ℤ) (hform : ∀ A, H A = (∑ a ∈ A, α a) + ∑ a ∈ A, ∑ b ∈ A, β a b) (hdiag : ∀ a, β a a = 0) (houtside : ∀ i, f i ∉ S i) (hstep : ∀ A : Finset (Fin m), ∀ a ∈ A, ((∑ i, if f i = a ∧ S i ⊆ A.erase a then w i else 0) : ℤ) + H (A.erase a) ≤ H A) : ((∑ i, w i) : ℤ) ≤ 2 * H univ := by classical have hα : ∀ a, 0 ≤ α a := by intro a have hl := hstep {a} a (by simp) simp only [erase_singleton] at hl rw [hform ∅, hform {a}] at hl simp only [erase_singleton, sum_empty, sum_singleton, hdiag, add_zero] at hl exact le_trans (by positivity) hl have hfull : ∀ a : Fin m, H univ = H (univ.erase a) + α a + (∑ b, β a b) + ∑ b, β b a := by intro a have hαsum := sum_erase_add univ α (mem_univ a) have hrows := sum_erase_add univ (fun x => ∑ y, β x y) (mem_univ a) have hcols := sum_erase_add univ (fun x => β x a) (mem_univ a) have hinner : (∑ x ∈ univ.erase a, ∑ y, β x y) = (∑ x ∈ univ.erase a, ∑ y ∈ univ.erase a, β x y) + ∑ x ∈ univ.erase a, β x a := by rw [← sum_add_distrib] apply sum_congr rfl intro x _ exact (sum_erase_add univ (β x) (mem_univ a)).symm rw [hdiag] at hcols rw [hform univ, hform (univ.erase a)] linarith have hgains : (∑ a : Fin m, ((∑ i, if f i = a ∧ S i ⊆ (univ : Finset (Fin m)).erase a then w i else 0) : ℤ)) = ((∑ i, w i) : ℤ) := by rw [sum_comm] apply sum_congr rfl intro i _ have ht : S i ⊆ (univ : Finset (Fin m)).erase (f i) := by intro b hb exact mem_erase.mpr ⟨by intro heq; subst b; exact houtside i hb, mem_univ b⟩ have heq : ∀ a, (if f i = a ∧ S i ⊆ (univ : Finset (Fin m)).erase a then (w i : ℤ) else 0) = if f i = a then (w i : ℤ) else 0 := by intro a by_cases ha : f i = a · subst a simp only [ht, and_true, if_true, eq_self_iff_true] · simp only [ha, false_and, if_false] simp_rw [heq] simp have hsum : (∑ a : Fin m, ((∑ i, if f i = a ∧ S i ⊆ (univ : Finset (Fin m)).erase a then w i else 0) : ℤ)) ≤ (∑ a : Fin m, (α a + (∑ b, β a b) + (∑ b, β b a))) := by apply sum_le_sum intro a _ have hl := hstep univ a (mem_univ a) have he := hfull a linarith rw [hgains] at hsum have hswap : (∑ a, ∑ b, β b a) = ∑ a, ∑ b, β a b := sum_comm simp only [sum_add_distrib] at hsum rw [hswap] at hsum have hnonneg : 0 ≤ ∑ a, α a := sum_nonneg (fun a _ => hα a) rw [hform univ] linarith