Not What You Meant? There are 28 definitions for Unit.

Root of unity

About 9 pages (2,712 words)

Questions on this topic? Just ask!

In mathematics, the nth 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.

1 Definition
2 Examples
3 Periodicity
4 Summation
5 Orthogonality
6 Cyclotomic polynomials
7 Cyclic groups
8 Cyclotomic fields
9 Example calculations
- 9.1 Extracting coefficients
- 9.2 The next-to-leading coefficient
10 References
11 See also

Definition

The 3rd roots of unity

Plot of z³-1, in which a zero is represented by the color black.

Plot of z⁵-1, in which a zero is represented by the color black.

An nth root of unity, where n = 1,2,3,···, is a complex number, z, satisfying the equation

see exponentiation. An nth root of unity is primitive if

<math>z^k \ne 1 \qquad (k = 1, 2, 3, \dots, n-1 )</math>

There are n different nth roots of unity:

<math>z^k \qquad (k = 1, 2, 3, \dots, n )</math>

where z is any primitive nth root of unity. 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 nth roots of unity are non-real complex numbers. One primitive nth root of unity is

(See Exponentiation and Euler's formula.)

Examples

The two primitive cube roots of unity are

<math>\left\{ \frac{-1 + i \sqrt{3}}{2}, \frac{-1 - i \sqrt{3}}{2} \right\} ,</math>

where <math> i </math> is the imaginary unit. The two primitive fourth roots of unity are

<math>\left\{+i, -i \right\} .</math>

The four primitive fifth roots of unity are

<math>\left\{\left . \frac{u\sqrt{5}-1}{4} + v\sqrt{\frac{5 + u\sqrt{5}}{8}}i

\right |u,v \in \{-1,1\}\right\}.</math> The two primitive sixth roots of unity are

<math>\left\{ \frac{1 + i \sqrt{3}}{2}, \frac{1 - i \sqrt{3}}{2} \right\} .</math>

A primitive eighth root of unity is

Periodicity

If z is a primitive nth root of unity, then the sequence of powers

··· , z⁻¹, z⁰, z¹, ···

is n-periodic, (because z ^j+n = z ^j·zⁿ = 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, ··· (for k = 1···n),

are all n-periodic. These n sequences have furthermore the property of linear independence. This means that any n-periodic sequence

··· , x₋₁ , x₀ , x₁ , ···

can be expressed as a linear combination of powers of a primitive nth root of unity:

x _j = Σ_k X_k·z^k·j = X₁·z^1·j + ··· + X_n·z^n·j .

This is a form of Fourier analysis. If j is a (discrete) time variable, then k is a frequency and X_k is a complex amplitude. Choosing for the primitive nth root of unity

z = e^i·2·π/n = cos(2·π/n) + i·sin(2·π/n)

allows x _j to be expressed as a linear combination of cos and sin

x _j = Σ_k A_k·cos(2·π·j·k/n) + Σ_k B_k·sin(2·π·j·k/n).

Complex numbers was once considered very advanced, and still some programming languages and many pocket calculators do not support complex arithmetic.

Summation

The nth 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 nth 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 = 1, ···, n and j ' = 1, ···, n

<math>\sum_{k=1}^{n} \overline{z^{j\cdot k}} \cdot z^{j'\cdot k} = n \cdot\delta_{j,j'}</math>

where <math>\delta</math> is the Kronecker delta and z is any primitive nth root of unity. The <math>n \times n</math> matrix <math>\ U</math> whose <math>(j,k)</math>th entry is

defines a discrete Fourier transform. Computing the inverse transformation using gaussian elimination requires O(n³) operations. However, it follows from the orthogonality that U is unitary. That is,

<math>\sum_{k=1}^{n} \overline{U_{j,k}} \cdot U_{k,j'} = \delta_{j,j'} ,</math>

and thus the inverse of U is simply the complex conjugate. (This fact was first noted by Gauss when solving the problem of trigonometric interpolation). The straightforward application of U or its inverse to a given vector requires O(n²) operations. The existence of fast Fourier transform algorithms reduces the number of operations further to O(n log n).

Cyclotomic polynomials

The zeroes of the polynomial

are precisely the nth roots of unity, each with multiplicity 1. The nth cyclotomic polynomial is defined by the fact that its zeros are precisely the primitive nth roots of unity, each with multiplicity 1:

where z₁,...,z_φ(n) are the primitive nth roots of unity, and <math>\phi(n)</math> is Euler's totient function. The polynomial <math>\Phi_n(z)</math> 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 nth root of unity is a primitive dth root of unity for exactly one positive divisor d of n. This implies that

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

<math>

\Phi_n(z) = \prod_{d\,\mid n}(z^{n/d}-1)^{\mu(d)} = \prod_{d\,\mid n}(z^{d}-1)^{\mu(n/d)}, </math> 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 pth roots of unity except 1 are primitive pth roots, and we have

<math>\Phi_p(z)=\frac{z^p-1}{z-1}=\sum_{k=0}^{p-1} z^k</math>.

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 <math>\Phi_{105}</math>, 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 nth roots of unity with the additional property^[1] that every value of the expression obtained by choosing values of the radicals (for example, signs of square roots) is a primitive nth root of unity. This was already shown by Gauss in 1797^[2]. Efficient algorithms exist for calculating such expressions^[3].

Cyclic groups

The nth 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 nth root of unity. The primitive nth roots of unity are those <math>e^{2 \pi i k/n}</math> where k and n are coprime. The number of different primitive nth roots of unity is given by Euler's totient function, <math>\phi(n)</math>. The nth 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.^[4] In particular, if a circulant Hermitian matrix is considered (for example, a discretized one-dimensional Laplacian with periodic boundaries^[5]), the orthogonality property immediately follows from the usual orthogonality of eigenvectors of Hermitian matrices.

Cyclotomic fields

Main article: Cyclotomic field

By adjoining a primitive nth root of unity to Q, one obtains the nth cyclotomic field F_n. This field contains all nth roots of unity and is the splitting field of the nth 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/nZ. 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.

Example calculations

Extracting coefficients

As a special case of orthogonality, we have

<math>\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}</math> i.e. the sum of the roots of unity raised to some fixed power <math>j</math> is <math>n</math> if <math>j</math> is divisible by <math>n</math>, and zero otherwise. This implies the following useful fact. If we have a polynomial or a series <math>f(x)</math> in <math>x</math>, where

then

<math>\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.</math> As a particular case, we have

<math>\frac{1}{n}

\sum_{k=0}^{n-1} f\left(e^{2 \pi i k/n} \right) = \sum_{n|j} f_j,</math> i.e. the sum of the coefficients that are divisible by <math>n</math>, 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 <math>[0, 10^{11}-1].\,</math> What is the probability that its digit sum will be divisible by <math>11</math>? Clearly the generating function of the digit sums of the integers in <math>[0, 10^{11}-1]\,</math> is

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

We seek the sum of the coefficients of <math>x</math> raised to a power that is divisible by <math>11</math>, giving

<math>\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},</math> because

<math>x^0 + x^1 + x^2 + \cdots + x^8 + x^9 = - x^{10}</math>

when <math>x</math> is an eleventh root of unity that is not one. Additional simplification now yields

<math>

\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.</math> This means that the desired probability is

<math> \frac{1}{11} - \frac{1}{11 \times 10^{10}} =

\frac{909090909}{10000000000} \approx \frac{1}{11}.</math> This problem was discussed on the newsgroup es.ciencia.matematicas, and the article is here.

The next-to-leading coefficient

We have the following equality:

<math> \left[z^{\varphi(n)-1}\right] \Phi_n(z) = - \mu(n)</math>

where <math>\mu</math> is the Moebius function and <math>[z^n]</math> is the coefficient-extraction operator for formal power series. To see this, observe that

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

where the <math>z_{k, n}</math> are the primitive roots of unity, so we must show that

which we do by complete mathematical induction. It certainly holds for <math>n=1</math> and <math>n=2</math>, because

Now suppose it holds for <math>m<n</math>. We know that

<math> \sum_{k=1}^n z_{k, n} = 0 \quad \mbox{and hence} \quad

\sum_{d|n} \sum_{(k, n)=d} z_{k, n} = 0.</math> This implies that

But for <math>d>1\,</math> we have

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

<math>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}</math> when <math>(k, n)=d.\,</math> Substitution now yields

which is

because the sum of the Moebius function evaluated at the divisors of an integer <math>n</math> is zero. QED. This problem was discussed on the newsgroup es.ciencia.matematicas, and the article is here.

References

^ Landau, Susan & Miller, Gary L. (1985), "Solvability by radicals is in polynomial time", Journal of Computer and System Sciences 30 (2): 179–208, DOI 10.1016/0022-0000(85)90013-3
^ Gauss, Carl F. (1965). Disquisitiones Arithmeticae. Yale University Press, §§359–360. ISBN 0-300-09473-6.
^ Weber, Andreas & Keckeisen, Michael, Solving Cyclotomic Polynomials by Radical Expressions, <http://cg.cs.uni-bonn.de/personal-pages/weber/publications/pdf/WeberA/WeberKeckeisen99a.pdf>. Retrieved on 2007-06-22
^ T. Inui, Y. Tanabe, and Y. Onodera, Group Theory and Its Applications in Physics (Springer, 1996).
^ Gilbert Strang, "The discrete cosine transform," SIAM Review 41 (1), 135-147 (1999).

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.