AFTD Auto-Formalizing Theoretical Domains

circulant_cycle_not_all_edge_steps

theoremverified

An injective sequence on Fin N cannot have every cyclic step equal to m when t ≥ 3 and N = 2m, because two steps of jump m return to the starting vertex.

Statement

theorem circulant_cycle_not_all_edge_steps {t N m : ℕ} (ht : 3 ≤ t) (hN : N = 2 * m) (hm : 0 < m)
    (x : Fin t → Fin N) (hinj : Function.Injective x) :
    ¬ (∀ i : Fin t, (x (finRotate t i) - x i).val = m)
Source
step towards circulant_mixed_graph_no_cycle_lt_g
Verified
23 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

The theorem is proved by contradiction using two auxiliary results about modular arithmetic and cyclic permutations. First, any cyclic difference of m in Fin N (with N = 2m) corresponds to adding m modulo N, so two consecutive steps advance the value by 2m = N ≡ 0 [MOD N], returning to the starting vertex. By injectivity of x, this forces rotating twice in Fin t to fix the starting index. Finally, a helper lemma shows that rotating twice on Fin t has no fixed points whenever t ≥ 3, yielding the contradiction.

  1. The cyclic difference condition (b - a).val = m implies N - a.val + b.val ≡ m [MOD N].

    By definition of subtraction in Fin N (Fin.val_sub), (b - a).val equals (N - a.val + b.val) % N. Since N = 2m with m > 0, we have m < N, so m % N = m, giving the congruence modulo N.

    lines 4–8

    uses Fin.val_sub, Nat.ModEq, Nat.mod_eq_of_lt

      have hsub : (N - a.val + b.val) % N = m := by
        simpa [Fin.val_sub] using h
      have hmN : m < N := by omega
      have hmod : N - a.val + b.val ≡ m [MOD N] := by
        rw [Nat.ModEq, hsub, Nat.mod_eq_of_lt hmN]
  2. Adding a.val to both sides yields N + b.val ≡ a.val + m [MOD N].

    Adding a.val to both sides using Nat.ModEq.add_left and simplifying a.val + (N - a.val + b.val) to N + b.val via linear arithmetic gives the congruence N + b.val ≡ a.val + m [MOD N].

    lines 9–12

    uses Nat.ModEq.add_left

      have h1 : N + b.val ≡ a.val + m [MOD N] := by
        have := Nat.ModEq.add_left a.val hmod
        have hEq : a.val + (N - a.val + b.val) = N + b.val := by omega
        simpa [hEq] using this
  3. Cancelling N modulo N proves the single-step lemma: b.val ≡ a.val + m [MOD N].

    Since N ≡ 0 [MOD N], adding b.val gives N + b.val ≡ b.val [MOD N]. Combining this with N + b.val ≡ a.val + m [MOD N] by symmetry and transitivity establishes b.val ≡ a.val + m [MOD N].

    lines 13–16

    uses Nat.ModEq, Nat.mod_self, Nat.zero_mod, Nat.ModEq.add, Nat.ModEq.refl

      have hN0 : N ≡ 0 [MOD N] := by rw [Nat.ModEq, Nat.mod_self, Nat.zero_mod]
      have hNB : N + b.val ≡ b.val [MOD N] := by
        simpa using Nat.ModEq.add hN0 (Nat.ModEq.refl b.val)
      exact hNB.symm.trans h1
  4. Assuming rotating twice fixes an index i in Fin t implies i + 2 ≡ i [MOD t].

    Assuming finRotate t (finRotate t i) = i, we rewrite each rotation as adding 1 (finRotate_apply), giving (i + 1) + 1 = i in Fin t. Converting this to an equality of natural numbers using Fin.val_add and simplifying gives (i + 2) % t = i, which is the congruence i + 2 ≡ i [MOD t].

    lines 20–27

    uses finRotate_apply, Fin.val_add, Nat.ModEq, Nat.mod_eq_of_lt

      haveI : NeZero t := ⟨by omega⟩
      intro h
      rw [finRotate_apply, finRotate_apply] at h
      have hv : (↑((i + 1) + 1) : ℕ) = ↑i := by rw [h]
      rw [Fin.val_add, Fin.val_add] at hv
      norm_num at hv
      have hmod : ↑i + 2 ≡ ↑i [MOD t] := by
        rw [Nat.ModEq, hv, Nat.mod_eq_of_lt i.isLt]
  5. Rotating twice cannot fix i when t ≥ 3.

    Cancelling i from i + 2 ≡ i [MOD t] yields 2 ≡ 0 [MOD t], so t divides 2, which implies t ≤ 2. But this directly contradicts the hypothesis 3 ≤ t, closing the proof of the rotation lemma.

    lines 28–32

    uses Nat.ModEq.add_left_cancel', Nat.modEq_zero_iff_dvd.mp, Nat.le_of_dvd

      have h2 : 2 ≡ 0 [MOD t] := by
        exact Nat.ModEq.add_left_cancel' (↑i) hmod
      have hdvd : t ∣ 2 := Nat.modEq_zero_iff_dvd.mp h2
      have hle : t ≤ 2 := Nat.le_of_dvd (by norm_num) hdvd
      omega
  6. Assume for contradiction that every cyclic step has difference m, and choose an initial index i = 0 in Fin t.

    We assume for contradiction that (x (finRotate t i) - x i).val = m for all i. Since t ≥ 3 > 0, we can choose i = 0 as a valid element of Fin t.

    lines 38–39

      intro h
      let i : Fin t := ⟨0, by omega⟩
  7. Each of the two cyclic steps starting from i advances the sequence value by m modulo N.

    Applying the single-step lemma circulant_cycle_not_all_edge_steps_step at index i and at index finRotate t i shows that x (finRotate t i) ≡ x i + m [MOD N] and x (finRotate t (finRotate t i)) ≡ x (finRotate t i) + m [MOD N].

    lines 40–43

    uses circulant_cycle_not_all_edge_steps_step

      have h1 : (x (finRotate t i)).val ≡ (x i).val + m [MOD N] :=
        circulant_cycle_not_all_edge_steps_step hN hm (h i)
      have h2 : (x (finRotate t (finRotate t i))).val ≡ (x (finRotate t i)).val + m [MOD N] :=
        circulant_cycle_not_all_edge_steps_step hN hm (h (finRotate t i))
  8. Two consecutive cyclic steps return to the initial value modulo N: x (finRotate t (finRotate t i)) ≡ x i [MOD N].

    Adding m to both sides of the first step gives x (finRotate t i) + m ≡ x i + m + m [MOD N], so by transitivity x (finRotate t (finRotate t i)) ≡ x i + m + m [MOD N]. Since 2m = N and N ≡ 0 [MOD N], x i + m + m = x i + N ≡ x i [MOD N].

    lines 44–54

    uses Nat.add_assoc, Nat.ModEq.add_right, Nat.ModEq, Nat.mod_self, Nat.zero_mod, Nat.ModEq.add, Nat.ModEq.refl

      have hC : (x (finRotate t (finRotate t i))).val ≡ (x i).val [MOD N] := by
        have h1' : (x (finRotate t i)).val + m ≡ (x i).val + m + m [MOD N] := by
          simpa [Nat.add_assoc] using Nat.ModEq.add_right m h1
        have hC' : (x (finRotate t (finRotate t i))).val ≡ (x i).val + m + m [MOD N] := h2.trans h1'
        have hAN : (x i).val + m + m ≡ (x i).val [MOD N] := by
          have hN0 : N ≡ 0 [MOD N] := by rw [Nat.ModEq, Nat.mod_self, Nat.zero_mod]
          have h := Nat.ModEq.add (Nat.ModEq.refl (x i).val) hN0
          have hAN' : (x i).val + N ≡ (x i).val [MOD N] := by simpa using h
          rw [show (x i).val + m + m = (x i).val + N by omega]
          exact hAN'
        exact hC'.trans hAN
  9. The sequence values after two steps are equal: x (finRotate t (finRotate t i)) = x i.

    Because both sequence values are strictly less than N, their modular congruence implies that their values as natural numbers are equal, which by Fin.ext means the elements of Fin N are equal.

    lines 55–57

    uses Fin.ext, Nat.ModEq.eq_of_lt_of_lt

      have hx : x (finRotate t (finRotate t i)) = x i := by
        apply Fin.ext
        exact Nat.ModEq.eq_of_lt_of_lt hC (x _).isLt (x i).isLt
  10. Injectivity of x forces rotating twice to fix i, contradicting t ≥ 3.

    By injectivity of x, x (finRotate t (finRotate t i)) = x i implies finRotate t (finRotate t i) = i. But circulant_cycle_not_all_edge_steps_rot_two_ne proves that rotating twice never fixes any index when t ≥ 3, which completes the proof by contradiction.

    lines 58–59

    uses circulant_cycle_not_all_edge_steps_rot_two_ne

      have hperm : finRotate t (finRotate t i) = i := hinj hx
      exact (circulant_cycle_not_all_edge_steps_rot_two_ne ht i) hperm
Fin.val_sub
The natural value of a difference a - b in Fin n equals (n - a.val + b.val) % n.
Nat.ModEq
Modular equivalence a ≡ b [MOD n] is defined as equality of remainders a % n = b % n.
Nat.mod_eq_of_lt
A natural number strictly less than the modulus equals its remainder: if a < b then a % b = a.
Nat.ModEq.add_left
Modular congruence is preserved by adding a constant on the left: if a ≡ b [MOD n] then c + a ≡ c + b [MOD n].
Nat.mod_self
Any natural number modulo itself is zero: n % n = 0.
Nat.zero_mod
Zero modulo any natural number is zero: 0 % b = 0.
Nat.ModEq.add
Modular congruences can be added: if a ≡ b [MOD n] and c ≡ d [MOD n], then a + c ≡ b + d [MOD n].
Nat.ModEq.refl
Modular congruence is reflexive: a ≡ a [MOD n].
finRotate_apply
The cyclic rotation permutation maps each element i in Fin n to i + 1.
Fin.val_add
The natural value of a sum a + b in Fin n equals (a.val + b.val) % n.
Nat.ModEq.add_left_cancel'
A constant added on the left can be cancelled in a modular congruence: c + a ≡ c + b [MOD n] implies a ≡ b [MOD n].
Nat.modEq_zero_iff_dvd.mp
A modular congruence m ≡ 0 [MOD n] implies that n divides m.
Nat.le_of_dvd
If m divides a strictly positive natural number n, then m ≤ n.
circulant_cycle_not_all_edge_steps_step
In Fin N with N = 2m and m > 0, if the cyclic difference b - a has value m, then b.val ≡ a.val + m [MOD N].
Nat.add_assoc
Addition of natural numbers is associative: n + m + k = n + (m + k).
Nat.ModEq.add_right
Modular congruence is preserved by adding a constant on the right: if a ≡ b [MOD n] then a + c ≡ b + c [MOD n].
Fin.ext
Two elements of Fin n are equal if and only if their underlying natural values are equal.
Nat.ModEq.eq_of_lt_of_lt
If two natural numbers are congruent modulo m and both are strictly less than m, then they are equal.
circulant_cycle_not_all_edge_steps_rot_two_ne
On a cycle of length t ≥ 3, rotating twice never fixes any element.

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

lemma circulant_cycle_not_all_edge_steps_step {N m : ℕ} (hN : N = 2 * m) (hm : 0 < m)    {a b : Fin N} (h : (b - a).val = m) :    (b.val : ℕ) ≡ a.val + m [MOD N] := by  have hsub : (N - a.val + b.val) % N = m := by    simpa [Fin.val_sub] using h  have hmN : m < N := by omega  have hmod : N - a.val + b.val ≡ m [MOD N] := by    rw [Nat.ModEq, hsub, Nat.mod_eq_of_lt hmN]  have h1 : N + b.val ≡ a.val + m [MOD N] := by    have := Nat.ModEq.add_left a.val hmod    have hEq : a.val + (N - a.val + b.val) = N + b.val := by omega    simpa [hEq] using this  have hN0 : N ≡ 0 [MOD N] := by rw [Nat.ModEq, Nat.mod_self, Nat.zero_mod]  have hNB : N + b.val ≡ b.val [MOD N] := by    simpa using Nat.ModEq.add hN0 (Nat.ModEq.refl b.val)  exact hNB.symm.trans h1lemma circulant_cycle_not_all_edge_steps_rot_two_ne {t : ℕ} (ht : 3 ≤ t) (i : Fin t) :    finRotate t (finRotate t i) ≠ i := by  haveI : NeZero t := ⟨by omega⟩  intro h  rw [finRotate_apply, finRotate_apply] at h  have hv : (↑((i + 1) + 1) : ℕ) = ↑i := by rw [h]  rw [Fin.val_add, Fin.val_add] at hv  norm_num at hv  have hmod : ↑i + 2 ≡ ↑i [MOD t] := by    rw [Nat.ModEq, hv, Nat.mod_eq_of_lt i.isLt]  have h2 : 2 ≡ 0 [MOD t] := by    exact Nat.ModEq.add_left_cancel' (↑i) hmod  have hdvd : t ∣ 2 := Nat.modEq_zero_iff_dvd.mp h2  have hle : t ≤ 2 := Nat.le_of_dvd (by norm_num) hdvd  omega/-- An injective sequence on Fin N cannot have every cyclic step equal to m when t ≥ 3 and N = 2m, because two steps of jump m return to the starting vertex. -/theorem circulant_cycle_not_all_edge_steps {t N m : ℕ} (ht : 3 ≤ t) (hN : N = 2 * m) (hm : 0 < m)    (x : Fin t → Fin N) (hinj : Function.Injective x) :    ¬ (∀ i : Fin t, (x (finRotate t i) - x i).val = m) := by  intro h  let i : Fin t := ⟨0, by omega⟩  have h1 : (x (finRotate t i)).val ≡ (x i).val + m [MOD N] :=    circulant_cycle_not_all_edge_steps_step hN hm (h i)  have h2 : (x (finRotate t (finRotate t i))).val ≡ (x (finRotate t i)).val + m [MOD N] :=    circulant_cycle_not_all_edge_steps_step hN hm (h (finRotate t i))  have hC : (x (finRotate t (finRotate t i))).val ≡ (x i).val [MOD N] := by    have h1' : (x (finRotate t i)).val + m ≡ (x i).val + m + m [MOD N] := by      simpa [Nat.add_assoc] using Nat.ModEq.add_right m h1    have hC' : (x (finRotate t (finRotate t i))).val ≡ (x i).val + m + m [MOD N] := h2.trans h1'    have hAN : (x i).val + m + m ≡ (x i).val [MOD N] := by      have hN0 : N ≡ 0 [MOD N] := by rw [Nat.ModEq, Nat.mod_self, Nat.zero_mod]      have h := Nat.ModEq.add (Nat.ModEq.refl (x i).val) hN0      have hAN' : (x i).val + N ≡ (x i).val [MOD N] := by simpa using h      rw [show (x i).val + m + m = (x i).val + N by omega]      exact hAN'    exact hC'.trans hAN  have hx : x (finRotate t (finRotate t i)) = x i := by    apply Fin.ext    exact Nat.ModEq.eq_of_lt_of_lt hC (x _).isLt (x i).isLt  have hperm : finRotate t (finRotate t i) = i := hinj hx  exact (circulant_cycle_not_all_edge_steps_rot_two_ne ht i) hperm
See it in the graphDiscuss this resultChallenge it