AFTD Auto-Formalizing Theoretical Domains

simple_graph_equivalence_covering_number_cycle_power_dyadic_upper

theoremverified

For natural k,m,n with k at least one, k+1 equal to 2 to the power m, and n at least max(2*k+2, twice the square of k), the equivalence covering number of the k-th power of the cycle on n vertices is at most m+2.

Statement

theorem simple_graph_equivalence_covering_number_cycle_power_dyadic_upper
    (k m n : ℕ) (hk : 1 ≤ k) (hkm : k+1 = 2^m)
    (hn : max (2*k+2) (2*k^2) ≤ n) :
    simple_graph_equivalence_covering_number (simple_graph_cycle_power n k) ≤ m+2
Source
arXiv:2610.15635, Proposition 3.2, with induced floor embedding from Lemma 3.1 and cover restriction from Lemma 2.1. This formalizes the published upper bound serving OP-205 / RT-1; no new research result is claimed.
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3

The proof, explained

The proof applies a known general upper bound, simple_graph_equivalence_covering_number_cycle_power_large_upper, which bounds the equivalence covering number of the k-th cycle power by 2 + ⌈log₂(k+1)⌉ for sufficiently large n. Because k+1 = 2^m, the ceiling logarithm ⌈log₂(k+1)⌉ is at most m. Combining these inequalities immediately gives the upper bound m+2.

  1. The equivalence covering number of the k-th power of the n-cycle is at most 2 + ⌈log₂(k+1)⌉.

    By simple_graph_equivalence_covering_number_cycle_power_large_upper, since 1 ≤ k and max(2k+2, 2k²) ≤ n, the equivalence covering number of the cycle power is bounded by 2 + ⌈log₂(k+1)⌉.

    line 9

    uses simple_graph_equivalence_covering_number_cycle_power_large_upper

      have hu := simple_graph_equivalence_covering_number_cycle_power_large_upper k n hk hn
  2. The equivalence covering number of the k-th power of the n-cycle is at most m + 2.

    Since k+1 = 2^m, in particular k+1 ≤ 2^m, so Nat.clog_le_of_le_pow implies that ⌈log₂(k+1)⌉ ≤ m. Combining this inequality with the upper bound from the previous step via linear integer arithmetic (omega) yields the target upper bound m+2.

    lines 10–11

    uses Nat.clog_le_of_le_pow

      have hlog : Nat.clog 2 (k+1) ≤ m := Nat.clog_le_of_le_pow hkm.le
      omega
simple_graph_equivalence_covering_number_cycle_power_large_upper
For natural numbers k and n with 1 ≤ k and n ≥ max(2k+2, 2k²), the equivalence covering number of the k-th power of the cycle graph on n vertices is at most 2 + ⌈log₂(k+1)⌉.
Nat.clog_le_of_le_pow
For natural numbers b, x, y, if x ≤ b^y, then the base-b ceiling logarithm ⌈log_b x⌉ is at most y.

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

open Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem simple_graph_equivalence_covering_number_cycle_power_dyadic_upper    (k m n : ℕ) (hk : 1 ≤ k) (hkm : k+1 = 2^m)    (hn : max (2*k+2) (2*k^2) ≤ n) :    simple_graph_equivalence_covering_number (simple_graph_cycle_power n k) ≤ m+2 := by  have hu := simple_graph_equivalence_covering_number_cycle_power_large_upper k n hk hn  have hlog : Nat.clog 2 (k+1) ≤ m := Nat.clog_le_of_le_pow hkm.le  omega
See it in the graphDiscuss this resultChallenge it