AFTD Auto-Formalizing Theoretical Domains

q_ary_deletion_collision

def

For natural numbers q, k, and n, and a q-ary word w of length n represented as a function from Fin n to Fin q, q_ary_deletion_collision q k n w is the sum over all words u of length n - k of the square of the number of embeddings of u as a subsequence of w.

Statement

def q_ary_deletion_collision (q k n : ℕ) (w : Fin n → Fin q) : ℕ
Defined in
knowledgebase OP-1359
Verified
10 Nov 2026
Axioms
none listed
Built on 1
  • 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…

Read back from the Lean

The function q_ary_deletion_collision takes natural numbers q, k, n and a word w : Fin n → Fin q, and computes the sum, over all words u : Fin (n - k) → Fin q, of the square of q_ary_subsequence_num_embeddings q (n - k) n u w.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The k-deletion collision sum of a q-ary word w of length n. -/
def q_ary_deletion_collision (q k n : ℕ) (w : Fin n → Fin q) : ℕ := ∑ u : Fin (n - k) → Fin q, (q_ary_subsequence_num_embeddings q (n - k) n u w) ^ 2
See it in the graphDiscuss this resultChallenge it