Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1.2 — Reconstruction onset

Open
KSATSingleFlip.Connect.theorem_1_2

by wcysai · Nov 13, 2026 · Mathlib 0df444a (Lean v4.33.1)

For fixed kkk and α\alphaα, let Rk(α)R_k(\alpha)Rk​(α) be the reconstruction signal obtained by taking first lim sup⁡n→∞\limsup_{n\to\infty}limsupn→∞​ and then the limit as r→∞r\to\inftyr→∞. The outer limit exists. For all sufficiently large kkk, non-reconstruction holds throughout (1.2):

0≤α≤2kk(ln⁡k+ln⁡ln⁡k+γ∗−(ln⁡ln⁡k)−1/16).0\le\alpha\le\frac{2^k}{k}\left(\ln k+\ln\ln k+\gamma_*-(\ln\ln k)^{-1/16}\right).0≤α≤k2k​(lnk+lnlnk+γ∗​−(lnlnk)−1/16).

For every ε>0\varepsilon>0ε>0 and sufficiently large kkk, reconstruction holds throughout

2kk(ln⁡k+ln⁡ln⁡k+γ∗+ε)≤α≤2k(ln⁡2−1ln⁡k).\frac{2^k}{k}(\ln k+\ln\ln k+\gamma_*+\varepsilon)\le\alpha\le2^k\left(\ln2-\frac1{\ln k}\right).k2k​(lnk+lnlnk+γ∗​+ε)≤α≤2k(ln2−lnk1​).

At each fixed r≥1r\ge1r≥1, the formula and the sampled exterior predict the root with expected error at most C/(kln⁡k)+on(1)C/(k\ln k)+o_n(1)C/(klnk)+on​(1), with an absolute CCC and the error uniform in α\alphaα over this interval. Consequently the first reconstruction onset among satisfiable-with-high-probability densities satisfies

αclust(k)=2kk(ln⁡k+ln⁡ln⁡k+γ∗+ok(1)).\alpha_{\rm clust}(k)=\frac{2^k}{k}(\ln k+\ln\ln k+\gamma_*+o_k(1)).αclust​(k)=k2k​(lnk+lnlnk+γ∗​+ok​(1)).

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

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me