Theorem 1.2 — Reconstruction onset
OpenKSATSingleFlip.Connect.theorem_1_2For fixed and , let be the reconstruction signal obtained by taking first and then the limit as . The outer limit exists. For all sufficiently large , non-reconstruction holds throughout (1.2):
For every and sufficiently large , reconstruction holds throughout
At each fixed , the formula and the sampled exterior predict the root with expected error at most , with an absolute and the error uniform in over this interval. Consequently the first reconstruction onset among satisfiable-with-high-probability densities satisfies
The formal statement spells out the error limit and its quantifiers. The rate uses a limit operator, and its convergence is stated explicitly; no density-monotonicity assumption is made.
Preamble
import Definitions.Def_KSATSingleFlip_Connect_ReconstructionThreshold import Definitions.Def_KSATSingleFlip_Connect_SoftField open scoped Classical BigOperators open Filter Topology
Formal statement
namespace KSATSingleFlip.Connect
/-- Theorem 1.2: the reconstruction onset and prediction error. -/
theorem theorem_1_2 :
(∀ k : ℕ, 2 ≤ k → ∀ α : ℝ, 0 ≤ α →
Tendsto (reconstructionProfile k α) atTop (𝓝 (reconstructionRate k α))) ∧
(∃ k₀ : ℕ, ∀ k ≥ k₀, ∀ α : ℝ, 0 ≤ α → α ≤ densityBound k gammaStar →
reconstructionRate k α = 0) ∧
(∃ C : ℝ, 0 < C ∧ ∀ ε : ℝ, 0 < ε → ∃ k₀ : ℕ, ∀ k ≥ k₀,
(∀ α : ℝ, 0 ≤ α →
((2 : ℝ) ^ k / k) * (Real.log k + Real.log (Real.log k) + gammaStar + ε) ≤ α →
α ≤ (2 : ℝ) ^ k * (Real.log 2 - 1 / Real.log k) →
0 < reconstructionRate k α) ∧
(∀ r : ℕ, 1 ≤ r → ∀ δ : ℝ, 0 < δ → ∃ n₀ : ℕ, ∀ n ≥ n₀, ∀ α : ℝ,
0 ≤ α →
((2 : ℝ) ^ k / k) * (Real.log k + Real.log (Real.log k) + gammaStar + ε) ≤ α →
α ≤ (2 : ℝ) ^ k * (Real.log 2 - 1 / Real.log k) →
expectedReconstructionError k n α r ≤ C / ((k : ℝ) * Real.log k) + δ)) ∧
Tendsto (fun k : ℕ => ((k : ℝ) / (2 : ℝ) ^ k) * reconstructionThreshold k -
Real.log k - Real.log (Real.log k) - gammaStar) atTop (𝓝 0) := by
sorry
end KSATSingleFlip.Connect
Source
Chunyang Wang, Yitong Yin, Yixiao Yu, Yiyao Zhang, Single-Variable Connectivity in Random k-SAT, Theorem 1.2 and preceding definition, printed p. 3 (PDF p. 5) of STOC 2027 submission #737, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/737.pdf