Paper oracle-cost expression with the source walk is below three
ProvedCountingLLL.ReciprocalTest.paper_cost_expressionalgorithmsprobability
Let , put and , and let be the expected reciprocal-counter change weight of the abstract contracted walk from level three and counter two. Then the paper’s displayed expression, with numerator , is strictly less than three. The equality between that expression and the operational algorithm’s expected oracle calls remains separate.
Preamble
import Definitions.Def_CountingLLL_ContractedCost open CountingLLL.ContractedWalk open scoped ENNReal
Formal statement
theorem CountingLLL.ReciprocalTest.paper_cost_expression (B : ℝ) (hB : Real.exp (-(3/10 : ℝ)) ≤ B) (hB1 : B ≤ 1) :
let u := 2*(1-B)/(2-B)
let θ := u^2/(1-u+u^2)
let M := (expectedWeightedChanges (ENNReal.ofReal θ) 3 2).toReal
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