AFTD Auto-Formalizing Theoretical Domains

condorcet_product_clone_uniform_half_obstruction

theoremverified

For a root map on ordered triples of m candidates, suppose each root has exactly m squared preimages under uniform iid sampling and the identity ranking satisfies strictly more than half the claims. For every positive k, there is a lifted root map on m times k candidates, represented as base-candidate and clone pairs, with exactly (m times k) squared preimages per root and strictly more than half the claims satisfied by the injective block rank k times base position plus clone position. The lifted root has the original root as its base coordinate. This lift carries the first sampled clone coordinate to the root and can depend on the ordered tuple; permutation or underlying-set invariance is not asserted.

Statement

theorem condorcet_product_clone_uniform_half_obstruction
    (m k : ℕ) (hk : 0 < k) (f : Fin m → Fin m → Fin m → Fin m)
    (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)) :
    ∃ F : (Fin m × Fin k) → (Fin m × Fin k) → (Fin m × Fin k) → (Fin m × Fin k),
      (∀ x y z,(F x y z).1=f x.1 y.1 z.1) ∧
      (∀ r,Fintype.card (condorcet_product_clone_root_fiber F r)=(m*k)^2) ∧
      Function.Injective (fun x : Fin m × Fin k => k*x.1.val+x.2.val) ∧
      (m*k)^3 < 2*Fintype.card (condorcet_product_clone_root_good F (fun x => k*x.1.val+x.2.val))
Source
IN-348 supporting lemma for the limitation of raw product-invariance certificates in OP-19. The base finite diagnostic is condorcet_product_uniform_half_score_obstruction. This general lift shows that arbitrarily small individual candidate masses alone do not repair the pointwise inference for ordered-tuple root maps. It supplies no election counterexample and does not obstruct selector-adapted weights or another fixed point. No research advance is claimed.
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 1

The proof, explained

To lift a root map f on m candidates to m * k candidates while preserving root uniformity and the Condorcet score, each candidate is represented as a pair of a base candidate and a clone index in Fin k. The lifted root map applies f to the base coordinates and copies the clone coordinate of the first candidate in the triple. This ensures each lifted root fiber is in bijection with the base fiber times (Fin k)², so fibers retain size (m * k)². Under the injective block ranking k * base + clone, every good base triple lifts to k³ good triples, preserving the strict majority of satisfied claims.

  1. The fiber of a lifted root (r₁, r₂) under the cloned root map is equivalent to the Cartesian product of the base fiber and two copies of the clone set.

    For any triple t in the fiber of (r₁, r₂), the lifted root definition gives f(t₁.1, t₂.1, t₃.1) = r₁ and t₁.2 = r₂. The second coordinate of the first candidate is uniquely fixed to r₂, while the clone coordinates t₂.2 and t₃.2 can be chosen arbitrarily. The equivalence maps t to ((t₁.1, t₂.1, t₃.1), t₂.2, t₃.2); its left inverse reconstructs t by restoring t₁.2 using Subtype.ext, congrArg Prod.snd, and Prod.ext, while the right inverse is definitionally trivial.

    lines 27–31

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

      left_inv t := by
        apply Subtype.ext
        have h := congrArg Prod.snd t.property
        exact Prod.ext (Prod.ext rfl h.symm) rfl
      right_inv t := by rfl
  2. The fiber cardinality of each lifted root is the original fiber cardinality multiplied by the square of the clone set size.

    Rewriting by Fintype.card_congr using the fiber equivalence condorcet_product_clone_clone_fiber_equiv shows that the fiber of (r₁, r₂) has size |fiber(f, r₁)| * |B| * |B|. The simplifier evaluates the product cardinality and uses pow_two to express |B| * |B| as |B|².

    lines 33–38

    uses Fintype.card_congr, condorcet_product_clone_clone_fiber_equiv, pow_two

    theorem condorcet_product_clone_clone_fiber_card {A B : Type*} [Fintype A] [Fintype B]
        [DecidableEq A] [DecidableEq B] (f : A → A → A → A) (r : A × B) :
        Fintype.card (condorcet_product_clone_root_fiber (condorcet_product_clone_clone_root f) r) =
          Fintype.card (condorcet_product_clone_root_fiber f r.1) * (Fintype.card B)^2 := by
      rw [Fintype.card_congr (condorcet_product_clone_clone_fiber_equiv f r)]
      simp [pow_two]
  3. Any good base triple together with three arbitrary clone coordinates forms a good triple under the block ranking. automation

    Given a good triple t for f—meaning rank(f(t)) < rank(tᵢ) for each i ∈ {1, 2, 3}—and clone indices c₁, c₂, c₃ < k, the lifted root has rank k * rank(f(t)) + c₁. For the first candidate, k * rank(f(t)) + c₁ < k * rank(t₁) + c₁ holds directly. For the other two candidates, since rank(f(t)) + 1 ≤ rank(tᵢ) and c₁ < k ≤ k + cᵢ, nlinarith verifies the strict inequalities k * rank(f(t)) + c₁ < k * rank(tᵢ) + cᵢ.

    lines 40–60

    def condorcet_product_clone_clone_good_embedding {A : Type*} [Fintype A]
        (k : ℕ) (f : A → A → A → A) (rank : A → ℕ) :
        condorcet_product_clone_root_good f rank × (Fin k × Fin k × Fin k) ↪
          condorcet_product_clone_root_good (condorcet_product_clone_clone_root f)
            (fun x : A × Fin k => k * 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 hb₁ := t.2.1.isLt
          have hb₂ := t.2.2.1.isLt
          have hb₃ := t.2.2.2.isLt
          change
            k * rank (f t.1.val.1 t.1.val.2.1 t.1.val.2.2) + t.2.1.val <
              k * rank t.1.val.1 + t.2.1.val ∧
            k * rank (f t.1.val.1 t.1.val.2.1 t.1.val.2.2) + t.2.1.val <
              k * rank t.1.val.2.1 + t.2.2.1.val ∧
            k * rank (f t.1.val.1 t.1.val.2.1 t.1.val.2.2) + t.2.1.val <
              k * rank t.1.val.2.2 + t.2.2.2.val
          constructor
          · nlinarith
          constructor <;> nlinarith⟩
  4. The map sending a good base triple and three clone coordinates to a lifted good triple is injective.

    If two inputs x and y have the same lifted triple, congrArg Subtype.val extracts equality of the underlying triples in (A × Fin k)³. Projecting onto base coordinates recovers equality of the good base triples via Subtype.ext and Prod.ext, while projecting onto clone coordinates recovers equality of the clone index triples via Prod.ext.

    lines 61–72

    uses congrArg, Subtype.val, Prod.ext, Subtype.ext

      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))
    
  5. The number of good triples for the cloned root map is at least the number of original good triples multiplied by k³.

    Applying Fintype.card_le_of_injective to the embedding condorcet_product_clone_clone_good_embedding bounds the lifted good triples from below by the cardinality of good(f) × (Fin k)³. The simplifier expands this product cardinality using Fintype.card_prod, pow_succ, and mul_assoc into |good(f)| * k³.

    lines 73–82

    uses Fintype.card_le_of_injective, condorcet_product_clone_clone_good_embedding, Fintype.card_prod, pow_succ, mul_assoc

    theorem condorcet_product_clone_clone_good_card {A : Type*} [Fintype A] [DecidableEq A]
        (k : ℕ) (f : A → A → A → A) (rank : A → ℕ) :
        Fintype.card (condorcet_product_clone_root_good f rank) * k^3 ≤
          Fintype.card (condorcet_product_clone_root_good (condorcet_product_clone_clone_root (B := Fin k) f)
            (fun x => k * rank x.1 + x.2.val)) := by
      have h := Fintype.card_le_of_injective
        (condorcet_product_clone_clone_good_embedding k f rank).toFun
        (condorcet_product_clone_clone_good_embedding k f rank).injective
      simpa [Fintype.card_prod, pow_succ, mul_assoc] using h
    
  6. The cloned root map witness preserves the base root in its first coordinate.

    We provide condorcet_product_clone_clone_root f as the witness lifted root map F. By definition, (F(x, y, z)).1 = f(x.1, y.1, z.1), so this base projection property holds by reflexivity (rfl), leaving the three goals for fiber size, ranking injectivity, and score bound.

    lines 83–92

    uses condorcet_product_clone_clone_root

    theorem condorcet_product_clone_uniform_half_obstruction
        (m k : ℕ) (hk : 0 < k) (f : Fin m → Fin m → Fin m → Fin m)
        (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)) :
        ∃ F : (Fin m × Fin k) → (Fin m × Fin k) → (Fin m × Fin k) → (Fin m × Fin k),
          (∀ x y z,(F x y z).1=f x.1 y.1 z.1) ∧
          (∀ r,Fintype.card (condorcet_product_clone_root_fiber F r)=(m*k)^2) ∧
          Function.Injective (fun x : Fin m × Fin k => k*x.1.val+x.2.val) ∧
          (m*k)^3 < 2*Fintype.card (condorcet_product_clone_root_good F (fun x => k*x.1.val+x.2.val)) := by
      refine ⟨condorcet_product_clone_clone_root f,fun _ _ _ => rfl,?_,?_,?_⟩
  7. Every root of the lifted map has exactly (m * k)² preimages under uniform sampling. automation

    For any lifted root r, condorcet_product_clone_clone_fiber_card rewrites its fiber size to |fiber(f, r.1)| * |Fin k|². Substituting the uniformity hypothesis huniform = m² and Fintype.card_fin k = k, the ring tactic verifies m² * k² = (m * k)².

    lines 93–95

    uses condorcet_product_clone_clone_fiber_card, Fintype.card_fin

      · intro r
        rw [condorcet_product_clone_clone_fiber_card,huniform,Fintype.card_fin]
        ring
  8. The block ranking function (x₁, x₂) ↦ k * x₁ + x₂ is injective.

    Injectivity is established by embedding into Fin (m * k) via finProdFinEquiv. By Fin.ext, equality of elements in Fin (m * k) reduces to equality of natural numbers, and simpa with add_comm aligns the equivalence definition x₂ + k * x₁ with the rank formula k * x₁ + x₂ to conclude from the assumption.

    lines 96–99

    uses finProdFinEquiv, Fin.ext, Equiv.coe_fn_mk, add_comm

      · intro x y h
        apply finProdFinEquiv.injective
        apply Fin.ext
        simpa only [finProdFinEquiv,Equiv.coe_fn_mk,add_comm] using h
  9. Strictly more than half of all (m * k)³ candidate triples are good for the lifted root map under the block ranking.

    From condorcet_product_clone_clone_good_card with the identity ranking Fin.val, we have |good(f)| * k³ ≤ |good(F)|. A calculation shows (m * k)³ = m³ * k³ by mul_pow, which is strictly less than 2 * |good(f)| * k³ by Nat.mul_lt_mul_of_pos_right and pow_pos since m³ < 2 * |good(f)| and k > 0. Regrouping by ring and multiplying the cardinality inequality by 2 via Nat.mul_le_mul_left yields (m * k)³ < 2 * |good(F)|.

    lines 100–107

    uses condorcet_product_clone_clone_good_card, Fin.val, mul_pow, Nat.mul_lt_mul_of_pos_right, pow_pos, condorcet_product_clone_clone_root, Nat.mul_le_mul_left

      · have hc := condorcet_product_clone_clone_good_card k f Fin.val
        calc
          (m*k)^3 = m^3*k^3 := mul_pow m k 3
          _ < (2*Fintype.card (condorcet_product_clone_root_good f Fin.val))*k^3 :=
            Nat.mul_lt_mul_of_pos_right hscore (pow_pos hk 3)
          _ = 2*(Fintype.card (condorcet_product_clone_root_good f Fin.val)*k^3) := by ring
          _ ≤ 2*Fintype.card (condorcet_product_clone_root_good (condorcet_product_clone_clone_root (B := Fin k) f)
            (fun x : Fin m × Fin k => k*x.1.val+x.2.val)) := Nat.mul_le_mul_left 2 hc
Subtype.ext
Two elements of a subtype are equal if their underlying values are equal.
congrArg
Functions preserve equality of their arguments.
Prod.snd
The projection function extracting the second element of an ordered pair.
Prod.ext
Two pairs are equal if their first and second components are respectively equal.
Fintype.card_congr
Equivalent finite types have equal cardinality.
condorcet_product_clone_clone_fiber_equiv
The preimage of a root under the cloned root map is equivalent to the preimage under the original root map times two copies of the clone type.
pow_two
The square of an element equals the product of the element with itself.
Subtype.val
The projection mapping an element of a subtype to its underlying value.
Fintype.card_le_of_injective
An injective map between finite types implies the domain has cardinality at most the codomain.
condorcet_product_clone_clone_good_embedding
An embedding from the product of good triples and three clone coordinates into the good triples of the cloned root map.
Fintype.card_prod
The cardinality of a Cartesian product of finite types is the product of their cardinalities.
pow_succ
The successor power formula a^(n+1) = a^n * a in a monoid.
mul_assoc
Multiplication in a semigroup is associative.
condorcet_product_clone_clone_root
The lifted root map on pairs that applies the original root map to base coordinates and retains the clone coordinate of the first candidate.
condorcet_product_clone_clone_fiber_card
The fiber cardinality of a root under the cloned root map is the fiber cardinality under the base map times the square of the clone size.
Fintype.card_fin
The cardinality of Fin n is n.
finProdFinEquiv
The canonical equivalence between Fin m × Fin n and Fin (m * n).
Fin.ext
Two elements of Fin n are equal if their underlying natural numbers are equal.
Equiv.coe_fn_mk
Coercing an equivalence constructed via Equiv.mk to a function yields its forward function.
add_comm
Addition is commutative.
condorcet_product_clone_clone_good_card
The number of good triples for the cloned root map is at least the number of original good triples times k cubed.
Fin.val
The coercion from Fin n to its underlying natural number.
mul_pow
The power of a product is the product of powers in a commutative monoid: (a * b)^n = a^n * b^n.
Nat.mul_lt_mul_of_pos_right
Strict inequality of natural numbers is preserved when multiplying on the right by a strictly positive number.
pow_pos
A strictly positive element raised to any natural power is strictly positive.
Nat.mul_le_mul_left
Multiplying both sides of a non-strict inequality of natural numbers on the left by a constant preserves the inequality.

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 10000-- This lift permits the root to depend on the ordered tuple. The finite-- 23-candidate witness is stronger: there the root depends only on its set.def condorcet_product_clone_clone_root {A B : Type*} (f : A → A → A → A)    (x y z : A × B) : A × B := (f x.1 y.1 z.1, x.2)abbrev condorcet_product_clone_root_fiber {A : Type*} (f : A → A → A → A) (r : A) :=  {t : A × A × A // f t.1 t.2.1 t.2.2 = r}abbrev condorcet_product_clone_root_good {A : Type*} (f : A → A → A → A) (rank : A → ℕ) :=  {t : A × A × A // rank (f t.1 t.2.1 t.2.2) < rank t.1 ∧    rank (f t.1 t.2.1 t.2.2) < rank t.2.1 ∧    rank (f t.1 t.2.1 t.2.2) < rank t.2.2}def condorcet_product_clone_clone_fiber_equiv {A B : Type*} (f : A → A → A → A) (r : A × B) :    condorcet_product_clone_root_fiber (condorcet_product_clone_clone_root f) r ≃      condorcet_product_clone_root_fiber f r.1 × (B × B) 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.2.2.2)  invFun t := ⟨((t.1.val.1,r.2),(t.1.val.2.1,t.2.1),(t.1.val.2.2,t.2.2)),    Prod.ext t.1.property rfl⟩  left_inv t := by    apply Subtype.ext    have h := congrArg Prod.snd t.property    exact Prod.ext (Prod.ext rfl h.symm) rfl  right_inv t := by rfltheorem condorcet_product_clone_clone_fiber_card {A B : Type*} [Fintype A] [Fintype B]    [DecidableEq A] [DecidableEq B] (f : A → A → A → A) (r : A × B) :    Fintype.card (condorcet_product_clone_root_fiber (condorcet_product_clone_clone_root f) r) =      Fintype.card (condorcet_product_clone_root_fiber f r.1) * (Fintype.card B)^2 := by  rw [Fintype.card_congr (condorcet_product_clone_clone_fiber_equiv f r)]  simp [pow_two]def condorcet_product_clone_clone_good_embedding {A : Type*} [Fintype A]    (k : ℕ) (f : A → A → A → A) (rank : A → ℕ) :    condorcet_product_clone_root_good f rank × (Fin k × Fin k × Fin k) ↪      condorcet_product_clone_root_good (condorcet_product_clone_clone_root f)        (fun x : A × Fin k => k * 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 hb₁ := t.2.1.isLt      have hb₂ := t.2.2.1.isLt      have hb₃ := t.2.2.2.isLt      change        k * rank (f t.1.val.1 t.1.val.2.1 t.1.val.2.2) + t.2.1.val <          k * rank t.1.val.1 + t.2.1.val ∧        k * rank (f t.1.val.1 t.1.val.2.1 t.1.val.2.2) + t.2.1.val <          k * rank t.1.val.2.1 + t.2.2.1.val ∧        k * rank (f t.1.val.1 t.1.val.2.1 t.1.val.2.2) + t.2.1.val <          k * rank t.1.val.2.2 + t.2.2.2.val      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_product_clone_clone_good_card {A : Type*} [Fintype A] [DecidableEq A]    (k : ℕ) (f : A → A → A → A) (rank : A → ℕ) :    Fintype.card (condorcet_product_clone_root_good f rank) * k^3 ≤      Fintype.card (condorcet_product_clone_root_good (condorcet_product_clone_clone_root (B := Fin k) f)        (fun x => k * rank x.1 + x.2.val)) := by  have h := Fintype.card_le_of_injective    (condorcet_product_clone_clone_good_embedding k f rank).toFun    (condorcet_product_clone_clone_good_embedding k f rank).injective  simpa [Fintype.card_prod, pow_succ, mul_assoc] using htheorem condorcet_product_clone_uniform_half_obstruction    (m k : ℕ) (hk : 0 < k) (f : Fin m → Fin m → Fin m → Fin m)    (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)) :    ∃ F : (Fin m × Fin k) → (Fin m × Fin k) → (Fin m × Fin k) → (Fin m × Fin k),      (∀ x y z,(F x y z).1=f x.1 y.1 z.1) ∧      (∀ r,Fintype.card (condorcet_product_clone_root_fiber F r)=(m*k)^2) ∧      Function.Injective (fun x : Fin m × Fin k => k*x.1.val+x.2.val) ∧      (m*k)^3 < 2*Fintype.card (condorcet_product_clone_root_good F (fun x => k*x.1.val+x.2.val)) := by  refine ⟨condorcet_product_clone_clone_root f,fun _ _ _ => rfl,?_,?_,?_⟩  · intro r    rw [condorcet_product_clone_clone_fiber_card,huniform,Fintype.card_fin]    ring  · intro x y h    apply finProdFinEquiv.injective    apply Fin.ext    simpa only [finProdFinEquiv,Equiv.coe_fn_mk,add_comm] using h  · have hc := condorcet_product_clone_clone_good_card k f Fin.val    calc      (m*k)^3 = m^3*k^3 := mul_pow m k 3      _ < (2*Fintype.card (condorcet_product_clone_root_good f Fin.val))*k^3 :=        Nat.mul_lt_mul_of_pos_right hscore (pow_pos hk 3)      _ = 2*(Fintype.card (condorcet_product_clone_root_good f Fin.val)*k^3) := by ring      _ ≤ 2*Fintype.card (condorcet_product_clone_root_good (condorcet_product_clone_clone_root (B := Fin k) f)        (fun x : Fin m × Fin k => k*x.1.val+x.2.val)) := Nat.mul_le_mul_left 2 hc
See it in the graphDiscuss this resultChallenge it