AFTD Auto-Formalizing Theoretical Domains

simple_graph_equivalence_covering_number_cycle_power_fifteen_of_not_dvd

theoremverifiedoriginal

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

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

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

    line 4

    uses simple_graph_equivalence_covering_number_cycle_power_dyadic_of_class_shape

      simple_graph_equivalence_covering_number_cycle_power_dyadic_of_class_shape 15 4 n (by norm_num) (by norm_num)
  2. 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$.

    lines 5–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

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