Limiting random SAT thresholds, sharp variance and computability

What OpenAI claims

For random k-SAT with independent uniformly signed proper clauses sampled with replacement, proves finite positive limiting thresholds and hitting-time variance Θ_k(n) for every fixed k ≥ 3, and computability of the 3-SAT threshold. We credit Gaia Carenini with priority for resolving the threshold-existence conjecture in her concurrent ECCC TR26-229, made public October 5, 2026; this family supplies another proof and the sharper variance and computability results. (Lean)

Papers (4)

1. A Limiting Satisfiability Threshold for Every Fixed Clause Size

   25 September 2026 · Preprint, not peer reviewed · PDF

   For every fixed integer k ≥ 3, random k-SAT with independent uniformly signed clauses on distinct variables, sampled with replacement, has a finite positive limiting satisfiability threshold. We credit Gaia Carenini [5] with priority for resolving the satisfiability conjecture. This paper gives an alternative proof, using concentration of a capped last satisfiable index and a comparison between different system sizes.

2. Linear Variance of the Random 3-SAT Hitting Time

   5 October 2026 · Preprint, not peer reviewed · PDF

   For random 3-SAT on n Boolean variables, with independent uniformly signed clauses on three distinct variables sampled with replacement, we prove that the first unsatisfiable prefix has variance Θ(n). The upper bound removes the logarithmic loss in the earlier variance estimate; the matching lower bound follows from Wilson's transition-width theorem.

3. Variance of the Random k-SAT Hitting Time

   27 September 2026 · Preprint, not peer reviewed · PDF

   Let Hn be the index of the first unsatisfiable prefix in random k-SAT on n variables, with independent uniformly signed clauses using k distinct variables and sampled with replacement. For every fixed k ≥ 4, we prove Var (H_n)=Θ_k(n). For k = 3, the variance is bounded below by a positive multiple of n and above by a constant multiple of n log n; the companion paper on random 3-SAT sharpens this to Θ(n). The same upper bounds proved here hold after clipping at any fixed positive multiple of n.

4. Computing the Random 3-SAT Threshold

   27 September 2026 · Preprint, not peer reviewed · PDF

   The limiting satisfiability threshold of uniform random 3-SAT is a computable real. We credit Gaia Carenini [4] with priority for resolving the satisfiability conjecture, which establishes the threshold's existence. We prove that one finite deterministic machine can approximate it to any prescribed accuracy. A deletion estimate gives explicit lower certificates, while a finite hierarchical approximation of the soft pressure gives upper certificates at every larger rational density. A fair search through these certificates halts without requiring a computable rate of finite-size convergence.

Status

Preprint. The papers have not been independently reviewed. Treat the result as OpenAI's claim until other mathematicians have checked it. If a video exists, it illustrates the statement; it is not the proof.