Lemma 8.11 — Exponential-rate bound
OpenKSATSingleFlip.Connect.lemma_8_11For the binary entropy with , define
Then
This numerical bound makes the exponential rate in the witness count strictly negative. The formal statement uses the equivalent strict bound at every point of ; continuity on this compact interval ensures that the maximum is attained.
Preamble
import Definitions.Def_KSATSingleFlip_Connect_WitnessRate
Formal statement
namespace KSATSingleFlip.Connect
/-- Lemma 8.11: the witness exponential rate is uniformly negative. -/
theorem lemma_8_11 :
∀ b ∈ Set.Icc (0 : ℝ) 1, witnessRate (13 / 34) (6 / 7) b < -(99 : ℝ) / 2000000 := by
sorry
end KSATSingleFlip.Connect
Source
Chunyang Wang, Yitong Yin, Yixiao Yu, Yiyao Zhang, Single-Variable Connectivity in Random k-SAT, Lemma 8.11, printed p. 71 (PDF p. 73) of STOC 2027 submission #737, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/737.pdf