An upper bound of 4.268 for the random 3-SAT satisfiability threshold
En palabras de los autores
We prove that a random 3-SAT formula with variables and clauses is unsatisfiable with high probability. The satisfiability threshold has attracted considerable attention: successive upper bounds reached 4.4898 in the work of D\'iaz, Kirousis, Mitsche, and P\'erez-Gim\'enez, 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\'endez. 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.
Apareció: viernes, 9 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 16 pages, 1 figure. Includes a complete Lean 4 formalization and a reproducible rational certificate