ReciprocalTest contracted-walk parameter bounds
ProvedCountingLLL.ReciprocalTest.source_parameter_boundsinequalitiesprobability
Under the hypothesis of Lemma 6.5, put and . Then and . These are the explicit bounds used in the analysis of Algorithm 6.
Preamble
import Mathlib
Formal statement
theorem CountingLLL.ReciprocalTest.source_parameter_bounds (B : ℝ) (hB : Real.exp (-(3/10 : ℝ)) ≤ B) (hB1 : B ≤ 1) :
let u := 2*(1-B)/(2-B)
let θ := u^2/(1-u+u^2)
0 ≤ u ∧ u < 33/80 ∧ 0 ≤ θ ∧ θ < 9/40 := 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