AFTD Auto-Formalizing Theoretical Domains

Halving.log_succ_le_log_of_double_le

theoremverifiedimported Lean

Logarithm increment under doubling. For natural numbers $a$ and $b$ with $b > 0$ and $2b \le a$, \[ \lfloor \log_2 b \rfloor + 1 \;\le\; \lfloor \log_2 a \rfloor, \] where $\lfloor \log_2 \cdot \rfloor$ denotes the integer (floor) base-$2$ logarithm.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
variable {Hyp X : Type*} in
lemma Halving.log_succ_le_log_of_double_le {a b : ℕ}
    (hb : 0 < b) (hhalve : 2 * b ≤ a) :
    Nat.log 2 b + 1 ≤ Nat.log 2 a
Source
TCSlib, `Halving.log_succ_le_log_of_double_le`
Lean proof
By Arhaan Aggarwal, from github.com/Shilun-Allan-Li/tcslib at c8a02591b1e5 (Copyright (c) 2026 Arhaan Aggarwal. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.
Verified
07 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1
  • Halving.mistakes_boundMistake bound for the Halving Algorithm. Let $\mathtt{eval} : \mathit{Hyp} \to X \to \mathsf{Bool}$ be an evaluation map, let $V$ be a…

Lean source view module on GitHub

set_option relaxedAutoImplicit false inset_option autoImplicit false invariable {Hyp X : Type*} in/-- If `b` is positive and `2 · b ≤ a`, then `⌊log₂ b⌋ + 1 ≤ ⌊log₂ a⌋` (floors of base-2 logarithms, as computed by `Nat.log`): doubling spends exactly one unit of logarithmic budget. Arithmetic glue for `mistakes_bound`, with no textbook counterpart. -/lemma Halving.log_succ_le_log_of_double_le {a b : ℕ}    (hb : 0 < b) (hhalve : 2 * b ≤ a) :    Nat.log 2 b + 1 ≤ Nat.log 2 a := by  have hbne : b ≠ 0 := by omega  have hpowlog : 2 ^ Nat.log 2 b ≤ b :=    Nat.pow_log_le_self 2 hbne  have hpow : 2 ^ (Nat.log 2 b + 1) ≤ a := by    calc      2 ^ (Nat.log 2 b + 1)          = 2 ^ Nat.log 2 b * 2 := by              rw [pow_succ]      _ ≤ b * 2 := Nat.mul_le_mul_right 2 hpowlog      _ = 2 * b := by omega      _ ≤ a := hhalve  exact Nat.le_log_of_pow_le (by norm_num : 1 < 2) hpow
See it in the graphDiscuss this resultChallenge it