AFTD Auto-Formalizing Theoretical Domains

condorcet_quadratic_subset_potential_half_barrier

theoremverified

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 than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.

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.

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

    lines 16–23

    uses erase_singleton, sum_empty, sum_singleton, add_zero, le_trans

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

    lines 24–39

    uses sum_erase_add, mem_univ, sum_add_distrib, sum_congr

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

    lines 40–57

    uses sum_comm, sum_congr, mem_erase.mpr, mem_univ, and_true, if_true, eq_self_iff_true, false_and, if_false

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

    lines 58–66

    uses sum_le_sum, mem_univ

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

    lines 67–73

    uses sum_comm, sum_add_distrib, sum_nonneg

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

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