Number of irreducible polynomials with some coefficients fixed over a finite field - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T01:21:19Z http://mathoverflow.net/feeds/question/39100 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/39100/number-of-irreducible-polynomials-with-some-coefficients-fixed-over-a-finite-fiel Number of irreducible polynomials with some coefficients fixed over a finite field Alex 2010-09-17T13:43:26Z 2010-09-17T14:40:47Z <p>I am interested in the following problem: I have a finite field $F_q$, two positive integers $n>m$ and elements $a_1,...,a_m\in F_q$. How many of the polynomials $x^n+a_1x^{n-1}+...+a_mx^{n-m}+c_{m+1}x^{n-m-1}+...+c_n,c_i\in F_q$ are irreducible? What are the best known estimates, esp. for $q$ fixed and $m,n\to\infty$?</p> http://mathoverflow.net/questions/39100/number-of-irreducible-polynomials-with-some-coefficients-fixed-over-a-finite-fiel/39108#39108 Answer by Felipe Voloch for Number of irreducible polynomials with some coefficients fixed over a finite field Felipe Voloch 2010-09-17T14:40:47Z 2010-09-17T14:40:47Z <p>This is similar to counting irreducibles in arithmetic progressions modulo $x^m$ (once you replace $x$ by $1/x$). You can turn the problem into counting rational points on a curve (coming from a "cyclotomic function field" in the sense of Carlitz) over $F_{q^n}$ and get an estimate $q^n/n + O(gq^{n/2})$, where $g$ is the genus of the curve. Unfortunately $g$ grows like $mq^m$ so you only get good estimates for $m$ small and nothing when $m$ gets close to $n/2$. There are plenty of papers on this (e.g. by S. Cohen). There is also some experimental work by Panario et al.. Mathscinet should help you locate these.</p>