AFTD Auto-Formalizing Theoretical Domains

binary_deletion_collision_eq_q_ary_two

theoremverified

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 LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
Used by 1

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.

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

    lines 5–6

    uses binary_deletion_collision, Fintype.sum_equiv, Equiv.arrowCongr, Equiv.refl, finTwoEquiv.symm

      unfold binary_deletion_collision
      refine Fintype.sum_equiv (Equiv.arrowCongr (Equiv.refl _) finTwoEquiv.symm) _ _ ?_
  2. 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.

    lines 7–9

    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_apply

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

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