An upper bound of 4.268 for the random 3-SAT satisfiability threshold
Abstract
We prove that a random 3-SAT formula with n variables and ⌊ 4.268n⌋ clauses is unsatisfiable with high probability. The satisfiability threshold has attracted considerable attention: successive upper bounds reached 4.4898 in the work of Díaz, Kirousis, Mitsche, and Pérez-Giménez, while the cavity method predicts a value near 4.267. Our bound brings the rigorous upper estimate close to this prediction. The proof builds on earlier interpolation methods, including the energetic approach of Achlioptas and Menchaca-Méndez. We study the smallest number of clauses that any assignment must violate, comparing the random formula with a simpler system of constraints on individual variables. This comparison reduces the bound to a finite calculation, which we verify using exact rational arithmetic. The proof is formalized in Lean 4.
Related
- The satisfiability threshold of random linear equations over finite commutative rings
- Almost sure upper bound for random multiplicative functions
- A sharp almost sure upper bound for partial sums of random multiplicative functions
- Almost sure upper bound for sums of random multiplicative functions and critical chaos
- An upper bound on the smallest singular value of dense signed random combinatorial matrices
BibTeX
@misc{vorobyev2026upper,
title = {{An upper bound of 4.268 for the random 3-SAT satisfiability threshold}},
author = {Fedor Vorobyev},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.10599},
eprint = {2610.10599},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.10599},
}
RIS
TY - UNPB
TI - An upper bound of 4.268 for the random 3-SAT satisfiability threshold
AU - Fedor Vorobyev
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.10599
UR - https://arxiv.org/abs/2610.10599
AB - We prove that a random 3-SAT formula with n variables and ⌊ 4.268n⌋ clauses is unsatisfiable with high probability. The satisfiability threshold has attracted considerable attention: successive upper bounds reached 4.4898 in the work of Díaz, Kirousis, Mitsche, and Pérez-Giménez, while the cavity method predicts a value near 4.267. Our bound brings the rigorous upper estimate close to this prediction. The proof builds on earlier interpolation methods, including the energetic approach of Achlioptas and Menchaca-Méndez. We study the smallest number of clauses that any assignment must violate, comparing the random formula with a simpler system of constraints on individual variables. This comparison reduces the bound to a finite calculation, which we verify using exact rational arithmetic. The proof is formalized in Lean 4.
ER -