AFTD Auto-Formalizing Theoretical Domains

binary_deletion_num_embeddings

def

For 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 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 binary_deletion_num_embeddings (k n : ℕ) (u : Fin (n - k) → Bool) (w : Fin n → Bool) : ℕ
Defined in
arXiv:2611.01064: Maximal input entropy for binary two-deletion and two-insertion channels
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 2
  • binary_deletion_collision_eq_q_ary_twoFor 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)…
  • 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…

Read back from the Lean

Given natural numbers k and n, a binary word u : Fin (n - k) → Bool, and a binary word w : Fin n → Bool, binary_deletion_num_embeddings k n u w is defined as the number of strictly monotone functions f : Fin (n - k) → Fin n such that for all i : Fin (n - k), w (f i) = u i.

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 number of index subsets of size n - k of a binary word w of length n whose retained subsequence equals u. -/
def binary_deletion_num_embeddings (k n : ℕ) (u : Fin (n - k) → Bool) (w : Fin n → Bool) : ℕ := (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