AFTD Auto-Formalizing Theoretical Domains

min_q_ary_deletion_collision

def

For 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 words u of length n - k of the square of the number of embeddings of u in w (or 0 if q = 0 and n > 0).

Statement

def min_q_ary_deletion_collision (q k n : ℕ) : ℕ
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…
Used by 3

Read back from the Lean

A definition of a function min_q_ary_deletion_collision taking natural numbers q, k, and n, and returning a natural number. If q > 0 or n = 0, it returns the minimum over all words w : Fin n → Fin q of the sum over all words u : Fin (n - k) → Fin q of (q_ary_subsequence_num_embeddings q (n - k) n u w)^2 (the square of the number of embeddings of u into w). Otherwise (if q = 0 and n > 0), it returns 0.

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 minimum k-deletion collision sum over all q-ary words of length n. -/
def min_q_ary_deletion_collision (q k n : ℕ) : ℕ := if h : 0 < q ∨ n = 0 then
    haveI : Nonempty (Fin n → Fin q) := by
      rcases h with hq | hn
      · exact ⟨fun _ => ⟨0, hq⟩⟩
      · subst hn
        exact ⟨fun x => x.elim0⟩
    (Finset.univ.image (fun w : Fin n → Fin q =>
      ∑ u : Fin (n - k) → Fin q, (q_ary_subsequence_num_embeddings q (n - k) n u w) ^ 2)).min'
      (Finset.Nonempty.image Finset.univ_nonempty _)
  else 0
See it in the graphDiscuss this resultChallenge it