NationMaster - Encyclopedia: 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. 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. Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ... Abraham de Moivre. ... The complex numbers are an extension of the real numbers, in which all non-constant polynomials have roots. ... Exponentiation is a mathematical operation, written an, involving two numbers, the base a and the exponent n. ... Illustration of a unit circle. ... In mathematics, the complex plane is a way of visualising the space of the complex numbers. ... Look up vertex in Wiktionary, the free dictionary. ... A regular pentagon A regular polygon is a simple polygon (a polygon which does not intersect itself anywhere) which is equiangular (all angles are equal) and equilateral (all sides have the same length). ...

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

Definition

The complex numbers z which solve The complex numbers are an extension of the real numbers, in which all non-constant polynomials have roots. ...

$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).$

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)$ . In group theory, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element a (called a generator of the group) such that, when written multiplicatively, every element of the group is a power of a (or na... In group theory, the term order is used in two closely related senses: the order of a group is its cardinality, i. ... In abstract algebra, a generating set of a group is a subset S such that every element of G can be expressed as the product of finitely many elements of S and their inverses. ... Coprime - Wikipedia /**/ @import /skins-1. ... The first thousand values of Ï†(n) In number theory, the totient (n) of a positive integer n is defined to be the number of positive integers less than or equal to n and coprime to n. ...

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. In mathematics, the imaginary unit (sometimes also represented by the Latin or the Greek iota) allows the real number system to be extended to the complex number system . ...

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{usqrt{5}-1}{4} + vsqrt{frac{5 + usqrt{5}}{8}}i right | u,v in {-1,1} right}.$

A primitive 8^th root of unity is

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

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. In mathematics, a geometric progression is a sequence of numbers such that the quotient of any two successive members of the sequence is a constant called the common ratio of the sequence. ... In mathematics, in the area of number theory, a Gaussian period is a certain kind of sum of roots of unity. ...

For n = 1:

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

For n > 1:

$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 .$

Orthogonality

One can use the summation formula to prove an orthogonality relationship: for j = 0, 1, ···, n − 1 and j ' = 0, 1, ···, n − 1 In mathematics, orthogonal is synonymous with perpendicular when used as a simple adjective that is not part of any longer phrase with a standard definition. ...

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

where $δ$ is the Kronecker delta. In mathematics, the Kronecker delta or Kroneckers delta, named after Leopold Kronecker (1823-1891), is a function of two variables, usually integers, which is 1 if they are equal, and 0 otherwise. ...

The $n times n$ matrix $U$ whose $(j, k)$ ^th entry is In mathematics, a matrix (plural matrices) is a rectangular table of numbers or, more generally, a table consisting of abstract quantities that can be added and multiplied. ...

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

is unitary. This matrix is the discrete Fourier transform (although normalization and sign conventions vary). In mathematics, a unitary matrix is an n by n complex matrix U satisfying the condition where In is the identity matrix and U* is the conjugate transpose (also called the Hermitian adjoint) of U. Note this condition says that a matrix U is unitary if it has an inverse... In mathematics, the discrete Fourier transform (DFT) is a transform for Fourier analysis of finite-domain discrete-time signals. ...

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. Group representation theory is the branch of mathematics that studies properties of abstract groups via their representations as linear transformations of vector spaces. ... In group theory, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element a (called a generator of the group) such that, when written multiplicatively, every element of the group is a power of a (or na... In mathematics, a character group is the group of representations of a group by complex-valued functions. ...

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). In linear algebra, the eigenvectors (from the German eigen meaning own) of a linear operator are non-zero vectors which, when operated on by the operator, result in a scalar multiple of themselves. ... A Hermitian matrix (or self-adjoint matrix) is a square matrix with complex entries which is equal to its own conjugate transpose â€” that is, the element in the ith row and jth column is equal to the complex conjugate of the element in the jth row and ith column, for... In vector calculus, the Laplace operator or Laplacian is a differential operator equal to the sum of all the unmixed second partial derivatives of a dependent variable. ...

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} fleft(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} fleft(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$ ? In mathematics, the digit sum of a given numbers is the sum of all its digits, e. ...

Clearly the generating function of the digit sums of the integers in $[0, 10^{11}-1],$ is In mathematics a generating function is a formal power series whose coefficients encode information about a sequence an that is indexed by the natural numbers. ...

$f(x) = left(x^0 + x^1 + x^2 + cdots + x^8 + x^9right)^{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} fleft(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} approx frac{1}{11}.$

This problem was discussed on the newsgroup es.ciencia.matematicas, and the article is here. 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. ...

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. It is also commonly denoted $ζ$ or $ζ n$ . In mathematics, the discrete Fourier transform (DFT) is a transform for Fourier analysis of finite-domain discrete-time signals. ...

Cyclotomic polynomials

The zeroes of the polynomial In mathematics, a polynomial is an expression in which constants and variables are combined using only addition, subtraction, multiplication, and positive whole number exponents (raising to a power). ...

$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.) The first thousand values of Ï†(n) In number theory, the totient (n) of a positive integer n is defined to be the number of positive integers less than or equal to n and coprime to n. ... In mathematics, the adjective irreducible means that an object cannot be expressed as a product of at least two non-trivial factors in a given ring. ... In mathematics, a rational number (commonly called a fraction) is a ratio or quotient of two integers, usually written as the vulgar fraction a/b, where b is not zero. ... In mathematics, Eisensteins criterion gives sufficient conditions for a polynomial to be irreducible over Q (or equivalently, over Z). ...

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 In mathematics, a divisor of an integer n, also called a factor of n, is an integer which evenly divides n without leaving a remainder. ...

$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 The classic MÃ¶bius inversion formula was introduced into number theory during the 19th century by August Ferdinand MÃ¶bius. ...

$Phi_n(z)=prod_{d,mid n}(z^{n/d}-1)^{mu(d)},$

where μ is the Möbius function. The classical MÃ¶bius function is an important multiplicative function in number theory and combinatorics. ...

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 In mathematics, a prime number (or a prime) is a natural number that has exactly two (distinct) natural number divisors, which are 1 and the prime number itself. ...

$Phi_p(z)=frac{z^p-1}{z-1}=sum_{k=0}^{p-1} z^k$ . Substituting for $zinmathbb{Z}^{+}$ , this is 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 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 1pmod{p}$ or $d equiv 0pmod{p}$ . In recreational mathematics, a repunit is a number like 11, 111, or 1111 that contains only the digit 1. ... In mathematics, a prime number (or a prime) is a natural number that has exactly two (distinct) natural number divisors, which are 1 and the prime number itself. ...

While in general polynomials of degree higher than 4 cannot be solved by radicals, cyclotomic polynomials can. This is because their Galois group is abelian, and hence solvable. Thus, every root of unity has an expression in radical form. Algorithms exist for calculating such expressions. The Abelâ€“Ruffini theorem (also known as Abels Impossibility Theorem) states that there is no general solution in radicals to polynomial equations of degree five or higher. ... In mathematics, an nth root of a number a is a number b, such that bn=a. ... In mathematics, a Galois group is a group associated with a certain type of field extension. ... Abelian, in mathematics, is used in many different definitions: In group theory: Abelian group, a group in which the binary operation is commutative Category of abelian groups Ab has abelian groups as objects and group homomorphisms as morphisms Metabelian group is a group where the commutator subgroup is contained in... In mathematics, computing, linguistics, and related disciplines, an algorithm is a procedure (a finite set of well-defined instructions) for accomplishing some task which, given an initial state, will terminate in a defined end-state. ...

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. The classical Möbius function is an important multiplicative function in number theory and combinatorics. ...

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. Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers. ...

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. The classical Möbius function is an important multiplicative function in number theory and combinatorics. ...

Cyclotomic fields

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/nZ. In mathematics, the n-th roots of unity or de Moivre numbers, named after Abraham de Moivre (1667 - 1754), are complex numbers located on the unit circle. ... In abstract algebra, a field is an algebraic structure in which the operations of addition, subtraction, multiplication and division (except division by zero) may be performed, and the same rules hold which are familiar from the arithmetic of ordinary numbers. ... In abstract algebra, the splitting field of a polynomial P(X) over a given field K is a field extension L of K, over which P factorizes into linear factors X âˆ’ ai, and such that the ai generate L over K. It can be shown that such splitting fields exist... In mathematics, the n-th roots of unity or de Moivre numbers, named after Abraham de Moivre (1667 - 1754), are complex numbers located on the unit circle. ... In mathematics, more specifically in abstract algebra, field extensions are the main object of study in field theory. ... In mathematics, a Galois group is a group associated with a certain type of field extension. ... In abstract algebra, a group isomorphism is a function between two groups that sets up a one-to-one correspondence between the elements of the groups in a way that respects the given group operations. ...

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 quite explicitly in terms of Gaussian periods: this theory from the Disquisitiones Arithmeticae of Gauss was published many years before Galois. In abstract algebra, an abelian extension is a field extension for which the associated Galois group is abelian. ... In mathematics, a Gaussian period is a certain kind of sum of roots of unity. ... The Disquisitiones Arithmeticae is a textbook of number theory written by German mathematician Carl Friedrich Gauss and first published in 1801 when Gauss was 24. ... (30 April 1777 â€“ 23 February 1855) was a German mathematician and scientist of profound genius who contributed significantly to many fields, including number theory, analysis, differential geometry, geodesy, magnetism, astronomy and optics. ...

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. Leopold Kronecker Leopold Kronecker (December 7, 1823 - December 29, 1891) was a German mathematician and logician who argued that arithmetic and analysis must be founded on whole numbers, saying, God made the integers; all else is the work of man (Bell 1986, p. ... In algebraic number theory, the Kronecker-Weber theorem states that every finite abelian extension of the field of rational numbers , or in other words every algebraic number field whose Galois group over is abelian, is a subfield of a cyclotomic field, i. ...

External links

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

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

Solving Cyclotomic Polynomials by Radical Expressions by Andreas Weber and Michael Keckeisen

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.

Contents