op_1359_q_two_of_binary_two_deletion_law
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
- min_q_ary_deletion_collision_two_eq_min_binaryFor all k and n, the minimum q-ary k-deletion collision sum over words of length n with q = 2 equals the minimum binary k-deletion…
- min_binary_deletion_collisionFor natural numbers k and n, min_binary_deletion_collision k n is the minimum over all binary words w of length n of…
- min_q_ary_deletion_collisionFor natural numbers q, k, and n, min_q_ary_deletion_collision q k n is the minimum over all q-ary words w of length n of the sum over all…
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.
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.
uses
min_q_ary_deletion_collision_two_eq_min_binarysimpa 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
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.
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