Roots of Unity ExactlyDate: 02/13/2011 at 23:30:08 From: Soft Subject: Roots of Unity I want to express roots of unity as the sum of specific real numbers. How do you calculate these without the sine and cosine functions? For example, the 3rd roots of unity are 1 [1 + (square root of 3)i]/2 [1 - (square root of 3)i]/2 I want these exact, explicit sums -- not expressions such as 0.5 + 0.866i, which are not precise. It's really hard to figure out the formula. The closest I get is to set the roots of unity as (a + bi), resulting in (a + bi)^n = 1 -- then expand. But that's really a bad way ... ^_^ Date: 02/15/2011 at 00:12:28 From: Doctor Vogler Subject: Re: Roots of Unity Hi Soft, Thanks for writing to Dr. Math. You know how to express the roots of unity exactly using trigonometric functions. So I presume that you want to write them using rational operators (that is, +, -, *, /) and roots (square roots, cube roots, etc.). The funny thing about your request is that all roots of unity are automatically roots of 1. But I'm sure that "cube root of 1" is not the answer you're looking for, and yet it confuses the issue of exactly what you *are* looking for, and makes it harder to prove the cases where you can't get it. I imagine that you want to express the real and imaginary parts of the roots of unity in terms of rational operators and *real*-valued roots. It turns out that this is possible for n'th roots of unity only when n is some power of two times a product of distinct Fermat primes: 3 = 1 + 2^2^0 5 = 1 + 2^2^1 17 = 1 + 2^2^2 257 = 1 + 2^2^3 65537 = 1 + 2^2^4 No others are known. So the only odd n less than 2^2147483648 (or 10^646456993) for which this is possible are: 1, 3, 5, 15, 7, 21, 35, 105, 17, 51, 85, 255, 119, 357, 595, 1785 257, 771, 1285, 3855, 1799, 5397, 8995, 26985, 4369, 13107, 21845, 65535, 30583, 91749, 152915, 458745 65537, 196611, 327685, 983055, 458759, 1376277, 2293795, 6881385, 1114129, 3342387, 5570645, 16711935, 7798903, 23396709, 38994515, 116983545 16843009, 50529027, 84215045, 252645135, 117901063, 353703189, 589505315, 1768515945, 286331153, 858993459, 1431655765, 4294967295, 2004318071, 6012954213, 10021590355, 30064771065 And the only other numbers less than 2^2147483648 (or 10^646456993) for which this is possible are the above odd numbers times various powers of 2. The first few roots of unity are easy enough to express simply: 1st roots of 1: 1 2nd roots of 1: 1, -1 3rd roots of 1: 1, (1 + sqrt(-3))/2, (1 - sqrt(-3))/2 4th roots of 1: 1, -1, i, -i 5th roots of 1: 1, (sqrt(5) - 1)/4 + i*sqrt(2)*sqrt(5 + sqrt(5))/4, (sqrt(5) - 1)/4 - i*sqrt(2)*sqrt(5 + sqrt(5))/4, -(1 + sqrt(5))/4 + i*sqrt(2)*sqrt(5 - sqrt(5))/4, -(1 + sqrt(5))/4 - i*sqrt(2)*sqrt(5 - sqrt(5))/4 6th roots of 1: -1, -(1 + sqrt(-3))/2, -(1 - sqrt(-3))/2, and 3rd roots 8th roots of 1: (1 + i)*sqrt(2)/2, (1 - i)*sqrt(2)/2, (-1 + i)*sqrt(2)/2, (-1 - i)*sqrt(2)/2, and 4th roots 10th roots of 1: the 5th roots of 1 and their negatives 12th roots of 1: the 6th roots of 1 and i times each of them In general, to get an (n*k)'th root of 1, you just need to multiply an n'th root of 1 with a k'th root of 1. And to get another power of 2, you can just use the half-angle formulas for sine and cosine. All that's left is getting the roots for the Fermat primes 3, 5, 17, 257, and 65537 -- and I've just shown you 3 and 5. Now I'll explain how to compute the real and imaginary parts of a 17'th root of unity. The idea is to reduce the problem to solving a series of quadratic equations. Let z be a 17th root of 1. Then it turns out that the two numbers ... x1 = z + z^2 + z^4 + z^8 + z^16 + z^32 + z^64 + z^128 = z + z^2 + z^4 + z^8 + z^16 + z^15 + z^13 + z^9 and x2 = z^3 + z^6 + z^12 + z^24 + z^48 + z^96 + z^192 + z^384 = z^3 + z^6 + z^12 + z^7 + z^14 + z^11 + z^5 + z^10 ... are roots of a quadratic equation, namely x^2 + x - 4 = 0. Note that x1 + x2 = -1, and you can compute x1*x2 = -4. Now, the two numbers ... y1 = z + z^4 + z^16 + z^64 = z + z^4 + z^16 + z^13 y2 = z^2 + z^8 + z^32 + z^128 = z^2 + z^8 + z^15 + z^9 ... are roots of a quadratic equation with coefficients containing x1 (notice that y1 + y2 = x1, obviously; and y1*y2 = -1), while ... y3 = z^3 + z^12 + z^48 + z^192 = z^3 + z^12 + z^14 + z^5 y4 = z^6 + z^24 + z^96 + z^384 = z^6 + z^7 + z^11 + z^10 ... are roots of a quadratic equation with coefficients containing x2 (as before, y3 + y4 = x2, and y3*y4 = -1). Then you can write quadratic equations with coefficients containing the y's, the roots of which are the eight numbers z + z^16 z^2 + z^32 z^3 + z^48 z^4 + z^64 z^5 + z^80 z^6 + z^96 z^7 + z^112 z^8 + z^128. (Those are the same as z^i + 1/z^i.) Then the sixteen primitive 17th roots of 1 (the roots other than 1) are the sixteen roots of eight quadratic equations, the coefficients of which involve the above eight numbers. After all, z^i and 1/z^i have product 1 and the sum that we already computed; you can make a quadratic equation out of that. So the quadratic equations are x^2 + x - 4 = 0 y^2 - x*y - 1 = 0 w^2 - y*w + y' = 0 (when y = y1, y2, y3, y4, then y' = y3, y4, y2, y1) z^2 - w*z + 1 = 0. And the solutions are x = (-1 +/- sqrt(17))/2 y = (x +/- sqrt(x^2 + 4))/2 w = (y +/- sqrt(y^2 - 4y'))/2 z = (w +/- i*sqrt(4 - w^2))/2. So the bottom line is that x1 = (-1 + sqrt(17))/2 x2 = (-1 - sqrt(17))/2 y1 = (-1 + sqrt(17) + sqrt(2*17 - 2*sqrt(17)))/4 y2 = (-1 + sqrt(17) - sqrt(2*17 - 2*sqrt(17)))/4 y3 = (-1 - sqrt(17) + sqrt(2*17 + 2*sqrt(17)))/4 y4 = (-1 - sqrt(17) - sqrt(2*17 + 2*sqrt(17)))/4. I'll let you multiply out w1 = (y1 + sqrt(y1^2 - 4*y3))/2 w2 = (y1 - sqrt(y1^2 - 4*y3))/2 w3 = (y2 + sqrt(y2^2 - 4*y4))/2 w4 = (y2 - sqrt(y2^2 - 4*y4))/2 w5 = (y3 + sqrt(y3^2 - 4*y2))/2 w6 = (y3 - sqrt(y3^2 - 4*y2))/2 w7 = (y4 + sqrt(y4^2 - 4*y1))/2 w8 = (y4 - sqrt(y4^2 - 4*y1))/2. You can check that they are all real numbers, and they all have absolute value less than 2. And finally, you can get the sixteen roots that you are interested in with z = (w +/- i*sqrt(4 - w^2))/2. You can do the same thing to find the 257'th roots of 1 and to find the 65537'th roots of 1, but I'll let you work out the details. For your information, I got most of this from the book "Abstract Algebra" (2nd edition), by Dummit and Foote, chapter 14, section 5. It's a great book on abstract algebra for all kinds of things *except* your first introduction to abstract algebra. If you have any questions about this or need more help, please write back and show me what you have been able to do, and I will try to offer further suggestions. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/ Date: 03/02/2011 at 09:20:26 From: Soft Subject: Thank you (Roots of Unity) Well, astonishing! Now I know how to do that! Thanks! |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/