circulant_cycle_not_all_edge_steps
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
- circulant_mixed_graph_no_cycle_lt_gFor z ≥ 1 and g ≥ 3, the circulant mixed graph on N(z, g) vertices contains no mixed cycle of length t < g.
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.
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.
uses
Fin.val_sub,Nat.ModEq,Nat.mod_eq_of_lthave 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]
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].
uses
Nat.ModEq.add_lefthave 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
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].
uses
Nat.ModEq,Nat.mod_self,Nat.zero_mod,Nat.ModEq.add,Nat.ModEq.reflhave 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
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].
uses
finRotate_apply,Fin.val_add,Nat.ModEq,Nat.mod_eq_of_lthaveI : 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]
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.
uses
Nat.ModEq.add_left_cancel',Nat.modEq_zero_iff_dvd.mp,Nat.le_of_dvdhave 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
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.
intro h let i : Fin t := ⟨0, by omega⟩
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].
uses
circulant_cycle_not_all_edge_steps_stephave 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))
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].
uses
Nat.add_assoc,Nat.ModEq.add_right,Nat.ModEq,Nat.mod_self,Nat.zero_mod,Nat.ModEq.add,Nat.ModEq.reflhave 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
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.
uses
Fin.ext,Nat.ModEq.eq_of_lt_of_lthave 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
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.
uses
circulant_cycle_not_all_edge_steps_rot_two_nehave 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
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.
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