--- Mark Underwood <

mark.underwood@...> wrote:

> > > x^8 - x^4 + 1 has no prime factors below 73 (!)

> >

> > Now do you see why PIES has such the incredible density of primes

> that it has?

> > The above is just Phi(24). PIES is looking at Phi(49152) and Phi

> (98304). The

> > super-fruit subprojects can have even higher densities.

> >

> > One puzzle I set the PIES guys was the following:

> > <<<

> > Mathematicians are invited to calculate the relative density of

> primes

> > of the form Phi(24576,715*b^2) compared to arbitrary numbers of the

> > same size.

> > >>>

> > Just finding out what its smallest possible factor is should be an

> eye-opener.

> >

>

> Phil,

> Something has gone whizzing over my head, and it had to do with Pies

> and Phi's and such. But it looks totally fascninating and I hope to

> learn more along those lines.

Phi's are cyclotomic polynomials. They are the primitive parts of the family of

polynomials f(x) = x^n-1. Equivalently they are the minimal polynomial which

vanishes at each of the primitive n-th roots of unity.

e.g.

Phi(2) = x+1, as -1 is the only primitive 2nd root of unity,

Phi(4) = x^2+1, as +/-i are the only two primitive 4th roots of unity.

> My last result with x^8 - x^4 + 1 producing primes of the form 24n+1

That 24 comes from the fact that the above is Phi(24)

(In Pari/GP, us "polcyclo" to get the n-th cyclotomic polynomial.)

It's instructive to prove that if p|Phi(n,x) then, with a few exceptions,

p == 1 (mod n).

> got me to realize that there might be application to the "Web of

> Ones" thread, and without introducing factors of five into the

> coefficients. And sure enough,

>

> x^32 - x^24 + x^16 - x^8 + 1

Phi(80,x)

> yields only prime factors ending in one.

> (Except when x=0) Furthermore the prime factors are all of the form

> 80n + 1, and there are just 4 different prime factors below 1000:

> 241,401,641 and 881.

Yup, this is why cyclotomics are rich hunting grounds for primes, as they can't

have small divisors. My GEFs are typically 2-3 times as dense as Yves' GFNs, as

I reject even more small factors.

Phil

() ASCII ribbon campaign () Hopeless ribbon campaign

/\ against HTML mail /\ against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]

__________________________________________________

Do You Yahoo!?

Tired of spam? Yahoo! Mail has the best spam protection around

http://mail.yahoo.com