The asymptotic k-SAT threshold

Since the early 2000s physicists have developed an ingenious but non-rigorous formalism called the cavity method to put forward precise conjectures on phase transitions in random problems (Mézard et al., 2002 [37]). The cavity method predicts that the satisfiability threshold in the random k-SAT problem is rk-SAT=2kln⁡2−12(1+ln⁡2)+εk, with limk→∞⁡εk=0 (Mertens et al., 2006 [35]). This paper contains a proof of the conjecture.