Documentation

ThreeMajority.Bounds

Elementary exponential and logarithm bounds #

Numeric lemmas underpinning the Chernoff-exponent estimates elsewhere in the development, none requiring calculus/derivatives:

theorem ThreeMajority.log_ge_quadratic {x : ℝ} (hx0 : 1 / 2 ≤ x) (hx1 : x ≤ 1) :
x - 1 - (x - 1) ^ 2 ≤ Real.log x

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].)

theorem ThreeMajority.log_le_tangent_div {L c : ℝ} (hL : 0 < L) (hc : 0 < c) :
Real.log L ≤ Real.log c - 1 + L / c

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.

theorem ThreeMajority.two_le_of_hbig {n : ℕ} (hbig : 30 ≤ Real.log ↑n) :
2 ≤ n

log n ≥ 30 already forces n ≥ 2: makes an explicit 2 ≤ n hypothesis redundant everywhere it appears alongside hbig, since Real.log 0 = Real.log 1 = 0 < 30.