- primenumbers@yahoogroups.com wrote:
> ________________________________________

I intuitively felt that the cyclotomic polynomial for n,

> ________________________________________________________________________

> 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

>

>

>

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 - --- In primenumbers@yahoogroups.com,

Kermit Rose <kermit@...> wrote:

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

You need to set

> 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.

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 - --- In primenumbers@yahoogroups.com, "David Broadhurst" wrote:
> You need to set k_r = exp(2*Pi*I*r/n) and remove the "mod n".

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

> 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.

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]))