AFTD Auto-Formalizing Theoretical Domains

Research Blogs

对所有不能被16整除的大偶数圈长,15次圈图幂的等价覆盖数均为6

medium tier2026-10-30OP-205审阅: Claude CodeEnglish

摘要

对于圈图 $C_n$ 的 $k$ 次幂 $C_n^k$,等价子图是团的不交并,而 $\operatorname{eq}(C_n^k)$ 表示覆盖 $C_n^k$ 的所有边所需的等价子图的最小数目。虽然当 $k+1$ 不是 $2$ 的幂、当 $k+1$ 整除 $n$ 或当 $n$ 为奇数时 $\operatorname{eq}(C_n^k)$ 是已知的,但在 $k+1 = 2^m$、$n$ 为偶数且 $2^m$ 不整除 $n$ 的剩余情形在 arXiv:2610.15635 中仍未解决,该文仅建立了双值界 $\operatorname{eq}(C_n^k) \in \{m+1, m+2\}$。我们确定了带宽 $k = 15$($m = 4$)时的精确等价覆盖数:对每个不能被 $16$ 整除且满足 $n \ge 3825 = 15^2 \cdot 17$ 的偶数 $n$,均有 $\operatorname{eq}(C_n^{15}) = 6 = 2 + \lceil\log_2 16\rceil$。该证明应用了一个二进归约定理,该定理表明在该问题的数值假设下,只要每个紧致的、精确二进覆盖的、完全普通覆盖的、每个顶点有 $m+1$ 个活跃类的整数布尔类模型中,各类均为初始区间与末尾区间的并(无选定孤岛),则等价覆盖数就不可能为 $m+1$。我们给出了 $m = 4$ 时的这一无孤岛结构性质,从而排除了较小的候选值 $5$ 并确立了精确值。所有定义、引理和主定理均已在 Lean 4 中形式化并得到检验。

1. 引言

简单图 $G = (V, E)$ 的等价子图是连通分支均为完全图的子图;等价地,它是 $V$ 的子集上的等价关系的图。$G$ 的等价覆盖数记作 $\operatorname{eq}(G)$,是其边集共同覆盖 $E(G)$ 的等价子图的最小数目。用等价子图覆盖图是图论中的经典课题,与偏序维数、相交图论以及网络分解有密切联系。

在此背景下一个自然且被广泛研究的图族是圈图的幂。对于整数 $n \ge 3$ 和 $k \ge 1$,$n$-圈的 $k$ 次幂记作 $C_n^k$,其顶点集为 $\mathbb{Z}/n\mathbb{Z}$,两个不同顶点相邻当且仅当它们沿 $C_n$ 的圈最短路径距离至多为 $k$。在 arXiv:2610.15635 中,针对大圈长 $n$ 系统地研究了等价覆盖数 $\operatorname{eq}(C_n^k)$。具体而言,arXiv:2610.15635 的定理 1.3 完全确定了在三种广泛情形下所有阶数 $n \ge \max\{2k+2, k^2(k+2)\}$ 的 $\operatorname{eq}(C_n^k)$ 的精确值:

  1. 当 $k+1$ 不是 $2$ 的幂时;
  2. 当 $k+1$ 整除 $n$ 时;
  3. 当 $k+1$ 是 $2$ 的幂且 $n$ 为奇数时。

然而,当 $k+1$ 是 $2$ 的幂、$n$ 为偶数且 $k+1$ 不整除 $n$ 时,定理 1.3 并不适用。在这一剩余情形下,记 $k+1 = 2^m$(其中 $m \ge 1$),arXiv:2610.15635 的定理 1.4 表明对所有充分大的 $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\}.$$ 对于所有 $m \ge 2$ 的二进带宽 $k = 2^m - 1$,真实的等价覆盖数究竟达到下界 $m+1$ 还是上界 $m+2$,在 arXiv:2610.15635 中仍未解决。

对于对应于带宽 $k = 3$($k+1 = 4$)的二进指数 $m = 2$,早期的形式化工作已经解决了该问题:对每个不能被 $4$ 整除的 $n \ge 10$ 验证了下界 $\operatorname{eq}(C_n^3) \ge 4$(simple_graph_not_has_equivalence_cover_cycle_power_three_of_not_dvd),从而对所有满足 $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),并解决了 $\operatorname{eq}(C_{46}^3) = 4$ 的极小实例 $n = 46$(simple_graph_equivalence_covering_number_cycle_power_forty_six_three)。

对于超过 $k = 3$ 的二进带宽,精确值一直悬而未决。对于 $k = 15$,即 $m = 4$ 且 $k+1 = 16$ 的情形,arXiv:2610.15635 的界对不能被 $16$ 整除的偶数 $n$ 仅给出 $\operatorname{eq}(C_n^{15}) \in \{5, 6\}$。在本帖中,我们报告在 Lean 4 中关于 simple_graph_equivalence_covering_number_cycle_power_fifteen_of_not_dvd 中 $k = 15$ 的精确等价覆盖数的形式化验证: $$\operatorname{eq}(C_n^{15}) = 6$$ 对每个满足 $16 \nmid n$ 的偶数 $n \ge 3825$ 均成立。这里的阶数界 $3825 = 15^2 \cdot 17$ 恰好对应于 arXiv:2610.15635 定理 1.3 中出现的阈值 $k^2(k+2) = \max\{2k+2, k^2(k+2)\}$。该结果确立了在此无限图族中始终成立上界备选项 $m+2 = 6$,排除了由 $5$ 个子图构成的等价覆盖。

2. 预备知识

我们介绍 Lean 4 形式化中使用的形式定义与约定。在全文中,$\mathbb{N}$ 表示非负整数 $\{0, 1, 2, \dots\}$,$\mathbb{Z}$ 表示整数。对于正整数 $n$,商 $\mathbb{Z}/n\mathbb{Z}$ 表示模 $n$ 整数环,具有来自整数的标准强制转换(coercion)以及在 $\{0, 1, \dots, n-1\}$ 中的典范代表元。

定义 1(圈图幂)。设 $n$ 和 $k$ 为非负整数。$n$-圈的 $k$ 次幂在形式化中表示为 simple_graph_cycle_power,是顶点集为 $\mathbb{Z}/n\mathbb{Z}$ 的简单图 $C_n^k$,其邻接关系定义为: $$u \sim v \iff u \ne v \land \min((u - v).\operatorname{val}, (v - u).\operatorname{val}) \le k.$$ 这里 $(u - v).\operatorname{val}$ 和 $(v - u).\operatorname{val}$ 表示沿圈在 $u$ 与 $v$ 之间的两个有向路径距离,它们的最小值是最短路径距离。根据定义,该图无自环且无向。

定义 2(等价子图与覆盖数)。设 $G = (V, E)$ 为简单图。$G$ 的等价子图是指连通分支均为完全图的子图;也就是说,活跃顶点上的邻接关系构成等价关系。大小为 $t$ 的 $G$ 的等价覆盖是指 $G$ 的 $t$ 个等价子图的族 $H_1, \dots, H_t$,使得 $\bigcup_{i=1}^t E(H_i) = E(G)$。 $G$ 的等价覆盖数在形式化中表示为 simple_graph_equivalence_covering_number,定义为: $$\operatorname{eq}(G) = \inf \{t \in \mathbb{N} \mid G \text{ has an equivalence cover of size } t\}.$$ 在 Lean 中,该下确界是利用自然数上的条件完备格下确界算子在覆盖大小的集合上取的。当不存在覆盖时(对于有限图不会发生),根据 $\mathbb{N}$ 中空集的下确界为 $0$ 的约定,该下确界计算结果为 $0$。

定义 3(二进类权重)。设 $m \in \mathbb{N}$ 为二进指数,并设 $b : \mathbb{N} \to \operatorname{Bool}$ 为偏移量 $\{0, 1, \dots, 2^m - 1\}$ 上的布尔轮廓。$b$ 的二进类权重在形式化中表示为 cycle_power_dyadic_class_weight,定义为: $$\operatorname{weight}_m(b) = 2 \cdot [b(0) \land b(2^m - 1)] + \sum_{j=1}^{m-1} \sum_{i=0}^{2^j - 1} [b(i) \land b(i + 2^m - 2^j)],$$ 其中 $[P]$ 表示整数示性函数:若 $P = \operatorname{true}$ 则为 $1$,若 $P = \operatorname{false}$ 则为 $0$。

定义 4(整数布尔类模型)。整数布尔类模型是一个函数 $x : \mathbb{Z} \to \mathbb{N} \to \operatorname{Bool}$,其中 $x(p)(a)$ 表示以位置 $p \in \mathbb{Z}$ 为根的等价类是否包含偏移量 $a \in \mathbb{N}$ 处的顶点(即格点位置 $p + a$)。对于固定的指数 $m$,我们考虑偏移量 $a \in \{0, 1, \dots, 2^m - 1\}$。 模型 $x$ 满足四个性质: 1. 紧致性:对每个 $p \in \mathbb{Z}$,其二进类权重等于该类中活跃偏移量的总数: $$\operatorname{weight}_m(x(p)) = \sum_{a=0}^{2^m - 1} [x(p)(a)].$$ 2. 精确二进覆盖:对每个尺度指标 $j \in \{0, 1, \dots, m-1\}$ 和每个格点位置 $v \in \mathbb{Z}$,恰有一个活跃类覆盖始于 $v$ 且距离为 $2^m - 2^j$ 的二进对: $$\sum_{a=0}^{2^j - 1} [x(v - a)(a) \land x(v - a)(a + 2^m - 2^j)] = 1.$$ 3. 完全普通覆盖:对每个满足 $1 \le d < 2^m$ 的普通距离 $d$ 以及每个位置 $v \in \mathbb{Z}$,均存在偏移量 $a < 2^m - d$ 使得 $x(v - a)(a) = \operatorname{true}$ 且 $x(v - a)(a + d) = \operatorname{true}$。 4. 精确活跃类数目:对每个位置 $v \in \mathbb{Z}$,覆盖 $v$ 的类的总数恰为 $m + 1$: $$\sum_{a=0}^{2^m - 1} [x(v - a)(a)] = m + 1.$$

定义 5(无孤岛性质)。若 $\{0, \dots, 2^m - 1\}$ 上的布尔轮廓 $b : \mathbb{N} \to \operatorname{Bool}$ 在经历一次先 false 后 true 的跃迁之后的所有偏移量均保持为 true,则称其无选定孤岛;形式化地,对所有满足 $a < b < c < 2^m$ 的偏移量 $a, b, c \in \mathbb{N}$: $$b(a) = \operatorname{false} \land b(b) = \operatorname{true} \implies b(c) = \operatorname{true}.$$ 等价地,这排除了模式 $\operatorname{false} \dots \operatorname{true} \dots \operatorname{false}$,意味着每个类均由一个初始区间与一个末尾区间组成(非活跃偏移量可能构成中间区间)。若对每个根 $p \in \mathbb{Z}$,轮廓 $x(p)$ 都具有此结构(即每个类都是初始区间与末尾区间的并),则称整数布尔类模型 $x$ 具有无孤岛性质。

关于形式化约定的注记。 在定义 3 中,Lean 定义 cycle_power_dyadic_class_weight 通过对 $j = 0$ 的显式警戒条件将对 $j \in \{0, \dots, m-1\}$ 的求和进行拆分,把距离为 $2^m - 1$ 的端点对置于权重为 $2$ 的首项中。在定义 1 中,图 $C_n^k$ 连接圈距离至多为 $k$ 的不同顶点,因此当且仅当最短圈路径长度至多为 $k$ 时,不同顶点 $u, v$ 之间存在一条边。在定义 4 中,格点 $v$ 和根 $p$ 取遍整数 $\mathbb{Z}$,表示 $\mathbb{Z}/n\mathbb{Z}$ 上的圆周覆盖问题的周期性展开。

3. 主要结果

定理(simple_graph_equivalence_covering_number_cycle_power_fifteen_of_not_dvd)。 设 $n$ 为偶数,满足 $n \ge 3825$ 且 $16$ 不整除 $n$。则 $n$-圈的 15 次幂的等价覆盖数为 $$\operatorname{eq}(C_n^{15}) = 6.$$

在 Lean 中,定理 simple_graph_equivalence_covering_number_cycle_power_fifteen_of_not_dvd 表述为:对于整数 $n$,在假定 $3825 \le n$、$n$ 为偶数且 $16$ 不整除 $n$ 的前提下,由 simple_graph_equivalence_covering_number 计算的参数为 $n$ 和 $15$ 的 simple_graph_cycle_power 的等价覆盖数等于 $6$。

背景与该结果的新增内容: 1. 解决指数 4 处的剩余二进情形。 arXiv:2610.15635 的定理 1.4 确立了对于 $k = 15$ 以及充分大且不能被 $16$ 整除的偶数 $n$,覆盖数 $\operatorname{eq}(C_n^{15})$ 为 $5$ 或 $6$。本主定理排除了较小的值 $5$,并表明上界值 $6 = 2 + \lceil\log_2 16\rceil$ 对所有满足 $16 \nmid n$ 的偶数 $n \ge 3825$ 无条件成立。

2. $n$ 的范围。 阈值 $3825 = 15^2 \cdot 17 = k^2(k+2)$ 正是未决情形本身的假设:对于 $k = 15$,$\max\{2k+2, k^2(k+2)\} = \max\{32, 3825\} = 3825$。该定理涵盖了该范围内满足 $16 \nmid n$ 的每一个偶数 $n$。

3. 超越指数 2 情形的进展。 此前,在剩余偶数情形中的精确覆盖数仅对 $k = 3$($m = 2$)已知,其中对所有满足 $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),并解决了特定极小阶数 $n = 46$ 的情形(simple_graph_equivalence_covering_number_cycle_power_forty_six_three)。本主定理给出了 $k = 15$($m = 4$)时的精确确定,解决了这一无限图族。

定理 simple_graph_equivalence_covering_number_cycle_power_fifteen_of_not_dvd (Lean 4 已验证)
theorem simple_graph_equivalence_covering_number_cycle_power_fifteen_of_not_dvd
    (n : ℕ) (hn : 3825 ≤ n) (hev : Even n) (hnd : ¬ 16 ∣ n) :
    simple_graph_equivalence_covering_number (simple_graph_cycle_power n 15) = 6

4. 证明

该证明表明 $C_n^{15}$ 不存在由 $5$ 个等价子图构成的等价覆盖,且存在一个由 $6$ 个等价子图构成的覆盖。证明分为两部分:一部分是针对一般的 $k = 2^m - 1$ 证明的归约,它归结为局部模型上的单一结构假设;另一部分是针对 $m = 4$ 证明该假设。

第 1 部分:归约。 引理 1(simple_graph_equivalence_covering_number_cycle_power_dyadic_of_class_shape)。设 $k + 1 = 2^m$(其中 $m \ge 1$),$n \ge \max\{2k+2, k^2(k+2)\}$ 为偶数,且 $k + 1 \nmid n$。假设指数 $m$ 处的每个整数布尔类模型(定义 4:紧致、具有精确二进覆盖、完全普通覆盖且穿过每个位置恰有 $m+1$ 个类)均无孤岛(定义 5)。则 $\operatorname{eq}(C_n^k) = m + 2$。

上界 $\operatorname{eq}(C_n^k) \le m+2$ 来自一个由 $m+2$ 个等价子图构成的显式覆盖,该覆盖在同一工作中对所有 $n \ge \max\{2k+2, 2k^2\}$ 均已形式化。对于下界,Lean 中的证明从由 $m+1$ 个等价子图构成的覆盖出发并建立一个周期性模型。处于最大距离 $k$ 处的每个对 $(p, p+k)$ 恰好位于恰好一个子图的恰好一个团中。设 $x(p)(a)$ 记录该团是否包含 $p + a$,并设 $\ell(p)$ 为其子图的指标。一个权重不等式迫使各处取等号:每个团的二进权重(定义 3)至多为其大小,且各权重之和等于 $n(m+1)$。等号给出了紧致性、二进距离 $2^m - 2^j$ 的精确覆盖、穿过每个位置恰有 $m + 1$ 个类,以及对每个普通距离的覆盖。交于某个公共位置且具有相同标签的两个类是同一个团。

在无孤岛假设下,在以 $p$ 为根的类的最后一个顶点 $p + 2^m - 1$ 处活跃的每一个其他类,都与以 $p + 2^m$ 为根的类相交。由于同一位置处的活跃类带有互不相同的标签,因此这些标签具有周期 $2^m$。在二进距离及其邻近距离 $2^m - 2^j \pm 1$ 上的平均不等式表明,某个类包含偏移量 $2^{m-1} - 1$ 或 $2^{m-1}$。这迫使相距 $2^{m-1}$ 的两个标签不同。具有周期 $n$ 与 $2^m$ 且具有两个此类标签的标签序列,利用最大公约数(gcd)论证可得出 $2^m \mid n$,这与 $k+1 \nmid n$ 矛盾。

第 2 部分:$m = 4$ 时无孤岛。 引理 2(cycle_power_fifteen_model_no_island)正是引理 1 在 $m = 4$ 时所假定形式的假设。在穿过每个位置有 $5$ 个类的紧致模型中,距离 $15$ 处的精确方程使得每个类都包含两个端点 $p$ 和 $p + 15$。紧致性进而表明每个类在偏移量 $1, \dots, 14$ 上的一个固定父映射下是封闭的:$2 \to 14$,$4 \to 12$,$5 \to 13$,$6 \to 14$,$9 \to 1$,$10 \to 2$,$11 \to 3$,$13 \to 1$(偏移量 $1, 3, 7$ 指向 $15$,而 $8, 12, 14$ 指向 $0$)。每个位置恰好是 $3$ 个类的内部元素(偏移量 $1$ 至 $14$)。距离为 $14$、$12$ 或 $8$ 的每个对都恰好被覆盖一次,且距离至多为 $15$ 的每一个其他对均被覆盖。

同一工作中的两个较早引理表明,在此模型中,每个类包含偏移量 $1$ 当且仅当它包含偏移量 $14$,且包含偏移量 $2$ 当且仅当它包含偏移量 $3$。这两个引理均通过在根的窗口 $[-32, 32]$ 上反驳以 $0$ 为根的类的不匹配来证明。新的步骤是以 $0$ 为根的类的九条单调性规则: $$x_4 \Rightarrow x_3,\quad x_5 \Rightarrow x_4,\quad x_6 \Rightarrow x_5,\quad x_7 \Rightarrow x_6,$$ $$x_8 \Rightarrow x_9,\quad x_9 \Rightarrow x_{10},\quad x_{10} \Rightarrow x_{11},\quad x_{11} \Rightarrow x_{12},\quad x_{12} \Rightarrow x_{13}.$$ 每条规则都是仅利用根的窗口 $[-24, 24]$ 上的约束,并将上述两个配对作为额外假设,通过反驳其违反而证明的。大多数比特由线性约束的单子句传播迫出,每一步都由 Lean 的整数算术判定过程检验。少数情况需要对一个比特进行分支。每个叶节点都通过至多 $45$ 个约束的线性组合封闭,并由 Lean 的线性算术策略检验。配对使每次反驳保持较小:情况树中至多只有五个节点。

父映射和配对提供了缺失的步骤。规则 $x_2 \Rightarrow x_1$ 成立是因为 $2 \to 14$ 且 $x_{14} = x_1$,而 $x_3 \Rightarrow x_2$ 即为配对。在另一侧,$x_{13} \Rightarrow x_{14}$ 成立是因为 $13 \to 1$ 且 $x_1 = x_{14}$;偏移量 $15$ 总是存在。因此对 $0 \le i \le 6$ 有 $x_{i+1} \Rightarrow x_i$,对 $8 \le i \le 14$ 有 $x_i \Rightarrow x_{i+1}$。由归纳法,该类在偏移量 $0, \dots, 7$ 中的部分是一个初始段,在 $8, \dots, 15$ 中的部分是一个末尾段,因此它没有孤岛。平移该模型可将任意根移动到 $0$,从而对每个根都给出了该性质。

有限搜索(不属于证明的一部分)证实了这一图像。在窗口 $[-24, 24]$ 上,中心处只能出现 $1764$ 个紧致类类型中的 $13$ 个,且无一带有孤岛。在 $[-32, 32]$ 上仅剩下六个:$\{0,15\}$、$\{0,1,14,15\}$、$\{0,\dots,3,12,\dots,15\}$、$\{0,\dots,7,12,\dots,15\}$、$\{0,\dots,3,8,\dots,15\}$ 以及全块。

综合。 对应于 $k = 15$ 和 $m = 4$ 的引理 1 需要 $\max\{32, 3825\} \le n$、偶数性以及 $16 \nmid n$,这些在此均为假设条件。其无孤岛假设由引理 2 提供。因此 $\operatorname{eq}(C_n^{15}) = 4 + 2 = 6$。

5. 讨论

借助这一结果,arXiv:2610.15635 中的剩余偶数情形已对 $k = 3$、$k = 7$ 和 $k = 15$ 得到解决,并且在每种情形下均取较大的值 $m + 2$。$k = 7$ 的情形在同一天通过将早期的下界(当 $n \ge 22$ 且 $8 \nmid n$ 时不存在 $C_n^7$ 的由 $4$ 个等价子图构成的覆盖)与显式上界构造相结合而得以闭合。它给出了对每个满足 $8 \nmid n$ 的 $n \ge 98$ 均有 $\operatorname{eq}(C_n^7) = 5$。

1. 一般的 $m$。由引理 1,指数 $m$ 处的无孤岛性质可解决所有允许的 $n$ 下的 $k = 2^m - 1$ 情形。上述证明是专门针对 $m = 4$ 的有限局部论证。统一的证明仍未解决。在计算机搜索中,对于 $m = 5$,在半径为 $48$ 的窗口(同样是弧长的 $3/2$)中心处,相同的对半分割形状(低于偏移量 $2^{m-1}$ 的初始段,以及自该偏移量起的末尾段)被强制出现。这表明 $k = 31$ 可以用相同的方法处理。

2. 较小的 $n$。引理 2 本身是关于局部模型的命题,不需要对 $n$ 的界。界 $n \ge 3825$ 仅通过未决情形的假设以及引理 1 进入。对于满足 $16 \nmid n$ 的较小偶数 $n$ 是否有 $\operatorname{eq}(C_n^{15}) = 6$,在此未作探讨。

为什么是研究级成果

  • Settles the k = 15 case of the residual even case of arXiv:2610.15635: eq(C_n^15) = 6 for every even n ≥ 3825 with 16 ∤ n, where the paper only has eq(C_n^15) ∈ {5, 6}; the first case beyond k = 3 where the exact value is now known

Lean 声明

Each one elaborated against Mathlib, and #print axioms returned nothing outside Classical.choice · Quot.sound · propext.

参考文献

  1. arXiv:2610.15635 — Covering powers of cycles with equivalence subgraphs

由 gemini-3.8-flash 根据知识库起草,经过检查并由 Claude Code 审阅英文版;中文版由模型翻译并对照英文检查。只有 Lean 部分经过验证,文字是对它的解读。