Elementary exponential and logarithm bounds #
Numeric lemmas underpinning the Chernoff-exponent estimates elsewhere in the development, none requiring calculus/derivatives:
log_ge_quadratic: the crude linear bound1 - 1/x ≤ log x(Mathlib'sReal.one_sub_inv_le_log_of_pos) is exactly tangent tologatx = 1, so plugging it into the Chernoff exponentk - μ - k·log(k/μ)gives exactly0wheneverk/μis close to1— useless, since what's needed is a bound strictly below0. This derives a genuinely quadratic-tight lower bound onlognear1, from Mathlib's degree-3Taylor lower bound forexp(Real.sum_le_exp_of_nonneg).- Mathlib's
Real.pow_div_factorial_le_exp:xᵏ/k! ≤ exp xfor any degreek, the single-term generalization of the same Taylor truncation. Pickingklarge enough relative to a given lower bound onlog nis what keeps that bound modest (Stage 2b,saturation_stage2b) instead of astronomically large. log_le_tangent_div,exp_three_ge_twenty,log_log_le_of_pos: a tangent-line bound onlogat an arbitrary reference pointc(tight atL = c, unlike a bound tangent at a single fixed point), instantiated atc = exp 3 ≥ 20to boundlog log nfar more tightly than tangenting atc = ewould — the second ingredient (besidesReal.pow_div_factorial_le_exp) that keepssaturation_stage2b's threshold onlog nmodest.
Quadratic-tight lower bound on log for x ∈ [1/2, 1]:
log x ≥ (x - 1) - (x - 1)². (The crude linear bound log x ≥ x - 1 is
false for x < 1; this corrected version holds throughout [1/2, 1].)
Tangent-line log bound: for L > 0 and any reference point c > 0,
log L ≤ log c - 1 + L / c, from the crude linear bound log t ≤ t - 1
applied to t := L / c. Tight at L = c (equality there), unlike a single
globally-fixed reference point, so choosing c close to the L actually in
play gives a far sharper bound than e.g. c = e.
exp 3 ≥ 20, from cubing the standard 10-digit lower bound on e
(Real.exp_one_gt_d9) via Real.exp_nat_mul.
log log x ≤ 2 + (log x) / 20 for log x > 0: the tangent-line
bound log_le_tangent_div at the reference point c = exp 3 (so
log c = 3 exactly), combined with exp_three_ge_twenty to replace
1 / exp 3 by the cruder but rational 1 / 20. Far tighter than a bound
tangent at the fixed point c = e once log x is more than a few units
above e, which is exactly the regime saturation_stage2b needs.