condorcet_product_clone_uniform_half_obstruction
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 thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- TotalPreorderA total preorder: a preorder where
- Used by 1
- condorcet_coherent_clone_uniform_half_obstructionSuppose a root selector on m candidates is invariant under input permutations and the two multiplicity patterns of a two-candidate sample,…
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.
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.
uses
Subtype.ext,congrArg,Prod.snd,Prod.extleft_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
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|².
uses
Fintype.card_congr,condorcet_product_clone_clone_fiber_equiv,pow_twotheorem 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]
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ᵢ.
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⟩
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.
uses
congrArg,Subtype.val,Prod.ext,Subtype.extinj' := 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))
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³.
uses
Fintype.card_le_of_injective,condorcet_product_clone_clone_good_embedding,Fintype.card_prod,pow_succ,mul_assoctheorem 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
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.
uses
condorcet_product_clone_clone_roottheorem 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,?_,?_,?_⟩
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)².
uses
condorcet_product_clone_clone_fiber_card,Fintype.card_fin· intro r rw [condorcet_product_clone_clone_fiber_card,huniform,Fintype.card_fin] ring
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.
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
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)|.
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.
- The lifted root construction sets the clone coordinate of the root to that of the first candidate in the triple, making the lift sensitive to the order of the candidates rather than permutation-invariant.
- Verifying that lifting a good triple produces a good triple under the block ranking relies on non-linear arithmetic automation (`nlinarith`).
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 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