Roots Of Unity - Is It Primitive?

[Sane]

All right, thanks to everybody's help, I've got the algorithm for determining the nth roots of unity.

However, for determining which ones are primitive, I'm still having a little trouble.

If n is odd, I can test if (n, k) are coprime. However, for even values of n, it seems that it doesn't work.

I took a guess and tried to see if (n-k-1, n) are coprime, to determine if the nth root of unity is primitive. It seems to work for all known examples I've tried.

Is that guess of mine incorrect? If not, what should I do for even values of n?

Here's some Python code, demonstrating that an even value of n, 4, yields only primitive roots of unity, by testing if (n-k-1, n) are coprime. Highlighted in blue.

import math

def resolve_limit (value):
    if value < 0.00001 and value > - 0.00001:
        return 0
    if value > 0.49999 and value < 0.50001:
        return 0.5
    if value < -0.49999 and value > -0.50001:
        return -0.5
    return value

def polar_to_complex (r, theta):
    a = math.cos (theta) * r
    b = math.sin (theta) * r
    a = resolve_limit (a)
    b = resolve_limit (b)
    return (a, b)

def gcd (a, b):
    while b:
        a, b = b, a % b
    return a

def coprime (a, b):
    if a == 0 or b == 0:
        return False
    return gcd (a, b) == 1

def prime_nth_roots (n):
    is_even = (n%2 == 0)

    for k in range (n):

        if is_even:
            [b][color=blue]if coprime (n-k-1, n)[/color][/b]:
                angle = k * 2 * math.pi / float(n)
                yield polar_to_complex (-1, angle)

        else:
            if coprime (k, n):
                angle = k * 2 * math.pi / float(n)
                yield polar_to_complex (1, angle)

print [root for root in prime_nth_roots (4)]

 

[Hurkyl]

If n is odd, I can test if (n, k) are coprime. However, for even values of n, it seems that it doesn't work.

Why do you think that?

Here's some Python code, demonstrating that an even value of n, 4, yields only primitive roots of unity, by testing if (n-k-1, n) are coprime.

This code gives wrong answers.

 

[Sane]

Why do you think that?

I think that because it wasn't outputting the correct answers, as suggested for certain situations. If you move my coprime function call test to the first dimension of the conditional statements, using the call "coprime (k, n)", and let n=4, it does not get the right answers.

This code gives wrong answers.

Are you positive? The code outputs:

>>>
[(-1.0, 0), (1.0, 0)]​

Which translates to +i and -i.

According to Wikipedia, these are the correct primitive nth roots of unity where n = 4.

The fourth roots of unity are

$$\left\{ 1, +i, -1, -i \right\} ,$$

of which +i and -i are primitive.

 

[Hurkyl]

Traditionally, and how you've written your code,

(a, b)

corresponds to

a + bi.

 

[Sane]

Yeah, I smacked my forehead right after I made that post. No sooner than I made that statement, I made the connection that my conclusion wasn't even correct in the first place. :tongue:

Oh geez. Hahah. So was it correct to only test coprime(n, k)?

Furthermore, if I only need "a primitive nth root of unity", do I only need to calculate and return the first rotation, since (1, n) will always be coprime? Which reduces the algorithm to O(1) time?

 

[Hurkyl]

I was hoping you'd see it just before you made your post.

Furthermore, if I only need "a primitive nth root of unity", do I only need to calculate and return the first rotation, since (1, n) will always be coprime? Which reduces the algorithm to O(n) time?

Why wouldn't it work?

Incidentally, isn't it much faster than O(n) time? You're just doing a couple multiplies and computing one sine and one cosine.

 

[mathwonk]

this programmed approach seems silly to me. just think about it.

 

[Hurkyl]

I assume computing the primitive 4-th roots was merely a test of his program, not the end goal.

 

[Sane]

Hahaha, yes. I actually immediately edited it to O(1) after I made the post. I'm surprised that you managed to catch my original post. You must have been close by at the time I posted.

It's O(1) because generally mathematical computations are expressed as a constant, even though they may themselves, take linear (or even polynomial) time.

Why wouldn't it work?

Just checking. That's great then! I just did not want to make a catastrophic mistake that could ressonate throughout my entire program!

I assume computing the primitive 4-th roots was merely a test of his program, not the end goal.

Precisely. The "Discrete Weighted Transform With An Irrational Base" (DWTIB) requires a primitive nth root of unity in the appropriate domain, where n is the chosen run time for the Algorithm W variant of the DWT.

 

[Sane]

I believe I found out why I figured my algorithm to be incorrect (yet used a wrong example in my first post)...

If n = 2, the only supposed primitive root is -1, yet my algorithm yields +1.

import math

def resolve_limit (value):
    if value < 0.00001 and value > - 0.00001:
        return 0
    if value > 0.49999 and value < 0.50001:
        return 0.5
    if value < -0.49999 and value > -0.50001:
        return -0.5
    return value

def deg_to_rad (deg):
    return deg * math.pi / 180.0

def complex_to_polar (a, b):
    r = (a**2.0 + b**2.0)**0.5
    theta = math.acos (a / r)
    return (r, theta)

def polar_to_complex (r, theta):
    a = math.cos (theta) * r
    b = math.sin (theta) * r
    a = resolve_limit (a)
    b = resolve_limit (b)
    return (a, b)

def gcd (a, b):
    while b:
        a, b = b, a % b
    return a

def coprime (a, b):
    if a == 0 or b == 0:
        return False
    return gcd (a, b) == 1

def prime_nth_roots (n):
    is_even = n%2 == 0
    for k in range (n):
        if coprime (k, n):
            angle = k * 2 * math.pi / float(n)
            yield polar_to_complex ((1, -1)[is_even], angle)

def a_prime_nth_root (n):
    is_even = n%2 == 0
    angle = 2 * math.pi / float(n)
    return polar_to_complex ((1, -1)[is_even], angle)

if __name__ == '__main__':
    n = 2
    
    print [root for root in prime_nth_roots (n)]
    print a_prime_nth_root (n)

 

[Hurkyl]

When I ran your original algorithm on 2 (after removing the "is_even" check), it gives me -1 is the only primitive root of 1.

When I run this new code, it says 1 is a primitive square root of 1.

 

[Sane]

In my second code I used a length of negative 1 for an even value of n. While in the first code, if you removed the "is_even" check, it would have used positive 1.

If a value of n is even, you need to either add pi to the angle, or set the length to negative 1.

That's not for something else is it?

 

[Hurkyl]

That's not for something else is it?

I think you're thinking of the trick to turn a primitive n-th root into a primitive (2n)-th root. (with n odd)

 

[Sane]

Oh my... so the algorithm dumbs down to something as little as...

def a_prime_nth_root (n):
    return polar_to_complex (1, 2 * math.pi / float(n))

Jesus christ, that's a lot simpler. Heh. Thanks for the help.

 

[CRGreathouse]

Hahaha, yes. I actually immediately edited it to O(1) after I made the post. I'm surprised that you managed to catch my original post. You must have been close by at the time I posted.

There's no way it's O(1). You're doing a division, which takes O(log(n)) absolute minimum -- and probably more like O(log(n)²).

 

[Sane]

Division and multiplication of 16-32 bit numbers is often only one operation for most 32-64 bit processors. n will never be more than 2 bytes.