结果族 235：Limiting random SAT thresholds, sharp variance and computability · 学科：Probability and statistical mechanics · 验证状态：暂无形式化证明，请以社区核验为准
3-SAT 那篇把悬崖宽度钉死在 √n；这篇论文搭的是一般 k 的脚手架：k ≥ 4 时宽度同样恰是 √n；k = 3 先证到 √(n·log n)，把最后一缕对数留给姊妹篇砍掉，并精确定位了对数损失是从哪一步漏进来的。它回答的是比”悬崖在哪”更细一层的问题：不同随机样本的崩溃点，彼此最多能差多远？
关键词卡片
@@M@@T_{n,B}=\min(H_n,\lfloor Bn\rfloor)@@：先在有限处截断、证完再放开的技术。@@M@@U_k=\log 2/(-\log(1-2^{-k}))@@：密度一旦超过它，满足指派的期望数爆炸。看个具体例子
数字版定理：@@M@@\operatorname{Var}(H_n)\le C_k\,n\,\ell_k(n)@@，其中 @@M@@\ell_3(n)=\log(en)@@、@@M@@\ell_k(n)=1@@（k ≥ 4）；同时 @@M@@\operatorname{Var}(H_n)\ge c_k n@@。代入 n = 10^6：@@M@@\log(en)\approx 14.8@@，即 k = 3 的上界多背一个约 15 倍的因子，k ≥ 4 则干净地线性。同样的一致上界对任何固定截断 @@M@@T_{n,B}@@ 也成立；当截断水平 @@M@@B>U_k@@ 时，截断版本还有线性下界。由此，固定概率水平 @@M@@\eta@@ 与 @@M@@1-\eta@@ 之间的转移窗口宽度为 @@M@@O_{k,\eta}(\sqrt{n\ell_k(n)})@@。对数的来源被查明：层饼积分的被积指数 @@M@@k-2\beta-1@@（@@M@@\beta=\dfrac{k}{k-1}@@）在 k = 3 时恰为 −1，积分发散成对数；k ≥ 4 时可积。
为什么值得关心
承上启下：把阈值存在性那篇的 @@M@@O_k(n^{1+2/k})@@ 界磨近最优，又为 3-SAT 姊妹篇搭好被其完整重证并沿用的”删除—根测试”框架；对数损失的病灶被精确定位，恰好就是姊妹篇下刀的地方。
暂无形式化证明（AI 结果待核验）
衔接《解读 Variance of the Random k-SAT Hitting Time》入门导读
第一级台阶
导读把这篇定位为”一般 k 的脚手架”。半数学地说：对象仍是逐条加入随机子句过程中、第一个使公式不可满足的时刻；要问的量是这个时刻在不同随机样本间的散布。本文对一般固定长度的子句回答：长度至少四时，散布的标准差恰为变量数的平方根量级；长度为三时先证到平方根乘一个对数因子，把最后那缕对数留给姊妹篇砍掉，并精确指认了它是从哪一步漏进来的。
第二级台阶
四个概念精确化。命中时间与截断：首个不可满足前缀的下标；技术上先在固定倍数于 n 处截断、证完再放开。Efron–Stein 不等式（坐标删除形式）：总方差不超过”逐条删去一条子句造成的延迟”的平方期望之和。根与测试子句：删去的子句的 k 个变量称为根并钉在其唯一 falsify 的取值上；若恢复该子句会破坏可满足性，则每个可用根翻转都必须被该根接触的、长度减一的测试子句拦截。冻结坐标与杀伤概率：若指派集合中某变量取值恒定，称其冻结；恰是冻结坐标的计数给出短子句杀伤概率的精确公式。
第三级台阶
定理的语境：固定 k 至少为三，上界对所有 n 成立、下界要求 n 充分大；截断版本的下界需要截断水平超过一阶矩阈值——每指派存活概率为 1−2^{-k}，超过该阈值后期望指派数爆炸，转移必然发生在截断之内，这条假设是实质的：截得太早，过程在随机相变前就被掐断。结论：命中时间的方差不超过常数倍 n 乘一个修正因子——k 至少为四时该因子为一，方差恰为线性；k 为三时因子为 log n。对数损失的病灶被定位：延迟平方的层饼积分中被积指数 k − 2β − 1（β = k/(k−1)）在 k 为三时恰为负一、积分发散成对数，k 至少为四时可积。相反应地，两个固定概率水平间的转移窗口宽度为该修正因子的平方根乘 √n。
对固定 @@M@@k\ge3@@ 的随机 @@M@@k@@-SAT，证明了首个不可满足前缀下标 @@M@@H_n@@ 的方差在 @@M@@k\ge4@@ 时恰为 @@M@@\Theta_k(n)@@；@@M@@k=3@@ 时介于正常数倍 @@M@@n@@ 与 @@M@@n\log n@@ 之间（对数空隙由 3-SAT 姊妹篇消除）。这把相变窗口宽度钉在 @@M@@\sqrt n@@ 量级，改进了此前 @@M@@O_k(n^{1+2/k})@@ 的方差估计。
阈值的位置与涨落是两个问题：Friedgut 证明随机 @@M@@k@@-SAT 的转移尖锐，但不给窗口宽度；Wilson 证明窗口至少 @@M@@\Omega_k(\sqrt n)@@ 宽；Carenini 的并发工作给出 @@M@@O_k(n^{1+2/k})@@ 的命中时间方差上界。窗口宽度本质上由命中时间（hitting time）@@M@@H_n@@ 的方差控制——方差小意味着各样本的相变时刻集中。此前技术需要对”删去子句后其变量的邻域大小”施加对数截断，在 @@M@@k=3@@ 处恰好造成对数损失。本文把邻域大小作为随机参数完整保留并直接控制其矩，得到接近最优的方差界，同时为 3-SAT 姊妹篇搭好框架。
定理：固定整数 @@M@@k\ge3@@，记 @@M@@\ell_k(n)=\log(en)@@（@@M@@k=3@@）、@@M@@\ell_k(n)=1@@（@@M@@k\ge4@@）。存在常数 @@M@@C_k,c_k>0@@ 使 @@M@@\operatorname{Var}(H_n)\le C_kn\ell_k(n)@@（一切 @@M@@n\ge k@@），且对充分大 @@M@@n@@ 有 @@M@@\operatorname{Var}(H_n)\ge c_kn@@；故 @@M@@k\ge4@@ 时 @@M@@\operatorname{Var}(H_n)=\Theta_k(n)@@。同样的上界对任意固定截断 @@M@@T_{n,B}=\min(H_n,\lfloor Bn\rfloor)@@ 成立；当 @@M@@B>U_k@@（@@M@@U_k=\log2/(-\log(1-2^{-k}))@@ 为一阶矩阈值）时截断版本也有线性下界。由此，固定概率水平 @@M@@\eta@@ 与 @@M@@1-\eta@@ 之间的转移窗口宽度为 @@M@@O_{k,\eta}(\sqrt{n\ell_k(n)})@@。
上界走坐标删除的 Efron–Stein 路线：删去第 @@M@@i@@ 条子句（保留时间指标）使截断命中时间延迟 @@M@@D_i\ge0@@，则 @@M@@\operatorname{Var}(T_{n,B})\le\sum_i\mathbb E D_i^2@@，只需一致证 @@M@@\mathbb E D_i^2=O_k(\ell_k(n))@@。核心是两种杀伤的比较：称一组子句”杀死”指派集合 @@M@@S@@，若 @@M@@S@@ 中无成员满足其全部子句。令 @@M@@q_d(S)@@ 为 @@M@@d@@ 条随机 @@M@@(k-1)@@-子句杀伤 @@M@@S@@ 的概率，@@M@@\tau_k(S)@@ 为逐条加入随机 @@M@@k@@-子句直到首次杀伤的期望条数。先用冻结坐标公式 @@M@@h_s(S)=(b)_s/(2^s(u)_s)@@ 与幂次比较证一条 @@M@@(k-1)@@-子句的杀伤力可用 @@M@@g@@ 条 @@M@@k@@-子句以 @@M@@K_kg^{-(k-1)}@@ 的误差模拟，对任意残差集合一致成立；例外情形（恰有 @@M@@k-1@@ 个冻结坐标，任何单条 @@M@@k@@-子句都无法杀伤）由整块的联合效应兜底。再逐条顺序条件化替换，选 @@M@@g\approx(q/2K_kd)^{-1/(k-1)}@@ 并把无限子句序列按块分组，得无任何下截断的寿命估计 @@M@@\tau_k(S)q_d(S)^\beta\le C_kd^\beta@@，其中 @@M@@\beta=k/(k-1)@@。下一步把 @@M@@C_i@@ 的 @@M@@k@@ 个变量定为根，其余子句按根接触分为普通、测试、碰撞三类；暴露全部根类型后，普通子句与测试子句的非根部分仍保持独立。若恢复 @@M@@C_i@@ 破坏可满足性，则每个可用根的翻转都须被该根的测试子句（长度 @@M@@k-1@@）拦截，无碰撞时给出 @@M@@k@@ 个独立测试同时杀伤非根解集 @@M@@S_m@@ 的概率 @@M@@q_m^k@@；而删除事件的剩余时长由寿命估计压到 @@M@@O(d^\beta q_m^{-\beta})@@。乘积中还剩 @@M@@q_m^{k-\beta}@@，对时间积分时再用首达停时的占位估计（水平 @@M@@a@@ 以上的停留时间 @@M@@\le C_kd^\beta a^{-\beta}@@）做层饼积分，被积指数 @@M@@k-2\beta-1@@ 在 @@M@@k=3@@ 时为 @@M@@-1@@ 而产生对数，在 @@M@@k\ge4@@ 时可积——这正是对数损失的来源与分界。最后用根入射计数 @@M@@d@@ 的一致有界指数矩、以及入射与碰撞的联合阶乘矩（@@M@@\mathbb E[d^p\mathbf 1_{\{V\ge r\}}]\le Cn^{-r}@@）平均掉稀有碰撞，求和得截断方差界；一阶矩指数尾部 @@M@@2^n(1-2^{-k})^m@@ 去掉足够晚的截断。下界由 Wilson 分位数分离定理（@@M@@3/4@@ 与 @@M@@1/4@@ 水平相距 @@M@@\ge d_k\sqrt n@@）加独立副本比较得到，要求截断晚于 @@M@@U_k@@ 以保证转移发生在截断之内。
本文主结果暂无形式化证明，OpenAI 官方声明未经形式化的结果可能有问题，请以社区核验为准。本文在族内承上启下：一方面改进阈值存在性姊妹篇中的 @@M@@O_k(n^{1+2/k})@@ 截断方差界，另一方面为 3-SAT 姊妹篇提供了被其完整重证并再利用的删除–根测试框架；引言还指出族内另有姊妹篇证明 @@M@@\alpha_3@@ 是可计算实数。@@M@@k=3@@ 处的对数空隙正是由 3-SAT 姊妹篇用势函数方法闭合的。作者将解决可满足性猜想的优先权归于 Carenini 的并发工作。
针对《Variance of the Random k-SAT Hitting Time》，基于论文原文（定理 1.1、引言 §1.1–1.2 及证明路线）
问 1：证明中最关键、最脆弱的一步是什么？
（答：寿命估计 τ_k(S) q_d(S)^β ≤ C_k d^β，β=k/(k−1)，且”对 q_d(S) 无任何下截断”（引言 §1.2）。它说：容易被 d 条 (k−1)-子句杀死的指派集，在 k-子句下期望寿命也短。证明要点是冻结坐标公式 (b)_s/(2^s(u)_s) 加幂次比较，把一条 (k−1)-子句用 g 条 k-子句以 K_k g^{-(k−1)} 误差逐块模拟，并覆盖”没有单条 k-子句能杀”的集合。若无”无下截断”，稀有但杀伤力介于中间的集合会逃过控制——这一条是全文改进的枢纽。）
问 2：相比前人的真正改进在哪？
（答：此前技术对”删去子句后根变量的邻域大小”施加对数截断，k=3 处造成损失；本文把邻域计数 d 作为随机参数完整保留、直接控制其各阶矩（引言 §1.1 末），代价是必须在不破坏短子句测试独立性的前提下使用 d——通过对截断内的入射模式条件化实现，碰撞由联合阶乘矩 E[d^p 1_{V≥r}] ≤ Cn^{-r} 买单。结果把阈值姊妹篇与 Carenini 的 O_k(n^{1+2/k}) 磨到 nℓ_k(n)，且对数损失的病灶被定位于层饼积分的指数 k−2β−1。）
问 3：截断下界为什么要求 B > U_k？
（答：U_k = log 2/(−log(1−2^{-k})) 是一阶矩阈值——每个指派以 1−2^{-k} 概率存活一条子句，超过 U_k 后期望存活指派数趋于零，转移必然落在截断之内；截得太早，过程还没走到随机相变就被掐断，截断方差自然小于真实方差（定理 1.1 后的说明）。论文还指出只需”整数帽 L_n=O(n) 且 P(H_n>L_n−1)≤1/4 最终成立”，B>U_k 只是显式充分条件。）
问 4：AI 生成证明最可能出错的模式？
（答：暴露与条件化的记账。根的暴露（普通/测试/碰撞三分）后必须保持”普通子句与测试子句的非根部分仍独立”——入射模式一经条件化，哪些量还独立、哪些已被污染，是最容易含糊的地方；其次是层饼积分的指数运算与”通过截断条件化使用 d”的相容性。好在附录 A 自证两条估计对任意指派集已是极限（sharp），等于画出了方法的边界，诚实且降低了过度声明的风险。）
问 5：k=3 的对数损失为什么恰好砍不掉又砍得掉？
（答：本文框架内砍不掉：附录 A 表明两条核心估计已达最优，积分指数在 k=3 时恰为 −1；姊妹篇换引擎（势函数漂移，β=3/2 与三个根配套）才把对数消掉。两文的关系是”框架 + 病灶定位”与”靶向新药”，本文引言明确把 k=3 的闭合归功于姊妹篇。）
问 6：这个结果与阈值存在性怎么衔接？
（答：引言点明：阈值姊妹篇给出 lim E H_n/n = α_k，但对方差尺度上的偏置 E H_n − α_k n 没有任何界——本文的集中是绕有限尺寸期望做的，不涉及 α_k。族内另有姊妹篇证明 α_3 是可计算实数。三层合起来：位置存在、位置可计算（k=3）、涨落尺度确定，缺的下一块自然是中心极限定理。）
问 7：谁会用到它？
（答：随机 SAT 精细相变社区获得每个固定 k 的正确涨落尺度；3-SAT 姊妹篇直接重用本文的删除–根测试框架；附录 B 的不同尺寸 proper 模型比较与附录 C 的第二条 k=3 证明（前缀暴露 + 入射截断）给后续工作提供了备选路线与常数收紧空间。）
总评
这是族内承重墙式的一篇：把方差界磨到近最优、给姊妹篇搭好全套脚手架、并诚实标出方法的边界与病灶；最大风险在入射模式条件化下的独立性记账——这类证明里”看似独立的量其实已 correlated”是最常见的隐性裂缝。