AFTD Auto-Formalizing Theoretical Domains

simple_graph_equivalence_covering_number_cycle_power_large_upper

theoremverifiedformalization

For every natural k at least one and natural 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 2 plus the ceiling of the base-two logarithm of k+1.

Statement

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

Read back from the Lean

For all natural numbers $k$ and $n$, if $1 \le k$ and $\max(2k + 2, 2k^2) \le n$, then the equivalence covering number of the $k$-th power of the $n$-cycle graph (with vertex set $\mathbb{Z}/n\mathbb{Z}$) is at most $2 + \lceil \log_2(k + 1) \rceil$ (where Nat.clog is the ceiling of the base-2 logarithm).

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 proof embeds the cycle power C_n^k as an induced subgraph into an inflated cycle power C_N^{2k}, where N = q(2k+1) is a multiple of 2k+1. This structured target graph admits an equivalence cover of size 1 + ⌈log₂(2k+1)⌉ by a divisibility covering theorem, which pulls back along the embedding to an equivalence cover of C_n^k. Applying the logarithmic inequality ⌈log₂(2k+1)⌉ ≤ ⌈log₂(k+1)⌉ + 1 then gives the desired bound 2 + ⌈log₂(k+1)⌉ on the equivalence covering number.

  1. Derive the inflation parameters q and N satisfying the required scaling inequalities.

    From the assumption max(2k+2, 2k²) ≤ n, the properties of maximum (le_max_left and le_max_right) give 2k+2 ≤ n and 2k² ≤ n. Setting q = ⌊(n+k)/(k+1)⌋ and N = q(2k+1), the lemma cycle_power_inflation_parameters establishes that 2 ≤ q, n ≤ N ≤ 2n, and (2k+1)n ≤ (k+1)N.

    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 cycle power C_n^k embeds as an induced subgraph into C_N^{2k} via the floor map.

    By cycle_power_floor_map_induced, the floor map u ↦ ⌊u · N / n⌋ is an injective homomorphism that preserves adjacencies in both directions, provided 0 < n ≤ N, kN ≤ (2k)n, and (2k+1)n ≤ (k+1)N. The strict positivity 0 < n is checked by linear arithmetic (omega), and kN ≤ 2kn follows by scaling N ≤ 2n by k via nonlinear arithmetic (nlinarith).

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

    Since N = q(2k+1) with 1 ≤ 2k (by omega from 1 ≤ k) and 2 ≤ q, the divisibility-cover lemma simple_graph_equivalence_covering_number_cycle_power_dvd_cover constructs an equivalence cover of C_N^{2k} using 1 + ⌈log₂(2k+1)⌉ equivalence relations.

    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 equivalence cover pulls back to an equivalence cover of C_n^k of size 1 + ⌈log₂(2k+1)⌉.

    Using simple_graph_has_equivalence_cover_pullback, an equivalence cover of size t on C_N^{2k} pulls back along the induced subgraph embedding to an equivalence cover of size t on C_n^k.

    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.

    By Nat.clog_le_of_le_pow, it suffices to show 2k+1 ≤ 2^(⌈log₂(k+1)⌉ + 1). By the defining equivalence of Nat.clog (Nat.clog_le_iff_le_pow applied to le_rfl), k+1 ≤ 2^(⌈log₂(k+1)⌉). Expanding the power by pow_succ gives 2^(⌈log₂(k+1)⌉ + 1) = 2^(⌈log₂(k+1)⌉) * 2 ≥ 2(k+1) = 2k+2 > 2k+1, which linear arithmetic (omega) verifies.

    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. The equivalence covering number of C_n^k is at most 2 + ⌈log₂(k+1)⌉.

    Unfolding the equivalence covering number as the infimum of valid cover sizes, Nat.sInf_le shows that the covering number is at most the cover size 1 + ⌈log₂(2k+1)⌉. Linear arithmetic (omega) combines this with the logarithmic inequality to conclude the upper bound 2 + ⌈log₂(k+1)⌉.

    lines 30–31

    uses Nat.sInf_le

      unfold simple_graph_equivalence_covering_number
      exact (Nat.sInf_le hpull).trans (by omega)
le_max_left
For any elements a and b in a linear order, a ≤ max a b.
le_max_right
For any elements a and b in a linear order, b ≤ max a b.
cycle_power_inflation_parameters
For k ≥ 1 and n ≥ max(2k+2, 2k²), setting q = ⌊(n+k)/(k+1)⌋ yields 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 ↦ ⌊u · N / n⌋ 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
An equivalence cover of size t on a graph pulls back along an induced subgraph embedding to an equivalence cover of size t on the domain graph.
Nat.clog_le_of_le_pow
If x ≤ b^y, then ⌈log_b x⌉ ≤ y.
Nat.clog_le_iff_le_pow
For base b > 1, ⌈log_b x⌉ ≤ y if and only if x ≤ b^y.
le_rfl
Every element in a preorder satisfies a ≤ a.
pow_succ
In a monoid, a^(n+1) = a^n * a.
Nat.sInf_le
If m belongs to a set of natural numbers s, then inf s ≤ m.

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_large_upper    (k n : ℕ) (hk : 1 ≤ k)    (hn : max (2*k+2) (2*k^2) ≤ n) :    simple_graph_equivalence_covering_number (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  unfold simple_graph_equivalence_covering_number  exact (Nat.sInf_le hpull).trans (by omega)
See it in the graphDiscuss this resultChallenge it