On the Enumeration of Irreducible Polynomials over $\text{GF}(q)$ with Prescribed Coefficients

We present an efficient deterministic algorithm which outputs exact expressions in terms of $n$ for the number of monic degree $n$ irreducible polynomials over ${\mathbb{F}}_q$ of characteristic $p$ for which the first $l < p$coefficientsareprescribed,providedthat$n$iscoprimeto$p$. Each of these counts is $\frac{1}{n}(q^{n-l}+\mathcal{O}(q^{n\mathrm{/}2}))$. The main idea behind the algorithm is to associate to an equivalent problem a set of Artin-Schreier curves defined over ${\mathbb{F}}_q$ whose number of ${\mathbb{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\ge p$ cases are seemingly harder. Nevertheless, we use an analogous algorithm to compute example curves for $q=2$ and $l\le 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.