Contracted walk: level bounded by the running counter
ProvedCountingLLL.ContractedWalk.running_level_boundcombinatoricsprobability
In the abstract contracted walk, start at level with . At any time, let be the initial counter plus the number of upward changes so far. Then the current level is at most . This pathwise inequality is part of the source computational-overhead argument; connecting the abstract walk to the operational algorithm remains a separate task.
Preamble
import Definitions.Def_CountingLLL_ContractedWalk open CountingLLL.ContractedWalk open scoped BigOperators
Formal statement
theorem CountingLLL.ContractedWalk.running_level_bound (ω : Tape) (j t : ℕ) (hj : 1 ≤ j) : level ω (2*j-1) t ≤ 2 * (j + ∑ k ∈ Finset.range t, if level ω (2*j-1) k ≠ 0 ∧ ω k = true then 1 else 0) - 1 := by sorry
Source
Liu, Wang, Yin, Zhang and Zhou, A Counting and Sampling Lovász Local Lemma, STOC #442, proof of Lemma 6.5, computational overhead, p. 28, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/442.pdf