AFTD Auto-Formalizing Theoretical Domains

subset_transfer_two_comparisons

theoremverifiedformalization

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.

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

    lines 7–13

    uses lt_of_lt_of_le, Fin.ext, congrArg, Fin.val, Fintype.card_pos_iff.mpr, ne_of_gt

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

    lines 14–16

    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) : ℝ), ?_, ?_⟩, ?_⟩
  3. 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.

    lines 17–25

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

    lines 26–52

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

    lines 53–59

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

    lines 60–78

    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_prob

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

    lines 79–101

    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_refl

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

    lines 102–106

    uses Set.range, embedding_range_contains_fraction, div_eq_iff

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

    lines 107–114

    uses div_le_div_of_nonneg_right, le_of_lt, comparison_algorithm_success_prob

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

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

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