wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> GCDs of cyclotomic polynomials
        
(Message started by: Eigenray on Jul 31st, 2007, 11:25am)
Title: GCDs of cyclotomic polynomials
Post by Eigenray on Jul 31st, 2007, 11:25am
Let http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gifn(x) denote the n-th cyclotomic polynomial.  For n http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif m, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gifn and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gifm are relatively prime, since they are both irreducible in the PID http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbq.gif[x], and therefore 1 can be expressed as a linear combination of http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gifn(x) and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gifm(x), with coefficients in http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbq.gif[x].  Clearing denominators, we have:

d = f(x)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gifn(x) + g(x)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gifm(x),

where d http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif, and f,g http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif[x].

(1) Give a closed form for d, in terms of n and m.

(2) It follows from the above that for any integer x, gcd(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gifn(x), http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gifm(x)) divides d.  But what gcds are actually obtained?

Example:
(a) n=2, m=6:
(2-x)*(x+1) + 1*(x2-x+1) = 3,
so gcd(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif2(x), http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif6(x)) always divides 3.  And in fact, for x=2, we do get 3.

(b) n=3, m=6:
(1-x)*(x2+x+1) + (1+x)*(x2-x+1) = 2,
so gcd(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif3(x), http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif6(x)) always divides 2.  However, in this case, the gcd is always 1.
Title: Re: GCDs of cyclotomic polynomials
Post by Barukh on Aug 2nd, 2007, 11:39am
To start with: if  n, m are prime  numbers, then d = 1.
Title: Re: GCDs of cyclotomic polynomials
Post by Barukh on Aug 3rd, 2007, 10:05am
...Later (no proof):

- if gcd(m, n) = 1, then d = 1.
- if m = pa, n = pb, then d = p (p is a prime).
Title: Re: GCDs of cyclotomic polynomials
Post by Barukh on Aug 4th, 2007, 5:44am
I think I've got a proof for the case m,n are relatively prime.

If gcd(m, n) = 1, then there exist a, b s.t. ma - nb = 1. According to factorization of xn – 1 into cyclotomic polynomials (http://en.wikipedia.org/wiki/Root_of_unity#Cyclotomic_polynomials),  we have:

(xma - 1)/(x-1) = 1 + x + … + xma-1 = f(x)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cphi.gifm(x)
(xnb - 1)/(x-1) = 1 + x + … + xnb-1 = g(x)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cphi.gifn(x)

Therefore, f(x)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cphi.gifm(x) – xg(x)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cphi.gifn(x) = 1.
Title: Re: GCDs of cyclotomic polynomials
Post by Eigenray on Aug 5th, 2007, 12:10am
I think I know what the answer to (1) is based on some sample data: [hide]d=1 unless m/n or n/m is a prime power pk, in which case d=p[/hide], but I'd be interested in a proof.

I was originally thinking about this because of [link=http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_easy;action=display;num=1185548773]this[/link].  In that problem, I was actually interested in the answer to part (2), and the approach I used there was to just solve the finitely many instances of part (1) with Mathematica.  It wasn't until just now that I realized that part (2) is (probably) easier to solve directly.

Hint for (2): [hide]The polynomials http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gifpn(x) and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gifn(x) are related mod p (in two different cases)[/hide].

Edit: Actually, (2) isn't as easy as I thought: you still need to rule out the possibility of the gcd being a prime power.
Title: Re: GCDs of cyclotomic polynomials
Post by Eigenray on Aug 6th, 2007, 1:13am
I finally have the complete answer for (2).  Hint: It turns out [hide]http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gifpn(x) is never divisible by p2[/hide], except when p=2 and n=1.
Title: Re: GCDs of cyclotomic polynomials
Post by Barukh on Aug 8th, 2007, 9:12am

on 08/05/07 at 00:10:31, Eigenray wrote:
I think I know what the answer to (1) is based on some sample data: [hide]d=1 unless m/n or n/m is a prime power pk, in which case d=p[/hide]

That makes sense! It explains why (2, 12) is 1, while (2, 6) is 3.


Quote:
but I'd be interested in a proof.]

Does that mean this result is new?
Title: Re: GCDs of cyclotomic polynomials
Post by Eigenray on Aug 9th, 2007, 6:06am
I doubt it is new.  I was interested in (1) to solve (2), which I've done by other means.  But it's still a curious result.

It's not even clear why d is well-defined.  That is, if the coefficients of f and g have no common factor, and

d = fhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gifn + ghttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gifm,

does it follow that there is equality of ideals

(d) = (http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gifnhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif[x] + http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gifmhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif[x]) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cap.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif?


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board