Search

P. Turan asked if there exists an absolute constant C such that for every polynomial f ∈ Z[x] there exists an irreducible polynomial g ∈ Z[x] with deg(g) ≤ deg(f) and L(f − g) ≤ C, where L(·) denotes the sum of the absolute values of the coefficients. We show that C = 5 suffices for all integer polynomials of degree at most 40 by investigating analogous questions in Fp[x] for small primes p. We also prove that a positive proportion of the polynomials in F2[x] have distance at least 4 to an arbitrary irreducible polynomial.

We present three algorithms to calculate Φ n ( z ) \Phi _n(z) , the n t h n_{th} cyclotomic polynomial. The first algorithm calculates Φ n ( z ) \Phi _n(z) by a series of polynomial divisions, which we perform using the fast Fourier transform. The second algorithm calculates Φ n ( z ) \Phi _n(z) as a quotient of products of sparse power series. These two algorithms, described in detail in the paper, were used to calculate cyclotomic polynomials of large height and length. In particular, we have found the least n n for which the height of Φ n ( z ) \Phi _n(z) is greater than n n , n 2 n^2 , n 3 n^3 , and n 4 n^4 , respectively. The third algorithm, the big prime algorithm, generates the terms of Φ n ( z ) \Phi _n(z) sequentially, in a manner which reduces the memory cost. We use the big prime algorithm to find the minimal known height of cyclotomic polynomials of order five. We include these results as well as other examples of cyclotomic polynomials of unusually large height, and bounds on the coefficient of the term of degree k k for all cyclotomic polynomials.

Jenkins in 2003 showed that every odd perfect number is divisible by a prime exceeding 10 7 . Using the properties of cyclotomic polynomials, we improve this result to show that every perfect number is divisible by a prime exceeding 10 8 .

We examine the problem of factoring the rth cyclotomic polynomial, Φ r (x), over Fp, r and p distinct primes. Given the traces of the roots of Φ r (x) we construct the coefficients of Φ r (x) in time O(r 4 ). We demonstrate a deterministic algorithm for factoring Φ r (x) in time O((r 1/2+ ∈log p) 9 ) when Φ r (x) has precisely two irreducible factors. Finally, we present a deterministic algorithm for computing the sum of the irreducible factors of Φ r (x) in time O(r 6 ).

Let q be a prime > 150 > 150 and F n {F_n} be the cyclotomic polynomial of order n. All triples (p, n, q) with p an odd prime > 10 6 > {10^6} when q > 100 q > 100 and p > 10 4 p > {10^4} when 100 > q > 150 100 > q > 150 are given for which F n ( q ) {F_n}(q) is divisible by p t ( t > 1 ) {p^t}(t > 1) .

The resultant ρ ( F m ( a x ) , F n ( b x ) ) \rho ({F_m}(ax),{F_n}(bx)) is calculated for arbitrary positive integers m and n, and arbitrary nonzero complex numbers a and b. An addendum gives an extended bibliography of work on cyclotomic polynomials published since 1919.

Some new results for finding all convenient moduli m for a complex number-theoretic transform with given transform length n and given primitive nth root of unity modulo m are presented. The main result is based on the prime factorization for values of cyclotomic polynomials in the ring of Gaussian integers.

If f ( x ) f(x) is a polynomial over G F ( q ) GF(q) , we observe (as has Berlekamp) that if h ( x ) q ≡ h ( x ) ( mod f ( x ) ) h{(x)^q} \equiv h(x)(\bmod f(x)) , then f ( x ) = ∏ a ∈ G F ( q ) gcd ( f ( x ) , h ( x ) − a ) f(x) = \prod {{{_a}_{ \in GF(q)}}\gcd (f(x),h(x) - a)} . The object of this paper is to give an explicit construction of enough such h h ’s so that the repeated application of this result will succeed in separating all irreducible factors of f f . The h h ’s chosen are loosely defined by h i ( x ) ≡ x i + x i q + x i q 2 + ⋯ ( mod f ( x ) ) {h_i}(x) \equiv {x^i} + {x^{iq}} + {x^{i{q^2}}} + \cdots (\bmod f(x)) . A detailed example over G F ( 2 ) GF(2) is given, and a table of the factors of the cyclotomic polynomials Φ n ( x ) ( mod p ) for p = 2 , n ≦ 250 ; p = 3 , n ≦ 100 ; p = 5 , 7 , n ≦ 50 {\Phi _n}(x)(\bmod p){\text { for }}p = 2,n \leqq 250;p = 3,n \leqq 100;p = 5,7,n \leqq 50 , is included.

It is shown here that if n is odd and perfect, then n has a prime divisor which exceeds 11200. 0. In 1944 Kanold (2) showed that at least one of the /?, is greater than or equal to 61. Our purpose here is to show that Kanold's result can be significantly improved. Thus, we shall prove the following result. Theorem. Ifn is an odd perfect number, then n is divisible by aprime which exceeds 11200. Our proof is computational in nature in as much as it is based on a search for the prime factors less than 11200 of

The following list contains one example of a primitive polynomial (mod 2) for each degree », 1 ^ n ^ 100. It was compiled with the aid of the Mercury computer at Manchester University by the following method. The polynomials P„(x) (mod 2) of degree n were tested in their natural order until a primitive polynomial was found. The test comprised three stages. In the first stage the small primes, of degree up to 9, were tried as possible factors (mod 2) of Pn . If no factor was found P„ went forward to the second stage, which tested whether Pn divides x" — 1, where N = 2" — 1. If it does, and N is prime (a Mersenne prime), this suffices to prove that P„ is primitive. If N is composite, however, Pn might divide xM — 1, where M is a factor of N, and then Pn would not be primitive. The third stage was, therefore, a trial of this possibility, in which M took the values N/p, where p runs through the prime factors of N. The two latter stages were carried out by a process in which the computer repeated the operations of squaring, possibly multiplying by x (depending on the binary representation of M), then dividing by Pn . The prime factors of N were taken from the tables of Kraitchik [1], supplemented by Robinson's [2] further decomposition of 296 — 1. If any more of these 'prime' factors should turn out to be composite, doubt would be cast on the corresponding Pn . Mersenne polynomials for n = 107 and 127 are also given. The prime x127 + x + 1 was found by Zier 1er [3]. Its nature follows from the general result that if ?,anxn divides 2c„x" (mod p), then