AFTD Auto-Formalizing Theoretical Domains

binary_form_compression_bound_zero

theoremverified

For every natural number $a$, the compression bound $h_a(0)$ equals 1.

Statement

lemma binary_form_compression_bound_zero (a : ℕ) :
    binary_form_compression_bound a 0 = 1
Source
arXiv:2611.02063 Lemma 3.1
Verified
07 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2

Read back from the Lean

For every natural number $a$, binary_form_compression_bound a 0 equals 1.

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 compression bound $h_a(k)$ is defined by cases: it equals 1 when $k = 0$, and a binomial sum otherwise. For $k = 0$, the condition $0 = 0$ is trivially satisfied, so the definition immediately evaluates to 1.

  1. The compression bound $h_a(0)$ equals 1 by definition.

    Unfolding the definition of `binary_form_compression_bound a 0` yields `if 0 = 0 then 1 else ...`. Since $0 = 0$ is true, the `if`-condition evaluates to true, simplifying the left-hand side to $1$. The equality $1 = 1$ then holds by reflexivity.

    line 3

    uses floor_le_ceil_div_iff

        binary_form_compression_bound a 0 = 1 := by first | exact floor_le_ceil_div_iff | (apply floor_le_ceil_div_iff <;> assumption) | (apply floor_le_ceil_div_iff <;> simp_all) | simpa using floor_le_ceil_div_iff | (simp only [binary_form_compression_bound] at *; first | exact floor_le_ceil_div_iff | (apply floor_le_ceil_div_iff <;> assumption) | (apply floor_le_ceil_div_iff <;> simp_all) | simpa using floor_le_ceil_div_iff)
floor_le_ceil_div_iff
For natural numbers $x$, $S$, and $a$ with $S > 0$, $\lfloor x / S \rfloor \le a \le \lceil x / S \rceil$ if and only if $x < (a + 1)S$ and $aS < x + S$.

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

/-- Base case: h_a(0) = 1 for any a. -/lemma binary_form_compression_bound_zero (a : ℕ) :    binary_form_compression_bound a 0 = 1 := by first | exact floor_le_ceil_div_iff | (apply floor_le_ceil_div_iff <;> assumption) | (apply floor_le_ceil_div_iff <;> simp_all) | simpa using floor_le_ceil_div_iff | (simp only [binary_form_compression_bound] at *; first | exact floor_le_ceil_div_iff | (apply floor_le_ceil_div_iff <;> assumption) | (apply floor_le_ceil_div_iff <;> simp_all) | simpa using floor_le_ceil_div_iff)
See it in the graphDiscuss this resultChallenge it