min_q_ary_deletion_collision_two_eq_min_binary
For 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 collision sum over binary words of length n.
Statement
theorem min_q_ary_deletion_collision_two_eq_min_binary (k n : ℕ) :
min_q_ary_deletion_collision 2 k n = min_binary_deletion_collision k n- Source
- Helper for OP-1359: its q = 2 case is the k = 2 case of OP-1352.
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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…
- 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…
- binary_deletion_collision_eq_q_ary_twoFor every k, n and binary word w of length n, the binary k-deletion collision sum of w equals the q-ary k-deletion collision sum (q = 2)…
- q_ary_subsequence_num_embeddingsFor words u of length m and w of length n over an alphabet of size q represented by Fin q, q_ary_subsequence_num_embeddings q m n u w is…
- binary_deletion_collisionFor natural numbers k and n and a binary word w of length n, binary_deletion_collision k n w is the sum over all binary words u of length…
- Used by 1
- op_1359_q_two_of_binary_two_deletion_lawIf 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…
The proof, explained
For q = 2, the minimum q-ary k-deletion collision sum equals the minimum binary k-deletion collision sum because both are the minimums over the set of collision sums achieved by length-n words. Since the condition 0 < 2 holds, the q-ary definition simplifies to the minimum over words in Fin n → Fin 2. The canonical bijection between Fin 2 and Bool then induces an identity between the set of 2-ary collision values and the set of binary collision values, so their minimums coincide.
The minimum 2-ary deletion collision sum simplifies to taking the minimum over the image of all words in Fin n → Fin 2.
Unfolding the definitions of `min_q_ary_deletion_collision` and `min_binary_deletion_collision`, the q-ary definition has a guard condition 0 < q ∨ n = 0. For q = 2, the inequality 0 < 2 holds, so `dif_pos` together with `Or.inl` selects the "then" branch.
uses
dif_pos,Or.inlunfold min_q_ary_deletion_collision min_binary_deletion_collision rw [dif_pos (Or.inl (by norm_num))]
It suffices to prove that the set of collision values achieved over all 2-ary words equals the set of collision values achieved over all binary words.
The minimum values of two finite sets of natural numbers coincide if the underlying sets of values are equal (`congr 1`).
congr 1The set equality reduces to showing that any natural number c is achieved by a 2-ary word if and only if it is achieved by a binary word.
By set extensionality (`ext c`), an element c belongs to the first set if and only if it belongs to the second. Using `Finset.mem_image` and `Finset.mem_univ`, and rewriting binary collision sums into 2-ary form via `binary_deletion_collision_eq_q_ary_two`, the goal becomes a two-way equivalence between the existence of a 2-ary witness and the existence of a binary witness. Splitting this equivalence (`constructor`) yields two directional implications.
uses
Finset.mem_image,Finset.mem_univ,true_and,binary_deletion_collision_eq_q_ary_twoext c simp only [Finset.mem_image, Finset.mem_univ, true_and, binary_deletion_collision_eq_q_ary_two] constructor
Every collision sum attained by a 2-ary word is attained by a binary word.
Given a 2-ary word w : Fin n → Fin 2, mapping each symbol across the bijection `finTwoEquiv` yields a binary word fun i => finTwoEquiv (w i). Inverting the bijection recovers w, so this binary word produces the exact same collision sum.
uses
finTwoEquiv· rintro ⟨w, rfl⟩ exact ⟨fun i => finTwoEquiv (w i), by simp⟩
Every collision sum attained by a binary word is attained by a 2-ary word.
Given a binary word w : Fin n → Bool, the word fun i => finTwoEquiv.symm (w i) is an explicit 2-ary word that attains the required collision sum by definition.
· rintro ⟨w, rfl⟩ exact ⟨_, rfl⟩
dif_pos- A dependent if-then-else expression evaluates to its "then" branch whenever the condition holds.
Or.inl- If a proposition a holds, then the disjunction a ∨ b holds.
Finset.mem_image- An element belongs to the image of a finite set under a function if and only if it is the image of some element in that set.
Finset.mem_univ- Every element of a finite type belongs to its universal finset.
true_and- The conjunction of True with any proposition p is equivalent to p.
binary_deletion_collision_eq_q_ary_two- The binary k-deletion collision sum of a boolean word equals the 2-ary deletion collision sum of the corresponding word over Fin 2.
finTwoEquiv- The canonical equivalence (bijection) between Fin 2 and Bool.
- In informal mathematics, binary words (alphabet {0, 1}) and boolean words (alphabet {false, true}) are identified without comment. Formally, Lean distinguishes `Fin 2` from `Bool`, so the proof explicitly transfers words across the canonical equivalence `finTwoEquiv`.
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 min_q_ary_deletion_collision_two_eq_min_binary (k n : ℕ) : min_q_ary_deletion_collision 2 k n = min_binary_deletion_collision k n := by unfold min_q_ary_deletion_collision min_binary_deletion_collision rw [dif_pos (Or.inl (by norm_num))] congr 1 ext c simp only [Finset.mem_image, Finset.mem_univ, true_and, binary_deletion_collision_eq_q_ary_two] constructor · rintro ⟨w, rfl⟩ exact ⟨fun i => finTwoEquiv (w i), by simp⟩ · rintro ⟨w, rfl⟩ exact ⟨_, rfl⟩