Cubic identity for the source weighted-change cost integrand
ProvedCountingLLL.ContractedWalk.cost_integrand_cubicanalysisprobability
Let be the source contracted-walk generating function, , and . Then
This follows from the cubic equation for and is the pointwise algebra connecting the harmonic generating function to the cost integral. The probabilistic weighted-change identity remains separate.
Preamble
import Definitions.Def_CountingLLL_ContractedGF open CountingLLL.ContractedWalk
Formal statement
theorem CountingLLL.ContractedWalk.cost_integrand_cubic (θ z : ℝ) (hθ0 : 0 < θ) (hθ1 : θ < 1/3)
(hz0 : 0 ≤ z) (hz1 : z < 1) :
let g := generatingFunction θ z
((1-g)/(θ*(1-z))-1)/θ = z*(1+g+g^2)/(1-θ*z*(1+g+g^2)) := 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