Computing cyclotomic polynomials of large height.
Michael Monagan, CECM
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.