probability-statistics / Random constraint satisfaction; random k-SAT phase transition

The satisfiability threshold conjecture: a limiting random k-SAT threshold for every k >= 3

Claims Theorem 1.1: for every fixed k≥3k\ge3 there is αk∈(0,∞)\alpha_k\in(0,\infty) with Pr⁡(Fn,⌊cn⌋∈SAT)→1\Pr(F_{n,\lfloor cn\rfloor}\in\mathrm{SAT})\to1 for c<αkc<\alpha_k and →0\to0 for c>αkc>\alpha_k; it says nothing at c=αkc=\alpha_k and does not identify αk\alpha_k for small kk. Companions claim hitting-time variance Θk(n)\Theta_k(n) for k≥4k\ge4 and Θ(n)\Theta(n) for k=3k=3, and that α3\alpha_3 is a computable real. Priority: the release credits Gaia Carenini's ECCC TR26-229 (made public 5 October 2026) with first resolving the existence conjecture; this is an independent second proof of the same result, not a contradiction. Carenini's paper states that none of its mathematical arguments was generated by a large language model; it proves the existence via a scaling window of width O(n1/2+1/k)O(n^{1/2+1/k}) and the Abbe-Montanari criterion.

42Significance / 100
1Frontier events
0Verification tasks
0Recorded attempts

Temporal state

Current frontier

No reconciled state yet.

Append-only history

Frontier timeline

probability-statisticsSep 25, 2026Significance 42/100Registry: lean checked

The satisfiability threshold conjecture: a limiting random k-SAT threshold for every k >= 3

Prior state unknown→proved

Claims Theorem 1.1: for every fixed k≥3k\ge3 there is αk∈(0,∞)\alpha_k\in(0,\infty) with Pr⁡(Fn,⌊cn⌋∈SAT)→1\Pr(F_{n,\lfloor cn\rfloor}\in\mathrm{SAT})\to1 for c<αkc<\alpha_k and →0\to0 for c>αkc>\alpha_k; it says nothing at c=αkc=\alpha_k and does not identify αk\alpha_k for small kk. Companions claim hitting-time variance Θk(n)\Theta_k(n) for k≥4k\ge4 and Θ(n)\Theta(n) for k=3k=3, and that α3\alpha_3 is a computable real. Priority: the release credi…

SourceReplayReproducedFormal proofStatement auditExternal checkExpert reviewPeer review

Research memory

Claims and attempts

Scoped claims

Source authenticated

Claims Theorem 1.1: for every fixed k≥3k\ge3 there is αk∈(0,∞)\alpha_k\in(0,\infty) with Pr⁡(Fn,⌊cn⌋∈SAT)→1\Pr(F_{n,\lfloor cn\rfloor}\in\mathrm{SAT})\to1 for c<αkc<\alpha_k and →0\to0 for c>αkc>\alpha_k; it says nothing at c=αkc=\alpha_k and does not identify αk\alpha_k for small kk. Companions claim hitting-time variance Θk(n)\Theta_k(n) for k≥4k\ge4 and Θ(n)\Theta(n) for k=3k=3, and that α3\alpha_3 is a computable real. Priority: the release credits Gaia Carenini's ECCC TR26-229 (made public 5 October 2026) with first resolving the existence conjecture; this is an independent second proof of the same result, not a contradiction. Carenini's paper states that none of its mathematical arguments was generated by a large language model; it proves the existence via a scaling window of width O(n1/2+1/k)O(n^{1/2+1/k}) and the Abbe-Montanari criterion.

Claims Theorem 1.1: for every fixed k≥3k\ge3 there is αk∈(0,∞)\alpha_k\in(0,\infty) with Pr⁡(Fn,⌊cn⌋∈SAT)→1\Pr(F_{n,\lfloor cn\rfloor}\in\mathrm{SAT})\to1 for c<αkc<\alpha_k and →0\to0 for c>αkc>\alpha_k; it says nothing at c=αkc=\alpha_k and does not identify αk\alpha_k for small kk. Companions claim hitting-time variance Θk(n)\Theta_k(n) for k≥4k\ge4 and Θ(n)\Theta(n) for k=3k=3, and that α3\alpha_3 is a computable real. Priority: the release credits Gaia Carenini's ECCC TR26-229 (made public 5 October 2026) with first resolving the existence conjecture; this is an independent second proof of the same result, not a contradiction. Carenini's paper states that none of its mathematical arguments was generated by a large language model; it proves the existence via a scaling window of width O(n1/2+1/k)O(n^{1/2+1/k}) and the Abbe-Montanari criterion.

Recorded attempts

Evidence graph

Connected research record