simple_graph_equivalence_covering_number_cycle_power_seven_of_not_dvd
For 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 case k = 7 (m = 3) of the open problem: for even n ≥ 441 not divisible by 8 the paper's Theorems 1.3-1.4 only give eq(C_n^7) ∈ {4, 5}; the larger value holds, and already from n = 98.
Statement
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) = 5- 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 6
- 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…
- 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_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…
- 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…
- Used by 2
- simple_graph_equivalence_covering_number_cycle_power_two_pow_even_not_dvd_of_alternating_endpointConditional reduction of OP-205 to alternation and endpoint-only classes: if for every m ≥ 5 every tight, exactly dyadically covered,…
- simple_graph_equivalence_covering_number_cycle_power_two_pow_even_not_dvd_of_alternating_pairedConditional resolution of OP-205: if, for every m ≥ 5, every tight, exactly dyadically covered, fully ordinarily covered integer Boolean…
Read back from the Lean
For every natural number $n$, if $98 \le n$ and $8$ does not divide $n$, then the equivalence covering number of the 7th power of the cycle graph on $n$ vertices (with vertex set $\mathbb{Z}/n\mathbb{Z}$) is equal to 5.
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 equivalence covering number of a graph is the minimum number of equivalence relations whose union covers its edge set. An upper bound of 5 is obtained from a general dyadic upper bound theorem applied to k = 7 = 2^3 - 1, which requires n ≥ max(16, 98) = 98. For the matching lower bound, any cover of size less than 5 would, by monotonicity, yield a cover of size 4; this is impossible by a known non-existence theorem for C_n^7 when n ≥ 22 and 8 ∤ n.
The graph C_n^7 has an equivalence cover of size 5.
We apply the dyadic upper bound theorem `simple_graph_has_equivalence_cover_cycle_power_dyadic_upper` with parameters k = 7 and m = 3. Its hypotheses require 1 ≤ 7 and 7 + 1 = 2^3 (both evaluated by arithmetic), as well as max(2 · 7 + 2, 2 · 7^2) = max(16, 98) ≤ n. Rewriting the maximum via `max_le_iff` reduces this to 16 ≤ n ∧ 98 ≤ n, which holds directly from the assumption n ≥ 98. Thus, C_n^7 admits an equivalence cover of size 3 + 2 = 5.
uses
simple_graph_has_equivalence_cover_cycle_power_dyadic_upper,max_le_iffhave hcov := simple_graph_has_equivalence_cover_cycle_power_dyadic_upper 7 3 n (by norm_num) (by norm_num) (by simp only [Nat.reduceMul, Nat.reduceAdd, Nat.reducePow, max_le_iff]; omega)
To prove that the equivalence covering number is 5, it suffices to show that every equivalence cover has size at least 5.
The equivalence covering number is defined as the infimum of the set of sizes of valid equivalence covers. Since 5 belongs to this set, the infimum is at most 5 by `Nat.sInf_le`. Applying antisymmetry of ≤ (`le_antisymm`) and the universal property of the infimum (`le_csInf`), equality to 5 reduces to showing that 5 is a lower bound, namely that any equivalence cover size t satisfies t ≥ 5.
uses
le_antisymm,Nat.sInf_le,le_csInfrefine le_antisymm (Nat.sInf_le hcov) (le_csInf ⟨3 + 2, hcov⟩ fun t ht => ?_)
Every equivalence cover of C_n^7 has size at least 5.
Suppose for contradiction that t < 5, which means t ≤ 4. By monotonicity of equivalence covers (`simple_graph_has_equivalence_cover_mono`), having a cover of size t implies having a cover of size 4. But by `simple_graph_not_has_equivalence_cover_cycle_power_seven_of_not_dvd`, no equivalence cover of size 4 exists whenever n ≥ 22 and 8 does not divide n. Since n ≥ 98 ≥ 22 and 8 ∤ n hold by assumption, this derives a contradiction.
uses
simple_graph_not_has_equivalence_cover_cycle_power_seven_of_not_dvd,simple_graph_has_equivalence_cover_monoby_contra hlt exact simple_graph_not_has_equivalence_cover_cycle_power_seven_of_not_dvd n (by omega) h8 (simple_graph_has_equivalence_cover_mono _ (by omega) ht)
simple_graph_has_equivalence_cover_cycle_power_dyadic_upper- For the cycle power C_n^k, if 1 ≤ k, k + 1 = 2^m, and n ≥ max(2k + 2, 2k^2), then C_n^k has an equivalence cover of size m + 2.
max_le_iff- The maximum of two elements is at most a third element if and only if both elements are at most that third element.
le_antisymm- In a partial order, if a ≤ b and b ≤ a, then a = b.
Nat.sInf_le- The infimum of a set of natural numbers is less than or equal to any element of that set.
le_csInf- In a conditionally complete lattice such as ℕ, if a nonempty set is bounded below by a, then a ≤ sInf s.
simple_graph_not_has_equivalence_cover_cycle_power_seven_of_not_dvd- For the 7th cycle power C_n^7, if n ≥ 22 and 8 does not divide n, then C_n^7 has no equivalence cover of size 4.
simple_graph_has_equivalence_cover_mono- If a graph has an equivalence cover of size s and s ≤ t, then it also has an equivalence cover of size t.
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_seven_of_not_dvd (n : ℕ) (hn : 98 ≤ n) (h8 : ¬ 8 ∣ n) : simple_graph_equivalence_covering_number (simple_graph_cycle_power n 7) = 5 := by have hcov := simple_graph_has_equivalence_cover_cycle_power_dyadic_upper 7 3 n (by norm_num) (by norm_num) (by simp only [Nat.reduceMul, Nat.reduceAdd, Nat.reducePow, max_le_iff]; omega) refine le_antisymm (Nat.sInf_le hcov) (le_csInf ⟨3 + 2, hcov⟩ fun t ht => ?_) by_contra hlt exact simple_graph_not_has_equivalence_cover_cycle_power_seven_of_not_dvd n (by omega) h8 (simple_graph_has_equivalence_cover_mono _ (by omega) ht)