simple_graph_has_equivalence_cover_cycle_power_large_upper
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
- simple_graph_has_equivalence_cover_pullbackLet G and H be simple graphs on arbitrary types V and W, t a natural number, and f an injective map from V to W such that G adjacency is…
- cycle_power_floor_mapThe map from ZMod n to ZMod N sending a vertex u to the residue class of floor(u.val*N/n).
- cycle_power_floor_map_inducedFor natural n,N,k,K with n positive, N at least n, k*N at most K*n, and (K+1)*n at most (k+1)*N, the balanced floor map from ZMod n to…
- cycle_power_inflation_parametersFor natural k at least one and natural n at least both 2*k+2 and 2*k squared, put q=floor((n+k)/(k+1)). Then q is at least two, n is at…
- 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_equivalence_covering_number_cycle_power_dvdFor k ≥ 1 and q ≥ 2, the k-th power of the cycle on q(k + 1) vertices has equivalence covering number exactly 1 + ⌈log₂(k + 1)⌉.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- Used by 1
- simple_graph_has_equivalence_cover_cycle_power_dyadic_upperFor 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…
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.
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).
uses
le_max_left,le_max_right,cycle_power_inflation_parametershave 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)
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.
uses
cycle_power_floor_map_inducedhave 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
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)⌉.
uses
simple_graph_equivalence_covering_number_cycle_power_dvd_coverhave hcov := simple_graph_equivalence_covering_number_cycle_power_dvd_cover (2*k) q (by omega) hp.1
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.
uses
simple_graph_has_equivalence_cover_pullbackhave 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⌈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.
uses
Nat.clog_le_of_le_pow,Nat.clog_le_iff_le_pow,le_rfl,pow_succhave 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
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)⌉.
uses
simple_graph_has_equivalence_cover_monoexact 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
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_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