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$, and $k$ can grow beyond $\log n$. Previously, asymptotic formulas were known either for fixed $q$, through the works of Warlimont and Hwang, or for small $k$, through the work of Arratia, Barbour and Tavaré. 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é.

13 pages, 1 figure. Typos fixed and some notation changed. Accepted version

Cited by in corpus (1)

• Universality for low degree factors of random polynomials over finite fields