Random k-SAT reconstruction rate and first onset
DefinitionKSATSingleFlip_Connect_ReconstructionThresholdWith and fixed, let be the limit as of the fixed-radius limit superior of the expected reconstruction signal. Define satisfiability with high probability by convergence of the satisfiability probability to one as , and define the first reconstruction onset as the infimum of nonnegative, satisfiable-with-high-probability densities at which . No monotonicity in density is assumed. The Lean limit is specified using the limit operator; a theorem using it must establish convergence of the underlying profile.
Definition code
import Definitions.Def_KSATSingleFlip_Connect_Reconstruction
noncomputable section
open scoped Classical BigOperators
open Filter Topology
namespace KSATSingleFlip.Connect
open OAI.FixedClauseThreshold
/-- The outer r→∞ limit in the source definition of reconstruction. -/
def reconstructionRate (k : ℕ) (α : ℝ) : ℝ :=
atTop.limUnder (reconstructionProfile k α)
/-- Satisfiability with high probability in the fixed-k, fixed-density limit. -/
def satisfiableWhp (k : ℕ) (α : ℝ) : Prop :=
Tendsto (fun n => formulaProb n k ⌊α * n⌋₊ (fun F => FSatPossible (ofFormula F)))
atTop (𝓝 1)
where
FSatPossible {n : ℕ} (Φ : GFormula (Fin n)) : Prop := ∃ x, FSat x Φ
/-- First reconstruction onset among nonnegative densities at which the formula
is satisfiable with high probability; no monotonicity in density is assumed. -/
def reconstructionThreshold (k : ℕ) : ℝ :=
sInf {α : ℝ | 0 ≤ α ∧ satisfiableWhp k α ∧ 0 < reconstructionRate k α}
end KSATSingleFlip.Connect
Source
Wang, Yin, Yu, Zhang, Single-Variable Connectivity in Random k-SAT, paragraph preceding Theorem 1.2, printed p. 3 (PDF p. 5), STOC 2027 submission #737, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/737.pdf