AFTD Auto-Formalizing Theoretical Domains

simple_graph_equivalence_covering_number_cycle_power_seven_of_not_dvd

theoremverifiedoriginal

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
Used by 2

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.

  1. 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.

    lines 4–5

    uses simple_graph_has_equivalence_cover_cycle_power_dyadic_upper, max_le_iff

      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)
  2. 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.

    line 6

    uses le_antisymm, Nat.sInf_le, le_csInf

      refine le_antisymm (Nat.sInf_le hcov) (le_csInf ⟨3 + 2, hcov⟩ fun t ht => ?_)
  3. 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.

    lines 7–9

    uses simple_graph_not_has_equivalence_cover_cycle_power_seven_of_not_dvd, simple_graph_has_equivalence_cover_mono

      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)
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

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)
See it in the graphDiscuss this resultChallenge it