binary_deletion_collision_eq_q_ary_two
For 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) of the word obtained from w by relabelling Bool as Fin 2.
Statement
theorem binary_deletion_collision_eq_q_ary_two (k n : ℕ) (w : Fin n → Bool) : binary_deletion_collision k n w = ∑ u : Fin (n - k) → Fin 2, (q_ary_subsequence_num_embeddings 2 (n - k) n u (fun i => finTwoEquiv.symm (w i))) ^ 2
- Source
- Helper for OP-1359: identifies its q = 2 case with the binary collision sum of OP-1352 / OP-999.
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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…
- 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_num_embeddingsFor natural numbers k and n, a binary word u of length n - k, and a binary word w of length n, binary_deletion_num_embeddings k n u w is…
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- Used by 1
- 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…
The proof, explained
The binary deletion collision sum is defined as the sum over all binary words of length n - k of the squared number of subsequence embeddings. We reindex this sum to range over words with alphabet Fin 2 using the canonical bijection between Bool and Fin 2. The proof then reduces to showing that the number of embeddings is preserved under relabelling, which holds because an index map matches the symbols of w and u if and only if it matches their relabelled symbols by injectivity of the bijection.
The collision sum over binary words of length n - k is reindexed to a sum over words with alphabet Fin 2, reducing the claim to termwise equality of the squared embedding counts.
Unfolding the definition of binary_deletion_collision, the left-hand side is the sum over binary words u : Fin (n - k) → Bool of the squared embedding counts. Using the canonical equivalence between Bool and Fin 2 (finTwoEquiv.symm) and the identity on position indices (Equiv.refl), we obtain a bijection between function types (Fin (n - k) → Bool) ≃ (Fin (n - k) → Fin 2) via Equiv.arrowCongr. Reindexing the sum along this bijection via Fintype.sum_equiv reduces the goal to showing that for each binary word u, its squared embedding count into w equals the squared embedding count of its relabelled counterpart into the relabelled w.
uses
binary_deletion_collision,Fintype.sum_equiv,Equiv.arrowCongr,Equiv.refl,finTwoEquiv.symmunfold binary_deletion_collision refine Fintype.sum_equiv (Equiv.arrowCongr (Equiv.refl _) finTwoEquiv.symm) _ _ ?_
For every binary word u, the number of embeddings of u into w equals the number of embeddings of the relabelled word into the relabelled word, closing the goal.
We fix an arbitrary binary word u (intro u). By definition (binary_deletion_num_embeddings and q_ary_subsequence_num_embeddings), both sides count strictly increasing index maps f : Fin (n - k) → Fin n that preserve character values. Under the function equivalence (Equiv.arrowCongr_apply), the relabelled target at index i is finTwoEquiv.symm (u i) and the relabelled word at f(i) is finTwoEquiv.symm (w (f i)). Because finTwoEquiv.symm is an equivalence, finTwoEquiv.symm (w (f i)) = finTwoEquiv.symm (u i) is equivalent to w (f i) = u i by Equiv.apply_eq_iff_eq. Simplifying with these facts along with the properties of function composition and the identity equivalence (Function.comp_apply, Equiv.refl_symm, Equiv.refl_apply) reveals that the two sets of embeddings are identical, so their cardinalities and squares coincide.
uses
binary_deletion_num_embeddings,q_ary_subsequence_num_embeddings,Equiv.arrowCongr_apply,Function.comp_apply,Equiv.apply_eq_iff_eq,Equiv.refl_symm,Equiv.refl_applyintro u simp only [binary_deletion_num_embeddings, q_ary_subsequence_num_embeddings, Equiv.arrowCongr_apply, Function.comp_apply, Equiv.apply_eq_iff_eq, Equiv.refl_symm, Equiv.refl_apply]
binary_deletion_collision- the binary k-deletion collision sum of a word w, defined as the sum over all binary words u of length n - k of the squared number of subsequence embeddings of u into w
Fintype.sum_equiv- given a bijection e between finite types, the sum of f(x) over the domain equals the sum of g(y) over the codomain provided f(x) = g(e(x)) for all x
Equiv.arrowCongr- given equivalences between domains and codomains, constructs the induced equivalence between the corresponding function types
Equiv.refl- the identity equivalence between a type and itself
finTwoEquiv.symm- the canonical equivalence from Bool to Fin 2
binary_deletion_num_embeddings- the number of embeddings of a binary word u of length n - k into a binary word w of length n, defined as the number of strictly increasing index maps that match symbols
q_ary_subsequence_num_embeddings- the number of embeddings of a word u of length m into a word w of length n over an alphabet of size q, defined as the number of strictly increasing index maps that match symbols
Equiv.arrowCongr_apply- evaluates the function equivalence (e₁.arrowCongr e₂) f at an argument a as e₂ (f (e₁.symm a))
Function.comp_apply- the definition of function composition, (f ∘ g)(x) = f(g(x))
Equiv.apply_eq_iff_eq- an equivalence is injective: f(x) = f(y) if and only if x = y
Equiv.refl_symm- the inverse of the identity equivalence is the identity equivalence
Equiv.refl_apply- the identity equivalence maps any element to itself
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 binary_deletion_collision_eq_q_ary_two (k n : ℕ) (w : Fin n → Bool) : binary_deletion_collision k n w = ∑ u : Fin (n - k) → Fin 2, (q_ary_subsequence_num_embeddings 2 (n - k) n u (fun i => finTwoEquiv.symm (w i))) ^ 2 := by unfold binary_deletion_collision refine Fintype.sum_equiv (Equiv.arrowCongr (Equiv.refl _) finTwoEquiv.symm) _ _ ?_ intro u simp only [binary_deletion_num_embeddings, q_ary_subsequence_num_embeddings, Equiv.arrowCongr_apply, Function.comp_apply, Equiv.apply_eq_iff_eq, Equiv.refl_symm, Equiv.refl_apply]