Date: Mon, 1 Dec 1997 11:26:22 -0600 (CST)
From: Dave Rusin <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 <rusin@math.niu.edu>
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 <rusin@math.niu.edu>
Subject: Kurt Foster's solution 

---------- Forwarded message ----------
Date: Thu, 27 Nov 1997 12:27:44 -0700 (MST)
From: Kurt Foster <kfoster@rmi.net>
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 <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 <rusin@math.niu.edu>
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