AFTD Auto-Formalizing Theoretical Domains

binary_form_compression_bound

def

The compression bound $h_a(k)$ is defined for natural numbers $a$ and $k$ by $h_a(0) = 1$, and $h_a(k) = 2 \sum_{j=0}^{a-1} \binom{k-1}{j}$ for $k \ge 1$.

Statement

def binary_form_compression_bound (a k : ℕ) : ℕ
Defined in
arXiv:2611.02063 Lemma 3.1
Verified
07 Nov 2026
Axioms
none listed
Used by 1

Read back from the Lean

The function binary_form_compression_bound takes two natural numbers $a$ and $k$ and returns a natural number, defined to be $1$ if $k = 0$, and $2 \sum_{j=0}^{a-1} \binom{k-1}{j}$ if $k \neq 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

/-- Compression bound h_a(k) for binary linear forms modulo 2^a in dimension k + 1. -/
def binary_form_compression_bound (a k : ℕ) : ℕ := if k = 0 then 1 else 2 * ∑ j ∈ Finset.range a, Nat.choose (k - 1) j
See it in the graphDiscuss this resultChallenge it