Limiting random SAT thresholds, sharp variance and computability

The explanation

Take three yes/no switches, x1, x2 and x3. A clause is a rule such as: x1 is on, or x2 is off, or x3 is on. It fails for exactly one of the 8 settings of the three switches. A formula is a list of such clauses, and it is satisfiable if some setting obeys all of themSource 1.

Now build a formula at random. Take n switches. Each new clause picks three different switches at random and flips a fair coin for each sign. Keep adding clauses. Early on, a setting that obeys everything almost surely exists. Later, almost surely none does. This is random 3-SAT, and the same game with k switches per clause is random k-SAT.

A quick count shows where the change must happen by. One clause rules out a fixed setting with chance 1/8Source 2. So after m clauses, the expected number of good settings is 2^n × (7/8)^m. With m = c × n clauses, this shrinks to zero once c is above log 2 / log(8/7), about 5.19. The number c is called the clause density.

For 3-SAT, earlier work showed the change happens between densities 3.52 and 4.4898Source 3. Physicists predict it near 4.267Source 4. In 1992, Chvátal and Reed conjectured that the change happens at one fixed density as n growsSource 5. Friedgut proved in 1999, with an appendix by Bourgain, that the change is sharp, but around a density that might still drift with nSource 6. That drift was the obstacleSource 7. Ding, Sly and Sun settled the question for all large enough kSource 8.

The first paper proves that for every k ≥ 3 the change happens at a single limiting densitySource 9. Below it, formulas are satisfiable with probability tending to one. Above it, the probability tends to zero. It says nothing about the density exactly at the thresholdSource 10. Gaia Carenini resolved this conjecture first, in work made public on 5 October 2026. The paper credits her with priority and gives a different proofSource 11,Source 12.

The proof has two halves. A switch is called forced when every good setting gives it the same valueSource 13. The paper bounds how many switches are forced along the way. That shows the stopping point barely wobbles around its average. But a steady average can still drift as n growsSource 14. So the paper compares a large system with two independent smaller onesSource 15. It shows the drift must die out.

A second paper studies that wobble directly. Add clauses one at a time and stop at the first unsatisfiable formula. For k ≥ 4, it proves that the variance of the stopping time grows like nSource 16. Variance measures the typical squared distance from the average. For k = 3 it proves a bound of order n log n. A third paper, from 5 October 2026, claims to remove that log factor for k = 3Source 17. Variance of order n means the typical wobble is a fixed multiple of √n. With 10,000 switches, √n is 100, against about 42,670 clauses at density 4.267.

A fourth paper proves that the 3-SAT threshold is computableSource 18. One fixed program can output it to any accuracy you ask forSource 19. The program checks certificates from below and from above until they are close enoughSource 20. It does not compute the actual value, or confirm the 4.267 predictionSource 21. It also gives no bound on how long the program runsSource 22.

How sure is this? Lean, a computer proof checker, has formal versions of three results. They are the threshold for every k ≥ 3, and the variance bounds. They also cover computability of the 3-SAT threshold. For k = 3, Lean has the n log n upper bound, not the sharper bound of the October paper. No specialist review of these papers has been published.

What it doesn't show. This does not give the numerical value of the 3-SAT threshold.