First-hit factorization of contracted-walk generating functions
ProvedCountingLLL.ContractedWalk.generating_function_factorprobability
For and , let be the generating function of upward moves before the contracted walk from level reaches zero. Then . This is the independent first-hit segmentation used in the paper to obtain the cubic recursion.
Preamble
import Definitions.Def_CountingLLL_ContractedGF open MeasureTheory CountingLLL.ContractedWalk
Formal statement
theorem CountingLLL.ContractedWalk.generating_function_factor (θ z : ℝ) (hθ0 : 0 ≤ θ) (hθ : θ < 1/3)
(hz0 : 0 ≤ z) (hz1 : z ≤ 1) (m : ℕ) :
(∫ ω : Tape, z ^ upwardCount ω (m+1) ∂tapeLaw (ENNReal.ofReal θ)) =
(∫ ω : Tape, z ^ upwardCount ω 1 ∂tapeLaw (ENNReal.ofReal θ)) *
(∫ ω : Tape, z ^ upwardCount ω m ∂tapeLaw (ENNReal.ofReal θ)) := 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. 27, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/442.pdf