AFTD Auto-Formalizing Theoretical Domains

two_deletion_posterior_sum_two

theoremverified

For every received binary word w of length 2, the posterior distribution two_deletion_posterior 2 w over words of length 4 sums to 1.

Statement

theorem two_deletion_posterior_sum_two (w : Fin 2 → Bool) : ∑ y : Fin 4 → Bool, two_deletion_posterior 2 w y = 1
Source
arXiv:2611.01064, Lemma 2.1
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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_deletion_num_embeddingsFor 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…

Read back from the Lean

For every boolean sequence $w : \mathrm{Fin}\ 2 \to \mathrm{Bool}$, the sum over all boolean sequences $y : \mathrm{Fin}\ 4 \to \mathrm{Bool}$ of $\mathrm{two\_deletion\_posterior}(2, w, y)$ is equal to $1$ (in $\mathbb{R}$).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof evaluates the posterior sum directly using finite verification and algebraic simplification. By definition, the two-deletion posterior probability of a transmitted word y given a received word w is the number of subsequence embeddings of w into y divided by 4 * Nat.choose 4 2 = 24. Exhaustive finite computation shows that the total number of embeddings of w across all 16 possible 4-bit words y is 24, so factoring the denominator out of the sum yields 24 / 24 = 1.

  1. For the given 2-bit word w, the total number of embeddings across all 16 candidate 4-bit words y is 24: ∑ y, two_deletion_num_embeddings 2 w y = 24. automation

    Because the types Fin 2 → Bool and Fin 4 → Bool are finite, Lean can verify by exhaustive evaluation (via `decide`) that for every 2-bit word, the sum of embedding counts over all 16 possible 4-bit transmitted words is exactly 24. Specializing this universal statement to the given word w yields the equation hw.

    lines 5–7

      have h : ∀ w : Fin 2 → Bool, ∑ y : Fin 4 → Bool, two_deletion_num_embeddings 2 w y = 24 := by
        decide
      have hw := h w
  2. The posterior sum is rewritten as ∑ y, (two_deletion_num_embeddings 2 w y : ℝ) / 24 = 1.

    Unfolding the definition of two_deletion_posterior, the posterior probability of y given w is its embedding count divided by 4 * Nat.choose 4 2. Since Nat.choose 4 2 = 6, the denominator 4 * 6 simplifies to 24 by numerical normalization.

    lines 8–10

    uses two_deletion_posterior

      simp only [two_deletion_posterior]
      rw [show Nat.choose 4 2 = 6 from by decide]
      norm_num
  3. The sum of the posterior probabilities evaluates to 1.

    Factoring the division by 24 out of the finite sum using Finset.sum_div and moving the real coercion outside the sum using Nat.cast_sum, the left-hand side becomes (↑∑ y, two_deletion_num_embeddings 2 w y) / 24. Rewriting with hw replaces the sum with 24, leaving 24 / 24 = 1, which holds by arithmetic.

    lines 11–14

    uses Finset.sum_div, Nat.cast_sum

      rw [← Finset.sum_div]
      rw [← Nat.cast_sum]
      rw [hw]
      norm_num
two_deletion_posterior
the posterior probability of transmitted word y given received word w after two deletions, defined as the number of embeddings divided by 4 * Nat.choose (n + 2) 2
Finset.sum_div
a constant divisor can be factored out of a finite sum: (∑ i ∈ s, f i) / a = ∑ i ∈ s, (f i / a)
Nat.cast_sum
coercing a sum of natural numbers to a semiring equals the sum of the coerced terms: ↑(∑ x ∈ s, f x) = ∑ x ∈ s, ↑(f x)

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- For any received binary word of length 2, the two-deletion posterior distribution sums to 1. -/theorem two_deletion_posterior_sum_two (w : Fin 2 → Bool) : ∑ y : Fin 4 → Bool, two_deletion_posterior 2 w y = 1 := by  -- Double counting / direct evaluation: for every w the total number of  -- embeddings over all transmitted words y is 4 * (4 choose 2) = 24.  have h : ∀ w : Fin 2 → Bool, ∑ y : Fin 4 → Bool, two_deletion_num_embeddings 2 w y = 24 := by    decide  have hw := h w  simp only [two_deletion_posterior]  rw [show Nat.choose 4 2 = 6 from by decide]  norm_num  rw [← Finset.sum_div]  rw [← Nat.cast_sum]  rw [hw]  norm_num
See it in the graphDiscuss this resultChallenge it