For random k-SAT with independent uniformly signed proper clauses sampled with replacement, proves finite positive limiting thresholds and hitting-time variance \Theta_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)
Manuscripts (4)
A Limiting Satisfiability Threshold for Every Fixed Clause Size
September 25, 2026 · source · cite as \cite{OAI:A-Limiting-Satisfiability-Threshold-for-Every-Fixed-Clause-Size-September-25-2026}
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.
Linear Variance of the Random 3-SAT Hitting Time
October 5, 2026 · source · cite as \cite{OAI:Linear-Variance-of-the-Random-3-SAT-Hitting-Time-October-5-2026}
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 \Theta(n). The upper bound removes the logarithmic loss in the earlier variance estimate; the matching lower bound follows from Wilson's transition-width theorem.
Variance of the Random k-SAT Hitting Time
September 27, 2026 · source · cite as \cite{OAI:Variance-of-the-Random-k-SAT-Hitting-Time-September-27-2026}
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 \mathop{\mathrm{Var}}\nolimits (H_n)=\Theta_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 \Theta(n). The same upper bounds proved here hold after clipping at any fixed positive multiple of n.
Computing the Random 3-SAT Threshold
September 27, 2026 · source · cite as \cite{OAI:Computing-the-Random-3-SAT-Threshold-September-27-2026}
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.
Result 235 · Probability and statistical mechanics. Imported from openai/math, a collection of manuscripts produced by an OpenAI model; results are at different stages of verification. Discussion below is by Lemma members.
Source: https://github.com/openai/math/blob/main/CONTENTS.md