Roots Of Unity - Is It Primitive?

  • Thread starter Sane
  • Start date
  • #1
221
0
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.

Code:
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)]
 
Last edited:

Answers and Replies

  • #2
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,950
19
Sane said:
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.
 
  • #3
221
0
Hurkyl said:
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.

Hurkyl said:
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.

Wikipedia said:
The fourth roots of unity are

[tex]\left\{ 1, +i, -1, -i \right\} ,[/tex]

of which +i and -i are primitive.
 
  • #4
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,950
19
Traditionally, and how you've written your code,

(a, b)

corresponds to

a + bi.
 
  • #5
221
0
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? :biggrin:
 
  • #6
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,950
19
I was hoping you'd see it just before you made your post. :wink:


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.
 
Last edited:
  • #7
mathwonk
Science Advisor
Homework Helper
11,274
1,475
this programmed approach seems silly to me. just think about it.
 
  • #8
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,950
19
I assume computing the primitive 4-th roots was merely a test of his program, not the end goal.
 
  • #9
221
0
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.

Hurkyl said:
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!

Hurkyl said:
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.
 
Last edited:
  • #10
221
0
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.

Code:
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)
 
  • #11
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,950
19
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.
 
  • #12
221
0
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?
 
  • #13
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,950
19
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)
 
  • #14
221
0
Oh my... so the algorithm dumbs down to something as little as...

Code:
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.
 
  • #15
CRGreathouse
Science Advisor
Homework Helper
2,824
0
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)2).
 
  • #16
221
0
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.
 
Last edited:

Related Threads on Roots Of Unity - Is It Primitive?

Replies
8
Views
6K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
7
Views
4K
Replies
2
Views
2K
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
6
Views
2K
Replies
1
Views
2K
  • Last Post
Replies
3
Views
2K
Replies
1
Views
684
Replies
5
Views
23K
Top