Root of unity

11 years, 1 month ago

2k times

1. Could someone explain the first statement? I understand why the roots are plus-minus paired (if is even), but what does the equation mean? An explanation of the equation will be appreciated.

asked May 17, 2012 at 0:31

answered May 17, 2012 at 1:50

Will Orrick

1 gold badge48 silver badges81 bronze badges

answered May 17, 2012 at 0:39

12 gold badges224 silver badges386 bronze badges

In mathematics, a root of unity, occasionally called a de Moivre number, is any complex number that yields 1 when raised to some positive integer power . Roots of unity are used in many branches of mathematics, and are especially important in number theory, the theory of group characters, and the discrete Fourier transform.

Roots of unity can be defined in any field. If the characteristic of the field is zero, the roots are complex numbers that are also algebraic integers. For fields with a positive characteristic, the roots belong to a finite field, and, conversely, every nonzero element of a finite field is a root of unity. Any algebraically closed field contains exactly th roots of unity, except when is a multiple of the (positive) characteristic of the field.

Specifically, if K is a field, then the nth roots of unity in K
are the numbers ω in K such that ωn=1.
Equivalently, they are all the roots of the polynomial Xn-1. No
matter what field K is, the polynomial can never have more than n
roots. Clearly 1 is an example; if n is even, then -1 will also
be an example. Beyond this, the list of possibilities depends on K.

• If K is the set of real numbers, then 1 and -1 are the
  only possibilities.

• If K is the field of the complex numbers, the fundamental
  theorem of algebra assures us that the polynomial Xn-1 has exactly
  n roots (counting multiplicities). Comparing Xn-1 with its
  formal derivative (), n⁢Xn-1, we see that they are coprime, and
  therefore all the roots of Xn-1 are distinct. That is, there exist
  n distinct complex numbers ω such that ωn=1.

  If drawn on the complex plane, the nth roots of unity are the
  vertices of a regular n-gon centered at the origin and with a vertex
  at 1.

• If K is a finite field having pa elements, for p a prime,
  then every nonzero element is a pa-1th root of unity (in
  fact this characterizes them completely; this is the role of the
  Frobenius operator). For other n, the answer is more complicated.
  For example, if n is divisible by p, the formal derivative of
  Xn-1 is n⁢Xn-1, which is zero since the
  characteristic of K is p and n is zero modulo
  p. So one is not guaranteed that the roots of unity will be
  distinct. For example, in the field of two elements, 1=-1, so there
  is only one square root of 1.

If an element ω is an nth root of unity but is not an mth
root of unity for any <math id="p4.m4" alttext="0<m0<m<n, then ω is called a
nth root of unity. For example,
the number ζ defined above is a
nth root of unity. If ω∈ℂ is a primitive nth
root of unity, then all of the primitive nth roots of unity have the
form ωm for some m∈ℤ with gcd⁡(m,n)=1.

The roots of unity in any field have many special relationships to one
another, some of which are true in general and some of which depend on
the field. It is upon these relationships that the various algorithms
for computing fast Fourier transforms are based.

Finally, one could ask about similar situations where K is not a
field but some more general object. Here, things are much more
complicated. For example, in the ring of endomorphisms of a vector
space, the unipotent linear transformations are the closest analogue
to roots of unity. They still form a group, but there may be many
more of them than n. In a finite group, every element g has a
power n such that gn=1.

Gauss generalized his method to
find an expression using radicals for any root of unity.
(Compare with Vandermonde’s method.)

For any expression \(\gamma\) containing \(\zeta\), define
\(S \gamma\) to be the same expression with each \(\zeta\) replaced by
\(\zeta^g\).

Suppose \(\gamma\) satisfies \(S^D \gamma = \gamma\). Then
define

Example: Take \(d=1, D=2, p=17\). Then \(q = 2, \beta = -1\). If we take
\(\gamma = x_1\) as defined earlier discussing
the 17-gon,
we see \(S x_1 = x_2, S x_2 = x_1\),
thus \(S^2 \gamma = \gamma\). Then the expression \(t\) is simply

and we saw before \(t^2\) must be an integer.

To continue, we took \(d=2, D=4\). Again \(q=2, \beta=-1\) and we can take
\(\gamma = y_1\) as defined earlier. Then note \(S^4 \gamma = \gamma\)
and we see \((y_1 — y_2)^2\) is an integer.

Now define \(t_i\) to be \(t\) where each \(\beta\) has been replaced by \(\beta^i\).
Then we have

(much cancellation occurs since the sum of the \(k\)th
roots of unity is zero for any \(k> 1\)).
By a similar argument, each \(t_i^q\) is known, and thus if we choose
\(q\)th roots correctly, then

Example: Let \(\zeta\) be a primitive fifth root of unity.
We shall derive an expression for \(\zeta\) in terms of a primitive
fourth root of unity.

We compute \(t_1^4\) and choose a fourth root of the result, from which we work
out \(t_2, t_3, t_4\). To make the computation easier we notice

Now that we have found the solutions of \(t_1\), we compute

(Actually first equation is unnecessary since we already have \(t_2\)
in terms of \(t_1\) from before.)

Thus after some algebraic manipulation we find

Finally, we have all four of the primitive fifth roots of unity:

where \(\alpha = \pm 1, \pm i\).

which can be verified to be the same solutions.

---

Algebraic expression

The th roots of unity are, by definition, the roots of the polynomial, and are thus algebraic numbers. As this polynomial is not irreducible (except for), the primitive th roots of unity are roots of an irreducible polynomial of lower degree, called the th cyclotomic polynomial, and often denoted . The degree of is given by Euler’s totient function, which counts (among other things) the number of primitive th roots of unity. The roots of are exactly the primitive th roots of unity.

Galois theory can be used to show that cyclotomic polynomials may be conveniently solved in terms of radicals. (The trivial form

Gauss proved that a primitive th root of unity can be expressed using only square roots, addition, subtraction, multiplication and division if and only if it is possible to construct with compass and straightedge the regular -gon. This is the case if and only if is either a power of two or the product of a power of two and Fermat primes that are all different.

If is a primitive th root of unity, the same is true for, and

is twice the real part of . In other words, is a reciprocal polynomial, the polynomial

that has as a root may be deduced from by the standard manipulation on reciprocal polynomials, and the primitive th roots of unity may be deduced from the roots of

by solving the quadratic equation

That is, the real part of the primitive root is

and its imaginary part is

is an irreducible polynomial whose roots are all real. Its degree is a power of two, if and only if is a product of a power of two by a product (possibly empty) of distinct Fermat primes, and the regular -gon is constructible with compass and straightedge. Otherwise, it is solvable in radicals, but one are in the casus irreducibilis, that is, every expression of the roots in terms of radicals involves nonreal radicals.

Explicit expressions in low degrees

• For, the cyclotomic polynomial is Therefore, the only primitive first root of unity is 1, which is a non-primitive th root of unity for every n > 1.
• As, the only primitive second (square) root of unity is −1, which is also a non-primitive th root of unity for every even . With the preceding case, this completes the list of real roots of unity.
• As, the primitive third (cube) roots of unity, which are the roots of this quadratic polynomial, are

},\ \frac .

• As, the two primitive fourth roots of unity are and .
• As, the four primitive fifth roots of unity are the roots of this quartic polynomial, which may be explicitly solved in terms of radicals, giving the roots

may take the two values 1 and −1 (the same value in the two occurrences).

• As, there are two primitive sixth roots of unity, which are the negatives (and also the square roots) of the two primitive cube roots:

• As 7 is not a Fermat prime, the seventh roots of unity are the first that require cube roots. There are 6 primitive seventh roots of unity, which are pairwise complex conjugate. The sum of a root and its conjugate is twice its real part. These three sums are the three real roots of the cubic polynomial

and the primitive seventh roots of unity are

}, where runs over the roots of the above polynomial. As for every cubic polynomial, these roots may be expressed in terms of square and cube roots. However, as these three roots are all real, this is casus irreducibilis, and any such expression involves non-real cube roots.

• As, the four primitive eighth roots of unity are the square roots of the primitive fourth roots, . They are thus

} \pm i\frac.

Cyclotomic fields

See main article: Cyclotomic field. By adjoining a primitive th root of unity to

one obtains the th cyclotomic field

This field contains all th roots of unity and is the splitting field of the th cyclotomic polynomial over

The field extension

has degree φ(n) and its Galois group is naturally isomorphic to the multiplicative group of units of the ring

As the Galois group of

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.

Orthogonality

} \cdot z^ = n \cdot\delta_

where is the Kronecker delta and is any primitive th root of unity.

The matrix whose th entry is

} \cdot U_ = \delta_,

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

Cyclic groups

The th roots of unity form under multiplication a cyclic group of order, 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 th root of unity.

Trigonometric expression

De Moivre’s formula, which is valid for all real and integers, is

Setting gives a primitive th root of unity – one gets

for . In other words,

is a primitive th root of unity.

This formula shows that in the complex plane the th roots of unity are at the vertices of a regular -sided polygon inscribed in the unit circle, with one vertex at 1 (see the plots for and on the right). This geometric fact accounts for the term «cyclotomic» in such phrases as cyclotomic field and cyclotomic polynomial; it is from the Greek roots «cyclo» (circle) plus «tomos» (cut, divide).

which is valid for all real, can be used to put the formula for the th roots of unity into the form

, is called a trigonometric number.

See also

• Argand system
• Circle group, the unit complex numbers
• Cyclotomic field
• Group scheme of roots of unity
• Dirichlet character
• Ramanujan’s sum
• Witt vector
• Teichmüller character

Relation to quadratic integers

For, both roots of unity and are integers.

For three values of, the roots of unity are quadratic integers:

• For they are Eisenstein integers .
• For they are Gaussian integers : see Imaginary unit.

For four other values of, the primitive roots of unity are not quadratic integers, but the sum of any root of unity with its complex conjugate (also an th root of unity) is a quadratic integer.

For, for any root of unity equals to either 0, ±2, or ± .

For, for any root of unity, equals to either 0, ±1, ±2 or ± .

Cyclotomic polynomials

See main article: Cyclotomic polynomial.

The zeros of the polynomial

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

and expanding via the binomial theorem.

Every th root of unity is a primitive th root of unity for exactly one positive divisor of . This implies that

This formula represents the factorization of the polynomial into irreducible factors:

Applying Möbius inversion to the formula gives

where is the Möbius function. So the first few cyclotomic polynomials are

If is a prime number, then all the th roots of unity except 1 are primitive th roots, and we have

Substituting any positive integer ≥&thinsp;2 for, this sum becomes a base 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 0, 1, or −1. The first exception is . It is not a surprise it takes this long to get an example, because the behavior of the coefficients depends not so much on as on how many odd prime factors appear in . More precisely, it can be shown that if has 1 or 2 odd prime factors (for example,) then the th cyclotomic polynomial only has coefficients 0, 1 or −1. Thus the first conceivable for which there could be a coefficient besides 0, 1, or −1 is a product of the three smallest odd primes, and that is . This by itself doesn’t prove the 105th polynomial has another coefficient, but does show it is the first one which even has a chance of working (and then a computation of the coefficients shows it does). A theorem of Schur says that there are cyclotomic polynomials with coefficients arbitrarily large in absolute value. In particular, if

are odd primes,

Many restrictions are known about the values that cyclotomic polynomials can assume at integer values. For example, if is prime, then if and only .

Group properties

Group of all roots of unity

The product and the multiplicative inverse of two roots of unity are also roots of unity. In fact, if and, then, and, where is the least common multiple of and .

Therefore, the roots of unity form an abelian group under multiplication. This group is the torsion subgroup of the circle group.

Group of th roots of unity

For an integer n, the product and the multiplicative inverse of two th roots of unity are also th roots of unity. Therefore, the th roots of unity form an abelian group under multiplication.

Given a primitive th root of unity, the other th roots are powers of . This means that the group of the th roots of unity is a cyclic group. It is worth remarking that the term of cyclic group originated from the fact that this group is a subgroup of the circle group.

Galois group of the primitive th roots of unity

be the field extension of the rational numbers generated over

by a primitive th root of unity . As every th root of unity is a power of, the field

contains all th roots of unity, and

is a Galois extension of

If is an integer, is a primitive th root of unity if and only if and are coprime. In this case, the map

induces an automorphism of

, which maps every th root of unity to its th power. Every automorphism of

is obtained in this way, and these automorphisms form the Galois group of

over the field of the rationals.

defines a group isomorphism between the units of the ring of integers modulo and the Galois group of

This shows that this Galois group is abelian, and implies thus that the primitive roots of unity may be expressed in terms of radicals.

Summation

Let be the sum of all the th roots of unity, primitive or not. Then

This is an immediate consequence of Vieta’s formulas. In fact, the th roots of unity being the roots of the polynomial, their sum is the coefficient of degree, which is either 1 or 0 according whether or .

Alternatively, for there is nothing to prove, and for there exists a root – since the set of all the th roots of unity is a group,, so the sum satisfies, whence .

Let be the sum of all the primitive th roots of unity. Then

where is the Möbius function.

In the section Elementary properties, it was shown that if is the set of all th roots of unity and is the set of primitive ones, is a disjoint union of the :

Applying the Möbius inversion formula gives

In this formula, if, then, and for : . Therefore, .

This is the special case of Ramanujan’s sum, defined as the sum of the th powers of the primitive th roots of unity:

Elementary properties

Every th root of unity is a primitive th root of unity for some, which is the smallest positive integer such that .

Any integer power of an th root of unity is also an th root of unity, as

This is also true for negative exponents. In particular, the reciprocal of an th root of unity is its complex conjugate, and is also an th root of unity:

If is an th root of unity and then . Indeed, by the definition of congruence modulo n, for some integer, and hence

Therefore, given a power of, one has, where is the remainder of the Euclidean division of by .

if and only if

If is not primitive then

Let be a primitive th root of unity. A power of is a primitive th root of unity for

is the greatest common divisor of and . This results from the fact that is the smallest multiple of that is also a multiple of . In other words, is the least common multiple of and . Thus

Thus, if and are coprime, is also a primitive th root of unity, and therefore there are distinct primitive th roots of unity (where is Euler’s totient function). This implies that if is a prime number, all the roots except are primitive.

In other words, if is the set of all th roots of unity and is the set of primitive ones, is a disjoint union of the :

where the notation means that goes through all the positive divisors of, including and .

Since the cardinality of is, and that of is, this demonstrates the classical formula

Periodicity

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

is -periodic (because for all values of), and the sequences of powers

for are all -periodic (because). Furthermore, the set of these sequences is a basis of the linear space of all -periodic sequences. This means that any -periodic sequence of complex numbers

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

for some complex numbers and every integer .

This is a form of Fourier analysis. If is a (discrete) time variable, then is a frequency and is a complex amplitude.

Choosing for the primitive th root of unity

allows to be expressed as a linear combination of and :

This is a discrete Fourier transform.

Notes and References

1. Book: Hadlock, Charles R.. Field Theory and Its Classical Problems, Volume 14. Cambridge University Press. 2000. 978-0-88385-032-9. 84–86.
2. Book: Lang, Serge. Roots of unity. Algebra. Springer. 2002. 978-0-387-95385-4. 276–277. https://books.google.com/books?id=Fge-BwqhqIYC&pg=PA276.
3. Emma Lehmer, On the magnitude of the coefficients of the cyclotomic polynomial, Bulletin of the American Mathematical Society 42 (1936), no. 6, pp. 389–392.
4. Landau. Susan. Miller. Gary L.. Solvability by radicals is in polynomial time. Journal of Computer and System Sciences. 30. 2. 179–208. 1985. 10.1016/0022-0000(85)90013-3. free.
5. Book: Gauss, Carl F.. Carl Friedrich Gauss. Disquisitiones Arithmeticae. §§359–360. Yale University Press. 1965. 0-300-09473-6.
6. Web site: Weber. Andreas. Keckeisen. Michael. Solving Cyclotomic Polynomials by Radical Expressions. 22 June 2007.
7. T. Inui, Y. Tanabe, and Y. Onodera, Group Theory and Its Applications in Physics (Springer, 1996).
8. [Gilbert Strang]
9. The Disquisitiones was published in 1801, Galois was born in 1811, died in 1832, but wasn’t published until 1846.

General definition

Unless otherwise specified, the roots of unity may be taken to be complex numbers (including the number 1, and the number −1 if is even, which are complex with a zero imaginary part), and in this case, the th roots of unity are

However, the defining equation of roots of unity is meaningful over any field (and even over any ring), and this allows considering roots of unity in . Whichever is the field, the roots of unity in are either complex numbers, if the characteristic of is 0, or, otherwise, belong to a finite field. Conversely, every nonzero element in a finite field is a root of unity in that field. See Root of unity modulo n and Finite field for further details.

An th root of unity is said to be if it is not an th root of unity for some smaller, that is if

 

If n is a prime number, then all th roots of unity, except 1, are primitive.

In the above formula in terms of exponential and trigonometric functions, the primitive th roots of unity are those for which and are coprime integers.

Subsequent sections of this article will comply with complex roots of unity. For the case of roots of unity in fields of nonzero characteristic, see . For the case of roots of unity in rings of modular integers, see Root of unity modulo n.

References

• Web site: James S.. Milne. Class Field Theory. Course Notes. 1997.
  • Book: Neukirch, Jürgen. Class Field Theory. Springer-Verlag. Berlin. 1986. 3-540-15251-2.
• Book: Washington, Lawrence C.. Introduction to Cyclotomic Fields. Springer-Verlag. New York. 1997. 2nd. 0-387-94762-0.
• Book: Derbyshire, John. John Derbyshire. Unknown Quantity. Roots of Unity. 2006. Joseph Henry Press. Washington, D.C.. 0-309-09657-X. registration.