结果族 235：Limiting random SAT thresholds, sharp variance and computability · 学科：Probability and statistical mechanics · 验证状态：暂无形式化证明，请以社区核验为准
想象一台抽奖机不停吐出”三选一”的逻辑谜题，每题都能判对错——题少时你总能全部答对，题多到某个密度后就必然顾此失彼。这篇论文研究这条”从能对到必错”的分界线：它不仅存在，而且是一台普通计算机就能逐位算出的数。
关键词卡片
看个具体例子
代入数字：1000 个变量的卷子，平均每变量摊 3 道子句时几乎必可满足，摊 5 道时几乎必无解；分界点 @@M@@\alpha_3@@ 被严格夹在 3.52 与 4.4898 之间（物理方法预言约 4.267）。主定理保证：一台程序收到精度 @@M@@10^{-3}@@ 的请求就停机，输出 @@M@@\alpha_3\pm 0.001@@；收到 @@M@@2^{-r}@@ 就精确到 @@M@@2^{-r}@@。
为什么值得关心
“存在”不等于”可算”（收敛序列可以收敛到不可计算的数），而本文跨过了这道沟：这个著名的相变点是可以被逐位确定的数学对象。
暂无形式化证明（AI 结果待核验）
第一级台阶
入门导读里那台”不停吐卷子的抽奖机”，翻译过来就是：对象是一份随机生成的判断题卷子，每道题圈住三个变量、随机定下”至少一个取值要对”的要求；我们做的唯一操作是问”整份卷子能否全部答对”。可调的旋钮只有一个——题量与变量数之比，也就是卷子的拥挤程度；”从能对到必错”的那道分界线，就是这个旋钮上的一个刻度。
第二级台阶
用本科概率论的语言精确化：随机 3-SAT 公式 @@M@@\Phi(n,m)@@ 由 @@M@@m@@ 条独立子句组成，每条从 @@M@@n@@ 个变量中均匀抽取三个不同变量并给每个变量独立公平地定号；可满足概率 @@M@@p(n,m)@@ 是该公式存在成真赋值的概率，比值 @@M@@m/n@@ 称为子句密度。可计算实数指：存在一台确定性图灵机，对任意输入精度 @@M@@1^r@@ 都停机并输出误差不超过 @@M@@2^{-r}@@ 的有理数——不需要任何神谕或外来常数。
第三级台阶
定理在这样的语境下陈述：Carenini（2026）已确立极限阈值 @@M@@\alpha_3@@ 的存在——密度低于它时 @@M@@p(n,\lfloor an\rfloor)\to1@@，高于它时趋于 @@M@@0@@——本文补上”可算”这一层。必须补的原因是 Specker 的反例：可计算的单调有理序列可以收敛到不可计算的数，故”是极限”推不出”能逼近”。论文的对策是双侧证书：删除估计给出 @@M@@f_n/n@@ 型的显式下界序列作为下证书，软压强的有限层次逼近在每个大于 @@M@@\alpha_3@@ 的有理密度处提供负值见证作为上证书；机器公平搜索两族证书，以证书区间本身作停机判据，从而完全绕开对有限尺寸收敛速率的需求。
证明了均匀随机 3-SAT 的极限可满足性阈值（satisfiability threshold）@@M@@\alpha_3@@ 存在，且是可计算实数（computable real）：一台不用神谕、不带任何不可计算常数的确定性图灵机就能把它算到任意指定精度。
随机 3-SAT 在 @@M@@n@@ 个变量中均匀选三个不同变量、独立公平地定号，抽 @@M@@m@@ 条独立子句，@@M@@m/n@@ 称为子句密度（clause density）。Mitchell–Selman–Levesque 1992 年的实验发现求解难度在”一半公式可满足”的密度附近激增，由此产生阈值猜想：存在临界密度，低于它公式渐近可满足，高于它渐近不可满足。Friedgut（1999，附 Bourgain 附录）证明了每个固定 @@M@@k\ge3@@ 都有陡峭相变（sharp transition），但相变中心可以随系统尺寸漂移，推不出极限存在。数值上，3.52（Kaporis–Kirousis–Lalas 2006）与 4.4898（Díaz 等 2009）从两侧夹住阈值，统计物理的空腔方法（cavity method）预言约 4.267；Ding–Sly–Sun（2022）对所有充分大的 @@M@@k@@ 证明了含数值的猜想，@@M@@k=3@@ 一直悬置。2026 年 10 月，Carenini 以 @@M@@O_{k,\eta}(n^{1/2+1/k})@@ 的多项式窗口对每个固定 @@M@@k\ge3@@ 确立了极限阈值的存在，论文明确把优先权归于她。本文处理下一步：即便极限存在，Specker（1949）早已构造出收敛到不可计算实数的可计算单调有理序列，所以”存在”并不自动等于”可算”。
主定理分两层。第一，存在 @@M@@\alpha_3\in(0,\infty)@@，使对每个固定实数 @@M@@a\ge0@@，可满足概率 @@M@@p(n,\lfloor an\rfloor)@@ 在 @@M@@a<\alpha_3@@ 时趋于 1、在 @@M@@a>\alpha_3@@ 时趋于 0。第二，存在一台有限确定性图灵机，输入一元精度 @@M@@1^r@@ 即停机并输出有理数 @@M@@q_r@@，满足 @@M@@|q_r-\alpha_3|\le2^{-r}@@；机器不使用神谕（oracle）、建议（advice）或任何不可计算实常数。论文同时划清边界：@@M@@a=\alpha_3@@ 处的行为未知，不给运行效率界，也不断言 @@M@@\alpha_3@@ 等于 4.267 的物理预言。
先把任务抽象成”证书搜索引理”：设有可计算有理序列 @@M@@\ell_k\to\alpha@@ 自下方逼近，另有一致可计算的测试值 @@M@@G(a,\beta;Q)@@，@@M@@Q@@ 取自可有效枚举的有限描述，满足两条符号条件——@@M@@G<0@@ 蕴含 @@M@@\alpha\le a@@，且每个有理 @@M@@a>\alpha@@ 都存在负值测试。对全部三元组 @@M@@(a,\beta,Q)@@ 做鸽笼式公平搜索，每阶段多执行若干步，随时用下证书抬高区间左端、用负值测试压低右端，区间长度一旦不超过 @@M@@2^{1-r}@@ 就输出中点。停机论证只用到”两族证书终会被找到”，完全不需要有限尺寸收敛的速率——这正是绕开 Specker 障碍的关键。
概率侧先在松弛泊松模型（relaxed Poisson model，三个变量下标独立取样、允许重复）中计算，最后经细化（thinning）与泊松计数比较转移回原模型。令 @@M@@T_0@@ 为首个不可满足时刻，@@M@@f_n=\E\min\{T_0,20n\}@@。核心是免费删除矩界：免费删去变量 @@M@@v@@ 换来的存活增量满足 @@M@@\E[(F_r^{+v}-F_r)^{6/5}]\le2^{60}@@，且对删除额度 @@M@@r@@ 一致。证明沿用 Friedgut 半立方引理与 Carenini 顺序替换的残余集条件化（residual-set conditioning）思想：固定不含 @@M@@v@@ 的基底子句流后，含 @@M@@v@@ 的子句投影成两文字测试，而 @@M@@d@@ 个三文字测试替换一个两文字测试时”全部歼灭”的概率至多损失 @@M@@1/d^2@@；再按残余集被消灭的概率二进分箱，未来基底流以几何速度歼灭各箱残余，逐箱积分后级数收敛，关键幂为 @@M@@2-3p/2=1/5>0@@。随后按子句最小变量指标分桶、用 Doob 鞅得集中不等式，又以加权插值比较”两块独立公式”与”合并公式”的可满足概率——两种子句的消灭概率 @@M@@\sum\lambda_ix_i^3@@ 与 @@M@@(\sum\lambda_ix_i)^3@@ 由 @@M@@x^3@@ 的凸性分出高下，再用品格函数展开把变量权重抹匀——得到次可乘不等式，进而 @@M@@f_n@@ 近似超可加，误差 @@M@@O(n^{5/6})@@，故 @@M@@f_n/n@@ 收敛于 @@M@@\alpha@@ 且带单侧证书 @@M@@\alpha\ge f_n/n-2^{67}n^{-1/6}@@；而 @@M@@f_n@@ 可一致计算——枚举全部子句列表与赋值、截断泊松尾即可——这就给出下证书序列。删除矩界另有一功：它保证超过 @@M@@\alpha@@ 后、以趋于 1 的概率任何赋值都违反多于 @@M@@\epsilon n@@ 条子句，于是软压强（soft pressure）@@M@@P(a,\beta)=\lim n^{-1}\E\log Z_n@@（其中 @@M@@Z_n=\sum_\sigma e^{-\beta H_n(\sigma)}@@）在某个整数惩罚 @@M@@\beta@@ 下严格为负。上证书由一族有限有理试验（trial）描述 @@M@@Q@@ 提供：插值方向留下非负余项 @@M@@(x-y)^2(x+2y)@@，给出 @@M@@P\le G@@；反向恒等式 @@M@@P=\inf_QG@@ 则借助 Ghirlanda–Guerra 恒等式的高斯探测、Panchenko 超度量（ultrametricity）定理与 Austin–Panchenko 层次表示，把不同位点共享的随机变量逐层剥离为独立采样，最后用有理数表离散化。组装两族证书即得定理；证明中取子序列、选条件律等非有效步骤只用于保证有限见证存在，机器本身只搜索有限描述。
本文主结果暂无形式化证明，OpenAI 官方声明未经形式化的结果可能有问题，请以社区核验为准。作为结果族 235 的可计算性成员，它与姊妹篇互为支撑：族内另一篇独立证明每个固定 @@M@@k\ge3@@ 的极限阈值存在并给出命中时方差（hitting-time variance）@@M@@\Theta_k(n)@@ 的尖锐估计，与本文共享删除矩界与压强符号机制；本文还证明所构造的 @@M@@\alpha@@ 与姊妹篇的 @@M@@k=3@@ 常数一致。Carenini 的优先权（ECCC TR26-229，2026 年 10 月 5 日公开）在摘要与引言中均被明确致谢。
问 1：Carenini 已经证明阈值存在，这篇论文还有多少剩余价值？
| （答：存在不等于可算。Specker（1949）构造过收敛到不可计算实数的可计算单调有理序列，所以”α₃ 是某个极限”并不自动给出逼近算法。本文定理 1.1 的增量正在于此：一台无神谕、无建议的有限确定性图灵机，输入一元精度 1^r 即停机并输出 | q_r−α₃ | ≤2^{-r} 的有理数。） |
问 2：证明中最脆弱、最值得审稿人逐行核对的是哪一步？
（答：上证书一侧的反向恒等式 P=inf_Q G。它要证明软压强的有限层次逼近确实能够逼近到压强本身，链条上借用了 Ghirlanda–Guerra 恒等式、Panchenko 超度量定理与 Austin–Panchenko 层次表示来逐层剥离共享随机变量，再以有理数表离散化。这是全文引用外部深定理最密集、组装最复杂的一环。）
问 3：公平搜索凭什么不需要有限尺寸收敛的速率？
（答：停机判据不是”估计达到精度”，而是”证书区间长度不超过 2^{1-r} 时输出中点”。鸽笼式搜索保证每个三元组 (a,β,Q) 终被穷尽；下证书序列趋近 α₃、每个有理 a>α₃ 处存在负值测试，这两条合起来保证区间必然收缩到停机，全程不出现收敛模。这是绕开 Specker 障碍的关键设计。）
问 4：哪个假设动不得？
（答：子句尺寸 k=3。引言明确承认计算性论证只针对 k=3；概率侧免费删除矩界 E[(F^{+v}−F)^{6/5}]≤2^{60} 与残余集分箱积分中的关键幂 2−3p/2=1/5>0 恰在 k=3 为正，换到更大的 k 这套常数与箱结构未必照搬得动。论文也不给运行效率界、不处理 a=α₃ 处的行为。）
问 5：与 Ding–Sly–Sun（2022）和 Bayati–Gamarnik–Tetali（2013）相比，真正的新意是什么？
（答：DSS 证明的是充分大 k 的阈值猜想并定出数值，k=3 不在其范围；BGT 的稀疏插值只处理”近可满足”（允许 o(n) 条违反子句），精确可满足不满足其框架。本文的新意是可计算性本身，以及删除估计＋软压强符号这套双侧证书机制。）
问 6：作为 AI 生成的证明，它最可能以什么方式出错？
（答：典型风险有二。一是”取子序列、选条件律”等非有效步骤与”机器只搜有限描述”之间的分工——若某个有限见证实际携带了非可计算信息，整个可计算性结论就崩塌；二是加权插值比较中 x^3 凸性给出次可乘不等式、误差 O(n^{5/6}) 的常数口径，一旦出错下证书 f_n/n−2^{67}n^{-1/6} 便不再合法。）
问 7：谁会真的用到这个结果？
（答：短期不是 SAT 求解器实践者——机器不搜满足赋值、无效率界、也不验证 4.267 的物理预言。受益方是随机约束满足与自旋玻璃可计算性纲领的研究者：把空腔方法式的层次结构转化为有限可验证证书的机制，可望移植到其他稀疏随机系统的相变常数上。）
总评
把”著名相变常数逐位可算”从哲学疑虑变成定理，概念增益实在；最大风险在上证书一环堆叠了一长串高深外部结果，且全文尚无形式化核验。