AFTD Auto-Formalizing Theoretical Domains

embedding_range_contains_fraction

theoremverified

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.

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

    lines 1–20

    uses embedding_range_contains_fraction_swapEmbed, embedding_range_contains_fraction_swapEmbed_involutive, Function.bijective_iff_has_inverse.mpr

    open 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'⟩
    
  2. 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.

    lines 21–34

    uses embedding_range_contains_fraction_swapEmbed, Set.mem_range, congr_arg, Equiv.swap_apply_right, Equiv.swap_apply_self

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

    lines 35–44

    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_swapEmbed

    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).symm
    
  4. 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.

    lines 45–53

    uses card_filter, sum_comm

    lemma 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]
  5. 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.

    lines 54–66

    uses card_filter, card_map, card_univ, Fintype.card_fin, sum_const, smul_eq_mul

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

    lines 67–79

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

    lines 80–85

    uses embedding_range_contains_fraction_sum_card_filter_eq, congr_arg

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

    lines 86–94

    uses Fin.nonempty_embedding_iff.mpr, Fintype.card_ne_zero, div_eq_div_iff

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

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