Clifford project

2. Roots of unity🔗

This section defines roots of unity and proves various basic facts about them. Throughout this section we assume that d ≥ 1.

Lean codevariable (d : ) [NeZero d]
Lemma2.2
Group: Roots of unity and their basic properties. (10)
Hover another entry in this group to preview it.
L∃∀Nused by 0

d is invertible in .

Proof

The inverse of d exists since d ∈ ℕ and d ≠ 0.

Lean code for Lemma2.2lemma d_invertible : IsUnit (d : ) := d:inst✝:NeZero dIsUnit d d:inst✝:NeZero d¬d = 0 All goals completed! 🐙

Define the primitive d-th root of unity.

Definition2.3
Group: Roots of unity and their basic properties. (10)
Hover another entry in this group to preview it.
L∃∀N
Used by 3
Hover a use site to preview it.

Let ω = \exp(2πi/d) be the primitive d-th root of unity.

Lean code for Definition2.3noncomputable def ω : := Complex.exp (2 * Real.pi * Complex.I / d)
Lemma2.4
Group: Roots of unity and their basic properties. (10)
Hover another entry in this group to preview it.
L∃∀Nused by 0

ω ≠ 0.

Lean code for Lemma2.4omit [NeZero d] in lemma omega_ne_zero : ω d 0 := d:ω d 0 All goals completed! 🐙
Lemma2.5
Group: Roots of unity and their basic properties. (10)
Hover another entry in this group to preview it.
L∃∀Nused by 0

ω^d = 1.

Proof

ω^d = (\exp(2πi/d))^d = \exp(d(2πi/d)) = \exp(2πi) = 1 where we could cancel d since d ≠ 0.

Lean code for Lemma2.5lemma omega_pow_d_eq_one : (ω d)^d = 1 := d:inst✝:NeZero dω d ^ d = 1 d:inst✝:NeZero dComplex.exp (2 * Real.pi * Complex.I / d) ^ d = 1 d:inst✝:NeZero dComplex.exp (d * (2 * Real.pi * Complex.I / d)) = 1 d:inst✝:NeZero dComplex.exp (2 * Real.pi * Complex.I) = 1d:inst✝:NeZero dIsUnit d d:inst✝:NeZero dComplex.exp (2 * Real.pi * Complex.I) = 1 All goals completed! 🐙 d:inst✝:NeZero dIsUnit d All goals completed! 🐙
Lean codelemma order_omega : orderOf (ω d) = d := d:inst✝:NeZero dorderOf (ω d) = d d:inst✝:NeZero d0 < dd:inst✝:NeZero dω d ^ d = 1d:inst✝:NeZero d (p : ), Nat.Prime p p d ω d ^ (d / p) 1 d:inst✝:NeZero dω d ^ d = 1d:inst✝:NeZero d (p : ), Nat.Prime p p d ω d ^ (d / p) 1 d:inst✝:NeZero d (p : ), Nat.Prime p p d ω d ^ (d / p) 1 intro p d:inst✝:NeZero dp:hp:Nat.Prime pp d ω d ^ (d / p) 1 d:inst✝:NeZero dp:hp:Nat.Prime phpdivd:p dω d ^ (d / p) 1 d:inst✝:NeZero dp:hp:Nat.Prime phpdivd:p dComplex.exp (2 * Real.pi * Complex.I / d) ^ (d / p) 1 d:inst✝:NeZero dp:hp:Nat.Prime phpdivd:p dComplex.exp ((d / p) * (2 * Real.pi * Complex.I / d)) 1 d:inst✝:NeZero dp:hp:Nat.Prime phpdivd:p dComplex.exp (d / p * (2 * Real.pi * Complex.I / d)) 1 d:inst✝:NeZero dp:hp:Nat.Prime phpdivd:p dComplex.exp (d * (2 * Real.pi * Complex.I) / (p * d)) 1 nth_rw 4 [mul_commd:inst✝:NeZero dp:hp:Nat.Prime phpdivd:p dComplex.exp (d * (2 * Real.pi * Complex.I) / (d * p)) 1 d:inst✝:NeZero dp:hp:Nat.Prime phpdivd:p dComplex.exp (d / d * (2 * Real.pi * Complex.I / p)) 1 --#check div_self (Nat.cast_ne_zero.2 (NeZero.ne d)) --rw [div_self, one_mul] d:inst✝:NeZero dp:hp:Nat.Prime phpdivd:p dComplex.exp ((d / d) * (2 * Real.pi * Complex.I / p)) 1 d:inst✝:NeZero dp:hp:Nat.Prime phpdivd:p d¬Complex.exp (2 * Real.pi * Complex.I / p) = 1 d:inst✝:NeZero dp:hp:Nat.Prime phpdivd:p d¬Complex.exp (2 * Real.pi * Complex.I * 1 / p) = 1 nth_rw 1 [ (Nat.cast_one (R:= )) d:inst✝:NeZero dp:hp:Nat.Prime phpdivd:p d¬Complex.exp (2 * Real.pi * Complex.I * 1 / p) = 1 d:inst✝:NeZero dp:hp:Nat.Prime phpdivd:p dhfalse:Complex.exp (2 * Real.pi * Complex.I * 1 / p) = 1False All goals completed! 🐙

This is an additional corrolary that is nice to have.

Lemma2.7
Group: Roots of unity and their basic properties. (10)
Hover another entry in this group to preview it.
L∃∀Nused by 0

ω^n = ω^{n \% d}.

Lean code for Lemma2.7lemma omega_pow_n_mod_d : n : Nat, (ω d) ^ n = (ω d) ^ (n % d) := d:inst✝:NeZero d (n : ), ω d ^ n = ω d ^ (n % d) d:inst✝:NeZero dn:ω d ^ n = ω d ^ (n % d) nth_rw 1 [(Nat.mod_add_div n d)d:inst✝:NeZero dn:ω d ^ (n % d + d * (n / d)) = ω d ^ (n % d) All goals completed! 🐙
Lean codelemma omega_pow_k_mod_d_eq_pow_k_int : k : Int, (ω d) ^ k = (ω d) ^ (k % d) := d:inst✝:NeZero d (k : ), ω d ^ k = ω d ^ (k % d) d:inst✝:NeZero dk:ω d ^ k = ω d ^ (k % d) nth_rw 1 [ (Int.emod_add_ediv_mul k d)d:inst✝:NeZero dk:ω d ^ (k % d + k / d * d) = ω d ^ (k % d) d:inst✝:NeZero dk:ω d ^ (k % d) * ω d ^ (k / d * d) = ω d ^ (k % d)d:inst✝:NeZero dk:ω d 0 k % d + k / d * d 0 k % d = 0 k / d * d = 0 nth_rw 2 [mul_commd:inst✝:NeZero dk:ω d ^ (k % d) * ω d ^ (d * (k / d)) = ω d ^ (k % d)d:inst✝:NeZero dk:ω d 0 k % d + k / d * d 0 k % d = 0 k / d * d = 0 d:inst✝:NeZero dk:ω d ^ (k % d) * (ω d ^ d) ^ (k / d) = ω d ^ (k % d)d:inst✝:NeZero dk:ω d 0 k % d + k / d * d 0 k % d = 0 k / d * d = 0 d:inst✝:NeZero dk:ω d ^ (k % d) * (ω d ^ d) ^ (k / d) = ω d ^ (k % d)d:inst✝:NeZero dk:ω d 0 k % d + k / d * d 0 k % d = 0 k / d * d = 0 d:inst✝:NeZero dk:ω d 0 k % d + k / d * d 0 k % d = 0 k / d * d = 0 d:inst✝:NeZero dk:ω d 0 d:inst✝:NeZero dk:Complex.exp (2 * Real.pi * Complex.I / d) 0 All goals completed! 🐙
Lean codelemma omega_pow_k_mod_d_eq_pow_k_zmod : k : Int, (ω d) ^ k = (ω d) ^ (k : ZMod d).val := d:inst✝:NeZero d (k : ), ω d ^ k = ω d ^ (↑k).val d:inst✝:NeZero dk:ω d ^ k = ω d ^ (↑k).val d:inst✝:NeZero dk:ω d ^ (k % d) = ω d ^ (↑k).val d:inst✝:NeZero dk:ω d ^ (↑k).val = ω d ^ (↑k).val All goals completed! 🐙

We will also need another root of unity which we call τ.

Definition2.10
Group: Roots of unity and their basic properties. (10)
Hover another entry in this group to preview it.
L∃∀N
Used by 3
Hover a use site to preview it.
Preview
Definition 5.46
Loading preview
Hover a use site to preview it.

Let τ = -\exp(πi/d).

Lean code for Definition2.10noncomputable def τ : := - Complex.exp (Real.pi * Complex.I / d)
Lemma2.11
Group: Roots of unity and their basic properties. (10)
Hover another entry in this group to preview it.
L∃∀N
Used by 3
Hover a use site to preview it.

τ^2 = ω.

Proof

τ^2 = (-\exp(πi/d))^2 = (-1)^2 · (\exp(πi/d))^2 = 1 · \exp(2πi/d) = ω.

Lean code for Lemma2.11lemma declaration uses `sorry`tau_sq_eq_omega : (τ d)^2 = ω d := d:inst✝:NeZero dτ d ^ 2 = ω d All goals completed! 🐙
Lemma2.12
Group: Roots of unity and their basic properties. (10)
Hover another entry in this group to preview it.
L∃∀Nused by 1

If d is odd then τ^d = 1.

Proof

τ^d = (-\exp(πi/d))^d = (-1)^d · (\exp(πi/d))^d = (-1)^d · \exp(πi) = (-1)^d · (-1) = (-1)^{d+1} = 1 when d is odd.

Lean code for Lemma2.12lemma tau_pow_d_eq_one_of_odd (hodd : Odd d) : (τ d)^d = 1 := d:inst✝:NeZero dhodd:Odd dτ d ^ d = 1 calc (-Complex.exp (Real.pi * Complex.I * (d)⁻¹)) ^ d = (-1 : )^d * Complex.exp (Real.pi * Complex.I * (d)⁻¹) ^ d := d:inst✝:NeZero dhodd:Odd d(-Complex.exp (Real.pi * Complex.I * (↑d)⁻¹)) ^ d = (-1) ^ d * Complex.exp (Real.pi * Complex.I * (↑d)⁻¹) ^ d All goals completed! 🐙 _ = (-1 : )^d * Complex.exp (Real.pi * Complex.I * d * (d)⁻¹) := d:inst✝:NeZero dhodd:Odd d(-1) ^ d * Complex.exp (Real.pi * Complex.I * (↑d)⁻¹) ^ d = (-1) ^ d * Complex.exp (Real.pi * Complex.I * d * (↑d)⁻¹) All goals completed! 🐙 _ = (-1 : )^d * Complex.exp (Real.pi * Complex.I) := d:inst✝:NeZero dhodd:Odd d(-1) ^ d * Complex.exp (Real.pi * Complex.I * d * (↑d)⁻¹) = (-1) ^ d * Complex.exp (Real.pi * Complex.I) All goals completed! 🐙 _ = (-1)^(d+1) := d:inst✝:NeZero dhodd:Odd d(-1) ^ d * Complex.exp (Real.pi * Complex.I) = (-1) ^ (d + 1) All goals completed! 🐙 _ = 1 := d:inst✝:NeZero dhodd:Odd d(-1) ^ (d + 1) = 1 d:inst✝:NeZero dhodd:Odd dEven (d + 1)d:inst✝:NeZero dhodd:Odd d-1 1 d:inst✝:NeZero dhodd:Odd dEven (d + 1) d:inst✝:NeZero dk:hk:d = 2 * k + 1Even (d + 1) d:inst✝:NeZero dk:hk:d = 2 * k + 1 r, d + 1 = r + r d:inst✝:NeZero dk:hk:d = 2 * k + 1d + 1 = k + 1 + (k + 1) All goals completed! 🐙 d:inst✝:NeZero dhodd:Odd d-1 1 All goals completed! 🐙
Lemma2.13
Group: Roots of unity and their basic properties. (10)
Hover another entry in this group to preview it.
L∃∀Nused by 0

τ^{d^2} = 1.

Proof

τ^{d^2} = (-\exp(πi/d))^{d^2} = (-1)^{d^2} · (-1)^d = (-1)^{d(d+1)} = 1 since either d or d+1 is even.

Lean code for Lemma2.13lemma tau_pow_d2_one : (τ d) ^ (d ^ 2) = 1 := d:inst✝:NeZero dτ d ^ d ^ 2 = 1 d:inst✝:NeZero d(-Complex.exp (Real.pi * Complex.I / d)) ^ d ^ 2 = 1 d:inst✝:NeZero d(-1 * Complex.exp (Real.pi * Complex.I / d)) ^ d ^ 2 = 1 d:inst✝:NeZero d(-1 * Complex.exp (Real.pi * Complex.I / d)) ^ (d * d) = 1 d:inst✝:NeZero d(-1) ^ (d * d) * Complex.exp (Real.pi * Complex.I / d) ^ (d * d) = 1 d:inst✝:NeZero d(-1) ^ (d * d) * Complex.exp ((d * d) * (Real.pi * Complex.I / d)) = 1 d:inst✝:NeZero d(-1) ^ (d * d) * Complex.exp (d * d * (Real.pi * Complex.I / d)) = 1 d:inst✝:NeZero d(-1) ^ (d * d) * Complex.exp (d * (d * (Real.pi * Complex.I / d))) = 1 d:inst✝:NeZero d(-1) ^ (d * d) * Complex.exp (d * (Real.pi * Complex.I)) = 1d:inst✝:NeZero dIsUnit d d:inst✝:NeZero d(-1) ^ (d * d) * Complex.exp (Real.pi * Complex.I) ^ d = 1d:inst✝:NeZero dIsUnit d d:inst✝:NeZero d(-1) ^ (d * d) * (-1) ^ d = 1d:inst✝:NeZero dIsUnit d d:inst✝:NeZero d(-1) ^ (d * d + d) = 1d:inst✝:NeZero dIsUnit d d:inst✝:NeZero d(-1) ^ (d * (d + 1)) = 1d:inst✝:NeZero dIsUnit d d:inst✝:NeZero dEven (d * (d + 1))d:inst✝:NeZero d-1 1d:inst✝:NeZero dIsUnit d d:inst✝:NeZero d-1 1d:inst✝:NeZero dIsUnit d d:inst✝:NeZero d-1 1 All goals completed! 🐙 d:inst✝:NeZero dIsUnit d All goals completed! 🐙
Lemma2.14
Group: Roots of unity and their basic properties. (10)
Hover another entry in this group to preview it.
L∃∀Nused by 0

τ ≠ 0.

Lean code for Lemma2.14omit [NeZero d] in lemma tau_ne_zero : τ d 0 := d:τ d 0 d:-Complex.exp (Real.pi * Complex.I / d) 0 d:- -Complex.exp (Real.pi * Complex.I / d) 0 d:Complex.exp (Real.pi * Complex.I / d) 0 All goals completed! 🐙
Lean codelemma mod_d_nonneg (a : ) : 0 a % d := d:inst✝:NeZero da:0 a % d d:inst✝:NeZero da:d 0 All goals completed! 🐙
Lemma2.16
Group: Roots of unity and their basic properties. (10)
Hover another entry in this group to preview it.
L∃∀Nused by 0

If d is odd then τ^{n} = τ^{n \% d}.

Lean code for Lemma2.16theorem tau_pow_n_mod_d_of_d_odd (n d : ) (hodd : Odd d) [NeZero d] : τ d ^ n = τ d ^ (n % d) := pow_eq_pow_mod n (tau_pow_d_eq_one_of_odd d hodd)
Lean codetheorem tau_star (d : ) (n : ) [NeZero d] : star (τ d ^ n) = τ d^(-n) := d:n:inst✝:NeZero dstar (τ d ^ n) = τ d ^ (-n) d:n:inst✝:NeZero dstar ((-Complex.exp (Real.pi * Complex.I / d)) ^ n) = (-Complex.exp (Real.pi * Complex.I / d)) ^ (-n) d:n:inst✝:NeZero d(-Complex.exp ((starRingEnd ) (Real.pi * Complex.I / d))) ^ n = (-Complex.exp (Real.pi * Complex.I / d)) ^ (-n) d:n:inst✝:NeZero d(-Complex.exp (-(Real.pi * Complex.I) / d)) ^ n = (-Complex.exp (Real.pi * Complex.I / d)) ^ (-n) d:n:inst✝:NeZero dh:Even n(-Complex.exp (-(Real.pi * Complex.I) / d)) ^ n = (-Complex.exp (Real.pi * Complex.I / d)) ^ (-n)d:n:inst✝:NeZero dh:¬Even n(-Complex.exp (-(Real.pi * Complex.I) / d)) ^ n = (-Complex.exp (Real.pi * Complex.I / d)) ^ (-n) d:n:inst✝:NeZero dh:Even n(-Complex.exp (-(Real.pi * Complex.I) / d)) ^ n = (-Complex.exp (Real.pi * Complex.I / d)) ^ (-n) d:n:inst✝:NeZero dh:Even nComplex.exp (-(Real.pi * Complex.I) / d) ^ n = Complex.exp (Real.pi * Complex.I / d) ^ (-n) d:n:inst✝:NeZero dh:Even nComplex.exp (n * (-(Real.pi * Complex.I) / d)) = Complex.exp ((-n) * (Real.pi * Complex.I / d)) d:n:inst✝:NeZero dh:Even nComplex.exp (n * (-(Real.pi * Complex.I) / d)) = Complex.exp (-n * (Real.pi * Complex.I / d)) All goals completed! 🐙 d:n:inst✝:NeZero dh:Odd n(-Complex.exp (-(Real.pi * Complex.I) / d)) ^ n = (-Complex.exp (Real.pi * Complex.I / d)) ^ (-n) d:n:inst✝:NeZero dh:Odd n-Complex.exp (-(Real.pi * Complex.I) / d) ^ n = -Complex.exp (Real.pi * Complex.I / d) ^ (-n) d:n:inst✝:NeZero dh:Odd n-Complex.exp (n * (-(Real.pi * Complex.I) / d)) = -Complex.exp ((-n) * (Real.pi * Complex.I / d)) d:n:inst✝:NeZero dh:Odd n-Complex.exp (n * (-(Real.pi * Complex.I) / d)) = -Complex.exp (-n * (Real.pi * Complex.I / d)) All goals completed! 🐙