AFTD Auto-Formalizing Theoretical Domains

circulant_cycle_val_sub_sum_dvd

theoremverified

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

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.

  1. 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`.

    lines 4–5

    uses ZMod.natCast_eq_zero_iff

      rw [← ZMod.natCast_eq_zero_iff]
      push_cast
  2. 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`.

    lines 6–11

    uses Fin.val_sub, ZMod.natCast_mod, Nat.cast_sub, le_of_lt, ZMod.natCast_self, zero_sub

      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
  3. 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`).

    lines 12–13

    uses Finset.sum_sub_distrib, Equiv.sum_comp, sub_self

      simp_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`.

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