Root of unity

From Wikipedia, the free encyclopedia

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. It can be shown that they are located on the unit circle of the complex plane and that in that plane they form the vertices of a n-sided regular polygon with one vertex on 1.

1 Definition
2 Primitive roots
3 Examples
4 Summation
5 Orthogonality
6 Example calculation: extracting coefficients
7 Notations
8 Cyclotomic polynomials
9 Example calculation: the next-to-leading coefficient
10 Cyclotomic fields
11 External links
12 References
13 See also

[edit] Definition

The complex numbers z which solve

$z^n = 1 \qquad (n = 1, 2, 3, \dots )$

are called the n^th roots of unity.

There are n different n^th roots of unity .

$e^{2 \pi i k/n} \qquad (k = 0, 1, 2, \dots, n - 1).$

[edit] Primitive roots

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 multiplicative subgroups of the complex numbers, except the trivial group {0}. A generator for this cyclic group is a primitive n^th root of unity. The primitive n^th roots of unity are $e 2π 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, $φ(n)$ .

[edit] Examples

There is only one first root of unity, equal to 1.

The second roots (square roots) of unity are +1 and -1, of which only -1 is primitive.

The third roots (cubic roots) of unity are

$\left\{ 1, \frac{-1 + i \sqrt{3}}{2}, \frac{-1 - i \sqrt{3}}{2} \right\} ,$

where $i$ is the imaginary unit; the latter two roots are primitive.

The fourth roots of unity are

$\left\{ 1, +i, -1, -i \right\} ,$

of which $+ i$ and $- i$ are primitive.

The 5^th roots of unity are

$\left\{\left . 1, \frac{u\sqrt{5}-1}{4} + v\sqrt{\frac{5 + u\sqrt{5}}{8}}i \right | u,v \in \{-1,1\} \right\}.$

A primitive 8^th root of unity is

$\sqrt{i}= \frac{\sqrt{2}}{2}+i\frac{\sqrt{2}}{2}.$

[edit] Summation

As long as n is at least 2, the n^th roots of unity add up to 0. This fact arises in many areas of mathematics and can be proved in a number of ways. One elementary proof is to apply the formula for a geometric series:

$\sum_{k=0}^{n-1} e^{2 \pi i k/n} = \frac{e^{2 \pi i n/n} - 1}{e^{2 \pi i/n} - 1} = \frac{1-1}{e^{2 \pi i/n} - 1} = 0 .$

Yet another reason for the zero summation is that the roots of unity, plotted in the complex plane, form the vertices of a regular polygon whose barycenter (by symmetry) lies at the origin. This summation is a special case of the Gaussian sum.

[edit] Orthogonality

One can use the summation formula to prove an orthogonality relationship:

$\sum_{k=0}^{n-1} e^{-2 \pi i j k/n} \cdot e^{2 \pi i j' k/n} = n \delta_{j,j'}$

where $δ$ is the Kronecker delta. Here the equality of $j$ and $j'$ is to be understood modulo $n$ , since

$e^{2 \pi i \, (j' + rn) \, k/n} = e^{2 \pi i j' k/n} e^{2 \pi i r k} = e^{2 \pi i j' k/n},$

where $r$ is an integer.

The $n$ ^th roots of unity can be used to form an $n \times n$ matrix whose $(j, k)$ ^th entry is

$U_{j,k}=n^{-\frac{1}{2}} e^{-2 \pi i j k/n}$

From above, the columns of this matrix are orthonormal and thus the matrix is unitary. In fact, this matrix is precisely the discrete Fourier transform (although normalization and sign conventions vary).

The n^th roots of unity form an irreducible representation of any cyclic group of order $n$ . The orthogonality relationship then follows from group-theoretic principles as described in character group.

The roots of unity appear as the eigenvectors of Hermitian matrices (for example, of a discretized one-dimensional Laplacian with periodic boundaries), from which the orthogonality property also follows (Strang, 1999).

[edit] Example calculation: extracting coefficients

As a special case of orthogonality, we have

$\sum_{k=0}^{n-1} \left(e^{2 \pi i k/n}\right)^j = \begin{cases} n \quad \mbox{if} \quad j \equiv 0 \mod n \\ 0 \quad \mbox{otherwise}, \end{cases}$

i.e. the sum of the roots of unity raised to some fixed power $j$ is $n$ if $j$ is divisible by $n$ , and zero otherwise.

This implies the following useful fact. If we have a polynomial or a series $f (x)$ in $x$ , where

$f(x) = \sum_j f_j x^j,\,$

then

$\frac{1}{n} \sum_{k=0}^{n-1} f\left(e^{2 \pi i k/n} \, x \right) = \sum_{n|j} f_j x^j.$

As a particular case, we have

$\frac{1}{n} \sum_{k=0}^{n-1} f\left(e^{2 \pi i k/n} \right) = \sum_{n|j} f_j,$

i.e. the sum of the coefficients that are divisible by $n$ , assuming it exists.

As an example as to how this may be applied, ask the following question: suppose we choose an integer at random from $[0, 10^{11}-1].\,$ What is the probability that its digit sum will be divisible by $11$ ?

Clearly the generating function of the digit sums of the integers in $[0, 10^{11}-1]\,$ is

$f(x) = \left(x^0 + x^1 + x^2 + \cdots + x^8 + x^9\right)^{11}.$

We seek the sum of the coefficients of $x$ raised to a power that is divisible by $11$ , giving

$\frac{1}{11} \sum_{k=0}^{10} f\left(e^{2 \pi i k/11} \right) = \frac{1}{11} f(1) + \frac{1}{11} \sum_{k=1}^{10} \left(- \left(e^{2 \pi i k/11}\right)^{10} \right)^{11},$

because

$x^0 + x^1 + x^2 + \cdots + x^8 + x^9 = - x^{10}$

when $x$ is an eleventh root of unity that is not one. Additional simplification now yields

$\frac{1}{11} 10^{11} - \frac{1}{11} \sum_{k=1}^{10} \left(e^{2 \pi i k}\right)^{10} = \frac{1}{11} 10^{11} - \frac{1}{11} 10.$

This means that the desired probability is

$\frac{1}{11} - \frac{1}{11 \times 10^{10}} = \frac{909090909}{10000000000} \sim \frac{1}{11}.$

This problem was discussed on the newsgroup es.ciencia.matematicas, and the article is here.

[edit] Notations

The primitive root $e - 2π i / n$ (or its conjugate $e 2π i / n$ ) is often denoted by $W n$ or $ω n$ (or sometimes simply $W$ or $ω$ when $n$ can be inferred from context), especially in the context of discrete Fourier transforms where this quantity occurs frequently.

[edit] 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 nth roots of unity, each with multiplicity 1:

$\Phi_n(z) = \prod_{k=1}^{\varphi(n)}(z-z_k)\;$

where z₁,...,z_φ(n) are the primitive n^th roots of unity, and $φ(n)$ is Euler's totient function. The polynomial $Φ n (z)$ has integer coefficients and is an irreducible polynomial over the rational numbers (i.e., cannot be written as a 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ⁿ - 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)},$

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 p^th roots of unity except 1 are primitive p^th roots, and we have

$\Phi_p(z)=\frac{z^p-1}{z-1}=\sum_{k=0}^{p-1} z^k$

Note that, contrary to first appearances, not all coefficients of all cyclotomic polynomials are 1, −1, or 0; the first polynomial where this occurs is Φ₁₀₅, 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 (z)$ then $d \equiv 1\pmod{p}\$ or $d \equiv 0\pmod{p}$ .

[edit] Example calculation: the next-to-leading coefficient

We have the following equality:

$\left[z^{\varphi(n)-1}\right] \Phi_n(z) = - \mu(n)$

where $μ$ is the Moebius function.

To see this, observe that

$\left[z^{\varphi(n)-1}\right] \Phi_n(z) = - \sum_{(k, n)=1} z_{k, n},$

where the $z k, n$ are the primitive roots of unity, so we must show that

$\mu(n) = \sum_{(k, n)=1} z_{k, n},\,$

which we do by complete mathematical induction.

It certainly holds for $n = 1$ and $n = 2$ , because

$\mu(1) = 1 = z_{1, 1} \quad \mbox{and} \quad \mu(2) = -1 = z_{1, 2}.$

Now suppose it holds for $m < n$ . We know that

$\sum_{k=1}^n z_{k, n} = 0 \quad \mbox{and hence} \quad \sum_{d|n} \sum_{(k, n)=d} z_{k, n} = 0.$

This implies that

$\sum_{(k, n)=1} z_{k, n} = - \sum_{d|n, \, d>1} \sum_{(k, n)=d} z_{k, n}\,.$

But for $d>1\,$ we have

$\sum_{(k, n)=d} z_{k, n} = \sum_{(l, n/d)=1} z_{l, n/d} = \mu(n/d)\,$

where the last equality is by induction (note that $d>1\,$ implies $n/d<n\,$ ) and we have used the fact that

$z_{k, n} = e^{2 \pi i \, k/n} = e^{2 \pi i \, (dl)/(d\,n/d)} = e^{2 \pi i \, l/(n/d)} = z_{l, n/d}$

when $(k, n)=d.\,$ Substitution now yields

$\sum_{(k, n)=1} z_{k, n} = - \sum_{d|n, \, d>1} \mu(n/d)$

which is

$\mu(n) - \sum_{d|n} \mu(n/d) = \mu(n) - \sum_{d|n} \mu(d) = \mu(n),\,$

because the sum of the Moebius function evaluated at the divisors of an integer $n$ is zero. QED.

This problem was discussed on the newsgroup es.ciencia.matematicas, and the article is here.

[edit] Cyclotomic fields

By adjoining a primitive $n$ -th root of unity to $\mathbb{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 $\mathbb{Q}$ . The field extension $F_n/\mathbb{Q}$ has degree $φ(n)$ and its Galois group is naturally isomorphic to the multiplicative group of units of the ring $\mathbb{Z}/n\mathbb{Z}$ .

As the Galois group of $F_n/\mathbb{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 quite 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 supplied the proof.

[edit] External links

León-Sotelo, Marko Riedel Escoger un entero, newsgroup es.ciencia.matematicas

Marko Riedel Secretos del Totient, newsgroup es.ciencia.matematicas

[edit] References

Lang, Serge (2002). Algebra, revised 3rd edition, New York: Springer-Verlag. ISBN 0-387-95385-X.
Milne, James S. (1998). Algebraic Number Theory. Course Notes.
Milne, James S. (1997). Class Field Theory. Course Notes.
Neukirch, Jürgen (1999). Algebraic Number Theory. Berlin: Springer-Verlag. ISBN 3-540-65399-6.
Neukirch, Jürgen (1986). Class Field Theory. Berlin: Springer-Verlag. ISBN 3-540-15251-2.
Washington, Lawrence C. (1997). Cyclotomic fields, 2nd edition, New York: Springer-Verlag. ISBN 0-387-94762-0.