Browse Groups

• ... I intuitively felt that the cyclotomic polynomial for n, Phi(n) = (x-k1)(x-k2). . . (x-k_m) mod n where m is the number of positive integers
Message 1 of 3 , May 10, 2009
View Source
> ________________________________________
> ________________________________________________________________________
> 3a. Re: Cyclotomic polynomial puzzles
> Posted by: "Phil Carmody" thefatphil@... thefatphil
> Date: Sun May 10, 2009 3:09 am ((PDT))
>
>
>
>> --- On Sat, 5/9/09, Phil Carmody <thefatphil@...>
>>
>>> 3a) Can you categorise p,q,r such that Phi(pqr) only has
>>> coefficients in {-1,0,1}?
>>> b) Can you find a bigger pqr with that property than
>>> anyone else?
>>>
>
> For largest-smallest, lets place a stake in the ground at p=29 with
> n = 29*31*5393 = 4848307
>
> It appears that swift evaluation of cyclotomic polynomials is the hard part - it requires large quantities of both CPU power and RAM. I wonder if there's a way using modular arithmetic, or even p-adic arithmetic to reduce the quantity of computation or storage.
>
> Phil
>
>
>

I intuitively felt that the cyclotomic polynomial for n,

Phi(n) = (x-k1)(x-k2). . . (x-k_m) mod n

where m is the number of positive integers < n, which are relatively
prime to n,
and the k1,k2,...k_m

are the m positive integers < n, that are relatively prime to n.

My intuition was not focused enough for me to see why I thought this.

I do not know why I expected that the coefficients of the cyclotomic
polynomial for n,
would never be greater than or equal to n.

David, can you give me a proof of this equation?

If this characterization of Phi(n) is true, for all n,

then using it, the difficulty of calculating the cyclotomic polynomial
is of approximately the same
order as the difficulty of calculating the integers relatively prime to n.

Kermit
• ... You need to set k_r = exp(2*Pi*I*r/n) and remove the mod n . For example, with n = 4, we get Phi(4) = (x - I)*(x + I) = x^2 + 1 which is not equivalent to
Message 1 of 3 , May 10, 2009
View Source
Kermit Rose <kermit@...> wrote:

> Phi(n) = (x-k1)(x-k2). . . (x-k_m) mod n
> where m is the number of positive integers < n,
> which are relatively prime to n, and the k1,k2,...k_m
> are the m positive integers < n, that are relatively prime to n.

You need to set
k_r = exp(2*Pi*I*r/n)
and remove the "mod n".

For example, with n = 4, we get

Phi(4) = (x - I)*(x + I) = x^2 + 1

which is not equivalent to your "modular construction"

print(lift((x-Mod(1,4))*(x-Mod(3,4))))
x^2 + 3

since 1 and 3 are inequivalent modulo 4.

David
• ... For the case at hand (order 3), it might be interesting, though, to use Phi_n(x)=product_(d|n)(1-x^(n/d))^mu(d) or maybe
Message 1 of 3 , May 10, 2009
View Source
> You need to set k_r = exp(2*Pi*I*r/n) and remove the "mod n".
> For example, with n = 4, we get
> Phi(4) = (x - I)*(x + I) = x^2 + 1
> which is not equivalent to your "modular construction"
> since 1 and 3 are inequivalent modulo 4.

For the case at hand (order 3), it might be interesting, though, to use

Phi_n(x)=product_(d|n)(1-x^(n/d))^mu(d)

or maybe

phi(n)=exp(sumdiv(n,d,moebius(d)*log(1-x^(n/d)+O(x^eulerphi(n)))))

(Dealing with the terms in an appropriate order, has anyone an idea for a significant "non-flat rejection criterion" ?)

Maximilian

(PARI)
phi(n)=my(d=divisors(n));prod(i=1,#d,(1-x^(n/d))^moebius(d[i]))
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.