circulant_cycle_val_sub_sum_dvd
The sum of cyclic differences of any function x : Fin t → Fin N is a multiple of N.
Statement
theorem circulant_cycle_val_sub_sum_dvd {t N : ℕ} (x : Fin t → Fin N) :
N ∣ ∑ i : Fin t, (x (finRotate t i) - x i).val- 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
To show that the sum of cyclic differences of a function x : Fin t → Fin N is divisible by N, the goal is recast as showing that the sum is zero in ℤ/Nℤ. Each cyclic difference modulo N algebraically equals x(finRotate t i).val - x(i).val in ℤ/Nℤ. Distributing the sum splits it into two identical sums because the cyclic shift is a permutation of the index set Fin t, so their difference is zero.
Divisibility by N reduces to showing that the sum of cyclic differences is zero in ℤ/Nℤ.
An integer sum is divisible by N if and only if its canonical image in ℤ/Nℤ is zero (`ZMod.natCast_eq_zero_iff`). Pushing the cast into the summation (`push_cast`) reduces the goal to showing that `∑ i, ((x (finRotate t i) - x i).val : ZMod N) = 0`.
uses
ZMod.natCast_eq_zero_iffrw [← ZMod.natCast_eq_zero_iff] push_cast
For each index i, the value of the cyclic difference modulo N equals the algebraic difference x(finRotate t i).val - x(i).val in ℤ/Nℤ.
By the definition of subtraction in `Fin N`, `(a - b).val = (N - b.val + a.val) % N` (`Fin.val_sub`). Modulo N, the outer remainder is identity (`ZMod.natCast_mod`). Pushing the cast and using `x(i).val < N` (`le_of_lt`) converts the natural subtraction `N - x(i).val` into `↑N - ↑(x(i).val)` (`Nat.cast_sub`). Since `N = 0` in `ZMod N` (`ZMod.natCast_self`), `0 - ↑(x(i).val)` simplifies to `-↑(x(i).val)` (`zero_sub`), and ring arithmetic (`ring`) rearranges the expression into `x(finRotate t i).val - x(i).val`.
uses
Fin.val_sub,ZMod.natCast_mod,Nat.cast_sub,le_of_lt,ZMod.natCast_self,zero_subhave h (i : Fin t) : (((x (finRotate t i) - x i).val : ZMod N) : ZMod N) = (x (finRotate t i)).val - (x i).val := by rw [Fin.val_sub, ZMod.natCast_mod] push_cast rw [Nat.cast_sub (le_of_lt (x i).isLt), ZMod.natCast_self, zero_sub] ring
The total sum of cyclic differences vanishes in ℤ/Nℤ.
Rewriting each summand using the identity `h` (`simp_rw [h]`) yields `∑ i, (x(finRotate t i).val - x(i).val)`. Distributing the sum over subtraction (`Finset.sum_sub_distrib`) splits this into `(∑ i, x(finRotate t i).val) - (∑ i, x(i).val)`. Because cyclic rotation `finRotate t` is a permutation of `Fin t`, re-indexing the first sum via `Equiv.sum_comp` makes the two sums identical, and their difference is zero (`sub_self`).
uses
Finset.sum_sub_distrib,Equiv.sum_comp,sub_selfsimp_rw [h] rw [Finset.sum_sub_distrib, Equiv.sum_comp (finRotate t) (fun i => ((x i).val : ZMod N)), sub_self]
ZMod.natCast_eq_zero_iff- In `ZMod b`, the natural cast of `a` is zero if and only if `b ∣ a`.
Fin.val_sub- For `a, b : Fin n`, the natural value of `a - b` is `(n - b.val + a.val) % n`.
ZMod.natCast_mod- In `ZMod n`, casting `a % n` is equal to casting `a`.
Nat.cast_sub- For natural numbers `m ≤ n`, the cast of `n - m` into an additive group equals `↑n - ↑m`.
le_of_lt- Strict inequality `a < b` implies non-strict inequality `a ≤ b`.
ZMod.natCast_self- In `ZMod n`, the modulus `n` casts to zero.
zero_sub- Subtracting an element from zero gives its negation: `0 - a = -a`.
Finset.sum_sub_distrib- The sum of differences over a finite set equals the difference of the sums: `∑ (f - g) = ∑ f - ∑ g`.
Equiv.sum_comp- Summing a function over a finite domain is invariant under precomposition with an equivalence (permutation).
sub_self- Subtracting an element from itself yields zero: `a - a = 0`.
- In Lean, subtraction on `Fin N` is defined on underlying natural numbers as `(N - b.val + a.val) % N`, so establishing that its image in `ZMod N` equals the algebraic difference `a.val - b.val` requires explicitly expanding this definition and simplifying modulo `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
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 sum of cyclic differences of any function x : Fin t → Fin N is a multiple of N. -/theorem circulant_cycle_val_sub_sum_dvd {t N : ℕ} (x : Fin t → Fin N) : N ∣ ∑ i : Fin t, (x (finRotate t i) - x i).val := by rw [← ZMod.natCast_eq_zero_iff] push_cast have h (i : Fin t) : (((x (finRotate t i) - x i).val : ZMod N) : ZMod N) = (x (finRotate t i)).val - (x i).val := by rw [Fin.val_sub, ZMod.natCast_mod] push_cast rw [Nat.cast_sub (le_of_lt (x i).isLt), ZMod.natCast_self, zero_sub] ring simp_rw [h] rw [Finset.sum_sub_distrib, Equiv.sum_comp (finRotate t) (fun i => ((x i).val : ZMod N)), sub_self]