binary_form_compression_bound_zero
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
- binary_form_compression_boundThe compression bound $h_a(k)$ is defined for natural numbers $a$ and $k$ by $h_a(0) = 1$, and…
- floor_le_ceil_div_iffFor S > 0, floor(x/S) <= a <= ceil(x/S) iff x < (a+1) S and a S < x + S.
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.
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.
uses
floor_le_ceil_div_iffbinary_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$.
- The lemma `floor_le_ceil_div_iff` (concerning rational division and floor/ceiling bounds) appears multiple times in the proof script due to an automated proof search, but it is mathematically irrelevant. The tactic `simpa using floor_le_ceil_div_iff` closes the goal entirely by simplifying `if True then 1 else ... = 1` to `1 = 1` and reflexivity, ignoring the supplied lemma.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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)