Generating function for the contracted walk’s final counter
ProvedCountingLLL.ContractedWalk.initial_counter_generating_functionprobability
Let an independent initial bit equal one with probability . If it is zero, start the contracted walk at level one with counter one; if it is one, start at level three with counter two. Let be the final counter, incremented on each upward move. For , and , its generating function satisfies . This is the paper’s suppressed-early-return contracted-walk model; its coupling to the full machine remains separate.
Preamble
import Definitions.Def_CountingLLL_ContractedGF open MeasureTheory CountingLLL.ContractedWalk open scoped ENNReal
Formal statement
theorem CountingLLL.ContractedWalk.initial_counter_generating_function (u θ z : ℝ) (hu0 : 0 ≤ u) (hu1 : u ≤ 1)
(hθ0 : 0 ≤ θ) (hθ : θ < 1/3) (hz0 : 0 ≤ z) (hz1 : z ≤ 1) :
(∫ x : Bool × Tape, z ^ (if x.1 then 1 + upwardCount x.2 3 else upwardCount x.2 1)
∂((bitLaw (ENNReal.ofReal u)).prod (tapeLaw (ENNReal.ofReal θ)))) =
(1-u)*generatingFunction θ z + u*z*(generatingFunction θ z)^3 := 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