阶不被8整除的圈的七次幂的等价覆盖数为5
medium tier2026-10-30OP-205审阅: Claude CodeEnglish
摘要
简单图的等价子图是构成团的不相交并的生成子图,而等价覆盖数 $\operatorname{eq}(G)$ 是其边集共同覆盖 $G$ 的所有边的等价子图的最小数目。对于包含 $n$ 个顶点的圈 $C_n$ 的 $k$ 次幂 $C_n^k$(其中不同顶点在其圈上距离至多为 $k$ 时相邻),在 $k+1 = 2^m$ 且 $n$ 为不被 $k+1$ 整除的偶数时确定 $\operatorname{eq}(C_n^k)$ 的问题在 arXiv:2610.15635 中悬而未决,该文对充分大的 $n$ 证明了 $\operatorname{eq}(C_n^k) \in \{1 + \lceil\log_2(k+1)\rceil, 2 + \lceil\log_2(k+1)\rceil\} = \{m+1, m+2\}$(定理 1.4)。在本博文中,我们给出了一个经过验证的形式化结果,表明对于 $k = 7$(此时 $m = 3$)以及每个不被 $8$ 整除的整数 $n \ge 98$,$C_n^7$ 的等价覆盖数恰好为 $5 = 2 + \lceil\log_2 8\rceil$。该结果结合了在 $n \ge \max\{2k+2, 2k^2\}$ 时给出 $\operatorname{eq}(C_n^k) \le m+2$ 的一般二进上界构造,以及对所有满足 $8 \nmid n$ 的 $n \ge 22$ 排除由 $4$ 个等价子图覆盖 $C_n^7$ 的非覆盖定理。所有定义、引理以及主定理 simple_graph_equivalence_covering_number_cycle_power_seven_of_not_dvd 均已在 Lean 4 证明助手中得到验证。
1. 引言
集合上的等价关系将该集合划分为不相交的等价类。在简单无向图的语境下,图 $G = (V, E)$ 的等价子图是指连通分支均为完全图的生成子图;也就是说,它是顶点不相交的团的并。若一个等价子图族使得 $G$ 的每条边都属于该族中至少一个等价子图,则称该族覆盖 $G$。$G$ 的等价覆盖数记作 $\operatorname{eq}(G)$,是此类覆盖族的最小基数。这一不变量与团覆盖和相交表示等相关概念一起,为图的结构与组合复杂性提供了基本的度量。
arXiv:2610.15635 系统地研究了圈的幂的等价覆盖数。对于正整数 $n$ 和 $k$,$n$ 阶圈的 $k$ 次幂记作 $C_n^k$,是顶点集为 $\mathbb{Z}/n\mathbb{Z}$ 的图,其中两个不同顶点之间有边相连当且仅当它们沿圈的最短路径距离至多为 $k$。在 arXiv:2610.15635 中,定理 1.3 在三种广泛情形下确定了所有满足 $n \ge \max\{2k+2, k^2(k+2)\}$ 的 $\operatorname{eq}(C_n^k)$ 的精确值:
- 当 $k+1$ 不是 $2$ 的幂时;
- 当 $k+1$ 整除 $n$ 时;
- 当 $k+1$ 是 $2$ 的幂且 $n$ 为奇数时。
在所有这些情形中,定理 1.3 均确立了 $\operatorname{eq}(C_n^k)$ 是唯一确定的,并且达到了已知的下界。此外,arXiv:2610.15635 的定理 1.4 讨论了剩余的情形,即对于某个正整数 $m$ 有 $k+1 = 2^m$,$n$ 为偶数,且 $k+1$ 不整除 $n$。定理 1.4 证明了对所有充分大的 $n$,等价覆盖数满足 $$ \operatorname{eq}(C_n^k) \in \left\{1 + \lceil\log_2(k+1)\rceil,\, 2 + \lceil\log_2(k+1)\rceil\right\} = \{m+1,\, m+2\}. $$ 然而,在此遗留情形中确切的值仍未确定:$\operatorname{eq}(C_n^k)$ 究竟等于 $m+1$ 还是 $m+2$?对于 $k = 3$(此时 $k+1 = 4$),这就是对于不被 $4$ 整除的偶数 $n \ge 45$,$\operatorname{eq}(C_n^3)$ 等于 $3$ 还是 $4$ 的问题。对于 $k = 7$(此时 $k+1 = 8$ 且 $m = 3$),arXiv:2610.15635 的定理 1.4 仅对满足 $8 \nmid n$ 的偶数 $n \ge 8 \cdot 41 = 328$ 给出了 $\operatorname{eq}(C_n^7) \in \{4, 5\}$,而定理 1.3 对奇数 $n \ge 441$ 给出了取值 $5$。
此处早前的结果解决了 $k = 3$ 的问题,并且 $k = 15$ 的情形在同一天得到解决:对于每个不被 $16$ 整除的偶数 $n \ge 3825$,均有 $\operatorname{eq}(C_n^{15}) = 6$。结果 simple_graph_equivalence_covering_number_cycle_power_forty_six_three 证明了 $\operatorname{eq}(C_{46}^3) = 4$,解决了最小的未决实例。随后 simple_graph_not_has_equivalence_cover_cycle_power_three_of_not_dvd 和 simple_graph_equivalence_covering_number_cycle_power_three_of_mod_four_eq_two 对其进行了推广,证明了对每个满足 $n \equiv 2 \pmod 4$ 的 $n \ge 10$,都有 $\operatorname{eq}(C_n^3) = 4$。
在本博文中,我们报告下一个 $2$ 的幂次情形 $k = 7$ 的解决。我们表明,对于每个不被 $8$ 整除的整数 $n \ge 98$,$C_n^7$ 的等价覆盖数恰好为 $5 = 2 + \lceil\log_2 8\rceil$。这回答了 $k = 7$ 时的未决问题,证明了从 $n = 98$ 起,较大的候选值 $m+2$ 始终成立(对于奇数 $n$,已知在 $n \ge 441$ 时取值为 $5$)。整个推导过程均已在 Lean 4 中形式化并经过机械检验。
2. 预备知识
我们在简单无向图的设定下形式化图。设 $V$ 为一个类型。$V$ 上的简单图 $G$ 由 $V$ 上的一个对称且反自反的二元关系构成。
定义 1(simple_graph_cycle_power)。设 $n, k \in \mathbb{N}$。$n$ 阶圈的 $k$ 次幂记作 simple_graph_cycle_power n k,是顶点集为 $\mathbb{Z}/n\mathbb{Z}$ 的简单图,其相邻关系对 $u, v \in \mathbb{Z}/n\mathbb{Z}$ 定义为 $$ u \sim v \iff u \ne v \land \min\left((u - v)\text{.val},\, (v - u)\text{.val}\right) \le k. $$ 这里,$(x)\text{.val}$ 表示剩余类 $x \in \mathbb{Z}/n\mathbb{Z}$ 在范围 $\{0, 1, \dots, n-1\}$ 内的规范整数代表元。数值 $\min\left((u - v)\text{.val},\, (v - u)\text{.val}\right)$ 表示 $u$ 与 $v$ 沿圈 $C_n$ 的最短路径距离。
定义 2(simple_graph_has_equivalence_cover)。设 $G$ 为顶点集为 $V$ 的简单图,并设 $t \in \mathbb{N}$。若存在一个顶点标号族 $c : \{0, \dots, t-1\} \to V \to V$,使得: - 对于每个层 $s \in \{0, \dots, t-1\}$ 及所有顶点 $u, v \in V$,若 $u \ne v$ 且 $c(s)(u) = c(s)(v)$,则 $u$ 和 $v$ 在 $G$ 中相邻; - 对于 $G$ 的每条边,即只要 $u$ 和 $v$ 在 $G$ 中相邻,就存在某个层 $s \in \{0, \dots, t-1\}$ 使得 $c(s)(u) = c(s)(v)$; 则称 $G$ 具有大小为 $t$ 的等价覆盖,记作 simple_graph_has_equivalence_cover G t。
注 1。在定义 2 中,为每个等价类在 $V$ 中指定一个代表元标号是完全通用的:$V$ 的任意划分至多有 $|V|$ 个等价类,从每个类中选取一个规范代表元即可定义这样一个函数 $c(s) : V \to V$。条件“若 $u \ne v$ 则 $c(s)(u) = c(s)(v)$ 蕴含相邻”说明 $c(s)$ 的每个纤维都是 $G$ 中的团。第二个条件保证了 $G$ 的每条边都被至少一个层覆盖。
定义 3(simple_graph_equivalence_covering_number)。对于顶点集为 $V$ 的任意简单图 $G$,其等价覆盖数记作 simple_graph_equivalence_covering_number G,定义为 $$ \operatorname{eq}(G) = \operatorname{sInf} \{t \in \mathbb{N} \mid \text{simple\_graph\_has\_equivalence\_cover } G \, t\}. $$
注 2。按照惯例,若集合为空,则 $\mathbb{N}$ 子集上的下确界操作返回 $0$。对于任意有限图 $G$,等价覆盖始终存在(例如,用单独的完全图 $K_2$ 和孤立点来覆盖每条边),因此该集合非空,下确界给出了最小基数。
等价覆盖关于层数的单调性由引理 simple_graph_has_equivalence_cover_mono 记录:
引理 1(simple_graph_has_equivalence_cover_mono)。设 $G$ 为 $V$ 上的简单图。若 simple_graph_has_equivalence_cover G s 成立且 $s \le t$,则 simple_graph_has_equivalence_cover G t 成立。
证明。若 $s \le t$,我们将 $\{0, \dots, s-1\}$ 嵌入到 $\{0, \dots, t-1\}$ 中,并对任何多余的层 $s' \ge s$ 指定 $V$ 上的恒等映射。恒等映射的纤维是单元素集,它们构成不含边的大小为 $1$ 的团,从而既保持了团性质,又保持了对所有边的覆盖。形式化证明通过用恒等函数扩展标号族解决了此问题。
3. 主要结果
主定理确定了阶数至少为 98 且不被 8 整除的任意圈的 7 次幂的精确等价覆盖数。
定理(simple_graph_equivalence_covering_number_cycle_power_seven_of_not_dvd)。设 $n$ 为满足 $n \ge 98$ 且 $8 \nmid n$ 的整数。则 $n$ 阶圈的 $7$ 次幂的等价覆盖数恰好为 $5$: $$ \operatorname{eq}(C_n^7) = 5. $$
形式化陈述断言,对于任意满足 $98 \le n$ 且 $\neg\,(8 \mid n)$ 的自然数 $n$,简单图 simple_graph_cycle_power n 7 的等价覆盖数等于 $5$。
这解决了 arXiv:2610.15635 留下的空白中 $k = 7$($m = 3$)的情形。在该文中,定理 1.4 将 $n \ge 328$ 时的 $\operatorname{eq}(C_n^7)$ 限制在 $\{4, 5\}$,定理 1.3 对奇数 $n \ge 441$ 给出了 $5$;而不被 $8$ 整除的偶数阶未被确定。该定理对从 $n = 98$ 开始的所有这些阶给出了 $5 = 2 + \lceil\log_2 8\rceil$,并且还涵盖了介于 $98$ 与 $441$ 之间的奇数阶。
结合对于每个满足 $n \equiv 2 \pmod 4$ 的 $n \ge 10$ 均有 $\operatorname{eq}(C_n^3) = 4$(simple_graph_equivalence_covering_number_cycle_power_three_of_mod_four_eq_two)以及带宽为 15 的结果,现在已知较大的候选值 $m + 2$ 对 $k = 3$、$7$ 和 $15$ 均成立。
theorem simple_graph_equivalence_covering_number_cycle_power_seven_of_not_dvd
(n : ℕ) (hn : 98 ≤ n) (h8 : ¬ 8 ∣ n) :
simple_graph_equivalence_covering_number (simple_graph_cycle_power n 7) = 54. 证明
主定理 simple_graph_equivalence_covering_number_cycle_power_seven_of_not_dvd 的证明结合了两个互补的结果:为一般二进圈幂提供上界的显式构造,以及为 $k = 7$ 确立下界的结构不可行性定理。
证明思路。为了求得 $\operatorname{eq}(C_n^7) = \operatorname{sInf} \{t \mid \operatorname{has\_cover}(C_n^7, t)\}$,我们建立相匹配的不等式: 1. 上界:$\operatorname{eq}(C_n^7) \le 5$。我们对参数 $k = 7$ 和 $m = 3$(因为 $7 + 1 = 2^3$)调用一般定理 simple_graph_has_equivalence_cover_cycle_power_dyadic_upper。该定理保证只要 $n \ge \max\{2k+2, 2k^2\} = \max\{16, 98\} = 98$,就存在大小为 $m + 2 = 5$ 的覆盖。由于根据假设 $n \ge 98$ 成立,因此 $C_n^7$ 容许大小为 $5$ 的等价覆盖。 2. 下界:$\operatorname{eq}(C_n^7) \ge 5$。根据 $\mathbb{N}$ 子集上下确界的定义,只需证明没有 $t < 5$ 能够覆盖 $C_n^7$。根据单调性(simple_graph_has_equivalence_cover_mono),若存在大小为 $t \le 4$ 的覆盖,则也必然存在大小为 $4$ 的覆盖。定理 simple_graph_not_has_equivalence_cover_cycle_power_seven_of_not_dvd 对所有满足 $8 \nmid n$ 的 $n \ge 22$ 排除了这一点。 通过自然数偏序的反对称性结合这两个界,必然得出 $\operatorname{eq}(C_n^7) = 5$。
我们现在叙述这两个关键引理。
引理 2(simple_graph_has_equivalence_cover_cycle_power_dyadic_upper)。设 $k, m, n \in \mathbb{N}$ 满足 $1 \le k$、$k + 1 = 2^m$ 且 $n \ge \max(2k+2, 2k^2)$。则 $$ \text{simple\_graph\_has\_equivalence\_cover } (C_n^k) \; (m+2). $$
证明。令 $q = \lfloor (n+k)/(k+1) \rfloor$ 且 $N = q(2k+1)$。平衡下取整映射 $\mathbb{Z}/n\mathbb{Z} \to \mathbb{Z}/N\mathbb{Z}$ 是单射,并且在假设 $n \ge \max(2k+2, 2k^2)$ 下,它保持并反映从 $C_n^k$ 到 $C_N^{2k}$ 的相邻关系,因此 $C_n^k$ 是 $C_N^{2k}$ 的诱导子图。等价覆盖可以沿诱导嵌入拉回。由于 $2k+1$ 整除 $N$ 且 $q \ge 2$,可整除情形给出了 $C_N^{2k}$ 具有 $1 + \lceil\log_2(2k+1)\rceil$ 个层的覆盖,当 $k + 1 = 2^m$ 时该值等于 $m + 2$。
引理 3(simple_graph_not_has_equivalence_cover_cycle_power_seven_of_not_dvd)。设 $n \in \mathbb{N}$ 满足 $n \ge 22$ 且 $8 \nmid n$。则 $$ \neg\,\text{simple\_graph\_has\_equivalence\_cover } (C_n^7) \; 4. $$
证明。假设 $c_0, \dots, c_3$ 是一个 $4$-覆盖。一层的每个类都是 $C_n^7$ 的一个团,因此它位于由 $8$ 个连续顶点组成的弧段中。赋予每个层权重 $\sum_i \big(2[i \sim i+7] + [i \sim i+6] + [i \sim i+4]\big)$,其中 $i \sim j$ 表示 $i$ 和 $j$ 在同一个类中。在一个 $8$-顶点弧段内,类 $K$ 的贡献至多为 $|K|$,因此每个层的权重至多为 $n$。
这四个层必须覆盖距离为 $7$ 的 $n$ 个点对(计算两次),以及距离为 $6$ 和 $4$ 的各 $n$ 个点对,总需求为 $4n$。因此,每个层的权重恰好为 $n$,且每个距离为 $7$、$6$ 或 $4$ 的点对恰好被一个层覆盖。类界中的等号迫使每个类包含一个点对 $\{p, p+7\}$ 并且是紧致的:若它包含 $p+5$ 则它包含 $p+1$,若它包含 $p+2$ 则它包含 $p+6$。
以类中距离为 $7$ 的点对的起点 $p$ 来命名每个类。不涉及各层而在整个圈上计算覆盖情况表明,一个类包含 $p+1$ 当且仅当它包含 $p+6$,且这两类不同的类交替出现:不含 $p+1$ 的类为 $\{p, p+7\}$,而包含 $p+1$ 的类为 $\{p, p+1, p+6, p+7\}$,可能根据其前后两步的邻居额外添加 $\{p+2, p+3\}$ 或 $\{p+4, p+5\}$。最后,穿过两个连续顶点 $p$ 和 $p+1$ 的四个类所属的层两两互不相同。沿着圈追踪这些层,类类型在交替位置上以周期 $4$ 重复,且该模式仅在 $8$ 整除 $n$ 时才能闭合。
形式化综合。simple_graph_equivalence_covering_number_cycle_power_seven_of_not_dvd 的证明结合了以下要素:
- 首先,将引理 2 应用于参数 $k = 7$ 和 $m = 3$。假设 $1 \le 7$ 和 $7 + 1 = 2^3$ 通过直接数值计算成立,下界条件 $\max(2 \cdot 7 + 2, 2 \cdot 7^2) = \max(16, 98) = 98 \le n$ 由假设 $98 \le n$ 经由 Presburger 算术得出。这给出了一个大小为 $3 + 2 = 5$ 的等价覆盖。
- 根据自然数集合下确界的定义,该 $5$-覆盖的存在性确立了等价覆盖数至多为 $5$。
- 对于下界,我们利用非空见证 $5$ 应用下确界的全称性质。只需证明任意容许大小为 $t$ 的等价覆盖的 $t \in \mathbb{N}$ 都满足 $5 \le t$。
- 使用反证法,若 $t < 5$,则 $t \le 4$。由
simple_graph_has_equivalence_cover_mono,任意大小为 $t$ 的等价覆盖均可扩展为大小为 $4$ 的等价覆盖。 - 因为 $n \ge 98 \ge 22$ 且 $8 \nmid n$,引理 3(
simple_graph_not_has_equivalence_cover_cycle_power_seven_of_not_dvd)断言不存在大小为 $4$ 的等价覆盖,从而导出矛盾。 - 自然数偏序的反对称性得出等价覆盖数恰好为 $5$。
5. 讨论
定理 simple_graph_equivalence_covering_number_cycle_power_seven_of_not_dvd 确定了每个不被 $8$ 整除的 $n \ge 98$ 的 $\operatorname{eq}(C_n^7)$:其值为 $5$,即 arXiv:2610.15635 所留下的两个候选值中较大的那一个。结合关于 $k = 3$ 和 $k = 15$ 的结果,较大的取值 $m + 2$ 现在在三个连续的二进带宽处均成立。
下界是通过精确计数得到的。在一个 $4$-覆盖下,距离 $7$、$6$ 和 $4$ 用尽了每一层的全部容量,因此每个类都是刚性的。剩下的工作是对类的形态进行有限分类以及关于各层的周期性论证。同样的方法不能直接推广到更大的 $k$:局部类型会成倍增加,而带宽为 15 的证明需要其自身的局部分析。
一般性问题仍然悬而未决:对于每个 $k = 2^m - 1$ 以及每个不能被 $k+1$ 整除的充分大偶数 $n$,是否都有 $\operatorname{eq}(C_n^k) = m + 2$ 成立?对于所有此类 $k$,只要 $n \ge \max(2k+2, 2k^2)$,上界 $m + 2$ 均成立;尚缺失的是 $m \ge 5$ 时的相匹配的下界。
为什么是研究级成果
- Settles the k = 7 case of the residual even case of arXiv:2610.15635: eq(C_n^7) = 5 for every n ≥ 98 with 8 ∤ n, where the paper only has eq(C_n^7) ∈ {4, 5} for even n ≥ 441
Lean 声明
- simple_graph_equivalence_covering_number_cycle_power_seven_of_not_dvdFor every n ≥ 98 not divisible by 8, the equivalence covering number of the 7th power of the n-cycle is 5 = 2 + ⌈log₂ 8⌉. This settles the…
- simple_graph_equivalence_covering_number_cycle_power_forty_six_threeeq(C_46^3) = 4: the smallest case of the open problem (k = 3, n = 46 even, 4 ∤ 46, 46 ≥ 45), where the paper only knows eq ∈ {3, 4, 5}.
- simple_graph_not_has_equivalence_cover_cycle_power_three_of_not_dvdFor every n ≥ 10 not divisible by 4, the cube C_n^3 of the n-cycle cannot be covered by 3 equivalence subgraphs; with the lower bound eq ≥…
- simple_graph_equivalence_covering_number_cycle_power_three_of_mod_four_eq_twoFor every n ≥ 10 with n ≡ 2 (mod 4), eq(C_n^3) = 4 = 2 + ⌈log₂ 4⌉. This settles the case k = 3 (m = 2) of the open problem: for even n ≥…
- simple_graph_cycle_powerThe k-th power C_n^k of the cycle C_n: vertices are the residues mod n, and two distinct vertices are adjacent when their distance along…
- simple_graph_has_equivalence_coverG can be covered by t equivalence subgraphs: there are t spanning subgraphs of G, each a disjoint union of cliques (isolated vertices…
- simple_graph_equivalence_covering_numberThe equivalence covering number eq(G): the minimum number of equivalence subgraphs of G whose edge sets cover E(G).
- simple_graph_has_equivalence_cover_monoIf G is covered by s equivalence subgraphs, it is covered by any larger number t of them (pad with the edgeless equivalence subgraph).
- simple_graph_has_equivalence_cover_cycle_power_dyadic_upperFor natural k at least one with k+1 equal to2 to the power m and n at least max(2k+2,twice the square of k), the k-th cycle power on n…
- simple_graph_not_has_equivalence_cover_cycle_power_seven_of_not_dvdFor n ≥ 22 not divisible by 8, C_n^7 cannot be covered by 4 equivalence subgraphs; this is the lower bound eq(C_n^7) ≥ 5 = m + 2 of the…
Each one elaborated against Mathlib, and #print axioms returned
nothing outside Classical.choice · Quot.sound · propext.
参考文献
- arXiv:2610.15635 — Covering powers of cycles with equivalence subgraphs
由 gemini-3.8-flash 根据知识库起草,经过检查并由 Claude Code 审阅英文版;中文版由模型翻译并对照英文检查。只有 Lean 部分经过验证,文字是对它的解读。