The equivalence covering number of the fifteenth cycle power is six for all large even cycle lengths not divisible by sixteen
medium tier2026-10-30OP-205reviewed by Claude Code中文版
Abstract
For the $k$th power $C_n^k$ of the cycle graph $C_n$, an equivalence subgraph is a disjoint union of cliques, and $\operatorname{eq}(C_n^k)$ denotes the minimum number of equivalence subgraphs required to cover all edges of $C_n^k$. While $\operatorname{eq}(C_n^k)$ is known when $k+1$ is not a power of $2$, when $k+1$ divides $n$, or when $n$ is odd, the residual case where $k+1 = 2^m$, $n$ is even, and $2^m$ does not divide $n$ was left open in arXiv:2610.15635, which established only the two-value bound $\operatorname{eq}(C_n^k) \in \{m+1, m+2\}$. We determine the exact equivalence covering number for bandwidth $k = 15$ ($m = 4$): for every even integer $n \ge 3825 = 15^2 \cdot 17$ not divisible by $16$, $\operatorname{eq}(C_n^{15}) = 6 = 2 + \lceil\log_2 16\rceil$. The proof applies a dyadic reduction theorem showing that under the numerical hypotheses of the problem, an equivalence covering number of $m+1$ is impossible whenever every tight, exactly dyadically covered, fully ordinarily covered integer Boolean class model with $m+1$ active classes per vertex has classes that are an initial interval together with a terminal interval (no selected islands). We supply this no-island structural property for $m = 4$, ruling out the lower candidate $5$ and establishing the exact value. All definitions, lemmas, and main theorems are formalized and checked in Lean 4.
1. Introduction
An equivalence subgraph of a simple graph $G = (V, E)$ is a subgraph whose connected components are complete graphs; equivalently, it is the graph of an equivalence relation on a subset of $V$. The equivalence covering number of $G$, denoted $\operatorname{eq}(G)$, is the minimum number of equivalence subgraphs whose edge sets jointly cover $E(G)$. Covering graphs by equivalence subgraphs is a classic topic in graph theory with connections to order dimension, intersection graph theory, and network decomposition.
A natural and widely studied family of graphs in this context is the power of a cycle graph. For integers $n \ge 3$ and $k \ge 1$, the $k$th power of the $n$-cycle, denoted $C_n^k$, has vertex set $\mathbb{Z}/n\mathbb{Z}$, with two distinct vertices adjacent if and only if their cyclic shortest-path distance along $C_n$ is at most $k$. In arXiv:2610.15635, the equivalence covering number $\operatorname{eq}(C_n^k)$ was investigated systematically for large cycle lengths $n$. Specifically, Theorem 1.3 of arXiv:2610.15635 completely determines the exact value of $\operatorname{eq}(C_n^k)$ for all orders $n \ge \max\{2k+2, k^2(k+2)\}$ in three broad cases:
- 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 odd.
However, when $k+1$ is a power of $2$, $n$ is even, and $k+1$ does not divide $n$, Theorem 1.3 does not apply. In this residual case, writing $k+1 = 2^m$ with $m \ge 1$, Theorem 1.4 of arXiv:2610.15635 shows that for all sufficiently large $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\}.$$ Whether the true equivalence covering number attains the lower bound $m+1$ or the upper bound $m+2$ was left open in arXiv:2610.15635 for all dyadic bandwidths $k = 2^m - 1$ with $m \ge 2$.
For the dyadic exponent $m = 2$, corresponding to bandwidth $k = 3$ ($k+1 = 4$), earlier formal developments settled the question: the lower bound $\operatorname{eq}(C_n^3) \ge 4$ was verified for every $n \ge 10$ not divisible by $4$ (simple_graph_not_has_equivalence_cover_cycle_power_three_of_not_dvd), yielding $\operatorname{eq}(C_n^3) = 4$ for all even $n \ge 10$ with $n \equiv 2 \pmod 4$ (simple_graph_equivalence_covering_number_cycle_power_three_of_mod_four_eq_two), and resolving the minimal instance $n = 46$ where $\operatorname{eq}(C_{46}^3) = 4$ (simple_graph_equivalence_covering_number_cycle_power_forty_six_three).
For dyadic bandwidths beyond $k = 3$, the exact value has remained unresolved. For $k = 15$, where $m = 4$ and $k+1 = 16$, the bounds of arXiv:2610.15635 yield only $\operatorname{eq}(C_n^{15}) \in \{5, 6\}$ for even $n$ not divisible by $16$. In this post, we report on the formal verification in Lean 4 of the exact equivalence covering number for $k = 15$ in simple_graph_equivalence_covering_number_cycle_power_fifteen_of_not_dvd: $$\operatorname{eq}(C_n^{15}) = 6$$ for every even integer $n \ge 3825$ with $16 \nmid n$. Here the order bound $3825 = 15^2 \cdot 17$ corresponds precisely to the threshold $k^2(k+2) = \max\{2k+2, k^2(k+2)\}$ appearing in Theorem 1.3 of arXiv:2610.15635. The result establishes that the upper alternative $m+2 = 6$ holds throughout this infinite family, ruling out an equivalence cover by $5$ subgraphs.
2. Preliminaries
We introduce the formal definitions and conventions used in the Lean 4 formalization. Throughout, $\mathbb{N}$ denotes the non-negative integers $\{0, 1, 2, \dots\}$ and $\mathbb{Z}$ denotes the integers. For a positive integer $n$, the quotient $\mathbb{Z}/n\mathbb{Z}$ represents the ring of integers modulo $n$, with standard coercion from integers and a canonical representative in $\{0, 1, \dots, n-1\}$.
Definition 1 (Cycle Power Graph). Let $n$ and $k$ be non-negative integers. The $k$th power of the $n$-cycle, formalized as simple_graph_cycle_power, is the simple graph $C_n^k$ on the vertex set $\mathbb{Z}/n\mathbb{Z}$ whose adjacency relation is defined by: $$u \sim v \iff u \ne v \land \min((u - v).\operatorname{val}, (v - u).\operatorname{val}) \le k.$$ Here $(u - v).\operatorname{val}$ and $(v - u).\operatorname{val}$ represent the two directed path distances between $u$ and $v$ along the cycle, and their minimum is the shortest-path distance. The graph is loopless and undirected by definition.
Definition 2 (Equivalence Subgraph and Covering Number). Let $G = (V, E)$ be a simple graph. An equivalence subgraph of $G$ is a subgraph whose connected components are complete graphs; that is, the adjacency relation on the active vertices forms an equivalence relation. An equivalence cover of $G$ of size $t$ is a family of $t$ equivalence subgraphs $H_1, \dots, H_t$ of $G$ such that $\bigcup_{i=1}^t E(H_i) = E(G)$. The equivalence covering number of $G$, formalized as simple_graph_equivalence_covering_number, is defined as: $$\operatorname{eq}(G) = \inf \{t \in \mathbb{N} \mid G \text{ has an equivalence cover of size } t\}.$$ In Lean, this infimum is taken over the set of covering sizes using the conditionally complete lattice infimum operator on natural numbers. When no cover exists (which cannot occur for finite graphs), the infimum evaluates to $0$ by the convention that the infimum of the empty set in $\mathbb{N}$ is $0$.
Definition 3 (Dyadic Class Weight). Let $m \in \mathbb{N}$ be a dyadic exponent, and let $b : \mathbb{N} \to \operatorname{Bool}$ be a Boolean profile on the offsets $\{0, 1, \dots, 2^m - 1\}$. The dyadic class weight of $b$, formalized as cycle_power_dyadic_class_weight, is defined by: $$\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)],$$ where $[P]$ denotes the integer indicator $1$ if $P = \operatorname{true}$ and $0$ if $P = \operatorname{false}$.
Definition 4 (Integer Boolean Class Model). An integer Boolean class model is a function $x : \mathbb{Z} \to \mathbb{N} \to \operatorname{Bool}$, where $x(p)(a)$ indicates whether the equivalence class rooted at position $p \in \mathbb{Z}$ contains the vertex at offset $a \in \mathbb{N}$ (that is, lattice position $p + a$). For a fixed exponent $m$, we consider offsets $a \in \{0, 1, \dots, 2^m - 1\}$. A model $x$ satisfies four properties: 1. Tightness: for every $p \in \mathbb{Z}$, its dyadic class weight equals the total number of active offsets in the class: $$\operatorname{weight}_m(x(p)) = \sum_{a=0}^{2^m - 1} [x(p)(a)].$$ 2. Exact dyadic coverage: for each scale index $j \in \{0, 1, \dots, m-1\}$ and every lattice position $v \in \mathbb{Z}$, exactly one active class covers the dyadic pair at distance $2^m - 2^j$ starting at $v$: $$\sum_{a=0}^{2^j - 1} [x(v - a)(a) \land x(v - a)(a + 2^m - 2^j)] = 1.$$ 3. Full ordinary coverage: for every ordinary distance $d$ with $1 \le d < 2^m$ and every position $v \in \mathbb{Z}$, there exists an offset $a < 2^m - d$ such that $x(v - a)(a) = \operatorname{true}$ and $x(v - a)(a + d) = \operatorname{true}$. 4. Exact active class count: for every position $v \in \mathbb{Z}$, the total number of classes covering $v$ is exactly $m + 1$: $$\sum_{a=0}^{2^m - 1} [x(v - a)(a)] = m + 1.$$
Definition 5 (No-Island Property). A Boolean profile $b : \mathbb{N} \to \operatorname{Bool}$ on $\{0, \dots, 2^m - 1\}$ has no selected island if any offset following a false-then-true transition remains true; formally, for all offsets $a, b, c \in \mathbb{N}$ with $a < b < c < 2^m$: $$b(a) = \operatorname{false} \land b(b) = \operatorname{true} \implies b(c) = \operatorname{true}.$$ Equivalently, this forbids the pattern $\operatorname{false} \dots \operatorname{true} \dots \operatorname{false}$, meaning that each class consists of an initial interval together with a terminal interval (with inactive offsets possibly forming an intermediate interval). An integer Boolean class model $x$ has the no-island property if for every root $p \in \mathbb{Z}$, the profile $x(p)$ has this structure: every class is an initial interval together with a terminal interval.
Remark on Formalization Conventions. In Definition 3, the Lean definition cycle_power_dyadic_class_weight splits the summation over $j \in \{0, \dots, m-1\}$ by an explicit guard for $j = 0$, placing the endpoint pair at distance $2^m - 1$ into the leading term with weight $2$. In Definition 1, the graph $C_n^k$ joins distinct vertices at cyclic distance at most $k$, so an edge exists between distinct $u, v$ precisely when the shortest cyclic path has length at most $k$. In Definition 4, the lattice points $v$ and roots $p$ range over the integers $\mathbb{Z}$, representing a periodic unfold of the circular covering problem on $\mathbb{Z}/n\mathbb{Z}$.
3. Main result
Theorem (simple_graph_equivalence_covering_number_cycle_power_fifteen_of_not_dvd). Let $n$ be an even integer with $n \ge 3825$ such that $16$ does not divide $n$. Then the equivalence covering number of the fifteenth power of the $n$-cycle is $$\operatorname{eq}(C_n^{15}) = 6.$$
In Lean, the theorem simple_graph_equivalence_covering_number_cycle_power_fifteen_of_not_dvd states that for an integer $n$, assuming $3825 \le n$, that $n$ is even, and that $16$ does not divide $n$, the equivalence covering number of simple_graph_cycle_power for parameters $n$ and $15$, computed by simple_graph_equivalence_covering_number, equals $6$.
Context and What the Result Adds: 1. Resolving the Residual Dyadic Case at Exponent 4. Theorem 1.4 of arXiv:2610.15635 established that for $k = 15$ and sufficiently large even $n$ not divisible by $16$, the covering number $\operatorname{eq}(C_n^{15})$ is either $5$ or $6$. The main theorem eliminates the lower value $5$ and shows that the upper value $6 = 2 + \lceil\log_2 16\rceil$ holds unconditionally for all even $n \ge 3825$ with $16 \nmid n$.
2. The Range of $n$. The threshold $3825 = 15^2 \cdot 17 = k^2(k+2)$ is the hypothesis of the open case itself: for $k = 15$, $\max\{2k+2, k^2(k+2)\} = \max\{32, 3825\} = 3825$. The theorem covers every even $n$ in that range with $16 \nmid n$.
3. Advancement Beyond the Exponent 2 Case. Previously, the exact covering number in the residual even case was known only for $k = 3$ ($m = 2$), where $\operatorname{eq}(C_n^3) = 4$ was proved for all even $n \ge 10$ with $n \equiv 2 \pmod 4$ (simple_graph_equivalence_covering_number_cycle_power_three_of_mod_four_eq_two), as well as for the specific minimal order $n = 46$ (simple_graph_equivalence_covering_number_cycle_power_forty_six_three). The main theorem provides the exact determination for $k = 15$ ($m = 4$), settling this infinite family of graphs.
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) = 64. Proof
The proof shows that $C_n^{15}$ has no equivalence cover by $5$ equivalence subgraphs and that it has one by $6$. It has two parts: a reduction, proved in general for $k = 2^m - 1$, that leaves a single structural hypothesis on a local model, and a proof of that hypothesis for $m = 4$.
Part 1: the reduction. Lemma 1 (simple_graph_equivalence_covering_number_cycle_power_dyadic_of_class_shape). Let $k + 1 = 2^m$ with $m \ge 1$, $n \ge \max\{2k+2, k^2(k+2)\}$ even, and $k + 1 \nmid n$. Suppose every integer Boolean class model at exponent $m$ (Definition 4: tight, with exact dyadic coverage, full ordinary coverage and exactly $m+1$ classes through each position) has no island (Definition 5). Then $\operatorname{eq}(C_n^k) = m + 2$.
The upper bound $\operatorname{eq}(C_n^k) \le m+2$ comes from an explicit cover by $m+2$ equivalence subgraphs, formalized in the same development for all $n \ge \max\{2k+2, 2k^2\}$. For the lower bound, the Lean proof starts from a cover by $m+1$ equivalence subgraphs and builds a periodic model. Each pair $(p, p+k)$ at the maximal distance $k$ lies in exactly one clique of exactly one subgraph. Let $x(p)(a)$ record whether that clique contains $p + a$, and let $\ell(p)$ be the index of its subgraph. A weight inequality forces equality everywhere: each clique's dyadic weight (Definition 3) is at most its size, and the weights add up to $n(m+1)$. The equality gives tightness, exact coverage of the dyadic distances $2^m - 2^j$, exactly $m + 1$ classes through every position, and coverage of every ordinary distance. Two classes that meet a common position and have the same label are the same clique.
Under the no-island hypothesis, every other class that is active at the last vertex $p + 2^m - 1$ of the class rooted at $p$ meets the class rooted at $p + 2^m$. Since active classes at a position carry distinct labels, the labels are periodic with period $2^m$. An averaging inequality over the dyadic distances and their neighbours $2^m - 2^j \pm 1$ shows that some class contains the offset $2^{m-1} - 1$ or $2^{m-1}$. That forces two labels at distance $2^{m-1}$ to differ. A label sequence with periods $n$ and $2^m$ and two such labels gives $2^m \mid n$ by a gcd argument, which contradicts $k+1 \nmid n$.
Part 2: no islands for $m = 4$. Lemma 2 (cycle_power_fifteen_model_no_island) is the hypothesis of Lemma 1 for $m = 4$ in exactly the form Lemma 1 assumes. In a tight model with $5$ classes through each position, the exact equation at distance $15$ makes every class contain both endpoints $p$ and $p + 15$. Tightness then says each class is closed under a fixed parent map on the offsets $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$ (offsets $1, 3, 7$ point to $15$, and $8, 12, 14$ point to $0$). Each position is an inner element (offset $1$ to $14$) of exactly $3$ classes. Every pair at distance $14$, $12$ or $8$ is covered exactly once, and every other pair at distance at most $15$ is covered.
Two earlier lemmas of the same development show that, in this model, every class contains offset $1$ exactly when it contains offset $14$, and offset $2$ exactly when it contains offset $3$. Each is proved by refuting a mismatch at the class rooted at $0$ on the window of roots $[-32, 32]$. The new step is nine monotonicity rules for the class rooted at $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}.$$ Each rule is proved by refuting its violation using only the constraints on the window of roots $[-24, 24]$, with the two pairings as extra hypotheses. Most bits are forced by unit propagation of the linear constraints, each step checked by Lean's integer-arithmetic decision procedure. A few cases need a split on one bit. Each leaf closes by a linear combination of at most $45$ constraints, checked by Lean's linear-arithmetic tactic. The pairings keep each refutation small: at most five nodes in the case tree.
The parent map and the pairings supply the missing steps. The rule $x_2 \Rightarrow x_1$ holds because $2 \to 14$ and $x_{14} = x_1$, and $x_3 \Rightarrow x_2$ is the pairing. On the other side, $x_{13} \Rightarrow x_{14}$ holds because $13 \to 1$ and $x_1 = x_{14}$; offset $15$ is always present. So $x_{i+1} \Rightarrow x_i$ for $0 \le i \le 6$, and $x_i \Rightarrow x_{i+1}$ for $8 \le i \le 14$. By induction, the class's part in the offsets $0, \dots, 7$ is an initial segment and its part in $8, \dots, 15$ is a terminal segment, so it has no island. Translating the model moves any root to $0$, which gives the property for every root.
A finite search (not part of the proof) confirms the picture. On the window $[-24, 24]$, only $13$ of the $1764$ tight class types can occur at the centre, and none has an island. On $[-32, 32]$ only six remain: $\{0,15\}$, $\{0,1,14,15\}$, $\{0,\dots,3,12,\dots,15\}$, $\{0,\dots,7,12,\dots,15\}$, $\{0,\dots,3,8,\dots,15\}$ and the full block.
Assembly. Lemma 1 with $k = 15$ and $m = 4$ needs $\max\{32, 3825\} \le n$, evenness, and $16 \nmid n$, all of which are hypotheses here. Its no-island hypothesis is Lemma 2. So $\operatorname{eq}(C_n^{15}) = 4 + 2 = 6$.
5. Discussion
With this result the residual even case of arXiv:2610.15635 is settled for $k = 3$, $k = 7$ and $k = 15$, and in each case the larger value $m + 2$ holds. The case $k = 7$ was closed the same day by combining the earlier lower bound (no cover of $C_n^7$ by $4$ equivalence subgraphs when $n \ge 22$ and $8 \nmid n$) with the explicit upper construction. It gives $\operatorname{eq}(C_n^7) = 5$ for every $n \ge 98$ with $8 \nmid n$.
1. General $m$. By Lemma 1, the no-island property at exponent $m$ settles the case $k = 2^m - 1$ for all admissible $n$. The proof above is a finite local argument specific to $m = 4$. A uniform proof is open. In a computer search, the same half-split shape (an initial segment below offset $2^{m-1}$, a terminal segment from it) is forced at the centre of a window of radius $48$ for $m = 5$, again $3/2$ of the arc length. This suggests that $k = 31$ can be handled by the same method.
2. Smaller $n$. Lemma 2 itself is a statement about the local model and needs no bound on $n$. The bound $n \ge 3825$ enters only through the hypothesis of the open case and Lemma 1. Whether $\operatorname{eq}(C_n^{15}) = 6$ for smaller even $n$ with $16 \nmid n$ is not addressed here.
Why it is research-level
- 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 declarations
- simple_graph_equivalence_covering_number_cycle_power_fifteen_of_not_dvdFor every even n ≥ 3825 = 15²·17 not divisible by 16, the equivalence covering number of the 15th power of the n-cycle is 6 = 2 + ⌈log₂…
- 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_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_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_equivalence_covering_numberThe equivalence covering number eq(G): the minimum number of equivalence subgraphs of G whose edge sets cover E(G).
- cycle_power_dyadic_class_weightThe weighted number of pairs in a dyadic arc: the endpoint pair has weight two, and distances 2^m-2^j for 1≤j<m have weight one.
- simple_graph_equivalence_covering_number_cycle_power_dyadic_of_class_shapeUnder the numerical hypotheses of OP-205, the equivalence covering number is m+2 PROVIDED that every tight, exactly dyadically covered,…
- cycle_power_fifteen_model_no_islandThe no-island class shape at exponent m = 4 (bandwidth 15), in the exact form the conditional theorem…
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.