当 $n \ge 22$ 不能被八整除时圈幂 $C_n^7$ 不能被四个等价子图覆盖
low tier2026-10-23审阅: Claude CodeEnglish
摘要
图 $G$ 的等价覆盖数 $\mathrm{eq}(G)$ 是其边集覆盖 $E(G)$ 的等价子图(团的生成不交并)的最小数量。对于圈的幂,arXiv:2610.15635 证明了当 $n$ 充分大时 $\mathrm{eq}(C_n^k) \in \{1+\lceil\log_2(k+1)\rceil,\ 2+\lceil\log_2(k+1)\rceil\}$,并确定了除 $k+1$ 为 $2$ 的幂、$n$ 为偶数且 $k+1 \nmid n$ 之外取哪个值。我们研究 $k = 7$ 的情形:对于每一个满足 $8 \nmid n$ 的 $n \ge 22$,图 $C_n^7$ 都不存在由 $4$ 个等价子图构成的覆盖,因此 $\mathrm{eq}(C_n^7) \ge 5$。结合 arXiv:2610.15635 的界,这给出了对于每一个满足 $8 \nmid n$ 的 $n \ge 328$ 都有 $\mathrm{eq}(C_n^7) = 5$,并且对于每一个 $n \ge 22$,$\mathrm{eq}(C_n^7) = 4$ 当且仅当 $8 \mid n$。该证明是一个双重计数:对每个距离为 $7$ 的对计权 $2$、对每个距离为 $6$ 或 $4$ 的对计权 $1$ 的权重在每一层中至多为 $n$,而覆盖所需的总权重为 $4n$。因此 $4$-覆盖是紧的,从而确定了每个类的形态;随后这些类所在的层被迫以 $8$ 为周期重复,但不能以 $4$ 为周期重复,而这除非 $8 \mid n$ 否则是不可能的。该定理及其所有引理均在 Lean 4 中得到证明。
1. 引言
等价图是指每个连通分支都是完全图的图。图 $G = (V, E)$ 的大小为 $t$ 的等价覆盖是指 $G$ 的 $t$ 个生成等价子图构成的族,它们的边集共同包含 $E$;等价地,它是 $V$ 上的 $t$ 个等价关系,每个关系仅关联相邻或相等的顶点,且它们的并包含每条边。等价覆盖数 $\mathrm{eq}(G)$ 是满足该条件的最小的 $t$。
对于 $n$ 和 $k$,$n$-圈的 $k$ 次幂 $C_n^k$ 的顶点集为 $\mathbb{Z}/n\mathbb{Z}$,当两个不同顶点的循环距离至多为 $k$ 时它们相邻。arXiv:2610.15635 研究了 $\mathrm{eq}(C_n^k)$。该文证明了对于 $n \ge 2k+2$ 有 $1 + \lceil\log_2(k+1)\rceil \le \mathrm{eq}(C_n^k) \le 1 + 2\lceil\log_2(k+1)\rceil$(定理 1.2);一旦 $n \ge (k+1)\max\{41, 5\lceil\log_2(k+1)\rceil\}$,$\mathrm{eq}(C_n^k)$ 是 $1+\lceil\log_2(k+1)\rceil$ 和 $2+\lceil\log_2(k+1)\rceil$ 这两个值之一(定理 1.4);并且对于所有 $q \ge 2$ 都有 $\mathrm{eq}(C_{q(k+1)}^k) = 1+\lceil\log_2(k+1)\rceil$(定理 2.6)。其定理 1.3 给出了 $n \ge \max\{2k+2, k^2(k+2)\}$ 时的精确值:当 $k+1$ 不是 $2$ 的幂或 $(k+1) \mid n$ 时取较小的值,当 $k+1$ 是 $2$ 的幂且 $n$ 为奇数时取较大的值。
这留下了一种情形:$k + 1 = 2^m$,$n$ 为偶数,且 $(k+1) \nmid n$。该文并未将其作为一个问题提出,但这恰恰是其精确值定理未能涵盖的情形。对于 $k = 1$,无需判定,因为每个偶数 $n$ 都能被 $2$ 整除。情形 $k = 3$ 此前在本知识库中已通过与下文相同的方法解决:simple_graph_equivalence_covering_number_cycle_power_three_of_mod_four_eq_two 证明了对于每一个满足 $n \equiv 2 \pmod 4$ 的 $n \ge 10$ 都有 $\mathrm{eq}(C_n^3) = 4$。
这里我们考虑下一个情形,$k = 7$($m = 3$)。两个候选值为 $4$ 和 $5$。一项布尔可满足性(SAT)计算发现,对于除 $8$ 的倍数以外的任何 $17 \le n \le 39$,$C_n^7$ 都不存在 $4$-覆盖,这提示了 $8 \mid n$ 是必需的。我们对所有 $n \ge 22$ 证明了这一点:如果 $8 \nmid n$,那么 $C_n^7$ 不存在大小为 $4$ 的等价覆盖。结合 arXiv:2610.15635 的定理 1.4(适用于 $n \ge 8 \cdot 41 = 328$),这给出了对于每一个满足 $8 \nmid n$ 的 $n \ge 328$ 都有 $\mathrm{eq}(C_n^7) = 5$。此前,该文仅对满足 $n \ge 441$ 的奇数 $n$ 得出了这一结果。
证明采用计数方法。赋予每个距离为 $7$ 的对权重 $2$,每个距离为 $6$ 或 $4$ 的对权重 $1$。单个层中的单个类所带的权重至多为其大小,因此每一层带有的权重至多为 $n$,而一个覆盖必须带有权重 $2n + n + n = 4n$。在有 $4$ 个层的情况下,每个不等式都取等号。这种紧性在相差一个二元选择的意义下确定了每个类的形态。剩下的步骤是一个染色论证:各类的层以 $8$ 为周期重复,但不以 $4$ 为周期重复,这迫使 $8 \mid n$。每一步均在 Lean 4 中得到证明。
2. 预备知识
所有图均为简单图。我们遵循 Lean 中的定义。
定义 1(等价覆盖)。设 $G = (V, E)$ 是一个图且 $t \in \mathbb{N}$。$G$ 的大小为 $t$ 的等价覆盖是一族映射 $c : \{0, \dots, t-1\} \to (V \to V)$,满足:
- 对于每一层 $s$ 以及满足 $c(s)(u) = c(s)(v)$ 的不同顶点 $u, v \in V$,对 $\{u, v\}$ 是一条边;也就是说,$c(s)$ 的每个纤维都是 $G$ 的团;
- 对于每条边 $\{u, v\}$,存在一层 $s$ 满足 $c(s)(u) = c(s)(v)$。
在 Lean 中: ``lean def simple_graph_has_equivalence_cover {V : Type*} (G : SimpleGraph V) (t : ℕ) : Prop := ∃ c : Fin t → V → V, (∀ s u v, u ≠ v → c s u = c s v → G.Adj u v) ∧ ∀ u v, G.Adj u v → ∃ s, c s u = c s v ``
每一层都是由标号给出的等价子图:其类为 $c(s)$ 的水平集,而单元素水平集是该层的孤立顶点。使用 $V$ 本身作为标号集不会失去一般性,因为 $V$ 的划分至多有 $|V|$ 个部分。$\mathrm{eq}(G)$ 是使 simple_graph_has_equivalence_cover G t 成立的最小的 $t$。
定义 2(圈幂)。对于 $n, k \in \mathbb{N}$,$C_n^k$ 是 $\mathbb{Z}/n\mathbb{Z}$ 上的图,其中当不同的 $u, v$ 满足 $\min((u-v).\mathrm{val}, (v-u).\mathrm{val}) \le k$ 时它们相邻,这里 $x.\mathrm{val} \in \{0, \dots, n-1\}$ 是 $x$ 的代表元。 ``lean def simple_graph_cycle_power (n k : ℕ) : SimpleGraph (ZMod n) where Adj u v := u ≠ v ∧ min (u - v).val (v - u).val ≤ k symm := ⟨fun (u v : ZMod n) (h : u ≠ v ∧ min (u - v).val (v - u).val ≤ k) => ⟨h.1.symm, by rw [min_comm]; exact h.2⟩⟩ loopless := ⟨fun (u : ZMod n) (h : u ≠ u ∧ min (u - u).val (u - u).val ≤ k) => h.1 rfl⟩ ``
约定。固定 $n \ge 22$ 且 $k = 7$。则 $u$ 与 $v$ 相邻当且仅当 $v = u + e$,其中整数 $e$ 满足 $0 < |e| \le 7$;且距离为 $d \le 7$ 的对对于唯一的 $i$ 具有形式 $\{i, i+d\}$。$C_n^7$ 的团的直径至多为 $7$,因此它包含在一个 $8$-弧 $\{p, p+1, \dots, p+7\}$ 中;如果它包含距离为 $7$ 的对 $\{p, p+7\}$,则其每个成员都包含在该弧中。
权重。对于具有标号 $c$ 的某一层,当 $c(i) = c(j)$ 时记 $i \sim j$。该层的权重为 $$w(c) = \sum_{i \in \mathbb{Z}/n\mathbb{Z}} \big(2[i \sim i+7] + [i \sim i+6] + [i \sim i+4]\big),$$ 即对同类中每个距离为 $7$ 的对计 $2$,对同类中每个距离为 $6$ 或 $4$ 的对计 $1$。单个类的权重以相同方式定义。
3. 主要结果
定理 1(simple_graph_not_has_equivalence_cover_cycle_power_seven_of_not_dvd)。设 $n \ge 22$ 且 $8 \nmid n$。则 $C_n^7$ 不存在大小为 $4$ 的等价覆盖。 ``lean theorem simple_graph_not_has_equivalence_cover_cycle_power_seven_of_not_dvd (n : ℕ) (hn : 22 ≤ n) (h8 : ¬ 8 ∣ n) : ¬ simple_graph_has_equivalence_cover (simple_graph_cycle_power n 7) 4 `` 由于大小为 $t \le 4$ 的覆盖可以通过添加单元素集构成的层填充至大小 $4$,定理 1 表明对于每一个满足 $8 \nmid n$ 的 $n \ge 22$ 都有 $\mathrm{eq}(C_n^7) \ge 5$。
推论,结合 arXiv:2610.15635(这些结合本身并未包含在 Lean 中):
- 对于 $n \ge 328$,该文定理 1.4 给出 $\mathrm{eq}(C_n^7) \in \{4, 5\}$。因此对于每一个满足 $8 \nmid n$ 的 $n \ge 328$ 都有 $\mathrm{eq}(C_n^7) = 5$。该文定理 1.3 仅对满足 $n \ge 441$ 的奇数 $n$ 得到了这一结论;余数 $n \equiv 2, 4, 6 \pmod 8$ 是新的。
- 该文定理 2.6 给出只要 $8 \mid n$ 且 $n \ge 16$ 就有 $\mathrm{eq}(C_n^7) = 4$。结合定理 1:对于每一个 $n \ge 22$,$\mathrm{eq}(C_n^7) = 4$ 当且仅当 $8 \mid n$。
- 对于满足 $8 \nmid n$ 的 $22 \le n < 328$,我们仅知道 $5 \le \mathrm{eq}(C_n^7) \le 7$,其中上界来自该文定理 1.2。
定理 1 是两个引理的结合。
引理 1(simple_graph_cycle_power_seven_cover_four_tight)。在 $C_n^7$($n \ge 22$)由 $4$ 个等价子图构成的每个覆盖中,每个距离为 $7$、$6$ 或 $4$ 的对都被恰好一个层覆盖,并且对于每个层 $s$ 和顶点 $i$,顶点 $i$ 在层 $s$ 中的类都包含一个满足 $0 \le d \le 7$ 的对 $\{i-d, i-d+7\}$。
引理 2(simple_graph_cycle_power_seven_cover_four_tight_dvd)。满足引理 1 的四条性质的 $C_n^7$($n \ge 22$)由 $4$ 个等价子图构成的覆盖仅在 $8 \mid n$ 时存在。
它们的 Lean 命题陈述在下一节中给出。
theorem simple_graph_not_has_equivalence_cover_cycle_power_seven_of_not_dvd (n : ℕ) (hn : 22 ≤ n)
(h8 : ¬ 8 ∣ n) : ¬ simple_graph_has_equivalence_cover (simple_graph_cycle_power n 7) 44. 证明
引理 1 在 Lean 中: ``lean theorem simple_graph_cycle_power_seven_cover_four_tight (n : ℕ) [NeZero n] (hn : 22 ≤ n) (c : Fin 4 → ZMod n → ZMod n) (hc : ∀ s u v, u ≠ v → c s u = c s v → (simple_graph_cycle_power n 7).Adj u v) (hcov : ∀ u v, (simple_graph_cycle_power n 7).Adj u v → ∃ s, c s u = c s v) : (∀ i, ∃! s, c s i = c s (i + 7)) ∧ (∀ i, ∃! s, c s i = c s (i + 6)) ∧ (∀ i, ∃! s, c s i = c s (i + 4)) ∧ ∀ s i, ∃ d : ℕ, d ≤ 7 ∧ c s (i - d) = c s (i - d + 7) ∧ c s (i - d) = c s i ``
引理 1 的证明。关键不等式是 simple_graph_cycle_power_seven_layer_weight_le:对于每个类都是 $C_n^7$ 的团的 $\mathbb{Z}/n\mathbb{Z}$ 的任意标号 $c$,都有 $w(c) \le n$。该结论逐类成立。一个类位于一个 $8$-弧中;将其写作 $p + T$,其中 $T \subseteq \{0, \dots, 7\}$ 且 $0 \in T$。如果 $7 \in T$,其权重为对 $\{0, 7\}$ 的 $2$,加上距离为 $6$ 的对 $\{0,6\}, \{1,7\}$ 的 $[1 \in T] + [6 \in T]$,再加上距离为 $4$ 的对的 $[4 \in T] + [3 \in T] + [1 \in T][5 \in T] + [2 \in T][6 \in T]$。减去 $|T|$ 后剩下 $$[1 \in T][5 \in T] + [2 \in T][6 \in T] - [2 \in T] - [5 \in T] \le 0.$$ 如果 $7 \notin T$,权重严格小于 $|T|$(例如 $\{0, 4\}$ 的权重为 $1$,而 $\{0,1,\dots,6\}$ 的权重为 $4$)。对所有类求和即得 $w(c) \le n$。
现在考虑一个 $4$-覆盖。每个距离为 $7$、$6$ 和 $4$ 的对都至少被覆盖一次,因此 $\sum_s w(c_s) \ge 2n + n + n = 4n$;由于四个层中每一层的权重至多为 $n$,每一层的权重恰好为 $n$(simple_graph_cycle_power_seven_cover_four_layer_weight_eq),且没有任何距离为 $7$、$6$ 或 $4$ 的对被重复覆盖两次。等号同样逐类成立,因此没有任何类缺少距离为 $7$ 的对;这就是生成性质。
引理 2 在 Lean 中: ``lean theorem simple_graph_cycle_power_seven_cover_four_tight_dvd (n : ℕ) [NeZero n] (hn : 22 ≤ n) (c : Fin 4 → ZMod n → ZMod n) (hc : ∀ s u v, u ≠ v → c s u = c s v → (simple_graph_cycle_power n 7).Adj u v) (hcov : ∀ u v, (simple_graph_cycle_power n 7).Adj u v → ∃ s, c s u = c s v) (h7 : ∀ i, ∃! s, c s i = c s (i + 7)) (h6 : ∀ i, ∃! s, c s i = c s (i + 6)) (h4 : ∀ i, ∃! s, c s i = c s (i + 4)) (hspan : ∀ s i, ∃ d : ℕ, d ≤ 7 ∧ c s (i - d) = c s (i - d + 7) ∧ c s (i - d) = c s i) : 8 ∣ n ``
引理 2 的证明。第 1 步:类的形态。根据上述计算,满足 $0, 7 \in T$ 的类 $p + T$ 的权重为 $|T|$ 仅当 $5 \in T \Rightarrow 1 \in T$ 且 $2 \in T \Rightarrow 6 \in T$(simple_graph_cycle_power_seven_layer_weight_eq_class_five_imp_one_two_imp_six)。由引理 1,每个对 $\{p, p+7\}$ 恰好位于一个类中;称其为始于 $p$ 的类,并令 $x_p(j)$ 表示该类包含 $p + j$。接下来的论证均针对这些比特,不再涉及层。
第 2 步:顶点处的计数。顶点 $u$ 位于四个层中各一个类中,且这些类中的每一个都始于某处。其中两个是包含 $\{u-7, u\}$ 和 $\{u, u+7\}$ 的类,它们位于不同的层,因为单个类不能同时包含这两个对。因此 $u$ 恰好是两个类的内部元素(偏移量为 $1$ 到 $6$)。距离为 $6$ 的唯一覆盖给出 $[x_{u-1}(1)] + [x_u(6)] = 1$,距离为 $4$ 的唯一覆盖给出类似的恒等式,并且距离为 $1, 2, 3, 5$ 的对都必须被覆盖。根据这些恒等式,cycle_power_seven_tight_type_sequence_one_iff_six 表明对每个 $p$ 都有 $x_p(1) = x_p(6)$,随后 cycle_power_seven_tight_type_sequence_types 对各类的类型进行了分类:它们的类型沿圈交替出现。不含 $p+1$ 的类就是 $\{p, p+7\}$。包含 $p+1$ 的类是 $\{p, p+1, p+6, p+7\}$ 与 $\{p+2, p+3\}$ 或 $\{p+4, p+5\}$ 之一的并;它包含 $\{p+2, p+3\}$ 恰好在始于 $p-2$ 的类不包含时成立,因此该选择具有周期 $4$。
第 3 步:层。令 $\sigma(p) \in \{0,1,2,3\}$ 为始于 $p$ 的类所在的层。共享顶点的类位于不同的层中。设 $p$ 为一个大类的起点。根据第 2 步中的形态,始于 $p$、始于 $p-6$ 以及始于 $p-2$ 与 $p-4$ 中能通过偏移量到达 $p$ 的那个类,都同时包含 $p$ 和 $p+1$。经过 $p$ 的第四个类是 $\{p-7, p\}$,经过 $p+1$ 的第四个类是 $\{p+1, p+8\}$。因此前三个层互不相同,且 $\sigma(p-7)$ 和 $\sigma(p+1)$ 都与这三个层不同。由于只有四个层,必有 $\sigma(p+1) = \sigma(p-7)$。遍历所有情形可得对每个 $q$ 都有 $\sigma(q - 8) = \sigma(q)$,并且还存在某个 $q$ 满足 $\sigma(q - 4) \ne \sigma(q)$(cycle_power_seven_tight_layer_colouring_dvd)。
第 4 步:整除性。如果 $8 \nmid n$,则 $\gcd(8, n)$ 整除 $4$,因此对某些整数 $a, b$ 有 $4 = 8a + nb$。在 $\mathbb{Z}/n\mathbb{Z}$ 中,平移 $4$ 因而等于平移 $8$ 的倍数,而 $\sigma$ 在此平移下是不变量。这与 $\sigma(q-4) \ne \sigma(q)$ 矛盾。因此 $8 \mid n$。
定理 1 的证明。假设 $c$ 是 $C_n^7$ 的一个 $4$-覆盖,其中 $n \ge 22$ 且 $8 \nmid n$。引理 1 给出四条紧性性质,引理 2 随后给出 $8 \mid n$,矛盾。在从 $n \ge 22$ 导出 NeZero n 之后,Lean 证明就是这两次应用。
5. 讨论
已解决的问题。对于 $k = 7$,arXiv:2610.15635 定理 1.3 留下的问题对所有 $n \ge 328$ 均已解决:在该范围内,当 $8 \mid n$ 时 $\mathrm{eq}(C_n^7)$ 为 $4$,否则为 $5$。定理 1 本身,即下界,自 $n = 22$ 起成立,且 SAT 计算将其下推至 $n = 17$(但未经 Lean 证明)。
较小阶数。对于满足 $8 \nmid n$ 的 $22 \le n < 328$,目前仅知 $5 \le \mathrm{eq}(C_n^7) \le 7$。要证明 $5$ 个层在此范围内足够需要显式构造;该文定理 1.4 中的上界构造要求 $n \ge 328$。
方法。证明包含三个部分。加权双重计数使得任何最小大小的覆盖都是紧的。紧性将可能的类缩减为少数几种形态。随后用四种颜色进行的染色论证迫使周期为 $8$ 但不为 $4$。$k = 3$ 的情形遵循相同的模式,对距离 $3$ 赋予权重 $2$,对距离 $2$ 赋予权重 $1$。对于一般的 $k = 2^m - 1$,人们需要寻找各距离上的权重(其中 $k$ 获得权重 $2$),使得每一层的权重至多为 $n$ 且总需求恰好为 $(m+1)n$。然后对每个 $m$,需要对紧的类进行分类,并证明用 $m+1$ 种颜色的染色迫使周期为 $2^m$。这将对所有满足 $2^m \nmid n$ 的大数 $n$ 给出 $\mathrm{eq}(C_n^{2^m-1}) = m + 2$。对紧类的分类和染色步骤在 $k = 3$ 和 $k = 7$ 时都是逐种情况检验的;是否存在一个论证能涵盖所有 $m$ 仍是未解决的问题。
为什么是研究级成果
- Settles the case k = 7 (k+1 = 8) of the gap left by Theorem 1.3 of arXiv:2610.15635: for n >= 22 with 8 not dividing n, C_n^7 has no cover by 4 equivalence subgraphs, so eq(C_n^7) >= 5. With the paper's Theorems 1.4 and 2.6, eq(C_n^7) = 5 for every n >= 328 with 8 not dividing n (the paper had it only for odd n >= 441), and eq(C_n^7) = 4 exactly when 8 | n. k = 3 was settled earlier the same way.
Lean 声明
- 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…
- 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_power_seven_cover_four_tightIn any cover of C_n^7 (n ≥ 22) by 4 equivalence subgraphs, every pair at distance 7, 6 or 4 is covered by exactly one layer, and every…
- simple_graph_cycle_power_seven_cover_four_tight_dvdA tight cover of C_n^7 (n ≥ 22) by 4 equivalence subgraphs (every distance-7, 6, 4 pair covered exactly once, every class spanned by a…
- simple_graph_cycle_power_seven_layer_weight_leLet n ≥ 22 and let c label the vertices of C_n^7 so that every label class is a clique. Then Σ_i (2·[i ~ i+7] + [i ~ i+6] + [i ~ i+4]) ≤…
- simple_graph_cycle_power_seven_cover_four_layer_weight_eqIn any cover of C_n^7 (n ≥ 22) by 4 equivalence subgraphs, every layer has weight exactly n: the sum over i of 2·[i ~ i+7] + [i ~ i+6] +…
- simple_graph_cycle_power_seven_layer_weight_eq_class_five_imp_one_two_imp_sixLet c label the vertices of C_n^7 (n ≥ 22) so that every label class is a clique, with total weight Σ_i (2·[i ~ i+7] + [i ~ i+6] + [i ~…
- cycle_power_seven_tight_type_sequence_one_iff_sixLayer-free form of h16. Let x p j say that the class starting at p (the class of the distance-7 pair (p, p+7)) contains p + j. If, around…
- cycle_power_seven_tight_type_sequence_typesLayer-free type classification for tight 4-covers of C_n^7. Let x p j say that the class starting at p (the class of the distance-7 pair…
- cycle_power_seven_tight_layer_colouring_dvdColouring core of the k = 7 lower bound. Positions of Z/n alternate between N-positions (where N holds) and P-positions, a is 4-periodic…
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 部分经过验证,文字是对它的解读。