simple_graph_has_equivalence_cover_cycle_power_dyadic_upper
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
- 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_has_equivalence_coverG can be covered by t equivalence subgraphs: there are t spanning subgraphs of G, each a disjoint union of cliques (isolated vertices…
- simple_graph_has_equivalence_cover_monoIf G is covered by s equivalence subgraphs, it is covered by any larger number t of them (pad with the edgeless equivalence subgraph).
- simple_graph_has_equivalence_cover_cycle_power_large_upperFor 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…
- Used by 2
- simple_graph_equivalence_covering_number_cycle_power_seven_of_not_dvdFor every n ≥ 98 not divisible by 8, the equivalence covering number of the 7th power of the n-cycle is 5 = 2 + ⌈log₂ 8⌉. This settles the…
- simple_graph_equivalence_covering_number_cycle_power_dyadic_of_class_shapeUnder the numerical hypotheses of OP-205, the equivalence covering number is m+2 PROVIDED that every tight, exactly dyadically covered,…
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.
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.
uses
simple_graph_has_equivalence_cover_cycle_power_large_upperhave hcov := simple_graph_has_equivalence_cover_cycle_power_large_upper k n hk hnNat.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.
uses
Nat.clog_le_of_le_powhave hlog : Nat.clog 2 (k+1) ≤ m := Nat.clog_le_of_le_pow hkm.leThe 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.
uses
simple_graph_has_equivalence_cover_monoexact 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
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_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