AFTD Auto-Formalizing Theoretical Domains

op_1359_q_two_of_binary_two_deletion_law

theoremverified

If the binary two-deletion law holds, that is, (min_binary_deletion_collision 2 n - binom(n,2)) / n^(3/2) tends to 2√2, then the q = 2 case of OP-1359 holds: (min_q_ary_deletion_collision 2 2 n - binom(n,2)) / n^(3/2) tends to 2√2.

Statement

theorem op_1359_q_two_of_binary_two_deletion_law
    (h : Filter.Tendsto
      (fun n : ℕ => ((min_binary_deletion_collision 2 n : ℝ) - (Nat.choose n 2 : ℝ)) /
        ((n : ℝ) ^ ((3 : ℝ) / 2)))
      Filter.atTop (nhds (2 * Real.sqrt 2))) :
    Filter.Tendsto
      (fun n : ℕ => ((min_q_ary_deletion_collision 2 2 n : ℝ) - (Nat.choose n 2 : ℝ)) /
        ((n : ℝ) ^ ((3 : ℝ) / 2)))
      Filter.atTop (nhds (2 * Real.sqrt 2))
Source
The q = 2 case of OP-1359 is exactly the k = 2 case of OP-1352 (equivalently OP-999); this conditional records the reduction.
Verified
10 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3

The proof, explained

The theorem deduces the q = 2 case of the asymptotic deletion collision law from the binary two-deletion law. The lemma min_q_ary_deletion_collision_two_eq_min_binary identifies the q = 2 deletion collision count with the binary collision count for every length n. Rewriting with this equivalence makes the desired limit identical to the assumed hypothesis.

  1. The asymptotic limit for the q = 2 deletion collision statistic holds, identical to the binary two-deletion law.

    Using the identity min_q_ary_deletion_collision_two_eq_min_binary, the q-ary collision count min_q_ary_deletion_collision 2 2 n in the goal is rewritten to the binary collision count min_binary_deletion_collision 2 n. The goal then matches the assumption h exactly.

    line 10

    uses min_q_ary_deletion_collision_two_eq_min_binary

      simpa only [min_q_ary_deletion_collision_two_eq_min_binary] using h
min_q_ary_deletion_collision_two_eq_min_binary
For alphabet size q = 2, the minimum q-ary deletion collision number equals the minimum binary deletion collision number for any number of deletions k and word length n.

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

theorem op_1359_q_two_of_binary_two_deletion_law    (h : Filter.Tendsto      (fun n : ℕ => ((min_binary_deletion_collision 2 n : ℝ) - (Nat.choose n 2 : ℝ)) /        ((n : ℝ) ^ ((3 : ℝ) / 2)))      Filter.atTop (nhds (2 * Real.sqrt 2))) :    Filter.Tendsto      (fun n : ℕ => ((min_q_ary_deletion_collision 2 2 n : ℝ) - (Nat.choose n 2 : ℝ)) /        ((n : ℝ) ^ ((3 : ℝ) / 2)))      Filter.atTop (nhds (2 * Real.sqrt 2)) := by  simpa only [min_q_ary_deletion_collision_two_eq_min_binary] using h
See it in the graphDiscuss this resultChallenge it