embedding_range_contains_fraction
For 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.
Statement
theorem embedding_range_contains_fraction {k n : ℕ} (hk : 0 < k) (hkn : k ≤ n) (m : Fin n) : ((Finset.univ.filter (fun f : Fin k ↪ Fin n => m ∈ Set.range f)).card : ℝ) / (Fintype.card (Fin k ↪ Fin n) : ℝ) = (k : ℝ) / (n : ℝ)
- Source
- arXiv:2610.34762 Lemma 6 proof (Step 4)
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- subset_transfer_two_comparisonsSuppose an algorithm on k objects succeeds in minimum selection with probability at least p on every strict order and uses at most two…
Read back from the Lean
For all natural numbers $k$ and $n$ satisfying $0 < k$ and $k \le n$, and for every element $m : \mathrm{Fin}\ n$, the ratio of the number of embeddings (injective functions) $f : \mathrm{Fin}\ k \hookrightarrow \mathrm{Fin}\ n$ whose range contains $m$ to the total number of embeddings from $\mathrm{Fin}\ k$ to $\mathrm{Fin}\ n$ is equal to $k / n$ (as real numbers).
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
The proof uses symmetry and double counting. By post-composing embeddings with the transposition of any two elements, one obtains a bijection on embeddings showing that every element of Fin n belongs to the range of the exact same number of embeddings. Summing this count over all n elements equals n times the count for a fixed element m, but by interchanging summations, the total sum also equals the number of embeddings times the range size k. Equating these two expressions and dividing by n and the total number of embeddings yields the fraction k / n.
The operation of post-composing an embedding with a transposition of two target elements is an involutive bijection on embeddings.
For any m, m' ∈ Fin n, post-composing an embedding f : Fin k ↪ Fin n with the transposition (m m') yields another embedding. Because swapping m and m' twice acts as the identity on Fin n, this operation is an involution and hence a bijection on the type of embeddings.
uses
embedding_range_contains_fraction_swapEmbed,embedding_range_contains_fraction_swapEmbed_involutive,Function.bijective_iff_has_inverse.mpropen Finset def embedding_range_contains_fraction_swapEmbed {k n : ℕ} (m m' : Fin n) (f : Fin k ↪ Fin n) : Fin k ↪ Fin n := f.trans (Equiv.swap m m').toEmbedding lemma embedding_range_contains_fraction_swapEmbed_involutive {k n : ℕ} (m m' : Fin n) (f : Fin k ↪ Fin n) : embedding_range_contains_fraction_swapEmbed m m' (embedding_range_contains_fraction_swapEmbed m m' f) = f := by ext x simp [embedding_range_contains_fraction_swapEmbed] lemma embedding_range_contains_fraction_swapEmbed_bijective {k n : ℕ} (m m' : Fin n) : Function.Bijective (embedding_range_contains_fraction_swapEmbed (k := k) m m') := Function.bijective_iff_has_inverse.mpr ⟨embedding_range_contains_fraction_swapEmbed m m', embedding_range_contains_fraction_swapEmbed_involutive m m', embedding_range_contains_fraction_swapEmbed_involutive m m'⟩
An element m' belongs to the range of the swapped embedding (m m') ∘ f if and only if m belongs to the range of f.
By definition of range, m' ∈ range((m m') ∘ f) means (m m')(f(x)) = m' for some x. Applying the transposition (m m') to both sides yields f(x) = m, so m ∈ range(f). The converse holds by the same logic, applying the transposition to f(x) = m.
uses
embedding_range_contains_fraction_swapEmbed,Set.mem_range,congr_arg,Equiv.swap_apply_right,Equiv.swap_apply_selflemma embedding_range_contains_fraction_mem_range_swapEmbed {k n : ℕ} (m m' : Fin n) (f : Fin k ↪ Fin n) : m' ∈ Set.range (embedding_range_contains_fraction_swapEmbed m m' f) ↔ m ∈ Set.range f := by simp [embedding_range_contains_fraction_swapEmbed, Set.mem_range] constructor · rintro ⟨x, hx⟩ use x have h := congr_arg (Equiv.swap m m') hx simp only [Equiv.swap_apply_right, Equiv.swap_apply_self] at h exact h · rintro ⟨x, hx⟩ use x simp [hx]
For any two elements m, m' ∈ Fin n, the number of embeddings containing m in their range equals the number containing m'.
The swap operation f ↦ (m m') ∘ f is a bijection on embeddings that maps the subset of embeddings whose range contains m bijectively onto the subset of embeddings whose range contains m'. By Finset.card_bijective, both subsets have the same cardinality.
uses
Finset.card_bijective,embedding_range_contains_fraction_swapEmbed,embedding_range_contains_fraction_swapEmbed_bijective,Finset.mem_filter,Finset.mem_univ,true_and,embedding_range_contains_fraction_mem_range_swapEmbedlemma embedding_range_contains_fraction_card_filter_range_eq {k n : ℕ} (m m' : Fin n) : (Finset.univ.filter (fun f : Fin k ↪ Fin n => m ∈ Set.range f)).card = (Finset.univ.filter (fun f : Fin k ↪ Fin n => m' ∈ Set.range f)).card := by apply Finset.card_bijective (embedding_range_contains_fraction_swapEmbed m m') (embedding_range_contains_fraction_swapEmbed_bijective m m') intro f simp only [Finset.mem_filter, Finset.mem_univ, true_and] exact (embedding_range_contains_fraction_mem_range_swapEmbed m m' f).symm
The sum over all m ∈ Fin n of the number of embeddings containing m in their range equals a double sum of indicators with the order of summation interchanged.
The size of each filtered set is expressed as a sum of indicator functions over all embeddings f. Summing these over all m ∈ Fin n gives a double sum, which is interchanged via sum_comm so the outer sum runs over embeddings f and the inner sum runs over elements m.
uses
card_filter,sum_commlemma embedding_range_contains_fraction_sum_card_filter_eq {k n : ℕ} : (∑ m : Fin n, (univ.filter (fun f : Fin k ↪ Fin n => m ∈ Set.range f)).card) = (Fintype.card (Fin k ↪ Fin n)) * k := by have h1 : ∀ m : Fin n, (univ.filter (fun f : Fin k ↪ Fin n => m ∈ Set.range f)).card = ∑ f : Fin k ↪ Fin n, if m ∈ Set.range f then 1 else 0 := by intro m exact card_filter _ univ simp_rw [h1] rw [sum_comm]
The total sum across all elements equals the total number of embeddings times k.
For each fixed embedding f, the inner sum of indicators over all m ∈ Fin n is the cardinality of the range of f. Because f is an embedding from Fin k, its range has size k. Summing this constant k over all embeddings yields |Fin k ↪ Fin n| · k.
uses
card_filter,card_map,card_univ,Fintype.card_fin,sum_const,smul_eq_mulhave h2 : ∀ f : Fin k ↪ Fin n, (∑ m : Fin n, if m ∈ Set.range f then 1 else 0) = k := by intro f have h3 : (∑ m : Fin n, if m ∈ Set.range f then 1 else 0) = (univ.filter (fun m : Fin n => m ∈ Set.range f)).card := by exact (card_filter (fun m => m ∈ Set.range f) univ).symm rw [h3] have h4 : (univ.filter (fun m : Fin n => m ∈ Set.range f)) = univ.map f := by ext x simp rw [h4, card_map, card_univ, Fintype.card_fin] simp_rw [h2] rw [sum_const, card_univ, smul_eq_mul]
The sum of the counts across all elements equals n times the count for any fixed element m.
Since every m' ∈ Fin n belongs to the range of the same number of embeddings as m does, every summand in the sum over m' ∈ Fin n can be replaced by the count for m. Summing this constant over all n elements of Fin n yields n times the count for m.
uses
Finset.sum_congr,embedding_range_contains_fraction_card_filter_range_eq,Finset.sum_const,Finset.card_univ,Fintype.card_fin,smul_eq_mul/-- For any fixed element `m : Fin n`, the fraction of embeddings `f : Fin k ↪ Fin n` whose range contains `m` is `k / n`. -/ theorem embedding_range_contains_fraction {k n : ℕ} (hk : 0 < k) (hkn : k ≤ n) (m : Fin n) : ((Finset.univ.filter (fun f : Fin k ↪ Fin n => m ∈ Set.range f)).card : ℝ) / (Fintype.card (Fin k ↪ Fin n) : ℝ) = (k : ℝ) / (n : ℝ) := by have hsum : (Finset.sum Finset.univ fun m' : Fin n => (Finset.univ.filter (fun f : Fin k ↪ Fin n => m' ∈ Set.range f)).card) = n * (Finset.univ.filter (fun f : Fin k ↪ Fin n => m ∈ Set.range f)).card := by have : (Finset.sum Finset.univ fun m' : Fin n => (Finset.univ.filter (fun f : Fin k ↪ Fin n => m' ∈ Set.range f)).card) = Finset.sum Finset.univ fun m' : Fin n => (Finset.univ.filter (fun f : Fin k ↪ Fin n => m ∈ Set.range f)).card := by apply Finset.sum_congr rfl intro m' _ exact (embedding_range_contains_fraction_card_filter_range_eq m m').symm rw [this, Finset.sum_const, Finset.card_univ, Fintype.card_fin, smul_eq_mul]
Equating the two expressions for the sum yields n · |{f | m ∈ range(f)}| = |Fin k ↪ Fin n| · k in both ℕ and ℝ.
Equating the formula from Step 6 with the double-counting formula from Step 5 gives n · |{f | m ∈ range(f)}| = |Fin k ↪ Fin n| · k in ℕ. Casting both sides of this equality to ℝ gives the corresponding identity in the real numbers.
uses
embedding_range_contains_fraction_sum_card_filter_eq,congr_arghave h_nat : n * (Finset.univ.filter (fun f : Fin k ↪ Fin n => m ∈ Set.range f)).card = (Fintype.card (Fin k ↪ Fin n)) * k := by rw [← hsum, embedding_range_contains_fraction_sum_card_filter_eq] have h_real : (n : ℝ) * ((Finset.univ.filter (fun f : Fin k ↪ Fin n => m ∈ Set.range f)).card : ℝ) = (Fintype.card (Fin k ↪ Fin n) : ℝ) * (k : ℝ) := by exact_mod_cast congr_arg (fun x : ℕ => (x : ℝ)) h_nat
Dividing by the denominators concludes that the fraction of embeddings whose range contains m equals k / n. automation
Because 0 < k ≤ n, the integer n is positive, so n ≠ 0 in ℝ. Since k ≤ n, there exists at least one embedding from Fin k into Fin n, so the total number of embeddings is non-zero. Dividing the real identity from Step 7 by n and by the total number of embeddings gives the fraction equality via div_eq_div_iff and linarith.
uses
Fin.nonempty_embedding_iff.mpr,Fintype.card_ne_zero,div_eq_div_iffhave hn : (n : ℝ) ≠ 0 := by have : n ≠ 0 := by omega positivity have hcard : (Fintype.card (Fin k ↪ Fin n) : ℝ) ≠ 0 := by have : Nonempty (Fin k ↪ Fin n) := Fin.nonempty_embedding_iff.mpr hkn have : Fintype.card (Fin k ↪ Fin n) ≠ 0 := Fintype.card_ne_zero positivity apply (div_eq_div_iff hcard hn).mpr linarith
Equiv.swap_apply_right- The transposition of a and b sends b to a.
Equiv.swap_apply_self- Applying the transposition of i and j twice to any element returns that element.
congr_arg- If two arguments are equal, the values of a function applied to them are equal.
Fintype.card_fin- The cardinality of Fin n is n.
Fintype.card_ne_zero- A nonempty finite type has non-zero cardinality.
Fin.nonempty_embedding_iff.mpr- If k ≤ n, then there exists an embedding from Fin k into Fin n.
Finset.card_bijective- A bijection between types maps a finset to a finset of equal cardinality, provided it preserves membership.
Finset.card_univ- The cardinality of the universal finset of a finite type equals the cardinality of that type.
Finset.mem_filter- An element belongs to a filtered finset if and only if it belongs to the base finset and satisfies the predicate.
Finset.mem_univ- Every element of a finite type belongs to the universal finset univ.
Finset.sum_congr- Two sums are equal if their index sets are equal and their summands agree on every element of the index set.
Finset.sum_const- The sum of a constant value over a finset equals the finset's cardinality times the constant.
Function.bijective_iff_has_inverse.mpr- A function with a two-sided inverse is bijective.
Set.mem_range- An element belongs to the range of a function if and only if it is the image of some input.
card_filter- The cardinality of a filtered finset equals the sum of its indicator function over the base finset.
card_map- Mapping a finset by an embedding preserves its cardinality.
card_univ- The cardinality of the universal finset univ of a finite type equals the cardinality of that type.
div_eq_div_iff- For non-zero denominators b and d, a / b = c / d if and only if a * d = c * b.
embedding_range_contains_fraction_card_filter_range_eq- For any two elements m and m' in Fin n, the number of embeddings containing m in their range equals the number containing m'.
embedding_range_contains_fraction_mem_range_swapEmbed- An element m' belongs to the range of the swapped embedding (m m') ∘ f if and only if m belongs to the range of f.
embedding_range_contains_fraction_sum_card_filter_eq- The sum over all m in Fin n of the number of embeddings containing m in their range equals the total number of embeddings times k.
embedding_range_contains_fraction_swapEmbed- Post-composes an embedding from Fin k to Fin n with the transposition of two elements m and m' in Fin n.
embedding_range_contains_fraction_swapEmbed_bijective- The swap operation on embeddings is a bijection.
embedding_range_contains_fraction_swapEmbed_involutive- Applying the swap operation twice to an embedding returns the original embedding.
smul_eq_mul- Scalar multiplication of natural numbers equals ordinary multiplication.
sum_comm- The order of summation in a finite double sum can be interchanged.
sum_const- The sum of a constant value over a finset equals the cardinality of the finset times that constant.
true_and- Conjunction with True simplifies: True ∧ p is equivalent to p.
- The proof relies on automated tactics (`omega`, `positivity`, `linarith`) in the final step to establish that the denominators $n$ and the number of embeddings are non-zero (using the hypotheses $0 < k \le n$) and to perform the final cross-multiplication in the field of real numbers.
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 Finsetdef embedding_range_contains_fraction_swapEmbed {k n : ℕ} (m m' : Fin n) (f : Fin k ↪ Fin n) : Fin k ↪ Fin n := f.trans (Equiv.swap m m').toEmbeddinglemma embedding_range_contains_fraction_swapEmbed_involutive {k n : ℕ} (m m' : Fin n) (f : Fin k ↪ Fin n) : embedding_range_contains_fraction_swapEmbed m m' (embedding_range_contains_fraction_swapEmbed m m' f) = f := by ext x simp [embedding_range_contains_fraction_swapEmbed]lemma embedding_range_contains_fraction_swapEmbed_bijective {k n : ℕ} (m m' : Fin n) : Function.Bijective (embedding_range_contains_fraction_swapEmbed (k := k) m m') := Function.bijective_iff_has_inverse.mpr ⟨embedding_range_contains_fraction_swapEmbed m m', embedding_range_contains_fraction_swapEmbed_involutive m m', embedding_range_contains_fraction_swapEmbed_involutive m m'⟩lemma embedding_range_contains_fraction_mem_range_swapEmbed {k n : ℕ} (m m' : Fin n) (f : Fin k ↪ Fin n) : m' ∈ Set.range (embedding_range_contains_fraction_swapEmbed m m' f) ↔ m ∈ Set.range f := by simp [embedding_range_contains_fraction_swapEmbed, Set.mem_range] constructor · rintro ⟨x, hx⟩ use x have h := congr_arg (Equiv.swap m m') hx simp only [Equiv.swap_apply_right, Equiv.swap_apply_self] at h exact h · rintro ⟨x, hx⟩ use x simp [hx]lemma embedding_range_contains_fraction_card_filter_range_eq {k n : ℕ} (m m' : Fin n) : (Finset.univ.filter (fun f : Fin k ↪ Fin n => m ∈ Set.range f)).card = (Finset.univ.filter (fun f : Fin k ↪ Fin n => m' ∈ Set.range f)).card := by apply Finset.card_bijective (embedding_range_contains_fraction_swapEmbed m m') (embedding_range_contains_fraction_swapEmbed_bijective m m') intro f simp only [Finset.mem_filter, Finset.mem_univ, true_and] exact (embedding_range_contains_fraction_mem_range_swapEmbed m m' f).symmlemma embedding_range_contains_fraction_sum_card_filter_eq {k n : ℕ} : (∑ m : Fin n, (univ.filter (fun f : Fin k ↪ Fin n => m ∈ Set.range f)).card) = (Fintype.card (Fin k ↪ Fin n)) * k := by have h1 : ∀ m : Fin n, (univ.filter (fun f : Fin k ↪ Fin n => m ∈ Set.range f)).card = ∑ f : Fin k ↪ Fin n, if m ∈ Set.range f then 1 else 0 := by intro m exact card_filter _ univ simp_rw [h1] rw [sum_comm] have h2 : ∀ f : Fin k ↪ Fin n, (∑ m : Fin n, if m ∈ Set.range f then 1 else 0) = k := by intro f have h3 : (∑ m : Fin n, if m ∈ Set.range f then 1 else 0) = (univ.filter (fun m : Fin n => m ∈ Set.range f)).card := by exact (card_filter (fun m => m ∈ Set.range f) univ).symm rw [h3] have h4 : (univ.filter (fun m : Fin n => m ∈ Set.range f)) = univ.map f := by ext x simp rw [h4, card_map, card_univ, Fintype.card_fin] simp_rw [h2] rw [sum_const, card_univ, smul_eq_mul]/-- For any fixed element `m : Fin n`, the fraction of embeddings `f : Fin k ↪ Fin n` whose range contains `m` is `k / n`. -/theorem embedding_range_contains_fraction {k n : ℕ} (hk : 0 < k) (hkn : k ≤ n) (m : Fin n) : ((Finset.univ.filter (fun f : Fin k ↪ Fin n => m ∈ Set.range f)).card : ℝ) / (Fintype.card (Fin k ↪ Fin n) : ℝ) = (k : ℝ) / (n : ℝ) := by have hsum : (Finset.sum Finset.univ fun m' : Fin n => (Finset.univ.filter (fun f : Fin k ↪ Fin n => m' ∈ Set.range f)).card) = n * (Finset.univ.filter (fun f : Fin k ↪ Fin n => m ∈ Set.range f)).card := by have : (Finset.sum Finset.univ fun m' : Fin n => (Finset.univ.filter (fun f : Fin k ↪ Fin n => m' ∈ Set.range f)).card) = Finset.sum Finset.univ fun m' : Fin n => (Finset.univ.filter (fun f : Fin k ↪ Fin n => m ∈ Set.range f)).card := by apply Finset.sum_congr rfl intro m' _ exact (embedding_range_contains_fraction_card_filter_range_eq m m').symm rw [this, Finset.sum_const, Finset.card_univ, Fintype.card_fin, smul_eq_mul] have h_nat : n * (Finset.univ.filter (fun f : Fin k ↪ Fin n => m ∈ Set.range f)).card = (Fintype.card (Fin k ↪ Fin n)) * k := by rw [← hsum, embedding_range_contains_fraction_sum_card_filter_eq] have h_real : (n : ℝ) * ((Finset.univ.filter (fun f : Fin k ↪ Fin n => m ∈ Set.range f)).card : ℝ) = (Fintype.card (Fin k ↪ Fin n) : ℝ) * (k : ℝ) := by exact_mod_cast congr_arg (fun x : ℕ => (x : ℝ)) h_nat have hn : (n : ℝ) ≠ 0 := by have : n ≠ 0 := by omega positivity have hcard : (Fintype.card (Fin k ↪ Fin n) : ℝ) ≠ 0 := by have : Nonempty (Fin k ↪ Fin n) := Fin.nonempty_embedding_iff.mpr hkn have : Fintype.card (Fin k ↪ Fin n) ≠ 0 := Fintype.card_ne_zero positivity apply (div_eq_div_iff hcard hn).mpr linarith