PROPERTY B · LOCAL CERTIFICATE

k=12:锁点法的更强局部下界

4633 → 4635 → 4647 → 4661 · 完整归约与整数证书 · 合作者方法的新实例

来源信息
Source: K12_LOCK_COMPARISON.md SHA256: aea109e6b64a Rendered: 2026-10-21 09:37 UTC

k=12:锁点证书的更强局部下界

完整整数证书给出 m(12)≥4661 的计算机辅助证明候选。 它将同一 RS 最大预算基线 4633 提高 28;较直接优化结构 RS 判据所得 4647 再提高 14。原方法是合作者的一至三锁有限证书准则;本次贡献是它在 k=12,M=4660 的完整新实例及迁移核查。新实例尚未 Lean 形式化;独立参数域与算术检查已在明确范围内通过,指定跨模型讨论的状态在末节分别列出。

路线m(12) 下界相对同一基线 4633结论与证据范围
同一最大 RS 预算基线46330BRS(12)=4632;本文定义的最大接受整数预算
一般增长定理4635+2全部 k≥12 的统一定理;已端到端 Lean
直接优化结构 RS 判据 C.24647+14k=12 的严格局部数值;不是本次锁点法
合作者锁点法的新实例4661+28纸面归约+691429 个完整局部型的整数证书;尚未 Lean

统一方法提供无限参数范围和已完成的形式证明;锁点法在这一固定参数上给出更强数值。本表的 +2、+14、+28 使用同一个 k=12 基线;总览图现已统一采用已核参考下界的最大值:k=11 的共同基线为 2245,故其红线增益是 2275−2245=30,与本页 k=12 的 28 使用同一比较规则。此前相对 GL 公式 2213 的 62 保留在历史附表。这里没有据单次成功断言 k=6,…,11 都容易,也没有把有限实例外推成任意大的 k 都能同样推进。比较基线及 C.2 的原始数值见 k=12…16 数值报告,一般定理的证明见 完整 Lean 阅读页。

1. 对象、来源与结论

定义 1.1(Property B 与 m(k))。 有限简单 k 元超图是有限集合 V 及由不同 k 元子集组成的边集 E。若存在 c:V→{red,blue},使每条边同时含两色,则称其具有 Property B。m(k) 是不具有 Property B 的此类超图的最少边数。

来源说明。 下文的随机排列、条件概率公式、最轻坏对扣除、统一证书准则和一般选锁定理,来自合作者 《一般 k-uniform Property B 的锁点证书定理:k=10,11 的严格整数验证》 的定理 A、其“数学基础”全节以及定理 B。它们本来就对一般 k≥3 成立;不能将这套方法归为本次新发明。下文把完整公式和证明连接重述在同一阅读页。原作者 k=10,11 的实例不作为 k=12 的计算证据。

定理 1.2(本次实例,计算机辅助证明候选)。 任意有限简单 12 元超图,若边数至多 4660,则具有 Property B。因此

m(12)≥4661.

证明结构。 引理 2.1 将任意假定反例归到同一实际的点对覆盖、恰有 4660 条边、93≤v≤782 的超图。引理 3.1–3.4 给出真实失败概率的证书上界;引理 4.1–4.3 保证所用锁点及全部迹型。命题 5.2 的整数计算覆盖每个候选点数及每个必要参数型,并逐型严格小于统一分母。于是每个反例都具有成功概率为正的染色,矛盾。具体公式、覆盖和证书结果如下;本页的“候选”状态指新实例尚待指定验收,不将尚未完成的审阅写成通过。◻

2. 从原始超图到完整有限点数域

引理 2.1(最小反例与补边;合作者定理 A 的实例化)。 若存在至多 M=4660 边的有限简单 12 元不可染超图,则存在同一类型的反例 H,恰有 M 条边,每点对共边,且顶点数恰落在 93≤v≤782。

证明。 在全部至多 M 边的反例中取顶点数最小者。若两个不同点不共边,将它们合并;每条边仍含 12 个不同点,去重后边数不增。商图任何染色都可拉回原图,故商仍不可染,矛盾。因此任意点对共边。记 d(x) 为度数、λxy 为共度,则

11d(x)=∑y≠xλxy≥v−1,d0(v)=⌈v−111⌉,vd0(v)≤12M.

当 v≤22 时,将两色类都取成至多 11 点即可。其余点数使用均衡随机染色;每条边单色的概率为

pv,12=(⌊v/2⌋12)+(⌈v/2⌉12)(v12).

若 Mpv,12<1,并集界直接给可染。完整整数筛查 23≤v≤12M,同时保留 vd0(v)≤12M 与 Mpv,12≥1,所得域恰为 93,…,782;不是取样。尾部还有显式界

783⌈78211⌉=56376>55920=12M,

且左侧随 v 单调不减。又

(9312)=416579843773639>M.

可在原顶点集补入不同的 12 边直至恰有 M 条;不可染性和点对覆盖保留。以下所有度数、迹重数及坏对均取自这一补后同一个实际 H。◻

3. 条件排列与真实失败概率

定义 3.1(锁点和精确迹)。 取 s∈{0,1,2,3} 个不同实际顶点 x1,…,xs,固定在排列位置 t1<⋯<ts,其余 N=v−s 点在空位上均匀随机排列。对一条实际边 e,令其迹 T(e)={j:xj∈e}⊆[s],其重数为 ℓT,自由顶点数为 rT=k−|T|。对位置 h,令 ah,bh 为其严格左/右侧自由空位数,Ih−,Ih+ 为其严格左/右侧锁点标签集合。约定不满足组合条件的二项式为零。

引理 3.1(失败的实际单交见证;合作者定理 A)。 初始全红,按排列依次处理各点;仅当当前点是某条仍全红边的最后点时将它改蓝。最终没有全红边;若有全蓝边,则存在实际有序边对 (A,B),满足

A∩B={x},maxσA=minσB=x.

证明。 红边在其最后点处必被破坏。若最终有蓝边 B,取它排列中第一个顶点 x。x 改蓝时有一条仍全红的见证边 A,且 x 是 A 的最后点。若 A,B 另共享 y,由 A 得 y 早于 x,由 B 得 y 晚于 x,矛盾。◻

定义 3.2(精确有序单交权重)。 对固定的实际单交对、迹为 T,U,其见证点恰处于 h 的概率如下。若 h 自由,T⊆Ih−、U⊆Ih+,rT,rU≥1 且 rT+rU−1≤N,则

wh(T,U)=(ahrT−1)(bhrU−1)N(N−1rT−1)(N−rTrU−1).

若 h=tj,T∩U={j},T∖{j}⊆Ih−、U∖{j}⊆Ih+ 且 rT+rU≤N,则

wh(T,U)=(ahrT)(bhrU)(NrT)(N−rTrU).

其余情形为零。这些是依次无放回选择左右顶点集的联合计数,没有假设左右事件独立。

定义 3.3(单边端点概率)。 单边终点概率为

lasth(T)={rTN(ahrT−1)(N−1rT−1),h 自由, T⊆Ih−, rT≥1,(ahrT)(NrT),h=tj, j∈T, T∖{j}⊆Ih−,0,其他情形.

firsth(T) 将左右对调。置

Ah=∑TℓTlasth(T),Bh=∑TℓTfirsth(T),Ch=∑T,UℓT(ℓU−1T=U)wh(T,U).

引理 3.2(加权 link 扣除;合作者定理 A)。 在锁点 xj 的位置 h=tj,至少有

qj=⌈(k−1)d(xj)−(v−1)k−2⌉

个无序 incident 边对还共享中心以外的点。对都含 j 的类型 T,U,令容量和双向权重分别为

cap(T,U)={(ℓT2),T=U,ℓTℓU,T≠U,δh(T,U)=wh(T,U)+wh(U,T).

从全部类型对槽位按 δh 升序取最轻的 qj 个,按容量计重,和为 Dh;自由位置令 Dh=0。则真实失败概率满足

Pr(Fail)≤U:=∑h=1vmin{Ah,Bh,Ch−Dh}.

证明。 去掉中心后的 d=d(xj) 条 link 边是不同的 (k−1) 元集合,覆盖全部 v−1 点。令外点出现次数为 ry≥1。重复超额

Ej=(k−1)d−(v−1)=∑y(ry−1)≤∑y(ry2)

等于或小于所有 link 边对交集大小之和;每一非空交集至多 k−2 点。因此至少有 qj 个额外相交的无序对。这些对不能是真实单交见证。真实坏对在类型槽位中占据至少 qj 个位置,其权重和至少为最轻槽位和 Dh;零权槽位同样计入,不能跳过。Ch−Dh 因而仍是见证事件的并集上界。该事件也分别被“某边终止于 h”和“某边始于 h”覆盖,概率分别至多 Ah,Bh;可逐位置取三者最小值,再对 h 求和。扣除仅用于该锁点位置,没有跨位置重复收费。◻

引理 3.3(零锁的全局修正;合作者定理 A)。 点对覆盖时,至少有

Qv=max{0,⌈M(k2)−(v2)(k−12)⌉}

个无序多交边对,故有序单交对数至多 M(M−1)−2Qv。零锁计算将这一数量代入 Ch。

证明。 按顶点对或边对双计数,且 (λ2)≥λ−1,得

∑{A,B}(|A∩B|2)=∑{x,y}(λxy2)≥M(k2)−(v2).

不同简单边交集至多 k−1,每个多交对贡献至多 (k−12),从而得到 Qv。◻

4. 实际锁点存在与两型覆盖

引理 4.1(一锁及二锁;合作者定理 A)。 一锁可取全图最低度点,其度数满足

d0(v)≤d≤⌊kMv⌋.

若 sd=2(v−1)−(k−1)d>0,则存在与该点共度恰为 1、度数 e 满足 d≤e≤Bd 的第二点,其中

Bd=d+⌊kM−vdsd⌋.

一锁重数为 ℓ∅=M−d,ℓ{1}=d;二锁重数为

ℓ∅=M−d−e+1,ℓ{1}=d−1,ℓ{2}=e−1,ℓ{1,2}=1.

证明。 最低度不超过平均度。若与最低度点共度 1 的点有 n1 个,其余共度至少 2,故 (k−1)d≥2(v−1)−n1,即 n1≥sd。若这些点全度至少 Bd+1,总度至少 vd+sd(Bd+1−d)>kM,矛盾。重数由共度恰 1 和实际度数恢复。◻

引理 4.2(一般选锁定理;合作者定理 B)。 对任意点对覆盖的简单 k 元超图,令

D≥d0(v),Z=(D+1)v−kM,T=(k−1)(D+1)−v+2.

若整数 s≥2 满足

Z>0,4(k−1)Z>(s−1)T2,

则存在 s 个度数至多 D、两两共度恰为 1 的点。

证明。 令 L={x:d(x)≤D},r=|L|。由 Z>0 得 r>0,总度预算给 ∑x∈Ld(x)≤r(D+1)−Z。在 L 上按 λxy≥2 连辅助图 G;每点的这类邻点数至多 (k−1)d(x)−(v−1),故

2e(G)≤(T−1)r−(k−1)Z.

Caro–Wei 和 Cauchy–Schwarz 给

α(G)≥r2r+2e(G)≥r2Tr−(k−1)Z.

这里分母由前式至少为 r>0。又

r2−(s−1)(Tr−(k−1)Z)=(r−(s−1)T2)2+(s−1)(k−1)Z−(s−1)2T24>0.

所以 α(G)>s−1,有至少 s 个两两无辅助边的点;原点对覆盖保证其共度恰为 1。◻

引理 4.3(三锁迹型完备;合作者定理 A)。 对两两共度恰为 1 的三锁,恰有以下两种多点迹;度数排序为 d1≤d2≤d3 后,全部重数为

triple:ℓ123=1,ℓi=di−1,ℓ∅=M−d1−d2−d3+2;separate:ℓ12=ℓ13=ℓ23=1,ℓi=di−2,ℓ∅=M−d1−d2−d3+3.

未列的迹重数均为零。

证明。 若有一条边含三锁,则它已经使用全部三对的唯一共边,不再有二点迹。否则三个点对各由不同边承载,得到三个二点迹。其余单点迹与空迹由各点实际度数和总边数唯一确定;没有第三型。排序只是给实际点重新命名,并将其放到相应固定位置;不需要概率公式对三个位置对称。◻

定义 4.4(本次布局和完整枚举域)。 一锁位置为 ⌊v/2⌋;二锁为 ⌊v/2⌋,⌊v/2⌋+1;三锁为 ⌊v/2⌋−1,⌊v/2⌋,⌊v/2⌋+1。一锁枚举引理 4.1 的全部 d;二锁对每个这样的 d 验证 sd>0 并枚举全部 d≤e≤Bd。三锁取 d0≤D≤M 中使

Z=(D+1)v−12M>0,22Z>[11(D+1)−v+2]2

成立的最小整数 D,枚举全部 d0≤d1≤d2≤d3≤D 及两种迹型。此处没有原 helper 的 D≤d0+49 截断,也没有用“最小度配置最坏”的未经证明单调性代替枚举。必要域允许包含无实际超图实现的类型;关键是包含每个实际输入且全部类型都满足严格证书界。

5. 向外舍入、逐位置最小值与完整整数证书

引理 5.1(整数证书的方向)。 取 S=252=4503599627370496。对所有概率上界系数用 ⌈Sp⌉;对每一方向的坏对删除权重用 ⌊Sw⌋。具体置

A^h=∑TℓT⌈Slasth(T)⌉,B^h=∑TℓT⌈Sfirsth(T)⌉,

C^h=∑T,UℓT(ℓU−1T=U)⌈Swh(T,U)⌉.

把每个无序槽位赋权 ⌊Swh(T,U)⌋+⌊Swh(U,T)⌋,按这些已向下舍入的权重排序取最轻 qj 个,得到 D^h。自由位置为零。则

Pr(Fail)≤Ucert/S,Ucert=∑h=1vmin{A^h,B^h,C^h−D^h}.

证明。 每个上界项向上舍入。任何真实坏对集合的原权重不小于它自己的向下舍入权重,后者又不小于全部槽位中最轻的 qj 个的和。因此减去 D^h 仍保留上界,重新排序不会破坏方向。三个数各自都是同一实际位置失败事件的上界,故其最小值也是上界;最后求和。严格的 Ucert<S 就足以给出正的成功概率,不使用浮点近似。零锁按引理 3.3 修正后的对数向上舍入计算。◻

命题 5.2(k=12,M=4660 的完整计算)。 下表覆盖全部 690 个候选点数,全部 691429 个必要局部参数型。每个最终分子严格小于 S。

锁数点数 v完整型数最大 Ucert最大处S−maxUcert
093–5114194503308793007378v=511290834363118
1512–56429294503474369079970v=564,d=52125258290526
2565–648878074503473506514732v=648,(d,e)=(59,59)126120855764
3649–7826002744498353804903973v=782,(71,71,71),separate5245822466523

计算证据。 完整逐点数记录在 M4660.json,分段及计数在 SUMMARY.json,实际执行日志在 M4660.log。全部计算墙钟 86.712 秒、CPU 84.620 秒、峰值 RSS 42.8 MB。这是完整局部度数/迹型证书,不是整图枚举,也不是由几张抽样超图归纳。

NumPy 只做确切 signed int64 的非负乘加。所有最终使用的 271 张锁表均检查了安全界:M2Wmax 的全局最大值为 95038134995454400,MPmax 的全局最大值为 492840100122427600,均小于 263−1=9223372036854775807。坏对扣除受同一对数容量界约束,最终逐位置最小值的和由 Python 无界整数计算。两个完整运行 M=4647,4660 共七个分段最紧型,另经原 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 个必要参数型,无漏项或重复;其中二锁的 Bd 直接由严格整数不等式搜索,三锁的最小 D 在完整区间中重新搜索。另以独立 Python Fraction 公式复算 31 个型,覆盖各段最紧型、锁数交界两侧、度数上下端点及两种三锁迹型,精确值均不超过原证书上界且严格小于 1。零/一锁的全部 3348 型还由独立 1020 分母、Python 大整数实现完整重放,1.690 秒,全部严格小于 1。二/三锁尚未由第二实现全量重算概率;不能称 691429 型都完成双算术复核。该检查是 same-family / provisional,范围详见 independent/REPORT.md,不负责以计算证明选锁结构引理。Grok 初次数学讨论已有效返回(grok-4.7-build、xhigh、end_turn):一般选锁准则与概率计数可迁移至 k=12,并要求完整覆盖实际输入域。该次讨论的提示使用早期 M=4647 试算,未审阅最终 M=4660 全表,不能记为最终新实例已获跨家族终审。原始回应保留原文;其中关于补边的压缩说法以本页引理 2.1 的正确方向为准:原图不可染蕴含加边后不可染,加边后的染色限制为原图染色。原始迁移核查见 STRUCTURAL_TRANSFER.md,计算说明见 pilot/REPORT.md。迁移报告末尾在途描述是早于完整 M4660 结果的历史快照。

M=4670 的当前 driver 在 v=507 失败:零锁分子 4518736808473300>S,一锁 d=46 分子 4504066958865140>S;二锁必要度域含 d=92、此时 sd=0;全部 46≤D≤4670 中三锁的严格差最大仍为 −507442。这是“每个 v 统一选一个零/一/二/三锁模式”的当前策略未取得完整证书。按度数混合不同锁数的分流尚未测试;失败不是不可染反例,不是锁点法上限,本次不展开新的研究。

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

本页独立于一般增长主阅读页与已发布图;它展示一个新固定参数实例,不改写旧小参数实例的验收状态。

MathRSI · GitHub ↗