Geometric Sum of Primitive Root Powers

StatusFully Proven
TypeTheorem
ModuleChebyshevCircles.Proofs.PowerSums

Statement

Theorem Geometric Sum of Primitive Root Powers

For $0 < m < N$, $\sum_{k=0}^{N-1} \omega^{km} = 0$ where $\omega = e^{2\pi i/N}$.

theorem sum_primitive_root_pow_mul (N m : ) (hN : 0 < N) (hm : 0 < m) (hm' : m < N) :
    let ω :=
Proof

 Complex.exp (2 * π * Complex.I / N)
     k  Finset.range N, ω ^ (k * m) = 0 := by
  intro ω
  have hN' : N  0 := Nat.pos_iff_ne_zero.mp hN
  have  : IsPrimitiveRoot ω N := Complex.isPrimitiveRoot_exp N hN'
  conv_lhs => arg 2; ext k; rw [mul_comm k m, pow_mul]
  have h_ne_one : ω ^ m  1 := by
    intro h_eq
    have h_div : N  m := (hω.pow_eq_one_iff_dvd m).mp h_eq
    have : N  m := Nat.le_of_dvd hm h_div
    omega
  have h_pow_N : (ω ^ m) ^ N = 1 := by
    calc (ω ^ m) ^ N = ω ^ (m * N) := by rw [ pow_mul]
      _ = ω ^ (N * m) := by rw [mul_comm]
      _ = (ω ^ N) ^ m := by rw [ pow_mul]
      _ = 1 ^ m := by rw [hω.pow_eq_one]
      _ = 1 := one_pow m
  have h_geom : (ω ^ m - 1) *  k  Finset.range N, (ω ^ m) ^ k = (ω ^ m) ^ N - 1 :=
    mul_geom_sum (ω ^ m) N
  rw [h_pow_N] at h_geom
  have h_eq_zero : (ω ^ m - 1) *  k  Finset.range N, (ω ^ m) ^ k = 0 := by
    rw [h_geom]; ring
  exact eq_zero_of_ne_zero_of_mul_left_eq_zero (sub_ne_zero_of_ne h_ne_one) h_eq_zero

Dependencies (uses)

None

Dependents (used by)

None

Neighborhood

Legend
Not Ready
Work in Progress
Sorry (theorems only)
Proven/Defined
Fully Proven (theorems only)
Axiom
Mathlib Ready
Theorems/Lemmas
Definitions
Axioms