AFTD Auto-Formalizing Theoretical Domains

condorcet_cubic_subset_potential_residue_barrier

theoremverified

For candidates indexed modulo19, orient a to b when b-a is one of the nine nonzero quadratic residues. Consider any finite family of natural-weighted challenger claims whose committees consist only of out-neighbors of their challenger. Let an integer subset potential be a membership polynomial of degree at most three with zero constant term, with arbitrary signed coefficients. If it satisfies every local removal inequality for this family, then1539 times the total claim weight is at most2869 times its full-set value. Thus it cannot certify a strict half-weight bound. This is a restriction on cubic polynomial potentials, not an election counterexample or dimension bound.

Statement

theorem condorcet_cubic_subset_potential_residue_barrier
    (q : ℕ) (S : Fin q → Finset (ZMod 19)) (f : Fin q → ZMod 19)
    (w : Fin q → ℕ) (H : Finset (ZMod 19) → ℤ)
    (c : Finset (ZMod 19) → ℤ)
    (hform : ∀ R, H R = ∑ T ∈
      (((univ : Finset (ZMod 19)).powersetCard 1 ∪ univ.powersetCard 2) ∪
        univ.powersetCard 3), if T ⊆ R then c T else 0)
    (hout : ∀ i, f i ∉ S i)
    (hcompat : ∀ i, ∀ b ∈ S i,
      (b-f i).val ∈ ({1,4,5,6,7,9,11,16,17} : Finset ℕ))
    (hstep : ∀ R : Finset (ZMod 19), ∀ b ∈ R,
      ((∑ i, if f i = b ∧ S i ⊆ R.erase b then w i else 0) : ℤ) +
        H (R.erase b) ≤ H R) :
    (1539 : ℤ) * (∑ i, (w i : ℤ)) ≤ 2869 * H univ
Source
IN-341 complete interpretation of the eight-row cubic diagnostic from IN-339, experiment8338. Supports the OP-19 uniform certificate campaign. The raw arithmetic and affine incidence audit is8502. The strict election convention is 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. No research advance is asserted.
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • condorcet_polynomial_potential_dual_boundLet a finite signed subset polynomial be a sum of monomials indexed by a specified finite support. Suppose weighted rooted removal sets…
  • weightThe support $\mathrm{supp}(p) \subseteq \mathrm{Fin}\,n$ consists of coordinates where $p(i) \neq I$; the weight is…
  • monomialFor a natural number s and a finite subset T of Fin s, the monomial associated with T is the function from (Fin s → ZMod 2) to ZMod 2…
  • g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.

The proof, explained

The proof establishes an obstruction against cubic polynomial potentials certifying a strict half-weight bound by constructing an explicit dual certificate in the linear programming duality principle `condorcet_polynomial_potential_dual_bound`. The certificate is constructed from 8 bitmask templates scaled across the 9 quadratic residue directions modulo 19. Translation invariance reduces verifying the constant monomial incidence condition to 361 pairs of differences {0, u, v}, which are exhaustively confirmed by the Lean kernel to each have incidence exactly K = 180747. For any challenger claim whose committee consists only of out-neighbors, the top four bitmasks guarantee a coverage of at least B = 96957. By duality, 96957 times the total claim weight is at most 180747 times H(univ), which reduces upon dividing by 63 to 1539 * (∑ w i) ≤ 2869 * H(univ).

  1. The incidence of any finite subset T of ℤ/19ℤ is invariant under translation by any z ∈ ℤ/19ℤ.

    We reindex the sum over T + z back to T using `sum_image` with the injection t ↦ t + z. In the test condition, the difference ((b + z) - (t + z)) simplifies to b - t by `add_sub_add_right_eq_sub`, so the inner boolean tests are identical.

    lines 30–40

    uses sum_image, sum_congr, forall_mem_image, add_sub_add_right_eq_sub, add_right_cancel

      unfold incidence
      rw [sum_image]
      · apply sum_congr rfl
        intro t _
        apply sum_congr rfl
        intro i _
        apply sum_congr rfl
        intro q _
        simp only [forall_mem_image, add_sub_add_right_eq_sub]
      · intro a _ b _ hab
        exact add_right_cancel hab
  2. For each fixed u ∈ {0, ..., 18} and all v ∈ ℤ/19ℤ, the incidence of {0, u, v} is 180747. automation

    The incidence values for all 361 pairs (u, v) are computed and verified to equal 180747 row by row directly in the Lean kernel using `decide +kernel`.

    lines 45–117

      decide +kernel
    
    
    theorem incidence_zero_row_1 : ∀ v : C, incidence {0,1,v} = 180747 := by
      decide +kernel
    
    
    theorem incidence_zero_row_2 : ∀ v : C, incidence {0,2,v} = 180747 := by
      decide +kernel
    
    
    theorem incidence_zero_row_3 : ∀ v : C, incidence {0,3,v} = 180747 := by
      decide +kernel
    
    
    theorem incidence_zero_row_4 : ∀ v : C, incidence {0,4,v} = 180747 := by
      decide +kernel
    
    
    theorem incidence_zero_row_5 : ∀ v : C, incidence {0,5,v} = 180747 := by
      decide +kernel
    
    
    theorem incidence_zero_row_6 : ∀ v : C, incidence {0,6,v} = 180747 := by
      decide +kernel
    
    
    theorem incidence_zero_row_7 : ∀ v : C, incidence {0,7,v} = 180747 := by
      decide +kernel
    
    
    theorem incidence_zero_row_8 : ∀ v : C, incidence {0,8,v} = 180747 := by
      decide +kernel
    
    
    theorem incidence_zero_row_9 : ∀ v : C, incidence {0,9,v} = 180747 := by
      decide +kernel
    
    
    theorem incidence_zero_row_10 : ∀ v : C, incidence {0,10,v} = 180747 := by
      decide +kernel
    
    
    theorem incidence_zero_row_11 : ∀ v : C, incidence {0,11,v} = 180747 := by
      decide +kernel
    
    
    theorem incidence_zero_row_12 : ∀ v : C, incidence {0,12,v} = 180747 := by
      decide +kernel
    
    
    theorem incidence_zero_row_13 : ∀ v : C, incidence {0,13,v} = 180747 := by
      decide +kernel
    
    
    theorem incidence_zero_row_14 : ∀ v : C, incidence {0,14,v} = 180747 := by
      decide +kernel
    
    
    theorem incidence_zero_row_15 : ∀ v : C, incidence {0,15,v} = 180747 := by
      decide +kernel
    
    
    theorem incidence_zero_row_16 : ∀ v : C, incidence {0,16,v} = 180747 := by
      decide +kernel
    
    
    theorem incidence_zero_row_17 : ∀ v : C, incidence {0,17,v} = 180747 := by
      decide +kernel
    
    
    theorem incidence_zero_row_18 : ∀ v : C, incidence {0,18,v} = 180747 := by
      decide +kernel
  3. The incidence sum over the product universe C × I × Q equals the nested finset sum over t ∈ T, i ∈ I, and q ∈ Q.

    We decompose the sum over the product type using `Fintype.sum_prod_type`, restrict the outermost sum over all candidates to T via `sum_subset` (since terms with t ∉ T evaluate to 0), and rewrite the subset condition T ⊆ A(t, i, q) into a universal quantifier over b ∈ T using `Finset.subset_iff`.

    lines 137–154

    uses Fintype.sum_prod_type, sum_subset, subset_univ, sum_congr, Finset.subset_iff

      simp only [Fintype.sum_prod_type]
      calc
        (∑ t : C, ∑ i : I, ∑ q : Q,
          if t ∈ T ∧ T ⊆ A (t,i,q) then L i else 0)
          = ∑ t ∈ T, ∑ i : I, ∑ q : Q,
              if t ∈ T ∧ T ⊆ A (t,i,q) then L i else 0 := by
            symm
            apply sum_subset (subset_univ T)
            intro t _ ht
            simp [ht]
        _ = _ := by
          apply sum_congr rfl
          intro t ht
          apply sum_congr rfl
          intro i _
          apply sum_congr rfl
          intro q _
          simp only [ht, true_and, Finset.subset_iff, hA]
  4. The restricted coverage sum for a single challenger f is bounded above by the total sum over all candidates j.1 in the universe.

    The sum over i and q restricted to j.1 = f is a single term g(f) of the total sum ∑_t g(t) over all t ∈ C. Since the terms are non-negative, `single_le_sum` gives the inequality.

    lines 162–165

    uses single_le_sum, Nat.zero_le, mem_univ, Fintype.sum_prod_type

      let g : C → ℕ := fun t => ∑ i : I, ∑ q : Q,
        if f = t ∧ S ⊆ (A (t,i,q)).erase t then L i else 0
      have hh : g f ≤ ∑ t, g t := single_le_sum (fun t _ => Nat.zero_le _) (mem_univ f)
      simpa only [g, Fintype.sum_prod_type, eq_self_iff_true, true_and] using hh
  5. For any pair u, v ∈ ℤ/19ℤ, the incidence of {0, u, v} is 180747.

    We perform a case split on the value of u using `fin_cases u`, and dispatch each case using the corresponding precomputed row lemma `incidence_zero_row_0` through `incidence_zero_row_18`.

    lines 168–188

    uses incidence_zero_row_0, incidence_zero_row_1, incidence_zero_row_2, incidence_zero_row_3, incidence_zero_row_4, incidence_zero_row_5, incidence_zero_row_6, incidence_zero_row_7, incidence_zero_row_8, incidence_zero_row_9, incidence_zero_row_10, incidence_zero_row_11, incidence_zero_row_12, incidence_zero_row_13, incidence_zero_row_14, incidence_zero_row_15, incidence_zero_row_16, incidence_zero_row_17, incidence_zero_row_18

      intro u v
      fin_cases u
      · exact incidence_zero_row_0 v
      · exact incidence_zero_row_1 v
      · exact incidence_zero_row_2 v
      · exact incidence_zero_row_3 v
      · exact incidence_zero_row_4 v
      · exact incidence_zero_row_5 v
      · exact incidence_zero_row_6 v
      · exact incidence_zero_row_7 v
      · exact incidence_zero_row_8 v
      · exact incidence_zero_row_9 v
      · exact incidence_zero_row_10 v
      · exact incidence_zero_row_11 v
      · exact incidence_zero_row_12 v
      · exact incidence_zero_row_13 v
      · exact incidence_zero_row_14 v
      · exact incidence_zero_row_15 v
      · exact incidence_zero_row_16 v
      · exact incidence_zero_row_17 v
      · exact incidence_zero_row_18 v
  6. Every non-empty subset T of ℤ/19ℤ with cardinality at most 3 has incidence equal to 180747.

    Any set of size 1, 2, or 3 can be written as {x, y, z}. By translation invariance (`incidence_shift`), its incidence equals that of {0, y - x, z - x}, which is 180747 by `incidence_zero_certificate`.

    lines 192–204

    uses card_eq_one.mp, card_eq_two.mp, card_eq_three.mp, incidence_shift, image_insert, image_singleton, zero_add, sub_add_cancel, incidence_zero_certificate

      have htuple : ∃ x y z : C, T = {x,y,z} := by
        have hc : T.card=1 ∨ T.card=2 ∨ T.card=3 := by omega
        rcases hc with h1 | h2 | h3
        · obtain ⟨x,hx⟩ := card_eq_one.mp h1
          exact ⟨x,x,x,by simpa using hx⟩
        · obtain ⟨x,y,_,hxy⟩ := card_eq_two.mp h2
          exact ⟨x,y,y,by simpa using hxy⟩
        · obtain ⟨x,y,z,_,_,_,hxyz⟩ := card_eq_three.mp h3
          exact ⟨x,y,z,hxyz⟩
      rcases htuple with ⟨x,y,z,rfl⟩
      have hs := incidence_shift ({0,y-x,z-x} : Finset C) x
      simp only [image_insert, image_singleton, zero_add, sub_add_cancel] at hs
      exact hs.trans (incidence_zero_certificate (y-x) (z-x))
  7. Every monomial subset T ∈ mono has incidence 180747.

    The family `mono` consists of subsets of cardinality 1, 2, or 3. By `incidence_of_card`, every such set has incidence 180747.

    lines 207–210

    uses mem_union, mem_powersetCard, subset_univ, incidence_of_card

      intro T hT
      have hm := hT
      simp only [mono, mem_union, mem_powersetCard, subset_univ, true_and] at hm
      apply incidence_of_card T <;> omega
  8. For every dual item j, its root candidate belongs to the committee set A(j). automation

    Evaluating the definition of A(j) at root j = t tests whether bit ((t - t) * mults q).val = 0 of rowMasks i is 1. Bit 0 is 1 for all 8 masks, verified by `decide +kernel`.

    lines 213–216

    uses mem_filter, mem_univ, sub_self, zero_mul

      intro j
      rcases j with ⟨t,i,q⟩
      simp only [root, A, mem_filter, mem_univ, true_and, sub_self, zero_mul]
      fin_cases i <;> decide +kernel
  9. For each quadratic residue difference, each multiplier, and each template index i ≥ 4, the bitmask accepts the element. automation

    Exhaustively checked over the finite domain of 9 residues, 9 multipliers, and 4 upper masks using `decide +kernel`.

    lines 220–221

        ∀ i : Fin 4, (rowMasks ⟨i.val+4, by omega⟩).testBit ((b*mults q).val) := by
      decide +kernel
  10. The sum of weights of dual items covering T and rooted in T equals `incidence T`.

    This specializes the abstract equivalence `in341_incidence_sum_generic` to the concrete finite fields and bitmask definitions.

    lines 233–236

    uses in341_incidence_sum_generic, mem_filter, mem_univ

      simpa only [root,weight,incidence] using
        in341_incidence_sum_generic C (Fin 8) (Fin 9) T A coeff
          (fun t i q b => (rowMasks i).testBit (((b-t)*mults q).val))
          (fun t i q b => by simp only [A,mem_filter,mem_univ,true_and])
  11. For any challenger claim with out-neighbor committee S, the dual coverage sum is at least 96957.

    By `row_cover`, for every template index i ≥ 4 and multiplier q, the set S is contained in A(f, i, q) \ {f}. Summing over all 9 multipliers gives 9 * coeff i for each i ≥ 4. Summing 9 * coeff i over i ∈ {4, 5, 6, 7} yields 9 * (6156 + 1463 + 1539 + 1615) = 96957. Bounding the slice sum by the full sum via `in341_claim_slice_le_generic` completes the step.

    lines 244–270

    uses Fin.ext, row_cover, mem_erase.mpr, mem_filter.mpr, mem_univ, sum_nonneg, sum_le_sum, in341_claim_slice_le_generic

      have hsub : ∀ (i : Fin 8), 4 ≤ i.val → ∀ q : Fin 9,
          S ⊆ (A (f,i,q)).erase f := by
        intro i hi q b hb
        let k : Fin 4 := ⟨i.val-4, by omega⟩
        have hk : (⟨k.val+4, by omega⟩ : Fin 8) = i := by
          apply Fin.ext
          dsimp [k]
          omega
        have hr := row_cover q (b-f) (hc b hb) k
        rw [hk] at hr
        refine mem_erase.mpr ⟨by intro he; subst b; exact hf hb, ?_⟩
        change b ∈ univ.filter (fun b => (rowMasks i).testBit (((b-f)*mults q).val))
        exact mem_filter.mpr ⟨mem_univ _, hr⟩
      have hpart : ∀ i : Fin 8,
          (if 4 ≤ i.val then 9*coeff i else 0) ≤
            ∑ q : Fin 9, if S ⊆ (A (f,i,q)).erase f then coeff i else 0 := by
        intro i
        by_cases hi : 4 ≤ i.val
        · simp [hi, hsub i hi, mul_comm]
        · simp only [hi, if_false]
          exact sum_nonneg fun q _ => by positivity
      have hsum := sum_le_sum (s := univ) (fun i _ => hpart i)
      have heval : (∑ i : Fin 8, if 4 ≤ i.val then 9*coeff i else 0) = 96957 := by
        decide +kernel
      rw [heval] at hsum
      apply hsum.trans
      simpa only [root,weight] using in341_claim_slice_le_generic C (Fin 8) (Fin 9) A coeff S f
  12. For any degree-3 potential H satisfying the local removal inequalities, 1539 * (∑ w i) ≤ 2869 * H(univ).

    We invoke the linear programming duality theorem `condorcet_polynomial_potential_dual_bound` with incidence constant K = 180747 and coverage bound B = 96957. This gives 96957 * (∑ w i) ≤ 180747 * H(univ). Dividing by 63 (since 96957 = 63 * 1539 and 180747 = 63 * 2869) via `norm_num` and `omega` yields the final bound 1539 * (∑ w i) ≤ 2869 * H(univ).

    lines 290–299

    uses condorcet_polynomial_potential_dual_bound, In341CubicField.root_mem, In341CubicField.incidence_eq_sum, In341CubicField.incidence_certificate, In341CubicField.claim_coverage

      have hd := condorcet_polynomial_potential_dual_bound
        (ZMod 19) (Fin q) In341CubicField.J In341CubicField.mono c H hform S f w
        In341CubicField.A In341CubicField.root In341CubicField.weight 180747 96957
        In341CubicField.root_mem
        (fun T hT => (In341CubicField.incidence_eq_sum T).trans
          (In341CubicField.incidence_certificate T hT))
        (fun i => In341CubicField.claim_coverage (S i) (f i) (hout i) (hcompat i))
        hstep
      norm_num at hd
      omega
sum_image
The sum of a function over the image of a finite set under an injection equals the sum over the original set.
sum_congr
If two index sets are identical and their summands agree at every element, their sums are equal.
forall_mem_image
A predicate holds for all elements of an image set f(s) if and only if it holds for f(x) for all x in s.
add_sub_add_right_eq_sub
In an additive group, (a + c) - (b + c) = a - b.
add_right_cancel
In an additive group, a + b = c + b implies a = c.
Fintype.sum_prod_type
The sum of a function over a product type α × β equals the iterated sum over α and β.
sum_subset
A sum over a subset s₁ equals the sum over a superset s₂ if the summand is zero outside s₁.
subset_univ
Any finite set is a subset of the universal set of its type.
Finset.subset_iff
A set s₁ is a subset of s₂ if and only if every element of s₁ belongs to s₂.
single_le_sum
A single term in a non-negative finite sum is bounded above by the total sum.
Nat.zero_le
Every natural number is greater than or equal to zero.
mem_univ
Every element of a finite type belongs to its universal set.
incidence_zero_row_0
The incidence of {0, 0, v} is 180747 for all v in ℤ/19ℤ.
incidence_zero_row_1
The incidence of {0, 1, v} is 180747 for all v in ℤ/19ℤ.
incidence_zero_row_2
The incidence of {0, 2, v} is 180747 for all v in ℤ/19ℤ.
incidence_zero_row_3
The incidence of {0, 3, v} is 180747 for all v in ℤ/19ℤ.
incidence_zero_row_4
The incidence of {0, 4, v} is 180747 for all v in ℤ/19ℤ.
incidence_zero_row_5
The incidence of {0, 5, v} is 180747 for all v in ℤ/19ℤ.
incidence_zero_row_6
The incidence of {0, 6, v} is 180747 for all v in ℤ/19ℤ.
incidence_zero_row_7
The incidence of {0, 7, v} is 180747 for all v in ℤ/19ℤ.
incidence_zero_row_8
The incidence of {0, 8, v} is 180747 for all v in ℤ/19ℤ.
incidence_zero_row_9
The incidence of {0, 9, v} is 180747 for all v in ℤ/19ℤ.
incidence_zero_row_10
The incidence of {0, 10, v} is 180747 for all v in ℤ/19ℤ.
incidence_zero_row_11
The incidence of {0, 11, v} is 180747 for all v in ℤ/19ℤ.
incidence_zero_row_12
The incidence of {0, 12, v} is 180747 for all v in ℤ/19ℤ.
incidence_zero_row_13
The incidence of {0, 13, v} is 180747 for all v in ℤ/19ℤ.
incidence_zero_row_14
The incidence of {0, 14, v} is 180747 for all v in ℤ/19ℤ.
incidence_zero_row_15
The incidence of {0, 15, v} is 180747 for all v in ℤ/19ℤ.
incidence_zero_row_16
The incidence of {0, 16, v} is 180747 for all v in ℤ/19ℤ.
incidence_zero_row_17
The incidence of {0, 17, v} is 180747 for all v in ℤ/19ℤ.
incidence_zero_row_18
The incidence of {0, 18, v} is 180747 for all v in ℤ/19ℤ.
card_eq_one.mp
A finite set of cardinality 1 is a singleton {x}.
card_eq_two.mp
A finite set of cardinality 2 consists of two distinct elements {x, y}.
card_eq_three.mp
A finite set of cardinality 3 consists of three pairwise distinct elements {x, y, z}.
incidence_shift
The incidence of a translated set T + z equals the incidence of T.
image_insert
The image of an inserted element is inserted into the image of the rest of the set.
image_singleton
The image of a singleton under a function is the singleton of the image element.
zero_add
Adding zero on the left is the identity.
sub_add_cancel
In an additive group, (a - b) + b = a.
incidence_zero_certificate
The incidence of any subset of the form {0, u, v} is 180747.
mem_union
An element is in a union of two sets if and only if it is in at least one of them.
mem_powersetCard
An element belongs to the powerset of size k if and only if it has cardinality k and is a subset.
incidence_of_card
Any non-empty subset of cardinality at most 3 has incidence 180747.
mem_filter
An element is in a filtered set if and only if it belongs to the base set and satisfies the filter predicate.
sub_self
In an additive group, subtracting an element from itself gives zero.
zero_mul
Multiplying zero on the left gives zero.
in341_incidence_sum_generic
Equivalence between a product-type dual incidence sum and an explicit nested sum.
Fin.ext
Two elements of Fin n are equal if their underlying natural values are equal.
row_cover
For every quadratic residue difference, multiplier, and row index at least 4, the bitmask condition is satisfied.
mem_erase.mpr
An element x is in s.erase a if x ≠ a and x ∈ s.
mem_filter.mpr
If an element is in the base set and satisfies the predicate, it is in the filtered set.
sum_nonneg
A finite sum of non-negative values is non-negative.
sum_le_sum
If f(x) ≤ g(x) for all x in s, then the sum of f over s is at most the sum of g over s.
in341_claim_slice_le_generic
A sum over one challenger candidate slice is bounded above by the total sum over all candidates.
condorcet_polynomial_potential_dual_bound
Linear programming duality theorem: if dual weights achieve constant monomial incidence K and coverage at least B for all claims, then B times the total weight is at most K times H(univ).
In341CubicField.root_mem
The root of any dual item j belongs to its associated set A(j).
In341CubicField.incidence_eq_sum
The dual item sum covering T equals the definition `incidence T`.
In341CubicField.incidence_certificate
Every monomial set T in `mono` has incidence 180747.
In341CubicField.claim_coverage
For any valid challenger claim, the dual coverage sum is at least 96957.

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 8000000set_option maxRecDepth 100000namespace In341CubicFieldabbrev C := ZMod 19abbrev J := C × Fin 8 × Fin 9def mults : Fin 9 → C := ![1, 4, 5, 6, 7, 9, 11, 16, 17]def rowMasks : Fin 8 → ℕ := ![1, 1303, 12481, 42577, 204799, 217083, 228347, 249851]def coeff : Fin 8 → ℕ := ![2793, 266, 3724, 2527, 6156, 1463, 1539, 1615]def A (j : J) : Finset C := univ.filter fun b =>  (rowMasks j.2.1).testBit (((b-j.1)*mults j.2.2).val)def root (j : J) : C := j.1def weight (j : J) : ℕ := coeff j.2.1def mono : Finset (Finset C) :=  (univ.powersetCard 1 ∪ univ.powersetCard 2) ∪ univ.powersetCard 3-- Test only actual monomial members, without materializing the full local-- remaining set for every finite arithmetic check.def incidence (T : Finset C) : ℕ :=  ∑ t ∈ T, ∑ i : Fin 8, ∑ q : Fin 9,    if ∀ b ∈ T, (rowMasks i).testBit (((b-t)*mults q).val) then coeff i else 0theorem incidence_shift (T : Finset C) (z : C) :    incidence (T.image fun t => t+z) = incidence T := by  unfold incidence  rw [sum_image]  · apply sum_congr rfl    intro t _    apply sum_congr rfl    intro i _    apply sum_congr rfl    intro q _    simp only [forall_mem_image, add_sub_add_right_eq_sub]  · intro a _ b _ hab    exact add_right_cancel hab-- Translation reduces the finite verification from all subsets to361-- pairs of differences. No coefficient or electorate symmetry is assumed.theorem incidence_zero_row_0 : ∀ v : C, incidence {0,0,v} = 180747 := by  decide +kerneltheorem incidence_zero_row_1 : ∀ v : C, incidence {0,1,v} = 180747 := by  decide +kerneltheorem incidence_zero_row_2 : ∀ v : C, incidence {0,2,v} = 180747 := by  decide +kerneltheorem incidence_zero_row_3 : ∀ v : C, incidence {0,3,v} = 180747 := by  decide +kerneltheorem incidence_zero_row_4 : ∀ v : C, incidence {0,4,v} = 180747 := by  decide +kerneltheorem incidence_zero_row_5 : ∀ v : C, incidence {0,5,v} = 180747 := by  decide +kerneltheorem incidence_zero_row_6 : ∀ v : C, incidence {0,6,v} = 180747 := by  decide +kerneltheorem incidence_zero_row_7 : ∀ v : C, incidence {0,7,v} = 180747 := by  decide +kerneltheorem incidence_zero_row_8 : ∀ v : C, incidence {0,8,v} = 180747 := by  decide +kerneltheorem incidence_zero_row_9 : ∀ v : C, incidence {0,9,v} = 180747 := by  decide +kerneltheorem incidence_zero_row_10 : ∀ v : C, incidence {0,10,v} = 180747 := by  decide +kerneltheorem incidence_zero_row_11 : ∀ v : C, incidence {0,11,v} = 180747 := by  decide +kerneltheorem incidence_zero_row_12 : ∀ v : C, incidence {0,12,v} = 180747 := by  decide +kerneltheorem incidence_zero_row_13 : ∀ v : C, incidence {0,13,v} = 180747 := by  decide +kerneltheorem incidence_zero_row_14 : ∀ v : C, incidence {0,14,v} = 180747 := by  decide +kerneltheorem incidence_zero_row_15 : ∀ v : C, incidence {0,15,v} = 180747 := by  decide +kerneltheorem incidence_zero_row_16 : ∀ v : C, incidence {0,16,v} = 180747 := by  decide +kerneltheorem incidence_zero_row_17 : ∀ v : C, incidence {0,17,v} = 180747 := by  decide +kerneltheorem incidence_zero_row_18 : ∀ v : C, incidence {0,18,v} = 180747 := by  decide +kernelend In341CubicFieldopen Finsetopen scoped BigOperatorsset_option maxHeartbeats 300000-- Keep finite-sum algebra abstract; instantiating a concrete finite universe-- before this step causes needless definitional expansion of its enumeration.private theorem in341_incidence_sum_generic    (C I Q : Type*) [Fintype C] [DecidableEq C] [Fintype I] [Fintype Q]    (T : Finset C) (A : C × I × Q → Finset C) (L : I → ℕ)    (P : C → I → Q → C → Prop) [∀ t i q, DecidablePred (P t i q)]    (hA : ∀ t i q b, b ∈ A (t,i,q) ↔ P t i q b) :    (∑ j : C × I × Q, if j.1 ∈ T ∧ T ⊆ A j then L j.2.1 else 0) =      ∑ t ∈ T, ∑ i : I, ∑ q : Q,        if ∀ b ∈ T, P t i q b then L i else 0 := by  simp only [Fintype.sum_prod_type]  calc    (∑ t : C, ∑ i : I, ∑ q : Q,      if t ∈ T ∧ T ⊆ A (t,i,q) then L i else 0)      = ∑ t ∈ T, ∑ i : I, ∑ q : Q,          if t ∈ T ∧ T ⊆ A (t,i,q) then L i else 0 := by        symm        apply sum_subset (subset_univ T)        intro t _ ht        simp [ht]    _ = _ := by      apply sum_congr rfl      intro t ht      apply sum_congr rfl      intro i _      apply sum_congr rfl      intro q _      simp only [ht, true_and, Finset.subset_iff, hA]private theorem in341_claim_slice_le_generic    (C I Q : Type*) [Fintype C] [DecidableEq C] [Fintype I] [Fintype Q]    (A : C × I × Q → Finset C) (L : I → ℕ) (S : Finset C) (f : C) :    (∑ i : I, ∑ q : Q, if S ⊆ (A (f,i,q)).erase f then L i else 0) ≤      ∑ j : C × I × Q,        if f = j.1 ∧ S ⊆ (A j).erase j.1 then L j.2.1 else 0 := by  let g : C → ℕ := fun t => ∑ i : I, ∑ q : Q,    if f = t ∧ S ⊆ (A (t,i,q)).erase t then L i else 0  have hh : g f ≤ ∑ t, g t := single_le_sum (fun t _ => Nat.zero_le _) (mem_univ f)  simpa only [g, Fintype.sum_prod_type, eq_self_iff_true, true_and] using hhnamespace In341CubicFieldtheorem incidence_zero_certificate : ∀ u v : C, incidence {0,u,v} = 180747 := by  intro u v  fin_cases u  · exact incidence_zero_row_0 v  · exact incidence_zero_row_1 v  · exact incidence_zero_row_2 v  · exact incidence_zero_row_3 v  · exact incidence_zero_row_4 v  · exact incidence_zero_row_5 v  · exact incidence_zero_row_6 v  · exact incidence_zero_row_7 v  · exact incidence_zero_row_8 v  · exact incidence_zero_row_9 v  · exact incidence_zero_row_10 v  · exact incidence_zero_row_11 v  · exact incidence_zero_row_12 v  · exact incidence_zero_row_13 v  · exact incidence_zero_row_14 v  · exact incidence_zero_row_15 v  · exact incidence_zero_row_16 v  · exact incidence_zero_row_17 v  · exact incidence_zero_row_18 vtheorem incidence_of_card (T : Finset C) (hpos : 0 < T.card) (hcard : T.card ≤ 3) :    incidence T = 180747 := by  have htuple : ∃ x y z : C, T = {x,y,z} := by    have hc : T.card=1 ∨ T.card=2 ∨ T.card=3 := by omega    rcases hc with h1 | h2 | h3    · obtain ⟨x,hx⟩ := card_eq_one.mp h1      exact ⟨x,x,x,by simpa using hx⟩    · obtain ⟨x,y,_,hxy⟩ := card_eq_two.mp h2      exact ⟨x,y,y,by simpa using hxy⟩    · obtain ⟨x,y,z,_,_,_,hxyz⟩ := card_eq_three.mp h3      exact ⟨x,y,z,hxyz⟩  rcases htuple with ⟨x,y,z,rfl⟩  have hs := incidence_shift ({0,y-x,z-x} : Finset C) x  simp only [image_insert, image_singleton, zero_add, sub_add_cancel] at hs  exact hs.trans (incidence_zero_certificate (y-x) (z-x))theorem incidence_certificate : ∀ T ∈ mono, incidence T = 180747 := by  intro T hT  have hm := hT  simp only [mono, mem_union, mem_powersetCard, subset_univ, true_and] at hm  apply incidence_of_card T <;> omegatheorem root_mem : ∀ j, root j ∈ A j := by  intro j  rcases j with ⟨t,i,q⟩  simp only [root, A, mem_filter, mem_univ, true_and, sub_self, zero_mul]  fin_cases i <;> decide +kerneltheorem row_cover : ∀ (q : Fin 9) (b : C),    b.val ∈ ({1,4,5,6,7,9,11,16,17} : Finset ℕ) →    ∀ i : Fin 4, (rowMasks ⟨i.val+4, by omega⟩).testBit ((b*mults q).val) := by  decide +kernelend In341CubicField-- Append after PolynomialDual.lean and CubicIncidence.lean for testing.namespace In341CubicFieldset_option backward.isDefEq.respectTransparency false intheorem incidence_eq_sum (T : Finset C) :    (∑ j : J, if root j ∈ T ∧ T ⊆ A j then weight j else 0) = incidence T := by  simpa only [root,weight,incidence] using    in341_incidence_sum_generic C (Fin 8) (Fin 9) T A coeff      (fun t i q b => (rowMasks i).testBit (((b-t)*mults q).val))      (fun t i q b => by simp only [A,mem_filter,mem_univ,true_and])set_option backward.isDefEq.respectTransparency false intheorem claim_coverage (S : Finset C) (f : C)    (hf : f ∉ S)    (hc : ∀ b ∈ S,      (b-f).val ∈ ({1,4,5,6,7,9,11,16,17} : Finset ℕ)) :    96957 ≤ ∑ j : J, if f = root j ∧ S ⊆ (A j).erase (root j) then weight j else 0 := by  have hsub : ∀ (i : Fin 8), 4 ≤ i.val → ∀ q : Fin 9,      S ⊆ (A (f,i,q)).erase f := by    intro i hi q b hb    let k : Fin 4 := ⟨i.val-4, by omega⟩    have hk : (⟨k.val+4, by omega⟩ : Fin 8) = i := by      apply Fin.ext      dsimp [k]      omega    have hr := row_cover q (b-f) (hc b hb) k    rw [hk] at hr    refine mem_erase.mpr ⟨by intro he; subst b; exact hf hb, ?_⟩    change b ∈ univ.filter (fun b => (rowMasks i).testBit (((b-f)*mults q).val))    exact mem_filter.mpr ⟨mem_univ _, hr⟩  have hpart : ∀ i : Fin 8,      (if 4 ≤ i.val then 9*coeff i else 0) ≤        ∑ q : Fin 9, if S ⊆ (A (f,i,q)).erase f then coeff i else 0 := by    intro i    by_cases hi : 4 ≤ i.val    · simp [hi, hsub i hi, mul_comm]    · simp only [hi, if_false]      exact sum_nonneg fun q _ => by positivity  have hsum := sum_le_sum (s := univ) (fun i _ => hpart i)  have heval : (∑ i : Fin 8, if 4 ≤ i.val then 9*coeff i else 0) = 96957 := by    decide +kernel  rw [heval] at hsum  apply hsum.trans  simpa only [root,weight] using in341_claim_slice_le_generic C (Fin 8) (Fin 9) A coeff S fend In341CubicFieldset_option backward.isDefEq.respectTransparency falsetheorem condorcet_cubic_subset_potential_residue_barrier    (q : ℕ) (S : Fin q → Finset (ZMod 19)) (f : Fin q → ZMod 19)    (w : Fin q → ℕ) (H : Finset (ZMod 19) → ℤ)    (c : Finset (ZMod 19) → ℤ)    (hform : ∀ R, H R = ∑ T ∈      (((univ : Finset (ZMod 19)).powersetCard 1 ∪ univ.powersetCard 2) ∪        univ.powersetCard 3), if T ⊆ R then c T else 0)    (hout : ∀ i, f i ∉ S i)    (hcompat : ∀ i, ∀ b ∈ S i,      (b-f i).val ∈ ({1,4,5,6,7,9,11,16,17} : Finset ℕ))    (hstep : ∀ R : Finset (ZMod 19), ∀ b ∈ R,      ((∑ i, if f i = b ∧ S i ⊆ R.erase b then w i else 0) : ℤ) +        H (R.erase b) ≤ H R) :    (1539 : ℤ) * (∑ i, (w i : ℤ)) ≤ 2869 * H univ := by  have hd := condorcet_polynomial_potential_dual_bound    (ZMod 19) (Fin q) In341CubicField.J In341CubicField.mono c H hform S f w    In341CubicField.A In341CubicField.root In341CubicField.weight 180747 96957    In341CubicField.root_mem    (fun T hT => (In341CubicField.incidence_eq_sum T).trans      (In341CubicField.incidence_certificate T hT))    (fun i => In341CubicField.claim_coverage (S i) (f i) (hout i) (hcompat i))    hstep  norm_num at hd  omega
See it in the graphDiscuss this resultChallenge it