simple_graph_equivalence_covering_number_cycle_power_dvd
For 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)⌉.
Statement
theorem simple_graph_equivalence_covering_number_cycle_power_dvd (k q : ℕ) (hk : 1 ≤ k) (hq : 2 ≤ q) :
simple_graph_equivalence_covering_number (simple_graph_cycle_power (q * (k + 1)) k) =
1 + Nat.clog 2 (k + 1)- Formalizes
- arXiv:2610.15635 (Covering powers of cycles with equivalence subgraphs), Theorem 2.6.
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- 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_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_geFor k ≥ 1 and n ≥ 2k + 2, eq(C_n^k) ≥ 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… - bitThe real embedding of a Boolean value, sending false to 0 and true to 1.
- Used by 2
- 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…
- 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…
The proof, explained
The proof determines the equivalence covering number of the power cycle C_n^k when the number of vertices is a multiple of k + 1, n = q(k + 1). The vertex set is divided into q contiguous blocks of size k + 1, which form cliques covered by a base equivalence relation (layer 0). Edges that cross between different blocks only connect adjacent blocks along the cycle and correspond to pairs where the offset in the earlier block is strictly greater than the offset in the later block; using the binary representation of offsets, ⌈log₂(k + 1)⌉ additional equivalence relations are constructed—one for each bit position—so that each cross-block edge is captured by the bit where the two offsets first differ. Matching this upper bound with the general lower bound yields the exact value 1 + ⌈log₂(k + 1)⌉.
Any two numbers b < a < 2^L differ at some bit position ℓ < L where a has 1 and b has 0, and they agree on all higher bits.
By induction on L: if a and b have the same quotient upon division by 2, they already differ at bit 0 (a is odd and b is even). Otherwise, their quotients a / 2 and b / 2 are distinct numbers strictly below 2^(L-1), so the induction hypothesis supplies a separating bit position ℓ, which shifts to ℓ + 1 for the original numbers.
uses
Nat.div_le_div_right,pow_succ,pow_succ',Nat.div_div_eq_div_mulintro L induction L with | zero => intro a b hab ha; simp at ha; omega | succ L ih => intro a b hab ha by_cases h2 : a / 2 = b / 2 · exact ⟨0, by omega, a / 2, by simp; omega, by simp; omega⟩ · have hle : b / 2 ≤ a / 2 := Nat.div_le_div_right hab.le have ha2 : a / 2 < 2 ^ L := by rw [pow_succ] at ha; omega obtain ⟨ℓ, hℓ, p, hp1, hp2⟩ := ih (a / 2) (b / 2) (by omega) ha2 refine ⟨ℓ + 1, by omega, p, ?_, ?_⟩ · rw [pow_succ', ← Nat.div_div_eq_div_mul]; exact hp1 · rw [pow_succ', ← Nat.div_div_eq_div_mul]; exact hp2
Dividing J * K + r by K yields quotient J and remainder r when r < K.
By standard arithmetic of Euclidean division, shifting by a multiple of K pulls J into the quotient and preserves the remainder r when r < K.
uses
add_comm,Nat.add_mul_div_right,Nat.div_eq_of_lt,zero_add,Nat.add_mul_mod_self_right,Nat.mod_eq_of_ltconstructor · rw [add_comm, Nat.add_mul_div_right _ _ hK, Nat.div_eq_of_lt hr, zero_add] · rw [add_comm, Nat.add_mul_mod_self_right, Nat.mod_eq_of_lt hr]
If two distinct vertices i, i' belong to the same block of length k + 1, their cyclic distance is at most k.
When i and i' have the same quotient mod k + 1, their difference |i - i'| is strictly positive and bounded above by k, so they are adjacent in C_n^k.
uses
Nat.div_add_mod',Nat.mod_lt,Nat.div_lt_iff_lt_mul,Nat.zero_le,Nat.lt_or_gt_of_ne,Or.inl,Or.inr,Nat.mod_eq_of_lthave hK : 0 < k + 1 := by omega have hdi := Nat.div_add_mod' i (k + 1) have hdi' := Nat.div_add_mod' i' (k + 1) have hmi := Nat.mod_lt i hK have hmi' := Nat.mod_lt i' hK have hjq : ∀ m, m < q * (k + 1) → m / (k + 1) < q := fun m hm => (Nat.div_lt_iff_lt_mul hK).mpr hm have hji := hjq i hi have hji' := hjq i' hi' have hz0 := Nat.zero_le (i / (k + 1)) have hz0' := Nat.zero_le (i' / (k + 1)) -- same block have hsame : i / (k + 1) = i' / (k + 1) → ∃ d, 1 ≤ d ∧ d ≤ k ∧ ((i + d) % (q * (k + 1)) = i' ∨ (i' + d) % (q * (k + 1)) = i) := by intro hj rw [hj] at hdi rcases Nat.lt_or_gt_of_ne hne with h | h · exact ⟨i' - i, by omega, by omega, Or.inl (by rw [show i + (i' - i) = i' by omega, Nat.mod_eq_of_lt hi'])⟩ · exact ⟨i - i', by omega, by omega, Or.inr (by rw [show i' + (i - i') = i by omega, Nat.mod_eq_of_lt hi])⟩
If two vertices in different blocks share the same label at layer ℓ with opposite ℓ-th bits, their cyclic distance along the cycle is at most k.
Decoding the common label shows that vertex m has bit 1 at position ℓ and belongs to block j, while m' has bit 0 and belongs to block j + 1 (mod q), with the higher bits of their block offsets matching. This implies that m's offset within block j is strictly greater than m''s offset within block j + 1, which ensures that the forward cyclic distance (k + 1) + (m' % (k + 1)) - (m % (k + 1)) lies between 1 and k, both in the non-wrapping case and the wrap-around case from block q - 1 to 0.
uses
simple_graph_equivalence_covering_number_cycle_power_dvd_decode,Nat.div_add_mod',Nat.mod_lt,Nat.zero_le,Nat.div_le_self,Nat.add_mod_right,Nat.mod_eq_of_lt,Nat.div_le_div_right,Nat.succ_mul,Nat.add_mod_lefthave hcross : ∀ m m' : ℕ, m < q * (k + 1) → m' < q * (k + 1) → ∀ ℓ, (m % (k + 1) / 2 ^ ℓ) % 2 = 1 → (m' % (k + 1) / 2 ^ ℓ) % 2 = 0 → simple_graph_equivalence_covering_number_cycle_power_dvd_lab q (k + 1) ℓ m = simple_graph_equivalence_covering_number_cycle_power_dvd_lab q (k + 1) ℓ m' → ∃ d, 1 ≤ d ∧ d ≤ k ∧ (m + d) % (q * (k + 1)) = m' := by intro m m' hm hm' ℓ h1 h0 hl unfold simple_graph_equivalence_covering_number_cycle_power_dvd_lab at hl rw [h1, h0] at hl have hdm := Nat.div_add_mod' m (k + 1) have hdm' := Nat.div_add_mod' m' (k + 1) have hmm := Nat.mod_lt m hK have hmm' := Nat.mod_lt m' hK have hjm := hjq m hm have hjm' := hjq m' hm' have hz := Nat.zero_le (m / (k + 1)) have hz' := Nat.zero_le (m' / (k + 1)) have hD : m % (k + 1) / 2 ^ ℓ ≤ m % (k + 1) := Nat.div_le_self _ _ have hD' : m' % (k + 1) / 2 ^ ℓ ≤ m' % (k + 1) := Nat.div_le_self _ _ have hq0 : 0 < q := by omega have hJ := Nat.mod_lt (m / (k + 1) + q - 1 + 1) hq0 have hJ' := Nat.mod_lt (m' / (k + 1) + q - 1 + 0) hq0 obtain ⟨hJJ, hpp⟩ := (by have e1 := simple_graph_equivalence_covering_number_cycle_power_dvd_decode (k + 1) ((m / (k + 1) + q - 1 + 1) % q) (m % (k + 1) / 2 ^ ℓ / 2) hK (by omega) have e2 := simple_graph_equivalence_covering_number_cycle_power_dvd_decode (k + 1) ((m' / (k + 1) + q - 1 + 0) % q) (m' % (k + 1) / 2 ^ ℓ / 2) hK (by omega) rw [hl] at e1 exact ⟨e1.1.symm.trans e2.1, e1.2.symm.trans e2.2⟩ : (m / (k + 1) + q - 1 + 1) % q = (m' / (k + 1) + q - 1 + 0) % q ∧ m % (k + 1) / 2 ^ ℓ / 2 = m' % (k + 1) / 2 ^ ℓ / 2) have hJm : (m / (k + 1) + q - 1 + 1) % q = m / (k + 1) := by rw [show m / (k + 1) + q - 1 + 1 = m / (k + 1) + q by have := Nat.zero_le (m / (k + 1)); omega, Nat.add_mod_right, Nat.mod_eq_of_lt hjm] rw [hJm] at hJJ -- the digit of m is one more than that of m', so m % K > m' % K have hlt : m' % (k + 1) < m % (k + 1) := by by_contra hc push_neg at hc have := Nat.div_le_div_right (c := 2 ^ ℓ) hc omega have hmul : (m / (k + 1) + 1) * (k + 1) = m / (k + 1) * (k + 1) + (k + 1) := by ring refine ⟨k + 1 + m' % (k + 1) - m % (k + 1), by omega, by omega, ?_⟩ by_cases hj0 : m' / (k + 1) = 0 · -- wrap-around: m is in the last block rw [hj0] at hJJ have hlast : m / (k + 1) = q - 1 := by rw [show 0 + q - 1 + 0 = q - 1 by omega, Nat.mod_eq_of_lt (by omega)] at hJJ exact hJJ have hqK : (q - 1) * (k + 1) + (k + 1) = q * (k + 1) := by rw [← Nat.succ_mul]; congr 1; omega rw [hlast] at hdm rw [hj0] at hdm' rw [show m + (k + 1 + m' % (k + 1) - m % (k + 1)) = q * (k + 1) + m' by omega, Nat.add_mod_left, Nat.mod_eq_of_lt hm'] · have hprev : m / (k + 1) + 1 = m' / (k + 1) := by rw [show m' / (k + 1) + q - 1 + 0 = (m' / (k + 1) - 1) + q by omega, Nat.add_mod_right, Nat.mod_eq_of_lt (by omega)] at hJJ omega rw [← hprev] at hdm' rw [show m + (k + 1 + m' % (k + 1) - m % (k + 1)) = m' by omega, Nat.mod_eq_of_lt hm']
Any two distinct vertices sharing a label at any layer s have cyclic distance at most k.
If s = 0, both vertices share the same block index, so the same-block lemma applies. If s > 0, we examine the parity of the (s - 1)-th bit of the block offsets: if they are equal, decoding forces the vertices to belong to the same block; if they are unequal, one has bit 1 and the other has bit 0, so the cross-block lemma applies.
uses
if_true,Nat.eq_of_mul_eq_mul_right,if_false,simple_graph_equivalence_covering_number_cycle_power_dvd_decode,Nat.div_le_self,Nat.ModEq.add_right_cancel',add_assoc,Nat.mod_eq_of_lt,Nat.mod_two_eq_zero_or_one,Or.inr,Or.inlby_cases hs : s = 0 · simp only [hs, if_true] at heq exact hsame (Nat.eq_of_mul_eq_mul_right hK heq) · simp only [hs, if_false] at heq by_cases hpar : (i % (k + 1) / 2 ^ (s - 1)) % 2 = (i' % (k + 1) / 2 ^ (s - 1)) % 2 · apply hsame unfold simple_graph_equivalence_covering_number_cycle_power_dvd_lab at heq rw [hpar] at heq have hq0 : 0 < q := by omega have e1 := simple_graph_equivalence_covering_number_cycle_power_dvd_decode (k + 1) ((i / (k + 1) + q - 1 + i' % (k + 1) / 2 ^ (s - 1) % 2) % q) (i % (k + 1) / 2 ^ (s - 1) / 2) hK (by have := Nat.div_le_self (i % (k + 1)) (2 ^ (s - 1)); omega) have e2 := simple_graph_equivalence_covering_number_cycle_power_dvd_decode (k + 1) ((i' / (k + 1) + q - 1 + i' % (k + 1) / 2 ^ (s - 1) % 2) % q) (i' % (k + 1) / 2 ^ (s - 1) / 2) hK (by have := Nat.div_le_self (i' % (k + 1)) (2 ^ (s - 1)); omega) rw [heq] at e1 have hJ := e1.1.symm.trans e2.1 have hmod := Nat.ModEq.add_right_cancel' (q - 1 + i' % (k + 1) / 2 ^ (s - 1) % 2) (show i / (k + 1) + (q - 1 + i' % (k + 1) / 2 ^ (s - 1) % 2) ≡ i' / (k + 1) + (q - 1 + i' % (k + 1) / 2 ^ (s - 1) % 2) [MOD q] by unfold Nat.ModEq rw [← add_assoc, ← add_assoc] rw [show i / (k + 1) + q - 1 = i / (k + 1) + (q - 1) by omega, show i' / (k + 1) + q - 1 = i' / (k + 1) + (q - 1) by omega] at hJ exact hJ) unfold Nat.ModEq at hmod rwa [Nat.mod_eq_of_lt hji, Nat.mod_eq_of_lt hji'] at hmod · rcases Nat.mod_two_eq_zero_or_one (i % (k + 1) / 2 ^ (s - 1)) with h | h · have h' : (i' % (k + 1) / 2 ^ (s - 1)) % 2 = 1 := by omega obtain ⟨d, hd1, hd2, hd⟩ := hcross i' i hi' hi (s - 1) h' h heq.symm exact ⟨d, hd1, hd2, Or.inr hd⟩ · have h' : (i' % (k + 1) / 2 ^ (s - 1)) % 2 = 0 := by omega obtain ⟨d, hd1, hd2, hd⟩ := hcross i i' hi hi' (s - 1) h h' heq exact ⟨d, hd1, hd2, Or.inl hd⟩
Vertices in the same block share a label at layer 0, and vertices in adjacent blocks with decreasing offsets share a label at some bit layer ℓ + 1.
Identical block indices immediately yield identical labels at layer s = 0. For adjacent blocks where the earlier vertex has offset a and the later vertex has offset a' < a, the bit-separation lemma finds a bit position ℓ < L where a has 1, a' has 0, and all higher bits match; by design of the labeling formula, this gives them identical labels at layer s = ℓ + 1.
uses
Nat.div_add_mod',Nat.mod_lt,Nat.zero_le,Nat.mul_le_mul_right,Nat.div_lt_iff_lt_mul,simple_graph_equivalence_covering_number_cycle_power_dvd_bits,if_false,Nat.add_mod_right,Nat.mod_eq_of_lthave hK : 0 < k + 1 := by omega have hq0 : 0 < q := by omega have hdi := Nat.div_add_mod' i (k + 1) have hmi := Nat.mod_lt i hK have hj0 := Nat.zero_le (i / (k + 1)) have hn2 : 2 * (k + 1) ≤ q * (k + 1) := Nat.mul_le_mul_right _ hq have hji : i / (k + 1) < q := (Nat.div_lt_iff_lt_mul hK).mpr hi have hmul : (i / (k + 1) + 1) * (k + 1) = i / (k + 1) * (k + 1) + (k + 1) := by ring have hsame : i' / (k + 1) = i / (k + 1) → ∃ s, s < 1 + L ∧ (if s = 0 then i / (k + 1) * (k + 1) else simple_graph_equivalence_covering_number_cycle_power_dvd_lab q (k + 1) (s - 1) i) = (if s = 0 then i' / (k + 1) * (k + 1) else simple_graph_equivalence_covering_number_cycle_power_dvd_lab q (k + 1) (s - 1) i') := by intro hj exact ⟨0, by omega, by simp [hj]⟩ have hcross : ∀ j' a', i' / (k + 1) = j' → i' % (k + 1) = a' → a' < i % (k + 1) → (j' = i / (k + 1) + 1 ∨ (i / (k + 1) = q - 1 ∧ j' = 0)) → ∃ s, s < 1 + L ∧ (if s = 0 then i / (k + 1) * (k + 1) else simple_graph_equivalence_covering_number_cycle_power_dvd_lab q (k + 1) (s - 1) i) = (if s = 0 then i' / (k + 1) * (k + 1) else simple_graph_equivalence_covering_number_cycle_power_dvd_lab q (k + 1) (s - 1) i') := by intro j' a' hj' ha' hlt hcase obtain ⟨ℓ, hℓ, p, hp1, hp2⟩ := simple_graph_equivalence_covering_number_cycle_power_dvd_bits L (i % (k + 1)) a' hlt (by omega) refine ⟨ℓ + 1, by omega, ?_⟩ simp only [show ℓ + 1 ≠ 0 by omega, if_false, show ℓ + 1 - 1 = ℓ by omega] unfold simple_graph_equivalence_covering_number_cycle_power_dvd_lab rw [hp1, hj', ha', hp2, show (2 * p + 1) % 2 = 1 by omega, show (2 * p + 1) / 2 = p by omega, show 2 * p % 2 = 0 by omega, show 2 * p / 2 = p by omega] congr 2 rw [show i / (k + 1) + q - 1 + 1 = i / (k + 1) + q by omega, Nat.add_mod_right, Nat.mod_eq_of_lt hji] rcases hcase with hc | ⟨hc1, hc2⟩ · rw [hc, show i / (k + 1) + 1 + q - 1 + 0 = i / (k + 1) + q by omega, Nat.add_mod_right, Nat.mod_eq_of_lt hji] · rw [hc2, hc1, show 0 + q - 1 + 0 = q - 1 by omega, Nat.mod_eq_of_lt (by omega)]
Any two vertices at cyclic forward distance d ∈ [1, k] receive the same label in at least one layer s < 1 + L.
Case split on whether the step of length d stays within the current block or crosses into the next block. If it stays within the same block, layer 0 covers it. If it crosses into the next block (including wrapping from block q - 1 to 0), the remainder in the next block is strictly smaller than in the previous block, so the cross-block assignment at the separating bit position provides the matching label.
uses
Nat.mod_eq_of_lt,simple_graph_equivalence_covering_number_cycle_power_dvd_decode,Or.inl,Nat.mod_eq_sub_mod,Nat.mul_le_mul_right,Nat.succ_mul,zero_mul,zero_add,Or.inrby_cases hwrap : i + d < q * (k + 1) · rw [Nat.mod_eq_of_lt hwrap] at h by_cases hsm : i % (k + 1) + d < k + 1 · apply hsame have e := simple_graph_equivalence_covering_number_cycle_power_dvd_decode (k + 1) (i / (k + 1)) (i % (k + 1) + d) hK hsm rw [show i / (k + 1) * (k + 1) + (i % (k + 1) + d) = i' by omega] at e exact e.1 · have e := simple_graph_equivalence_covering_number_cycle_power_dvd_decode (k + 1) (i / (k + 1) + 1) (i % (k + 1) + d - (k + 1)) hK (by omega) rw [show (i / (k + 1) + 1) * (k + 1) + (i % (k + 1) + d - (k + 1)) = i' by omega] at e exact hcross _ _ e.1 e.2 (by omega) (Or.inl rfl) · have h' : i' = i + d - q * (k + 1) := by rw [Nat.mod_eq_sub_mod (by omega), Nat.mod_eq_of_lt (by omega)] at h exact h.symm have hlast : i / (k + 1) = q - 1 := by by_contra hc have hle : i / (k + 1) + 1 + 1 ≤ q := by omega have := Nat.mul_le_mul_right (k + 1) hle rw [Nat.succ_mul] at this omega have hqK : (q - 1) * (k + 1) + (k + 1) = q * (k + 1) := by rw [← Nat.succ_mul]; congr 1; omega rw [hlast] at hdi have e := simple_graph_equivalence_covering_number_cycle_power_dvd_decode (k + 1) 0 i' hK (by omega) rw [zero_mul, zero_add] at e exact hcross 0 i' e.1 e.2 (by omega) (Or.inr ⟨hlast, rfl⟩)
A cyclic forward offset d with 1 ≤ d ≤ k implies adjacency in the power cycle graph C_n^k.
The congruence (u.val + d) % n = v.val in integers implies v = u + d in ZMod n, and cyclic forward shifts by distance at most k are adjacent in C_n^k by definition.
uses
ZMod.val_injective,ZMod.val_add,ZMod.val_cast_of_lt,simple_graph_equivalence_covering_number_cycle_power_ge_adjhave hv : v = u + (d : ZMod n) := by apply ZMod.val_injective rw [ZMod.val_add, ZMod.val_cast_of_lt hdn] exact h.symm rw [hv] exact simple_graph_equivalence_covering_number_cycle_power_ge_adj n k u d hd1 hdk hdn
The proposed family of 1 + ⌈log₂(k + 1)⌉ subgraphs is well-defined and sound (each equivalence class forms a clique in C_n^k).
We define the cover using s = 0 for the block partition and s ∈ {1, ..., L} for the binary digit subgraphs. Bounding the integer formulas shows that the labels are strictly less than n = q(k + 1), so equality in ZMod n is equivalent to equality of the integer labels. The soundness theorem then guarantees that any two vertices with identical labels are at cyclic distance at most k, and hence adjacent.
uses
ZMod.val_lt,lt_of_le_of_lt,Nat.div_mul_le_self,Nat.mod_lt,Nat.div_le_self,Nat.mul_le_mul_right,Nat.succ_mul,congrArg,ZMod.val_cast_of_lt,ZMod.val_injective,simple_graph_equivalence_covering_number_cycle_power_dvd_sound,simple_graph_equivalence_covering_number_cycle_power_dvd_adjclassical have : NeZero (q * (k + 1)) := ⟨by positivity⟩ have hK : 0 < k + 1 := by omega have hq0 : 0 < q := by omega have hn : 2 * k + 2 ≤ q * (k + 1) := by nlinarith refine ⟨fun s v => (((if s.val = 0 then v.val / (k + 1) * (k + 1) else simple_graph_equivalence_covering_number_cycle_power_dvd_lab q (k + 1) (s.val - 1) v.val) : ℕ) : ZMod (q * (k + 1))), ?_, ?_⟩ · intro s u v huv h have hb : ∀ w : ZMod (q * (k + 1)), (if s.val = 0 then w.val / (k + 1) * (k + 1) else simple_graph_equivalence_covering_number_cycle_power_dvd_lab q (k + 1) (s.val - 1) w.val) < q * (k + 1) := by intro w have hw := ZMod.val_lt w split_ifs · exact lt_of_le_of_lt (Nat.div_mul_le_self _ _) hw · unfold simple_graph_equivalence_covering_number_cycle_power_dvd_lab have hJ := Nat.mod_lt (w.val / (k + 1) + q - 1 + w.val % (k + 1) / 2 ^ (s.val - 1) % 2) hq0 have hD := Nat.div_le_self (w.val % (k + 1)) (2 ^ (s.val - 1)) have hm := Nat.mod_lt w.val hK have hle := Nat.mul_le_mul_right (k + 1) (show (w.val / (k + 1) + q - 1 + w.val % (k + 1) / 2 ^ (s.val - 1) % 2) % q + 1 ≤ q from hJ) rw [Nat.succ_mul] at hle omega have hnat := congrArg ZMod.val h simp only at hnat rw [ZMod.val_cast_of_lt (hb u), ZMod.val_cast_of_lt (hb v)] at hnat have hne : u.val ≠ v.val := fun h' => huv (ZMod.val_injective _ h') obtain ⟨d, hd1, hd2, hd⟩ := simple_graph_equivalence_covering_number_cycle_power_dvd_sound k q hq u.val v.val (ZMod.val_lt u) (ZMod.val_lt v) hne s.val hnat rcases hd with hd | hd · exact simple_graph_equivalence_covering_number_cycle_power_dvd_adj _ k u v d hd1 hd2 (by omega) hd · exact (simple_graph_equivalence_covering_number_cycle_power_dvd_adj _ k v u d hd1 hd2 (by omega) hd).symm
The family of subgraphs is complete (every edge of C_n^k is covered by at least one subgraph).
Any adjacent pair u, v in C_n^k has either forward distance (v - u).val ≤ k or backward distance (u - v).val ≤ k. The completeness theorem for forward offsets applies with L = ⌈log₂(k + 1)⌉, producing a layer index s < 1 + L where the labels of u and v coincide.
uses
Nat.le_pow_clog,Nat.eq_zero_or_pos,ZMod.val_eq_zero,sub_eq_zero,ZMod.val_add,add_sub_cancel,simple_graph_equivalence_covering_number_cycle_power_dvd_complete,ZMod.val_lt,min_le_iff,Ne.symm· have hL : k + 1 ≤ 2 ^ Nat.clog 2 (k + 1) := Nat.le_pow_clog (by norm_num) _ have key : ∀ u v : ZMod (q * (k + 1)), u ≠ v → (v - u).val ≤ k → ∃ s : Fin (1 + Nat.clog 2 (k + 1)), (((if s.val = 0 then u.val / (k + 1) * (k + 1) else simple_graph_equivalence_covering_number_cycle_power_dvd_lab q (k + 1) (s.val - 1) u.val) : ℕ) : ZMod (q * (k + 1))) = (((if s.val = 0 then v.val / (k + 1) * (k + 1) else simple_graph_equivalence_covering_number_cycle_power_dvd_lab q (k + 1) (s.val - 1) v.val) : ℕ) : ZMod (q * (k + 1))) := by intro u v hne hle have hd1 : 1 ≤ (v - u).val := by rcases Nat.eq_zero_or_pos (v - u).val with h0 | h0 · rw [ZMod.val_eq_zero, sub_eq_zero] at h0 exact absurd h0.symm hne · exact h0 have hmod : (u.val + (v - u).val) % (q * (k + 1)) = v.val := by rw [← ZMod.val_add, add_sub_cancel] obtain ⟨s, hs, heq⟩ := simple_graph_equivalence_covering_number_cycle_power_dvd_complete k q (Nat.clog 2 (k + 1)) hq hL u.val v.val (v - u).val (ZMod.val_lt u) (ZMod.val_lt v) hd1 hle hmod exact ⟨⟨s, hs⟩, by simp only; rw [heq]⟩ intro u v huv obtain ⟨hne, hmin⟩ := huv rcases min_le_iff.mp hmin with h | h · obtain ⟨s, hs⟩ := key v u (Ne.symm hne) h exact ⟨s, hs.symm⟩ · exact key u v hne h
The equivalence covering number of C_{q(k+1)}^k is exactly 1 + ⌈log₂(k + 1)⌉.
By antisymmetry of ≤: the explicit cover of size 1 + ⌈log₂(k + 1)⌉ provides an upper bound on the infimum defining the equivalence covering number, while the general lower bound theorem for cycle powers establishes that at least 1 + ⌈log₂(k + 1)⌉ equivalence relations are required whenever 2k + 2 ≤ q(k + 1).
uses
le_antisymm,Nat.sInf_le,simple_graph_equivalence_covering_number_cycle_power_dvd_cover,simple_graph_equivalence_covering_number_cycle_power_geapply le_antisymm · unfold simple_graph_equivalence_covering_number exact Nat.sInf_le (simple_graph_equivalence_covering_number_cycle_power_dvd_cover k q hk hq) · exact simple_graph_equivalence_covering_number_cycle_power_ge (q * (k + 1)) k hk (by nlinarith)
Nat.div_le_div_right- for non-negative integers with a ≤ b, a / c ≤ b / c
pow_succ- a ^ (n + 1) = a ^ n * a
pow_succ'- a ^ (n + 1) = a * a ^ n
Nat.div_div_eq_div_mul- division distributes over iterated division: (m / n) / k = m / (n * k)
add_comm- addition is commutative: a + b = b + a
Nat.add_mul_div_right- for z > 0, (x + y * z) / z = x / z + y
Nat.div_eq_of_lt- if a < b, then a / b = 0
zero_add- 0 + a = a
Nat.add_mul_mod_self_right- (x + y * z) % z = x % z
Nat.mod_eq_of_lt- if a < b, then a % b = a
Nat.div_add_mod'- integer division theorem: (a / b) * b + a % b = a
Nat.mod_lt- for y > 0, x % y < y
Nat.div_lt_iff_lt_mul- for k > 0, x / k < y ↔ x < y * k
Nat.zero_le- 0 ≤ n for every natural number n
Nat.lt_or_gt_of_ne- if a ≠ b, then a < b or a > b
Or.inl- left injection into a disjunction: P implies P ∨ Q
Or.inr- right injection into a disjunction: Q implies P ∨ Q
simple_graph_equivalence_covering_number_cycle_power_dvd_decode- for K > 0 and r < K, (J * K + r) / K = J and (J * K + r) % K = r
Nat.div_le_self- for all n and k, n / k ≤ n
Nat.add_mod_right- (x + z) % z = x % z
Nat.succ_mul- (n + 1) * m = n * m + m
Nat.add_mod_left- (x + z) % x = z % x
if_true- the if-then-else evaluates to the true branch when the condition is True
Nat.eq_of_mul_eq_mul_right- if n * m = k * m and m > 0, then n = k
if_false- the if-then-else evaluates to the false branch when the condition is False
Nat.ModEq.add_right_cancel'- if a + c ≡ b + c [MOD n], then a ≡ b [MOD n]
add_assoc- addition is associative: a + b + c = a + (b + c)
Nat.mod_two_eq_zero_or_one- every natural number mod 2 is either 0 or 1
Nat.mul_le_mul_right- if n ≤ m, then n * k ≤ m * k
simple_graph_equivalence_covering_number_cycle_power_dvd_bits- for b < a < 2^L, there is a bit position ℓ < L where a has bit 1, b has bit 0, and they agree on higher bits
Nat.mod_eq_sub_mod- if a ≥ b, then a % b = (a - b) % b
zero_mul- 0 * b = 0 in any ring
ZMod.val_injective- the value map from ZMod n to ℕ is injective
ZMod.val_add- the integer value of a sum in ZMod n is (val a + val b) % n
ZMod.val_cast_of_lt- if a < n, the integer value of the cast of a into ZMod n is a
simple_graph_equivalence_covering_number_cycle_power_ge_adj- vertices u and u + d in C_n^k are adjacent whenever 1 ≤ d ≤ k and d < n
ZMod.val_lt- the integer value of an element of ZMod n is strictly less than n
lt_of_le_of_lt- if a ≤ b and b < c, then a < c
Nat.div_mul_le_self- (m / n) * n ≤ m for all natural numbers m, n
congrArg- equality is preserved under applying a function: a = b implies f a = f b
simple_graph_equivalence_covering_number_cycle_power_dvd_sound- distinct vertices receiving identical labels in layer s have cyclic distance at most k
simple_graph_equivalence_covering_number_cycle_power_dvd_adj- an offset d with 1 ≤ d ≤ k gives adjacency between u and v in C_n^k
Nat.le_pow_clog- x ≤ b ^ ⌈log_b x⌉ for b > 1
Nat.eq_zero_or_pos- every natural number is either zero or positive
ZMod.val_eq_zero- the integer value of an element of ZMod n is 0 if and only if the element is 0
sub_eq_zero- in an additive group, a - b = 0 if and only if a = b
add_sub_cancel- a + (b - a) = b in any additive group
simple_graph_equivalence_covering_number_cycle_power_dvd_complete- vertices at forward distance 1 ≤ d ≤ k share a label in at least one layer s < 1 + L
min_le_iff- min b c ≤ a ↔ b ≤ a ∨ c ≤ a
Ne.symm- inequality is symmetric: a ≠ b implies b ≠ a
le_antisymm- if a ≤ b and b ≤ a, then a = b
Nat.sInf_le- if m is in a set of natural numbers, the infimum of the set is at most m
simple_graph_equivalence_covering_number_cycle_power_dvd_cover- C_{q(k+1)}^k has an equivalence cover of size 1 + ⌈log₂(k + 1)⌉
simple_graph_equivalence_covering_number_cycle_power_ge- the equivalence covering number of C_n^k is at least 1 + ⌈log₂(k + 1)⌉ when 2k + 2 ≤ n
- Linear arithmetic solvers (`omega`, `nlinarith`) and algebraic normalization (`ring`) handle the division, modulo bounds, and index arithmetic across blocks and binary representations without explicit steps.
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.
/-- The label of vertex `i` in the `ℓ`-th binary-digit subgraph: blocks of `K` vertices,`D = (i mod K) / 2^ℓ`; odd `D` joins its own block's class, even `D` the previous one. -/def simple_graph_equivalence_covering_number_cycle_power_dvd_lab (q K ℓ i : ℕ) : ℕ := ((i / K + q - 1 + (i % K / 2 ^ ℓ) % 2) % q) * K + (i % K / 2 ^ ℓ) / 2/-- Two numbers `b < a < 2^L` agree above some bit `ℓ < L` where `a` has a one and `b` a zero. -/theorem simple_graph_equivalence_covering_number_cycle_power_dvd_bits : ∀ (L a b : ℕ), b < a → a < 2 ^ L → ∃ ℓ, ℓ < L ∧ ∃ p, a / 2 ^ ℓ = 2 * p + 1 ∧ b / 2 ^ ℓ = 2 * p := by intro L induction L with | zero => intro a b hab ha; simp at ha; omega | succ L ih => intro a b hab ha by_cases h2 : a / 2 = b / 2 · exact ⟨0, by omega, a / 2, by simp; omega, by simp; omega⟩ · have hle : b / 2 ≤ a / 2 := Nat.div_le_div_right hab.le have ha2 : a / 2 < 2 ^ L := by rw [pow_succ] at ha; omega obtain ⟨ℓ, hℓ, p, hp1, hp2⟩ := ih (a / 2) (b / 2) (by omega) ha2 refine ⟨ℓ + 1, by omega, p, ?_, ?_⟩ · rw [pow_succ', ← Nat.div_div_eq_div_mul]; exact hp1 · rw [pow_succ', ← Nat.div_div_eq_div_mul]; exact hp2theorem simple_graph_equivalence_covering_number_cycle_power_dvd_decode (K J r : ℕ) (hK : 0 < K) (hr : r < K) : (J * K + r) / K = J ∧ (J * K + r) % K = r := by constructor · rw [add_comm, Nat.add_mul_div_right _ _ hK, Nat.div_eq_of_lt hr, zero_add] · rw [add_comm, Nat.add_mul_mod_self_right, Nat.mod_eq_of_lt hr]/-- Labels that agree come from vertices at cyclic distance at most `k`. -/theorem simple_graph_equivalence_covering_number_cycle_power_dvd_sound (k q : ℕ) (hq : 2 ≤ q) (i i' : ℕ) (hi : i < q * (k + 1)) (hi' : i' < q * (k + 1)) (hne : i ≠ i') (s : ℕ) (heq : (if s = 0 then i / (k + 1) * (k + 1) else simple_graph_equivalence_covering_number_cycle_power_dvd_lab q (k + 1) (s - 1) i) = (if s = 0 then i' / (k + 1) * (k + 1) else simple_graph_equivalence_covering_number_cycle_power_dvd_lab q (k + 1) (s - 1) i')) : ∃ d, 1 ≤ d ∧ d ≤ k ∧ ((i + d) % (q * (k + 1)) = i' ∨ (i' + d) % (q * (k + 1)) = i) := by have hK : 0 < k + 1 := by omega have hdi := Nat.div_add_mod' i (k + 1) have hdi' := Nat.div_add_mod' i' (k + 1) have hmi := Nat.mod_lt i hK have hmi' := Nat.mod_lt i' hK have hjq : ∀ m, m < q * (k + 1) → m / (k + 1) < q := fun m hm => (Nat.div_lt_iff_lt_mul hK).mpr hm have hji := hjq i hi have hji' := hjq i' hi' have hz0 := Nat.zero_le (i / (k + 1)) have hz0' := Nat.zero_le (i' / (k + 1)) -- same block have hsame : i / (k + 1) = i' / (k + 1) → ∃ d, 1 ≤ d ∧ d ≤ k ∧ ((i + d) % (q * (k + 1)) = i' ∨ (i' + d) % (q * (k + 1)) = i) := by intro hj rw [hj] at hdi rcases Nat.lt_or_gt_of_ne hne with h | h · exact ⟨i' - i, by omega, by omega, Or.inl (by rw [show i + (i' - i) = i' by omega, Nat.mod_eq_of_lt hi'])⟩ · exact ⟨i - i', by omega, by omega, Or.inr (by rw [show i' + (i - i') = i by omega, Nat.mod_eq_of_lt hi])⟩ -- the oriented cross-block case have hcross : ∀ m m' : ℕ, m < q * (k + 1) → m' < q * (k + 1) → ∀ ℓ, (m % (k + 1) / 2 ^ ℓ) % 2 = 1 → (m' % (k + 1) / 2 ^ ℓ) % 2 = 0 → simple_graph_equivalence_covering_number_cycle_power_dvd_lab q (k + 1) ℓ m = simple_graph_equivalence_covering_number_cycle_power_dvd_lab q (k + 1) ℓ m' → ∃ d, 1 ≤ d ∧ d ≤ k ∧ (m + d) % (q * (k + 1)) = m' := by intro m m' hm hm' ℓ h1 h0 hl unfold simple_graph_equivalence_covering_number_cycle_power_dvd_lab at hl rw [h1, h0] at hl have hdm := Nat.div_add_mod' m (k + 1) have hdm' := Nat.div_add_mod' m' (k + 1) have hmm := Nat.mod_lt m hK have hmm' := Nat.mod_lt m' hK have hjm := hjq m hm have hjm' := hjq m' hm' have hz := Nat.zero_le (m / (k + 1)) have hz' := Nat.zero_le (m' / (k + 1)) have hD : m % (k + 1) / 2 ^ ℓ ≤ m % (k + 1) := Nat.div_le_self _ _ have hD' : m' % (k + 1) / 2 ^ ℓ ≤ m' % (k + 1) := Nat.div_le_self _ _ have hq0 : 0 < q := by omega have hJ := Nat.mod_lt (m / (k + 1) + q - 1 + 1) hq0 have hJ' := Nat.mod_lt (m' / (k + 1) + q - 1 + 0) hq0 obtain ⟨hJJ, hpp⟩ := (by have e1 := simple_graph_equivalence_covering_number_cycle_power_dvd_decode (k + 1) ((m / (k + 1) + q - 1 + 1) % q) (m % (k + 1) / 2 ^ ℓ / 2) hK (by omega) have e2 := simple_graph_equivalence_covering_number_cycle_power_dvd_decode (k + 1) ((m' / (k + 1) + q - 1 + 0) % q) (m' % (k + 1) / 2 ^ ℓ / 2) hK (by omega) rw [hl] at e1 exact ⟨e1.1.symm.trans e2.1, e1.2.symm.trans e2.2⟩ : (m / (k + 1) + q - 1 + 1) % q = (m' / (k + 1) + q - 1 + 0) % q ∧ m % (k + 1) / 2 ^ ℓ / 2 = m' % (k + 1) / 2 ^ ℓ / 2) have hJm : (m / (k + 1) + q - 1 + 1) % q = m / (k + 1) := by rw [show m / (k + 1) + q - 1 + 1 = m / (k + 1) + q by have := Nat.zero_le (m / (k + 1)); omega, Nat.add_mod_right, Nat.mod_eq_of_lt hjm] rw [hJm] at hJJ -- the digit of m is one more than that of m', so m % K > m' % K have hlt : m' % (k + 1) < m % (k + 1) := by by_contra hc push_neg at hc have := Nat.div_le_div_right (c := 2 ^ ℓ) hc omega have hmul : (m / (k + 1) + 1) * (k + 1) = m / (k + 1) * (k + 1) + (k + 1) := by ring refine ⟨k + 1 + m' % (k + 1) - m % (k + 1), by omega, by omega, ?_⟩ by_cases hj0 : m' / (k + 1) = 0 · -- wrap-around: m is in the last block rw [hj0] at hJJ have hlast : m / (k + 1) = q - 1 := by rw [show 0 + q - 1 + 0 = q - 1 by omega, Nat.mod_eq_of_lt (by omega)] at hJJ exact hJJ have hqK : (q - 1) * (k + 1) + (k + 1) = q * (k + 1) := by rw [← Nat.succ_mul]; congr 1; omega rw [hlast] at hdm rw [hj0] at hdm' rw [show m + (k + 1 + m' % (k + 1) - m % (k + 1)) = q * (k + 1) + m' by omega, Nat.add_mod_left, Nat.mod_eq_of_lt hm'] · have hprev : m / (k + 1) + 1 = m' / (k + 1) := by rw [show m' / (k + 1) + q - 1 + 0 = (m' / (k + 1) - 1) + q by omega, Nat.add_mod_right, Nat.mod_eq_of_lt (by omega)] at hJJ omega rw [← hprev] at hdm' rw [show m + (k + 1 + m' % (k + 1) - m % (k + 1)) = m' by omega, Nat.mod_eq_of_lt hm'] by_cases hs : s = 0 · simp only [hs, if_true] at heq exact hsame (Nat.eq_of_mul_eq_mul_right hK heq) · simp only [hs, if_false] at heq by_cases hpar : (i % (k + 1) / 2 ^ (s - 1)) % 2 = (i' % (k + 1) / 2 ^ (s - 1)) % 2 · apply hsame unfold simple_graph_equivalence_covering_number_cycle_power_dvd_lab at heq rw [hpar] at heq have hq0 : 0 < q := by omega have e1 := simple_graph_equivalence_covering_number_cycle_power_dvd_decode (k + 1) ((i / (k + 1) + q - 1 + i' % (k + 1) / 2 ^ (s - 1) % 2) % q) (i % (k + 1) / 2 ^ (s - 1) / 2) hK (by have := Nat.div_le_self (i % (k + 1)) (2 ^ (s - 1)); omega) have e2 := simple_graph_equivalence_covering_number_cycle_power_dvd_decode (k + 1) ((i' / (k + 1) + q - 1 + i' % (k + 1) / 2 ^ (s - 1) % 2) % q) (i' % (k + 1) / 2 ^ (s - 1) / 2) hK (by have := Nat.div_le_self (i' % (k + 1)) (2 ^ (s - 1)); omega) rw [heq] at e1 have hJ := e1.1.symm.trans e2.1 have hmod := Nat.ModEq.add_right_cancel' (q - 1 + i' % (k + 1) / 2 ^ (s - 1) % 2) (show i / (k + 1) + (q - 1 + i' % (k + 1) / 2 ^ (s - 1) % 2) ≡ i' / (k + 1) + (q - 1 + i' % (k + 1) / 2 ^ (s - 1) % 2) [MOD q] by unfold Nat.ModEq rw [← add_assoc, ← add_assoc] rw [show i / (k + 1) + q - 1 = i / (k + 1) + (q - 1) by omega, show i' / (k + 1) + q - 1 = i' / (k + 1) + (q - 1) by omega] at hJ exact hJ) unfold Nat.ModEq at hmod rwa [Nat.mod_eq_of_lt hji, Nat.mod_eq_of_lt hji'] at hmod · rcases Nat.mod_two_eq_zero_or_one (i % (k + 1) / 2 ^ (s - 1)) with h | h · have h' : (i' % (k + 1) / 2 ^ (s - 1)) % 2 = 1 := by omega obtain ⟨d, hd1, hd2, hd⟩ := hcross i' i hi' hi (s - 1) h' h heq.symm exact ⟨d, hd1, hd2, Or.inr hd⟩ · have h' : (i' % (k + 1) / 2 ^ (s - 1)) % 2 = 0 := by omega obtain ⟨d, hd1, hd2, hd⟩ := hcross i i' hi hi' (s - 1) h h' heq exact ⟨d, hd1, hd2, Or.inl hd⟩/-- Vertices at forward distance `d ∈ [1, k]` share a label. -/theorem simple_graph_equivalence_covering_number_cycle_power_dvd_complete (k q L : ℕ) (hq : 2 ≤ q) (hL : k + 1 ≤ 2 ^ L) (i i' d : ℕ) (hi : i < q * (k + 1)) (hi' : i' < q * (k + 1)) (hd1 : 1 ≤ d) (hdk : d ≤ k) (h : (i + d) % (q * (k + 1)) = i') : ∃ s, s < 1 + L ∧ (if s = 0 then i / (k + 1) * (k + 1) else simple_graph_equivalence_covering_number_cycle_power_dvd_lab q (k + 1) (s - 1) i) = (if s = 0 then i' / (k + 1) * (k + 1) else simple_graph_equivalence_covering_number_cycle_power_dvd_lab q (k + 1) (s - 1) i') := by have hK : 0 < k + 1 := by omega have hq0 : 0 < q := by omega have hdi := Nat.div_add_mod' i (k + 1) have hmi := Nat.mod_lt i hK have hj0 := Nat.zero_le (i / (k + 1)) have hn2 : 2 * (k + 1) ≤ q * (k + 1) := Nat.mul_le_mul_right _ hq have hji : i / (k + 1) < q := (Nat.div_lt_iff_lt_mul hK).mpr hi have hmul : (i / (k + 1) + 1) * (k + 1) = i / (k + 1) * (k + 1) + (k + 1) := by ring have hsame : i' / (k + 1) = i / (k + 1) → ∃ s, s < 1 + L ∧ (if s = 0 then i / (k + 1) * (k + 1) else simple_graph_equivalence_covering_number_cycle_power_dvd_lab q (k + 1) (s - 1) i) = (if s = 0 then i' / (k + 1) * (k + 1) else simple_graph_equivalence_covering_number_cycle_power_dvd_lab q (k + 1) (s - 1) i') := by intro hj exact ⟨0, by omega, by simp [hj]⟩ have hcross : ∀ j' a', i' / (k + 1) = j' → i' % (k + 1) = a' → a' < i % (k + 1) → (j' = i / (k + 1) + 1 ∨ (i / (k + 1) = q - 1 ∧ j' = 0)) → ∃ s, s < 1 + L ∧ (if s = 0 then i / (k + 1) * (k + 1) else simple_graph_equivalence_covering_number_cycle_power_dvd_lab q (k + 1) (s - 1) i) = (if s = 0 then i' / (k + 1) * (k + 1) else simple_graph_equivalence_covering_number_cycle_power_dvd_lab q (k + 1) (s - 1) i') := by intro j' a' hj' ha' hlt hcase obtain ⟨ℓ, hℓ, p, hp1, hp2⟩ := simple_graph_equivalence_covering_number_cycle_power_dvd_bits L (i % (k + 1)) a' hlt (by omega) refine ⟨ℓ + 1, by omega, ?_⟩ simp only [show ℓ + 1 ≠ 0 by omega, if_false, show ℓ + 1 - 1 = ℓ by omega] unfold simple_graph_equivalence_covering_number_cycle_power_dvd_lab rw [hp1, hj', ha', hp2, show (2 * p + 1) % 2 = 1 by omega, show (2 * p + 1) / 2 = p by omega, show 2 * p % 2 = 0 by omega, show 2 * p / 2 = p by omega] congr 2 rw [show i / (k + 1) + q - 1 + 1 = i / (k + 1) + q by omega, Nat.add_mod_right, Nat.mod_eq_of_lt hji] rcases hcase with hc | ⟨hc1, hc2⟩ · rw [hc, show i / (k + 1) + 1 + q - 1 + 0 = i / (k + 1) + q by omega, Nat.add_mod_right, Nat.mod_eq_of_lt hji] · rw [hc2, hc1, show 0 + q - 1 + 0 = q - 1 by omega, Nat.mod_eq_of_lt (by omega)] by_cases hwrap : i + d < q * (k + 1) · rw [Nat.mod_eq_of_lt hwrap] at h by_cases hsm : i % (k + 1) + d < k + 1 · apply hsame have e := simple_graph_equivalence_covering_number_cycle_power_dvd_decode (k + 1) (i / (k + 1)) (i % (k + 1) + d) hK hsm rw [show i / (k + 1) * (k + 1) + (i % (k + 1) + d) = i' by omega] at e exact e.1 · have e := simple_graph_equivalence_covering_number_cycle_power_dvd_decode (k + 1) (i / (k + 1) + 1) (i % (k + 1) + d - (k + 1)) hK (by omega) rw [show (i / (k + 1) + 1) * (k + 1) + (i % (k + 1) + d - (k + 1)) = i' by omega] at e exact hcross _ _ e.1 e.2 (by omega) (Or.inl rfl) · have h' : i' = i + d - q * (k + 1) := by rw [Nat.mod_eq_sub_mod (by omega), Nat.mod_eq_of_lt (by omega)] at h exact h.symm have hlast : i / (k + 1) = q - 1 := by by_contra hc have hle : i / (k + 1) + 1 + 1 ≤ q := by omega have := Nat.mul_le_mul_right (k + 1) hle rw [Nat.succ_mul] at this omega have hqK : (q - 1) * (k + 1) + (k + 1) = q * (k + 1) := by rw [← Nat.succ_mul]; congr 1; omega rw [hlast] at hdi have e := simple_graph_equivalence_covering_number_cycle_power_dvd_decode (k + 1) 0 i' hK (by omega) rw [zero_mul, zero_add] at e exact hcross 0 i' e.1 e.2 (by omega) (Or.inr ⟨hlast, rfl⟩)/-- Forward distance `d ∈ [1, k]` in values gives adjacency in `C_n^k`. -/theorem simple_graph_equivalence_covering_number_cycle_power_dvd_adj (n k : ℕ) [NeZero n] (u v : ZMod n) (d : ℕ) (hd1 : 1 ≤ d) (hdk : d ≤ k) (hdn : d < n) (h : (u.val + d) % n = v.val) : (simple_graph_cycle_power n k).Adj u v := by have hv : v = u + (d : ZMod n) := by apply ZMod.val_injective rw [ZMod.val_add, ZMod.val_cast_of_lt hdn] exact h.symm rw [hv] exact simple_graph_equivalence_covering_number_cycle_power_ge_adj n k u d hd1 hdk hdn/-- The cover of `C_{q(k+1)}^k` by `1 + ⌈log₂(k+1)⌉` equivalence subgraphs: the blocks of`k + 1` consecutive vertices, and one subgraph per binary digit. -/theorem simple_graph_equivalence_covering_number_cycle_power_dvd_cover (k q : ℕ) (hk : 1 ≤ k) (hq : 2 ≤ q) : simple_graph_has_equivalence_cover (simple_graph_cycle_power (q * (k + 1)) k) (1 + Nat.clog 2 (k + 1)) := by classical have : NeZero (q * (k + 1)) := ⟨by positivity⟩ have hK : 0 < k + 1 := by omega have hq0 : 0 < q := by omega have hn : 2 * k + 2 ≤ q * (k + 1) := by nlinarith refine ⟨fun s v => (((if s.val = 0 then v.val / (k + 1) * (k + 1) else simple_graph_equivalence_covering_number_cycle_power_dvd_lab q (k + 1) (s.val - 1) v.val) : ℕ) : ZMod (q * (k + 1))), ?_, ?_⟩ · intro s u v huv h have hb : ∀ w : ZMod (q * (k + 1)), (if s.val = 0 then w.val / (k + 1) * (k + 1) else simple_graph_equivalence_covering_number_cycle_power_dvd_lab q (k + 1) (s.val - 1) w.val) < q * (k + 1) := by intro w have hw := ZMod.val_lt w split_ifs · exact lt_of_le_of_lt (Nat.div_mul_le_self _ _) hw · unfold simple_graph_equivalence_covering_number_cycle_power_dvd_lab have hJ := Nat.mod_lt (w.val / (k + 1) + q - 1 + w.val % (k + 1) / 2 ^ (s.val - 1) % 2) hq0 have hD := Nat.div_le_self (w.val % (k + 1)) (2 ^ (s.val - 1)) have hm := Nat.mod_lt w.val hK have hle := Nat.mul_le_mul_right (k + 1) (show (w.val / (k + 1) + q - 1 + w.val % (k + 1) / 2 ^ (s.val - 1) % 2) % q + 1 ≤ q from hJ) rw [Nat.succ_mul] at hle omega have hnat := congrArg ZMod.val h simp only at hnat rw [ZMod.val_cast_of_lt (hb u), ZMod.val_cast_of_lt (hb v)] at hnat have hne : u.val ≠ v.val := fun h' => huv (ZMod.val_injective _ h') obtain ⟨d, hd1, hd2, hd⟩ := simple_graph_equivalence_covering_number_cycle_power_dvd_sound k q hq u.val v.val (ZMod.val_lt u) (ZMod.val_lt v) hne s.val hnat rcases hd with hd | hd · exact simple_graph_equivalence_covering_number_cycle_power_dvd_adj _ k u v d hd1 hd2 (by omega) hd · exact (simple_graph_equivalence_covering_number_cycle_power_dvd_adj _ k v u d hd1 hd2 (by omega) hd).symm · have hL : k + 1 ≤ 2 ^ Nat.clog 2 (k + 1) := Nat.le_pow_clog (by norm_num) _ have key : ∀ u v : ZMod (q * (k + 1)), u ≠ v → (v - u).val ≤ k → ∃ s : Fin (1 + Nat.clog 2 (k + 1)), (((if s.val = 0 then u.val / (k + 1) * (k + 1) else simple_graph_equivalence_covering_number_cycle_power_dvd_lab q (k + 1) (s.val - 1) u.val) : ℕ) : ZMod (q * (k + 1))) = (((if s.val = 0 then v.val / (k + 1) * (k + 1) else simple_graph_equivalence_covering_number_cycle_power_dvd_lab q (k + 1) (s.val - 1) v.val) : ℕ) : ZMod (q * (k + 1))) := by intro u v hne hle have hd1 : 1 ≤ (v - u).val := by rcases Nat.eq_zero_or_pos (v - u).val with h0 | h0 · rw [ZMod.val_eq_zero, sub_eq_zero] at h0 exact absurd h0.symm hne · exact h0 have hmod : (u.val + (v - u).val) % (q * (k + 1)) = v.val := by rw [← ZMod.val_add, add_sub_cancel] obtain ⟨s, hs, heq⟩ := simple_graph_equivalence_covering_number_cycle_power_dvd_complete k q (Nat.clog 2 (k + 1)) hq hL u.val v.val (v - u).val (ZMod.val_lt u) (ZMod.val_lt v) hd1 hle hmod exact ⟨⟨s, hs⟩, by simp only; rw [heq]⟩ intro u v huv obtain ⟨hne, hmin⟩ := huv rcases min_le_iff.mp hmin with h | h · obtain ⟨s, hs⟩ := key v u (Ne.symm hne) h exact ⟨s, hs.symm⟩ · exact key u v hne htheorem simple_graph_equivalence_covering_number_cycle_power_dvd (k q : ℕ) (hk : 1 ≤ k) (hq : 2 ≤ q) : simple_graph_equivalence_covering_number (simple_graph_cycle_power (q * (k + 1)) k) = 1 + Nat.clog 2 (k + 1) := by apply le_antisymm · unfold simple_graph_equivalence_covering_number exact Nat.sInf_le (simple_graph_equivalence_covering_number_cycle_power_dvd_cover k q hk hq) · exact simple_graph_equivalence_covering_number_cycle_power_ge (q * (k + 1)) k hk (by nlinarith)