ReciprocalTest source oracle-cost expression is below three
ProvedCountingLLL.ReciprocalTest.oracle_cost_scalar_boundinequalitiesprobability
For and , the displayed formal expression with numerator is strictly less than . This is a valid auxiliary inequality but is not the paper’s oracle-cost expression: the source uses instead. The source-faithful correction is being formalized separately.
Preamble
import Mathlib
Formal statement
theorem CountingLLL.ReciprocalTest.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 2027 #442, proof of Lemma 6.5, PDF p. 28, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/442.pdf