simple_graph_equivalence_covering_number_cycle_power_large_upper
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
- 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_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_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. - 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…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- Used by 1
- simple_graph_equivalence_covering_number_cycle_power_dyadic_upperFor 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…
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.
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.
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 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).
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)⌉.
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.
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 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.
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.
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.
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
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)⌉.
uses
Nat.sInf_leunfold 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
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_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)