AFTD Auto-Formalizing Theoretical Domains

qary_deletion_num_embeddings

def

For natural numbers q, k, and n, a word u of length n - k over an alphabet of size q, and a word w of length n over the same alphabet, qary_deletion_num_embeddings q k n u w is the number of strictly increasing functions f from Fin (n - k) to Fin n such that w (f i) = u i for all i.

Statement

def qary_deletion_num_embeddings (q k n : ℕ) (u : Fin (n - k) → Fin q) (w : Fin n → Fin q) : ℕ
Defined in
arXiv:2611.01064
Verified
10 Nov 2026
Axioms
none listed
Built on 2
  • 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
  • qary_deletion_collisionFor natural numbers q, k, and n and a word w of length n over an alphabet of size q, qary_deletion_collision q k n w is the sum over all…

Read back from the Lean

For natural numbers q, k, and n, and functions (words) u : Fin (n - k) → Fin q and w : Fin n → Fin q, qary_deletion_num_embeddings q k n u w is defined as the cardinality of the set of all functions f : Fin (n - k) → Fin n such that: 1. f is strictly monotone (f preserves strict order: for all a < b, f a < f b), and 2. w (f i) = u i for all i : Fin (n - k).

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

/-- Number of strictly increasing index embeddings from Fin (n - k) to Fin n spelling u in w. -/
def qary_deletion_num_embeddings (q k n : ℕ) (u : Fin (n - k) → Fin q) (w : Fin n → Fin q) : ℕ := (Finset.univ.filter (fun f : Fin (n - k) → Fin n => StrictMono f ∧ ∀ i, w (f i) = u i)).card
See it in the graphDiscuss this resultChallenge it