AFTD Auto-Formalizing Theoretical Domains

simple_graph_has_equivalence_cover_cycle_power_dyadic_upper

theoremverified

For 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 vertices has an equivalence cover with m+2 layers.

Statement

theorem simple_graph_has_equivalence_cover_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_has_equivalence_cover (simple_graph_cycle_power n k) (m+2)
Source
Uniform formal assembly for OP-205 / RT-1 following arXiv:2610.15635 Proposition3.2. The explicit upper covers formalize a published construction. The final reduction keeps the still-unproved pure class-shape theorem as an EXPLICIT additional hypothesis. No unconditional graph covering result or research advance is claimed.
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
Used by 2

The proof, explained

The proof applies a general upper bound showing that the k-th cycle power on n vertices has an equivalence cover of size 2 + ⌈log₂(k+1)⌉. Because k + 1 = 2^m, the ceiling logarithm ⌈log₂(k+1)⌉ is at most m, so 2 + ⌈log₂(k+1)⌉ ≤ m + 2. The result then follows by monotonicity of equivalence cover sizes.

  1. The cycle power simple_graph_cycle_power n k has an equivalence cover of size 2 + Nat.clog 2 (k + 1).

    We apply the known upper bound simple_graph_has_equivalence_cover_cycle_power_large_upper to k and n, which applies because 1 ≤ k and max(2k+2, 2k²) ≤ n.

    line 9

    uses simple_graph_has_equivalence_cover_cycle_power_large_upper

      have hcov := simple_graph_has_equivalence_cover_cycle_power_large_upper k n hk hn
  2. Nat.clog 2 (k + 1) ≤ m

    Since k + 1 = 2^m, we have k + 1 ≤ 2^m, so by Nat.clog_le_of_le_pow the ceiling logarithm of k + 1 to base 2 is at most m.

    line 10

    uses Nat.clog_le_of_le_pow

      have hlog : Nat.clog 2 (k+1) ≤ m := Nat.clog_le_of_le_pow hkm.le
  3. The cycle power simple_graph_cycle_power n k has an equivalence cover of size m + 2.

    From Nat.clog 2 (k + 1) ≤ m, linear integer arithmetic (via omega) yields 2 + Nat.clog 2 (k + 1) ≤ m + 2. We then invoke simple_graph_has_equivalence_cover_mono to increase the size of the equivalence cover from 2 + Nat.clog 2 (k + 1) to m + 2.

    line 11

    uses simple_graph_has_equivalence_cover_mono

      exact simple_graph_has_equivalence_cover_mono (simple_graph_cycle_power n k) (by omega) hcov
simple_graph_has_equivalence_cover_cycle_power_large_upper
For k ≥ 1 and n ≥ max(2k+2, 2k²), the k-th cycle power on n vertices has an equivalence cover of size 2 + ⌈log₂(k+1)⌉.
Nat.clog_le_of_le_pow
If x ≤ b^y, then ⌈log_b x⌉ ≤ y.
simple_graph_has_equivalence_cover_mono
If a simple 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

open Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem simple_graph_has_equivalence_cover_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_has_equivalence_cover (simple_graph_cycle_power n k) (m+2) := by  have hcov := simple_graph_has_equivalence_cover_cycle_power_large_upper k n hk hn  have hlog : Nat.clog 2 (k+1) ≤ m := Nat.clog_le_of_le_pow hkm.le  exact simple_graph_has_equivalence_cover_mono (simple_graph_cycle_power n k) (by omega) hcov
See it in the graphDiscuss this resultChallenge it