结果族 229：Exact three- and four-state reconstruction thresholds and four-state tree capacity · 学科：Probability and statistical mechanics · 验证状态：暂无形式化证明，请以社区核验为准
一张匿名社交网络图里藏着三个朋友圈：圈内人更容易互加好友。只看图，能不能把三个圈分开？这篇论文给出了精确的”能/不能”分界线；而解题的钥匙，是一个关于三种颜色传话游戏的纯数学定理。
关键词卡片
看个具体例子
树侧：正则 b 叉树上重构当且仅当 b·λ^2 大于 1，等号处不重构；反铁磁端点 λ=−1/2（三着色通道）在分支数 4 处不可重构。图侧推论（圈内连接率 a、圈间 b）：
@@M@@(a-b)^2 > 3(a+2b)@@ 时可分且 O(n log n) 时间可达；否则信息论上不可能。
代入数字：a=3、b=1 时 4 远小于 15，分不出来；a=9、b=1 时 64 超过 33，可以分出来。其中 a、b 是圈内、圈间的平均连接强度，只要求平均度 (a+2b)/3 超过 1。
为什么值得关心
补全了 Mézard–Montanari 2006 年猜想在小区数与负参数上的缺口，并直接定出三社区稀疏随机块模型的精确信息论与算法阈值。
暂无形式化证明（AI 结果待核验）。
第一级台阶
导读给了两个互相咬合的场景：一张匿名社交网络图里藏着三个朋友圈，圈内人更容易互加好友，只看图能否把圈分开；而解题的钥匙是一个三种颜色的传话游戏——老祖宗抽一色，每传一代都可能出错，错误在另外两色间均匀分摊，且偏向可以朝两个方向（更保真或更爱换色）。半数学地说：对象是一棵家谱树加一条”错误均匀分摊”的传话规则；核心量仍是远代信息对根的残留优势；社交网络问题将通过”网络的局部长得像随机家谱”这扇门被树上的定理解决。
第二级台阶
精确化：通道 @@M@@K_\lambda@@ 取对角元 @@M@@(1+2\lambda)/3@@、非对角元 @@M@@(1-\lambda)/3@@，参数 @@M@@-\frac12\le\lambda\le1@@ 是通道的非平凡特征值（@@M@@\lambda=-\frac12@@ 即三着色端点）。树取每个节点 @@M@@b\ge2@@ 个孩子的正则树，或观测型的 Poisson@@M@@(d)@@ Galton–Watson 树（@@M@@d>1@@，观测含无标签树形与深度处的自旋，期望不依存活条件化）。重构优势 @@M@@a_\ell@@ 是后验与均匀律的期望总变差；非重构即 @@M@@a_\ell\to0@@。
第三级台阶
定理断言：两类树上重构当且仅当 @@M@@d\lambda^2>1@@（正则取 @@M@@d=b@@），且一切容许等号 @@M@@d\lambda^2=1@@ 处不重构——正负两种符号均如此；负参数的重构区恰为 @@M@@d>4@@ 且 @@M@@-\frac12\le\lambda<-d^{-1/2}@@，特别地三着色通道在分支数 4 处不可重构。配合 Mossel–Sly–Sohn 的树到图转移（无大度数限制）与 Abbe–Sandon 算法，泊松部分直接给出三社区稀疏随机块模型的推论：在 @@M@@a,b>0@@、平均度 @@M@@(a+2b)/3>1@@ 下，弱恢复可行当且仅当 @@M@@(a-b)^2>3(a+2b)@@，严格不等时 @@M@@O(n\log n)@@ 时间可达，等号及以下信息论不可能。假设 @@M@@d>1@@ 挡住次临界灭绝树，等号判定则全靠熵泛函与有限实验的逐区间攻坚。
证明对称三态广播通道在一切 @@M@@b\ge2@@ 正则树与均值 @@M@@d>1@@ 的观测泊松树上重构当且仅当 @@M@@d\lambda^2>1@@、等号处不重构（两种符号均成立），并据树到图转移推出三社区稀疏随机块模型的精确弱恢复阈值 @@M@@(a-b)^2>3(a+2b)@@。
三态对称通道的重构阈值是否与 Kesten–Stigum 条件 @@M@@d\lambda^2>1@@ 重合，自 Mézard–Montanari（2006）提出猜想、Sly（2011）证明大度数正则树情形以来悬而未决；Mossel–Sly–Sohn（2025）证得大平均度泊松树情形，小度数（尤其负参数与三着色端点 @@M@@\lambda=-1/2@@）一直缺失。由于 Sly 已证 @@M@@q\ge5@@ 态时谱判据失效，三态的必要性必须超出二阶矩框架。此外，观测泊松树上的结论经既有的树到图转移定理可直接决定稀疏随机块模型（stochastic block model）的信息论与算法阈值，这赋予该问题超越树模型的分量。
通道 @@M@@K_\lambda@@：对角元 @@M@@(1+2\lambda)/3@@、非对角元 @@M@@(1-\lambda)/3@@，@@M@@-\frac12\le\lambda\le1@@。主定理：对每个整数 @@M@@b\ge2@@ 与每个实数 @@M@@d>1@@，重构当且仅当 @@M@@d\lambda^2>1@@（正则模型取 @@M@@d=b@@），且一切容许等号 @@M@@d\lambda^2=1@@ 处不重构。正参数阈值为 @@M@@\lambda=d^{-1/2}@@；负参数当且仅当 @@M@@d>4@@ 且 @@M@@-\frac12\le\lambda<-d^{-1/2}@@ 时重构；特别地三着色通道 @@M@@\lambda=-\frac12@@ 在分支数 4 处不可重构。推论（三社区 SBM）：社区内/间连接率 @@M@@a,b>0@@、平均度 @@M@@(a+2b)/3>1@@ 时，弱恢复（weak recovery）可行当且仅当 @@M@@(a-b)^2>3(a+2b)@@；严格不等号时有 @@M@@O(n\log n)@@ 时间算法，等号及以下信息论不可能。
先把后验向量嵌入复平面：@@M@@\zeta=p_1+\omega p_2+\omega^2p_3@@（@@M@@\omega=e^{2\pi i/3}@@），用不变量 @@M@@x=|\zeta|^2@@、@@M@@y=\Re(\zeta^3)@@ 工作；不重构等价于极限不动点处 @@M@@\E x=0@@。阈值以上由线性估计量重构，通道与后代稀疏化把其余参数归约到临界等号与分支 4 的着色情形。正参数等号处：构造熵泛函 @@M@@F=3I-2J+\frac45B@@，其中 @@M@@J@@ 的可加恒等式是 Formentin–Külske 对称化熵递推的对称通道形式，@@M@@B@@ 是中心化对数二次修正。一方面证明恒等式 @@M@@\E(F-dF_e)=-3H+\frac85\alpha(\E J)^2@@，其中 @@M@@H@@ 是合并分支生成的相关性（非负相对熵）；另一方面证明径向亏损不等式 @@M@@F(m)-\lambda^{-2}F(1+\lambda v)\ge\frac{1-\lambda^2}{2}x^2@@，由径向求导与多项式符号分解解析证得。在 @@M@@d=\lambda^{-2}@@ 时两式合并得 @@M@@\frac{1-\lambda^2}{2}\nu+3H\le\frac85\alpha(\E J)^2@@；再用矩估计 @@M@@0\le\E J\le\mu-\lambda q\nu@@ 与投影下界给出的 @@M@@H@@ 下界与之矛盾，分三个 @@M@@\lambda@@ 区间（含仅泊松模型可达的 @@M@@\frac1{\sqrt2}<\lambda<1@@）逐一排除非均匀不动点。负参数：先证一致性缺口——负等号处任何非均匀对称不动点满足 @@M@@\mu=\E x>1/20@@，证明靠 @@M@@x,y,x^2@@ 的两两不等式做矩自助（bootstrap），而不等式由十四个整系数多项式的系数非负性认证；远离着色通道的剩余不动点由加权对数恒等式排除；着色端点附近则用 Bhatnagar–Maneva 式有限实验上界：把后验律放到 @@M@@H=72@@ 网格的 469 个置换轨道上，用重心加细与纯后验补全（截断向下取整、以完全信息消息补足后代尾部）构造支配真实验的上递推，纯整数算术验证在第 162 层（正则着色）或第 99–104 层（泊松分箱）使上实验 @@M@@\E x<1/20@@，与缺口结合逼出均匀极限。全部十进制常数是精确有理数，无任何模拟进入判定。
本文与同族两篇四态论文合成”三、四态精确重构阈值”的完整图景：四态篇处理铁磁 Potts 并提供容量篇所需的封闭后验律类，本文独立处理对称三态（含反铁磁符号与着色端点），技术路线同为”后验律递推 + 严格多项式证书”。主结果暂无形式化证明；负参数与着色部分的证明是计算机辅助的（精确整数算术），SBM 推论还引用 Mossel–Sly–Sohn 的树到图转移定理与 Abbe–Sandon 算法，请以社区核验为准。OpenAI 官方声明：未经形式化的结果可能有问题。
问 1：等号 @@M@@d\lambda^2=1@@ 处，正负参数为什么必须用完全不同的两套论证？
（答：正等号处用的是熵泛函 @@M@@F=3I-2J+\frac45B@@：一边有恒等式 @@M@@\E(F-dF_e)=-3H+\frac85\alpha(\E J)^2@@（@@M@@H@@ 为合并分支生成的非负相关性），另一边径向亏损不等式 @@M@@F(m)-\lambda^{-2}F(1+\lambda v)\ge\frac{1-\lambda^2}{2}x^2@@ 给出下界，两者在非均匀不动点处矛盾。负参数侧该结构失效，改走”一致性缺口”路线：任何非均匀对称不动点满足 @@M@@\E x>1/20@@，再设法让真实验落到缺口之下。）
问 2：证明中最脆弱的一步在哪里？
（答：着色端点附近的有限实验论证。把后验律放到 @@M@@H=72@@ 网格的 469 个置换轨道上，用重心加细与”纯后验补全”（截断向下取整、以完全信息消息补足后代尾部）构造支配真实验的上递推，靠纯整数算术在第 162 层（正则着色）或第 99–104 层（泊松分箱）验证 @@M@@\E x<1/20@@。上实验必须真的支配真实验，且递推须不发散——网格密度、补全方向、层数三者任何一处失衡，缺口论证就接不上。）
问 3：负参数的重构区为什么限制在 @@M@@d>4@@？
（答：@@M@@\lambda<0@@ 时谱阈值条件 @@M@@d\lambda^2>1@@ 要求 @@M@@|\lambda|>d^{-1/2}@@，而通道容许的最负值是 @@M@@-1/2@@，两式相容当且仅当 @@M@@d>4@@。这不是证明的软弱，是参数空间的硬边界；三着色通道 @@M@@\lambda=-1/2@@ 恰在分支数 4 处碰到等号，定理判定其不可重构。）
问 4：与 Sly 2011、Mossel–Sly–Sohn 2025 相比，真正的新意是什么？
（答：Sly 证了大度数正则树、MSS 证了大平均度泊松树；小度数、负参数与着色端点一直缺失。本文去掉大分支限制，完成 Mézard–Montanari 2006 猜想的全度数形式（含 Sly 的 Conjecture 1），并借无大度数限制的转移定理把三社区稀疏 SBM 的弱恢复阈值精确钉死——这是此前没有任何一篇文章单独完成的。）
问 5：SBM 推论的依赖链有多长，哪一环最细？
（答：三环相扣：本文泊松非重构（平均意义）@@M@@\to@@ MSS 树到图转移定理（Theorem 2.1，无大度数限制）@@M@@\to@@ Abbe–Sandon 的 @@M@@O(n\log n)@@ 算法（阈值以上）。最细的一环是从”平均树上非重构”转成转移定理所需的”固定树假设”，论文在第 7 节专门处理这一步——随机树与给定树的交换若不严格，整个信息论下界悬空。）
问 6：AI 生成证明最可能出错的模式是什么？
（答：本文是”解析 + 计算机辅助”双引擎：解析侧的复嵌入 @@M@@\zeta=p_1+\omega p_2+\omega^2p_3@@ 与不变量 @@M@@x,y@@ 的两两不等式靠十四个整系数多项式的系数非负性认证，机器侧的网格递推靠整数算术——典型风险是两类证明接口处常数（@@M@@\frac85\alpha@@、@@M@@1/20@@、@@M@@H=72@@、层数）的一致性错位，以及”上实验支配真实验”这类单调性断言的符号方向。全部未形式化，且论文自印验证程序，代码正确性只能靠复现。）
问 7：这个结果落谁手里最有用？
（答：社区发现领域拿到三社区稀疏 SBM 的完整答案：信息论阈值、算法阈值、@@M@@O(n\log n)@@ 复杂度一次配齐，Decelle–Krzakala–Moore–Zdeborová 2011 的空腔法预测至此在三社区情形严格化；树上的重构理论则补上三态全度数拼图，为 @@M@@q\ge5@@ 谱判据失效前的最后地带画上句号。）
总评
这是同时关掉两个悬置问题的工作——三态全度数重构阈值与三社区 SBM 精确弱恢复阈值，且含负参数与着色端点；最大风险在计算机辅助的网格与多项式证书环节及其与解析部分的接口，虽号称纯整数算术可复现，但未经形式化核验。