condorcet_cubic_subset_potential_residue_barrier
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).
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.
uses
sum_image,sum_congr,forall_mem_image,add_sub_add_right_eq_sub,add_right_cancelunfold 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
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`.
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
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`.
uses
Fintype.sum_prod_type,sum_subset,subset_univ,sum_congr,Finset.subset_iffsimp 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]
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.
uses
single_le_sum,Nat.zero_le,mem_univ,Fintype.sum_prod_typelet 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
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`.
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_18intro 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
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`.
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_certificatehave 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))
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.
uses
mem_union,mem_powersetCard,subset_univ,incidence_of_cardintro T hT have hm := hT simp only [mono, mem_union, mem_powersetCard, subset_univ, true_and] at hm apply incidence_of_card T <;> omega
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`.
uses
mem_filter,mem_univ,sub_self,zero_mulintro 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
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`.
∀ i : Fin 4, (rowMasks ⟨i.val+4, by omega⟩).testBit ((b*mults q).val) := by decide +kernel
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.
uses
in341_incidence_sum_generic,mem_filter,mem_univsimpa 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])
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.
uses
Fin.ext,row_cover,mem_erase.mpr,mem_filter.mpr,mem_univ,sum_nonneg,sum_le_sum,in341_claim_slice_le_generichave 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
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).
uses
condorcet_polynomial_potential_dual_bound,In341CubicField.root_mem,In341CubicField.incidence_eq_sum,In341CubicField.incidence_certificate,In341CubicField.claim_coveragehave 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.
- The 361 incidence evaluations for sets of the form {0, u, v} are verified by exhaustive computation directly in the Lean kernel (`decide +kernel`) split into 19 row lemmas.
- The bitmask coverage property `row_cover` is also verified by the Lean kernel via `decide +kernel`.
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 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