subset_transfer_two_comparisons
Suppose an algorithm on k objects succeeds in minimum selection with probability at least p on every strict order and uses at most two ordinary comparisons. For every n >= k, there exists an algorithm on n objects with the same comparison budget that succeeds with probability at least k * p / n on every strict order.
Statement
theorem subset_transfer_two_comparisons {k n : ℕ} (hk : 0 < k) (hkn : k ≤ n)
(A : ComparisonAlgorithm k 2) (p : ℝ)
(hp : ∀ (L : LinearOrder (Fin k)), p ≤ comparison_algorithm_success_prob hk A L) :
∃ A' : ComparisonAlgorithm n 2, ∀ (hn : 0 < n) (L : LinearOrder (Fin n)),
((k : ℝ) * p) / (n : ℝ) ≤ comparison_algorithm_success_prob hn A' L- Formalizes
- arXiv:2610.34762 Lemma 6
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- ComparisonAlgorithmA comparison algorithm on n objects with comparison budget c specifies, for each linear order on Fin n, an output probability distribution…
- comparison_algorithm_success_probThe probability that a comparison algorithm A on n objects selects the minimum element under linear order L.
- embedding_range_contains_fractionFor any fixed element m of Fin n and any 0 < k <= n, the fraction of embeddings from Fin k into Fin n whose range contains m equals k / n.
- lift_linear_order_min_eqIf the global minimum of a linear order on Fin n lies in the range of an embedding f from Fin k to Fin n with f(j) = m, then j is the…
- linearOrderMinThe minimum element of Fin n with respect to a linear order L, for n > 0.
Read back from the Lean
For any natural numbers $k$ and $n$ such that $0 < k$ and $k \le n$, any comparison algorithm $A$ on $k$ elements with budget 2, and any real number $p$ such that for all linear orders $L$ on $\mathrm{Fin}(k)$, $p$ is less than or equal to the success probability of $A$ on $L$ (with proof $hk$), there exists a comparison algorithm $A'$ on $n$ elements with budget 2 such that for every proof $hn : 0 < n$ and every linear order $L$ on $\mathrm{Fin}(n)$, $(k \cdot p) / n$ is less than or equal to the success probability of $A'$ on $L$ (with proof $hn$).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To transfer an algorithm A on k elements to an algorithm A' on n elements (n ≥ k), we construct A' by choosing a uniformly random embedding f : Fin k ↪ Fin n, running A on the sub-order induced by f, and mapping the chosen element back into Fin n. The minimum element m of Fin n is selected whenever it falls in the image of f and A correctly identifies the minimum on the induced k-element order. By symmetry, m belongs to the image of f with probability k / n, and whenever it does, A finds it with probability at least p. Averaging over all embeddings proves that A' succeeds with probability at least (k * p) / n.
The set of embeddings from Fin k to Fin n is nonempty, so its cardinality N is strictly positive.
Since k ≤ n, mapping each index i ∈ Fin k to the element in Fin n with the identical numerical value defines a valid injection. This witness shows that the type of embeddings Fin k ↪ Fin n is nonempty, and hence its cardinality N is a strictly positive natural number, which remains strictly positive and nonzero when coerced to ℝ.
uses
lt_of_lt_of_le,Fin.ext,congrArg,Fin.val,Fintype.card_pos_iff.mpr,ne_of_gtclassical have hNnat : 0 < Fintype.card (Fin k ↪ Fin n) := by have hne : Nonempty (Fin k ↪ Fin n) := ⟨⟨fun i => ⟨i.1, lt_of_lt_of_le i.2 hkn⟩, fun a b h => Fin.ext (by simpa using congrArg Fin.val h)⟩⟩ exact Fintype.card_pos_iff.mpr hne have hNpos : (0 : ℝ) < (Fintype.card (Fin k ↪ Fin n) : ℝ) := by exact_mod_cast hNnat have hNne : (Fintype.card (Fin k ↪ Fin n) : ℝ) ≠ 0 := ne_of_gt hNpos
Construct candidate algorithm A' on n elements by uniformly averaging A over all embeddings from Fin k into Fin n.
For any linear order L on Fin n and element i ∈ Fin n, algorithm A' outputs i with probability equal to the average, over all N embeddings f : Fin k ↪ Fin n, of the probability that A selects the preimage of i under the induced pullback order f* L (or 0 if i is not in the image of f).
uses
LinearOrder.lift'refine ⟨⟨fun L i => (∑ f : Fin k ↪ Fin n, ∑ j : Fin k, if f j = i then A.prob (LinearOrder.lift' f.toFun f.injective) j else 0) / (Fintype.card (Fin k ↪ Fin n) : ℝ), ?_, ?_⟩, ?_⟩
The probability assigned to each element by A' is non-negative.
For any order L and element i, every summand in the numerator is either A.prob(...) ≥ 0 (by non-negativity of A) or 0 ≥ 0. Because the denominator N is strictly positive, the quotient is non-negative.
uses
div_nonneg,le_of_lt,Finset.sum_nonneg,le_refl· intro L i apply div_nonneg _ (le_of_lt hNpos) apply Finset.sum_nonneg intro f _ apply Finset.sum_nonneg intro j _ split_ifs · exact A.nonneg _ _ · exact le_refl 0
For any linear order L on Fin n, the probabilities assigned by A' sum to 1.
Summing over all elements i ∈ Fin n and swapping the order of summation, the sum over i collapses because f(j) = i holds for exactly one i. The sum over j ∈ Fin k then evaluates to 1 by the total probability condition of A. Finally, summing 1 over all N embeddings gives N, and dividing by N yields 1.
uses
LinearOrder.lift',Finset.sum_comm,Finset.sum_congr,Finset.sum_ite_eq,Finset.sum_const,Finset.card_univ,nsmul_eq_mul,mul_one,Finset.sum_div,div_self· intro L have hsum : (∑ i : Fin n, ∑ f : Fin k ↪ Fin n, ∑ j : Fin k, (if f j = i then A.prob (LinearOrder.lift' f.toFun f.injective) j else 0)) = (Fintype.card (Fin k ↪ Fin n) : ℝ) := by calc ∑ i : Fin n, ∑ f : Fin k ↪ Fin n, ∑ j : Fin k, (if f j = i then A.prob (LinearOrder.lift' f.toFun f.injective) j else 0) = ∑ f : Fin k ↪ Fin n, ∑ i : Fin n, ∑ j : Fin k, (if f j = i then A.prob (LinearOrder.lift' f.toFun f.injective) j else 0) := Finset.sum_comm _ = ∑ f : Fin k ↪ Fin n, ∑ j : Fin k, ∑ i : Fin n, (if f j = i then A.prob (LinearOrder.lift' f.toFun f.injective) j else 0) := by apply Finset.sum_congr rfl intro f _ exact Finset.sum_comm _ = ∑ f : Fin k ↪ Fin n, ∑ j : Fin k, A.prob (LinearOrder.lift' f.toFun f.injective) j := by apply Finset.sum_congr rfl intro f _ apply Finset.sum_congr rfl intro j _ rw [Finset.sum_ite_eq] simp _ = ∑ f : Fin k ↪ Fin n, (1:ℝ) := by apply Finset.sum_congr rfl intro f _ exact A.total _ _ = (Fintype.card (Fin k ↪ Fin n) : ℝ) := by rw [Finset.sum_const, Finset.card_univ, nsmul_eq_mul, mul_one] rw [← Finset.sum_div, hsum, div_self hNne]
Fix an arbitrary linear order L with minimum m; it suffices to show that A' selects m with probability at least (k * p) / n.
Let m be the minimum element of Fin n under L. To prove that the success probability of A' on L is at least (k * p) / n, it suffices to establish the inequality for the unrolled probability assigned to m by A'.
uses
linearOrderMin,ne_of_gt,LinearOrder.lift'· intro hn L set m := linearOrderMin hn L with hm have hnne : (n : ℝ) ≠ 0 := by exact_mod_cast (ne_of_gt hn) have hgoal : ((k : ℝ) * p) / (n : ℝ) ≤ (∑ f : Fin k ↪ Fin n, ∑ j : Fin k, (if f j = m then A.prob (LinearOrder.lift' f.toFun f.injective) j else 0)) / (Fintype.card (Fin k ↪ Fin n) : ℝ) := by
For any embedding f whose image contains m, algorithm A selects the preimage of m with probability at least p.
If m is in the range of f, injectivity ensures there is a unique j₀ ∈ Fin k such that f(j₀) = m. The inner sum over j collapses to A.prob(f* L, j₀). Because f(j₀) = m is the minimum of L, j₀ must be the minimum of the pulled-back order f* L by `lift_linear_order_min_eq`. By assumption, A succeeds with probability at least p on any order of size k, so this probability is at least p.
uses
Set.range,LinearOrder.lift',Finset.mem_filter,Finset.mem_univ,true_and,Finset.sum_eq_single,lift_linear_order_min_eq,comparison_algorithm_success_probhave hfv : ∀ f ∈ Finset.univ.filter (fun f : Fin k ↪ Fin n => m ∈ Set.range f), p ≤ ∑ j : Fin k, (if f j = m then A.prob (LinearOrder.lift' f.toFun f.injective) j else 0) := by intro f hf simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hf obtain ⟨j0, hj0⟩ := hf have hv : (∑ j : Fin k, (if f j = m then A.prob (LinearOrder.lift' f.toFun f.injective) j else 0)) = A.prob (LinearOrder.lift' f.toFun f.injective) j0 := by have h := Finset.sum_eq_single (s := Finset.univ) (f := fun j => if f j = m then A.prob (LinearOrder.lift' f.toFun f.injective) j else 0) j0 ?_ ?_ · simpa [hj0] using h · intro b _ hb have hbm : f b ≠ m := fun hb' => hb (f.injective (hb'.trans hj0.symm)) simp [hbm] · intro h; exact absurd (Finset.mem_univ j0) h rw [hv] have hmin := lift_linear_order_min_eq hk hn L f j0 (hj0.trans hm) have hprob := hp (LinearOrder.lift' f.toFun f.injective) rw [comparison_algorithm_success_prob, hmin] at hprob exact hprob
The sum of selection probabilities over all embeddings is at least |{f | m ∈ range(f)}| * p.
Summing the lower bound p over all embeddings whose image contains m gives |{f | m ∈ range(f)}| * p. Because all summands are non-negative, restricting the sum over all embeddings to the subset of embeddings covering m produces a valid lower bound.
uses
Set.range,LinearOrder.lift',Finset.sum_le_sum,Finset.sum_const,nsmul_eq_mul,Finset.sum_le_sum_of_subset_of_nonneg,Finset.filter_subset,Finset.sum_nonneg,le_reflhave h1 : ∑ f ∈ Finset.univ.filter (fun f : Fin k ↪ Fin n => m ∈ Set.range f), p ≤ ∑ f ∈ Finset.univ.filter (fun f : Fin k ↪ Fin n => m ∈ Set.range f), ∑ j : Fin k, (if f j = m then A.prob (LinearOrder.lift' f.toFun f.injective) j else 0) := Finset.sum_le_sum hfv have h2 : ∑ f ∈ Finset.univ.filter (fun f : Fin k ↪ Fin n => m ∈ Set.range f), p = ((Finset.univ.filter (fun f : Fin k ↪ Fin n => m ∈ Set.range f)).card : ℝ) * p := by rw [Finset.sum_const, nsmul_eq_mul] have h3 : ∑ f ∈ Finset.univ.filter (fun f : Fin k ↪ Fin n => m ∈ Set.range f), ∑ j : Fin k, (if f j = m then A.prob (LinearOrder.lift' f.toFun f.injective) j else 0) ≤ ∑ f : Fin k ↪ Fin n, ∑ j : Fin k, (if f j = m then A.prob (LinearOrder.lift' f.toFun f.injective) j else 0) := by apply Finset.sum_le_sum_of_subset_of_nonneg · exact Finset.filter_subset _ _ · intro f _ _ apply Finset.sum_nonneg intro j _ split_ifs · exact A.nonneg _ _ · exact le_refl 0 have hsum_ge : ((Finset.univ.filter (fun f : Fin k ↪ Fin n => m ∈ Set.range f)).card : ℝ) * p ≤ ∑ f : Fin k ↪ Fin n, ∑ j : Fin k, (if f j = m then A.prob (LinearOrder.lift' f.toFun f.injective) j else 0) := by linarith
The number of embeddings covering m is N * (k / n).
By `embedding_range_contains_fraction`, exactly a k / n fraction of all embeddings Fin k ↪ Fin n contain the element m in their image. Multiplying both sides by N gives the exact count.
uses
Set.range,embedding_range_contains_fraction,div_eq_iffhave hcardval : ((Finset.univ.filter (fun f : Fin k ↪ Fin n => m ∈ Set.range f)).card : ℝ) = (Fintype.card (Fin k ↪ Fin n) : ℝ) * ((k : ℝ) / (n : ℝ)) := by have hc := embedding_range_contains_fraction hk hkn m rw [div_eq_iff hNne] at hc rw [hc]; ring
Dividing by N proves that A' succeeds with probability at least (k * p) / n.
Dividing the lower bound N * (k / n) * p by N cancels N, leaving (k * p) / n. By definition, the probability assigned to m by A' is its success probability on L, which completes the proof.
uses
div_le_div_of_nonneg_right,le_of_lt,comparison_algorithm_success_probhave hdiv := div_le_div_of_nonneg_right hsum_ge (le_of_lt hNpos) rw [hcardval] at hdiv have heq : ((Fintype.card (Fin k ↪ Fin n) : ℝ) * ((k : ℝ) / (n : ℝ)) * p) / (Fintype.card (Fin k ↪ Fin n) : ℝ) = ((k : ℝ) * p) / (n : ℝ) := by field_simp rw [heq] at hdiv linarith simpa [comparison_algorithm_success_prob, hm] using hgoal
lt_of_lt_of_le- Transitivity of strict and non-strict inequalities: if a < b and b ≤ c, then a < c.
Fin.ext- Extensionality for `Fin n`: two elements are equal if and only if their underlying natural numbers are equal.
congrArg- Congruence of arguments: if a₁ = a₂, then f(a₁) = f(a₂).
Fin.val- The projection function returning the underlying natural number value of an element of `Fin n`.
Fintype.card_pos_iff.mpr- A finite type has strictly positive cardinality if and only if it is nonempty.
ne_of_gt- If b < a, then a ≠ b.
LinearOrder.lift'- Pulls back a linear order structure along an injective function to endow the domain with a linear order.
div_nonneg- If a ≥ 0 and b ≥ 0, then a / b ≥ 0.
le_of_lt- If a < b, then a ≤ b.
Finset.sum_nonneg- A finite sum of non-negative elements is non-negative.
le_refl- Reflexivity of inequality: a ≤ a for every element a.
Finset.sum_comm- Fubini's theorem for finite sums: exchanging the order of summation in a double sum preserves the total.
Finset.sum_congr- Congruence for finite sums: if the index sets are equal and the summands agree pointwise, the sums are equal.
Finset.sum_ite_eq- Summing an indicator `if a = x then b x else 0` over a finite set evaluates to b(a) if a is in the set, and 0 otherwise.
Finset.sum_const- Summing a constant c over a finite set s equals |s| • c.
Finset.card_univ- The cardinality of the universal finset `Finset.univ` of a finite type equals `Fintype.card`.
nsmul_eq_mul- Scalar multiplication by a natural number n • a in a semiring equals the cast product n * a.
mul_one- Multiplying an element by 1 yields the element itself: a * 1 = a.
Finset.sum_div- Distributivity of division over finite sums: (∑ x) / c = ∑ (x / c).
div_self- For any nonzero element a, a / a = 1.
linearOrderMin- The unique minimum element of a nonempty finite linear order.
Set.range- The range (set of values) of a function.
Finset.mem_filter- An element belongs to `s.filter p` if and only if it belongs to s and satisfies the predicate p.
Finset.mem_univ- Every element of a finite type belongs to its universal finset.
true_and- Logical simplification rule: True ∧ p ↔ p.
Finset.sum_eq_single- If all terms in a finite sum are zero except possibly at a single index, the sum equals the term at that index.
lift_linear_order_min_eq- If an embedding f maps an element j to the minimum of a linear order L, then j is the minimum of the pulled-back order f* L.
comparison_algorithm_success_prob- The probability that a comparison algorithm selects the minimum element of a given linear order.
Finset.sum_le_sum- Monotonicity of finite sums: if f(i) ≤ g(i) for all elements i in a set, then ∑ f(i) ≤ ∑ g(i).
Finset.sum_le_sum_of_subset_of_nonneg- If s ⊆ t and the summand is non-negative on t \ s, then the sum over s is at most the sum over t.
Finset.filter_subset- Filtering a finite set by a predicate produces a subset of the original set.
embedding_range_contains_fraction- For k ≤ n, the proportion of embeddings from Fin k to Fin n whose image contains a fixed element m is k / n.
div_eq_iff- For b ≠ 0, a / b = c if and only if a = c * b.
div_le_div_of_nonneg_right- If a ≤ b and c ≥ 0, then a / c ≤ b / c.
- The comparison budget of 2 is an index in the type `ComparisonAlgorithm n 2`, but the transfer construction does not inspect the comparison tree; it operates purely on the marginal output distributions via linearity of expectation.
- The restriction of a linear order on `Fin n` to the image of an embedding `f : Fin k ↪ Fin n` is formalized by pulling the order back to `Fin k` via `LinearOrder.lift'`.
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.
/-- Subset transfer: an algorithm on `k` objects with success `p` transfers to `n ≥ k` with success `k*p/n`. -/theorem subset_transfer_two_comparisons {k n : ℕ} (hk : 0 < k) (hkn : k ≤ n) (A : ComparisonAlgorithm k 2) (p : ℝ) (hp : ∀ (L : LinearOrder (Fin k)), p ≤ comparison_algorithm_success_prob hk A L) : ∃ A' : ComparisonAlgorithm n 2, ∀ (hn : 0 < n) (L : LinearOrder (Fin n)), ((k : ℝ) * p) / (n : ℝ) ≤ comparison_algorithm_success_prob hn A' L := by classical have hNnat : 0 < Fintype.card (Fin k ↪ Fin n) := by have hne : Nonempty (Fin k ↪ Fin n) := ⟨⟨fun i => ⟨i.1, lt_of_lt_of_le i.2 hkn⟩, fun a b h => Fin.ext (by simpa using congrArg Fin.val h)⟩⟩ exact Fintype.card_pos_iff.mpr hne have hNpos : (0 : ℝ) < (Fintype.card (Fin k ↪ Fin n) : ℝ) := by exact_mod_cast hNnat have hNne : (Fintype.card (Fin k ↪ Fin n) : ℝ) ≠ 0 := ne_of_gt hNpos refine ⟨⟨fun L i => (∑ f : Fin k ↪ Fin n, ∑ j : Fin k, if f j = i then A.prob (LinearOrder.lift' f.toFun f.injective) j else 0) / (Fintype.card (Fin k ↪ Fin n) : ℝ), ?_, ?_⟩, ?_⟩ · intro L i apply div_nonneg _ (le_of_lt hNpos) apply Finset.sum_nonneg intro f _ apply Finset.sum_nonneg intro j _ split_ifs · exact A.nonneg _ _ · exact le_refl 0 · intro L have hsum : (∑ i : Fin n, ∑ f : Fin k ↪ Fin n, ∑ j : Fin k, (if f j = i then A.prob (LinearOrder.lift' f.toFun f.injective) j else 0)) = (Fintype.card (Fin k ↪ Fin n) : ℝ) := by calc ∑ i : Fin n, ∑ f : Fin k ↪ Fin n, ∑ j : Fin k, (if f j = i then A.prob (LinearOrder.lift' f.toFun f.injective) j else 0) = ∑ f : Fin k ↪ Fin n, ∑ i : Fin n, ∑ j : Fin k, (if f j = i then A.prob (LinearOrder.lift' f.toFun f.injective) j else 0) := Finset.sum_comm _ = ∑ f : Fin k ↪ Fin n, ∑ j : Fin k, ∑ i : Fin n, (if f j = i then A.prob (LinearOrder.lift' f.toFun f.injective) j else 0) := by apply Finset.sum_congr rfl intro f _ exact Finset.sum_comm _ = ∑ f : Fin k ↪ Fin n, ∑ j : Fin k, A.prob (LinearOrder.lift' f.toFun f.injective) j := by apply Finset.sum_congr rfl intro f _ apply Finset.sum_congr rfl intro j _ rw [Finset.sum_ite_eq] simp _ = ∑ f : Fin k ↪ Fin n, (1:ℝ) := by apply Finset.sum_congr rfl intro f _ exact A.total _ _ = (Fintype.card (Fin k ↪ Fin n) : ℝ) := by rw [Finset.sum_const, Finset.card_univ, nsmul_eq_mul, mul_one] rw [← Finset.sum_div, hsum, div_self hNne] · intro hn L set m := linearOrderMin hn L with hm have hnne : (n : ℝ) ≠ 0 := by exact_mod_cast (ne_of_gt hn) have hgoal : ((k : ℝ) * p) / (n : ℝ) ≤ (∑ f : Fin k ↪ Fin n, ∑ j : Fin k, (if f j = m then A.prob (LinearOrder.lift' f.toFun f.injective) j else 0)) / (Fintype.card (Fin k ↪ Fin n) : ℝ) := by have hfv : ∀ f ∈ Finset.univ.filter (fun f : Fin k ↪ Fin n => m ∈ Set.range f), p ≤ ∑ j : Fin k, (if f j = m then A.prob (LinearOrder.lift' f.toFun f.injective) j else 0) := by intro f hf simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hf obtain ⟨j0, hj0⟩ := hf have hv : (∑ j : Fin k, (if f j = m then A.prob (LinearOrder.lift' f.toFun f.injective) j else 0)) = A.prob (LinearOrder.lift' f.toFun f.injective) j0 := by have h := Finset.sum_eq_single (s := Finset.univ) (f := fun j => if f j = m then A.prob (LinearOrder.lift' f.toFun f.injective) j else 0) j0 ?_ ?_ · simpa [hj0] using h · intro b _ hb have hbm : f b ≠ m := fun hb' => hb (f.injective (hb'.trans hj0.symm)) simp [hbm] · intro h; exact absurd (Finset.mem_univ j0) h rw [hv] have hmin := lift_linear_order_min_eq hk hn L f j0 (hj0.trans hm) have hprob := hp (LinearOrder.lift' f.toFun f.injective) rw [comparison_algorithm_success_prob, hmin] at hprob exact hprob have h1 : ∑ f ∈ Finset.univ.filter (fun f : Fin k ↪ Fin n => m ∈ Set.range f), p ≤ ∑ f ∈ Finset.univ.filter (fun f : Fin k ↪ Fin n => m ∈ Set.range f), ∑ j : Fin k, (if f j = m then A.prob (LinearOrder.lift' f.toFun f.injective) j else 0) := Finset.sum_le_sum hfv have h2 : ∑ f ∈ Finset.univ.filter (fun f : Fin k ↪ Fin n => m ∈ Set.range f), p = ((Finset.univ.filter (fun f : Fin k ↪ Fin n => m ∈ Set.range f)).card : ℝ) * p := by rw [Finset.sum_const, nsmul_eq_mul] have h3 : ∑ f ∈ Finset.univ.filter (fun f : Fin k ↪ Fin n => m ∈ Set.range f), ∑ j : Fin k, (if f j = m then A.prob (LinearOrder.lift' f.toFun f.injective) j else 0) ≤ ∑ f : Fin k ↪ Fin n, ∑ j : Fin k, (if f j = m then A.prob (LinearOrder.lift' f.toFun f.injective) j else 0) := by apply Finset.sum_le_sum_of_subset_of_nonneg · exact Finset.filter_subset _ _ · intro f _ _ apply Finset.sum_nonneg intro j _ split_ifs · exact A.nonneg _ _ · exact le_refl 0 have hsum_ge : ((Finset.univ.filter (fun f : Fin k ↪ Fin n => m ∈ Set.range f)).card : ℝ) * p ≤ ∑ f : Fin k ↪ Fin n, ∑ j : Fin k, (if f j = m then A.prob (LinearOrder.lift' f.toFun f.injective) j else 0) := by linarith have hcardval : ((Finset.univ.filter (fun f : Fin k ↪ Fin n => m ∈ Set.range f)).card : ℝ) = (Fintype.card (Fin k ↪ Fin n) : ℝ) * ((k : ℝ) / (n : ℝ)) := by have hc := embedding_range_contains_fraction hk hkn m rw [div_eq_iff hNne] at hc rw [hc]; ring have hdiv := div_le_div_of_nonneg_right hsum_ge (le_of_lt hNpos) rw [hcardval] at hdiv have heq : ((Fintype.card (Fin k ↪ Fin n) : ℝ) * ((k : ℝ) / (n : ℝ)) * p) / (Fintype.card (Fin k ↪ Fin n) : ℝ) = ((k : ℝ) * p) / (n : ℝ) := by field_simp rw [heq] at hdiv linarith simpa [comparison_algorithm_success_prob, hm] using hgoal