Source reciprocal-test weighted walk cost satisfies M < 74/25
ProvedCountingLLL.ContractedWalk.source_M_boundalgorithmsanalysisprobability
For , let be the expected sum of reciprocal-counter weights before changes of the abstract contracted walk started at level three and counter two. Then
This is the sharp numerical bound required in the paper’s oracle-call analysis. Connecting that abstract walk to the operational ReciprocalTest and deriving the full expected-call formula are separate results.
Preamble
import Definitions.Def_CountingLLL_ContractedCost open MeasureTheory CountingLLL.ContractedWalk open scoped ENNReal
Formal statement
theorem CountingLLL.ContractedWalk.source_M_bound (θ : ℝ) (hθ0 : 0 ≤ θ) (hθ1 : θ ≤ 9/40) :
expectedWeightedChanges (ENNReal.ofReal θ) 3 2 < ENNReal.ofReal (74/25 : ℝ) := 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