 Root of unity

In mathematics, a root of unity, or de Moivre number, is any complex number that equals 1 when raised to some integer power n. Roots of unity are used in many branches of mathematics, and are especially important in number theory, the theory of group characters, field theory, and the discrete Fourier transform.
The notion of root of unity also applies to any algebraic ring with a multiplicative identity element, namely a root of unity is any element of finite multiplicative order.
Contents
Definition
An nth root of unity, where n = 1,2,3,··· is a positive integer, is a complex number z satisfying the equation
An nth root of unity is primitive if it is not a kth root of unity for some smaller k:
Elementary facts
Every nth root of unity z is a primitive ath root of unity for some a where 1 ≤ a ≤ n: if z^{1} = 1 then z is a primitive first root of unity, otherwise if z^{2} = 1 then z is a primitive second (square) root of unity, otherwise, ..., and by assumption there must be a "1" at or before the nth term in the sequence.
If z is an nth root of unity and a ≡ b (mod n) then z^{a} = z^{b}. By the definition of congruence, a = b + kn for some integer k. But then,
Therefore, given a power z^{a} of z, it can be assumed that 1 ≤ a ≤ n. This is often convenient.
Any integer power of an nth root of unity is also an nth root of unity:
Here k may be negative. In particular, the reciprocal of an nth root of unity is its complex conjugate, and is also an nth root of unity:
Let z be a primitive nth root of unity. Then the powers z, z^{2}, ... z^{n−1}, z^{n} = z^{0} = 1 are all distinct. Assume the contrary, that z^{a} = z^{b} where 1 ≤ a < b ≤ n. Then z^{b−a} = 1. But 0 < b−a < n, which contradicts z being primitive.
Since an nth degree polynomial equation can only have n distinct roots, this implies that the powers of a primitive root z, z^{2}, ... z^{n−1}, z^{n} = z^{0} = 1 are in fact all of the nth roots of unity.
From the preceding facts it follows that if z is a primitive nth root of unity:
If z is not primitive there is only one implication:
An example showing that the converse implication is false is given by:
Let z be a primitive nth root of unity and let k be a positive integer. From the above discussion, z^{k} is a primitive root of unity for some a. Now if z^{ka} = 1, ka must be a multiple of n. The smallest number that is divisible by both n and k is their least common multiple, denoted by lcm(n, k). It is related to their greatest common divisor, gcd(n, k), by the formula:
i.e.
Therefore, z^{k} is a primitive ath root of unity where
Thus, if k and n are coprime z^{k} is also a primitive nth root of unity, and therefore there are φ(n) (where φ is Euler's totient function) distinct primitive nth roots of unity. (This implies that if n is a prime number, all the roots except +1 are primitive).
In other words, if R(n) is the set of all nth roots of unity and P(n) is the set of primitive ones, R(n) is a disjoint union of the P(n):
where the notation means that d goes through all the divisors of n, including 1 and n.
Since the cardinality of R(n) is n, and that of P(n) is φ(n), this demonstrates the classical formula
Examples
de Moivre's formula, which is valid for all real x and integers n, is
Setting x = 2π/n gives a primitive nth root of unity:
but for k = 1, 2, ... n−1,
This formula shows that on the complex plane the nth roots of unity are at the vertices of a regular nsided polygon inscribed in the unit circle, with one vertex at 1. (See the plots for n = 3 and n = 5 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 x, can be used to put the formula for the nth roots of unity into its most familiar form
It follows from the discussion in the previous section that this is a primitive root if and only if the fraction k/n is in lowest terms, i.e. that k and n are coprime.
The roots of unity are, by definition, the roots of a polynomial equation and are thus algebraic numbers. In fact, Galois theory can be used to show that they may be expressed as expressions involving integers and the operations of addition, subtraction, multiplication, division, and the extraction of roots. (There are more details later in this article at Cyclotomic fields.)
The equation z^{1} = 1 obviously has only one solution, +1, which is therefore the only primitive first root of unity. It is a nonprimitive 2nd, 3rd, 4th, ... root of unity.
The equation z^{2} = 1 has two solutions, +1 and −1. +1 is the primitive first root of unity, leaving −1 as the only primitive second (square) root of unity. It is a nonprimitive 4th, 6th, 8th, ...root of unity.
The only real roots of unity are ±1; all the others are nonreal complex numbers, as can be seen from de Moivre's formula or the figures.
The third (cube) roots satisfy the equation z^{3} − 1 = 0; the nonprincipal root +1 may be factored out, giving (z − 1)(z^{2} + z + 1) = 0. Therefore, the primitive cube roots of unity are the roots of a quadratic equation. (See Cyclotomic polynomial, below.)
The two primitive fourth roots of unity are the two square roots of the primitive square root of unity, −1
The four primitive fifth roots of unity are
The two primitive sixth roots of unity are the negatives (and also the square roots) of the two primitive cube roots:
Gauss observed that if a primitive nth root of unity can be expressed using only square roots, then it is possible to construct the regular ngon using only ruler and compass, and that if the root of unity requires third or fourth or higher radicals the regular polygon cannot be constructed. The 7th roots of unity are the first that require cube roots. Note that the real part and imaginary part are both real numbers, but complex numbers are buried in the expressions. They cannot be removed. See casus irreducibilis for details.
One of the primitive seventh roots of unity is^{[citation needed]}
where ω and ω^{2} are the primitive cube roots of unity exp(2πi/3) and exp(4πi/3).
The four primitive eighth roots of unity are ± the square roots of the primitive fourth roots, ±i. One of them is:
See heptadecagon for the real part of a 17th root of unity.
Periodicity
If z is a primitive nth root of unity, then the sequence of powers
 …, z^{−1}, z^{0}, z^{1}, …
is nperiodic (because z ^{j+n} = z ^{j}·z^{n} = z ^{j}·1 = z ^{j} for all values of j), and the n sequences of powers
 s_{k}: …, z^{k·(−1)}, z^{k·0}, z^{k·1}, …
for k = 1, …, n are all nperiodic (because z^{k·(j+n)} = z^{k·j}). Furthermore, the set {s_{1}, …, s_{n}} of these sequences is a basis of the linear space of all nperiodic sequences. This means that any nperiodic sequence of complex numbers
 …, x_{−1}, x_{0}, x_{1} , …
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_{1}·z^{1·j} + ··· + X_{n}·z^{n·j}
for some complex numbers X_{1}, …, X_{n} and every integer 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^{2πi/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).
This is a discrete Fourier transform.
Summation
Let SR(n) be the sum of all the nth roots of unity, primitive or not. Then
For n = 1 there is nothing to prove. For n > 1, it is "intuitively obvious" from the symmetry of the roots in the complex plane. For a rigorous proof, let z be a primitive nth root of unity. Then the set of all roots is given by z^{k}, k = 0, 1, ..., n−1, and their sum is given by the formula for a geometric series:
Let SP(n) be the sum of all the primitive nth roots of unity. Then
where μ(n) is the Mobius function.
In the section Elementary facts, it was shown that if R(n) is the set of all nth roots of unity and P(n) is the set of primitive ones, R(n) is a disjoint union of the P(n):
This implies
Applying the Mobius inversion formula gives
In this formula, if d < n SR(n/d) = 0, and for d = n, SR(n/d) = 1. Therefore, SP(n) = μ(n).
This is the special case c_{n}(1) of Ramanujan's sum c_{n}(s), defined as the sum of the sth powers of the primitive nth roots of unity:
Orthogonality
From the summation formula follows an orthogonality relationship: for j = 1, ···, n and j ' = 1, ···, n
where δ is the Kronecker delta and z is any primitive nth root of unity.
The matrix whose (j,k)th entry is
defines a discrete Fourier transform. Computing the inverse transformation using gaussian elimination requires O(n^{3}) operations. However, it follows from the orthogonality that U is unitary. That is,
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^{2}) operations. The fast Fourier transform algorithms reduces the number of operations further to O(n log n).
Cyclotomic polynomials
Main article: Cyclotomic polynomialThe 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_{1},z_{2},z_{3},...,z_{φ(n)} are the primitive nth 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., it cannot be written as the product of two positivedegree polynomials with rational coefficients). The case of prime n, which is easier than the general assertion, follows by applying Eisenstein's criterion to the polynomial ((z + 1)^{n}−1) / ((z + 1) − 1), and expanding via the binomial theorem.
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^{n} − 1 into irreducible factors.
 z^{1}−1 = z−1
 z^{2}−1 = (z−1)·(z+1)
 z^{3}−1 = (z−1)·(z^{2}+z+1)
 z^{4}−1 = (z−1)·(z+1)·(z^{2}+1)
 z^{5}−1 = (z−1)·(z^{4}+z^{3}+z^{2}+z+1)
 z^{6}−1 = (z−1)·(z+1)·(z^{2}+z+1)·(z^{2}−z+1)
 z^{7}−1 = (z−1)·(z^{6}+z^{5}+z^{4}+z^{3}+z^{2}+z+1)
Applying Möbius inversion to the formula gives
where μ is the Möbius function.
So the first few cyclotomic polynomials are
 Φ_{1}(z) = z−1
 Φ_{2}(z) = (z^{2}−1)·(z−1)^{−1} = z+1
 Φ_{3}(z) = (z^{3}−1)·(z−1)^{−1} = z^{2}+z+1
 Φ_{4}(z) = (z^{4}−1)·(z^{2}−1)^{−1} = z^{2}+1
 Φ_{5}(z) = (z^{5}−1)·(z−1)^{−1} = z^{4}+z^{3}+z^{2}+z+1
 Φ_{6}(z) = (z^{6}−1)·(z^{3}−1)^{−1}·(z^{2}−1)^{−1}·(z−1) = z^{2}−z+1
 Φ_{7}(z) = (z^{7}−1)·(z−1)^{−1} = z^{6}+z^{5}+z^{4}+z^{3}+z^{2}+z+1
If p is a prime number, then all the pth roots of unity except 1 are primitive pth roots, and we have
Substituting any positive integer ≥ 2 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 0, 1, or −1. The first exception is Φ_{105}. It is not a surprise it takes this long to get an example, because the behavior of the coefficients depends not so much on n as on how many odd prime factors appear in n. More precisely, it can be shown that if n has 1 or 2 odd prime factors (e.g., n = 150) then the nth cyclotomic polynomial only has coefficients 0, 1 or −1. Thus the first conceivable n for which there could be a coefficient besides 0, 1, or −1 is a product of the three smallest odd primes, and that is 3·5·7 = 105. 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 n = p_{1}·p_{2}· ... ·p_{t}, where p_{1} < p_{2} < ... < p_{t} are odd primes, p_{1} + p_{2} > p_{t}, and t is odd, then 1 − t occurs as a coefficient in the nth cyclotomic polynomial.^{[1]}
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 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^{[2]} 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.^{[3]} Efficient algorithms exist for calculating such expressions.^{[4]}
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 nth roots of unity form an irreducible representation of any cyclic group of order n. The orthogonality relationship also follows from grouptheoretic principles as described in character group.
The roots of unity appear as entries of 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.^{[5]} In particular, if a circulant Hermitian matrix is considered (for example, a discretized onedimensional Laplacian with periodic boundaries^{[6]}), the orthogonality property immediately follows from the usual orthogonality of eigenvectors of Hermitian matrices.
Cyclotomic fields
Main article: Cyclotomic fieldBy 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.^{[7]}
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.
See also
 Circle group
 Group scheme of roots of unity
 Primitive root modulo n
 Root of unity modulo n
 Dirichlet character
 Ramanujan's sum
Notes
 ^ 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.
 ^ 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/00220000(85)900133
 ^ Gauss, Carl F. (1965). Disquisitiones Arithmeticae. Yale University Press. pp. §§359–360. ISBN 0300094736.
 ^ Weber, Andreas; Keckeisen, Michael. "Solving Cyclotomic Polynomials by Radical Expressions". http://cg.cs.unibonn.de/personalpages/weber/publications/pdf/WeberA/WeberKeckeisen99a.pdf. Retrieved 20070622
 ^ 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).
 ^ The Disquisitiones was published in 1801, Galois was born in 1811, died in 1832, but wasn't published until 1846.
References
 Lang, Serge (2002), Algebra, Graduate Texts in Mathematics, 211 (Revised third ed.), New York: SpringerVerlag, ISBN 9780387953854, MR1878556
 Milne, James S. (1998). "Algebraic Number Theory". Course Notes. http://www.jmilne.org/math.
 Milne, James S. (1997). "Class Field Theory". Course Notes. http://www.jmilne.org/math.
 Neukirch, Jürgen (1999), Algebraic Number Theory, Grundlehren der mathematischen Wissenschaften, 322, Berlin: SpringerVerlag, ISBN 9783540653998, MR1697859
 Neukirch, Jürgen (1986). Class Field Theory. Berlin: SpringerVerlag. ISBN 3540152512.
 Washington, Lawrence C. (1997). Cyclotomic fields (2nd ed.). New York: SpringerVerlag. ISBN 0387947620.
 Derbyshire, John (2006). "Roots of Unity". Unknown Quantity. Washington, D.C.: Joseph Henry Press. ISBN 030909657X. http://www.JohnDerbyshire.com/Books/Unknown/page.html.
Categories: Algebraic numbers
 Cyclotomic fields
 Polynomials
 One
 Complex numbers
Wikimedia Foundation. 2010.
Look at other dictionaries:
root of unity — Math. a complex number that when raised to some positive integral power results in 1. * * * … Universalium
root of unity — a real or complex solution of the equation xn 1 . 0 where n is an integer * * * Math. a complex number that when raised to some positive integral power results in 1 … Useful english dictionary
Root (disambiguation) — A root is the part of a plant that is below ground. Root or Roots may also refer to: Contents 1 Computing 2 Geography 2.1 Switzerland … Wikipedia
Unity (Alastis album) — Unity Album par Alastis Sortie 2001 Enregistrement Nov./Dec. 2000 Sound Suite Studio, France Durée 46:53 Genre Dark Metal Producteur Alastis Terje Refsn … Wikipédia en Français
root — root1 rootlike, adj. /rooht, root/, n. 1. a part of the body of a plant that develops, typically, from the radicle and grows downward into the soil, anchoring the plant and absorbing nutriment and moisture. 2. a similar organ developed from some… … Universalium
Root — /rooht/, n. 1. Elihu /el euh hyooh /, 1845 1937, U.S. lawyer and statesman: Nobel peace prize 1912. 2. John Wellborn /wel beuhrn/, 1851 91, U.S. architect. * * * In botany, the underground anchoring part of a plant. It grows downward in response… … Universalium
Root locus — In control theory, the root locus is the locus of the poles and zeros of a transfer function as the system gain K is varied on some interval. The root locus is a useful tool for analyzing single input single output (SISO) linear dynamic systems.… … Wikipedia
Unity of type — Type Type, n. [F. type; cf. It. tipo, from L. typus a figure, image, a form, type, character, Gr. ? the mark of a blow, impression, form of character, model, from the root of ? to beat, strike; cf. Skr. tup to hurt.] [1913 Webster] 1. The mark or … The Collaborative International Dictionary of English
nth root — In mathematics, the nth root of a number x is a number r which, when raised to the power of n, equals x rn = x, where n is the degree of the root. A root of degree 2 is usually called a square root and a root of degree 3, a cube root. For example … Wikipedia
Square root — Measured fall time of a small steel sphere falling from various heights. The data is in good agreement with the predicted fall time of , where h is the height and g is the acceleration of gravity. In mathematics, a square root of a number x is a… … Wikipedia