Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Random k-SAT exterior reconstruction observables

Definition
KSATSingleFlip_Connect_Reconstruction

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

For a Boolean CNF formula, form the graph in which distinct variables are adjacent when they occur in a common clause. The exterior Br(v)B_r(v)Br​(v) consists of variables at distance at least rrr from vvv, including disconnected variables. Let pvp_vpv​ be the uniform-solution marginal at vvv and let qv,rq_{v,r}qv,r​ be the marginal after conditioning on the sampled exterior. These definitions give pvp_vpv​, qv,rq_{v,r}qv,r​, the expectation of ∣qv,r−pv∣|q_{v,r}-p_v|∣qv,r​−pv​∣, the Bayes prediction error min⁡(qv,r,1−qv,r)\min(q_{v,r},1-q_{v,r})min(qv,r​,1−qv,r​), and the fixed-rrr limit superior as the variable count tends to infinity. Formula, variable and solution are sampled as in Theorem 1.2; unsatisfiable formulas contribute zero.

Definition code
import Definitions.Def_KSATSingleFlip_Connect_Model

noncomputable section
open scoped Classical BigOperators
open Filter
namespace KSATSingleFlip.Connect
open OAI.FixedClauseThreshold

/-- Variables are adjacent if they occur together in a clause. -/
def variableGraph {n : ℕ} (Φ : GFormula (Fin n)) : SimpleGraph (Fin n) :=
  SimpleGraph.fromRel fun u v => ∃ C ∈ Φ, u ∈ vbl C ∧ v ∈ vbl C

/-- Variables at graph distance at least r from v. Disconnected variables
have infinite distance and are included at every finite radius. -/
def exterior {n : ℕ} (Φ : GFormula (Fin n)) (v : Fin n) (r : ℕ) : Finset (Fin n) :=
  Finset.univ.filter fun u => ¬ (variableGraph Φ).Reachable v u ∨ r ≤ (variableGraph Φ).dist v u

/-- The uniform-solution marginal at v, with value 0 when the formula is unsatisfiable. -/
def vertexMarginal {n : ℕ} (Φ : GFormula (Fin n)) (v : Fin n) : ℝ :=
  (((sols Φ).filter fun x => x v = true).card : ℝ) / (numSols Φ : ℝ)

/-- Satisfying assignments agreeing with x on the exterior of the radius-r ball. -/
def exteriorFiber {n : ℕ} (Φ : GFormula (Fin n)) (v : Fin n) (r : ℕ)
    (x : Fin n → Bool) : Finset (Fin n → Bool) :=
  (sols Φ).filter fun y => ∀ u ∈ exterior Φ v r, y u = x u

/-- Conditional solution marginal after revealing the exterior, with zero
for an empty conditional fiber. -/
def exteriorPosterior {n : ℕ} (Φ : GFormula (Fin n)) (v : Fin n) (r : ℕ)
    (x : Fin n → Bool) : ℝ :=
  (((exteriorFiber Φ v r x).filter fun y => y v = true).card : ℝ) /
    ((exteriorFiber Φ v r x).card : ℝ)

/-- Average reconstruction signal over a uniform variable and uniform solution.
On an unsatisfiable formula, the empty uniform average is zero. -/
def reconstructionSignal {n : ℕ} (Φ : GFormula (Fin n)) (r : ℕ) : ℝ :=
  uexp fun v : Fin n => uexp fun x : {x // x ∈ sols Φ} =>
    |exteriorPosterior Φ v r x.1 - vertexMarginal Φ v|

/-- Average optimal 0–1 prediction error given the revealed exterior. -/
def reconstructionError {n : ℕ} (Φ : GFormula (Fin n)) (r : ℕ) : ℝ :=
  uexp fun v : Fin n => uexp fun x : {x // x ∈ sols Φ} =>
    min (exteriorPosterior Φ v r x.1) (1 - exteriorPosterior Φ v r x.1)

/-- Average signal at fixed k,n,α,r over the fixed-clause random k-SAT law. -/
def expectedReconstructionSignal (k n : ℕ) (α : ℝ) (r : ℕ) : ℝ :=
  uexp fun F : Formula n k ⌊α * n⌋₊ => reconstructionSignal (ofFormula F) r

/-- Average Bayes prediction error in the same model. -/
def expectedReconstructionError (k n : ℕ) (α : ℝ) (r : ℕ) : ℝ :=
  uexp fun F : Formula n k ⌊α * n⌋₊ => reconstructionError (ofFormula F) r

/-- The inner limit superior, first n→∞ with k, α, r fixed. -/
def reconstructionProfile (k : ℕ) (α : ℝ) (r : ℕ) : ℝ :=
  Filter.limsup (fun n => expectedReconstructionSignal k n α r) atTop

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

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