AFTD Auto-Formalizing Theoretical Domains

simple_graph_has_equivalence_cover_cycle_power_large_upper

theoremverified

For natural k at least one and n at least max(2k+2,twice the square of k), the k-th cycle power on n vertices has an equivalence cover with2 plus the ceiling base-two logarithm of k+1 layers.

Statement

theorem simple_graph_has_equivalence_cover_cycle_power_large_upper
    (k n : ℕ) (hk : 1 ≤ k)
    (hn : max (2*k+2) (2*k^2) ≤ n) :
    simple_graph_has_equivalence_cover (simple_graph_cycle_power n k)
      (2+Nat.clog 2 (k+1))
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 10
Used by 1

The proof, explained

The theorem is proved by embedding C_n^k as an induced subgraph into an inflated cycle power C_N^{2k} whose vertex count N = q(2k+1) is a multiple of 2k+1. Choosing q = ⌊(n+k)/(k+1)⌋ ensures that the floor map u ↦ ⌊uN/n⌋ is an induced embedding, allowing the known equivalence cover for the divisible case C_{q(2k+1)}^{2k} to pull back to C_n^k with 1 + ⌈log₂(2k+1)⌉ layers. A standard logarithmic inequality ⌈log₂(2k+1)⌉ ≤ ⌈log₂(k+1)⌉ + 1 combined with monotonicity completes the bound.

  1. The inflation parameters q = ⌊(n+k)/(k+1)⌋ and N = q(2k+1) satisfy 2 ≤ q, n ≤ N ≤ 2n, and (2k+1)n ≤ (k+1)N.

    From the hypothesis n ≥ max(2k+2, 2k²), we extract the lower bounds 2k+2 ≤ n via le_max_left and 2k² ≤ n via le_max_right. We then invoke cycle_power_inflation_parameters with k ≥ 1 and these two bounds to obtain the arithmetic relations for q and N = q(2k+1).

    lines 10–16

    uses le_max_left, le_max_right, cycle_power_inflation_parameters

      have hn₀ : 2*k+2 ≤ n := (le_max_left _ _).trans hn
      have hn₂ : 2*k^2 ≤ n := (le_max_right _ _).trans hn
      let q := (n+k)/(k+1)
      have hp := cycle_power_inflation_parameters n k hk hn₀ hn₂
      change 2 ≤ q ∧ n ≤ q*(2*k+1) ∧ q*(2*k+1) ≤ 2*n ∧
        (2*k+1)*n ≤ (k+1)*(q*(2*k+1)) at hp
      let N := q*(2*k+1)
  2. The floor map from ℤ/nℤ to ℤ/Nℤ is an induced subgraph embedding of C_n^k into C_N^{2k}.

    We apply cycle_power_floor_map_induced with parameters n, N, k, and K = 2k. The required conditions 0 < n, n ≤ N, and (2k+1)n ≤ (k+1)N come directly from the parameter bounds, while kN ≤ 2kn follows by multiplying N ≤ 2n by k. This proves the floor map is injective and preserves adjacency in both directions.

    lines 17–18

    uses cycle_power_floor_map_induced

      have hemb := cycle_power_floor_map_induced n N k (2*k) (by omega) hp.2.1
        (by dsimp [N]; nlinarith [hp.2.2.1]) hp.2.2.2
  3. The inflated cycle power C_N^{2k} has an equivalence cover of size 1 + ⌈log₂(2k+1)⌉.

    Because N = q(2k+1) is an exact multiple of (2k)+1 with q ≥ 2 and 2k ≥ 1, simple_graph_equivalence_covering_number_cycle_power_dvd_cover applies directly to C_{q((2k)+1)}^{2k}, giving an equivalence cover of size 1 + ⌈log₂(2k+1)⌉.

    lines 19–20

    uses simple_graph_equivalence_covering_number_cycle_power_dvd_cover

      have hcov := simple_graph_equivalence_covering_number_cycle_power_dvd_cover (2*k) q
        (by omega) hp.1
  4. The cycle power C_n^k has an equivalence cover of size 1 + ⌈log₂(2k+1)⌉.

    By simple_graph_has_equivalence_cover_pullback, an equivalence cover on a target graph pulls back along an induced subgraph embedding to a cover of the source graph of the same size. Pulling back the cover of C_N^{2k} along the floor map embedding gives an equivalence cover of C_n^k with 1 + ⌈log₂(2k+1)⌉ layers.

    lines 21–23

    uses simple_graph_has_equivalence_cover_pullback

      have hpull := simple_graph_has_equivalence_cover_pullback
        (simple_graph_cycle_power n k) (simple_graph_cycle_power N (2*k))
        (1+Nat.clog 2 (2*k+1)) (cycle_power_floor_map n N) hemb.1 hemb.2 hcov
  5. ⌈log₂(2k+1)⌉ ≤ ⌈log₂(k+1)⌉ + 1.

    Using Nat.clog_le_of_le_pow, it suffices to check 2k+1 ≤ 2^(⌈log₂(k+1)⌉ + 1). Applying the equivalence Nat.clog_le_iff_le_pow to the tautology le_rfl yields k+1 ≤ 2^(⌈log₂(k+1)⌉). Rewriting the exponent with pow_succ gives 2^(⌈log₂(k+1)⌉ + 1) = 2^(⌈log₂(k+1)⌉) * 2, so linear arithmetic finishes the inequality 2k+1 ≤ 2(k+1) ≤ 2^(⌈log₂(k+1)⌉) * 2.

    lines 24–29

    uses Nat.clog_le_of_le_pow, Nat.clog_le_iff_le_pow, le_rfl, pow_succ

      have hlog : Nat.clog 2 (2*k+1) ≤ Nat.clog 2 (k+1)+1 := by
        apply Nat.clog_le_of_le_pow
        have hbase : k+1 ≤ 2^(Nat.clog 2 (k+1)) :=
          (Nat.clog_le_iff_le_pow (by decide)).mp le_rfl
        rw [pow_succ]
        omega
  6. C_n^k has an equivalence cover of size 2 + ⌈log₂(k+1)⌉.

    From the logarithmic bound, 1 + ⌈log₂(2k+1)⌉ ≤ 2 + ⌈log₂(k+1)⌉. Applying simple_graph_has_equivalence_cover_mono increases the cover size from 1 + ⌈log₂(2k+1)⌉ to the target bound 2 + ⌈log₂(k+1)⌉.

    line 30

    uses simple_graph_has_equivalence_cover_mono

      exact simple_graph_has_equivalence_cover_mono (simple_graph_cycle_power n k) (by omega) hpull
le_max_left
For any two elements in a linear order, the first is at most their maximum: a ≤ max a b.
le_max_right
For any two elements in a linear order, the second is at most their maximum: b ≤ max a b.
cycle_power_inflation_parameters
For k ≥ 1, if n ≥ 2k+2 and n ≥ 2k², then q = ⌊(n+k)/(k+1)⌋ satisfies 2 ≤ q, n ≤ q(2k+1) ≤ 2n, and (2k+1)n ≤ (k+1)q(2k+1).
cycle_power_floor_map_induced
If 0 < n ≤ N, kN ≤ Kn, and (K+1)n ≤ (k+1)N, then the floor map u ↦ ⌊uN/n⌋ is injective and is an induced subgraph embedding of C_n^k into C_N^K.
simple_graph_equivalence_covering_number_cycle_power_dvd_cover
For k ≥ 1 and q ≥ 2, the cycle power C_{q(k+1)}^k has an equivalence cover of size 1 + ⌈log₂(k+1)⌉.
simple_graph_has_equivalence_cover_pullback
If f is an induced subgraph embedding from G to H, any equivalence cover of H of size t pulls back along f to an equivalence cover of G of size t.
Nat.clog_le_of_le_pow
If x ≤ b^y, then ⌈log_b x⌉ ≤ y.
Nat.clog_le_iff_le_pow
For b > 1, ⌈log_b x⌉ ≤ y if and only if x ≤ b^y.
le_rfl
The preorder relation ≤ is reflexive: a ≤ a for every a.
pow_succ
In any monoid, a^(n+1) = a^n * a.
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

open Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem simple_graph_has_equivalence_cover_cycle_power_large_upper    (k n : ℕ) (hk : 1 ≤ k)    (hn : max (2*k+2) (2*k^2) ≤ n) :    simple_graph_has_equivalence_cover (simple_graph_cycle_power n k)      (2+Nat.clog 2 (k+1)) := by  have hn₀ : 2*k+2 ≤ n := (le_max_left _ _).trans hn  have hn₂ : 2*k^2 ≤ n := (le_max_right _ _).trans hn  let q := (n+k)/(k+1)  have hp := cycle_power_inflation_parameters n k hk hn₀ hn₂  change 2 ≤ q ∧ n ≤ q*(2*k+1) ∧ q*(2*k+1) ≤ 2*n ∧    (2*k+1)*n ≤ (k+1)*(q*(2*k+1)) at hp  let N := q*(2*k+1)  have hemb := cycle_power_floor_map_induced n N k (2*k) (by omega) hp.2.1    (by dsimp [N]; nlinarith [hp.2.2.1]) hp.2.2.2  have hcov := simple_graph_equivalence_covering_number_cycle_power_dvd_cover (2*k) q    (by omega) hp.1  have hpull := simple_graph_has_equivalence_cover_pullback    (simple_graph_cycle_power n k) (simple_graph_cycle_power N (2*k))    (1+Nat.clog 2 (2*k+1)) (cycle_power_floor_map n N) hemb.1 hemb.2 hcov  have hlog : Nat.clog 2 (2*k+1) ≤ Nat.clog 2 (k+1)+1 := by    apply Nat.clog_le_of_le_pow    have hbase : k+1 ≤ 2^(Nat.clog 2 (k+1)) :=      (Nat.clog_le_iff_le_pow (by decide)).mp le_rfl    rw [pow_succ]    omega  exact simple_graph_has_equivalence_cover_mono (simple_graph_cycle_power n k) (by omega) hpull
See it in the graphDiscuss this resultChallenge it