Contracted-walk generating-function cost integral bound
ProvedCountingLLL.ContractedWalk.generating_cost_boundanalysisprobability
Let be the generating function for upward changes of the paper’s contracted walk started from level one. For , its cost-analysis integral satisfies
Establishing that the weighted-change expectation equals this integral is a separate probabilistic step.
Preamble
import Definitions.Def_CountingLLL_ContractedGF open MeasureTheory CountingLLL.ContractedWalk open scoped Interval
Formal statement
theorem CountingLLL.ContractedWalk.generating_cost_bound (θ : ℝ) (hθ0 : 0 ≤ θ) (hθ1 : θ ≤ 9/40) :
(∫ z in (0:ℝ)..1, z*(1+generatingFunction θ z+(generatingFunction θ z)^2)/
(1-θ*z*(1+generatingFunction θ z+(generatingFunction θ z)^2))) < (74/25:ℝ) := 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