01
问题
| 体系 | 三维空间中 N 个同种原子(2 ≤ N ≤ 200),零压强下的自由团簇。每一对原子都通过 Lennard-Jones 势相互作用,写成距离平方 s = r² 的函数:φ(s) = 4ε(σ¹²/s⁶ − σ⁶/s³),不截断。 |
| 能量 | E(x) = ½ Σi≠j φ(sij)。能量、梯度与 Hessian 都是坐标的有理函数,检查器精确计算的正是 Lean 中推理的那个公式(CSP-C01)。 |
| 对称性 | E 在转动与反射、平移、原子重新编号下不变,所以极小在 ℝ3N 中从不孤立:它是模这些运动的极小,6 个轨道方向由 Eckart 规范固定。 |
| 输入 | ε、σ 与每个坐标在证书中都是精确的二进有理数 m·2e,即搜索器实际得到的 double。检查器以 PROBLEM 行回显问题,供调用者比对。 |
02
一次认证运行的报告
LJ₁₃,种子 1,12 代、每代 12 个粒子。搜索器保留三个最好的不同极小,并把最好的一个转动、原子倒序编号后再加一次,演示去重证书。检查器读入证书,用精确有理数重新检查一切;下面是它的完整输出。
certify-csp lj13.cert
PROBLEM N 13 eps 1.00000000000000000000 sigma 1.00000000000000000000 pressure 0 MIN_OK 0 -44.326801419534023 -44.326801419534022 0.000056994475 0.00000000000611516998 MIN_OK 1 -41.471979847810849 -41.471979847810848 0.000027927293 0.00000000001481269784 MIN_OK 2 -41.444597002447481 -41.444597002447480 0.000019549105 0.00000000002081694528 MIN_OK 3 -44.326801419534023 -44.326801419534022 0.000056994475 0.00000000000610162457 SAME_OK 0 3 DISTINCT 0 1 DISTINCT 0 2 DISTINCT 1 2 DISTINCT 1 3 DISTINCT 2 3 BEST 3 -44.326801419534023 -44.326801419534022 TIE 3 0 CSP_OK 4
| 输出行 | Lean 定理保证的结论 | 命题 |
|---|---|---|
| PROBLEM | 证书所针对的问题(N、ε、σ、压强)的精确值,供调用者与自己要求的问题比对。 | CSP-B02 |
| MIN_OK k lo hi R d | 在候选 k 周围半径 R 的球内(Eckart 截面上),能量恰有一个极小点 x*,带二次增长;它是球内唯一的驻点,在整个 ℝ3N 中 ∇E(x*) = 0,‖x* − x₀‖ ≤ d,E(x*) ∈ [lo, hi]。离 x₀ 不超过 R 的任何构型能量都 ≥ E(x*),取等时只能是 x* 经转动、反射或平移得到的副本。 | CSP-B01、D01、D02 |
| SAME_OK a b | 候选 a、b 的精确极小是同一个结构:相差一个原子置换、一个正交变换和一个平移,能量相等。 | CSP-B04 |
| DISTINCT a b | 两个能量区间不相交,所以两个精确极小是不同的结构:任何置换、转动、反射或平移都不能把一个变成另一个。 | CSP-B04 |
| UNDECIDED a b | 两者都未证明:区间相交,证书中也没有这一对的 same 记录。 | — |
| BEST k lo hi | 候选 k 在这次运行的候选中能量上界最小。不是全局最优的结论。 | CSP-B02 |
| TIE k j | 候选 j 的区间与最低者相交,这次运行无法判定哪个更低。这里 j 是转动并重新编号的副本,SAME_OK 已证明它是同一个结构。 | CSP-B02 |
| CSP_OK K / CSP_FAIL | 全部 K 个候选通过;否则检查器指出第一个未通过的检查,不认证任何结论。 | CSP-B02 |
03
证书如何工作
搜索器停在一个梯度很小但不为零的点 x₀。证书证明在它给出的半径内有一个真正的极小 x*:在构型空间的合适截面上,能量在一个小球内强凸。所有检查都是精确有理数运算,搜索器的浮点数只是数据。
- 1
Eckart 规范
转动与平移使 Hessian 在 6 个方向上奇异。检查器在过 x₀ 的 Eckart 截面上工作:相对 x₀ 没有净平移、没有净转动的位移。Lean 证明任何构型都可以经转动与平移移进这个截面且离 x₀ 不更远,所以截面上的严格极小就是模欧氏运动的严格极小(CSP-D01)。
- 2
原子保持分开
在半径 R 的球内,任一对原子的相对位移不超过 √2·R,所以每个距离平方都大于显式的 slo > 0。检查器据此用 φ″、φ‴ 的显式界和中值定理,算出每一对原子的 Hessian 在球内最多下降多少。
- 3
梯度小
‖∇E(x₀)‖ ≤ g:每一项向下舍入到 2⁻¹⁰⁰ 的格点,舍入误差计入界中。
- 4
精确的正定性
x₀ 处的 Hessian 减去成对损失、加上 6 个轨道方向上的罚项 κ、再减 μ·I,用 Schur 补消元证明半正定:每一步舍入到 2⁻¹⁰⁰ 的格点并在对角线上减去舍入误差(在 Lean 中证明可靠)。于是 E 在截面内整个球上 μ-强凸。
- 5
强凸球定理
若 g < μR,球内恰有一个驻点,即唯一的极小点,离 x₀ 不超过 g/μ,能量在 [E(x₀) − g²/(2μ), E(x₀)] 中(CSP-D02)。检查器自己精确包住 E(x₀),这就是输出的区间。
- 6
相同或不同
same记录给出一个置换、一个精确正交的有理矩阵(带符号的 Cayley 变换,精确检查 QᵀQ = I)和一个平移,把一个候选映进另一个的唯一性球内,反之亦然。能量区间不相交的两个极小无需更多数据就是不同的结构。
区间为什么这么窄:搜索器每次弛豫最后用 Newton 法把梯度降到约 10⁻¹³,所以 g²/(2μ) 约为 10⁻²⁴;区间宽度由 2⁻¹⁰⁰ 格点的舍入和输出小数的向外舍入决定。唯一性半径为 2×10⁻⁵ 到 1.7×10⁻⁴ σ,受 Lennard-Jones Hessian 变化之快的限制。
04
搜索,以及关于它证明了什么
搜索器 build/mini-csp(C11,双精度)按 Wang、Lv、Zhu、Ma 发表的算法(PRB 82, 094116, 2010;CPC 183, 2063, 2012)实现,只依据论文,不参考任何现有程序。每一代把每个粒子弛豫(BFGS,再用带规范罚项的 Newton 法收尾),按能量排序,把最差的一部分换成新的随机结构,其余按粒子群更新 v ← ωv + c₁r₁(p − x) + c₂r₂(g − x)、x ← x + v 移动。排序后的原子间距离作为指纹,只用来提出合并,由检查器决定。
搜索器做的一切都不进入可信链:它的错误只会让它漏掉结构,不会产生错误的认证结论。另外,Lean 在账本中写明的理想化假设下证明了搜索算法本身的两条性质:
- 粒子群稳定区域(CSP-A01)吸引子固定、随机数理想均匀时,粒子的均值收敛当且仅当 |ω| < 1 且 0 < c₁ + c₂ < 4(1 + ω);均方收敛当且仅当落在一个更小的区域内,c₁ = c₂ 时即 Poli 的 0 < c < 24(1 − ω²)/(7 − 5ω)。两者都是充要条件,经二次、三次多项式的 Schur–Cohn/Jury 判据证明。Clerc–Kennedy 缺省参数 ω = 0.7298、c₁ = c₂ = 1.49618(以及它们的精确 double 值)在两个区域内。
- 随机补充找到全局最优的吸引盆(CSP-A02)若每一代至少有一个独立的、在包含全局极小的盒子中均匀抽取的结构,t 代后仍没有一个落在其 δ 邻域内的概率不超过 (1 − pδ)t → 0,pδ > 0。只是渐近结论,不给有限次运行的保证。
致谢。搜索算法来自 CALYPSO,作者是王彦超、吕健、朱力、马琰铭(吉林大学)。正是他们对粒子群结构预测清晰的公开描述,才使独立、可验证的实现成为可能;mini-CSP 是向这项工作的致敬,不是它的替代。
05
可信账本中的命题
| 命题 | 内容 | 等级 |
|---|---|---|
| CSP-C01 | 团簇能量及其一阶、二阶方向导数是坐标的有理函数,距离都为正时就是真正的导数;能量在正交变换、平移与原子置换下不变;成对 Hessian 的显式下界 | T3 |
| CSP-D02 | 强凸球定理:球上 μ-强凸、球心梯度 ≤ g < μR,则球内恰有一个驻点,即带二次增长的唯一极小点,离球心不超过 g/μ,能量在 [f(x₀) − g²/(2μ), f(x₀)] 中 | T3 |
| CSP-D01 | 规范:任何构型经转动、反射与平移可移进 Eckart 截面且离 x₀ 不更远;截面上的严格极小是模欧氏运动的严格局部极小,也是整个 ℝ3N 中的驻点 | T3 |
| CSP-B01 | 检查器可靠(局部极小):MIN_OK 所说的结论 | T4 |
| CSP-B04 | 检查器可靠(去重):SAME_OK 与 DISTINCT | T4 |
| CSP-B02 | 检查器输出:每一行都由 B01、B04 直接读出;BEST 是区间的比较,不是全局最优的结论;PROBLEM 回显 | T4 |
| CSP-A01 | 粒子群的一阶与均方稳定区域(充要条件);缺省参数在两个区域内(理想化模型 A-CSP-01、02) | T3 |
| CSP-A02 | 随机补充以趋于 1 的概率到达全局极小的任意邻域(理想化模型 A-CSP-03) | T3 |
| CSP-T01 | 搜索器找到 LJ₃…LJ₁₃ 的剑桥团簇数据库极小,每个输出被检查器接受;篡改的证书被拒绝(verify_all 的已知答案) | T0 |
| CSP-B06 | 统一的退出码(10 月 7 日第二轮对抗式复审):没有行首记号以 _FAIL 或 _PARTIAL 结尾的行时才为 0;主检查通过、次要检查未通过时为 3;拒绝为 1,无法解析为 2 | T0 |
| CSP-P01 | C 粒子群单步(速度截断、盒子处理、分数坐标折回)在 IEEE 754 模型下的 Frama-C/WP 证明:尚未编写,目标 T4 | T0 |
checkMin_sound、checkSame_sound、distinct_sound、ball_min、align 的 #print axioms 只有 Lean 的标准公理 propext、Classical.choice、Quot.sound。
06
证明依赖
命题之间谁建立在谁之上,直接从 Lean 证明项读出(不是账本里手写的“依赖”列)。图中先只显示本领域;点图例可以加上其他领域,切到“全部 Lean 定理”可以看到定理一级。所有领域合在一起的图在纲领页。
- 命题或定理,颜色表示领域
- 用到:箭头指向证明依赖的东西
- 越大,被越多的结果用到
- 选中节点用到的
- 用到选中节点的
拖动平移,滚轮或双指缩放,拖动节点可以移动它;点一个节点看它的上下游,“只看它的链”只显示它直接或间接用到的与用到它的。命题 A 指向命题 B 表示 A 的证明(沿着不属于任何命题的引理)用到了 B 的定理;两个命题可以互相用到。没有 Lean 定理的命题(测试、T0–T2)不在图中。图由 scripts/depgraph.py 生成,只帮助阅读,不属于可信链。
07
交叉校验与辅助证据
| 团簇 | 认证的最低能量(Lean 区间) | 剑桥团簇数据库 |
|---|---|---|
| LJ3 | [-3.000000000000001, -2.999999999999999] | -3.000000 |
| LJ4 | [-6.000000000000001, -5.999999999999999] | -6.000000 |
| LJ5 | [-9.103852415707557, -9.103852415707556] | -9.103852 |
| LJ6 | [-12.712062256809339, -12.712062256809338] | -12.712062 |
| LJ7 | [-16.505384168012216, -16.505384168012215] | -16.505384 |
| LJ8 | [-19.821489192154761, -19.821489192154760] | -19.821489 |
| LJ9 | [-24.113360433647182, -24.113360433647181] | -24.113360 |
| LJ10 | [-28.422531893437559, -28.422531893437558] | -28.422532 |
| LJ11 | [-32.765970089979004, -32.765970089979003] | -32.765970 |
| LJ12 | [-37.967599562363927, -37.967599562363926] | -37.967600 |
| LJ13 | [-44.326801419534023, -44.326801419534022] | -44.326801 |
- ASE 3.29(
LennardJones,截断 1000 σ)在 11 个认证球心上的能量,对照 mpmath 40 位精确求和≤ 7.1×10⁻¹⁵ - 唯一性半径 R / 距离界 ‖x* − x₀‖,LJ₃…LJ₁₃2×10⁻⁵…1.7×10⁻⁴ σ / ≤ 2.1×10⁻¹¹ σ
- 一个坐标的尾数加 2³⁰CSP_FAIL(局部极小检查)
same置换中交换两项CSP_FAIL(same 检查)- 证书中把 ε 改成 2被接受,由已知答案与
PROBLEM回显发现 - 每个团簇的搜索时间 / N = 3、7、13 时检查 4 个候选的时间0.01–9 秒 / 0.1、1.3、17 秒
- AddressSanitizer、UBSan、LeakSanitizer 下的搜索器无报错
08
缺口
- 全局最优
BEST是这次运行找到的最低认证极小。证明它是全局最优需要构型空间上的分支定界证书(计划阶段 5,CSP-B05)。 - 晶体、对称性与压强目前只有零压强的自由团簇。对称约束生成与对称性证书、周期晶胞、压强、多组元体系在阶段 2、3(CSP-B03、C02、D03、D04)。
- 搜索中的去重
same记录目前只由--same-demo产生;搜索中指纹提出的合并还没有置换与转动的证书,只保留一个代表(计划用置换匹配加 Kabsch 对齐)。 - 搜索器的代码不受信任(T0)。粒子群单步计划在 IEEE 754 模型下做 Frama-C/WP 证明(CSP-P01);搜索循环、分发与断点续跑写 TLA+ 规范并做 trace validation(CSP-L01);另加带 JSON 输出的
fis csp命令(CSP-L02)。 - 理想化模型之外CSP-A01、A02 假设吸引子固定、随机数理想、坐标为实数;均方结论只覆盖 p = g。阶段 1 的搜索器用 ω = 0.7、c₁ = c₂ = 1.5,按证明的公式在两个区域内,但不是
defaults_stable的那组常数;它还截断速度,这不在模型之内。
计划:docs/plan-mini-csp.md;规格:domains/csp/README.md;账本:domains/csp/LEDGER.md。在同一体系上与 CALYPSO 本身对照是可选的,不是依赖。