Cyclotomic Polynomials



Andrew Arnold, Michael Monagan

The algorithms:

Download our papers:
A high-performance algorithm for calculating cyclotomic polynomials (PDF)
-Submitted to the International Workshop on Parallel and Symbolic Computation (PASCO), to be held July 18-21, 2010 in Grenoble, France.

Calculating Cyclotomic Polynomials (with new revisions) (PDF)
Calculating Cyclotomic Polynomials (PDF)
-Submitted with revisions April 26, 2010 to Mathematics of Computation. Originally submitted Oct 10, 2008.

The $n_{th}$ cyclotomic polynomial $\Phi_n(z)$ is monic polynomial whose roots are the $n_{th}$ primitive roots of unity. It is the minimal polynomial, over the integers, of the $n_{th}$ primitive roots of unity. The height of $\Phi_n(z)$, $A(n)$, is the largest coefficient of $\Phi_n(z)$ in terms of absolute value.

The $n_{th}$ inverse cyclotomic polynomial, $\Psi_n(z)$, is the monic polynomial whose roots are the $n_{th}$ non-primitive roots of unity.

We develop and implement algorithms to calculate cyclotomic polynomials, towards the end of studying their coefficients.

We have three algorithms for calculating cyclotomic polynomials $\Phi_n(z)$, which we use to calculate $\Phi_n(z)$ for "small" $n$. (Currently roughly $n<2*10^{10}$)

Our first algorithm does repeated polynomial division using the FFT to calculate images of $\Phi_n(z)$ modulo primes $p$, and then reconstructs $\Phi_n(z)$ by way of Chinese remaindering. Using this approach we were able to find the first examples of $n$ such that $A(n)>n^2, and n^4. We call this algorithm the FFT-CRT method.

Our second algorithm, the SPS algorithm, calculates $\Phi_n(z)$ as a quotient of sparse truncated power series. Our implementation of the SPS algorithm is roughly an order of magnitude faster than that of the FFT-CRT algorithm.

Our third, newest algorithm, the recursive SPS algorithm, computes $\Phi_n(z)$ in a manner similar to that of the SPS algorithm; however, with our new approach we truncate any intermediate power series in our compuation to as minimal degree as necessary. This improves on the SPS algorithm by roughly another order of magnitude. For instance, to compute $\Phi_{n}(z)$ for $n=3234846615$, the product of the first nine odd primes, it originally required some 12 hours and 40 GB of memory on a powerful server using the FFT-CRT method. Using the SPS algorithm we were able to compute the same polynomial in under a half hour using roughly 4 GB of memory. Using our newest algorithm (and more intelligent inline assembly overflow checking), we are able to compute $\Phi_n(z)$ in under a minute.

We have a fourth algorith, the big prime algorithm, which was used to compute $\Phi_n(z)$ for $n=mp$ with large prime divisor $p$. This algorithm was mostly used to study cyclotomic polynomials of order four and five with very large degree and very low height. If you are interested in a particular cyclotomic polynomial computation or would like to look at my source code you can email me at (ada26 AT sfu DOT ca).

The shape of the coefficients of $\Phi_n(z)$

We show some plots of coefficients of cyclotomic polynomials. These plots are of a subset of the coefficients of $\Phi_n(z)$; we take the coefficient of term of degree $k$, for $k$ a multiple of some prime $p$. We chose $p$ so that our plots are roughly 10000 data points. We see that for some cyclotomic polynomials, the coefficients appear to be somewhat random, others have very definite structure.

Plots of cyclotomic polynomial coefficients (LINK)

Data

Heights and lengths of cyclotomic polynomials

Library of data on the heights and lengths of cyclotomic polynomials
This data was produced using the FFT-CRT, SPS, and the resursive SPS algorithms, as well as low-memory variants of the SPS algorithms. For further details you can refer to my thesis. We also computed cyclotomic polynomials of particularly large height which we have grouped into families. These families are not well-defined, but cyclotomic polynomials belonging to a family typically share many prime factors and have very similar height.

Cyclotomic polynomials of order 5 with potentially low height

For n < 3\cdot 10^8, the only \Phi_n(z) of order four for which A(n)=1 are exactly the n=p_1p_2p_3p_4 such that We calculate A(n) for n=p_1p_2p_3p_4p_5<2^{63} such that n/p_i satisfies the congruences above for i=1,2,...,5. That is, We only consider n=p_1p_2p_3p_4p_5 for which, given(p1,p2,p3,p4), p_5 is the minimal prime in its congruence class.
A(n) for all such n less than 2^63
Alternatively, here are all such n separted into their respective congruence sets. They all satisfy p_2 \equiv -1 mod p_1 and p_3 \equiv -1 mod p_1p_2:

Bounding cyclotomic coefficients of a given fixed degree

Write \Phi_n(z) = \sum_{k=0}^{\phi(n)}a_n(k)z^k.
Let a(k) = \max_n |a_n(k)}. That is, a(k) is the largest magnitude of any z^k cyclotomic coefficient. Similarly, let a_+(k) = \max_n a_n(k) and a_-(k) = \min_n a_n(k)$. We list a(k), a_+(k), and a_-(k) below. We also define alpha(b) to be the minimum k for which b occurs as |a_n(k)|. We similarly define \bar{alpha}(b) to be the smallest k for which b occurs as a_n(k). Note that \alpha(b) is the minimum of \bar{alpha}(b) and \bar{alpha}(-b).
The links below give alpha(b) for 0 \leq b \leq 927 and \bar{alpha}_(b) for 0 \leq |b| \leq 927. We also give the smallest n for which, given b and alpha(b)=k, that |a_n(k)|=b, and similarly for \bar{alpha}(k).
NOTE: n is not necessarily minimal in the data here for if alpha(b)=173. It is certainly minimal for alpha(b) < 173.

Code

Here is an implementation of the recursive SPS algorithm with 64-bit precision and no overflow checking: SPS4_64.c