Browse › Probability and statistical mechanics › 235 Limiting random SAT thresholds, sharp variance and computability
Variance of the Random k-SAT Hitting Time
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
Abstract
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.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Formalization
- OpenAI math release, Limiting random SAT thresholds, sharp variance and computability — Lean scope notes (lean/docs/235.md, October 2026). Describes Lean statements of $\mathrm{Var}(H_n)=\Theta_k(n)$ for $k\ge4$ and of the linear lower bound and $O(n\log n)$ upper bound for $k=3$, including the capped versions (comparator
SATVariance.lean), as well as the sharpness supplements (SATSharpness.lean). [family-level]
Related prior literature mentioned by others
- Gaia Carenini, A polynomial scaling window for random k-SAT and a proof of the satisfiability conjecture (ECCC TR26-229, 5 October 2026). Its polynomial scaling-window bound and limiting-threshold theorem provide concurrent context for this paper’s sharper fluctuation estimates, and the release credits it with priority for threshold existence. [family-level]
Possibly relevant literature (found by the agent, not checked)
- B. Bollobás, C. Borgs, J. T. Chayes, J. H. Kim, D. B. Wilson, The Scaling Window of the 2-SAT Transition (Random Structures Algorithms 18 (2001); arXiv:math/9909031). This paper determines the 2-SAT scaling window as $1\pm\Theta(n^{-1/3})$ in density, which gives a point of comparison for the transition-window width $O_{k,\eta}(\sqrt{n\ell_k(n)})$ in clauses that the paper derives for $k\ge3$.
News and blogs
- OfficeChai Team, OpenAI Releases Over 300 Mathematical Results Produced By An Internal Model (OfficeChai, 7 October 2026). Discusses the random SAT family specifically through its credit to Carenini for priority on threshold existence. [family-level]
Elsewhere
- Emergent Mind: family 235
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:Variance-of-the-Random-k-SAT-Hitting-Time-September-27-2026,
author = {{OpenAI}},
title = {{Variance of the Random $k$-SAT Hitting Time}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Variance-of-the-Random-k-SAT-Hitting-Time-September-27-2026/article.pdf}{OAI:Variance-of-the-Random-k-SAT-Hitting-Time-September-27-2026}},
year = {2026}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/235.md. The Lean statements have not been checked by people against the paper's claims.
Family 235: Limiting random SAT thresholds, sharp variance and computability
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.
Other papers in this family:
- A Limiting Satisfiability Threshold for Every Fixed Clause Size · September 25, 2026
- Linear Variance of the Random 3-SAT Hitting Time · October 5, 2026
- Computing the Random 3-SAT Threshold · September 27, 2026