The satisfiability threshold of random k-SAT for small k: convergence of the threshold densities $r_k(n)$ and tighter rigorous upper bounds for random 3-SAT

In the fixed-length random $k$-SAT model, $m = rn$ clauses are drawn uniformly at random over $n$ Boolean variables, and for $k \ge 3$ the probability of satisfiability drops sharply around a critical density. Friedgut proved a sharp threshold at an $n$-dependent density $r_k(n)$, but whether $r_k(n)$ converges to a constant $r_k$ — the satisfiability conjecture — remains open for every fixed small $k$, notably $k = 3$, where the rigorous bounds $3.52 \le r_3 \le 4.268$ still leave a gap to the statistical-physics prediction of $r_3 \approx 4.267$. The source paper (Antonopoulou, 2020) derives an upper bound on the unsatisfiability threshold via Kolmogorov-complexity (incompressibility) arguments, generalizing an earlier 3-SAT incompressibility result, against the open conjecture that a constant threshold density $r_k$ exists for every $k$. Two cores of this setting remain open: (i) the convergence problem for small $k$, and (ii) improving the known rigorous upper bounds, in particular for random 3-SAT. Ding–Sly–Sun resolved the conjecture only for sufficiently large $k$, and the rigorous 3-SAT upper bound, long at 4.4898 (Díaz–Kirousis–Mitsche–Pérez-Giménez), was improved to 4.268 in 2026 (Vorobyev).

Background

Propositional satisfiability (SAT) asks whether a Boolean formula can be made true by some assignment of truth values to its variables; it is the canonical NP-complete problem. A $k$-CNF formula is a conjunction of clauses, each clause a disjunction of exactly $k$ literals (a variable or its negation). In the fixed-length random $k$-SAT model, a formula on $n$ variables is generated by choosing $m = rn$ clauses independently and uniformly at random from the $\binom{2n}{k}$ possible clauses, where $r > 0$ is the clause-to-variable density. Throughout, 'whp' (with high probability) means with probability tending to 1 as $n \to \infty$. Since the early 1990s, experiments and rigorous results have shown a threshold phenomenon: for fixed $k \ge 3$ there is a critical density — empirically near 4.2 for $k = 3$ — below which a random formula is satisfiable whp and above which it is unsatisfiable whp.

A standard tool for upper bounds is the first-moment method: if the expected number of satisfying assignments of a random formula tends to 0, the formula is unsatisfiable whp. Applied naively this yields the bound $r \ge -\ln 2 / \ln(1 - 2^{-k})$, about 5.19 for $k = 3$. All subsequent improvements count only a carefully selected subfamily of satisfying assignments. The most successful such refinement is the 'flips' technique of Dubois–Boufkhad–Mandler: count only locally maximal assignments — satisfying assignments that cease to satisfy the formula after any single variable is flipped (single-flip assignments) — which shrinks the expected count by an exponential factor; choosing the subfamily optimally becomes an optimization problem over the statistics of variable degrees. This line produced the record bound $r_3 \le 4.4898$ for the standard random 3-SAT model, due to Díaz–Kirousis–Mitsche–Pérez-Giménez (2008/2009), which remained the best rigorous upper bound until Vorobyev (2026) improved it to $r_3 \le 4.268$. On the satisfiable side, analyses of greedy assignment algorithms via the differential-equation method (tracking a random process by a deterministic system of ODEs) give $r_3 \ge 3.52$. Statistical-physics analyses based on the cavity method — a non-rigorous mean-field technique from spin-glass theory, refined into the 'survey propagation' algorithm — predict $r_3 \approx 4.267$, together with a clustered geometry of the solution space that is believed to explain both the threshold location and the computational hardness of instances near it.

Qualitatively, Friedgut (1999), building on general sharp-threshold machinery with an appendix by Bourgain, proved that for every $k \ge 3$ satisfiability of random $k$-SAT exhibits a sharp threshold at some $n$-dependent density $r_k(n)$ bounded between constants: for every $\varepsilon > 0$, formulas at density $(1 - \varepsilon) r_k(n)$ are satisfiable whp and at $(1 + \varepsilon) r_k(n)$ unsatisfiable whp. The satisfiability conjecture asserts the stronger statement that $r_k(n)$ converges to a constant $r_k$, so that the same dichotomy holds around an $n$-independent density for each $k \ge 2$. The conjecture is known for $k = 2$ (2-SAT is solvable in linear time via implication graphs) and, in a major breakthrough, for all sufficiently large $k$ by Ding–Sly–Sun (published 2022), who confirmed the physics prediction $r_k = 2^k \ln 2 - (1 + \ln 2)/2 + o_k(1)$ obtained from the one-step replica-symmetry-breaking (1-RSB) analysis; their argument requires $k$ above an ineffective constant and gives nothing for small $k$ such as 3.

Kolmogorov complexity measures the descriptional complexity of a finite string as the length of the shortest program that outputs it; most strings are incompressible (algorithmically random). The incompressibility method turns this into a proof technique: any scheme that encodes a combinatorial object together with structural data more compactly than the information-theoretic minimum must fail on incompressible instances, which yields counting bounds. Antonopoulou (2020) applied this descriptional-complexity approach to random $k$-SAT, deriving an upper bound on the unsatisfiability threshold that generalizes an earlier incompressibility-based result for random 3-SAT; the paper's abstract also recalls the conjecture that a constant threshold density $r_k$ exists for every $k$. Whether descriptional-complexity arguments — alone or combined with the flips refinement described above — can sharpen the known numerical upper bounds is an open question.

Problem Statement

Consider random $k$-SAT in the fixed-length model: a formula on $n$ Boolean variables is built by drawing $m = rn$ clauses, each a disjunction of $k$ literals chosen uniformly at random, for a fixed clause-to-variable density $r > 0$; 'whp' means with probability tending to 1 as $n \to \infty$. The problem, in the setting of the source paper (Antonopoulou, 2020) and left open by the field, is to locate the satisfiability threshold of random $k$-SAT for small clause sizes — the central case being $k = 3$ — through two linked components:

(1) Convergence of the threshold densities. Friedgut's theorem provides, for each $k \ge 3$, an $n$-dependent critical density $r_k(n)$ at which the satisfiability probability of a random formula drops sharply from 1 to 0. Determine whether $r_k(n)$ converges as $n \to \infty$ to a constant $r_k$ independent of $n$ — that is, prove or refute the satisfiability conjecture for fixed small $k$, in particular $k = 3$: does there exist $r_k$ such that for every $\varepsilon > 0$ a random formula is satisfiable whp at densities below $(1 - \varepsilon) r_k$ and unsatisfiable whp at densities above $(1 + \varepsilon) r_k$? (This is known only for $k = 2$ and for all sufficiently large $k$.)

(2) Tighter rigorous upper bounds for random 3-SAT. The best rigorous upper bound on the unsatisfiability threshold of the standard random 3-SAT model is 4.268 (Vorobyev, 2026), against a lower bound of 3.52 and a statistical-physics prediction of $r_3 \approx 4.267$. Establish a rigorous upper bound strictly below 4.268 for the fixed-length random 3-SAT model: exhibit an explicit constant $r_0 < 4.268$ and prove that a random 3-CNF formula on $n$ variables with $m \ge r_0 n$ clauses is unsatisfiable whp. The object of this component is the improved bound itself, so an assessment of what any particular method can or cannot achieve does not by itself constitute an advance here.

Components (1) and (2) measure the same overarching objective — the rigorous location of $r_3$ within narrowing bounds, culminating in existence plus exact location. Any sound advance on either component constitutes progress on the problem; full completion of component (1) for $k = 3$ would settle the famous satisfiability conjecture in its central case, and should not be conflated with the known large-$k$ theorem of Ding–Sly–Sun.

References

1. Hera Antonopoulou, 'Kolmogorov complexity based upper bounds for the unsatisfiability threshold of random k-SAT', Journal of Discrete Mathematical Sciences and Cryptography 23(7):1431–1438, 2020. DOI: 10.1080/09720529.2020.1711602, https://doi.org/10.1080/09720529.2020.1711602 (source of the open problem)
2. Ehud Friedgut (appendix by Jean Bourgain), 'Sharp thresholds of graph properties, and the k-sat problem', Journal of the American Mathematical Society 12(4):1017–1054, 1999. DOI: 10.1090/S0894-0347-99-00305-7, https://doi.org/10.1090/S0894-0347-99-00305-7
3. Olivier Dubois, Yacine Boufkhad, Jacques Mandler, 'Typical random 3-SAT formulae and the satisfiability threshold', 2002. arXiv:cs/0211036, https://arxiv.org/abs/cs/0211036 (earlier version in Proc. 11th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2000, pp. 126–127)
4. Josep Díaz, Lefteris M. Kirousis, Dieter Mitsche, Xavier Pérez-Giménez, 'On the satisfiability threshold of formulas with three literals per clause', Theoretical Computer Science 410(30):2920–2934, 2009. DOI: 10.1016/j.tcs.2009.02.020, https://doi.org/10.1016/j.tcs.2009.02.020 (preprint: 'A new upper bound for 3-SAT', arXiv:0807.3600, https://arxiv.org/abs/0807.3600)
5. MohammadTaghi Hajiaghayi, Gregory B. Sorkin, 'The Satisfiability Threshold of Random 3-SAT Is at Least 3.52', 2003. arXiv:math/0310193, https://arxiv.org/abs/math/0310193
6. Don Coppersmith, David Gamarnik, MohammadTaghi Hajiaghayi, Gregory B. Sorkin, 'Random Max SAT, Random Max Cut, and their phase transitions', Random Structures & Algorithms 24(4):502–545, 2004. DOI: 10.1002/rsa.20015, https://doi.org/10.1002/rsa.20015
7. Alexis C. Kaporis, Lefteris M. Kirousis, Efthimios G. Lalas, 'The probabilistic analysis of a greedy satisfiability algorithm', Random Structures & Algorithms 28(4):444–480, 2006. DOI: 10.1002/rsa.20104, https://doi.org/10.1002/rsa.20104
8. Jian Ding, Allan Sly, Nike Sun, 'Proof of the satisfiability conjecture for large k', Annals of Mathematics 196(1):1–388, 2022. DOI: 10.4007/annals.2022.196.1.1, https://doi.org/10.4007/annals.2022.196.1.1 (preprint arXiv:1411.0650, 2014)
9. Will Perkins, 'Searching for (sharp) thresholds in random structures: Where are we now?', Bulletin of the American Mathematical Society 62(1):113–143, 2025 (published online October 2024). DOI: 10.1090/bull/1857, https://doi.org/10.1090/bull/1857 (updated version arXiv:2401.01800, https://arxiv.org/abs/2401.01800, v2 August 2024)
10. Marc Mézard, Giorgio Parisi, Riccardo Zecchina, 'Analytic and Algorithmic Solution of Random Satisfiability Problems', Science 297(5582):812–815, 2002. DOI: 10.1126/science.1073287, https://doi.org/10.1126/science.1073287
11. Marc Mézard, Riccardo Zecchina, 'Random K-satisfiability problem: From an analytic solution to an efficient algorithm', Physical Review E 66:056126, 2002. DOI: 10.1103/PhysRevE.66.056126, https://doi.org/10.1103/PhysRevE.66.056126
12. Yacine Boufkhad, Thomas Hugel, 'Non Uniform Selection of Solutions for Upper Bounding the 3-SAT Threshold', 2010. arXiv:1002.1636, https://arxiv.org/abs/1002.1636 (also in Proc. SAT 2010, Lecture Notes in Computer Science, DOI: 10.1007/978-3-642-14186-7_10)
13. Jochen Messner, Thomas Thierauf, 'A Kolmogorov complexity proof of the Lovász Local Lemma for satisfiability', Theoretical Computer Science 461:55–64, 2012. DOI: 10.1016/j.tcs.2012.06.005, https://doi.org/10.1016/j.tcs.2012.06.005
14. Ioannis Caragiannis, Nick Gravin, Zhile Jiang, 'On the satisfiability of random 3-SAT formulas with k-wise independent clauses', 2024. arXiv:2411.03813, https://arxiv.org/abs/2411.03813
15. Zongchen Chen, Aditya Lonkar, Chunyang Wang, Kuan Yang, Yitong Yin, 'Counting random k-SAT near the satisfiability threshold', 2024. arXiv:2411.02980, https://arxiv.org/abs/2411.02980 (STOC 2025)
16. Fedor Vorobyev, 'An upper bound of 4.268 for the random 3-SAT satisfiability threshold', 2026. arXiv:2610.10599, https://arxiv.org/abs/2610.10599 (proof formalized in Lean 4)