Paper oracle-cost expression is strictly below three
ProvedCountingLLL.ReciprocalTest.paper_oracle_cost_scalar_boundanalysisprobability
For and , the numerical expression in the paper’s expected oracle-call calculation, with numerator , is strictly smaller than . This is a scalar inequality; it does not identify the expression with any operational expected cost.
Preamble
import Mathlib
Formal statement
theorem CountingLLL.ReciprocalTest.paper_oracle_cost_scalar_bound (u M : ℝ) (hu0 : 0 ≤ u) (hu1 : u ≤ 33/80)
(hM0 : 0 ≤ M) (hM : M ≤ 74/25) :
1-u+(1-u^2)/(1-u+u^2) * (1-u+u/(1-u+u^2)*M) < 3 := by sorrySource
Liu, Wang, Yin, Zhang and Zhou, A Counting and Sampling Lovász Local Lemma, STOC #442, proof of Lemma 6.5, calls to O, p. 28, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/442.pdf