Uniform estimates for almost primes over finite fields

Abstract:

We establish a new asymptotic formula for the number of polynomials of degree $n$ with $k$ prime factors over a finite field $\mathbb {F}_q$. The error term tends to $0$ uniformly in $n$ and in $q$. Previously, asymptotic formulas were known either for fixed $q$, through the works of Warlimont [Arch. Math. (Basel) 60 (1993), pp. 58–72] and Hwang [Random Structures Algorithms 13 (1998), pp. 17–47], or for small $k$, through the work of Arratia, Barbour and Tavaré [Math. Proc. Cambridge Philos. Soc. 114 (1993), pp. 347–368].

As an application, we estimate the total variation distance between the number of cycles in a random permutation on $n$ elements and the number of prime factors of a random polynomial of degree $n$ over $\mathbb {F}_q$. The distance tends to $0$ at rate $1/(q\sqrt {\log n})$. Previously this was only understood when either $q$ is fixed and $n$ tends to $\infty$, or $n$ is fixed and $q$ tends to $\infty$, by results of Arratia, Barbour and Tavaré.