condorcet_coherent_clone_uniform_half_obstruction
Suppose a root selector on m candidates is invariant under input permutations and the two multiplicity patterns of a two-candidate sample, has uniform iid output, and has strictly more than half of its claims satisfied by the identity ranking. For every natural k it has a lift with five-to-the-k clones of each candidate that preserves the base root, permutation invariance, duplicate-pattern coherence, and uniform output, together with an injective block ranking still satisfying strictly more than half the claims. The lift is a selector depending only on the sampled underlying set. Together with the proved23-candidate base witness this gives such obstructions with arbitrarily small uniform candidate masses. It obstructs a pointwise inference from raw iid uniform weights and flat marginals; it is not a failed election or a limitation of all selector-adapted weights.
Statement
theorem condorcet_coherent_clone_uniform_half_obstruction (m k : ℕ) (f : Fin m → Fin m → Fin m → Fin m) (hsym : ∀ a b c,f a b c=f b a c ∧ f a b c=f a c b) (hdup : ∀ a b,f a a b=f a b b) (huniform : ∀ r : Fin m,Fintype.card (condorcet_product_clone_root_fiber f r)=m^2) (hscore : m^3 < 2*Fintype.card (condorcet_product_clone_root_good f Fin.val)) : let G := condorcet_coherent_clone_group k let ρ := Fintype.equivFin G ∃ F : (Fin m × G) → (Fin m × G) → (Fin m × G) → (Fin m × G), (∀ x y z,(F x y z).1=f x.1 y.1 z.1) ∧ (∀ x y z,F x y z=F y x z ∧ F x y z=F x z y) ∧ (∀ x y,F x x y=F x y y) ∧ (∀ r,Fintype.card (condorcet_product_clone_root_fiber F r)=(m*5^k)^2) ∧ Function.Injective (fun x : Fin m × G => 5^k*x.1.val+(ρ x.2).val) ∧ (m*5^k)^3 < 2*Fintype.card (condorcet_product_clone_root_good F (fun x => 5^k*x.1.val+(ρ x.2).val))
- Source
- IN-348 method diagnostic for OP-19, extending condorcet_product_clone_uniform_half_obstruction to fully permutation- and duplicate-coherent selectors. The base witness is condorcet_product_uniform_half_score_obstruction. Related product fixed-point method: https://theorydish.blog/2026/09/11/condorcet-quintets-a-proof-from-the-book/ . The finite mean-of-distinct-samples construction was audited in experiment8690; only this exact Lean statement is asserted. No election counterexample, general dimension bound, or research advance is claimed.
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- condorcet_product_clone_uniform_half_obstructionFor a root map on ordered triples of m candidates, suppose each root has exactly m squared preimages under uniform iid sampling and the…
- condorcet_product_uniform_half_score_obstructionThere is a strict regular tournament on 23 candidates, every candidate beating exactly 11 others, and a root map for ordered triples. Each…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
The proof, explained
To lift an obstruction to Condorcet consistency from an m-candidate root selector f to an m·5^k-candidate selector, each candidate is expanded into a cluster of 5^k clones indexed by the group G = (ZMod 5)^k. The lifted selector evaluates f on the base candidates and averages the clone components via an affine mean whose coefficients (3 for duplicated inputs, 2 for distinct inputs) are chosen so that 6 ≡ 1 mod 5 guarantees equivariance under uniform shifts by G. Shift equivariance ensures that every fiber has size |f⁻¹(r)| · (5^k)², preserving uniform output distribution across all candidate-clone pairs. Under a lexicographic block ranking, every good triple for the base selector lifts to (5^k)³ good triples for the clone selector, strictly preserving the condition that more than half of all triples are good.
Translation by t in the clone component is an equivalence on candidate-clone pairs. automation
Unfolding the definition of shifting and taking the componentwise equality of pairs shows that shifting by t preserves and reflects equality.
uses
condorcet_coherent_clone_shift,Prod.ext_ifftheorem condorcet_coherent_clone_shift_eq {A : Type*} {k : ℕ} (t : condorcet_coherent_clone_group k) (x y : A × condorcet_coherent_clone_group k) : condorcet_coherent_clone_shift t x=condorcet_coherent_clone_shift t y ↔ x=y := by simp [condorcet_coherent_clone_shift,Prod.ext_iff]
The clone mean function is symmetric under all permutations of its three arguments. automation
By splitting on the equality of inputs among the three pairs (x = y, x = z, y = z), each branch simplifies to a linear combination in ZMod 5 where ring arithmetic and commutativity of addition confirm invariance under swapping the first two or last two arguments.
uses
condorcet_coherent_clone_mean,eq_commtheorem condorcet_coherent_clone_mean_sym {A : Type*} [DecidableEq A] {k : ℕ} (x y z : A × condorcet_coherent_clone_group k) : condorcet_coherent_clone_mean x y z=condorcet_coherent_clone_mean y x z ∧ condorcet_coherent_clone_mean x y z=condorcet_coherent_clone_mean x z y := by by_cases hxy : x=y <;> by_cases hxz : x=z <;> by_cases hyz : y=z all_goals simp_all [condorcet_coherent_clone_mean,eq_comm] <;> ring <;> simp_all
The clone mean satisfies duplicate-pattern coherence: mean(x, x, y) = mean(x, y, y). automation
A case analysis on whether x = y shows that both sides evaluate to x.2 if x = y, and both evaluate to 3 * (x.2 + y.2) if x ≠ y.
uses
condorcet_coherent_clone_meantheorem condorcet_coherent_clone_mean_duplicate {A : Type*} [DecidableEq A] {k : ℕ} (x y : A × condorcet_coherent_clone_group k) : condorcet_coherent_clone_mean x x y=condorcet_coherent_clone_mean x y y := by by_cases h : x=y <;> simp [condorcet_coherent_clone_mean,h]
The clone mean is equivariant under uniform shifts by any group element t. automation
After expanding the shift on all three arguments, the equality conditions are invariant under translation. In every branch, factoring out t yields a coefficient of 6 · t = 1 · t in ZMod 5 because 6 ≡ 1 mod 5 (for two identical elements, 3 · 2t = 6t; for three distinct elements, 2 · 3t = 6t), which equals the unshifted mean plus t.
uses
condorcet_coherent_clone_shift_eq,condorcet_coherent_clone_mean,condorcet_coherent_clone_shift,mul_onetheorem condorcet_coherent_clone_mean_shift {A : Type*} [DecidableEq A] {k : ℕ} (t : condorcet_coherent_clone_group k) (x y z : A × condorcet_coherent_clone_group k) : condorcet_coherent_clone_mean (condorcet_coherent_clone_shift t x) (condorcet_coherent_clone_shift t y) (condorcet_coherent_clone_shift t z)= condorcet_coherent_clone_mean x y z+t := by have heq (u v : A × condorcet_coherent_clone_group k) : ((u.1,u.2+t) : A × condorcet_coherent_clone_group k)=(v.1,v.2+t) ↔ u=v := condorcet_coherent_clone_shift_eq t u v simp only [condorcet_coherent_clone_mean,condorcet_coherent_clone_shift] simp only [heq] split_ifs <;> ext i <;> simp_all <;> ring_nf all_goals simp only [show (6 : ZMod 5)=1 from by decide,mul_one]
The lifted root selector condorcet_coherent_clone_root f x y z equals (f x.1 y.1 z.1, mean x y z).
The first component is f(x.1, y.1, z.1) by definition. For the second component, shifting (x.1, 0), (y.1, y.2 - x.2), (z.1, z.2 - x.2) by x.2 recovers the original inputs x, y, z, and applying shift equivariance gives mean(x, y, z) = x.2 + mean((x.1, 0), ...).
uses
Prod.ext,condorcet_coherent_clone_mean_shift,condorcet_coherent_clone_root,condorcet_coherent_clone_shift,add_commdef condorcet_coherent_clone_root {A : Type*} [DecidableEq A] {k : ℕ} (f : A → A → A → A) (x y z : A × condorcet_coherent_clone_group k) := (f x.1 y.1 z.1, x.2+condorcet_coherent_clone_mean (x.1,0) (y.1,y.2-x.2) (z.1,z.2-x.2)) theorem condorcet_coherent_clone_root_eq {A : Type*} [DecidableEq A] {k : ℕ} (f : A → A → A → A) (x y z : A × condorcet_coherent_clone_group k) : condorcet_coherent_clone_root f x y z=(f x.1 y.1 z.1,condorcet_coherent_clone_mean x y z) := by apply Prod.ext · rfl · have h := condorcet_coherent_clone_mean_shift x.2 (x.1,0) (y.1,y.2-x.2) (z.1,z.2-x.2) simpa [condorcet_coherent_clone_root,condorcet_coherent_clone_shift,add_comm] using h.symm
The fiber of the lifted selector at (r.1, r.2) is canonically in bijection with the base fiber at r.1 crossed with G × G.
Given any input triple in the lifted fiber, subtract the first clone index from the second and third to obtain two free group offsets; the base candidate triple lies in the base fiber at r.1. Conversely, given a base triple and two offsets, the equivariance of the clone mean uniquely determines the first clone index so that the mean equals r.2. Checking both directions confirms this is a two-sided inverse.
uses
Prod.ext,condorcet_coherent_clone_root,Subtype.ext,congrArg,Prod.snd,condorcet_coherent_clone_meandef condorcet_coherent_clone_fiber_equiv {A : Type*} [DecidableEq A] {k : ℕ} (f : A → A → A → A) (r : A × condorcet_coherent_clone_group k) : condorcet_product_clone_root_fiber (condorcet_coherent_clone_root f) r ≃ condorcet_product_clone_root_fiber f r.1 × (condorcet_coherent_clone_group k × condorcet_coherent_clone_group k) where toFun t := (⟨(t.val.1.1,t.val.2.1.1,t.val.2.2.1), congrArg Prod.fst t.property⟩,t.val.2.1.2-t.val.1.2,t.val.2.2.2-t.val.1.2) invFun t := let g := condorcet_coherent_clone_mean (t.1.val.1,0) (t.1.val.2.1,t.2.1) (t.1.val.2.2,t.2.2) let a := r.2-g ⟨((t.1.val.1,a),(t.1.val.2.1,a+t.2.1),(t.1.val.2.2,a+t.2.2)),by apply Prod.ext t.1.property simp [condorcet_coherent_clone_root,a,g]⟩ left_inv t := by apply Subtype.ext have h := congrArg Prod.snd t.property dsimp [condorcet_coherent_clone_root] at h have hg : r.2-condorcet_coherent_clone_mean (t.val.1.1,0) (t.val.2.1.1,t.val.2.1.2-t.val.1.2) (t.val.2.2.1,t.val.2.2.2-t.val.1.2)=t.val.1.2 := by rw [← h] abel dsimp rw [hg] simp right_inv t := by apply Prod.ext · apply Subtype.ext rfl · dsimp simp
Each fiber of the lifted selector has cardinality equal to |f⁻¹(r.1)| · (5^k)². automation
The cardinality of the fiber matches the cardinality of the product fiber by the established equivalence. Since |G| = 5^k, the product of two copies of G has size (5^k)².
uses
Fintype.card_congr,condorcet_coherent_clone_fiber_equiv,Fintype.card_fun,ZMod.card,pow_twotheorem condorcet_coherent_clone_fiber_card {A : Type*} [Fintype A] [DecidableEq A] {k : ℕ} (f : A → A → A → A) (r : A × condorcet_coherent_clone_group k) : Fintype.card (condorcet_product_clone_root_fiber (condorcet_coherent_clone_root f) r)= Fintype.card (condorcet_product_clone_root_fiber f r.1)*(5^k)^2 := by rw [Fintype.card_congr (condorcet_coherent_clone_fiber_equiv f r)] simp [Fintype.card_fun,ZMod.card,pow_two]
Good triples of the base selector cross with B³ injectively embed into good triples of the lifted selector.
Under the lexicographical block ranking rank(c, b) = |B| · rank(c) + ρ(b), the leading term |B| · rank(c) dominates since the clone offset satisfies ρ(b) < |B|. Thus whenever the base root strictly beats all three inputs in base rank, the lifted root strictly beats all three lifted inputs regardless of the clone values. Injectivity follows componentwise from the injectivity of the projections.
uses
congrArg,Subtype.val,Prod.extdef condorcet_coherent_clone_good_embedding {A B : Type*} [Fintype A] [Fintype B] (f : A → A → A → A) (F : (A × B) → (A × B) → (A × B) → (A × B)) (hF : ∀ x y z,(F x y z).1=f x.1 y.1 z.1) (rank : A → ℕ) (ρ : B ≃ Fin (Fintype.card B)) : condorcet_product_clone_root_good f rank × (B × B × B) ↪ condorcet_product_clone_root_good F (fun x => Fintype.card B*rank x.1+(ρ x.2).val) where toFun t := ⟨((t.1.val.1,t.2.1),(t.1.val.2.1,t.2.2.1),(t.1.val.2.2,t.2.2.2)),by obtain ⟨h₁,h₂,h₃⟩ := t.1.property have hr := (ρ (F (t.1.val.1,t.2.1) (t.1.val.2.1,t.2.2.1) (t.1.val.2.2,t.2.2.2)).2).isLt change Fintype.card B*rank (F _ _ _).1+_ < Fintype.card B*rank t.1.val.1+_ ∧ Fintype.card B*rank (F _ _ _).1+_ < Fintype.card B*rank t.1.val.2.1+_ ∧ Fintype.card B*rank (F _ _ _).1+_ < Fintype.card B*rank t.1.val.2.2+_ rw [hF] constructor · nlinarith constructor <;> nlinarith⟩ inj' := by intro x y h have hval := congrArg Subtype.val h apply Prod.ext · apply Subtype.ext exact Prod.ext (congrArg (fun t => t.1.1) hval) (Prod.ext (congrArg (fun t => t.2.1.1) hval) (congrArg (fun t => t.2.2.1) hval)) · exact Prod.ext (congrArg (fun t => t.1.2) hval) (Prod.ext (congrArg (fun t => t.2.1.2) hval) (congrArg (fun t => t.2.2.2) hval))
Setup of the lifted selector F on m · 5^k candidates preserving the base root.
Define F as condorcet_coherent_clone_root on candidates Fin m × G, where G = (Fin k → ZMod 5) has cardinality 5^k. The candidate projection of F matches f by construction.
uses
condorcet_coherent_clone_root,condorcet_coherent_clone_group,Fintype.card_fun,ZMod.cardtheorem condorcet_coherent_clone_uniform_half_obstruction (m k : ℕ) (f : Fin m → Fin m → Fin m → Fin m) (hsym : ∀ a b c,f a b c=f b a c ∧ f a b c=f a c b) (hdup : ∀ a b,f a a b=f a b b) (huniform : ∀ r : Fin m,Fintype.card (condorcet_product_clone_root_fiber f r)=m^2) (hscore : m^3 < 2*Fintype.card (condorcet_product_clone_root_good f Fin.val)) : let G := condorcet_coherent_clone_group k let ρ := Fintype.equivFin G ∃ F : (Fin m × G) → (Fin m × G) → (Fin m × G) → (Fin m × G), (∀ x y z,(F x y z).1=f x.1 y.1 z.1) ∧ (∀ x y z,F x y z=F y x z ∧ F x y z=F x z y) ∧ (∀ x y,F x x y=F x y y) ∧ (∀ r,Fintype.card (condorcet_product_clone_root_fiber F r)=(m*5^k)^2) ∧ Function.Injective (fun x : Fin m × G => 5^k*x.1.val+(ρ x.2).val) ∧ (m*5^k)^3 < 2*Fintype.card (condorcet_product_clone_root_good F (fun x => 5^k*x.1.val+(ρ x.2).val)) := by classical dsimp only let F := @condorcet_coherent_clone_root (Fin m) _ k f have hF : ∀ x y z,(F x y z).1=f x.1 y.1 z.1 := fun _ _ _ => rfl have hcard : Fintype.card (condorcet_coherent_clone_group k)=5^k := by simp [condorcet_coherent_clone_group,Fintype.card_fun,ZMod.card] refine ⟨F,hF,?_,?_,?_,?_,?_⟩
The lifted selector F is invariant under all permutations of its three inputs.
The first component is invariant because f is permutation-invariant by hypothesis; the second component is invariant because the clone mean is invariant under transpositions of inputs.
uses
condorcet_coherent_clone_root_eq,Prod.ext,condorcet_coherent_clone_mean_sym· intro x y z dsimp [F] simp only [condorcet_coherent_clone_root_eq] exact ⟨Prod.ext (hsym _ _ _).1 (condorcet_coherent_clone_mean_sym x y z).1, Prod.ext (hsym _ _ _).2 (condorcet_coherent_clone_mean_sym x y z).2⟩
The lifted selector F satisfies duplicate-pattern coherence: F(x, x, y) = F(x, y, y).
Both components satisfy the property: f(x.1, x.1, y.1) = f(x.1, y.1, y.1) by the duplicate hypothesis on f, and mean(x, x, y) = mean(x, y, y) by duplicate coherence of the clone mean.
uses
condorcet_coherent_clone_root_eq,Prod.ext,condorcet_coherent_clone_mean_duplicate· intro x y dsimp [F] simp only [condorcet_coherent_clone_root_eq] exact Prod.ext (hdup _ _) (condorcet_coherent_clone_mean_duplicate x y)
The lifted selector F has uniform fiber cardinality (m · 5^k)². automation
By the fiber cardinality formula, |F⁻¹(r)| = |f⁻¹(r.1)| · (5^k)². Since f is uniform with fiber size m², this evaluates to m² · (5^k)² = (m · 5^k)².
uses
condorcet_coherent_clone_fiber_card· intro r rw [condorcet_coherent_clone_fiber_card,huniform] ring
The block ranking on Fin m × G is injective.
The block ranking encodes a pair of finite indices via the standard bijection finProdFinEquiv between Fin m × Fin (5^k) and Fin (m · 5^k). Since this product equivalence and the identification of G with Fin (5^k) are injective, the ranking function is injective.
uses
finProdFinEquiv,Fin.ext,congrArg,Fintype.equivFin· intro x y h have he : finProdFinEquiv (x.1,Fintype.equivFin _ x.2)= finProdFinEquiv (y.1,Fintype.equivFin _ y.2) := by apply Fin.ext simpa only [finProdFinEquiv,Equiv.coe_fn_mk,hcard,add_comm] using h have he' := finProdFinEquiv.injective he apply Prod.ext · exact congrArg (fun p : Fin m × Fin (Fintype.card (condorcet_coherent_clone_group k)) => p.1) he' · apply (Fintype.equivFin (condorcet_coherent_clone_group k)).injective exact congrArg (fun p : Fin m × Fin (Fintype.card (condorcet_coherent_clone_group k)) => p.2) he'
Strictly more than half of all triples remain good for the lifted selector F.
Using the embedding of good triples, the number of good triples for F is at least the number of good triples for f multiplied by (5^k)³. Multiplying the base hypothesis m³ < 2 · |good(f)| by (5^k)³ yields (m · 5^k)³ < 2 · |good(f)| · (5^k)³ ≤ 2 · |good(F)|, establishing the half-obstruction inequality.
uses
Fintype.card_le_of_injective,condorcet_coherent_clone_good_embedding,Fin.val,Fintype.equivFin,Fintype.card_prod,pow_succ,pow_zero,mul_one,one_mul,mul_assoc,mul_pow,Nat.mul_lt_mul_of_pos_right,Nat.mul_le_mul_left· have hc := Fintype.card_le_of_injective (condorcet_coherent_clone_good_embedding f F hF Fin.val (Fintype.equivFin _)).toFun (condorcet_coherent_clone_good_embedding f F hF Fin.val (Fintype.equivFin _)).injective have hc' : Fintype.card (condorcet_product_clone_root_good f Fin.val)*(5^k)^3 ≤ Fintype.card (condorcet_product_clone_root_good F (fun x => 5^k*x.1.val+(Fintype.equivFin _ x.2).val)) := by simpa only [Fintype.card_prod,hcard,pow_succ,pow_zero,mul_one,one_mul,mul_assoc] using hc calc (m*5^k)^3 = m^3*(5^k)^3 := mul_pow _ _ _ _ < (2*Fintype.card (condorcet_product_clone_root_good f Fin.val))*(5^k)^3 := Nat.mul_lt_mul_of_pos_right hscore (by positivity) _ = 2*(Fintype.card (condorcet_product_clone_root_good f Fin.val)*(5^k)^3) := by ring _ ≤ _ := Nat.mul_le_mul_left 2 hc'
add_comm- Addition in an additive commutative group or magma is commutative.
condorcet_coherent_clone_group- The abelian group (Fin k → ZMod 5) of size 5^k used to index clones.
condorcet_coherent_clone_fiber_card- The cardinality of each fiber of the lifted selector is the base fiber cardinality multiplied by (5^k)^2.
condorcet_coherent_clone_fiber_equiv- A bijection between the fiber of the lifted root selector at r and the product of the base fiber at r.1 with two independent copies of the clone group.
condorcet_coherent_clone_good_embedding- An injective embedding from good triples of the base selector crossed with three clone indices into the good triples of the lifted selector under the block ranking.
condorcet_coherent_clone_mean- A symmetric averaging function on three candidate-clone pairs with values in the clone group (Fin k → ZMod 5).
condorcet_coherent_clone_mean_duplicate- The clone mean satisfies mean(x, x, y) = mean(x, y, y) for all inputs x and y.
condorcet_coherent_clone_mean_shift- The clone mean shifts by t when all three inputs are shifted by t.
condorcet_coherent_clone_mean_sym- The clone mean is invariant under transposition of the first two or last two inputs.
condorcet_coherent_clone_root- The lifted root selector, defined by applying the base selector to the candidate components and the clone mean to the clone components.
condorcet_coherent_clone_root_eq- The lifted root selector equals (f(x.1, y.1, z.1), mean(x, y, z)).
condorcet_coherent_clone_shift- The translation of a candidate-clone pair by a group element t in the clone coordinate.
condorcet_coherent_clone_shift_eq- Translating candidate-clone pairs by a fixed group element is an injective operation.
congrArg- Applying a function to equal inputs produces equal outputs.
eq_comm- Equality is symmetric: a = b is equivalent to b = a.
Fin.ext- Two elements of Fin n are equal if and only if their underlying natural values are equal.
Fin.val- The natural number value of an index in Fin n.
finProdFinEquiv- The canonical equivalence between Fin m × Fin n and Fin (m * n).
Fintype.card_congr- Equivalent finite types have the same number of elements.
Fintype.card_fun- The cardinality of the function type A → B is |B|^|A|.
Fintype.card_le_of_injective- An injective map between finite types implies the cardinality of the domain is at most that of the codomain.
Fintype.card_prod- The cardinality of the Cartesian product of two finite types is the product of their cardinalities.
Fintype.equivFin- The canonical bijection between any finite type and Fin of its cardinality.
mul_assoc- Associativity of multiplication: (a * b) * c = a * (b * c).
mul_one- Multiplying any element by 1 leaves it unchanged.
mul_pow- The power of a product is the product of the powers: (a * b)^n = a^n * b^n.
Nat.mul_le_mul_left- Multiplying an inequality of natural numbers by a non-negative integer on the left preserves weak inequality.
Nat.mul_lt_mul_of_pos_right- Multiplying a strict inequality of natural numbers by a positive integer on the right preserves strict inequality.
one_mul- Multiplying 1 by any element leaves it unchanged.
pow_zero- Any element to the zeroth power equals 1.
pow_succ- Inductive step for exponentiation: a^(n + 1) = a^n * a.
pow_two- The square of an element equals the element multiplied by itself: a^2 = a * a.
Prod.ext- Two ordered pairs are equal if their first components are equal and their second components are equal.
Prod.ext_iff- Two ordered pairs are equal if and only if both their first and second components are equal.
Prod.snd- The second projection of an ordered pair.
Subtype.ext- Two elements of a subtype are equal if their underlying values are equal.
Subtype.val- The underlying value of a subtype element.
ZMod.card- The cardinality of ZMod n is n.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open Finsetopen scoped BigOperatorsset_option maxHeartbeats 4000000set_option maxRecDepth 10000abbrev condorcet_coherent_clone_group (k : ℕ) := Fin k → ZMod 5def condorcet_coherent_clone_mean {A : Type*} [DecidableEq A] {k : ℕ} (x y z : A × condorcet_coherent_clone_group k) : condorcet_coherent_clone_group k := if x=y then if y=z then x.2 else 3*(x.2+z.2) else if x=z then 3*(x.2+y.2) else if y=z then 3*(x.2+y.2) else 2*(x.2+y.2+z.2)def condorcet_coherent_clone_shift {A : Type*} {k : ℕ} (t : condorcet_coherent_clone_group k) (x : A × condorcet_coherent_clone_group k) := (x.1,x.2+t)theorem condorcet_coherent_clone_shift_eq {A : Type*} {k : ℕ} (t : condorcet_coherent_clone_group k) (x y : A × condorcet_coherent_clone_group k) : condorcet_coherent_clone_shift t x=condorcet_coherent_clone_shift t y ↔ x=y := by simp [condorcet_coherent_clone_shift,Prod.ext_iff]theorem condorcet_coherent_clone_mean_sym {A : Type*} [DecidableEq A] {k : ℕ} (x y z : A × condorcet_coherent_clone_group k) : condorcet_coherent_clone_mean x y z=condorcet_coherent_clone_mean y x z ∧ condorcet_coherent_clone_mean x y z=condorcet_coherent_clone_mean x z y := by by_cases hxy : x=y <;> by_cases hxz : x=z <;> by_cases hyz : y=z all_goals simp_all [condorcet_coherent_clone_mean,eq_comm] <;> ring <;> simp_alltheorem condorcet_coherent_clone_mean_duplicate {A : Type*} [DecidableEq A] {k : ℕ} (x y : A × condorcet_coherent_clone_group k) : condorcet_coherent_clone_mean x x y=condorcet_coherent_clone_mean x y y := by by_cases h : x=y <;> simp [condorcet_coherent_clone_mean,h]theorem condorcet_coherent_clone_mean_shift {A : Type*} [DecidableEq A] {k : ℕ} (t : condorcet_coherent_clone_group k) (x y z : A × condorcet_coherent_clone_group k) : condorcet_coherent_clone_mean (condorcet_coherent_clone_shift t x) (condorcet_coherent_clone_shift t y) (condorcet_coherent_clone_shift t z)= condorcet_coherent_clone_mean x y z+t := by have heq (u v : A × condorcet_coherent_clone_group k) : ((u.1,u.2+t) : A × condorcet_coherent_clone_group k)=(v.1,v.2+t) ↔ u=v := condorcet_coherent_clone_shift_eq t u v simp only [condorcet_coherent_clone_mean,condorcet_coherent_clone_shift] simp only [heq] split_ifs <;> ext i <;> simp_all <;> ring_nf all_goals simp only [show (6 : ZMod 5)=1 from by decide,mul_one]def condorcet_coherent_clone_root {A : Type*} [DecidableEq A] {k : ℕ} (f : A → A → A → A) (x y z : A × condorcet_coherent_clone_group k) := (f x.1 y.1 z.1, x.2+condorcet_coherent_clone_mean (x.1,0) (y.1,y.2-x.2) (z.1,z.2-x.2))theorem condorcet_coherent_clone_root_eq {A : Type*} [DecidableEq A] {k : ℕ} (f : A → A → A → A) (x y z : A × condorcet_coherent_clone_group k) : condorcet_coherent_clone_root f x y z=(f x.1 y.1 z.1,condorcet_coherent_clone_mean x y z) := by apply Prod.ext · rfl · have h := condorcet_coherent_clone_mean_shift x.2 (x.1,0) (y.1,y.2-x.2) (z.1,z.2-x.2) simpa [condorcet_coherent_clone_root,condorcet_coherent_clone_shift,add_comm] using h.symmdef condorcet_coherent_clone_fiber_equiv {A : Type*} [DecidableEq A] {k : ℕ} (f : A → A → A → A) (r : A × condorcet_coherent_clone_group k) : condorcet_product_clone_root_fiber (condorcet_coherent_clone_root f) r ≃ condorcet_product_clone_root_fiber f r.1 × (condorcet_coherent_clone_group k × condorcet_coherent_clone_group k) where toFun t := (⟨(t.val.1.1,t.val.2.1.1,t.val.2.2.1), congrArg Prod.fst t.property⟩,t.val.2.1.2-t.val.1.2,t.val.2.2.2-t.val.1.2) invFun t := let g := condorcet_coherent_clone_mean (t.1.val.1,0) (t.1.val.2.1,t.2.1) (t.1.val.2.2,t.2.2) let a := r.2-g ⟨((t.1.val.1,a),(t.1.val.2.1,a+t.2.1),(t.1.val.2.2,a+t.2.2)),by apply Prod.ext t.1.property simp [condorcet_coherent_clone_root,a,g]⟩ left_inv t := by apply Subtype.ext have h := congrArg Prod.snd t.property dsimp [condorcet_coherent_clone_root] at h have hg : r.2-condorcet_coherent_clone_mean (t.val.1.1,0) (t.val.2.1.1,t.val.2.1.2-t.val.1.2) (t.val.2.2.1,t.val.2.2.2-t.val.1.2)=t.val.1.2 := by rw [← h] abel dsimp rw [hg] simp right_inv t := by apply Prod.ext · apply Subtype.ext rfl · dsimp simptheorem condorcet_coherent_clone_fiber_card {A : Type*} [Fintype A] [DecidableEq A] {k : ℕ} (f : A → A → A → A) (r : A × condorcet_coherent_clone_group k) : Fintype.card (condorcet_product_clone_root_fiber (condorcet_coherent_clone_root f) r)= Fintype.card (condorcet_product_clone_root_fiber f r.1)*(5^k)^2 := by rw [Fintype.card_congr (condorcet_coherent_clone_fiber_equiv f r)] simp [Fintype.card_fun,ZMod.card,pow_two]def condorcet_coherent_clone_good_embedding {A B : Type*} [Fintype A] [Fintype B] (f : A → A → A → A) (F : (A × B) → (A × B) → (A × B) → (A × B)) (hF : ∀ x y z,(F x y z).1=f x.1 y.1 z.1) (rank : A → ℕ) (ρ : B ≃ Fin (Fintype.card B)) : condorcet_product_clone_root_good f rank × (B × B × B) ↪ condorcet_product_clone_root_good F (fun x => Fintype.card B*rank x.1+(ρ x.2).val) where toFun t := ⟨((t.1.val.1,t.2.1),(t.1.val.2.1,t.2.2.1),(t.1.val.2.2,t.2.2.2)),by obtain ⟨h₁,h₂,h₃⟩ := t.1.property have hr := (ρ (F (t.1.val.1,t.2.1) (t.1.val.2.1,t.2.2.1) (t.1.val.2.2,t.2.2.2)).2).isLt change Fintype.card B*rank (F _ _ _).1+_ < Fintype.card B*rank t.1.val.1+_ ∧ Fintype.card B*rank (F _ _ _).1+_ < Fintype.card B*rank t.1.val.2.1+_ ∧ Fintype.card B*rank (F _ _ _).1+_ < Fintype.card B*rank t.1.val.2.2+_ rw [hF] constructor · nlinarith constructor <;> nlinarith⟩ inj' := by intro x y h have hval := congrArg Subtype.val h apply Prod.ext · apply Subtype.ext exact Prod.ext (congrArg (fun t => t.1.1) hval) (Prod.ext (congrArg (fun t => t.2.1.1) hval) (congrArg (fun t => t.2.2.1) hval)) · exact Prod.ext (congrArg (fun t => t.1.2) hval) (Prod.ext (congrArg (fun t => t.2.1.2) hval) (congrArg (fun t => t.2.2.2) hval))theorem condorcet_coherent_clone_uniform_half_obstruction (m k : ℕ) (f : Fin m → Fin m → Fin m → Fin m) (hsym : ∀ a b c,f a b c=f b a c ∧ f a b c=f a c b) (hdup : ∀ a b,f a a b=f a b b) (huniform : ∀ r : Fin m,Fintype.card (condorcet_product_clone_root_fiber f r)=m^2) (hscore : m^3 < 2*Fintype.card (condorcet_product_clone_root_good f Fin.val)) : let G := condorcet_coherent_clone_group k let ρ := Fintype.equivFin G ∃ F : (Fin m × G) → (Fin m × G) → (Fin m × G) → (Fin m × G), (∀ x y z,(F x y z).1=f x.1 y.1 z.1) ∧ (∀ x y z,F x y z=F y x z ∧ F x y z=F x z y) ∧ (∀ x y,F x x y=F x y y) ∧ (∀ r,Fintype.card (condorcet_product_clone_root_fiber F r)=(m*5^k)^2) ∧ Function.Injective (fun x : Fin m × G => 5^k*x.1.val+(ρ x.2).val) ∧ (m*5^k)^3 < 2*Fintype.card (condorcet_product_clone_root_good F (fun x => 5^k*x.1.val+(ρ x.2).val)) := by classical dsimp only let F := @condorcet_coherent_clone_root (Fin m) _ k f have hF : ∀ x y z,(F x y z).1=f x.1 y.1 z.1 := fun _ _ _ => rfl have hcard : Fintype.card (condorcet_coherent_clone_group k)=5^k := by simp [condorcet_coherent_clone_group,Fintype.card_fun,ZMod.card] refine ⟨F,hF,?_,?_,?_,?_,?_⟩ · intro x y z dsimp [F] simp only [condorcet_coherent_clone_root_eq] exact ⟨Prod.ext (hsym _ _ _).1 (condorcet_coherent_clone_mean_sym x y z).1, Prod.ext (hsym _ _ _).2 (condorcet_coherent_clone_mean_sym x y z).2⟩ · intro x y dsimp [F] simp only [condorcet_coherent_clone_root_eq] exact Prod.ext (hdup _ _) (condorcet_coherent_clone_mean_duplicate x y) · intro r rw [condorcet_coherent_clone_fiber_card,huniform] ring · intro x y h have he : finProdFinEquiv (x.1,Fintype.equivFin _ x.2)= finProdFinEquiv (y.1,Fintype.equivFin _ y.2) := by apply Fin.ext simpa only [finProdFinEquiv,Equiv.coe_fn_mk,hcard,add_comm] using h have he' := finProdFinEquiv.injective he apply Prod.ext · exact congrArg (fun p : Fin m × Fin (Fintype.card (condorcet_coherent_clone_group k)) => p.1) he' · apply (Fintype.equivFin (condorcet_coherent_clone_group k)).injective exact congrArg (fun p : Fin m × Fin (Fintype.card (condorcet_coherent_clone_group k)) => p.2) he' · have hc := Fintype.card_le_of_injective (condorcet_coherent_clone_good_embedding f F hF Fin.val (Fintype.equivFin _)).toFun (condorcet_coherent_clone_good_embedding f F hF Fin.val (Fintype.equivFin _)).injective have hc' : Fintype.card (condorcet_product_clone_root_good f Fin.val)*(5^k)^3 ≤ Fintype.card (condorcet_product_clone_root_good F (fun x => 5^k*x.1.val+(Fintype.equivFin _ x.2).val)) := by simpa only [Fintype.card_prod,hcard,pow_succ,pow_zero,mul_one,one_mul,mul_assoc] using hc calc (m*5^k)^3 = m^3*(5^k)^3 := mul_pow _ _ _ _ < (2*Fintype.card (condorcet_product_clone_root_good f Fin.val))*(5^k)^3 := Nat.mul_lt_mul_of_pos_right hscore (by positivity) _ = 2*(Fintype.card (condorcet_product_clone_root_good f Fin.val)*(5^k)^3) := by ring _ ≤ _ := Nat.mul_le_mul_left 2 hc'