min_q_ary_deletion_collision
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
- 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…
- min_q_ary_deletion_collision_three_three_fiveThe minimum, over ternary words of length 5, of the 3-deletion collision sum is 14, so C_3(5) - binom(5,3) = 4.
- 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…
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