Base-two ceiling gives a logarithmic bit bound
ProvedQuantumLTF.Membership.ceil_logb_bits_boundreal-analysis
There is a universal positive constant bounding four plus the natural ceiling of the base-two logarithm of n by that constant times the natural logarithm of n, for every n at least two.
Preamble
import Mathlib
Formal statement
theorem QuantumLTF.Membership.ceil_logb_bits_bound :
∃ C : ℝ, 0 < C ∧ ∀ n : ℕ, 2 ≤ n →
((4 + ⌈Real.logb 2 n⌉₊ : ℕ) : ℝ) ≤ C * Real.log n := by sorrySource
Bit-complexity estimate used in Lemma 3.1 of Fast Quantum Algorithms for Learning Linear Threshold Functions