AFTD Auto-Formalizing Theoretical Domains

simple_graph_equivalence_covering_number_cycle_power_dvd

theoremverifiedformalization

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
Used by 2

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)⌉.

  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.

    lines 9–21

    uses Nat.div_le_div_right, pow_succ, pow_succ', Nat.div_div_eq_div_mul

      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 hp2
  2. 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.

    lines 25–27

    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_lt

      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]
  3. 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.

    lines 37–57

    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_lt

      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])⟩
  4. 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.

    lines 59–119

    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_left

      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']
  5. 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.

    lines 120–155

    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.inl

      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⟩
  6. 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.

    lines 167–202

    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_lt

      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)]
  7. 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.

    lines 203–230

    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.inr

      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⟩)
  8. 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.

    lines 236–241

    uses ZMod.val_injective, ZMod.val_add, ZMod.val_cast_of_lt, simple_graph_equivalence_covering_number_cycle_power_ge_adj

      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
  9. 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.

    lines 249–283

    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_adj

      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
  10. 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.

    lines 284–309

    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
  11. 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).

    lines 314–318

    uses le_antisymm, Nat.sInf_le, simple_graph_equivalence_covering_number_cycle_power_dvd_cover, simple_graph_equivalence_covering_number_cycle_power_ge

      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)
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

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

/-- 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)
See it in the graphDiscuss this resultChallenge it