Integrated contracted-counter output formula
ProvedCountingLLL.ContractedWalk.counter_integral_correctnessanalysisprobability
For , put and . The source’s contracted-counter generating function satisfies . This verifies the integrated output formula in the abstract walk model; the correspondence with the full ReciprocalTest execution remains separate.
Preamble
import Definitions.Def_CountingLLL_ContractedGF open MeasureTheory CountingLLL.ContractedWalk open scoped Interval
Formal statement
theorem CountingLLL.ContractedWalk.counter_integral_correctness (B : ℝ) (hB0 : 0 < B) (hB1 : B < 1)
(hB : Real.exp (-(3/10 : ℝ)) ≤ B) :
let u := 2*(1-B)/(2-B)
let θ := u^2/(1-u+u^2)
1 - (∫ z in (0:ℝ)..1, ((1-u)*generatingFunction θ z + u*z*(generatingFunction θ z)^3))/2 = 1/(2*B) := 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 pp. 27–28, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/442.pdf