Why is this true?

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

DT_
Posts: 44
Joined: Mon Feb 01, 2010 4:41 am UTC

Why is this true?

Postby DT_ » Thu Feb 11, 2010 11:50 pm UTC

The problem asks me to find the product of the n nth-roots of unity, when n is odd and n is even. I have [imath]\omega^0\times\omega^1\times\dots\times\omega^{n-1} = \omega^{\frac{n(n + 1)}{2}}[/imath].
If n is odd then I've shown the answer is 1. If n is even then I know that the answer is -1 but I can't quite get there:
Suppose n is even, then [imath]\omega^{\frac{n(n + 1)}{2}} = \left({\omega^{n+1}}\right)^{\frac{n}{2}} = \left(\omega^n\omega\right)^{\frac{n}{2}} = \omega^\frac{n}{2}[/imath].
This means I have a number that, when squared, produces 1. However, both 1 and -1 are square roots of 1, so why must it be that [imath]\omega^\frac{n}{2}[/imath] can only be -1 and not 1?

Any insight would be greatly appreciated.

User avatar
antonfire
Posts: 1772
Joined: Thu Apr 05, 2007 7:31 pm UTC

Re: Why is this true?

Postby antonfire » Fri Feb 12, 2010 12:04 am UTC

Because you're taking omega to be a primitive n'th root of unity, presumably. It's certainly not true that [imath]\omega^{n(n+1)/2} = -1[/imath] for any n'th root of unity [imath]\omega[/imath], even when n is odd. Take [imath]\omega=1[/imath], for instance.
Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?

User avatar
Kurushimi
Posts: 841
Joined: Thu Oct 02, 2008 12:06 am UTC

Re: Why is this true?

Postby Kurushimi » Fri Feb 12, 2010 12:46 am UTC

I'm pretty sure if you're multiplying to w^(n-1), it should equal w^(n(n-1)/2). I mean, if all you're doing is adding the exponents as in normal multiplication. I haven't worked with anything like this.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Why is this true?

Postby Qaanol » Fri Feb 12, 2010 1:00 am UTC

If [imath]\omega[/imath] is a primitive even root of unity, can you see why [imath]\omega^{\frac{n}{2}}=-1[/imath]?

One way to show your desired result is through rearranging the multiplication by pairing up complex conjugates:

[imath]\omega^0\cdot\omega^{\frac{n}{2}}\cdot\left(\omega^1\cdot\omega^{n-1}\right)\cdot\left(\omega^2\cdot\omega^{n-2}\right)\cdots\left(\omega^{\frac{n}{2}-1}\cdot\omega^{n-\left(\frac{n}{2}-1\right)}\right)[/imath]

But this is just

[imath](1)(-1)\cdot1\cdot1\cdots1[/imath]
wee free kings

DT_
Posts: 44
Joined: Mon Feb 01, 2010 4:41 am UTC

Re: Why is this true?

Postby DT_ » Fri Feb 12, 2010 1:30 am UTC

@Kurushimi: Yes, it should be n(n-1)/2.

@antonfire/Qaanol: Up until now I hadn't even heard of a primitive root of unity. It isn't in the textbook and the professor never talked it, we were just given that [imath]\omega=e^{2\pi i / n}[/imath] (I should mention that this isn't a math course, it's an algorithms course and we're working with fourier transforms). Looking on Wikipedia I see that if [imath]\omega[/imath] is a primitive root then [imath]\omega^x \not = 1[/imath] for any x < n, which gives me the desired result. However, as is often the case for me, it doesn't feel "right" because it's basically just a definition that gives me exactly what I was asking for in the first place; I don't really see where it came from or why [imath]\omega=e^{2\pi i / n}[/imath] is a primitive root.

hnooch
Posts: 128
Joined: Mon Nov 26, 2007 6:55 pm UTC

Re: Why is this true?

Postby hnooch » Fri Feb 12, 2010 1:41 am UTC

Here's an alternative approach. You want the product of the roots of the polynomial f(z) = zn-1. Do you know of any results that let you write this degree n polynomial as a product of polynomials of lesser degree?

User avatar
MartianInvader
Posts: 808
Joined: Sat Oct 27, 2007 5:51 pm UTC

Re: Why is this true?

Postby MartianInvader » Fri Feb 12, 2010 1:44 am UTC

Here's a hint for yet another approach: How did a young Gauss add up all the integers from 1 to 100? (Well, from 0 to 100 might be a slightly better analogy.)
Let's have a fervent argument, mostly over semantics, where we all claim the burden of proof is on the other side!

DT_
Posts: 44
Joined: Mon Feb 01, 2010 4:41 am UTC

Re: Why is this true?

Postby DT_ » Fri Feb 12, 2010 2:18 am UTC

@hnooch: Do you mean f(z) = ([imath]z^{n/2}[/imath] - 1)([imath]z^{n/2}[/imath] + 1) (if n is even), and then continue reducing those until you somehow get some result?

@MartianInvader: Unless I'm way off about your alternate approach, I think you misunderstood my question.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Why is this true?

Postby Qaanol » Fri Feb 12, 2010 3:05 am UTC

DT_ wrote:@Kurushimi: Yes, it should be n(n-1)/2.

@antonfire/Qaanol: Up until now I hadn't even heard of a primitive root of unity. It isn't in the textbook and the professor never talked it, we were just given that [imath]\omega=e^{2\pi i / n}[/imath] (I should mention that this isn't a math course, it's an algorithms course and we're working with fourier transforms). Looking on Wikipedia I see that if [imath]\omega[/imath] is a primitive root then [imath]\omega^x \not = 1[/imath] for any x < n, which gives me the desired result. However, as is often the case for me, it doesn't feel "right" because it's basically just a definition that gives me exactly what I was asking for in the first place; I don't really see where it came from or why [imath]\omega=e^{2\pi i / n}[/imath] is a primitive root.

If it's an algorithms course working with Fourier transforms, there's probably a lot of math they expect you've already had. For example, Euler's formula, [imath]e^{i\theta}=\cos\theta+i\cdot\sin\theta[/imath], should be background knowledge at this point, as should the locations of the nth roots of unity in the complex plane.

In any case, knowing [imath]\omega=e^{i\frac{2\pi}{n}}[/imath], you can work directly with powers of e, since [imath]\large\omega^m=e^{i\frac{2m\pi}{n}}[/imath]. Then when you multiply together the powers of [imath]\omega[/imath], you're summing the powers of e. This gives
[math]\large e^{i\frac{2\pi}{n}\frac{n(n-1)}{2}}=e^{i\pi(n-1)}[/math]

From there you can plug in for [imath]n=\begin{cases}2k+1 & \text{if } n \text{ is odd} \\ 2k & \text{if } n \text{ is even} \end{cases}[/imath] and simplify. If n is even it'll just become Euler's identity.
wee free kings

DT_
Posts: 44
Joined: Mon Feb 01, 2010 4:41 am UTC

Re: Why is this true?

Postby DT_ » Fri Feb 12, 2010 3:34 am UTC

That clears it up, thanks Qaanol.

User avatar
ConMan
Shepherd's Pie?
Posts: 1690
Joined: Tue Jan 01, 2008 11:56 am UTC
Location: Beacon Alpha

Re: Why is this true?

Postby ConMan » Fri Feb 12, 2010 3:53 am UTC

DT_ wrote:@hnooch: Do you mean f(z) = ([imath]z^{n/2}[/imath] - 1)([imath]z^{n/2}[/imath] + 1) (if n is even), and then continue reducing those until you somehow get some result?

@MartianInvader: Unless I'm way off about your alternate approach, I think you misunderstood my question.

I think it's more [imath]z^n-1=(z-1)(z^{n-1}+z^{n-2}+\dots+z+1)[/imath] which helps you find the sum of the primitive roots.
pollywog wrote:
Wikihow wrote:* Smile a lot! Give a gay girl a knowing "Hey, I'm a lesbian too!" smile.
I want to learn this smile, perfect it, and then go around smiling at lesbians and freaking them out.

hnooch
Posts: 128
Joined: Mon Nov 26, 2007 6:55 pm UTC

Re: Why is this true?

Postby hnooch » Fri Feb 12, 2010 7:22 am UTC

I guess I was unclear. I was heading in the direction of:

zn - 1 = (z - z1)(z - z2)...(z - zn)

where z1, z2, ... , zn are the n roots of 1. Expand the right hand side, and equate coefficients.

User avatar
MartianInvader
Posts: 808
Joined: Sat Oct 27, 2007 5:51 pm UTC

Re: Why is this true?

Postby MartianInvader » Fri Feb 12, 2010 2:30 pm UTC

What I was trying to hint at was that the way Gauss found the formula n(n+1)/2 was by "pairing off" the first and last element, then the second and second-to-last, etc, and found that each pair gave the same thing.

Similarly, [imath]\omega[/imath] and [imath]\omega^{n-1}[/imath] can pair off to form a cancelling pair (their product is 1). Indeed, for every root of unity a + bi, the number a - bi is also a root of unity, and their product is 1. This only works if b isn't zero, since otherwise they're both the same number.

So the product of all the non-real roots of unity is always 1. But the only real roots of unity are 1 and, if n is even, -1. Q.E.D.

Your approach works too, I just like to minimize formulas in my arguments :)
Let's have a fervent argument, mostly over semantics, where we all claim the burden of proof is on the other side!


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 7 guests