An explicit size threshold for Poisson mean fluctuations
ProvedKSATSingleFlip.Connect.lemma_2_6_size_conditionFor positive a, L and n, if 16 L²ν ≤ a²n then √(νn) ≤ an/(4L). This makes the large-n condition in the Poisson-count proof of Lemma 2.6 explicit.
Preamble
import Mathlib set_option autoImplicit false
Formal statement
theorem KSATSingleFlip.Connect.lemma_2_6_size_condition (ν a L n : ℝ) (hν : 0 ≤ ν) (ha : 0 < a) (hL : 0 < L) (hn : 0 < n)
(hsize : 16*L^2*ν ≤ a^2*n) :
Real.sqrt (ν*n) ≤ a*n/(4*L) := by sorrySource
Wang–Yin–Yu–Zhang, Single-Variable Connectivity in Random k-SAT, Lemma 2.6, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/737.pdf