AFTD Auto-Formalizing Theoretical Domains

two_insertion_collision_defect_envelope

deforiginal

For a natural number n, two_insertion_collision_defect_envelope n is n.choose 2 plus the minimum over all k in the defect set K_n of the cost 2 * k * n + 2 * k^2 + n - 10 * k - 2 + (k + 1 - r) * q^2 + r * (q + 1)^2, where K_n is the union of {1} and all integers k with 2 ≤ k ≤ (n - 2) / 3 - 1, and q = (n - 2) / (k + 1) and r = (n - 2) % (k + 1).

Statement

def two_insertion_collision_defect_envelope (n : ℕ) : ℕ
Related work
arXiv:2611.01064 Maximal input entropy for binary two-deletion and two-insertion channels
Verified
04 Nov 2026
Axioms
none listed
Used by 4

Read back from the Lean

The declaration defines a function two_insertion_collision_defect_envelope : ℕ → ℕ. For a given $n \in \mathbb{N}$, it evaluates to: $$\binom{n}{2} + \min_{k \in K} \left( 2kn + 2k^2 + n - 10k - 2 + (k + 1 - r)q^2 + r(q + 1)^2 \right)$$ where: - $K \subseteq \mathbb{N}$ is the finite set $\{1\} \cup \{k \in \mathbb{N} \mid 2 \le k \le \lfloor (n - 2) / 3 \rfloor - 1\}$, which is non-empty because $1 \in K$; - for each $k \in K$, $q = \lfloor (n - 2) / (k + 1) \rfloor$ and $r = (n - 2) \pmod{k + 1}$; - all arithmetic operations (addition, multiplication, exponentiation, integer division, modulo, and subtraction) are performed on $\mathbb{N}$, so subtractions truncate at 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 exact balanced defect collision envelope for two insertions in a binary word of length n. -/
def two_insertion_collision_defect_envelope (n : ℕ) : ℕ := let K : Finset ℕ := insert 1 (Finset.Icc 2 ((n - 2) / 3 - 1))
  n.choose 2 + (K.image (fun k =>
    let q := (n - 2) / (k + 1)
    let r := (n - 2) % (k + 1)
    2 * k * n + 2 * k ^ 2 + n - 10 * k - 2 + (k + 1 - r) * q ^ 2 + r * (q + 1) ^ 2)).min'
    (Finset.Nonempty.image ⟨1, Finset.mem_insert_self 1 _⟩ _)
See it in the graphDiscuss this resultChallenge it