AFTD Auto-Formalizing Theoretical Domains

two_deletion_num_embeddings

def

For a binary word w of length n and y of length n + 2, two_deletion_num_embeddings n w y is the number of strictly increasing index embeddings from Fin n into Fin (n + 2) that select w as a subword of y.

Statement

def two_deletion_num_embeddings (n : ℕ) (w : Fin n → Bool) (y : Fin (n + 2) → Bool) : ℕ
Defined in
arXiv:2611.01064, Section 2
Verified
03 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 3
  • two_deletion_posterior_sum_twoFor every received binary word w of length 2, the posterior distribution two_deletion_posterior 2 w over words of length 4 sums to 1.
  • two_deletion_posteriorFor a received binary word w of length n, two_deletion_posterior n w y is the posterior probability of transmitting y of length n + 2…
  • two_insertion_collisionFor a binary word w of length m + 2, two_insertion_collision m w is the sum over all binary words u of length m of the square of…

Read back from the Lean

Given a natural number n, a boolean sequence w : Fin n → Bool, and a boolean sequence y : Fin (n + 2) → Bool, two_deletion_num_embeddings n w y is the number of strictly monotone functions f : Fin n → Fin (n + 2) such that for all i : Fin n, y (f i) = w 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

/-- Number of subsequence embeddings of a binary word of length n into a word of length n + 2. -/
def two_deletion_num_embeddings (n : ℕ) (w : Fin n → Bool) (y : Fin (n + 2) → Bool) : ℕ := (Finset.univ.filter (fun f : Fin n → Fin (n + 2) => StrictMono f ∧ ∀ i, y (f i) = w i)).card
See it in the graphDiscuss this resultChallenge it