ROOT OF UNITY

In mathematics, the '''n''th roots of unity', or de Moivre numbers, are all the complex numbers which yield 1 when raised to a given power ''n''. They are located on the unit circle of the complex plane, and in that plane they form the vertices of an ''n''-sided regular polygon with one vertex on 1.

Contents

Definition

Examples

Summation

Orthogonality

Periodicity

Cyclotomic polynomials

Cyclic groups

Cyclotomic fields

References

See also

Definition

An '''n''th root of unity', where ''n'' = 1,2,3,···, is a complex number, ''z'', satisfying the equation
:$z^n\; =\; 1\; ,,$
see exponentiation.
An ''n''th root of unity is 'primitive' if
:$z^k$
e 1 qquad (k = 1, 2, 3, dots, n-1 )
There are ''n'' different ''n''th roots of unity:
:$z^k\; qquad\; (k\; =\; 1,\; 2,\; 3,\; dots,\; n\; )$
where ''z'' is any primitive ''n''th root of unity.
One primitive ''n''th root of unity is
:$e^\{2\; pi\; i/n\}\; ,$
see Exponentiation#Complex_roots_of_unity and Euler's formula.
Second roots are called square roots, and third roots are called cube roots.
The number (+1) is a square root of unity because (+1)² = 1, but it is not a primitive square root of unity because (+1)¹ = 1. So (+1) is only a primitive ''first'' root of unity.
The number (−1) is a primitive square root of unity because (−1)¹ ≠ 1 and (−1)² = 1.
For ''n''>2, the primitive ''n''th roots of unity are non-real complex numbers.
$e^\{2\; pi\; i\; /n\}$ (or its conjugate $e^\{-2\; pi\; i\; /n\}$) is often denoted by $W\_n$ or $omega\_n$ (or sometimes simply $W$ or $omega$ when $n$ can be inferred from context), especially in the context of discrete Fourier transforms where this quantity occurs frequently.^[1][2] It is also commonly denoted $zeta$ or $zeta\_n$.

Examples

The 2 primitive cube roots of unity are
:
ight} ,
where $i$ is the imaginary unit.
The 2 primitive fourth roots of unity are
:$left\{+i,\; -i$
ight} .
The 4 primitive 5th roots of unity are
:
ight |u,v in {-1,1}
ight}.
The 2 primitive 6th roots of unity are
:
ight} .
A primitive 8th root of unity is
:

Summation

The ''n''th roots of unity add up according to the formula for a geometric series. (This summation is a special case of the Gaussian sum.) For ''n'' > 1:
:
where ''z'' is a primitive ''n''th root of unity. For ''n'' = 1, the sum has only one term (''k''=0) and equals 1.

Orthogonality

From the summation formula follows an orthogonality relationship: for ''j'' = 0, 1, ···, ''n'' − 1 and ''j'' ' = 0, 1, ···, ''n'' − 1
:$sum\_\{k=0\}^\{n-1\}\; overline\{z^\{jcdot\; k\}\}\; cdot\; z^\{j\text{'}cdot\; k\}\; =\; n\; cdotdelta\_\{j,j\text{'}\}$
where $delta$ is the Kronecker delta and ''z'' is any primitive ''n''th root of unity.
It follows that the $n\; imes\; n$ matrix $U$ whose $(j,k)$th entry is
:
is unitary. That is,
:$sum\_\{k=0\}^\{n-1\}\; U\_\{j,k\}\; overline\{U\_\{k,j\text{'}\}\}\; =\; delta\_\{j,j\text{'}\}\; ,$
and thus the inverse of ''U'' is the complex conjugate of its transpose.
For $z\; =\; exp(-2pi\; i/n)$, this matrix is the discrete Fourier transform (DFT) (although normalization and sign conventions vary). The fact that the matrix ''U'' is both unitary and (complex) symmetric means that the inverse DFT is related to the DFT merely by a complex conjugation (rather than by more expensive methods to solve linear equations, such as gaussian elimination), a fact first noted by Gauss when solving the problem of trigonometric interpolation. Although the application of ''U'' or its inverse to a given vector would therefore seem to require ''O''(''n''²) operations, in fact only ''O''(''n'' log ''n'') operations are required thanks to the existence of fast Fourier transform algorithms.

Periodicity

If ''z'' is a primitive ''n''th root of unity, then the sequence of powers
: ··· , ''z''⁻¹, ''z''⁰, ''z''¹, ··· , ''z'' ^''j'' , ···
is '''n''-periodic', (because ''z'' ^''j''+''n'' = ''z'' ^''j''·''z''^''n'' = ''z'' ^''j''·1 = ''z'' ^''j'' for all values of ''j'',) and the ''n'' sequences of powers
:··· , ''z'' ^{''k''·(−1)}, ''z'' ^''k''·0, ''z''^''k''·1, ··· , ''z'' ^''k''·''j'' , ··· (for ''k'' = 0, 1, ··· , ''n''−1),
are all ''n''-periodic. These ''n'' sequences have furthermore the property of linear independence. This means that for ''any'' ''n''-periodic sequence
: ··· , ''x''₋₁ , ''x''₀ , ''x''₁ , ··· , ''x'' _''j'' , ···
''x'' _''j'' can be expressed as a linear combination of ''j''-th powers of the ''n''th roots of unity:
:''x'' _''j'' = ''X''₀·''z''^0·''j'' + ··· + ''X''_''k''·''z''^''k''·''j'' + ··· + ''X''_(''n''−1)·''z''^{(''n''−1)·''j''}.
This is a form of Fourier analysis, where ''k'' represents a frequency. For the choice $z\; =\; exp(2pi\; i/n)$ the summation above (computing ''x'' from ''X'') is an inverse discrete Fourier transform (inverse DFT), while the computation of ''X'' from ''x'' is a DFT. The interpretation of this frequency as an oscillation rate, however, is somewhat complicated by the phenomenon of aliasing, as discussed in the DFT article.

Cyclotomic polynomials

The zeroes of the polynomial
:$p(z)\; =\; z^n\; -\; 1!$
are precisely the ''n''th roots of unity, each with multiplicity 1.
The ''n''th 'cyclotomic polynomial' is defined by the fact that its zeros are precisely the ''primitive'' ''n''th roots of unity, each with multiplicity 1:
:$Phi\_n(z)\; =\; prod\_\{k=1\}^\{phi(n)\}(z-z\_k);$
where ''z''₁,...,''z''_φ(''n'') are the primitive ''n''th roots of unity, and $phi(n)$ is Euler's totient function. The polynomial $Phi\_n(z)$ has integer coefficients and is an irreducible polynomial over the rational numbers (i.e., it cannot be written as the product of two positive-degree polynomials with rational coefficients). The case of prime ''n'', which is easier than the general assertion, follows from Eisenstein's criterion.
Every ''n''th root of unity is a primitive ''d''th root of unity for exactly one positive divisor ''d'' of ''n''. This implies that
:$z^n\; -\; 1\; =\; prod\_\{d,mid,n\}\; Phi\_d(z).;$
This formula represents the factorization of the polynomial ''z''^''n'' − 1 into irreducible factors.
:''z''¹−1 = ''z''−1
:''z''²−1 = (''z''−1)·(''z''+1)
:''z''³−1 = (''z''−1)·(''z''²+''z''+1)
:''z''⁴−1 = (''z''−1)·(''z''+1)·(''z''²+1)
:''z''⁵−1 = (''z''−1)·(''z''⁴+''z''³+''z''²+''z''+1)
:''z''⁶−1 = (''z''−1)·(''z''+1)·(''z''²+''z''+1)·(''z''²−''z''+1)
:''z''⁷−1 = (''z''−1)·(''z''⁶+''z''⁵+''z''⁴+''z''³+''z''²+''z''+1)
Applying Möbius inversion to the formula gives
:$$
Phi_n(z) = prod_{d,mid n}(z^{n/d}-1)^{mu(d)} = prod_{d,mid n}(z^{d}-1)^{mu(n/d)},

where μ is the Möbius function.
So the first few cyclotomic polynomials are
:Φ₁(''z'') = ''z''−1
:Φ₂(''z'') = (''z''²−1)·(''z''−1)⁻¹ = ''z''+1
:Φ₃(''z'') = (''z''³−1)·(''z''−1)⁻¹ = ''z''²+''z''+1
:Φ₄(''z'') = (''z''⁴−1)·(''z''²−1)⁻¹ = ''z''²+1
:Φ₅(''z'') = (''z''⁵−1)·(''z''−1)⁻¹ = ''z''⁴+''z''³+''z''²+''z''+1
:Φ₆(''z'') = (''z''⁶−1)·(''z''³−1)⁻¹·(''z''²−1)⁻¹·(''z''−1) = ''z''²−''z''+1
:Φ₇(''z'') = (''z''⁷−1)·(''z''−1)⁻¹ = ''z''⁶+''z''⁵+''z''⁴+''z''³+''z''²+''z''+1
If ''p'' is a prime number, then all the ''p''th roots of unity except 1 are primitive ''p''th roots, and we have
:.
Substituting any positive integer for ''z'', this sum becomes a base ''z'' repunit. Thus a necessary (but not sufficient) condition for a repunit to be prime is that its length be prime.
Note that, contrary to first appearances, ''not'' all coefficients of all cyclotomic polynomials are 1, −1, or 0. The first exception is $Phi\_\{105\}$, since 105 = 3·5·7 is the first product of three odd primes. Many restrictions are known about the values that cyclotomic polynomials can assume at integer values. For example, if ''p'' is prime and ''d'' | Φ_''p''(''d''), then either ''d'' ≡ 1 mod (''p''), or ''d'' ≡ 0 mod (''p'').
Cyclotomic polynomials are trivially solvable in radicals, as roots of unity are themselves radicals. Moreover, there exist more informative radical expressions for ''n''th roots of unity with the additional property^[3] that every value of the expression obtained by choosing values of the radicals (for example, signs of square roots) is a primitive ''n''th root of unity. This was already shown by Gauss in 1797^[4]. Efficient algorithms exist for calculating such expressions^[3].

Cyclic groups

The ''n''th roots of unity form under multiplication a cyclic group of order ''n'', and in fact these groups comprise all of the finite subgroups of the multiplicative group of the complex number field. A generator for this cyclic group is a primitive ''n''th root of unity. The primitive ''n''th roots of unity are those $e^\{2\; pi\; i\; k/n\}$ where ''k'' and ''n'' are coprime. The number of different primitive ''n''th roots of unity is given by Euler's totient function, $phi(n)$.
The ''n''th roots of unity form an irreducible representation of any cyclic group of order ''n''. The orthogonality relationship also follows from group-theoretic principles as described in character group.
The roots of unity appear as the eigenvectors of any circulant matrix, i.e. matrices that are invariant under cyclic shifts, a fact that also follows from group representation theory as a variant of Bloch's theorem.^[6] In particular, if a circulant Hermitian matrix is considered (for example, a discretized one-dimensional Laplacian with periodic boundaries^[7]), the orthogonality property immediately follows from the usual orthogonality of eigenvectors of Hermitian matrices.

Cyclotomic fields

Main articles: Cyclotomic field

By adjoining a primitive ''n''th root of unity to 'Q', one obtains the ''n''th cyclotomic field ''F_n''. This field contains all ''n''th roots of unity and is the splitting field of the ''n''th cyclotomic polynomial over 'Q'. The field extension ''F_n''/'Q' has degree φ(''n'') and its Galois group is naturally isomorphic to the multiplicative group of units of the ring 'Z'/''n'''Z'.
As the Galois group of ''F_n''/'Q' is abelian, this is an abelian extension. Every subfield of a cyclotomic field is an abelian extension of the rationals. In these cases Galois theory can be written out explicitly in terms of Gaussian periods: this theory from the ''Disquisitiones Arithmeticae'' of Gauss was published many years before Galois.
Conversely, ''every'' abelian extension of the rationals is such a subfield of a cyclotomic field — this is the content of a theorem of Kronecker, usually called the ''Kronecker-Weber theorem'' on the grounds that Weber completed the proof.

References

1. Donald E. Knuth, ''The Art of Computer Programming Volume 1: Fundamental Algorithms'' (Addison-Wesley: New York, 1997).
2. Discrete-time signal processing, Oppenheim, Alan V.; Schafer, R. W.; and Buck, J. R., , , Prentice Hall, 1999, ISBN 0-13-754920-2
3.
4. Disquisitiones Arithmeticae, , Carl F., Gauss, Yale University Press, ,
5.
6. T. Inui, Y. Tanabe, and Y. Onodera, ''Group Theory and Its Applications in Physics'' (Springer, 1996).
7. Gilbert Strang, "The discrete cosine transform," ''SIAM Review'' '41' (1), 135-147 (1999).


★ Algebra, Lang, Serge, , , Springer-Verlag, 2002, ISBN 0-387-95385-X

★ Algebraic Number Theory

★ Class Field Theory

★ Algebraic Number Theory, , Jürgen, Neukirch, Springer-Verlag, 1999, ISBN 3-540-65399-6

★ Class Field Theory, , Jürgen, Neukirch, Springer-Verlag, 1986, ISBN 3-540-15251-2

★ Cyclotomic fields, , Lawrence C., Washington, Springer-Verlag, 1997, ISBN 0-387-94762-0

See also

★ Circle group