Computing cyclotomic polynomials of large height.

Michael Monagan, CECM

Tuesday December 4th, 2007 in IRMACS 10940.

Abstract:

The cyclotomic polynomial of order n is the irreducible factor of the
polynomial x^n-1 whose complex roots are the primitive n'th roots of
unity.  The cyclotomic polynomials of order 1, 2, 3, 4, 5, and 6 are

   x-1, x+1, x^2+x+1, x^2+1, x^4+x^3+x^2+x+1, and x^2-x+1.

Notice that the coefficients are all 1 in magnitude.  This is true for all n < 105.
But for n = 105, the cyclotomic polynomial has a -2 coefficient.  Let H_n
denote the height of the n'th cyclotomic polynomial, that is, the magnitude
of its largest coefficient, an integer.  A well known theorem of Paul Erdos states:

   For any constant c there exists and order n such that H_n > n^c.

As far as we know, no values of n were known for which H_n > n.

We have computed increasing values of H_n up to 100 million and other
selected values of n with large H_n.
In particular, for n = 1,181,895 we have H_n = 14,102,773 and
for n = 43,105,965, H_n = 862,550,638,890,874,931.  These are the
first n for which H_n > n and H_n > n^2 respectively.

In this talk we describe the two algorithms we used for computing H_n.  The first
algorithm does a sequence of polynomial divisions using the discrete FFT modulo
several machine primes.  The second algorithm does a sequence of sparse power series 
multiplications and divisions.  We have uses the first algorithm to find that
n = 2,317,696,095 has H_n > n^4 and are presently the second algorithm to
search 43,105,965 < n < 2,317,696,095 for the first H_n > n^3 and H_n > n^4.

This is joint work with Andrew Arnold.