On the degrees of polynomial divisors over finite fields

Abstract

We show that the proportion of polynomials of degree $n$ over the finite field with $q$ elements, which have a divisor of every degree below $n$, is given by $c_q{n}^{-1}+O(n^{-2})$. More generally, we give an asymptotic formula for the proportion of polynomials, whose set of degrees of divisors has no gaps of size greater than $m$. To that end, we first derive an improved estimate for the proportion of polynomials of degree $n$, all of whose non-constant divisors have degree greater than $m$. In the limit as $q\to \infty$, these results coincide with corresponding estimates related to the cycle structure of permutations.

21 pages, 1 figure