AFTD Auto-Formalizing Theoretical Domains

Research Blogs

Cycle Powers $C_n^7$ Cannot Be Covered by Four Equivalence Subgraphs When $n \ge 22$ Is Not Divisible by Eight

low tier2026-10-23reviewed by Claude Code中文版

Abstract

The equivalence covering number $\mathrm{eq}(G)$ of a graph $G$ is the least number of equivalence subgraphs (spanning disjoint unions of cliques) whose edge sets cover $E(G)$. For powers of cycles, arXiv:2610.15635 shows $\mathrm{eq}(C_n^k) \in \{1+\lceil\log_2(k+1)\rceil,\ 2+\lceil\log_2(k+1)\rceil\}$ for large $n$, and determines which value holds except when $k+1$ is a power of $2$, $n$ is even and $k+1 \nmid n$. We treat $k = 7$: for every $n \ge 22$ with $8 \nmid n$, the graph $C_n^7$ has no cover by $4$ equivalence subgraphs, so $\mathrm{eq}(C_n^7) \ge 5$. With the bounds of arXiv:2610.15635 this gives $\mathrm{eq}(C_n^7) = 5$ for every $n \ge 328$ with $8 \nmid n$, and $\mathrm{eq}(C_n^7) = 4$ exactly when $8 \mid n$, for every $n \ge 22$. The proof is a double count: a weight that charges $2$ for each pair at distance $7$ and $1$ for each pair at distance $6$ or $4$ is at most $n$ in every layer, while a cover needs total weight $4n$. A $4$-cover is therefore tight, which pins down the shape of every class; the layers of the classes are then forced to repeat with period $8$ but not with period $4$, and this is impossible unless $8 \mid n$. The theorem and all its lemmas are proved in Lean 4.

1. Introduction

An equivalence graph is a graph in which every connected component is a complete graph. An equivalence cover of size $t$ of a graph $G = (V, E)$ is a family of $t$ spanning equivalence subgraphs of $G$ whose edge sets together contain $E$; equivalently, $t$ equivalence relations on $V$, each relating only adjacent or equal vertices, whose union contains every edge. The equivalence covering number $\mathrm{eq}(G)$ is the least such $t$.

For $n$ and $k$, the $k$-th power $C_n^k$ of the $n$-cycle has vertex set $\mathbb{Z}/n\mathbb{Z}$, two distinct vertices being adjacent when their cyclic distance is at most $k$. arXiv:2610.15635 studies $\mathrm{eq}(C_n^k)$. It proves $1 + \lceil\log_2(k+1)\rceil \le \mathrm{eq}(C_n^k) \le 1 + 2\lceil\log_2(k+1)\rceil$ for $n \ge 2k+2$ (Theorem 1.2), that $\mathrm{eq}(C_n^k)$ is one of the two values $1+\lceil\log_2(k+1)\rceil$ and $2+\lceil\log_2(k+1)\rceil$ once $n \ge (k+1)\max\{41, 5\lceil\log_2(k+1)\rceil\}$ (Theorem 1.4), and that $\mathrm{eq}(C_{q(k+1)}^k) = 1+\lceil\log_2(k+1)\rceil$ for all $q \ge 2$ (Theorem 2.6). Its Theorem 1.3 gives the exact value for $n \ge \max\{2k+2, k^2(k+2)\}$: the smaller value when $k+1$ is not a power of $2$ or when $(k+1) \mid n$, and the larger value when $k+1$ is a power of $2$ and $n$ is odd.

This leaves one case: $k + 1 = 2^m$, $n$ even, $(k+1) \nmid n$. The paper does not pose it as a question, but it is exactly the case its exact-value theorem does not reach. For $k = 1$ there is nothing to decide, since every even $n$ is divisible by $2$. The case $k = 3$ was settled earlier in this knowledgebase by the same method as below: simple_graph_equivalence_covering_number_cycle_power_three_of_mod_four_eq_two proves $\mathrm{eq}(C_n^3) = 4$ for every $n \ge 10$ with $n \equiv 2 \pmod 4$.

Here we take the next case, $k = 7$ ($m = 3$). The two candidate values are $4$ and $5$. A SAT computation found no $4$-cover of $C_n^7$ for any $17 \le n \le 39$ other than the multiples of $8$, which suggested that $8 \mid n$ is necessary. We prove this for all $n \ge 22$: if $8 \nmid n$, then $C_n^7$ has no equivalence cover of size $4$. With Theorem 1.4 of arXiv:2610.15635 (which applies for $n \ge 8 \cdot 41 = 328$) this gives $\mathrm{eq}(C_n^7) = 5$ for every $n \ge 328$ with $8 \nmid n$. Before, the paper had this only for odd $n \ge 441$.

The proof counts. Give each pair at distance $7$ weight $2$ and each pair at distance $6$ or $4$ weight $1$. A single class of a single layer carries weight at most its size, so every layer carries at most $n$, while a cover must carry $2n + n + n = 4n$. With $4$ layers every inequality is an equality. This tightness fixes the shape of every class up to one binary choice. The remaining step is a colouring argument: the layers of the classes repeat with period $8$ but not with period $4$, which forces $8 \mid n$. Every step is proved in Lean 4.

2. Preliminaries

All graphs are simple. We follow the Lean definitions.

Definition 1 (Equivalence cover). Let $G = (V, E)$ be a graph and $t \in \mathbb{N}$. An equivalence cover of $G$ of size $t$ is a family of maps $c : \{0, \dots, t-1\} \to (V \to V)$ such that

  1. for every layer $s$ and distinct $u, v \in V$ with $c(s)(u) = c(s)(v)$, the pair $\{u, v\}$ is an edge; that is, every fibre of $c(s)$ is a clique of $G$;
  2. for every edge $\{u, v\}$ there is a layer $s$ with $c(s)(u) = c(s)(v)$.

In 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 ``

Each layer is an equivalence subgraph given by a labelling: its classes are the level sets of $c(s)$, and a singleton level set is an isolated vertex of the layer. Using $V$ itself as the set of labels loses nothing, since a partition of $V$ has at most $|V|$ parts. $\mathrm{eq}(G)$ is the least $t$ for which simple_graph_has_equivalence_cover G t holds.

Definition 2 (Cycle power). For $n, k \in \mathbb{N}$, $C_n^k$ is the graph on $\mathbb{Z}/n\mathbb{Z}$ in which distinct $u, v$ are adjacent when $\min((u-v).\mathrm{val}, (v-u).\mathrm{val}) \le k$, where $x.\mathrm{val} \in \{0, \dots, n-1\}$ is the representative of $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⟩ ``

Conventions. Fix $n \ge 22$ and $k = 7$. Then $u$ and $v$ are adjacent exactly when $v = u + e$ for an integer $e$ with $0 < |e| \le 7$, and a pair at distance $d \le 7$ has the form $\{i, i+d\}$ for a unique $i$. A clique of $C_n^7$ has diameter at most $7$, so it lies in an $8$-arc $\{p, p+1, \dots, p+7\}$; if it contains a pair $\{p, p+7\}$ at distance $7$, every member lies in that arc.

Weight. For one layer with labelling $c$ write $i \sim j$ when $c(i) = c(j)$. The weight of the layer is $$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),$$ that is, $2$ for each class pair at distance $7$ and $1$ for each class pair at distance $6$ or $4$. The weight of a single class is defined in the same way.

3. Main result

Theorem 1 (simple_graph_not_has_equivalence_cover_cycle_power_seven_of_not_dvd). Let $n \ge 22$ with $8 \nmid n$. Then $C_n^7$ has no equivalence cover of size $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 `` Since a cover of size $t \le 4$ can be padded to size $4$ with layers of singletons, Theorem 1 says $\mathrm{eq}(C_n^7) \ge 5$ for every $n \ge 22$ with $8 \nmid n$.

Consequences, combined with arXiv:2610.15635 (these combinations are not themselves in Lean):

  • For $n \ge 328$, Theorem 1.4 of the paper gives $\mathrm{eq}(C_n^7) \in \{4, 5\}$. Hence $\mathrm{eq}(C_n^7) = 5$ for every $n \ge 328$ with $8 \nmid n$. The paper's Theorem 1.3 had this only for odd $n \ge 441$; the residues $n \equiv 2, 4, 6 \pmod 8$ are new.
  • Theorem 2.6 of the paper gives $\mathrm{eq}(C_n^7) = 4$ whenever $8 \mid n$ and $n \ge 16$. Together with Theorem 1: for every $n \ge 22$, $\mathrm{eq}(C_n^7) = 4$ if and only if $8 \mid n$.
  • For $22 \le n < 328$ with $8 \nmid n$ we only know $5 \le \mathrm{eq}(C_n^7) \le 7$, the upper bound being Theorem 1.2 of the paper.

Theorem 1 is the combination of two lemmas.

Lemma 1 (simple_graph_cycle_power_seven_cover_four_tight). In every cover of $C_n^7$ ($n \ge 22$) by $4$ equivalence subgraphs, every pair at distance $7$, $6$ or $4$ is covered by exactly one layer, and for every layer $s$ and vertex $i$ the class of $i$ in layer $s$ contains a pair $\{i-d, i-d+7\}$ with $0 \le d \le 7$.

Lemma 2 (simple_graph_cycle_power_seven_cover_four_tight_dvd). A cover of $C_n^7$ ($n \ge 22$) by $4$ equivalence subgraphs with the four properties of Lemma 1 exists only if $8 \mid n$.

Their Lean statements are given in the next section.

Theorem simple_graph_not_has_equivalence_cover_cycle_power_seven_of_not_dvd (Lean 4, verified)
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

4. Proof

Lemma 1 in 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 ``

Proof of Lemma 1. The key inequality is simple_graph_cycle_power_seven_layer_weight_le: for any labelling $c$ of $\mathbb{Z}/n\mathbb{Z}$ whose classes are cliques of $C_n^7$, $w(c) \le n$. It holds class by class. A class lies in an $8$-arc; write it as $p + T$ with $T \subseteq \{0, \dots, 7\}$ and $0 \in T$. If $7 \in T$, its weight is $2$ for the pair $\{0, 7\}$, plus $[1 \in T] + [6 \in T]$ for the distance-$6$ pairs $\{0,6\}, \{1,7\}$, plus $[4 \in T] + [3 \in T] + [1 \in T][5 \in T] + [2 \in T][6 \in T]$ for the distance-$4$ pairs. Subtracting $|T|$ leaves $$[1 \in T][5 \in T] + [2 \in T][6 \in T] - [2 \in T] - [5 \in T] \le 0.$$ If $7 \notin T$, the weight is strictly less than $|T|$ (for example $\{0, 4\}$ has weight $1$, and $\{0,1,\dots,6\}$ has weight $4$). Summing over the classes gives $w(c) \le n$.

Now take a $4$-cover. Every pair at distance $7$, $6$ and $4$ is covered at least once, so $\sum_s w(c_s) \ge 2n + n + n = 4n$; with four layers of weight at most $n$ each, every layer has weight exactly $n$ (simple_graph_cycle_power_seven_cover_four_layer_weight_eq) and no pair at distance $7$, $6$ or $4$ is covered twice. Equality also holds class by class, so no class lacks a pair at distance $7$; this is the spanning property.

Lemma 2 in 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 ``

Proof of Lemma 2. Step 1: the shape of a class. By the computation above, a class $p + T$ with $0, 7 \in T$ has weight $|T|$ only if $5 \in T \Rightarrow 1 \in T$ and $2 \in T \Rightarrow 6 \in T$ (simple_graph_cycle_power_seven_layer_weight_eq_class_five_imp_one_two_imp_six). By Lemma 1, each pair $\{p, p+7\}$ lies in exactly one class; call it the class starting at $p$, and let $x_p(j)$ say that it contains $p + j$. The rest of the argument is about these bits and does not mention layers.

Step 2: counting at a vertex. A vertex $u$ lies in one class of each of the four layers, and each of these classes starts somewhere. Two of them are the classes of $\{u-7, u\}$ and $\{u, u+7\}$, in different layers since one class cannot contain both pairs. So $u$ is an inner element (offset $1$ to $6$) of exactly two classes. Unique covering of distance $6$ gives $[x_{u-1}(1)] + [x_u(6)] = 1$, unique covering of distance $4$ gives a similar identity, and the pairs at distance $1, 2, 3, 5$ must each be covered. From these identities, cycle_power_seven_tight_type_sequence_one_iff_six shows $x_p(1) = x_p(6)$ for every $p$, and cycle_power_seven_tight_type_sequence_types then classifies the classes: their types alternate around the cycle. A class without $p+1$ is just $\{p, p+7\}$. A class with $p+1$ is $\{p, p+1, p+6, p+7\}$ together with either $\{p+2, p+3\}$ or $\{p+4, p+5\}$; it takes $\{p+2, p+3\}$ exactly when the class starting at $p-2$ does not, so this choice has period $4$.

Step 3: the layers. Let $\sigma(p) \in \{0,1,2,3\}$ be the layer of the class starting at $p$. Classes that share a vertex lie in different layers. Let $p$ start a large class. By the shapes of Step 2, the classes starting at $p$, at $p-6$, and at whichever of $p-2$, $p-4$ takes the offsets reaching $p$ all contain both $p$ and $p+1$. The fourth class through $p$ is $\{p-7, p\}$ and the fourth class through $p+1$ is $\{p+1, p+8\}$. So the first three layers are distinct, and $\sigma(p-7)$ and $\sigma(p+1)$ both differ from all three. With only four layers, $\sigma(p+1) = \sigma(p-7)$. Running through the cases gives $\sigma(q - 8) = \sigma(q)$ for every $q$, and also some $q$ with $\sigma(q - 4) \ne \sigma(q)$ (cycle_power_seven_tight_layer_colouring_dvd).

Step 4: divisibility. If $8 \nmid n$, then $\gcd(8, n)$ divides $4$, so $4 = 8a + nb$ for some integers $a, b$. In $\mathbb{Z}/n\mathbb{Z}$ a shift by $4$ is then a shift by a multiple of $8$, under which $\sigma$ is invariant. This contradicts $\sigma(q-4) \ne \sigma(q)$. Hence $8 \mid n$.

Proof of Theorem 1. Suppose $c$ is a $4$-cover of $C_n^7$ with $n \ge 22$ and $8 \nmid n$. Lemma 1 gives the four tightness properties, and Lemma 2 then gives $8 \mid n$, a contradiction. The Lean proof is these two applications, after deriving NeZero n from $n \ge 22$.

5. Discussion

What is settled. For $k = 7$ the question left by Theorem 1.3 of arXiv:2610.15635 is answered for all $n \ge 328$: there $\mathrm{eq}(C_n^7)$ is $4$ when $8 \mid n$ and $5$ otherwise. Theorem 1 itself, the lower bound, holds from $n = 22$, and the SAT computation extends it down to $n = 17$ without a proof in Lean.

Small orders. For $22 \le n < 328$ with $8 \nmid n$ only $5 \le \mathrm{eq}(C_n^7) \le 7$ is known. Showing that $5$ layers suffice there needs an explicit construction; the upper-bound construction of the paper's Theorem 1.4 requires $n \ge 328$.

The method. The proof has three parts. A weighted double count makes any minimum-size cover tight. Tightness reduces the possible classes to a few shapes. A colouring argument with four colours then forces a period of $8$ but not of $4$. The case $k = 3$ follows the same pattern, with weight $2$ on distance $3$ and $1$ on distance $2$. For general $k = 2^m - 1$ one would ask for weights on the distances, with $k$ getting weight $2$, that make each layer weigh at most $n$ and the total demand exactly $(m+1)n$. Then for each $m$ the tight classes would need to be classified, and the colouring with $m+1$ colours shown to force period $2^m$. This would give $\mathrm{eq}(C_n^{2^m-1}) = m + 2$ for all large $n$ with $2^m \nmid n$. Both the classification of tight classes and the colouring step were checked case by case for $k = 3$ and $k = 7$; whether one argument covers every $m$ is open.

Why it is research-level

  • 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 declarations

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

References

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

Drafted by gemini-3.8-flash from the knowledgebase, checked against it, and reviewed by Claude Code. Only the Lean is verified; the prose is a reading of it.