Appendix B.4, p. 18 — ceiling choice and exponential ratio bound
ProvedCompositeLB.DetSC.ratio_exp_boundexponential-decaylower-boundp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1real-inequality
Let , , and let nonnegative integers satisfy . Then
This turns the chain's geometric decay into a bound expressed in completed rounds.
Formalization Note The hypotheses give , so and the ceiling has its intended meaning. The ceiling is an integer, matching .
Preamble
import Mathlib import Definitions.Def_CompositeLB_DetSC_HardInstance
Formal statement
namespace CompositeLB.DetSC
/-- Appendix B.4, p. 18: the ceiling choice of `k` yields an exponential gap. -/
theorem ratio_exp_bound (Q q : ℝ) (hQ : 1 < Q)
(hq : q = (Real.sqrt Q - 1) / (Real.sqrt Q + 1))
(t k : ℕ)
(hk : (k : ℤ) + 1 = ⌈(t : ℝ) - 1 / (2 * Real.log q)⌉) :
(q ^ (2 * t) - q ^ (2 * k + 2)) / Real.sqrt Q ≥
q ^ (2 * t) / (2 * Real.sqrt Q) ∧
q ^ (2 * t) / (2 * Real.sqrt Q) ≥
1 / (2 * Real.sqrt Q) *
Real.exp (-4 * (t : ℝ) / (Real.sqrt Q - 1)) := by sorry
end CompositeLB.DetSC
Source
Woodworth & Srebro, arXiv:1605.08003v3, App. B.4, p. 18, opening display
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.