On the enumeration of irreducible polynomials over GF(q) with prescribed coefficients

Abstract We present an efficient deterministic algorithm which outputs exact expressions in terms of n for the number of monic degree n irreducible polynomials over F q of characteristic p for which the first l p coefficients are prescribed, provided that n is coprime to p . Each of these counts is 1 n ( q n − l + O ( q n / 2 ) ) . The main idea behind the algorithm is to associate to an equivalent problem a set of Artin–Schreier curves defined over F q whose number of F q n -rational affine points must be combined. This is accomplished by computing their zeta functions using a p -adic algorithm due to Lauder and Wan. Using the computational algebra system Magma one can, for example, compute the zeta functions of the arising curves for q = 5 and l = 4 very efficiently, and we detail a proof-of-concept demonstration. Due to the failure of Newton's identities in positive characteristic, the l ≥ p cases are seemingly harder. Nevertheless, we use an analogous algorithm to compute example curves for q = 2 and l ≤ 7 , and for q = 3 and l = 3 . Again using Magma, for q = 2 we computed the relevant zeta functions for l = 4 and l = 5 , obtaining explicit formulae for these open problems for n odd, as well as for subsets of these problems for all n , while for q = 3 we obtained explicit formulae for l = 3 and n coprime to 3. We also discuss some of the computational challenges and theoretical questions arising from this approach in the general case and propose some natural open problems.