Date: Mon, 1 Dec 1997 11:26:22 -0600 (CST)
From: Dave Rusin
To: [Permission pending]
Subject: Re: When does a polynomial admit cyclotomic roots?
Newsgroups: sci.math
In article <347B586C.41C6@math.mcgill.ca> you write:
>I am interested in determining when the polynomials
>
>f(t) = t^2 - 2t + 2 + t^(p+2)(t-1) + (t^(p+1) - 1)/(t+1)
>
>(p an odd integer) have roots which are nth roots of unity.
>Another way to say this is:
>
> When is gcd(f, t^n - 1) <> 1?
>
>In fact I have solved the problem using some brutal algebra.
>What I am looking for now is a more elegant solution.
>
>A colleague has suggested that there was a paper on this subject
>in the SIGSAM bulletin. Any ideas or references would be much
>appreciated.
I'm curious about what you found and what you proved. In maple, I did
with(numtheory):
F2:={(t^3-t^2+1)^n-(t^3-t+1)^n,cyclotomic(n,t)};
for i from 1 to 100 do x:=gcd(op(eval(subs(n=i,F2)))):if degree(x,t)>1 then lprint(i,x):fi:od:
and found out that the primitive n-th roots of unity are roots of such
an equation only if n = 6,8,9,10,12 (checked through n=100, as you can see).
Of course for each such n we have solutions for lots of p.
dave
==============================================================================
Date: Mon, 1 Dec 1997 22:41:39 -0500 (EST)
From: [Permission pending]
To: Dave Rusin
Subject: Re: When does a polynomial admit cyclotomic roots?
Hi Dave Rusin,
I don't quite understand what you've done since p doesn't show up
anywhere in your F2. In particular, p should be an odd integer which
I don't think you've accounted for. At least I hope there's some kind
of discrepancy like this since our answers disagree.
I found that f(t) admits the following cylotomic roots.
6th roots of unity <=> p == 0 mod 3
10th roots of unity <=> p == 1 mod 10
12th roots of unity <=> p == 3 mod 12
15th roots of unity <=> p == 5 mod 30
My proof was not so nice, as I indicated earlier. However, Kurt Foster
has suggested a nice argument. I will send it in a separate post.
Best Regards,
Thomas
[an attached copy of my letter deleted -- djr]
==============================================================================
Date: Mon, 1 Dec 1997 22:45:25 -0500 (EST)
From: [Permission pending]
To: Dave Rusin
Subject: Kurt Foster's solution
---------- Forwarded message ----------
Date: Thu, 27 Nov 1997 12:27:44 -0700 (MST)
From: Kurt Foster
To: [Permission pending]
Subject: Got it -- I think...
I'm posting the following proof outline to sci.math also...
Multiplying by (t+1) gives the equation
(1) t^(p+4) - t^(p+2) + t^(p+1) + t^3 - t^2 + 1 = 0
Plugging in t = exp(2*pi*i/n), and doing a bit of algebra yields
(2) cos((p+4)*pi/n) - cos(p*pi/n) + cos((p-2)*pi/n) = 0.
This may be recast (assuming (p+1)/n isn't a half-integer) as
(3) 2 * cos(3*pi/n) = cos(p*pi/n)/cos((p+1)*pi/n)
Direct verification rules out n = 3, 4, and 5 as possibilities, and
turns up the solution n = 6 when p == 3 (mod 6). The left side of (3) is
positive for n > 6, and is > 1 for n > 9. Inspection rules out any
solutions in the case n = 9. We assume henceforth that n > 6. We clearly
may restrict p to 0 =< p < n.
Taking logs (assuming n isn't 9) and applying the Mean Value Theorem
tells us that
(pi/n) * tan(x) = ln(2 * cos(3*pi/n)), p*pi/n < x < (p+1)*pi/n.
If n is sufficiently large, we may then write
(*) p < n/2 - (n/pi)*arctan(pi/n*ln(2*cos(3*pi/n))) < p+1,
which will for each n force the value of p. The limiting value of the
expression being subtracted from n/2 is 1/ln(2) as n increases without
bound, so it will be between 1 and 1.5 for sufficiently large n. It
follows that, if n is large enough, the integrality of p forces
p = n/2 - 2 if n is even, and p = (n-1)/2 -1 if n is odd.
Direct substitution of these values then shows the relation (3) fails.
All that remains is to mop things up for small values of n. A simple
computer routine checked the values of n = 7 to 40 (except n = 9), to see
whether (3) held to within 2^(-30). The program flagged the pairs
n = 8, p = 6; n = 10, p = 1; n = 12, p = 3; and n = 15, p = 5
The first value of p is even, so doesn't fit the original problem -- the
expression (1) isn't divisible by (t+1) if p is even -- but it does give a
solution of (3), and yields the primitive 8-th roots of unity as solutions
to (1) when p == 6 (mod 8). The other pairs do give solutions (direct
verification).
The program indicates that n >= 40 is "sufficiently large" for the
"large n" argument to apply. I'm sure this could be checked rigorously by
someone more ambitious than I am ;-)
==============================================================================
Date: Mon, 1 Dec 1997 22:59:35 -0600 (CST)
From: Dave Rusin
To: [Permission pending]
Subject: Re: When does a polynomial admit cyclotomic roots?
Thanks. I missed I sign, and didn't mind your requirement that p be odd.
In fact, my reasoning was: given that f(t)=0, we rearrange terms to deduce
- t^(p+1) = (t^3-t^2+1)/(t^3-t+1)
(That ^ is the sign I missed).
If you want roots of f which are nth roots of unity, then t^n=1, so
raising both sides to the nth power gives
(-1)^n = (t3-t^2+1)^n/(t^3-t+1)^n
and therefore t must also be a root of
F2 = (t^3-t^2+1)^n - ( (-1)(t^3 - t + 1) )^n
This is the point at which I used maple; note that p is irrelevant here,
although your condition that p be odd will mean that some of the values of
n for which F2 has a common root with cyclotomic(n) will have to be
rejected (don't meet your extra condition).
Kurt's solution is nice.
Thanks for responding.
dave
==============================================================================
Date: Thu, 4 Dec 1997 00:55:26 -0500 (EST)
From: [Permission pending]
To: Dave Rusin
Subject: Re: When does a polynomial admit cyclotomic roots?
On Mon, 1 Dec 1997, Dave Rusin wrote:
> Thanks. I missed I sign, and didn't mind your requirement that p be odd.
> In fact, my reasoning was: given that f(t)=0, we rearrange terms to deduce
> - t^(p+1) = (t^3-t^2+1)/(t^3-t+1)
> (That ^ is the sign I missed).
>
> If you want roots of f which are nth roots of unity, then t^n=1, so
> raising both sides to the nth power gives
> (-1)^n = (t3-t^2+1)^n/(t^3-t+1)^n
> and therefore t must also be a root of
> F2 = (t^3-t^2+1)^n - ( (-1)(t^3 - t + 1) )^n
>
> This is the point at which I used maple; note that p is irrelevant here,
> although your condition that p be odd will mean that some of the values of
> n for which F2 has a common root with cyclotomic(n) will have to be
> rejected (don't meet your extra condition).
Oh I see! Thanks for explaining it to me. This is also a nice way to
approach the problem. I tried it with the change in sign you suggested and
now the n's which show up are 6, 8, 10, 12 and 15. So the only incongruous
one is 8 which corresponds to an even value of p.
> Thanks for responding.
Thank you for your suggestion.
Best Regards,
Thomas