k=12:锁点法的更强局部下界
4633 → 4635 → 4647 → 4661 · 完整归约与整数证书 · 合作者方法的新实例
来源信息
k=12:锁点证书的更强局部下界
完整整数证书给出
| 路线 | 相对同一基线 | 结论与证据范围 | |
|---|---|---|---|
| 同一最大 RS 预算基线 | 4633 | 0 | |
| 一般增长定理 | 4635 | +2 | 全部 |
| 直接优化结构 RS 判据 C.2 | 4647 | +14 | |
| 合作者锁点法的新实例 | 4661 | +28 | 纸面归约+691429 个完整局部型的整数证书;尚未 Lean |
统一方法提供无限参数范围和已完成的形式证明;锁点法在这一固定参数上给出更强数值。本表的 +2、+14、+28 使用同一个 k=12 基线;总览图现已统一采用已核参考下界的最大值:
1. 对象、来源与结论
定义 1.1(Property B 与
来源说明。 下文的随机排列、条件概率公式、最轻坏对扣除、统一证书准则和一般选锁定理,来自合作者 《一般 k-uniform Property B 的锁点证书定理:k=10,11 的严格整数验证》 的定理 A、其“数学基础”全节以及定理 B。它们本来就对一般
定理 1.2(本次实例,计算机辅助证明候选)。 任意有限简单 12 元超图,若边数至多
证明结构。 引理 2.1 将任意假定反例归到同一实际的点对覆盖、恰有
2. 从原始超图到完整有限点数域
引理 2.1(最小反例与补边;合作者定理 A 的实例化)。 若存在至多
证明。 在全部至多
当
若
且左侧随
可在原顶点集补入不同的 12 边直至恰有
3. 条件排列与真实失败概率
定义 3.1(锁点和精确迹)。 取
引理 3.1(失败的实际单交见证;合作者定理 A)。 初始全红,按排列依次处理各点;仅当当前点是某条仍全红边的最后点时将它改蓝。最终没有全红边;若有全蓝边,则存在实际有序边对
证明。 红边在其最后点处必被破坏。若最终有蓝边
定义 3.2(精确有序单交权重)。 对固定的实际单交对、迹为
若
其余情形为零。这些是依次无放回选择左右顶点集的联合计数,没有假设左右事件独立。
定义 3.3(单边端点概率)。 单边终点概率为
引理 3.2(加权 link 扣除;合作者定理 A)。 在锁点
个无序 incident 边对还共享中心以外的点。对都含
从全部类型对槽位按
证明。 去掉中心后的
等于或小于所有 link 边对交集大小之和;每一非空交集至多
引理 3.3(零锁的全局修正;合作者定理 A)。 点对覆盖时,至少有
个无序多交边对,故有序单交对数至多
证明。 按顶点对或边对双计数,且
不同简单边交集至多
4. 实际锁点存在与两型覆盖
引理 4.1(一锁及二锁;合作者定理 A)。 一锁可取全图最低度点,其度数满足
若
一锁重数为
证明。 最低度不超过平均度。若与最低度点共度 1 的点有
引理 4.2(一般选锁定理;合作者定理 B)。 对任意点对覆盖的简单
若整数
则存在
证明。 令
Caro–Wei 和 Cauchy–Schwarz 给
这里分母由前式至少为
所以
引理 4.3(三锁迹型完备;合作者定理 A)。 对两两共度恰为 1 的三锁,恰有以下两种多点迹;度数排序为
未列的迹重数均为零。
证明。 若有一条边含三锁,则它已经使用全部三对的唯一共边,不再有二点迹。否则三个点对各由不同边承载,得到三个二点迹。其余单点迹与空迹由各点实际度数和总边数唯一确定;没有第三型。排序只是给实际点重新命名,并将其放到相应固定位置;不需要概率公式对三个位置对称。
定义 4.4(本次布局和完整枚举域)。 一锁位置为
成立的最小整数
5. 向外舍入、逐位置最小值与完整整数证书
引理 5.1(整数证书的方向)。 取
把每个无序槽位赋权
证明。 每个上界项向上舍入。任何真实坏对集合的原权重不小于它自己的向下舍入权重,后者又不小于全部槽位中最轻的
命题 5.2(
| 锁数 | 点数 | 完整型数 | 最大 | 最大处 | |
|---|---|---|---|---|---|
| 0 | 93–511 | 419 | 4503308793007378 | 290834363118 | |
| 1 | 512–564 | 2929 | 4503474369079970 | 125258290526 | |
| 2 | 565–648 | 87807 | 4503473506514732 | 126120855764 | |
| 3 | 649–782 | 600274 | 4498353804903973 | 5245822466523 |
计算证据。 完整逐点数记录在 M4660.json,分段及计数在 SUMMARY.json,实际执行日志在 M4660.log。全部计算墙钟 86.712 秒、CPU 84.620 秒、峰值 RSS 42.8 MB。这是完整局部度数/迹型证书,不是整图枚举,也不是由几张抽样超图归纳。
NumPy 只做确切 signed int64 的非负乘加。所有最终使用的 271 张锁表均检查了安全界:FixedCertificate 的纯 Python 大整数路径逐位复核;这七型复核本身不被描述为第二实现重跑全部 691429 型。
定理 1.2 的完成。 任意假定反例先由引理 2.1 进入实际候选域。每个点数落入命题 5.2 的某段;引理 4.1 或 4.2 给出真实锁点,引理 4.3 和定义 4.4 保证其真实型被枚举。引理 3.1–3.3 与 5.1 将对应分子接回该超图的失败概率。命题 5.2 给严格小于 1,因此某个条件排列的贪心结果是正确二染色,矛盾。原命题不增加点数、点对覆盖、度数、锁点或证书作为外部前提。
6. 证据状态与未通过试验的准确含义
本次已经取得纸面迁移归约和完整整数证书。新实例尚未 Lean 形式化。独立实现已重建全部 690 个候选点数、全部 691429 个必要参数型,无漏项或重复;其中二锁的 Fraction 公式复算 31 个型,覆盖各段最紧型、锁数交界两侧、度数上下端点及两种三锁迹型,精确值均不超过原证书上界且严格小于 1。零/一锁的全部 3348 型还由独立 grok-4.7-build、xhigh、end_turn):一般选锁准则与概率计数可迁移至
7. 源码与复现
原合作者方法与公式:原稿定理 A/B;原算术实现:FixedCertificate、FastExact。本次新增:完整 driver、标量重放与安全汇总、分段汇总。原作者文件保持原样。
在项目根目录执行:
OPENBLAS_NUM_THREADS=1 OMP_NUM_THREADS=1 .tools/math-python/bin/python context/propertyb-general/k12-lock-pilot-20261021/pilot/scan.py 4660 --seconds 350
OPENBLAS_NUM_THREADS=1 OMP_NUM_THREADS=1 .tools/math-python/bin/python context/propertyb-general/k12-lock-pilot-20261021/pilot/replay.py
.tools/math-python/bin/python context/propertyb-general/k12-lock-pilot-20261021/pilot/summarize.py
本页独立于一般增长主阅读页与已发布图;它展示一个新固定参数实例,不改写旧小参数实例的验收状态。