condorcet_tournament_stationary_restriction_obstruction
There is a complete outside-challenger selector on all1771 three-element subsets of23 candidates such that every challenger dominates every committee member in the single quadratic-residue tournament modulo23, yet no natural weighting stationary under uniform evict-one/insert-the-challenger transitions has strict half-weight score for every ranking: the canonical candidate ordering already satisfies at least half its weight. Each transition evicts one distinct committee member. This is an obstruction to that additional certificate restriction even under tournament consistency. It asserts no election counterexample and no dimension bound.
Statement
theorem condorcet_tournament_stationary_restriction_obstruction : ∃ (S : Fin 1771 → Finset (Fin 23)) (f : Fin 1771 → Fin 23) (d : Fin 1771 → Fin 3 → Fin 23) (next : Fin 1771 → Fin 3 → Fin 1771), (∀ i, (S i).card=3) ∧ (∀ T : Finset (Fin 23), T.card=3 → ∃ i,S i=T) ∧ (∀ i, f i ∉ S i) ∧ (∀ i, Function.Injective (d i) ∧ ∀ c,c∈S i ↔ ∃ k,d i k=c) ∧ (∀ i, ∀ c∈S i, (c.val+23-(f i).val)%23 ∈ ({1,2,3,4,6,8,9,12,13,16,18} : Finset ℕ)) ∧ (∀ i k,S (next i k)=insert (f i) ((S i).erase (d i k))) ∧ ∀ w : Fin 1771 → ℕ, (∀ j, 3*w j=∑ i,∑ k : Fin 3,if next i k=j then w i else 0) → (∑ i,w i) ≤ 2*∑ i,if ∀ c∈S i,f i<c then w i else 0
- Source
- IN-341 OP-19 method diagnostic, experiments8577 and8584. The prior8-candidate stationarity obstruction has mutual root arcs, so does not imply this tournament-consistent version. Exact23-candidate conservation data give C45,K23 and p<=73. Related election convention and general problem: Condorcet winning sets (2015), https://www.lamsade.dauphine.fr/~lang/papers/els15.pdf and arXiv:2604.19851v2. No research advance is claimed.
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 10
- condorcet_stationary_telescoping_generalOn an arbitrary finite three-successor transition graph, suppose a natural potential has local conservation lower bound K against scale C…
- condorcet_qr23_selector_memberThe k-th smallest member of the i-th three-element subset of Fin 23 in lexicographic order (stored as lookup tables).
- condorcet_qr23_selector_challengerThe outside challenger of the i-th triple: the first candidate cyclically before its minimum that beats all three members in the…
- condorcet_qr23_selector_nextThe index of the triple obtained from the i-th triple by evicting its k-th smallest member and inserting its challenger.
- condorcet_qr23_selector_potentialAn integer potential on the 1771 triples certifying the local inequality 23 + 3 p(i) <= 45 score(i) + sum over the three transitions of p.
- condorcet_qr23_selector_completeEvery three-element subset of Fin 23 is the member set of some indexed triple.
- condorcet_qr23_selector_chkEach indexed triple is listed in increasing order, its challenger is outside it, and the challenger beats every member in the…
- condorcet_qr23_selector_localThe potential satisfies 23 + 3 p(i) <= 45 [challenger below the minimum] + the sum of p over the three transitions, for every triple.
- condorcet_qr23_selector_trans_loFor the first 886 triples, each transition's member list is the old triple with the evicted member replaced by the challenger (as sets of…
- condorcet_qr23_selector_trans_hiFor the last 885 triples, each transition's member list is the old triple with the evicted member replaced by the challenger (as sets of…
The proof, explained
The theorem constructs an explicit outside-challenger selector on all 1771 three-candidate subsets of 23 candidates such that each challenger is beaten by all three committee members in the modulo 23 quadratic-residue tournament. Transitions evict one member to insert the challenger, and an explicit potential function on committees satisfies a local inequality bounding 23 + 3 * p(i) by 45 times the canonical ranking score indicator plus the transitioned potentials. By a general telescoping argument, summing over any stationary weight distribution cancels the potentials, demonstrating that the canonical candidate ordering satisfies at least half of the total weight and obstructing any strict half-weight certificate restriction.
An element c belongs to S i if and only if c is one of the three enumerated committee members d i k for k ∈ {0, 1, 2}.
Unfolding the definition of S i as {d i 0, d i 1, d i 2} and expanding the existential quantifier over Fin 3 into cases k = 0, 1, 2 reduces the equivalence to a propositional disjunction, which is verified in both directions.
uses
Finset.mem_insert,Finset.mem_singleton,Fin.exists_fin_succ,Fin.exists_fin_zeroprivate theorem condorcet_tournament_stationary_restriction_obstruction_mem (i : Fin 1771) (c : Fin 23) : c ∈ condorcet_tournament_stationary_restriction_obstruction_S i ↔ ∃ k, condorcet_qr23_selector_member i k = c := by simp only [condorcet_tournament_stationary_restriction_obstruction_S, Finset.mem_insert, Finset.mem_singleton, Fin.exists_fin_succ, Fin.exists_fin_zero] constructor · rintro (h | h | h) <;> simp [h] · rintro (h | h | h | h) <;> simp_all [Fin.succ]
Any candidate c in S i must be d i 0, d i 1, or d i 2.
Unfolding the membership in the explicit three-element set {d i 0, d i 1, d i 2} simplifies the hypothesis to the disjunction of the three equalities.
uses
Finset.mem_insert,Finset.mem_singletonprivate theorem condorcet_tournament_stationary_restriction_obstruction_mem3 (i : Fin 1771) (c : Fin 23) (h : c ∈ condorcet_tournament_stationary_restriction_obstruction_S i) : c = condorcet_qr23_selector_member i 0 ∨ c = condorcet_qr23_selector_member i 1 ∨ c = condorcet_qr23_selector_member i 2 := by simpa only [condorcet_tournament_stationary_restriction_obstruction_S, Finset.mem_insert, Finset.mem_singleton] using h
Each committee S i contains exactly three distinct candidates.
From the precomputed ordering condorcet_qr23_selector_chk, the three members satisfy d i 0 < d i 1 < d i 2, which ensures they are pairwise distinct. A finset with three pairwise distinct elements has cardinality 3.
uses
condorcet_qr23_selector_chk,Finset.card_eq_three.mprprivate theorem condorcet_tournament_stationary_restriction_obstruction_card (i : Fin 1771) : (condorcet_tournament_stationary_restriction_obstruction_S i).card = 3 := by obtain ⟨h01, h12, -⟩ := condorcet_qr23_selector_chk i exact Finset.card_eq_three.mpr ⟨_, _, _, h01.ne, (h01.trans h12).ne, h12.ne, rfl⟩
The outside challenger f i is never a member of the committee S i.
Assuming for contradiction that f i ∈ S i implies f i equals one of the three members d i 0, d i 1, or d i 2. Each case contradicts the distinctness conditions provided by condorcet_qr23_selector_chk.
uses
condorcet_qr23_selector_chk,condorcet_tournament_stationary_restriction_obstruction_mem3private theorem condorcet_tournament_stationary_restriction_obstruction_fnot (i : Fin 1771) : condorcet_qr23_selector_challenger i ∉ condorcet_tournament_stationary_restriction_obstruction_S i := by obtain ⟨-, -, h0, h1, h2, -⟩ := condorcet_qr23_selector_chk i intro h rcases condorcet_tournament_stationary_restriction_obstruction_mem3 i _ h with h | h | h exacts [h0 h, h1 h, h2 h]
The assignment k ↦ d i k is an injective map from Fin 3 to Fin 23.
The precomputed inequalities d i 0 < d i 1 and d i 1 < d i 2 show that k ↦ d i k is strictly monotone on Fin 3, which implies injectivity.
uses
condorcet_qr23_selector_chk,Fin.strictMono_iff_lt_succ.mprprivate theorem condorcet_tournament_stationary_restriction_obstruction_inj (i : Fin 1771) : Function.Injective (condorcet_qr23_selector_member i) := by obtain ⟨h01, h12, -⟩ := condorcet_qr23_selector_chk i refine (Fin.strictMono_iff_lt_succ.mpr fun m => ?_).injective fin_cases m exacts [h01, h12]
Every committee member in S i dominates the challenger f i in the mod 23 quadratic-residue tournament.
For any c ∈ S i, c = d i k for some k ∈ {0, 1, 2}. The precomputed verification condorcet_qr23_selector_chk ensures that (d i k + 23 - f i) % 23 is in the list of quadratic residues modulo 23, which is then converted into finset membership.
uses
condorcet_qr23_selector_chk,condorcet_tournament_stationary_restriction_obstruction_mem,List.mem_cons,List.not_mem_nil,or_false,Finset.mem_insert,Finset.mem_singletonprivate theorem condorcet_tournament_stationary_restriction_obstruction_qr : ∀ i, ∀ c ∈ condorcet_tournament_stationary_restriction_obstruction_S i, (c.val + 23 - (condorcet_qr23_selector_challenger i).val) % 23 ∈ ({1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18} : Finset ℕ) := by intro i c hc obtain ⟨-, -, -, -, -, hq⟩ := condorcet_qr23_selector_chk i obtain ⟨k, rfl⟩ := (condorcet_tournament_stationary_restriction_obstruction_mem i c).mp hc have := hq k simp only [List.mem_cons, List.not_mem_nil, or_false] at this simp only [Finset.mem_insert, Finset.mem_singleton] exact this
Transitioning along next i k replaces member d i k by challenger f i: S (next i k) = insert (f i) ((S i).erase (d i k)).
Case splitting on whether i < 886 applies either condorcet_qr23_selector_trans_lo or condorcet_qr23_selector_trans_hi. In both cases, the precomputed transition certificate confirms that the members of next i k are precisely f i together with the two members of S i other than d i k.
uses
condorcet_qr23_selector_trans_lo,condorcet_qr23_selector_trans_hi,Finset.mem_insert,Finset.mem_erase,condorcet_tournament_stationary_restriction_obstruction_mem,Or.inl,Or.inrprivate theorem condorcet_tournament_stationary_restriction_obstruction_trans (i : Fin 1771) (k : Fin 3) : condorcet_tournament_stationary_restriction_obstruction_S (condorcet_qr23_selector_next i k) = insert (condorcet_qr23_selector_challenger i) ((condorcet_tournament_stationary_restriction_obstruction_S i).erase (condorcet_qr23_selector_member i k)) := by obtain ⟨hA, hB, hC⟩ := (if h : i.val < 886 then condorcet_qr23_selector_trans_lo i h k else condorcet_qr23_selector_trans_hi i (by omega) k) ext c rw [Finset.mem_insert, Finset.mem_erase, condorcet_tournament_stationary_restriction_obstruction_mem, condorcet_tournament_stationary_restriction_obstruction_mem] constructor · rintro ⟨m, rfl⟩ rcases hA m with h | ⟨hne, h⟩ · exact Or.inl h · refine Or.inr ⟨hne, ?_⟩ rcases h with h | h | h exacts [⟨0, h⟩, ⟨1, h⟩, ⟨2, h⟩] · rintro (rfl | ⟨hne, m, rfl⟩) · rcases hB with h | h | h exacts [⟨0, h.symm⟩, ⟨1, h.symm⟩, ⟨2, h.symm⟩] · have hm : m ≠ k := fun e => hne (e ▸ rfl) rcases hC m hm with h | h | h exacts [⟨0, h.symm⟩, ⟨1, h.symm⟩, ⟨2, h.symm⟩]
The local potential inequality holds with the score condition that the challenger is ranked ahead of every committee member.
The precomputed lemma condorcet_qr23_selector_local establishes 23 + 3 * p i ≤ 45 * [f i < d i 0] + ∑ k, p (next i k). Since d i 0 < d i 1 < d i 2, the condition f i < d i 0 is equivalent by transitivity to f i < c for all c ∈ S i, allowing the indicator to be rewritten.
uses
condorcet_qr23_selector_local,condorcet_qr23_selector_chk,condorcet_tournament_stationary_restriction_obstruction_mem,condorcet_tournament_stationary_restriction_obstruction_mem3,if_pos,if_negprivate theorem condorcet_tournament_stationary_restriction_obstruction_local (i : Fin 1771) : 23 + 3 * condorcet_qr23_selector_potential i ≤ 45 * (if ∀ c ∈ condorcet_tournament_stationary_restriction_obstruction_S i, condorcet_qr23_selector_challenger i < c then 1 else 0) + ∑ k : Fin 3, condorcet_qr23_selector_potential (condorcet_qr23_selector_next i k) := by have h := condorcet_qr23_selector_local i obtain ⟨h01, h12, -⟩ := condorcet_qr23_selector_chk i by_cases hc : ∀ c ∈ condorcet_tournament_stationary_restriction_obstruction_S i, condorcet_qr23_selector_challenger i < c · have h0 : condorcet_qr23_selector_challenger i < condorcet_qr23_selector_member i 0 := hc _ ((condorcet_tournament_stationary_restriction_obstruction_mem i _).mpr ⟨0, rfl⟩) rw [if_pos hc]; rwa [if_pos h0] at h · have h0 : ¬ condorcet_qr23_selector_challenger i < condorcet_qr23_selector_member i 0 := fun h0 => hc fun c hc' => by rcases condorcet_tournament_stationary_restriction_obstruction_mem3 i c hc' with e | e | e <;> rw [e] exacts [h0, h0.trans h01, (h0.trans h01).trans h12] rw [if_neg hc]; rwa [if_neg h0] at h
There exist committee, challenger, member, and transition functions satisfying all required structural and tournament properties.
The existential quantifiers are instantiated with the explicit constructions S, f, d, and next, and the six structural claims (cardinality 3, completeness over all 3-element subsets, challenger disjointness, injective indexing, tournament dominance, and transition correctness) are supplied by the helper lemmas proved above.
uses
condorcet_tournament_stationary_restriction_obstruction_card,condorcet_qr23_selector_complete,condorcet_tournament_stationary_restriction_obstruction_fnot,condorcet_tournament_stationary_restriction_obstruction_inj,condorcet_tournament_stationary_restriction_obstruction_mem,condorcet_tournament_stationary_restriction_obstruction_qr,condorcet_tournament_stationary_restriction_obstruction_transtheorem condorcet_tournament_stationary_restriction_obstruction : ∃ (S : Fin 1771 → Finset (Fin 23)) (f : Fin 1771 → Fin 23) (d : Fin 1771 → Fin 3 → Fin 23) (next : Fin 1771 → Fin 3 → Fin 1771), (∀ i, (S i).card=3) ∧ (∀ T : Finset (Fin 23), T.card=3 → ∃ i,S i=T) ∧ (∀ i, f i ∉ S i) ∧ (∀ i, Function.Injective (d i) ∧ ∀ c,c∈S i ↔ ∃ k,d i k=c) ∧ (∀ i, ∀ c∈S i, (c.val+23-(f i).val)%23 ∈ ({1,2,3,4,6,8,9,12,13,16,18} : Finset ℕ)) ∧ (∀ i k,S (next i k)=insert (f i) ((S i).erase (d i k))) ∧ ∀ w : Fin 1771 → ℕ, (∀ j, 3*w j=∑ i,∑ k : Fin 3,if next i k=j then w i else 0) → (∑ i,w i) ≤ 2*∑ i,if ∀ c∈S i,f i<c then w i else 0 := by refine ⟨condorcet_tournament_stationary_restriction_obstruction_S, condorcet_qr23_selector_challenger, condorcet_qr23_selector_member, condorcet_qr23_selector_next, condorcet_tournament_stationary_restriction_obstruction_card, condorcet_qr23_selector_complete, condorcet_tournament_stationary_restriction_obstruction_fnot, fun i => ⟨condorcet_tournament_stationary_restriction_obstruction_inj i, condorcet_tournament_stationary_restriction_obstruction_mem i⟩, condorcet_tournament_stationary_restriction_obstruction_qr, condorcet_tournament_stationary_restriction_obstruction_trans, ?_⟩
Under any stationary weighting w, the canonical ordering satisfies at least half of the total weight: ∑ i, w i ≤ 2 * ∑ i, (if ∀ c ∈ S i, f i < c then w i else 0).
Applying the general stationary telescoping lemma with K = 23 and C = 45 (using 0 < 23 and 45 ≤ 2 * 23) cancels the potential terms via stationarity of w, yielding the bound on total weight in terms of the score sum under the canonical ordering.
uses
condorcet_stationary_telescoping_general,condorcet_tournament_stationary_restriction_obstruction_local,Finset.sum_congr,ite_mul,one_mul,zero_mulintro w hw have h := condorcet_stationary_telescoping_general 1771 45 23 (by norm_num) (by norm_num) condorcet_qr23_selector_next condorcet_qr23_selector_potential (fun i => if ∀ c ∈ condorcet_tournament_stationary_restriction_obstruction_S i, condorcet_qr23_selector_challenger i < c then 1 else 0) w (fun i => condorcet_tournament_stationary_restriction_obstruction_local i) hw have e : (∑ i, (fun i => if ∀ c ∈ condorcet_tournament_stationary_restriction_obstruction_S i, condorcet_qr23_selector_challenger i < c then 1 else 0) i * w i) = ∑ i, if ∀ c ∈ condorcet_tournament_stationary_restriction_obstruction_S i, condorcet_qr23_selector_challenger i < c then w i else 0 := Finset.sum_congr rfl fun i _ => by simp only [ite_mul, one_mul, zero_mul] rw [e] at h exact h
Finset.mem_insert- An element a belongs to insert b s if and only if a = b or a ∈ s.
Finset.mem_singleton- An element b belongs to {a} if and only if b = a.
Fin.exists_fin_succ- An existential quantifier over Fin (n + 1) is equivalent to the predicate holding at 0 or at the successor of some element of Fin n.
Fin.exists_fin_zero- An existential quantifier over Fin 0 is false.
condorcet_qr23_selector_chk- For every committee index i, the members are strictly ordered, the challenger is distinct from all members, and every member dominates the challenger in the mod 23 quadratic-residue tournament.
Finset.card_eq_three.mpr- A finite set with three pairwise distinct elements has cardinality 3.
condorcet_tournament_stationary_restriction_obstruction_mem3- Any element of committee S i is equal to member 0, member 1, or member 2.
Fin.strictMono_iff_lt_succ.mpr- A function on Fin n is strictly monotone if each element is strictly less than its successor.
condorcet_tournament_stationary_restriction_obstruction_mem- An element c belongs to committee S i if and only if c = d i k for some k : Fin 3.
List.mem_cons- An element belongs to a cons list b :: l if and only if it equals b or belongs to l.
List.not_mem_nil- No element belongs to the empty list.
or_false- The proposition p ∨ False is equivalent to p.
condorcet_qr23_selector_trans_lo- For index i < 886, replacing committee member d i k with challenger f i yields the members of committee next i k.
condorcet_qr23_selector_trans_hi- For index i ≥ 886, replacing committee member d i k with challenger f i yields the members of committee next i k.
Finset.mem_erase- An element a belongs to s.erase b if and only if a ≠ b and a ∈ s.
Or.inl- Constructs a proof of a ∨ b from a proof of a.
Or.inr- Constructs a proof of a ∨ b from a proof of b.
condorcet_qr23_selector_local- For each committee i, the potential satisfies 23 + 3 * p i ≤ 45 * (if f i < member i 0 then 1 else 0) + ∑ k, p (next i k).
if_pos- If a condition c is true, the expression if c then t else e reduces to t.
if_neg- If a condition c is false, the expression if c then t else e reduces to e.
condorcet_tournament_stationary_restriction_obstruction_card- Every committee S i has cardinality 3.
condorcet_qr23_selector_complete- Every 3-element subset of 23 candidates is represented by S i for some index i.
condorcet_tournament_stationary_restriction_obstruction_fnot- The challenger f i is not a member of committee S i.
condorcet_tournament_stationary_restriction_obstruction_inj- The member enumeration d i is an injective function on Fin 3.
condorcet_tournament_stationary_restriction_obstruction_qr- Every member of committee S i dominates the challenger in the quadratic-residue tournament modulo 23.
condorcet_tournament_stationary_restriction_obstruction_trans- The committee at next i k equals S i with member d i k evicted and challenger f i inserted.
condorcet_stationary_telescoping_general- If a local potential inequality holds with constants K > 0 and C ≤ 2 * K, any stationary weight w satisfies ∑ i, w i ≤ 2 * ∑ i, score i * w i.
condorcet_tournament_stationary_restriction_obstruction_local- The local potential inequality holds with the score condition that the challenger precedes all committee members.
Finset.sum_congr- Congruence for finite sums: identical terms on identical domains yield equal sums.
ite_mul- Multiplication distributes over an if-then-else: (if P then a else b) * c = if P then a * c else b * c.
one_mul- One is the left identity for multiplication: 1 * a = a.
zero_mul- Zero multiplied by any element is zero: 0 * a = 0.
- The selector, transitions, and local potential inequality rely on precomputed explicit data tables and decision procedures verified in auxiliary lemmas (such as condorcet_qr23_selector_chk, condorcet_qr23_selector_trans_lo, condorcet_qr23_selector_trans_hi, and condorcet_qr23_selector_local).
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.
private def condorcet_tournament_stationary_restriction_obstruction_S (i : Fin 1771) : Finset (Fin 23) := {condorcet_qr23_selector_member i 0, condorcet_qr23_selector_member i 1, condorcet_qr23_selector_member i 2}private theorem condorcet_tournament_stationary_restriction_obstruction_mem (i : Fin 1771) (c : Fin 23) : c ∈ condorcet_tournament_stationary_restriction_obstruction_S i ↔ ∃ k, condorcet_qr23_selector_member i k = c := by simp only [condorcet_tournament_stationary_restriction_obstruction_S, Finset.mem_insert, Finset.mem_singleton, Fin.exists_fin_succ, Fin.exists_fin_zero] constructor · rintro (h | h | h) <;> simp [h] · rintro (h | h | h | h) <;> simp_all [Fin.succ]private theorem condorcet_tournament_stationary_restriction_obstruction_mem3 (i : Fin 1771) (c : Fin 23) (h : c ∈ condorcet_tournament_stationary_restriction_obstruction_S i) : c = condorcet_qr23_selector_member i 0 ∨ c = condorcet_qr23_selector_member i 1 ∨ c = condorcet_qr23_selector_member i 2 := by simpa only [condorcet_tournament_stationary_restriction_obstruction_S, Finset.mem_insert, Finset.mem_singleton] using hprivate theorem condorcet_tournament_stationary_restriction_obstruction_card (i : Fin 1771) : (condorcet_tournament_stationary_restriction_obstruction_S i).card = 3 := by obtain ⟨h01, h12, -⟩ := condorcet_qr23_selector_chk i exact Finset.card_eq_three.mpr ⟨_, _, _, h01.ne, (h01.trans h12).ne, h12.ne, rfl⟩private theorem condorcet_tournament_stationary_restriction_obstruction_fnot (i : Fin 1771) : condorcet_qr23_selector_challenger i ∉ condorcet_tournament_stationary_restriction_obstruction_S i := by obtain ⟨-, -, h0, h1, h2, -⟩ := condorcet_qr23_selector_chk i intro h rcases condorcet_tournament_stationary_restriction_obstruction_mem3 i _ h with h | h | h exacts [h0 h, h1 h, h2 h]private theorem condorcet_tournament_stationary_restriction_obstruction_inj (i : Fin 1771) : Function.Injective (condorcet_qr23_selector_member i) := by obtain ⟨h01, h12, -⟩ := condorcet_qr23_selector_chk i refine (Fin.strictMono_iff_lt_succ.mpr fun m => ?_).injective fin_cases m exacts [h01, h12]private theorem condorcet_tournament_stationary_restriction_obstruction_qr : ∀ i, ∀ c ∈ condorcet_tournament_stationary_restriction_obstruction_S i, (c.val + 23 - (condorcet_qr23_selector_challenger i).val) % 23 ∈ ({1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18} : Finset ℕ) := by intro i c hc obtain ⟨-, -, -, -, -, hq⟩ := condorcet_qr23_selector_chk i obtain ⟨k, rfl⟩ := (condorcet_tournament_stationary_restriction_obstruction_mem i c).mp hc have := hq k simp only [List.mem_cons, List.not_mem_nil, or_false] at this simp only [Finset.mem_insert, Finset.mem_singleton] exact thisprivate theorem condorcet_tournament_stationary_restriction_obstruction_trans (i : Fin 1771) (k : Fin 3) : condorcet_tournament_stationary_restriction_obstruction_S (condorcet_qr23_selector_next i k) = insert (condorcet_qr23_selector_challenger i) ((condorcet_tournament_stationary_restriction_obstruction_S i).erase (condorcet_qr23_selector_member i k)) := by obtain ⟨hA, hB, hC⟩ := (if h : i.val < 886 then condorcet_qr23_selector_trans_lo i h k else condorcet_qr23_selector_trans_hi i (by omega) k) ext c rw [Finset.mem_insert, Finset.mem_erase, condorcet_tournament_stationary_restriction_obstruction_mem, condorcet_tournament_stationary_restriction_obstruction_mem] constructor · rintro ⟨m, rfl⟩ rcases hA m with h | ⟨hne, h⟩ · exact Or.inl h · refine Or.inr ⟨hne, ?_⟩ rcases h with h | h | h exacts [⟨0, h⟩, ⟨1, h⟩, ⟨2, h⟩] · rintro (rfl | ⟨hne, m, rfl⟩) · rcases hB with h | h | h exacts [⟨0, h.symm⟩, ⟨1, h.symm⟩, ⟨2, h.symm⟩] · have hm : m ≠ k := fun e => hne (e ▸ rfl) rcases hC m hm with h | h | h exacts [⟨0, h.symm⟩, ⟨1, h.symm⟩, ⟨2, h.symm⟩]private theorem condorcet_tournament_stationary_restriction_obstruction_local (i : Fin 1771) : 23 + 3 * condorcet_qr23_selector_potential i ≤ 45 * (if ∀ c ∈ condorcet_tournament_stationary_restriction_obstruction_S i, condorcet_qr23_selector_challenger i < c then 1 else 0) + ∑ k : Fin 3, condorcet_qr23_selector_potential (condorcet_qr23_selector_next i k) := by have h := condorcet_qr23_selector_local i obtain ⟨h01, h12, -⟩ := condorcet_qr23_selector_chk i by_cases hc : ∀ c ∈ condorcet_tournament_stationary_restriction_obstruction_S i, condorcet_qr23_selector_challenger i < c · have h0 : condorcet_qr23_selector_challenger i < condorcet_qr23_selector_member i 0 := hc _ ((condorcet_tournament_stationary_restriction_obstruction_mem i _).mpr ⟨0, rfl⟩) rw [if_pos hc]; rwa [if_pos h0] at h · have h0 : ¬ condorcet_qr23_selector_challenger i < condorcet_qr23_selector_member i 0 := fun h0 => hc fun c hc' => by rcases condorcet_tournament_stationary_restriction_obstruction_mem3 i c hc' with e | e | e <;> rw [e] exacts [h0, h0.trans h01, (h0.trans h01).trans h12] rw [if_neg hc]; rwa [if_neg h0] at htheorem condorcet_tournament_stationary_restriction_obstruction : ∃ (S : Fin 1771 → Finset (Fin 23)) (f : Fin 1771 → Fin 23) (d : Fin 1771 → Fin 3 → Fin 23) (next : Fin 1771 → Fin 3 → Fin 1771), (∀ i, (S i).card=3) ∧ (∀ T : Finset (Fin 23), T.card=3 → ∃ i,S i=T) ∧ (∀ i, f i ∉ S i) ∧ (∀ i, Function.Injective (d i) ∧ ∀ c,c∈S i ↔ ∃ k,d i k=c) ∧ (∀ i, ∀ c∈S i, (c.val+23-(f i).val)%23 ∈ ({1,2,3,4,6,8,9,12,13,16,18} : Finset ℕ)) ∧ (∀ i k,S (next i k)=insert (f i) ((S i).erase (d i k))) ∧ ∀ w : Fin 1771 → ℕ, (∀ j, 3*w j=∑ i,∑ k : Fin 3,if next i k=j then w i else 0) → (∑ i,w i) ≤ 2*∑ i,if ∀ c∈S i,f i<c then w i else 0 := by refine ⟨condorcet_tournament_stationary_restriction_obstruction_S, condorcet_qr23_selector_challenger, condorcet_qr23_selector_member, condorcet_qr23_selector_next, condorcet_tournament_stationary_restriction_obstruction_card, condorcet_qr23_selector_complete, condorcet_tournament_stationary_restriction_obstruction_fnot, fun i => ⟨condorcet_tournament_stationary_restriction_obstruction_inj i, condorcet_tournament_stationary_restriction_obstruction_mem i⟩, condorcet_tournament_stationary_restriction_obstruction_qr, condorcet_tournament_stationary_restriction_obstruction_trans, ?_⟩ intro w hw have h := condorcet_stationary_telescoping_general 1771 45 23 (by norm_num) (by norm_num) condorcet_qr23_selector_next condorcet_qr23_selector_potential (fun i => if ∀ c ∈ condorcet_tournament_stationary_restriction_obstruction_S i, condorcet_qr23_selector_challenger i < c then 1 else 0) w (fun i => condorcet_tournament_stationary_restriction_obstruction_local i) hw have e : (∑ i, (fun i => if ∀ c ∈ condorcet_tournament_stationary_restriction_obstruction_S i, condorcet_qr23_selector_challenger i < c then 1 else 0) i * w i) = ∑ i, if ∀ c ∈ condorcet_tournament_stationary_restriction_obstruction_S i, condorcet_qr23_selector_challenger i < c then w i else 0 := Finset.sum_congr rfl fun i _ => by simp only [ite_mul, one_mul, zero_mul] rw [e] at h exact h