Lipschitz bound for the admissible cubic root
ProvedCountingLLL.ContractedWalk.cubic_root_lipschitzanalysisprobability
For , two admissible roots of at parameters satisfy . This gives continuity of the contracted-walk generating function needed for the source’s change of variables.
Preamble
import Mathlib
Formal statement
theorem CountingLLL.ContractedWalk.cubic_root_lipschitz (θ x y g h : ℝ) (ht0 : 0 ≤ θ) (ht : θ < 1/3)
(hx0 : 0 ≤ x) (hx : x ≤ 1) (hy0 : 0 ≤ y) (hy : y ≤ 1)
(hg0 : 0 ≤ g) (hg : g ≤ 1) (hh0 : 0 ≤ h) (hh : h ≤ 1)
(hgEq : g = 1-θ+θ*x*g^3) (hhEq : h = 1-θ+θ*y*h^3) :
|g-h| ≤ θ/(1-3*θ)*|x-y| := 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