simple_graph_equivalence_covering_number_cycle_power_dyadic_upper
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
- simple_graph_cycle_powerThe k-th power C_n^k of the cycle C_n: vertices are the residues mod n, and two distinct vertices are adjacent when their distance along…
- simple_graph_equivalence_covering_numberThe equivalence covering number eq(G): the minimum number of equivalence subgraphs of G whose edge sets cover E(G).
- simple_graph_equivalence_covering_number_cycle_power_large_upperFor 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…
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.
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)⌉.
uses
simple_graph_equivalence_covering_number_cycle_power_large_upperhave hu := simple_graph_equivalence_covering_number_cycle_power_large_upper k n hk hnThe 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.
uses
Nat.clog_le_of_le_powhave 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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