[dayepdwu] Cyclotomic primes

Cyclotomic polynomials evaluated at the nonnegative integers probably produce integer sequences each of which include an infinite number of primes within them.  This is in contrast to polynomials which have algebraic factorizations: they produce sequences with a finite number of primes, often zero.

Cyclotomic polynomials can be considered a superset of the polynomials a^2^n+1 that define Generalized Fermat primes (Generalized Fermat numbers).  This project was inspired by initially investigating primes of the form a^n+1 and noticing that that form always has an algebraic factorization except when the exponent is itself a power of 2.  What happens after the algebraic factors are removed?

Cyclotomic polynomials are the quotient after algebraic factors are removed from a^n-1 (note the minus sign).  (Future work: what happens if we start from a^n+1?)

We conjecture that each cyclotomic polynomial produces an infinite number of primes.  Cyclotomic polynomials are indexed by integers.  We verify that polynomials #1 through #1427 each produce at least 3 primes, or 4 if evaluating at 1 produced a prime.  (In other words, we approximate infinity with 3.)

(For which polynomials has the above conjecture been proved?  The linear polynomials, namely cyclotomic polynomials #1 and #2, each produce all the integers, so proving the conjecture for those two is equivalent to proving that there are an infinite number of primes among all the integers.  There are, thanks to Euclid, so the conjecture has at least been proven for cyclotomic polynomials #1 and #2.)

Update: the above conjecture is part of the Bunyakovsky conjecture.  Its current status is that only that only the linear polynomials have been proven to contain an infinitude of primes; everything beyond them is unknown.

for(n=1 , +oo , print1(n," :") ; c=0 ; for(x=0 , +oo , p=polcyclo(n,x) ; if(ispseudoprime(p) , print1(" ",x) ; if(x>1,c++); if(3==c , print();break))))

Full log output.

First 10 lines:

1 : 3 4 6
2 : 1 2 4 6
3 : 1 2 3 5
4 : 1 2 4 6
5 : 1 2 7 12
6 : 2 3 4
7 : 1 2 3 5
8 : 1 2 4 6
9 : 1 2 3 8
10 : 2 3 5

For example, the 10th cyclotomic polynomial is (x^10-1) / (x-1) / (x+1) / (x^4+x^3+x^2+x+1) = x^4 - x^3 + x^2 - x + 1 .  This polynomial evaluated at 2, 3, and 5 yields primes 11, 61, and 521.

The first column is OEIS A117544.

Last 30 lines:

1398 : 901 1195 1373
1399 : 1 191 935 1673
1400 : 69 185 218
1401 : 342 481 557
1402 : 2 81 327
1403 : 580 929 2584
1404 : 10 229 281
1405 : 1568 1721 1799
1406 : 15 424 576
1407 : 908 1094 1308
1408 : 22 36 671
1409 : 1 115 1199 6536
1410 : 734 880 896
1411 : 873 2218 2959
1412 : 623 1622 2111
1413 : 159 219 778
1414 : 103 299 347
1415 : 295 561 581
1416 : 295 298 1166
1417 : 551 614 1219
1418 : 20 35 42
1419 : 326 348 1230
1420 : 270 280 509
1421 : 250 530 700
1422 : 168 358 1263
1423 : 1 28 1630 1855
1424 : 42 360 722
1425 : 258 922 2619
1426 : 3 10 59
1427 : 1 2118 4288 4349

The largest prime seen was polcyclo(1409,6536) which has size 17846 bits.

Additionally, we also investigated evaluating the cyclotomic polynomials at negative integers.  Surprisingly, despite negative inputs, all polynomials of index greater than or equal to 3 seem to produce only positive outputs.  (Why?)  We verified that each polynomial up to index 1341 produces at least 3 prime numbers from negative inputs (or 4, if -1 produced a prime).

Full log output for negative inputs.

The polcyclo function in Pari/GP is nifty; it seems rather hairy to implement.  Its running time for a given index seems hard to predict.

For a cyclotomic prime p, does factoring p-1 tend to be easier than doing the same for a random prime of similar size?  Some brief experimentation seems to suggest yes.

Are some cyclotomic polynomials richer in primes than others, beyond that which can be explained by the Prime Number Theorem?

Cyclotomic polynomials define an infinite family of infinite integer sequences.  Because they are indexed by integers, it's easy to pick a random one.  Unfortunately, they become difficult to compute for large indices (2^22 or larger) and difficult to find primes in them beyond the range or indices investigated in this post.