display | more...

Definition

Suppose I take a number x, and a natural number n. Now raise it to the nth power, by multiplying n x's together, in a process called exponentiation. If the answer comes out as 1, then x is an nth root of unity. A formal mathematical definition might look something like: The nth roots of unity are the solutions to the equation xn = 1. Mathematicians may like nothing more than being formal, but there have been no surprises so far, and this may not look like a very interesting concept. Let's see how far it can go. Indeed, there seems to be little of interest going on if we look at real numbers. There's only one positive nth root of 1, and that's 1 itself, for every n. If we allow negative numbers, then -1 is an nth root as well if and only if n is even. That's it. When we start to look at complex numbers, things begin to get a little more interesting. And there's a whole world of other algebraic number systems out there, such as modular arithmetic.

Complex numbers

There are n nth complex roots of unity, of the form exp(k*2πi/n), as k ranges from 0 to n-1. They are n equally spaced points on the unit circle. We can quickly prove that's all of them, since 1 is itself on the unit circle, powers of points inside the unit circle are still inside the unit circle, and powers of points outside, stay outside. The modulus of any complex solutions must be 1. What about the argument - the angle of the number on an Argand diagram? Since exponentiation multiplies this angle, it follows the angle must be a whole number of rotations, divided by n, for a number to be an n'th root. It's no accident that there are exactly n roots in the complex plane. It's a consequence of the fundamental theorem of algebra, but there are algebraic structures in which it is not always true, which we'll visit later.

However, we can still say more. Consider the case n=4. The 4th roots of unity are {1, i, -1, -i} in the complex number system. However, 1 is unity itself, and -1 is a square root. Only i and -i satisfy x4 = 1 and are not solutions to xn = 1 for any smaller value of n. These roots are known as primitive roots. For a given n, there are exactly φ(n) primitive roots, where φ is the Euler phi function, the number of integers less than n, but with no common factor with n (other than 1). By convention, one of these primitive roots can be denoted by ω. It turns out that the set of values {ω0 = 1, ω1, ω2 ... ωn-1} are all distinct and are precisely the nth roots of unity again. A lot of the jargon for these properties reflects this circular behavior. For example "ω is a generator of the cyclic group of nth roots", or "the primitive roots satisfy the nth cyclotomic polynomial". Many of these facts still hold true in other systems.

Modular arithmetic

We can similarly consider the notion of nth roots of unity in modular arithmetic where all operations are performed modulo some number m - in other words, we only consider ourselves with the remainders on division by m after any arithmetic. The easiest case turns out to be when m is a prime number. Let's use m=17 for an example, and pick g=3. We can write a table of the powers of g:

g0 =  1
g1 =  3
g2 =  9
g3 = 27 = 10 mod 17
g4 = g * g3 = 3 * 10 = 30 = 13 mod 17
g5 = g * g4 = 3 * 13 = 39 =  5 mod 17
...
By continuing the table, it turns out that 316 = 1 mod 17, but 3n is not 1 for any smaller value of n. 3 is a primitive 16th root, modulo 17. What's more, the 16 powers of 3 form a covering of all the nonzero values, modulo 17. Every nonzero value modulo 17 appears exactly once in this list of powers. We could reverse the table above, and get a new table of discrete logarithms:
 x | log3x mod 17
=======================
 1 |  0 (30 = 1)
 2 | 14 (314 = 2 mod 17)
 3 |  1 (31 = 3)
 4 | 12 (312 = 4 mod 17)
 5 |  5 (35 = 5 mod 17)
...
Just like regular logarithms, we could multiply numbers modulo 17 by adding their discrete logarithms, which sounds like there could be an easy way to multiply and divide in general. However, the problem of finding a discrete logarithm is hard. Apart from drawing up the whole table (which, even for a small number like 17, appears to be quite some work) there appears to be no efficient way of solving the discrete logarithm problem. Many cryptography systems depend on this, for it appears that exponentiation is a one-way function. It's quite easy to exponentiate, but so far seems very difficult to perform the inverse process of finding a discrete logarithm. Furthermore, many other problems can be shown to be equivalent to the discrete logarithm problem. Should anyone find an efficient method, it will have quite some consequences.

The behavior of multiplication modulo 17 (that the 16 non-zero values are all 16th roots of unity, and there exists a primitive 16th roots) is typical for prime moduli, and has many applications in number theory. The picture is quite different, however, for composite moduli.

Composite moduli

What about arithmetic modulo some composite number, such as 15? It turns out that things behave significantly differently from in the prime case. For example, here's a list of values x and their squares:
 x | x2 mod 15
===================
 1 |   1 = 1 mod 15
 4 |  16 = 1 mod 15
11 | 121 = 1 mod 15
14 | 196 = 1 mod 15
Already, there is something different going on. 1 appears to have four square roots modulo 15. Aren't there only supposed to be two? If you investigate further, you'll find there are eight fourth roots, no unique generator, and the values modulo 15 that have common factors with 15 are never roots of unity at all. Evidently the behavior is different because 15 is composite, but can we explain it?

If we reduce the values in the table modulo the prime factors of 15, that's 3 and 5, the problem does disappear. There's two square roots of unity for each prime factor. There are four possible combinations of these roots from the factors, which produce the four values in the table after applying the Chinese remainder theorem. Furthermore, we can look at the square roots modulo 15 as solutions to the equation x2-1 = 0 mod 15. The left hand side factors as a difference of two squares, so (x-1)(x+1) = 0 mod 15. Substituting one of the "rogue" values like x=4 and we get 3*5 = 0 mod 15, in other words, we have managed to find the factors. The fundamental theorem of algebra did not apply, because it's no longer true that if the product is zero, one of the original terms in the equation has to be zero, too. (In technical terms, modulo 15 arithmetic occurs in a ring, not a field).

Applications

It's already been implied that the behavior of the nth roots of unity has applications in number theory, particularly primality testing. If p is a prime, then all the non-zero elements modulo p are (p-1)'th roots of unity. This is equivalent to Fermat's little theorem (not with be confused with his "last"). The contrapositive statement requires a little care to formulate and we have to be particularly careful with the grammar. If there exists an element a modulo n such that an-1 is not 1 modulo n, then n is surely composite. Such an a is called a witness to the composite nature of n. The converse of the little theorem is not true - there do exist pseudoprimes which satisfy the condition of the little theorem for a particular value of a, but are composite. There are even composite numbers called Carmichael numbers that satisfy the Fermat condition for all values of a that have no common factor with n. However, with a little work, even these can be resolved. For a prime modulus n, there are not only (n-1)th roots, but also (n-1)th primitive roots, and finding one of those proves primality. For large values of n, the difficult part then becomes factoring n-1. However, it is a basis for many primality tests with low time complexity.

Roots of unity also surface in numerical applications such as the fast Fourier transform. While it can be formulated in terms of complex roots, it is also possible to construct an integer FFT by performing all arithmetic modulo some number with known roots. As noted above, the discrete logarithm problem is difficult, so finding the roots to some arbitrary modulus is not the way to proceed. Instead, a construction is used to produce a convenient modulus and roots which are easy to manipulate in computation. However, some care is required, since all arithmetic must be done to that modulus. Results that exceed that modulus will overflow and wrap around.

Sources

Hardy, G. H. and Wright, E. M. An Introduction to the Theory of Numbers, 5th ed. Oxford, England: Clarendon Press, 1979.

Grandlund, T. FFT Multiplication, from the GNU MP documentation. http://www.gnu.org/software/gmp/manual/html_node/FFT-Multiplication.html , viewed on July 16, 2005.

Log in or register to write something here or to contact authors.