结果族 162：Counterexamples to Ryser’s covering conjecture · 学科：Combinatorics · 验证状态：主结果已 Lean 形式化
还是那个社团组队的游戏：每支小队从各部门各抽一人，任何两支小队必有共同成员，你想尽量少地挑人覆盖所有小队。Ryser 猜想同样断言”q 个人足够”。姊妹篇用素数阶构造给出反例，这篇论文另辟蹊径：在”扩域”（一层层套娃般的数系）里构造，同样把覆盖数顶到理论上限——而且这份证明已经通过 Lean 形式化的机器检验。
关键词卡片
@@M@@\tau\le r-1@@。@@M@@\mathbb{F}_q@@：只有有限多个数、加减乘除自成一体的数系；扩域 @@M@@\mathbb{F}_{s^n}@@ 像在小区上再盖高楼。@@M@@x\mapsto x^3@@；立方映射是否双射大有讲究。看个具体例子
公式卡（数字版定理）：取素数 @@M@@s=5@@（满足 @@M@@s\equiv 2\pmod 3@@）、充分大的奇数 n、令 @@M@@q=s^n@@，则存在相交的 @@M@@(q+1)@@-部 @@M@@(q+1)@@-一致超图，其覆盖数 @@M@@\tau=q+1@@——而 Ryser 猜想只允许 @@M@@\tau\le q@@。核心戏法是在小域 @@M@@\mathbb{F}_5@@ 上用 @@M@@x\mapsto x^3@@ 换坐标：因为 @@M@@\gcd(3,5-1)=1@@，立方映射是双射，同一批”被删的直线”在旧坐标下是直线、新坐标下变成与任何直线至多交三点的三次曲线。两套几何性质叠加，令任何省人的覆盖方案顾此失彼；n 取奇数则是为了不让中间层的子域”漏气”。
为什么值得关心
它与素数阶姊妹篇互相独立、覆盖不同的秩范围，共同宣判 Ryser 猜想（相交情形）失效，且本篇已获 Lean 形式化背书。
已 Lean 形式化
第一级台阶
入门导读沿用社团组队的比喻：部门、小队、挑人覆盖一切；本篇的新意是把舞台搬进”一层层套娃”般的扩域数系。半数学地说：对象仍是按部门分组的多方关系结构，操作仍是挑选尽量少的成员去碰到每支小队；与素数阶姊妹篇殊途同归，覆盖数在这里也被顶到理论上限。
第二级台阶
用本科术语精确化：顶点分 r 组、每条边恰含每组一元的超图是 r-部 r-一致超图；任何两边都相交时匹配数 @@M@@\nu=1@@，Ryser 猜想化为 @@M@@\tau\le r-1@@；有限域 @@M@@\mathbb{F}_q@@ 是只有有限多个元素却四则自洽的数系，扩域 @@M@@\mathbb{F}_{s^n}@@ 是在小域上再扩 n 层。当 @@M@@s\equiv2\pmod3@@ 时映射 @@M@@x\mapsto x^3@@ 可逆，坐标变换 @@M@@f(x,y)=(x^3,y)@@ 成为双射——这是全文的核心机关。
第三级台阶
定理陈述：对每个足够大的素数 @@M@@s\equiv2\pmod3@@ 与足够大的奇数 @@M@@n@@（令 @@M@@q=s^n@@），存在相交的 (q+1)-部 (q+1)-一致超图，覆盖数为 @@M@@q+1@@。模三条件挡住了立方映射不可逆、异常边不再相交的麻烦；奇数 @@M@@n@@ 挡住了中间子域过大的泄漏——真子域阶不超过 @@M@@q^{1/3}@@，和积方法的常数才保持一致。结论：相交情形的 Ryser 猜想在无穷多个秩上失效，Gyárfás 单色树覆盖猜想随之倒下，且主结果带有 Lean 形式化背书。
对每个足够大的素数 @@M@@s\equiv2\pmod3@@ 与足够大的奇数 @@M@@n@@（@@M@@q=s^n@@），本文构造出覆盖数为 @@M@@q+1@@ 的相交（intersecting）@@M@@(q+1)@@-部 @@M@@(q+1)@@-一致超图，推翻 Ryser 覆盖猜想的相交情形，并连带推翻 Gyárfás 单色树覆盖猜想。
Ryser 覆盖猜想称：@@M@@r@@-部 @@M@@r@@-一致超图（@@M@@r@@-partite @@M@@r@@-uniform hypergraph）满足 @@M@@\tau(H)\le(r-1)\nu(H)@@，@@M@@\tau@@ 为覆盖数（covering number），@@M@@\nu@@ 为匹配数。@@M@@r=2@@ 即 König 定理；Aharoni 证明三部情形。相交时 @@M@@\nu=1@@，猜想要求 @@M@@\tau\le r-1@@，此前验证到秩 5（Gyárfás 秩 4、Tuza 秩 5），任意两边恰交一点的线性情形验证到秩 9。截断射影平面在 @@M@@r-1@@ 为素数幂时取等 @@M@@\tau=r-1@@；Haxell–Scott 的一般下界为 @@M@@\tau\ge r-4@@。覆盖可从各部任取顶点，要把覆盖数推到最大值 @@M@@r@@，是长期未破的障碍。
定理：存在 @@M@@s_0@@，对每个素数 @@M@@s\ge s_0@@ 且 @@M@@s\equiv2\pmod3@@，存在 @@M@@n_0(s)\ge3@@，使得对每个奇数 @@M@@n\ge n_0(s)@@（令 @@M@@q=s^n@@），存在有限相交 @@M@@(q+1)@@-部 @@M@@(q+1)@@-一致超图 @@M@@H@@ 满足 @@M@@\tau(H)=q+1@@。任一条边本身就是覆盖，故 @@M@@\tau\le q+1@@ 平凡，定理取到极值。推论：在秩 @@M@@r=q+1@@ 上存在 @@M@@r@@-边染色完全图，覆盖其全部顶点需恰好 @@M@@r@@ 棵单色树（monochromatic tree），换成连通单色子图结论相同，故 Gyárfás 树覆盖猜想失败；文中还指出这同时反驳 Milićević 的有界直径强化与 DeBiasio–Kamel–McCourt–Sheats 猜想的 @@M@@\alpha=1@@ 情形。
先从仿射平面对偶出发：部为方向、顶点为直线标签、保留的点为边；但整条平行类永远是 @@M@@q@@ 条线的覆盖，故在保留大量普通边之外还需加入异常边（exceptional edges）。证明要办三件事：保持相交、限制普通边的小覆盖、让异常边对这些覆盖代价过高。
核心装置是”同一集合的两套坐标”。在小素域 @@M@@\mathbb{F}_s^2@@ 中，每个非零有限斜率方向各删一条直线得集合 @@M@@Y@@。因 @@M@@s\equiv2\pmod3@@ 时 @@M@@\gcd(3,s-1)=1@@，映射 @@M@@x\mapsto x^3@@ 可逆，坐标变换 @@M@@f(x,y)=(x^3,y)@@ 是双射；它保持水平、竖直两个平行类，把其余直线变成与任一直线至多交三点的三次曲线。于是同一批删除在新旧两套坐标下分别给出”每线至少五个 @@M@@Y@@ 点”与”每线至少 @@M@@s/8@@ 个 @@M@@f(Y)@@ 点”的存活性质。关键刚性（gadget 引理）：若 @@M@@a@@ 条直线与 @@M@@b@@ 个点以权重 @@M@@a+b/2\le s@@ 盖住 @@M@@f(Y)@@，则必 @@M@@a=s@@、@@M@@b=0@@，且这些线恰为一个完整平行类。其支柱是删点引理：在真子域阶均不超过 @@M@@q^{1/3}@@ 的域上，盖住几乎所有存活点的 @@M@@\le q@@ 条线中必有 @@M@@(1-\rho)q@@ 条过同一射影点（近似铅笔/pencil）；证明用到 Freedman 型鞅集中不等式与 Bourgain–Katz–Tao 和积方法（sum–product）的关联节省。
放置阶段把 @@M@@Y@@ 的线性变换副本嵌入 @@M@@\mathbb{F}_q^2@@，@@M@@n@@ 取奇数正是为保证真子域阶 @@M@@\le q^{1/3}@@；再用乘法陪集 @@M@@\lambda\mathbb{F}_s^*@@ 分配各副本负责改写的方向，使每个方向至多被两个副本改写；每组建 @@M@@K@@ 个独立随机平移的候选池，用 Haxell 式独立横截（independent transversal）选出互不冲突的副本，删除估计经确定性包含关系转移。
最后拼装超图：普通顶点是环境直线，异常边在其改写方向上换成经 @@M@@f@@ 读出的子域直线标签。相交性按四种点对分型验证，@@M@@f@@ 保持两条轴平行类是同组异常边相交的关键。排除 @@M@@\le q@@ 的覆盖时，先由删点引理逼出一支铅笔并迫使其中未删成员全部入选，再按铅笔中心分三种情形清账：中心在无穷远时，两组权重下界相加得 @@M@@2s\le2(s-1)@@，矛盾；中心落入某副本时，剩余预算会把 @@M@@f(Y)@@ 用至多 @@M@@s@@ 条线（含两条不平行的轴线）盖住，违反刚性；中心在所有副本之外时，过中心的每条删除线贡献五条盖不住的异常边，而每个额外顶点至多盖住五条，预算差一。三情形皆矛盾，故 @@M@@\tau\ge q+1@@，结合平凡上界得 @@M@@\tau=q+1@@。
据任务元数据与官方批注，本文主结果已有 Lean 形式化证明（见结果族 162 的 Lean 文档）。姊妹篇在素数阶构造出每部恰 @@M@@q+1@@ 个非孤立顶点的”平衡”反例，与本篇扩域阶构造相互独立、覆盖不同的秩范围，两篇互引的只有附录 A 的三条初等估计。按 OpenAI 官方声明，未经形式化的结果可能有问题；本篇主定理虽有形式化背书，概率构造细节仍宜对照形式化文档与同行评议。
问 1：证明中最关键、也最脆弱的一步是哪里？
答：删点引理——在真子域阶均不超过 @@M@@q^{1/3}@@ 的域上，盖住几乎所有存活点的至多 q 条线中必有 @@M@@(1-\rho)q@@ 条共点，形成近似铅笔。它依赖 Bourgain–Katz–Tao 和积方法的关联节省与 Freedman 型鞅集中不等式；铅笔提不出来，后面按中心分三情形清账的全部矛盾就都无从谈起。
问 2：@@M@@s\equiv2\pmod3@@ 这个条件为什么不能去掉？
答：它等价于 @@M@@\gcd(3,s-1)=1@@，从而 @@M@@x\mapsto x^3@@ 在小域上是双射，坐标变换 @@M@@f(x,y)=(x^3,y)@@ 才把直线变成与任何直线至多交三点的三次曲线、同时保持两条轴平行类——异常边组内相交正依赖后者。@@M@@s\equiv1\pmod3@@ 时立方映射三对一，机关失灵；论文未给该情形的替代构造。
问 3：奇数 @@M@@n@@ 是装饰还是必需？
答：必需。@@M@@q=s^n@@ 的真子域阶为 @@M@@s^d@@（@@M@@d@@ 为 @@M@@n@@ 的真因子），@@M@@n@@ 为奇数时最大真因子至多 @@M@@n/3@@，故真子域阶不超过 @@M@@q^{1/3}@@；若 @@M@@n@@ 为偶数会出现 @@M@@q^{1/2}@@ 阶的中间子域，和积与删点引理的一致常数不再适用。
问 4：与已有工作相比真正的新意是什么？
答：相对 Haxell–Scott 的 @@M@@\tau\ge r-4@@ 与 Abu-Khazneh 等的”加一部取等”，本篇在扩域阶把 @@M@@\tau@@ 直接顶到上限 @@M@@r@@；相对素数阶姊妹篇，新意在”一套集合、两套坐标”的机关——同一删除集在旧坐标下是直线结构、新坐标下是三次曲线结构，任何省人的覆盖顾此失彼。两篇构造相互独立，互引仅附录三条初等估计。
问 5：这类 AI 参与生成的证明最可能在哪里出错？
答：三情形清账的权重簿记：铅笔中心在无穷远、落在某个副本之内、或在所有副本之外，各有一套预算算术（@@M@@2s\le2(s-1)@@ 型矛盾、违反 @@M@@f(Y)@@ 的覆盖刚性、五条盖不住对五个可盖的差一）。分情形若有一处遗漏或权重算错，@@M@@\tau\ge q+1@@ 即告吹。主定理已有 Lean 形式化背书，但概率放置一节的细节仍宜对照形式化文档核验。
问 6：谁会用到它？
答：树覆盖理论首当其冲：推论不仅否定 Gyárfás 猜想，还反驳 Milićević 的有界直径强化与 DeBiasio–Kamel–McCourt–Sheats 猜想的 @@M@@\alpha=1@@ 情形；有限几何遮蔽集（blocking number）与超图覆盖社区也可引用其删点与独立横截引理。论文未讨论 @@M@@\nu>1@@ 的一般情形反例。
总评
与姊妹篇双管齐下宣判相交 Ryser 猜想死刑，本篇另享形式化背书，可信度为族内最高；剩余风险集中在概率放置与三情形清账两处，均属可局部核验的范围。