AFTD Auto-Formalizing Theoretical Domains

condorcet_coherent_clone_uniform_half_obstruction

theoremverified

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

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.

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

    lines 19–23

    uses condorcet_coherent_clone_shift, Prod.ext_iff

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

    lines 24–30

    uses condorcet_coherent_clone_mean, eq_comm

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

    lines 31–35

    uses condorcet_coherent_clone_mean

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

    lines 36–48

    uses condorcet_coherent_clone_shift_eq, condorcet_coherent_clone_mean, condorcet_coherent_clone_shift, mul_one

    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]
    
  5. 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), ...).

    lines 49–62

    uses Prod.ext, condorcet_coherent_clone_mean_shift, condorcet_coherent_clone_root, condorcet_coherent_clone_shift, add_comm

    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.symm
    
  6. 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.

    lines 63–94

    uses Prod.ext, condorcet_coherent_clone_root, Subtype.ext, congrArg, Prod.snd, condorcet_coherent_clone_mean

    def 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
    
  7. 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)².

    lines 95–101

    uses Fintype.card_congr, condorcet_coherent_clone_fiber_equiv, Fintype.card_fun, ZMod.card, pow_two

    theorem 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]
    
  8. 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.

    lines 102–133

    uses congrArg, Subtype.val, Prod.ext

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

    lines 134–156

    uses condorcet_coherent_clone_root, condorcet_coherent_clone_group, Fintype.card_fun, ZMod.card

    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,?_,?_,?_,?_,?_⟩
  10. 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.

    lines 157–161

    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⟩
  11. 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.

    lines 162–165

    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)
  12. 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)².

    lines 166–168

    uses condorcet_coherent_clone_fiber_card

      · intro r
        rw [condorcet_coherent_clone_fiber_card,huniform]
        ring
  13. 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.

    lines 169–178

    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'
  14. 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.

    lines 179–191

    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

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