simple_graph_equivalence_covering_number_cycle_power_fifteen_of_not_dvd
For 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₂ 16⌉. This settles the case k = 15 (m = 4) of the open problem: the paper's Theorems 1.3-1.4 leave eq(C_n^15) ∈ {5, 6} open for these n; the larger value holds.
Statement
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- Related work
- arXiv:2610.15635, Theorems 1.3 and 1.4 (Covering powers of cycles with equivalence subgraphs); OP-205; research thread RT-1
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- cycle_power_fifteen_model_no_islandThe no-island class shape at exponent m = 4 (bandwidth 15), in the exact form the conditional theorem…
- 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,…
- 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_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…
- 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.
Read back from the Lean
For any natural number $n$ such that $n \ge 3825$, $n$ is even, and $16$ does not divide $n$, the equivalence covering number of the 15th power of the $n$-cycle graph (i.e., the graph with vertex set $\mathbb{Z}/n\mathbb{Z}$ where distinct vertices $u, v$ are adjacent if and only if $\min((u - v)\text{.val}, (v - u)\text{.val}) \le 15$) is equal to $6$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The result is established by specializing the general classification theorem for dyadic cycle powers, `simple_graph_equivalence_covering_number_cycle_power_dyadic_of_class_shape`, to $k = 15$ and $m = 4$ (since $15 + 1 = 2^4$). The required lower bound $n \ge \max(2 \cdot 15 + 2, 15^2 \cdot 17) = 3825$, the evenness of $n$, and the condition $16 \nmid n$ hold directly from the hypotheses. Finally, the structural no-island property for valid configurations at $m = 4$ is supplied by the auxiliary theorem `cycle_power_fifteen_model_no_island`, concluding that the equivalence covering number is $4 + 2 = 6$.
The parameters $k = 15$ and $m = 4$ satisfy the dyadic conditions $1 \le m$ and $k + 1 = 2^m$ required by the dyadic covering theorem.
We apply the general theorem `simple_graph_equivalence_covering_number_cycle_power_dyadic_of_class_shape` with $k = 15$, $m = 4$, and graph order $n$. The parameter preconditions $1 \le 4$ and $15 + 1 = 2^4$ are discharged by direct numerical evaluation (`norm_num`).
uses
simple_graph_equivalence_covering_number_cycle_power_dyadic_of_class_shapesimple_graph_equivalence_covering_number_cycle_power_dyadic_of_class_shape 15 4 n (by norm_num) (by norm_num)
The lower bound, evenness, and non-divisibility hypotheses on $n$ hold, and the configuration model satisfies the no-island condition, establishing that the equivalence covering number of $C_n^{15}$ is 6.
The size bound $\max(2 \cdot 15 + 2, 15^2 \cdot (15 + 2)) \le n$ simplifies via `Nat.reduceMul`, `Nat.reduceAdd`, `Nat.reducePow`, and `max_le_iff` to $32 \le n \land 3825 \le n$, which is proved by linear arithmetic (`omega`) from the hypothesis $3825 \le n$. The evenness hypothesis `hev` is supplied directly, and the non-divisibility condition $\neg (15 + 1 \mid n)$ is discharged by `simpa` using the hypothesis $16 \nmid n$. Finally, the required no-island shape condition on valid models for $m = 4$ is supplied by the auxiliary theorem `cycle_power_fifteen_model_no_island`. With all hypotheses satisfied, the dyadic theorem concludes that the covering number is $m + 2 = 4 + 2 = 6$.
uses
Nat.reduceMul,Nat.reduceAdd,Nat.reducePow,max_le_iff,cycle_power_fifteen_model_no_island(by simp only [Nat.reduceMul, Nat.reduceAdd, Nat.reducePow, max_le_iff]; omega) hev (by simpa using hnd) (fun x h1 h2 h3 h4 => cycle_power_fifteen_model_no_island x h1 h2 h3 h4)
simple_graph_equivalence_covering_number_cycle_power_dyadic_of_class_shape- For dyadic cycle powers where $k + 1 = 2^m$ with $m \ge 1$, if an even graph order $n$ satisfies $n \ge \max(2k+2, k^2(k+2))$ and $(k+1) \nmid n$, and every valid model satisfies the no-island shape condition, then the equivalence covering number of $C_n^k$ is $m + 2$.
Nat.reduceMul- A simplification rule that evaluates multiplication of natural number literals.
Nat.reduceAdd- A simplification rule that evaluates addition of natural number literals.
Nat.reducePow- A simplification rule that evaluates exponentiation of natural number literals.
max_le_iff- The maximum of two elements is at most a third if and only if both elements are at most that third: $\max(a, b) \le c \iff a \le c \land b \le c$.
cycle_power_fifteen_model_no_island- For $m = 4$ ($k = 15$), any configuration satisfying the tightness, exactness, cover, and count conditions satisfies the no-island property: for any class $p$ and indices $a < b < c < 16$, if $x(p, a) = \text{false}$ and $x(p, b) = \text{true}$, then $x(p, c) = \text{true}$.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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 := simple_graph_equivalence_covering_number_cycle_power_dyadic_of_class_shape 15 4 n (by norm_num) (by norm_num) (by simp only [Nat.reduceMul, Nat.reduceAdd, Nat.reducePow, max_le_iff]; omega) hev (by simpa using hnd) (fun x h1 h2 h3 h4 => cycle_power_fifteen_model_no_island x h1 h2 h3 h4)