结果族 235：Limiting random SAT thresholds, sharp variance and computability · 学科：Probability and statistical mechanics · 验证状态：暂无形式化证明，请以社区核验为准
往一台机器里一条条塞随机”要求”（子句），起初它总能全部满足；塞到某个密度，机器突然全面崩溃。三十多年前数学家猜测：崩溃点会收敛到一个固定密度 α_k。本文证明这个”可满足性猜想”对每个 k ≥ 3 都成立——猜想的优先权属 Carenini 的并发工作，本文给出一条技术路线独立的证明。
关键词卡片
看个具体例子
k = 2 时早已知道 @@M@@\alpha_2=1@@。对 k ≥ 3，定理保证 @@M@@\alpha_k@@ 存在且落在 @@M@@[a_0,\,2^k+1]@@：例如 k = 3 时 @@M@@\alpha_3\in(0,9)@@——注意定理只承诺”存在”，不告诉你具体数值。证明骨架是”先集中、再锚定、最后排除漂移”：先证截断命中时间的方差只有 @@M@@O_k(n^{1+2/k})@@，把转移窗口压窄；再用匹配论证把中心锚定在正区间内；最后用近似超可加性排除中心随 n 漂移的可能。论文还附赠单侧逼近速率 @@M@@\mu_s\le\alpha_k+C_k s^{-\delta_k}@@，其中 @@M@@\delta_k=\dfrac{k-2}{4k}@@（k = 3 时为 1/12）。
为什么值得关心
可满足性猜想是随机约束满足领域的中心问题；本文的集中性估计比并发结果更锋利，直接被族内另两篇方差论文拿来使用。
暂无形式化证明（AI 结果待核验）
衔接《解读 A Limiting Satisfiability Threshold for Every Fixed Clause Size》入门导读
第一级台阶
导读的图景是”往机器里一条条塞随机要求，塞到某个密度突然崩溃”。半数学地说：对象是一个随机增长过程——在给定的变量池上，一条接一条独立地生成随机要求，每条要求挑固定个数个不同变量、各自随机地取正反；要跟踪的量是”到第 m 条为止的全部要求仍能被同时满足”的概率，它随 m 单调下降。问题是：崩溃发生的位置换算成”每变量摊到的要求条数”后，是否会随变量数增长而稳定到一个固定数。
第二级台阶
三个概念精确化。随机 k-SAT：每条子句从 n 个变量中均匀选 k 个互异变量、符号独立公平，整条子句有放回抽样；子句密度定义为条数与变量数之比。阈值与尖锐阈值：使可满足概率从接近一跌到接近零的临界密度；尖锐阈值定理只保证转移发生在宽度次线性的窗口内、给出一列可能随 n 漂移的临界位置，不保证收敛。集中性：关键随机量围绕其期望的波动大小的控制，通常以方差界的形式出现，是把”窗口窄”升级为”位置不漂移”的前提。
第三级台阶
定理的语境是每个固定的子句长度 k 至少为三；k=2 的阈值为一是早已另案解决的经典结果，一长子句在线性尺度下平凡，故被排除在定理之外。结论是：存在有限的正常数 α_k，使得当密度严格小于它时前若干条子句的合取以趋于一的概率可满足、严格大于它时以趋于零的概率不可满足；在密度恰等于 α_k 处定理不作断言，α_k 的具体数值也未被识别。证明的支柱有二：先证截断后的”最后可满足下标”有次线性波动，把每个有限尺寸的中心钉住；再用不同尺寸系统之间的近似超可加比较排除中心随尺寸漂移。需注意：可满足性猜想的解决优先权属 Carenini 的并发工作，本文是一条技术路线独立的另一证明。
证明了固定 @@M@@k\ge3@@ 的随机 @@M@@k@@-SAT 存在有限的极限阈值密度 @@M@@\alpha_k@@：子句密度低于它时公式渐近可满足，高于它时渐近不可满足。这一三十余年悬置的可满足性猜想的解决优先权属 Carenini，本文给出一条技术路线独立的完整证明。
往 @@M@@n@@ 个布尔变量上逐条加入随机子句（clause），问可满足概率何时从接近 @@M@@1@@ 跌到接近 @@M@@0@@。Friedgut（附 Bourgain 附录）的尖锐阈值定理早已表明转移在 @@M@@o(n)@@ 窗口内完成，但只给出一列随 @@M@@n@@ 变化的临界密度；这列位置是否收敛到单一极限 @@M@@\alpha_k@@，是 Chv'atal 与 Reed 明确提出的著名猜想。@@M@@k=2@@ 已知 @@M@@\alpha_2=1@@（Chv'atal–Reed、Goerdt 独立证明）；@@M@@k@@ 充分大时 Ding–Sly–Sun 证明阈值存在且等于统计物理的 1RSB 预测；而所有固定的中等 @@M@@k@@ 始终留有缺口。Gaia Carenini 于 2026 年 10 月 5 日公开的 ECCC 报告率先解决该猜想，作者在文中明确把优先权归于她；本文的价值在于给出一条不同的证明，且其集中性估计比并发结果更便于族内其他论文使用。
考虑 proper @@M@@k@@-clause 模型：每条子句在 @@M@@n@@ 个变量中均匀选取 @@M@@k@@ 个互异变量，文字符号独立公平，整条子句有放回抽样；记 @@M@@P_n(m)@@ 为前 @@M@@m@@ 条子句的合取可满足的概率。主定理：对每个固定整数 @@M@@k\ge3@@，存在 @@M@@\alpha_k\in(0,\infty)@@，使得 @@M@@\lim_{n\to\infty}P_n(\lfloor cn\rfloor)=1@@（当 @@M@@0\le c<\alpha_k@@）、@@M@@=0@@（当 @@M@@c>\alpha_k@@）。定理不断言 @@M@@c=\alpha_k@@ 处的概率值，也不识别 @@M@@\alpha_k@@ 的大小；文中另说明 @@M@@k=2@@ 时 @@M@@\alpha_2=1@@、@@M@@k=1@@ 时线性尺度上阈值为 @@M@@0@@，与之分开。证明还附赠单侧有限尺寸信息：@@M@@\mu_s\le\alpha_k+C_ks^{-\delta_k}@@。
骨架是”先集中、再锚定、最后排除漂移”。设 @@M@@H_n@@ 为首个不可满足前缀的下标，截断 @@M@@V_n=\min(H_n-1,2^{k+1}n)@@，取中心 @@M@@\mu_n=\mathbb E V_n/n@@。第一步控制强制变量（forced，即可满足指派都给它同一值的变量）：删除含 @@M@@x_n@@ 的子句并抹去其文字，得到 @@M@@(k-1)@@-子句；替换引理证明一条 @@M@@(k-1)@@-子句的杀伤力可用 @@M@@g=O_k(n^{1/k})@@ 条普通 @@M@@k@@-子句以误差 @@M@@\varepsilon=n^{-(k-1)/k}@@ 模拟，且对任意背景公式一致成立，核心是 @@M@@q_k\ge x^{k/(k-1)}/k@@ 的幂次比较。再对前缀长度做望远镜求和，得积分型估计 @@M@@\sum_j\mathbb E\,b(F_{n,j})/n=O_k(n^{1/k})@@。第二步做集中性：删去第 @@M@@i@@ 条子句而保留其余时间指标，延迟平方按 pivotal 对展开；”后一个 pivotal 时刻仍存活”要求中间每条子句都避开杀伤当前解集，给出几何衰减 @@M@@(1-q_m)^{\ell-m}@@；用 @@M@@\min\{Mq,1\}\le(Mq)^{1/k}@@ 取 @@M@@k@@ 次根接回强制比例，代入 Efron–Stein 型方差不等式得 @@M@@\operatorname{Var}(V_n)=O_k(n^{1+2/k})@@，Chebyshev 不等式给出次线性窗口 @@M@@n^{1-\delta_k}@@，其中 @@M@@\delta_k=(k-2)/(4k)@@。第三步锚定中心：低密度用 Hall 定理把子句匹配到互异变量给下界 @@M@@a_0>0@@，高密度用指派一阶矩给上界 @@M@@2^k+1@@。最后排除中心漂移：在允许变量重复的辅助 Poisson 模型中对两族子句均值做插值求导（Bayati–Gamarnik–Tetali 冻结变量方法的 Poisson 形式），导数符号由 @@M@@z\mapsto z^k@@ 的凸性决定，得乘积不等式 @@M@@s_{r+s}(c)\ge s_r(c)s_s(c)@@；经 Poisson 细化与 proper 模型互相转移（重复子句的期望数有界）后，低侧转移界是固定正概率而高侧趋零，二者比较化为近似超可加不等式 @@M@@x_{r+s}\ge\min\{x_r,x_s\}-4\min\{r,s\}^{-\delta}@@；最后沿平衡二叉树自叶向根累加几何衰减的误差（Abbe–Montanari 论证的确定性形式），得 @@M@@\mu_n@@ 收敛于某 @@M@@\alpha_k\in[a_0,2^k+1]@@，再由集中性把概率极限推到两侧密度。
本文主结果暂无形式化证明，OpenAI 官方声明未经形式化的结果可能有问题，请以社区核验为准。族内姊妹篇互相支撑：本文的截断方差界与集中性技术同方差姊妹篇共享删除–pivotal 框架，而方差姊妹篇（@@M@@k\ge4@@ 时 @@M@@\Theta_k(n)@@、3-SAT 时 @@M@@\Theta(n)@@）把本文的涨落估计磨到最优；反过来本文给出的极限位置 @@M@@\alpha_k@@ 为她们提供了中心的语言。需注意证明只给单侧逼近率 @@M@@\mu_s\le\alpha_k+C_ks^{-\delta_k}@@，没有逼近 @@M@@\alpha_k@@ 的有效双侧速度；猜想的解决优先权属 Carenini 的并发工作。
针对《A Limiting Satisfiability Threshold for Every Fixed Clause Size》，基于论文原文（定理 1.1、引言 §1.1–1.2 及各节证明概述）
问 1：证明中最关键、最脆弱的一步是什么？
（答：截断命中时间的方差界 Var(V_n)=O_k(n^{1+2/k})。手法是删去单条子句而保留其余时间指标，延迟的平方按 pivotal 对展开——”后一个 pivotal 时刻仍存活”要求中间每条子句都避开杀伤当前解集，给几何衰减 (1−q_m)^{ℓ−m}；再用 min{Mq,1}≤(Mq)^{1/k} 取 k 次根接回强制变量比例，代入 Efron–Stein 型不等式（引言 §1.2）。没有这个次线性窗口，后续一切”中心比较”都无从谈起；若几何衰减或幂次嫁接处常数有误，整个收敛论证断裂。）
问 2：替换引理为什么必须对任意背景公式一致成立？
（答：因为强制变量的论证要”边走边用”：删除含某变量的子句并抹去其文字得到 (k−1)-子句，其杀伤力须能用 g=O_k(n^{1/k}) 条普通 k-子句以误差 n^{-(k-1)/k} 模拟，且对任意背景公式一致——背景在望远镜求和中是随机的、不可枚举的。一致性的核心是幂次比较 q_k≥x^{k/(k-1)}/k；这是 Friedgut 半立方替换的定量后代，也是全文技术密度最高的引理之一。）
问 3：k=2 为什么不进定理？
（答：k=2 的阈值 α₂=1 由 Chv´atal–Reed（及 Goerdt 等独立）经蕴涵图机制解决，与本文的强制—删除—插值路线完全不同；k=1 在线性尺度下阈值为零。定理只处理 k≥3，这不是疏漏而是路线适配——蕴涵图的机制不推广到一般 k，本文的机制在 k=2 上也无必要。）
问 4：与已有工作相比，这篇的位置是什么？
（答：Friedgut 只给尖锐窗口、位置可能漂移；Ding–Sly–Sun 对充分大的 k 证了存在性且识别了数值（1RSB 预言）；Coja-Oghlan–Panagiotou 是 k→∞ 的渐近；中间的所有固定 k 是缺口。Carenini 的并发工作以 O(n^{1/2+1/k}) 窗口加 Abbe–Montanari 判据率先解决猜想、拥有优先权；本文是独立路线的第二证明，不断言 α_k 的值，但集中性估计更便于族内方差论文使用。）
问 5：AI 生成证明最可能出错的模式？
（答：插值不等式的符号。在允许变量重复的辅助 Poisson 模型中对两族子句均值插值求导（Bayati–Gamarnik–Tetali 冻结变量方法的连续参数形式），导数符号由 x↦x^k 的凸性决定，得乘积不等式 s_{r+s}(c)≥s_r(c)s_s(c)——凸性用错方向或用在错误的量（全局强制变量的比例）上，是最典型的隐性错误。其次是”只在两尺寸可比时比较”的近似超可加引理（min{r,s}^{-δ} 误差沿平衡二叉树累加），本文自证其确定性形式，非标准变体的边界条件值得逐行核。）
问 6：定理留下了什么没说？
（答：c=α_k 处的概率值无断言；α_k 无任何数值识别（只知落在 [a₀, 2^k+1]）；有限尺寸信息只有单侧率 μ_s≤α_k+C_k s^{-δ_k}（δ_k=(k−2)/(4k)），无双侧逼近速度。论文对这些留白均如实声明。）
问 7：谁会用到它？
（答：随机约束满足与稀疏随机结构社区获得”每个固定 k 都有极限阈值”这一基准事实；族内两篇方差论文直接沿用本文的截断方差与删除—pivotal 框架；后续做 α_k 数值逼近（如 k=3 的物理预测 ~4.267）的人有了收敛性保证作地基。）
总评
作为可满足性猜想的独立第二证明，其分量在于”集中性 + 近似超可加”这条干净路线和可复用的方差工具；最大风险在替换引理的一致性与插值符号这类”方向错了全文白费”的细节上——好在优先权已由 Carenini 兜底，即使本文有缝，猜想的地位也不依赖它。