Equivalence Covering Number of the Seventh Power of Cycles of Order Not Divisible by Eight Is Five
medium tier2026-10-30OP-205reviewed by Claude Code中文版
Abstract
An equivalence subgraph of a simple graph is a spanning subgraph that forms a disjoint union of cliques, and the equivalence covering number $\operatorname{eq}(G)$ is the minimum number of equivalence subgraphs whose edge sets together cover all edges of $G$. For the $k$th power $C_n^k$ of the cycle $C_n$ on $n$ vertices, where distinct vertices are adjacent whenever their cyclic distance is at most $k$, determining $\operatorname{eq}(C_n^k)$ when $k+1 = 2^m$ and $n$ is an even integer not divisible by $k+1$ was left open by arXiv:2610.15635, which established that $\operatorname{eq}(C_n^k) \in \{1 + \lceil\log_2(k+1)\rceil, 2 + \lceil\log_2(k+1)\rceil\} = \{m+1, m+2\}$ for sufficiently large $n$ (Theorem 1.4). In this post, we present a verified formalization showing that for $k = 7$ (where $m = 3$) and every integer $n \ge 98$ not divisible by $8$, the equivalence covering number of $C_n^7$ is exactly $5 = 2 + \lceil\log_2 8\rceil$. The result combines a general dyadic upper bound construction yielding $\operatorname{eq}(C_n^k) \le m+2$ whenever $n \ge \max\{2k+2, 2k^2\}$ with a non-covering theorem ruling out any cover of $C_n^7$ by $4$ equivalence subgraphs for all $n \ge 22$ with $8 \nmid n$. All definitions, lemmas, and the main theorem simple_graph_equivalence_covering_number_cycle_power_seven_of_not_dvd have been verified in the Lean 4 proof assistant.
1. Introduction
An equivalence relation on a set partitions the set into disjoint equivalence classes. In the setting of simple undirected graphs, an equivalence subgraph of a graph $G = (V, E)$ is a spanning subgraph whose connected components are complete graphs; that is, it is a vertex-disjoint union of cliques. A collection of equivalence subgraphs covers $G$ if every edge of $G$ belongs to at least one of the equivalence subgraphs in the collection. The equivalence covering number of $G$, denoted by $\operatorname{eq}(G)$, is the minimum cardinality of such a covering collection. This invariant, along with related notions such as clique covers and intersection representations, provides a fundamental measure of the structural and combinatorial complexity of a graph.
The study of equivalence covering numbers for powers of cycles was systematically undertaken in arXiv:2610.15635. For positive integers $n$ and $k$, the $k$th power of an $n$-cycle, denoted $C_n^k$, is the graph on vertex set $\mathbb{Z}/n\mathbb{Z}$ where two distinct vertices are joined by an edge if and only if their shortest path distance along the cycle is at most $k$. In arXiv:2610.15635, Theorem 1.3 determines the exact value of $\operatorname{eq}(C_n^k)$ for all $n \ge \max\{2k+2, k^2(k+2)\}$ in three broad regimes:
- when $k+1$ is not a power of $2$;
- when $k+1$ divides $n$;
- when $k+1$ is a power of $2$ and $n$ is an odd integer.
In all of these cases, Theorem 1.3 establishes that $\operatorname{eq}(C_n^k)$ is uniquely determined and matches known lower bounds. Furthermore, Theorem 1.4 of arXiv:2610.15635 addresses the remaining regime, where $k+1 = 2^m$ for some positive integer $m$, $n$ is an even integer, and $k+1$ does not divide $n$. Theorem 1.4 proves that for all sufficiently large $n$, the equivalence covering number satisfies $$ \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\}. $$ However, the exact value remained undetermined in this residual case: does $\operatorname{eq}(C_n^k)$ equal $m+1$ or $m+2$? For $k = 3$ (where $k+1 = 4$) this is the question whether $\operatorname{eq}(C_n^3)$ equals $3$ or $4$ for even $n \ge 45$ not divisible by $4$. For $k = 7$ (where $k+1 = 8$ and $m = 3$), Theorem 1.4 of arXiv:2610.15635 gives only $\operatorname{eq}(C_n^7) \in \{4, 5\}$ for even $n \ge 8 \cdot 41 = 328$ with $8 \nmid n$, while Theorem 1.3 gives the value $5$ for odd $n \ge 441$.
Earlier results here settled the question for $k = 3$, and the case $k = 15$ was settled the same day: $\operatorname{eq}(C_n^{15}) = 6$ for every even $n \ge 3825$ not divisible by $16$. The result simple_graph_equivalence_covering_number_cycle_power_forty_six_three demonstrated that $\operatorname{eq}(C_{46}^3) = 4$, resolving the smallest open instance. This was generalized by simple_graph_not_has_equivalence_cover_cycle_power_three_of_not_dvd and simple_graph_equivalence_covering_number_cycle_power_three_of_mod_four_eq_two, which proved that $\operatorname{eq}(C_n^3) = 4$ for every $n \ge 10$ with $n \equiv 2 \pmod 4$.
In this post, we report on the resolution of the next power-of-two case, $k = 7$. We show that for every integer $n \ge 98$ not divisible by $8$, the equivalence covering number of $C_n^7$ is precisely $5 = 2 + \lceil\log_2 8\rceil$. This answers the open question for $k = 7$, proving that the upper candidate value $m+2$ always holds, from $n = 98$ on (for odd $n$ the value $5$ was known from $n \ge 441$). The entire development has been formalized and mechanically checked in Lean 4.
2. Preliminaries
We formalize graphs in the setting of simple undirected graphs. Let $V$ be a type. A simple graph $G$ on $V$ consists of a symmetric, irreflexive binary relation on $V$.
Definition 1 (simple_graph_cycle_power). Let $n, k \in \mathbb{N}$. The $k$th power of the $n$-cycle, denoted by simple_graph_cycle_power n k, is the simple graph with vertex set $\mathbb{Z}/n\mathbb{Z}$ whose adjacency relation is defined for $u, v \in \mathbb{Z}/n\mathbb{Z}$ by $$ u \sim v \iff u \ne v \land \min\left((u - v)\text{.val},\, (v - u)\text{.val}\right) \le k. $$ Here, $(x)\text{.val}$ denotes the canonical integer representative of the residue $x \in \mathbb{Z}/n\mathbb{Z}$ in the range $\{0, 1, \dots, n-1\}$. The value $\min\left((u - v)\text{.val},\, (v - u)\text{.val}\right)$ represents the shortest path distance between $u$ and $v$ along the cycle $C_n$.
Definition 2 (simple_graph_has_equivalence_cover). Let $G$ be a simple graph on vertex set $V$, and let $t \in \mathbb{N}$. We say that $G$ has an equivalence cover of size $t$, written simple_graph_has_equivalence_cover G t, if there exists a family of vertex labellings $c : \{0, \dots, t-1\} \to V \to V$ such that:
- for every layer $s \in \{0, \dots, t-1\}$ and all vertices $u, v \in V$, if $u \ne v$ and $c(s)(u) = c(s)(v)$, then $u$ and $v$ are adjacent in $G$;
- for every edge of $G$, i.e., whenever $u$ and $v$ are adjacent in $G$, there exists some layer $s \in \{0, \dots, t-1\}$ such that $c(s)(u) = c(s)(v)$.
Remark 1. In Definition 2, assigning each equivalence class a representative label in $V$ is completely general: any partition of $V$ has at most $|V|$ equivalence classes, and choosing a canonical representative from each class defines such a function $c(s) : V \to V$. The condition that $c(s)(u) = c(s)(v)$ implies adjacency for $u \ne v$ states that every fiber of $c(s)$ is a clique in $G$. The second condition guarantees that every edge of $G$ is covered by at least one layer.
Definition 3 (simple_graph_equivalence_covering_number). For any simple graph $G$ on vertex set $V$, its equivalence covering number, denoted by simple_graph_equivalence_covering_number G, is defined as $$ \operatorname{eq}(G) = \operatorname{sInf} \{t \in \mathbb{N} \mid \text{simple\_graph\_has\_equivalence\_cover } G \, t\}. $$
Remark 2. By convention, the infimum operation on subsets of $\mathbb{N}$ returns $0$ if the set is empty. For any finite graph $G$, an equivalence cover always exists (for instance, by covering each edge with a separate complete graph $K_2$ and isolated vertices), so the set is non-empty and the infimum yields the minimum cardinality.
The monotonicity of equivalence coverings with respect to the number of layers is recorded by the lemma simple_graph_has_equivalence_cover_mono:
Lemma 1 (simple_graph_has_equivalence_cover_mono). Let $G$ be a simple graph on $V$. If simple_graph_has_equivalence_cover G s holds and $s \le t$, then simple_graph_has_equivalence_cover G t holds.
Proof. If $s \le t$, we embed $\{0, \dots, s-1\}$ into $\{0, \dots, t-1\}$ and assign any extra layers $s' \ge s$ the identity map on $V$. The fibers of the identity map are singletons, which form cliques of size $1$ containing no edges, thus preserving both the clique property and the covering of all edges. The formal proof settles this by extending the family of labellings with identity functions.
3. Main result
The main theorem establishes the exact equivalence covering number for the 7th power of any cycle whose order is at least 98 and not divisible by 8.
Theorem (simple_graph_equivalence_covering_number_cycle_power_seven_of_not_dvd). Let $n$ be an integer satisfying $n \ge 98$ and $8 \nmid n$. Then the equivalence covering number of the $7$th power of the $n$-cycle is exactly $5$: $$ \operatorname{eq}(C_n^7) = 5. $$
The formal statement asserts that for any natural number $n$ such that $98 \le n$ and $\neg\,(8 \mid n)$, the equivalence covering number of the simple graph simple_graph_cycle_power n 7 equals $5$.
This settles the $k = 7$ ($m = 3$) case of the gap left by arXiv:2610.15635. There, Theorem 1.4 restricts $\operatorname{eq}(C_n^7)$ to $\{4, 5\}$ for $n \ge 328$, and Theorem 1.3 gives $5$ for odd $n \ge 441$; the even orders not divisible by $8$ were undecided. The theorem gives $5 = 2 + \lceil\log_2 8\rceil$ for all of them from $n = 98$ on, and also covers the odd orders between $98$ and $441$.
Together with $\operatorname{eq}(C_n^3) = 4$ for every $n \ge 10$ with $n \equiv 2 \pmod 4$ (simple_graph_equivalence_covering_number_cycle_power_three_of_mod_four_eq_two) and the bandwidth-15 result, the larger candidate value $m + 2$ is now known to hold for $k = 3$, $7$ and $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. Proof
The proof of the main theorem simple_graph_equivalence_covering_number_cycle_power_seven_of_not_dvd combines two complementary results: an explicit construction providing an upper bound for general dyadic cycle powers, and a structural impossibility theorem establishing the lower bound for $k = 7$.
Idea of the proof. To evaluate $\operatorname{eq}(C_n^7) = \operatorname{sInf} \{t \mid \operatorname{has\_cover}(C_n^7, t)\}$, we establish matching inequalities: 1. Upper bound: $\operatorname{eq}(C_n^7) \le 5$. We invoke the general theorem simple_graph_has_equivalence_cover_cycle_power_dyadic_upper with parameters $k = 7$ and $m = 3$ (since $7 + 1 = 2^3$). The theorem guarantees a cover of size $m + 2 = 5$ provided $n \ge \max\{2k+2, 2k^2\} = \max\{16, 98\} = 98$. Since $n \ge 98$ holds by hypothesis, $C_n^7$ admits an equivalence cover of size $5$. 2. Lower bound: $\operatorname{eq}(C_n^7) \ge 5$. By definition of the infimum on subsets of $\mathbb{N}$, it suffices to show that no $t < 5$ can cover $C_n^7$. By monotonicity (simple_graph_has_equivalence_cover_mono), if a cover of size $t \le 4$ existed, then a cover of size $4$ would also exist. The theorem simple_graph_not_has_equivalence_cover_cycle_power_seven_of_not_dvd rules this out for every $n \ge 22$ with $8 \nmid n$. Combining these two bounds by the antisymmetry of the partial order on natural numbers forces $\operatorname{eq}(C_n^7) = 5$.
We now state the two key lemmas.
Lemma 2 (simple_graph_has_equivalence_cover_cycle_power_dyadic_upper). Let $k, m, n \in \mathbb{N}$ such that $1 \le k$, $k + 1 = 2^m$, and $n \ge \max(2k+2, 2k^2)$. Then $$ \text{simple\_graph\_has\_equivalence\_cover } (C_n^k) \; (m+2). $$
Proof. Put $q = \lfloor (n+k)/(k+1) \rfloor$ and $N = q(2k+1)$. The balanced floor map $\mathbb{Z}/n\mathbb{Z} \to \mathbb{Z}/N\mathbb{Z}$ is injective and, under the hypothesis $n \ge \max(2k+2, 2k^2)$, it preserves and reflects adjacency from $C_n^k$ to $C_N^{2k}$, so $C_n^k$ is an induced subgraph of $C_N^{2k}$. An equivalence cover pulls back along an induced embedding. Since $2k+1$ divides $N$ and $q \ge 2$, the divisible case gives $C_N^{2k}$ a cover with $1 + \lceil\log_2(2k+1)\rceil$ layers, which equals $m + 2$ when $k + 1 = 2^m$.
Lemma 3 (simple_graph_not_has_equivalence_cover_cycle_power_seven_of_not_dvd). Let $n \in \mathbb{N}$ such that $n \ge 22$ and $8 \nmid n$. Then $$ \neg\,\text{simple\_graph\_has\_equivalence\_cover } (C_n^7) \; 4. $$
Proof. Suppose $c_0, \dots, c_3$ is a $4$-cover. Every class of a layer is a clique of $C_n^7$, so it lies in an arc of $8$ consecutive vertices. Give a layer the weight $\sum_i \big(2[i \sim i+7] + [i \sim i+6] + [i \sim i+4]\big)$, where $i \sim j$ means that $i$ and $j$ are in the same class. Inside an $8$-arc a class $K$ contributes at most $|K|$, so every layer has weight at most $n$.
The four layers must cover the $n$ pairs at distance $7$ (counted twice), and the $n$ pairs each at distances $6$ and $4$, a total demand of $4n$. Hence every layer has weight exactly $n$ and every pair at distance $7$, $6$ or $4$ is covered by exactly one layer. Equality in the class bound forces every class to contain a pair $\{p, p+7\}$ and to be tight: if it contains $p+5$ it contains $p+1$, and if it contains $p+2$ it contains $p+6$.
Name each class by the start $p$ of its distance-$7$ pair. Counting coverage around the cycle, without reference to layers, then shows that a class contains $p+1$ exactly when it contains $p+6$, and that the two kinds of classes alternate: a class without $p+1$ is $\{p, p+7\}$, and a class with $p+1$ is $\{p, p+1, p+6, p+7\}$, possibly with $\{p+2, p+3\}$ or $\{p+4, p+5\}$ added according to its neighbours two steps back and ahead. Finally, the layers of the four classes through two consecutive vertices $p$ and $p+1$ are pairwise distinct. Following these layers along the cycle, the class types repeat with period $4$ on alternate positions, and the pattern closes up only when $8$ divides $n$.
Formal synthesis. The proof of simple_graph_equivalence_covering_number_cycle_power_seven_of_not_dvd combines these ingredients:
- First, Lemma 2 is applied with parameters $k = 7$ and $m = 3$. The hypotheses $1 \le 7$ and $7 + 1 = 2^3$ hold by direct numerical evaluation, and the lower bound condition $\max(2 \cdot 7 + 2, 2 \cdot 7^2) = \max(16, 98) = 98 \le n$ follows from the assumption $98 \le n$ by Presburger arithmetic. This yields an equivalence cover of size $3 + 2 = 5$.
- By the definition of the infimum of a set of natural numbers, the existence of this $5$-cover establishes that the equivalence covering number is at most $5$.
- For the lower bound, we apply the universal property of the infimum with the non-empty witness $5$. It suffices to prove that any $t \in \mathbb{N}$ admitting an equivalence cover of size $t$ satisfies $5 \le t$.
- Arguing by contradiction, if $t < 5$, then $t \le 4$. By
simple_graph_has_equivalence_cover_mono, any equivalence cover of size $t$ extends to an equivalence cover of size $4$. - Because $n \ge 98 \ge 22$ and $8 \nmid n$, Lemma 3 (
simple_graph_not_has_equivalence_cover_cycle_power_seven_of_not_dvd) asserts that no equivalence cover of size $4$ exists, generating a contradiction. - The antisymmetry of the partial order on natural numbers concludes that the equivalence covering number is exactly $5$.
5. Discussion
The theorem simple_graph_equivalence_covering_number_cycle_power_seven_of_not_dvd determines $\operatorname{eq}(C_n^7)$ for every $n \ge 98$ not divisible by $8$: the value is $5$, the upper of the two candidates left by arXiv:2610.15635. With the results for $k = 3$ and $k = 15$, the larger value $m + 2$ now holds at three consecutive dyadic bandwidths.
The lower bound is exact counting. Under a $4$-cover, the distances $7$, $6$ and $4$ use up the whole capacity of every layer, so every class is rigid. What remains is a finite classification of the class shapes and a periodicity argument for the layers. The same method does not carry over directly to larger $k$: the local types multiply, and the bandwidth-15 proof needed its own local analysis.
The general question stays open: does $\operatorname{eq}(C_n^k) = m + 2$ hold for every $k = 2^m - 1$ and every large even $n$ not divisible by $k+1$? The upper bound $m + 2$ holds for all such $k$ once $n \ge \max(2k+2, 2k^2)$; what is missing is the matching lower bound for $m \ge 5$.
Why it is research-level
- 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 declarations
- 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.
References
- 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.