# ON THE DISTRIBUTION OF POLYNOMIALS HAVING A GIVEN NUMBER OF IRREDUCIBLE
FACTORS OVER FINITE FIELDS

Arghya Datta  Département de mathématiques et de statistique
Université de Montréal
CP 6192 Succ. Centre-ville, Montréal, QC H3C 3J7, Canada
<EMAIL_ADDRESS>
###### Abstract.

Let $q\geqslant 2$ be a fixed prime power. We prove an asymptotic formula for
counting the number of monic polynomials that are of degree $n$ and have
exactly $k$ irreducible factors over the finite field $\mathbb{F}_{q}$. We
also compare our results with the analogous existing ones in the integer case,
where one studies all the natural numbers up to $x$ with exactly $k$ prime
factors. In particular, we show that the number of monic polynomials grows at
a surprisingly higher rate when $k$ is a little larger than $\log n$ than what
one would speculate from looking at the integer case.

###### Key words and phrases:

polynomials over finite field, fixed number of irreducible factors, Selberg-
Delange method, multiplicative functions, saddle point approximation

###### 2020 Mathematics Subject Classification:

11T06, 11N37, 11T55, 11N56

##  1\. Introduction

How many integers are there up to $1000$ billion (or any large number) with
exactly 2022 (or any given integer) prime factors? This exciting question
fascinated mathematicians for ages. Gauss initially started the investigation
and the question was later pursued by several eminent mathematicians,
including Landau, Hardy and Ramanujan, Sathe and Selberg. Thanks to their
compound effort, we entirely understand these answers in the integer setting.
The main goal of this work is to study the analogous question for polynomials
over finite fields. We begin our discussion with a brief historical interlude
and then state our main results.
Let $m\leqslant x$ be positive integers and $\Omega(m)$ denotes the number of
prime factors counted with multiplicity that divide $m$. In 1900, Landau
[References] showed using the prime number theorem that for $k\in\mathbb{N}$
fixed we have

$\Pi(x,k)\sim\dfrac{x}{\log x}\dfrac{(\log\log x)^{k-1}}{(k-1)!},$

where

$\Pi(x,k):=\\#\bigg{\\{}m\leqslant x:\Omega(m)=k\bigg{\\}}.$

The above result was predicted by Gauss [References] long ago. However,
understanding the asymptotic behaviour of $\Pi(x,k)$ for growing $k$ uniformly
with $x$ remained an open problem for a long time.
In 1953, Sathe [References] ingeniously showed that if $\epsilon\in(0,2)$ is
given, then uniformly for $1\leqslant k\leqslant(2-\epsilon)\log\log x$ we
have

(1.1) $\Pi(x,k)\sim F\left(\dfrac{k}{\log\log x}\right)\dfrac{{(\log\log
x)}^{k-1}}{(k-1)!}\dfrac{x}{\log x},$

where

$F(z)=\dfrac{1}{\Gamma(z+1)}\displaystyle\prod\limits_{p}\left(1-\dfrac{1}{p}\right)^{z}\left(1-\dfrac{z}{p}\right)^{-1}\quad(|z|<2).$

This beautiful result was further extended by Selberg [References] when $k$ is
a little larger and varies uniformly in a slightly wider range
$(2+\epsilon)\log\log x\leqslant k\leqslant B^{*}\log\log x$, where $B^{*}>2$
is a real constant. In his paper Selberg only discussed the main ideas behind
the proof. He observed a significant change in the asymptotic behaviour of
$\Pi(x,k)$. He showed for this range we have

(1.2) $\Pi(x,k)\sim\dfrac{Cx\log(x/2^{k})}{2^{k}},$

where $C$ is an absolute constant. Finally Nicolas [References] settled this
question for the entire range $(2+\epsilon)\log\log x\leqslant k<\log x/\log
2$ by proving the same asymptotic result holds as (1.2) in this range. Unlike
the previous attempts his main idea behind the proof was less analytic and
more of combinatorial nature.
As mentioned earlier, we will be working in the polynomial ring
$\mathbb{F}_{q}[t]$. Henceforth $q$ is assumed to be fixed and all the implied
constants are allowed to depend on $q$. For an easy reference later on, we
employ some standard notation that will be used throughout the paper.

###  1.1. Notation

We set

$\mathcal{M}:=\bigg{\\{}\text{set of all monics in
}\mathbb{F}_{q}[t]\bigg{\\}},$ $\widetilde{\mathcal{M}}:=\bigg{\\{}\text{set
of all monics in }\mathbb{F}_{q}[t]\text{ having no root in
}\mathbb{F}_{q}\bigg{\\}},$ $\mathcal{P}:=\bigg{\\{}\text{set of all monic
irreducibles in }\mathbb{F}_{q}[t]\bigg{\\}}.$

$\mathcal{M}_{n}$ consists of only those monics that have degree $n$ and
similarly we define $\widetilde{\mathcal{M}}_{n}$, $\mathcal{P}_{n}$. Let
$\mathcal{P}_{\geqslant j}$ denotes the set of all monic irreducibles whose
degree is at least $j.$
Given $f\in\mathbb{F}_{q}[t]$, let $\Omega(f)$ denotes the number of
irreducible polynomials counted with multiplicity that divide $f$. We also set

$N(n,k):=\\#\bigg{\\{}f\in\mathcal{M}_{n}:\Omega(f)=k\bigg{\\}},$
$N^{\prime}(n,k):=\\#\bigg{\\{}f\in\widetilde{\mathcal{M}_{n}}:\Omega(f)=k\bigg{\\}}.$

As discussed initially, we are interested in understanding the object $N(n,k)$
for different ranges of $k$. Surprisingly one of our main results reveals that
the situation in $\mathbb{F}_{q}[t]$ is quite different than what one could
naively guess from the knowledge in the integer case. This is remarkable since
these two worlds are significantly different in only a few instances.
We first give a proof of (1.1) in the context of polynomials. The result was
first proved in Warlimont [References] and Car [References]. The following
result has been generalized in a recent work [References], which is uniform in
both parameters $n$ and $q$. However, $q$ remains fixed for our purposes and
we sketch a proof of Warlimont’s result for completeness and the techniques we
discuss are tailored in a way that will naturally extend to our main result
which is Theorem 1.2.

######  Theorem 1.1.

Given $\epsilon\in(0,q)$, then uniformly for $1\leqslant
k\leqslant(q-\epsilon)\log n$ we have

$N(n,k)\sim\dfrac{q^{n}}{n}H\left(\dfrac{k}{\log n}\right)\dfrac{{(\log
n)}^{k-1}}{(k-1)!},$

where

$H(z)=\dfrac{1}{\Gamma(z+1)}\displaystyle\prod\limits_{p\in\mathcal{P}}\left(1-\dfrac{1}{q^{deg(p)}}\right)^{z}\left(1-\dfrac{z}{{q^{deg(p)}}}\right)^{-1}$

for $|z|<q.$

We may notice that the expression for the function $H$ is quite similar to $F$
in the integer case. The appearance of $q^{n}/n$ is also no surprise as
letting $q^{n}\approx x$ yields $q^{n}/n\approx x/\log x$ up to constant
factors. While the above result is more or less an application of the Selberg-
Delange method developed in [References], the following surprising outcome of
our work is where a substantial amount of new techniques goes in.
We would like to mention that Hwang [References] considered the object
$N(n,k)$ for the entire range $1\leqslant k\leqslant n$. We reproduce similar
results but using a completely different approach. We consider a mild
restriction on the range of uniformity of $k$ but this assumption allows us to
obtain a result that has a considerably simpler shape (only in terms of
elementary functions) compared to Hwang. Hwang considered the following
decomposition $\Omega(f)=\Omega^{(1)}(f)+\Omega^{(2)}(f)$, where
$\Omega^{(1)}(f)$ and $\Omega^{(2)}(f)$ denote the number of monic irreducible
factors of $f$ of degree $\geqslant 2$ and $=1$. Roughly speaking, Hwang
showed that if $f\in\mathcal{M}_{n}$ is chosen uniformly at random then the
object $\Omega^{(1)}$ is roughly Poisson distributed while $\Omega^{(2)}$
follows a negative binomial distribution. Hwang then looks at the sum of these
two random objects and studies their convolution law for different ranges of
$k$. He showed that if $k$ is small, i.e. $1\leqslant
k\leqslant(q-\epsilon)\log n$, then the behaviour of
$\Omega_{q}=\Omega_{q}^{(1)}+\Omega_{q}^{(2)}$ is dominated by the
$\Omega_{q}^{(1)}$ component and thus resulting an approx Poisson distribution
(as obtained by Warlimont earlier)

$\mathbb{P}(\Omega_{q}=k)\sim H\left(\dfrac{k}{\log n}\right)\dfrac{(\log
n)^{k-1}}{(k-1)!}\dfrac{1}{n}.$

On the other hand, if $k$ is “largish” and in particular $k/\log n\to\infty$,
then the sum $\Omega_{q}$ is considerably inflated by the component
$\Omega_{q}^{(2)}$ resulting a significant change in the final asymptotic.
Contrary to Hwang’s probabilistic approach, our line of attack uses a crucial
combinatorial decomposition identity from [References] in the context of
polynomials.
It is worthwhile to mention that similar studies concerning the function
$\omega(f)$ instead of $\Omega(f)$ can be found in [References].

######  Theorem 1.2.

Let $B\geqslant 2$ be a real constant and $q>2$ be a prime power. Let
$\xi:\mathbb{N}\to\mathbb{R}$ be a function such that $\xi(n)\to\infty$
however slowly as $n\to\infty$. Then uniformly for $\xi(n)\log n\leqslant
k\leqslant{n}/{B}$ we have

$N(n,k)\thicksim C(q)\dfrac{q^{n}k^{q-1}(n-k)^{q-1}}{q^{k}},$

where

$C(q)=\dfrac{1}{\left((q-1)!\right)^{2}}\left(1-\dfrac{1}{q}\right)^{q^{2}}\displaystyle\prod\limits_{p\in\mathcal{P}_{\geqslant
2}}\left(1-\frac{1}{q^{deg(p)-1}}\right)^{-1}\left(1-\frac{1}{q^{deg(p)}}\right)^{q},$

a constant that depends only on $q$.

Here “however slowly” means that $\xi(n)$ could be any function that grows to
infinity with an additional constraint that $\xi$ is sufficiently small so
that the interval $[\xi(n)\log n,n/B]$ contains at least one integer for $n$
large enough. We remind the reader that $x/2^{k}$ is replaced by $q^{n}/q^{k}$
as was expected. The appearance of $(n-k)$ is not also surprising in light of
the main theorem proved in [References] and (1.2) where a factor of
$\log\left(x/2^{k}\right)$ is present in the statement. However, the extra
factor $k^{q-1}$ and also the presence of higher powers of $(n-k)$ are what
seem surprising at the moment, which shows $N(n,k)$ grows at a much larger
rate than what we would predict from (1.2).
We note Theorem 1.2 is valid for $q\neq 2$. Our methods do not cover the case
$q=2$ for technical reasons. We will discuss this technical restriction in the
proof of Proposition 4.7. (see Remark 4.8) Also, there is a slight gap between
the upper bound of $k$ in Theorem 1.1 and the lower bound of $k$ in Theorem
1.2. While it is fairly easy to prove an upper bound of the shape $N(n,k)\ll
q^{n-k}k^{q-1}(n-k)^{q-1}$ in the intermediate range $q\log n\leqslant
k\ll\log n$ using the ideas in Proposition 4.7, it seems difficult to obtain
any meaningful and “simple to state” lower bound for that range. The proofs of
the above theorems are discussed in detail in the following sections. The main
ingredients are the following two key propositions.

######  Proposition 1.3.

For all $\epsilon\in(0,q)$ and uniformly for $|z|\leqslant q-\epsilon$ we have

${M_{z}}(n):=\displaystyle\sum\limits_{f\in{\mathcal{M}_{n}}}z^{\Omega(f)}=q^{n}n^{z-1}\Bigg{\\{}zH(z)+O_{\epsilon}\left(\dfrac{1}{n}\right)\Bigg{\\}},$

with $H(z)$ as described in Theorem 1.1.

######  Proposition 1.4.

For all $\delta\in(0,1)$ and uniformly for $|z|\leqslant q^{2}-\delta$ we have

$\widetilde{M_{z}}(n):=\displaystyle\sum\limits_{f\in\widetilde{\mathcal{M}_{n}}}z^{\Omega(f)}=q^{n}n^{z-1}\Bigg{\\{}zh(z)+O_{\delta}\left(\dfrac{1}{n}\right)\Bigg{\\}},$

where
$h(z)=\dfrac{1}{\Gamma(z+1)}\left(1-\dfrac{1}{q}\right)^{qz}\displaystyle\prod\limits_{p\in\mathcal{P}_{\geqslant
2}}\left(1-\frac{z}{q^{deg(p)}}\right)^{-1}\left(1-\frac{1}{q^{deg(p)}}\right)^{z}$,
an analytic function for $|z|<q^{2}$.

The connection between Theorem 1.1 and Proposition 1.3 becomes clear once we
notice $N(n,k)$ is precisely given by the coefficient of $z^{k}$ in
$M_{z}(n)$. In other words, if we could extract the information about $N(n,k)$
from $M_{z}(n)$, we would have our result. Furthermore, we note that
$M_{z}(n)$ is polynomial in $z$ of degree at most $n$ and therefore, we could
hope to study the coefficients using Cauchy’s integral formula. This is going
to be our main strategy to attack Theorem 1.1. The connection between
$\widetilde{M_{z}}(n)$ and Theorem 1.2 is not as immediate as the previous
case since the coefficient of $z^{k}$ in $\widetilde{M_{z}}(n)$ is
$N^{\prime}(n,k)$ and not $N(n,k)$. As we shall see, in section 4 the two
objects $N(n,k)$ and $N^{\prime}(n,k)$ are intimately entangled, and
information about one could be transferred into another. Also, one can check
the relation $C(q)=qh(q)/(q-1)!$ holds.

Acknowledgements. The author would like to thank his supervisor, Prof. Andrew
Granville, for suggesting that he work on this problem and also his co-
supervisor, Prof. Dimitris Koukoulopoulos, for many helpful conversations and
continuous support during this project and for their valuable suggestions and
comments on the previous versions of this manuscript. The author would also
like to thank the anonymous referee for many useful comments and Ofir
Gorodetsky for informing him about the previous works on the same problem,
which the author was initially unaware of. The author was financially
supported by his supervisors and the fellowships provided by Faculté des
études supérieures et postdoctorales (FESP), Bourse d’exemption of Université
de Montréal, Centre interuniversitaire en calcul mathématique algébrique
(CICMA) while carrying out this work.

##  2\. Set-up and the proof of Proposition 1.3

###  2.1. Preparatory results for Proposition 1.3

In this subsection we aim to develop the framework for a Selberg-Delange type
argument that will be used to establish Proposition 1.3. As already discussed
we are interested in the quantity

$M_{z}(n):=\displaystyle\sum\limits_{f\in\mathcal{M}_{n}}z^{\Omega(f)}=\displaystyle\sum\limits_{k\geqslant
0}z^{k}N(n,k).$

We also want to introduce an auxiliary quantity

(2.1)
$G_{z}(u)=\displaystyle\sum\limits_{f\in\mathcal{M}}z^{\Omega(f)}u^{deg(f)}=\displaystyle\prod_{p\in\mathcal{P}}\left(1-zu^{deg(p)}\right)^{-1}.$

The function $G_{z}(u)$ defines an analytic function since the Euler product
converges uniformly on the compacts subsets of the region defined by
$|u|<\min\big{\\{}|z|^{-1},q^{-1}\big{\\}}$ which we argue now.
We recall a well known result from complex analysis that says for a sequence
of complex numbers $\\{a_{n}\\}\subset\mathbb{C}$ with $a_{n}\neq-1$ if
$\sum\limits_{n=1}^{\infty}|a_{n}|<\infty$, then

$\prod\limits_{n=1}^{\infty}(1+a_{n})\text{ converges. }$

Using this result we see the product in (2.1) converges uniformly on the
compact subsets of the region $0<|u|<q^{-1}.$ Indeed we have

$\displaystyle\displaystyle\sum\limits_{p\in\mathcal{P}}\left|zu^{deg(p)}\right|$
$\displaystyle\leqslant\displaystyle\sum\limits_{p\in\mathcal{P}}|u|^{deg(p)-1}\qquad(|uz|<1)$
$\displaystyle\leqslant q+\displaystyle\sum\limits_{p\in\mathcal{P}_{\geqslant
2}}|u|^{deg(p)-1}$ $\displaystyle\leqslant
q+\displaystyle\sum\limits_{n=2}^{\infty}q^{n}|u|^{n-1}\qquad\left(\text{
since }\\#\mathcal{P}_{n}\leqslant q^{n}\right)$ $\displaystyle\leqslant
q+\dfrac{1}{|u|}\displaystyle\sum\limits_{n=2}^{\infty}|qu|^{n}<\infty,\qquad(|qu|<1)$

where the finite quantity $\sum\limits_{n=2}^{\infty}q^{n}|u|^{n-1}$ depends
only on the chosen compact subset of the region $0<|u|<q^{-1}$, but not on the
point $(u,z)$. Finally we check that

$|1-zu^{deg(p)}|\geqslant 1-|zu^{deg(p)}|\geqslant 1-|zu|>0,$

showing there is no pole in the concerned region.
Our job is to understand $M_{z}(n)$, which is precisely given by the
coefficient of $u^{n}$ in the power series of $G_{z}(u)$. Hence information
about $M_{z}(n)$ can be obtained from $G_{z}(u)$ by applying Cauchy’s integral
formula. We took this leap from $M_{z}(n)$ to $G_{z}$ because it seems to have
a nicer arithmetic structure (i.e. an Euler product expansion), making it more
amenable from the analytic point of view. Therefore it is natural to seek to
meromorphically extend $G_{z}(u)$ beyond the region of absolute convergence
discussed above to collect the contribution coming from the singularity of
$G_{z}$ in the extended domain. We do this job by introducing another function
$F_{z}(u)$ via the Euler product

(2.2)
$F_{z}(u)=\displaystyle\prod\limits_{p\in\mathcal{P}}\left(1-zu^{deg(p)}\right)^{-1}\left(1-u^{deg(p)}\right)^{z}.$

We intend to analyze the above Euler product in the following open region and
show it is holomorphic.

$\mathcal{R}:=\Big{\\{}(u,z)\in\mathbb{C}^{2}:|z|<q,|u|<|z|^{-1},|u|<q^{-1/2}\Big{\\}}\subset\mathbb{C}^{2}.$

The following lemma shows $F_{z}(u)$ does converge uniformly on the compact
subsets of $\mathcal{R}$ which is what we wanted to establish.

######  Lemma 2.1.

We have that $F_{z}(u)$ defined in (2.2) converges uniformly on the compact
subsets of $\mathcal{R}$ and hence defines a holmorphic function in the sense
two complex variables.

###### Proof.

We take the standard branch of complex logarithm defined over
$\mathbb{C}\setminus(-\infty,0]$. Since $|u|^{n},|zu^{n}|<1$ we could make use
of their Taylor series and write

$\displaystyle z\log(1-u^{n})-\log(1-zu^{n})$
$\displaystyle=-zu^{n}+O\left(\left|zu^{2n}\right|\right)+zu^{n}+O\left(\left|z^{2}u^{2n}\right|\right)$
$\displaystyle=O\left(\left|q^{2}u^{2n}\right|\right)\qquad\left(|z|<q\right)$

and hence using $\exp(O(x))=1+O(x)$ for $x=O(1)$ we get

$(1-u^{n})^{z}(1-zu^{n})^{-1}=1+O\left(\left|q^{2}u^{2n}\right|\right).$

We now observe the product in (2.2) converges uniformly in the compact subsets
of $\mathcal{R}$. Since $\\#\mathcal{P}_{n}\leqslant q^{n}$, we have that

$\displaystyle\sum\limits_{p\in\mathcal{P}}|u|^{2n}\leqslant\displaystyle\sum\limits_{n\geqslant
1}|qu^{2}|^{n}<\infty,$

where the finite quantity $\sum\limits_{n\geqslant 1}|qu^{2}|^{n}$ depends on
the chosen compact subset of $\mathcal{R}$, but is independent of the point
$(u,z)$. ∎

We recall the Riemann zeta function in the context of polynomials over finite
field, defined for $|u|<q^{-1}$

$\zeta(u)=\dfrac{1}{1-qu}=\displaystyle\prod_{p\in\mathcal{P}}\left(1-u^{deg(p)}\right)^{-1}.$

As we can see $\zeta(u)$ can be continued mermorphically on $\mathbb{C}$ with
a simple pole at $u=1/q$. Furthermore considering the Euler products in (2.1)
and $(\ref{l55})$ we can connect $G_{z}(u)$ and $F_{z}(u)$ in the following
way whenever $|u|<\min\big{\\{}|z|^{-1},q^{-\frac{1}{2}}\big{\\}}$

(2.4) $G_{z}(u)=\zeta(u)^{z}F_{z}(u).$

We are now in a position to prove our first Proposition. However, first, we
want to record the following estimate [References, Lemma 1], which is going to
be helpful in the further calculation of the contribution that comes from the
singularity of $G_{z}(u)$ at $u=1/q$.

Figure 1. The contour $\mathcal{H}$ appearing in Lemma
2.2$O$$x$$y$$\begin{array}[]{l}-n\delta\\\ \end{array}$

######  Lemma 2.2.

Let $A,\delta>0$. Let $\mathcal{H}$ be the Hankel contour of radius $1$ around
$0$ going in clockwise direction along the negative real axis to $-n\delta$.
Then uniformly for $|z|\leqslant A$ we have that

$\dfrac{1}{2\pi
i}\displaystyle\int_{\mathcal{H}}w^{z}\dfrac{dw}{\left(1-\dfrac{w}{n}\right)^{n+1}}=-\dfrac{1}{\Gamma(-z)}+O_{\delta,A}\left(\dfrac{1}{n}\right).$

Figure 2. The contour appearing in the proof of Proposition
1.3${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathcal{H}^{\prime}}$${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}|u|=1/q+\eta}$${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}|u|=1/q}$${\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}|u|=r}$

###  2.2. Deduction of Proposition 1.3

###### Proof of Proposition 1.3.

Let $|u|=r<q^{-1}$ (small green circle in Fig-2 above). Using Cauchy’s
integral formula on (2.1) we get for each fixed $z$ satisfying the hypothesis
$|z|\leqslant q-\epsilon$,

(2.5) $M_{z}(n)=\dfrac{1}{2\pi
i}\displaystyle\int\limits_{|u|=r}G_{z}(u)\dfrac{du}{u^{n+1}}=\dfrac{1}{2\pi
i}\displaystyle\int\limits_{|u|=r}\zeta(u)^{z}F_{z}(u)\dfrac{du}{u^{n+1}}.$

We wish to get past the point $u=1/q$ so that we could collect the
contribution coming from the singularity of $\zeta(u)$ there. We shift the
smaller (green) circle $|u|=r$ to a bigger circle (black) $|u|=q^{-1}+\eta$
and a portion of Hankel contour (red) around the point $q^{-1}$ (Fig-2). (to
be specified shortly) Let $\mathcal{H}^{\prime}$ be the contour that consists
of a circle of radius $(qn)^{-1}$ traversed clockwise around $q^{-1}$ and the
two line segments on the ray $0$ to $q^{-1}$ joining this small circle to the
bigger circle $|u|=q^{-1}+\eta$ where $\eta>0$ is a fixed number. However we
must have $q^{-1}+\eta<q^{-\frac{1}{2}}$ as we cannot go beyond the region
$\mathcal{R}$ in (2.4) where $G_{z}(u)$ makes sense. We recall that
$|z|\leqslant(q-\epsilon)$ inside $\mathcal{R}$ while performing the above
integral. Keeping this in mind we get another constraint on $\eta$,
$|uz|\leqslant(q^{-1}+\eta)(q-\epsilon)\leqslant 1$. This shows taking any
$0<\eta<\min\\{1/(q-\epsilon)-1/q,1/\sqrt{q}-1/q\\}$ suffices. We then plan to
use Lemma 2.2 to evaluate the integral in (2.5) with
$\eta=\min\\{1/(q-\epsilon)-1/q,1/\sqrt{q}-1/q\\}/2$ for $|z|\leqslant
q-\epsilon.$ We observe that for $z$ fixed, $F_{z}(u)$ and $\zeta(u)$ are both
analytic in an open neighbourhood containing the circle $|u|=q^{-1}+\eta$
which is compact. This implies $F_{z}(u),\zeta(u)$ and hence $G_{z}(u)$ are
uniformly bounded (bound depends on $q,\eta$) on this circle. Thus we obtain

$M_{z}(n)=\dfrac{1}{2\pi
i}\displaystyle\int\limits_{\mathcal{H}^{\prime}}G_{z}(u)\dfrac{du}{u^{n+1}}+O\left(\displaystyle\int\limits_{|u|=\frac{1}{q}+\eta}\left|G_{z}(u)\dfrac{du}{u^{n+1}}\right|\right):=I+O_{q,\epsilon}\left(\dfrac{q^{n}}{(1+q\eta)^{n}}\right),$

where at the last step we used the fact that,
$\int_{|u|=R}|du/u^{n+1}|=\frac{1}{R^{n+1}}\int_{|u|=R}|du|=2\pi/R^{n}$ and
the big-O-uniform bound here depends only on $q$ and $\eta$ while $\eta$
according our choice depends only on $q$ and $\epsilon$. Now we focus on the
integral $I$.
Analyticity of $F_{z}$ near $q^{-1}$ allows us to consider the Taylor series
around $q^{-1}$ and write

$F_{z}(u)=F_{z}\left(1/q\right)+a_{1}\left(u-1/q\right)+a_{2}\left(u-1/q\right)^{2}+\ldots$

Hence we have that

$I=F_{z}\left(\dfrac{1}{q}\right)\dfrac{1}{2\pi
i}\displaystyle\int_{\mathcal{H}^{\prime}}\zeta(u)^{z}\dfrac{du}{u^{n+1}}+O\left(\displaystyle\int_{\mathcal{H}^{\prime}}\left|\left(u-\dfrac{1}{q}\right)\zeta(u)^{z}\dfrac{du}{u^{n+1}}\right|\right).$

We use a change of variable so that our contour $\mathcal{H}^{\prime}$
transforms to $\mathcal{H}$ and we could then use our Lemma 2.2. The change of
variable is given by, $w=n(1-uq)\implies u=1/q\left(1-w/n\right).$ We can
quickly check the transformation is indeed a valid one. If $u$ is
parameterized by
$u=1/q+(1/qn)e^{-it},t\in[\epsilon^{\prime},2\pi-\epsilon^{\prime}]$ for some
small enough $\epsilon^{\prime}>0$ near the tiny circle around $1/q$ then
$w=-e^{-it}$ is a circle revolving around $0$ of radius $1$ in the clockwise
direction and similarly the horizontal ray part also gets reflected and
$\mathcal{H}^{\prime}$ indeed transforms into $\mathcal{H}$ and as $|u|$ goes
up to $1/q+\eta$, we have $w$ goes up to $-n\delta$ with $\delta=\eta q$. We
note for this change of variable $du=-dw/nq$. First we show the alleged error
term is small. The $O$-term is

$\displaystyle\ll_{q}\displaystyle\int_{\mathcal{H}^{\prime}}\left|\dfrac{(1-qu)du}{u^{n+1}(1-qu)^{z}}\right|$
$\displaystyle=\displaystyle\int_{\mathcal{H}}\left|\dfrac{1}{\left(\dfrac{w}{n}\right)^{z-1}}\dfrac{\dfrac{-dw}{nq}}{\dfrac{1}{q^{n+1}}\left(1-\dfrac{w}{n}\right)^{n+1}}\right|$
$\displaystyle=\dfrac{q^{n}}{n}\displaystyle\int_{\mathcal{H}}\left|\dfrac{1}{\left(\dfrac{w}{n}\right)^{z-1}}\dfrac{dw}{\left(1-\dfrac{w}{n}\right)^{n+1}}\right|\qquad(\text{
using Lemma }\ref{l3})$ $\displaystyle\ll q^{n}n^{\Re(z)-2}.$

Now, we evaluate the main term using Lemma 2.2

$\displaystyle F_{z}\left(\dfrac{1}{q}\right)\dfrac{1}{2\pi
i}\displaystyle\int_{\mathcal{H}^{\prime}}\zeta(u)^{z}\dfrac{du}{u^{n+1}}$
$\displaystyle=F_{z}\left(\dfrac{1}{q}\right)\dfrac{1}{2\pi
i}\displaystyle\int_{\mathcal{H}^{\prime}}\dfrac{1}{(1-qu)^{z}}\dfrac{du}{u^{n+1}}$
$\displaystyle=F_{z}\left(\dfrac{1}{q}\right)\dfrac{q^{n}}{n}\dfrac{1}{2\pi
i}\displaystyle\int_{\mathcal{H}}\dfrac{1}{\left(\dfrac{w}{n}\right)^{z}}\dfrac{-dw}{\left(1-\dfrac{w}{n}\right)^{n+1}}$
$\displaystyle=F_{z}\left(\dfrac{1}{q}\right)q^{n}n^{z-1}\left(\dfrac{1}{\Gamma(z)}+O_{\epsilon}\left(\dfrac{1}{n}\right)\right).$

Hence we have that

(2.6)
$M_{z}(n)=F_{z}\left(\dfrac{1}{q}\right)\dfrac{q^{n}n^{z-1}}{\Gamma(z)}+O\left(q^{n}n^{\Re(z)-2}\right)=q^{n}n^{z-1}\Bigg{\\{}zH(z)+O_{\epsilon}\left(\dfrac{1}{n}\right)\Bigg{\\}},$

where $H(z)=\frac{1}{\Gamma(z+1)}F_{z}\left(\frac{1}{q}\right)$ is an analytic
function for $|z|<q.$ ∎

##  3\. Deduction of Theorem 1.1

With Proposition 1.3 at our disposal, we are now ready to prove Theorem 1.1.
We also note three other straightforward results which will help us do so. We
will verify the following claims in the appendix A.

######  Lemma 3.1.

For $t\in[-\pi,\pi]$ we have $\cos t-1\leqslant-\dfrac{t^{2}}{5}$ and
$\left|1-e^{it}\right|^{2}\leqslant t^{2}.$

######  Lemma 3.2.

We have the following upper bound

$\displaystyle\int_{|z|=r}\left|n^{z-r}\right||dz|\ll\dfrac{r}{\sqrt{j}},$

where $j=r\log n.$

######  Lemma 3.3.

We have the following estimate

$\displaystyle\int\limits_{-\infty}^{\infty}\theta^{2}\exp\left(-\dfrac{k\theta^{2}}{5}\right)d\theta\ll
k^{-\frac{3}{2}}.$

###### Deduction of Theorem 1.1.

We plan to recover $N(n,k)$ with another application of Cauchy’s integral
formula,

(3.1) $N(n,k)=\dfrac{1}{2\pi i}\displaystyle\int\limits_{|z|=\frac{k}{\log
n}}M_{z}(n)\dfrac{dz}{z^{k+1}}.$

Given $\epsilon\in(0,q)$ by the hypothesis of Theorem 1.1, from (2.6) we see
the main term of $M_{z}(n)$ which is
$F_{z}\left(\frac{1}{q}\right)\frac{q^{n}n^{z-1}}{\Gamma(z)}$ is analytic in
the disk $|z|=r={k}/{\log n}\leqslant(q-\epsilon)$ since
$F_{z}\left(\frac{1}{q}\right)$ is analytic for $|z|<q$ and $n^{z},1/\Gamma$
are entire functions. Now writing
$M_{z}(n)/q^{n}=n^{z-1}\left(f(z)+O\left(1/n\right)\right)$ where
$f(z)=zH(z)=F_{z}\left(1/q\right)\frac{1}{\Gamma(z)}$ and considering the
Taylor expansion of $f(z)$ near $z=r$,
$f(z)=f(r)+f^{\prime}(r)(z-r)+O(|z-r|^{2})$ we get

(3.2) $\dfrac{1}{q^{n}}N(n,k)=\dfrac{1}{2\pi
i}\displaystyle\int_{|z|=r}n^{z-1}f(z)\dfrac{dz}{z^{k+1}}+O(E),$

where $E$ is given by
$\dfrac{1}{n}\displaystyle\int_{|z|=r}\left|\dfrac{n^{z-1}}{z^{k+1}}\right||dz|$.
We see that

$\dfrac{1}{2\pi
i}\displaystyle\int_{|z|=r}(z-r)n^{z-1}\dfrac{dz}{z^{k+1}}=\dfrac{1}{n}\Bigg{\\{}\dfrac{(\log
n)^{k-1}}{(k-1)!}-r\dfrac{(\log n)^{k}}{k!}\Bigg{\\}}=0.$

Hence

$\displaystyle\dfrac{1}{q^{n}}N(n,k)$ $\displaystyle=f(r)\dfrac{1}{2\pi
i}\displaystyle\int_{|z|=r}n^{z-1}\dfrac{dz}{z^{k+1}}+O\left(r^{-k-1}\displaystyle\int_{|z|=r}|n^{z-1}(z-r)^{2}||dz|+E\right)$
$\displaystyle=f(r)\dfrac{(\log n)^{k}}{k!n}+\text{Error term}.$

By using Lemma 3.1 and Lemma 3.3, we see the integral in the Error term is
bounded by

$\dfrac{r^{3}}{n}\displaystyle\int_{-\pi}^{\pi}|1-e^{i\theta}|^{2}e^{k\cos\theta}d\theta\ll\dfrac{r^{3}}{n}\displaystyle\int_{-\infty}^{\infty}\theta^{2}e^{k(1-\frac{\theta^{2}}{5})}d\theta\ll\dfrac{r^{3}}{n}e^{k}k^{-\frac{3}{2}}.$

Since there is a factor of $r^{-k-1}$ outside, we have the above expression
(final step by Stirling’s formula)

$\ll\dfrac{1}{n}r^{2-k}e^{k}k^{-\frac{3}{2}}\ll(\log
n)^{k-2}\dfrac{e^{k}\sqrt{k}}{nk^{k}}\ll\dfrac{1}{n}\dfrac{(\log
n)^{k-2}}{(k-1)!}.$

Noting $e^{k}=n^{r}\iff k=r\log n$ and using Lemma 3.2, we also see the term
$E$ is bounded by

$\ll\dfrac{r^{-k-1}e^{k}}{n^{2}}\displaystyle\int_{|z|=r}|n^{z-r}||dz|\ll\dfrac{r^{-k-1}e^{k}}{n^{2}}\left(\dfrac{r}{\sqrt{k}}\right)\ll\dfrac{1}{n^{2}}\dfrac{(e\log
n)^{k}}{k^{k+\frac{1}{2}}}\ll\dfrac{1}{n^{2}}\dfrac{(\log n)^{k}}{k!},$

where in the last step we have used Stirling. Thus we finally obtain

$N(n,k)\thicksim q^{n}f(r)\dfrac{(\log
n)^{k}}{k!n}=\dfrac{q^{n}}{n}F_{r}\left(\dfrac{1}{q}\right)\dfrac{1}{\Gamma(r+1)}\dfrac{(\log
n)^{k-1}}{(k-1)!}$

and the proof follows once we recall $r={k}/{\log n}$. The derived expression
is identical to the integer case for $k\leqslant(2-\epsilon)\log\log x$ as
mentioned in [References] on the first page, a result due to Sathe(1953)
[References].
∎

We now begin to discuss the main contribution of this work. For the
convenience of the reader, we provide the following outline.

###  3.1. Organization of the following sections

The proof of Theorem 1.2 rests on a technique developed by Sathe and Selberg
along with a combination of an observation made by Nicolas [References] in his
work and an analogue of the Selberg-Delange style argument for function fields
developed in Porrit [References, section 2]. We will also use ideas from
Tenenbaum [References, Chapter II.6], where the author outlines an application
of the Selberg-Delange method to integers with a given number of prime
factors. In the earlier sections, we gave detailed proofs of Theorem 1.1 and
Proposition 1.3 as a direct application of the Selberg-Delange method
discussed in [References]. The flow of the argument and preliminary lemmas
leading to Theorem 1.2 are fairly delicate. Proof of Proposition 1.4 will be
fundamentally the same as that of Proposition 1.3 apart from some technical
modifications. We will begin section 4 by establishing Lemma 4.1, an odd-even
decomposition for polynomials. We will then discuss the role of the auxiliary
results Lemma 4.2, Lemma 4.5, Lemma 4.6, Lemma 4.4 behind the main proof of
the Theorem 1.2. Next, we establish two important results, Proposition 4.3 and
Proposition 4.7 which will finally lead us to Theorem 1.2. Detailed proofs of
the technical lemmas and Proposition 1.4 will be presented in the appendix.
The graphical dependency between the results in section 4 is described below:

Lemma 4.4 Lemma 4.6 Proposition 4.3 Proposition 4.7 Theorem 1.2 Lemma 4.2
Lemma 4.5 Proposition 1.4

##  4\. Preparatory results and an odd-even decomposition

###  4.1. An odd-even decomposition for polynomials

We begin this subsection by introducing a decomposition for $\Pi(x,k)$ into
$k$ smaller parts used by Nicolas [References] to prove $(\ref{l25})$. We
first note that any integer $n\leqslant x$ can be uniquely written as
$n=2^{j}\ell$ with $\ell$ odd. We note the following identity

(4.1) $\Pi(x,k)=\sum\limits_{0\leqslant j\leqslant
k}\Pi^{\prime}(x/2^{k-j},j),$

where

$\Pi^{\prime}(x,k):=\\#\bigg{\\{}m\leqslant x:\text{ $m$ odd and
}\Omega(m)=k\bigg{\\}}$

holds. If $2\log\log x<k<\log x/\log 2$, then the key idea proposed in
[References] says the major contribution in (4.1) comes if we restrict
$0\leqslant j\leqslant\alpha\log\log(x/2^{k})$ for some explicit constant
$\alpha>2$.
Inspired from the idea above we wish to write $f=hg$ for any
$f\in\mathcal{M}_{n}$, where the polynomials $g$ and $h$ are expected to play
the role of “odd” and “even” respectively in some appropriate sense. Let us
define the set

$\mathcal{S}(j):=\bigg{\\{}h\in\mathcal{M}_{j}:h\text{ has only degree
}1\text{ irreducible factors }\bigg{\\}}.$

Given $f\in\mathcal{M}_{n}$ with $\Omega(f)=k$, we can uniquely write $f=hg$
where $h\in\mathcal{S}(j)$ for some $0\leqslant j\leqslant k$ and $g$ has no
degree $1$ irreducible factor. Elements of the set $\mathcal{S}(j)$ mimic the
even part while the odd part is mimicked by the polynomial $g$. Using this
heuristic we could prove the following decomposition result for $N(n,k)$.

######  Lemma 4.1.

We have

$N(n,k)=\displaystyle\sum_{1\leqslant j\leqslant
k}\binom{k-j+q-1}{q-1}N^{\prime}(n+j-k,j)$

for $1\leqslant k\leqslant n/2.$

###### Proof.

We observe that for any $h\in\mathcal{S}(j)$, one can find non negative
integers $a_{1},a_{2},\ldots,a_{q}$ such that
$h(t)=(t-\alpha_{1})^{a_{1}}(t-\alpha_{2})^{a_{2}}\ldots(t-\alpha_{q})^{a_{q}}$
with $\Omega(h)=a_{1}+a_{2}+\ldots+a_{q}=j$. Here
$\\{\alpha_{i}\\}_{1\leqslant i\leqslant q}$ are the $q$-elements in
$\mathbb{F}_{q}.$ Counting the number of non negative integral solutions we
readily see that, $\\#\mathcal{S}(j)=\binom{j+q-1}{q-1}.$ If we consider the
unique decomposition $f=hg$ for some $f\in\mathcal{M}_{n}$ with $\Omega(f)=k$
then we note that $j\neq k$. For if $j=k$ then $f=hg$ will imply $f=h$ and
hence they both have the same degree, a contradiction since $k\leqslant n/2$
by the hypothesis. Therefore we obtain

$N(n,k)=\displaystyle\sum\limits_{0\leqslant j\leqslant
k-1}\displaystyle\sum\limits_{h\in\mathcal{S}(j)}N^{\prime}(n-j,k-j)=\displaystyle\sum\limits_{0\leqslant
j\leqslant k-1}\binom{j+q-1}{q-1}N^{\prime}(n-j,k-j).$

The statement of the lemma follows after we make the change of variable
$j\mapsto k-j.$ ∎

The rough sketch of our strategy to prove the Theorem 1.2 is: (a) In light of
the approach discussed in (4.1) in the integer setting, we start by splitting
the whole sum in the above decomposition up to $j\ll\log(n-k)$ and hence we
end up with two parts so that we can write, $T_{1}={\sum_{1\leqslant
j\ll\log(n-k)}\binom{k-j+q-1}{q-1}N^{\prime}(n+j-k,j)}$ and
$T_{2}={\sum_{\log(n-k)\ll j\leqslant
k}\binom{k-j+q-1}{q-1}N^{\prime}(n+j-k,j)}$.

(b) We then show the main contribution comes from $T_{1}$ and is of order
$q^{n-k}k^{q-1}(n-k)^{q-1}$ while the term $T_{2}$ is significantly smaller
and is of order $q^{n-k}(n-k)^{q-2}$. Unlike the ideas discussed in the
integer case, which is very combinatorial, our proof will be more analytical.
The central idea to use a Selberg-Delange type argument followed by an
application of Cauchy’s integral formula shall remain the same. The situation
over $\mathbb{F}_{q}[t]$ is quite different due to the presence of many degree
$1$ irreducibles which is why an extra binomial term and other technical
difficulties arise.
We begin our preparation with the easier task, a non-trivial upper bound on
$T_{2}$. To do so, we would like an upper bound on each summand of $T_{2}$.
The following result accomplishes this job.

######  Lemma 4.2.

Let $0<\delta<1,0<\eta\leqslant q^{2}-q-\delta$ be given. We have the
following upper bound

$N^{\prime}(n,j)\ll_{\delta}q^{n}n^{q+\eta-1}\left(\dfrac{1}{q+\eta}\right)^{j}.$

Throughout our discussion, the implied constants are allowed to depend on
$q,\delta$ and the value of $\delta$ is soon to be fixed in the following
result. It is possible to show the above result as a direct application
Proposition 1.4. The proof of Proposition 1.4 will roughly be in the same
spirit as that of Proposition 1.3. We will present this proof followed by an
argument leading to Lemma 4.2 in the appendix B.1, B.2. We now shift our
attention to check that the term $T_{2}$ is small as claimed.

######  Proposition 4.3.

Let $q>2$ be an integer and $Y=\log(n-k)$. We have the following upper bound

$T_{2}=\displaystyle\sum\limits_{eqY<j\leqslant
k}\binom{q-1+k-j}{q-1}N^{\prime}(n+j-k,j)\ll_{B}q^{n-k}(n-k)^{q-2}.$

###### Proof.

We plan to use
$\displaystyle\binom{\alpha}{\beta}\leqslant{\alpha^{\beta}}/{\beta!}$ for
positive integers $\alpha$ and $\beta$. We apply Lemma 4.2 with
$\eta=(e-1)q\text{ and }\delta=0.6$ so that $(q+\eta)=eq$. First we check this
choice satisfies the hypothesis of Lemma 4.2. We see that $(e-1)q<q^{2}-q-0.6$
is true whenever $q\geqslant 3$. We now have that

$\displaystyle T_{2}$
$\displaystyle\ll\displaystyle\sum\limits_{j>(q+\eta)Y}\dfrac{(q-1+k-j)^{q-1}}{(q-1)!}q^{n-k+j}(n+j-k)^{q+\eta-1}\left(\dfrac{1}{q+\eta}\right)^{j}$
$\displaystyle\ll
q^{n-k}\displaystyle\sum\limits_{j>(q+\eta)Y}(q-1+k-j)^{q-1}(n+j-k)^{q+\eta-1}\left(\dfrac{q}{q+\eta}\right)^{j}$
$\displaystyle=q^{n-k}\displaystyle\sum\limits_{j>eqY}(n-k)^{q-1}{\left(\dfrac{q-1}{n-k}+\dfrac{k-j}{n-k}\right)^{q-1}}(n-k)^{q+\eta-1}\left(1+\dfrac{j}{n-k}\right)^{q+\eta-1}e^{-j},$

where we used $q+\eta=eq$. Since $k\leqslant n/B$ we have
$\left(\frac{q-1}{n-k}+\frac{k-j}{n-k}\right)^{q-1}\leqslant\left(q-1+\frac{k}{n-k}\right)^{q-1}\leqslant\left(q-1+\frac{1}{B-1}\right)^{q-1}\ll_{B}1$
. Also $k+j\leqslant 2k\leqslant n$ gives
$\left(1+\frac{j}{n-k}\right)^{eq-1}\ll 1$. Recalling $Y=\log(n-k)$ and
continuing from the previous step we get

$T_{2}\ll_{B}q^{n-k}(n-k)^{eq+q-2}\displaystyle\sum\limits_{j>eqY}e^{-j}\ll_{B}q^{n-k}(n-k)^{eq+q-2}e^{-eqY}=q^{n-k}(n-k)^{q-2}.$

∎

We are now only left to estimate $T_{1}$ and show it dominates in the
asymptotic of $N(n,k)$. For the ease of exploration, the calculation of
$T_{1}$ is broken down into three smaller sub-parts. To have a good estimate
for $T_{1}={\sum_{1\leqslant
j\ll\log(n-k)}\binom{k-j+q-1}{q-1}N^{\prime}(n+j-k,j)}$, first it is natural
to want to understand the terms $N^{\prime}(n+j-k,j)$ when the range for $j$
is restricted to $\ll\log(n-k)$. With these observations in mind we could show
the following result.

######  Lemma 4.4.

Let $Y=\log(n-k)$. We have uniformly for $j\leqslant eqY,$

$N^{\prime}(n+j-k,j)=\dfrac{q^{n+j-k}}{n-k}\Bigg{\\{}Q_{j}(Y)+O\left(\dfrac{(\log(n-k))^{j+1}}{j!(n-k)}\right)\Bigg{\\}}$

where

$Q_{j}(X):=\displaystyle\sum\limits_{m+\ell=j-1}\dfrac{1}{m!\ell!}h^{(m)}(0)X^{\ell}.$

If we are given the above result in our toolbox, it is then evident that we
are just a few steps away from proving an estimate for $T_{1}$ once we take
care of what happens with the sum when the terms $N^{\prime}(n+j-k,j)$ are
twisted by appropriate binomial coefficients for different $j$’s. However,
before we proceed to do that, we would like to mention a few words about what
goes into the proof of Lemma 4.4. The proof of the above result rests on
another two fairly technical auxiliary lemmas, which we shall state next.
Details of these three claims are postponed till the appendix B.3, B.4, B.5
and can be skipped at the moment as they do not offer many insights into our
actual goal.

######  Lemma 4.5.

We have uniformly for $j\leqslant eq\log n,$

$N^{\prime}(n,j)=\dfrac{q^{n}}{n}\Bigg{\\{}Q_{j}(\log n)+O\left(\dfrac{(\log
n)^{j}}{j!n}\right)\Bigg{\\}}.$

######  Lemma 4.6.

Let $m\geqslant 1$ be an integer. We have the following upper bounds

$h^{(m)}(0)/m!\ll\left(\dfrac{1}{2.9q}\right)^{m},$
$Q_{j}(X)\ll\dfrac{X^{j-1}}{(j-1)!}\text{ and
}Q_{j}^{\prime}(X)\ll\dfrac{X^{j-2}}{(j-2)!},$

for $1\leqslant j\leqslant eqX$ uniformly, where $X$ is a parameter that tends
to $\infty$ with $n.$

We can now set up the stage for proving Theorem 1.2. As mentioned earlier we
need to have a precise estimate for the twisted binomial sum appearing in
$T_{1}$. Therefore the following Proposition plays a key role in establishing
Theorem 1.2.

######  Proposition 4.7.

Let $Y=\log(n-k)$. We have the following estimate

$\displaystyle\sum\limits_{j\leqslant
eqY}\displaystyle\binom{q-1+k-j}{q-1}q^{j}Q_{j}(Y)=\dfrac{k^{q-1}qe^{qY}}{(q-1)!}h(q)\Big{\\{}1+o(1)\Big{\\}}.$

###### Proof.

We start with an observation first. By the hypothesis of Theorem 1.2 we have
$k>\xi(n)\log n$ yielding $k-j\geqslant\xi(n)\log
n-eq\log(n-k)\geqslant(\xi(n)-eq)\log n\to\infty$. Therefore using the
standard fact $\binom{\alpha}{\beta}=(1+o(1))\frac{\alpha^{\beta}}{\beta!}$
where $\beta$ is assumed to be fixed and $\alpha\to\infty$ we obtain

$\displaystyle\displaystyle\sum\limits_{j\leqslant
eqY}\displaystyle\binom{q-1+k-j}{q-1}q^{j}Q_{j}(Y)$
$\displaystyle=\dfrac{1}{(q-1)!}\displaystyle\sum\limits_{j\leqslant
eqY}\Big{\\{}q^{j}(q-1+k-j)^{q-1}Q_{j}(Y)\Big{\\}}(1+o(1))$
$\displaystyle=\dfrac{k^{q-1}}{(q-1)!}\displaystyle\sum\limits_{j\leqslant
eqY}\Big{\\{}q^{j}Q_{j}(Y)\Big{\\}}(1+o(1)),$

where we used the the Taylor expansion of
$\left(k+q-j-1\right)^{q-1}=k^{q-1}(1+o(1))$ since $j=o(k).$

We now evaluate the sum

$\displaystyle\displaystyle\sum\limits_{j\leqslant eqY}q^{j}Q_{j}(Y)$
$\displaystyle=\left(\displaystyle\sum\limits_{j\geqslant
1}q^{j}\sum\limits_{\begin{subarray}{c}m+\ell=j-1\\\ m,\ell\geqslant
0\end{subarray}}\dfrac{h^{m}(0)}{m!\ell!}Y^{\ell}\right)-R$
$\displaystyle=\left(q\displaystyle\sum\limits_{\ell\geqslant
0}\dfrac{(qY)^{\ell}}{\ell!}\sum\limits_{j-m=\ell+1}\dfrac{h^{m}(0)}{m!}q^{j-\ell-1}\right)-R\qquad(\text{after
interchanging the sum})$
$\displaystyle=\left(q\displaystyle\sum\limits_{\ell\geqslant
0}\dfrac{(qY)^{\ell}}{\ell!}\sum\limits_{m\geqslant
0}\dfrac{h^{m}(0)}{m!}q^{m}\right)-R\qquad(\text{since }m=j-\ell-1\text{ and
}j\geqslant\ell+1)$ $\displaystyle=qe^{qY}h(q)-R,\qquad(\text{$h(z)$ is
analytic for $|z|<q^{2}$})$

where

$\displaystyle R$ $\displaystyle=\sum\limits_{j>\lfloor
eqY\rfloor}q^{j}Q_{j}(Y)\quad(\text{where }\lfloor x\rfloor\text{ denotes the
greatest integer }\leqslant x)$
$\displaystyle=\displaystyle\sum\limits_{j\geqslant\lfloor
eqY\rfloor+1}q^{j}\sum\limits_{\begin{subarray}{c}m+\ell=j-1\\\
m,\ell\geqslant 0\end{subarray}}\dfrac{h^{m}(0)}{m!\ell!}Y^{\ell}$
$\displaystyle=q\left(\displaystyle\sum\limits_{0\leqslant\ell\leqslant\lfloor
eqY\rfloor}\dfrac{(qY)^{\ell}}{\ell!}\sum\limits_{m\geqslant\lfloor
eqY\rfloor-\ell}\dfrac{h^{m}(0)}{m!}q^{m}\right)+q\left(\displaystyle\sum\limits_{\ell\geqslant\lfloor
eqY\rfloor+1}\dfrac{(qY)^{\ell}}{\ell!}\sum\limits_{m\geqslant
0}\dfrac{h^{m}(0)}{m!}q^{m}\right)$
$\displaystyle\ll_{q}S_{1}+S_{2}.\quad(\text{say})$

We have the following estimates,

$\displaystyle S_{1}$
$\displaystyle\leqslant\displaystyle\sum\limits_{0\leqslant\ell\leqslant\lfloor
eqY\rfloor}\dfrac{(qY)^{\ell}}{\ell!}\sum\limits_{m\geqslant\lfloor
eqY\rfloor-\ell}\left(\dfrac{1}{2}\right)^{m}\quad\left(\text{using
}h^{(m)}(0)/m!<(1/2q)^{m}\text{ from Lemma \ref{l12}}\right)$
$\displaystyle=\displaystyle\sum\limits_{0\leqslant\ell\leqslant\lfloor
eqY\rfloor}\dfrac{(qY)^{\ell}}{\ell!}\left(\dfrac{1}{2}\right)^{\lfloor
eqY\rfloor-\ell}$ $\displaystyle=\left(\dfrac{1}{2}\right)^{\lfloor
eqY\rfloor}\displaystyle\sum\limits_{0\leqslant\ell\leqslant\lfloor
eqY\rfloor}\dfrac{(2qY)^{\ell}}{\ell!}$ $\displaystyle\leqslant
e^{0.12qY}.\quad\left(\text{since }\left(\dfrac{1}{2}\right)^{\lfloor
eqY\rfloor}=e^{-1.88qY}\text{ and the rest is bounded by the complete sum
}e^{2qY}\right)$

Similarly

$\displaystyle S_{2}$
$\displaystyle=h(q)\displaystyle\sum\limits_{\ell\geqslant\lfloor
eqY\rfloor+1}\dfrac{(qY)^{\ell}}{\ell!}$ $\displaystyle\ll(qY)^{\lfloor
eqY\rfloor}\displaystyle\sum\limits_{\ell\geqslant
1}\dfrac{(qY)^{\ell}}{\left(\ell+\lfloor
eqY\rfloor\right)!}\quad\left(\text{dropping $h(q)$and using a change of
variable }\ell\mapsto\ell-\lfloor eqY\rfloor\right)$
$\displaystyle\leqslant\dfrac{(qY)^{\lfloor eqY\rfloor}}{\lfloor
eqY\rfloor!}\displaystyle\sum\limits_{\ell\geqslant
1}\dfrac{(qY)^{\ell}}{\ell!}\left(\text{since
}\displaystyle\binom{\ell+\lfloor eqY\rfloor}{\ell}\geqslant 1\text{ so that
}\dfrac{1}{(\ell+\lfloor eqY\rfloor)!}\leqslant\dfrac{1}{\ell!\lfloor
eqY\rfloor!}\right)$ $\displaystyle\ll\dfrac{1}{\sqrt{\lfloor
eqY\rfloor}}e^{qY},$

where at the last step we used Stirling. Indeed letting $p=eqY$, we have

$\dfrac{(qY)^{\lfloor eqY\rfloor}}{\lfloor
eqY\rfloor!}\ll\dfrac{\left(\dfrac{p}{e}\right)^{\lfloor
p\rfloor}}{\left(\dfrac{\lfloor p\rfloor}{e}\right)^{\lfloor
p\rfloor}\sqrt{\lfloor p\rfloor}}=\left(\dfrac{p}{\lfloor
p\rfloor}\right)^{\lfloor p\rfloor}\dfrac{1}{\sqrt{\lfloor
p\rfloor}}\leqslant\left(1+\dfrac{1}{\lfloor p\rfloor}\right)^{\lfloor
p\rfloor}\dfrac{1}{\sqrt{\lfloor p\rfloor}}\leqslant\dfrac{e}{\sqrt{\lfloor
p\rfloor}}.$

∎

######  Remark 4.8.

In the hypothesis of the above proposition, the factor $e$ in the parameter
$eqY$ was chosen carefully. The final application of Stirling will not work if
we choose a factor strictly smaller than $e$. This choice induces a
restriction in the hypothesis of the Lemma 4.5. The proof of the lemma in
appendix B.3 crucially uses the technical condition $q>e$. This is why our
methods do not cover the case $q=2$.

###### Proof of Theorem 1.2.

We have that

$\displaystyle N(n,k)$ $\displaystyle=\displaystyle\sum_{1\leqslant j\leqslant
eqY}\binom{k-j+q-1}{q-1}N^{\prime}(n+j-k,j)+\displaystyle\sum_{j>eqY}\binom{k-j+q-1}{q-1}N^{\prime}(n+j-k,j)$
$\displaystyle=T_{1}+T_{2}.$

Proposition 4.3 shows the tail $T_{2}$ is small and is $\ll
q^{n-k}(n-k)^{q-2}.$
Lemma 4.4 and Proposition 4.7 implies,

$\displaystyle T_{1}$ $\displaystyle=\displaystyle\sum\limits_{j\leqslant
eqY}\binom{k-j+q-1}{q-1}\dfrac{q^{n+j-k}}{n-k}Q_{j}(Y)+O\left(\displaystyle\sum\limits_{j\leqslant
eqY}\binom{k-j+q-1}{q-1}\dfrac{(\log(n-k))^{j+1}}{j!(n-k)}\right)$
$\displaystyle=\dfrac{q^{n-k}}{n-k}\displaystyle\sum\limits_{j\leqslant
eqY}\binom{k-j+q-1}{q-1}q^{j}Q_{j}(Y)+O\left(\displaystyle\sum\limits_{j\leqslant
eqY}\binom{k-j+q-1}{q-1}\dfrac{(\log(n-k))^{j+1}}{j!(n-k)}\right)$
$\displaystyle=\dfrac{q^{n-k+1}k^{q-1}e^{qY}}{(q-1)!(n-k)}h(q)\Big{\\{}1+o(1)\Big{\\}}+O\left((1+o(1))\frac{k^{q-1}}{(q-1)!}\displaystyle\sum\limits_{j=1}^{\infty}\dfrac{(\log(n-k))^{j+1}}{j!(n-k)}\right)$
$\displaystyle=\dfrac{q^{n-k+1}k^{q-1}e^{qY}}{(q-1)!(n-k)}h(q)\Big{\\{}1+o(1)\Big{\\}}+O\left(k^{q-1}\dfrac{\log(n-k)e^{\log(n-k)}}{n-k}\right)$
$\displaystyle=\dfrac{q^{n-k+1}k^{q-1}e^{qY}}{(q-1)!(n-k)}h(q)\Big{\\{}1+o(1)\Big{\\}}+O\left(k^{q-1}\log(n-k)\right).$

Thus we obtain

$T_{1}\thicksim\dfrac{q^{n-k}k^{q-1}e^{qY}}{(n-k)}\dfrac{qh(q)}{(q-1)!}\thicksim
C(q)\dfrac{q^{n}k^{q-1}(n-k)^{q-1}}{q^{k}},$

where we used $e^{qY}/(n-k)=(n-k)^{q-1}$ when $Y=\log(n-k)$ and

$C(q)=\dfrac{qh(q)}{(q-1)!}=\dfrac{1}{\left((q-1)!\right)^{2}}\left(1-\dfrac{1}{q}\right)^{q^{2}}\displaystyle\prod\limits_{p\in\mathcal{P}_{\geqslant
2}}\left(1-\frac{1}{q^{deg(p)-1}}\right)^{-1}\left(1-\frac{1}{q^{deg(p)}}\right)^{q},$

a constant that only depends on $q$. ∎

##  Appendix A Auxiliary results towards theorem 1.1

We establish the technical Lemmas 3.1, 3.2 and 3.3, used in the proofs of
Theorem 1.1 and will again be used in showing Proposition 1.4. See 3.1

###### Proof of Lemma 3.1.

We define the function $f(t):=1-\frac{t^{2}}{5}-\cos t$ for $t\in[0,\pi]$ and
observe that $f^{\prime}(t)=0\implies\sin t=\frac{2t}{5}$. A quick graph plot
or plugging this equation into a computer reveals that it has only two
solutions in the interval $[0,\pi]$ , namely $t=0$ and $t\approx 2.125$. We
verify that $f^{\prime\prime}(0)=-\frac{2}{5}+\cos 0=\frac{3}{5}>0$ and hence
$t=0$ is the global minima in the interval $[0,\pi]$ since $0=f(0)<f(2.125)$,
which can also be checked on a computer. Finally since $\cos t$ and $t^{2}$
are both even functions, we have for all $t\in[-\pi,\pi]$ the following
inequality

$f(t)\geqslant 0\implies 1-\dfrac{t^{2}}{5}-\cos t\geqslant 0\implies\cos
t-1\leqslant-\dfrac{t^{2}}{5}.$

For $0\leqslant x,t\leqslant\pi$ it is well known that,

$\sin x\leqslant x\implies\displaystyle\int_{0}^{t}\sin
xdx\leqslant\displaystyle\int_{0}^{t}xdx\implies 1-\cos
t\leqslant\dfrac{t^{2}}{2}.$

Again the above inequality is true for $-\pi\leqslant t\leqslant\pi$ since
$\cos$ and $t^{2}$ are both even functions. Finally we observe
$\left|1-e^{it}\right|^{2}=(1-\cos t)^{2}+\sin^{2}t=2(1-\cos t)\leqslant
t^{2}$ and the claim follows. ∎

See 3.2

###### Proof of Lemma 3.2.

Let $I_{0}=\displaystyle\int_{|z|=r}\left|n^{z-r}\right||dz|$. After
substituting $z=re^{2\pi it}$ where
$t\in\left[-\dfrac{1}{2},\dfrac{1}{2}\right)$ we get

$\displaystyle I_{0}$
$\displaystyle\ll\displaystyle\int_{-\frac{1}{2}}^{\frac{1}{2}}\left|n^{re^{2\pi
it}-r}\right|rdt$
$\displaystyle=r\displaystyle\int_{-\frac{1}{2}}^{\frac{1}{2}}\left|n^{r(\cos
2\pi t-1)}\right|dt\qquad\left(\left|n^{ir\sin 2\pi t}\right|=1\right)$
$\displaystyle\ll
r\displaystyle\int_{-\frac{1}{2}}^{\frac{1}{2}}n^{-\frac{4\pi^{2}rt^{2}}{5}}dt\qquad(\text{
by Lemma }\ref{l15})$ $\displaystyle\ll
r\displaystyle\int_{-\infty}^{\infty}e^{-t^{2}}\dfrac{dt}{\sqrt{r\log
n}}\qquad\left(t\mapsto 2\pi t\sqrt{\dfrac{r\log n}{{5}}}\right)$
$\displaystyle\ll r\dfrac{1}{\sqrt{r\log
n}}=\dfrac{r}{\sqrt{j}}.\qquad(j=r\log n)$

∎

See 3.3

###### Proof of Lemma 3.3.

$\displaystyle\displaystyle\int\limits_{-\infty}^{\infty}\theta^{2}\exp\left(-\dfrac{k\theta^{2}}{5}\right)d\theta$
$\displaystyle=\dfrac{5\sqrt{5}}{k^{\frac{3}{2}}}\displaystyle\int_{0}^{\infty}\sqrt{z}e^{-z}dz\qquad\left(z=\dfrac{k\theta^{2}}{5}\right)$
$\displaystyle\ll k^{-\frac{3}{2}}.\qquad\left(\text{ since
}\displaystyle\int_{0}^{\infty}\sqrt{z}e^{-z}dz\text{ is convergent}\right)$

∎

##  Appendix B towards Proposition 1.4 and auxiliary results for theorem 1.2

###  B.1. A Selberg-Delange style argument for $\widetilde{M_{z}}(n)$

See 1.4

###### Proof of Proposition 1.4.

We recall some definitions for convenience,

$\widetilde{\mathcal{M}}:=\bigg{\\{}\textit{set of all monics in
}\mathbb{F}_{q}[t]\textit{ having no root in }\mathbb{F}_{q}\bigg{\\}},$
$\widetilde{\mathcal{M}_{n}}:=\bigg{\\{}\textit{set of all of degree
}n\textit{ monics in }\mathbb{F}_{q}[t]\textit{ having no root in
}\mathbb{F}_{q}\bigg{\\}},$
$N^{\prime}(n,k):=\\#\bigg{\\{}f\in\widetilde{\mathcal{M}_{n}}:\Omega(f)=k\bigg{\\}}.$

We proceed as the proof of Theorem 1.1 by first defining the following
quantities,

$\widetilde{M}_{z}(n)=\displaystyle\sum\limits_{f\in\widetilde{\mathcal{M}_{n}}}z^{\Omega(f)}=\displaystyle\sum\limits_{k\geqslant
0}z^{k}N^{\prime}(n,k)\text{ and
}\widetilde{G}_{z}(u)=\displaystyle\sum\limits_{f\in\widetilde{\mathcal{M}}}z^{\Omega(f)}u^{deg(f)}.$

Our Euler product decomposition for $\widetilde{G}_{z}(u)$ now becomes

$\widetilde{G_{z}}(u)=\displaystyle\prod_{p\in\mathcal{P}_{\geqslant
2}}\left(1-zu^{deg(p)}\right)^{-1}.$

Following the same spirit we now have

$\widetilde{G}_{z}(u)=\zeta(u)^{z}\widetilde{F}_{z}(u),$

where $\widetilde{F}_{z}$ is given by the Euler product below

$\widetilde{F}_{z}(u)=(1-u)^{qz}\displaystyle\prod\limits_{p\in\mathcal{P}_{\geqslant
2}}\left(1-zu^{deg(p)}\right)^{-1}\left(1-u^{deg(p)}\right)^{z}.$

We first show the above Euler product converges absolutely in the region
defined by,

$\widetilde{\mathcal{R}}:=\Big{\\{}(u,z)\in\mathbb{C}^{2}:|z|<q^{2},|u|^{2}<|z|^{-1},|u|<q^{-1/2}\Big{\\}}\subset\mathbb{C}^{2}.$

We take the standard branch of complex logarithm defined over
$\mathbb{C}\setminus(-\infty,0]$ and get for each integer $n\geqslant 2$,
(since $|u|^{n}<1,|zu^{n}|\leqslant|zu^{2}|<1)$

$\displaystyle z\log(1-u^{n})-\log(1-zu^{n})$
$\displaystyle=-zu^{n}+O\left(\left|zu^{2n}\right|\right)+zu^{n}+O\left(\left|z^{2}u^{2n}\right|\right)$
$\displaystyle=O\left(\left|q^{4}u^{2n}\right|\right)\qquad\left(|z|<q^{2}\right).$

and hence using $\exp(O(x))=1+O(x)$ for $x=O(1)$ we get,

$(1-u^{n})^{z}(1-zu^{n})^{-1}=1+O\left(\left|q^{4}u^{2n}\right|\right).$

We now observe the Euler product for $\widetilde{F}_{z}$ converges uniformly
on the compact subsets of $\widetilde{\mathcal{R}}$ as

$\displaystyle\sum\limits_{p\in\mathcal{P}_{\geqslant
2}}|u|^{2n}\leqslant\displaystyle\sum\limits_{n\geqslant
2}|qu^{2}|^{n}<\infty.\qquad(\text{where we used},\\#\mathcal{P}_{n}\leqslant
q^{n})$

We also verify $|1-zu^{deg(p)}|\geqslant 1-|zu^{deg(p)}|\geqslant
1-|zu^{2}|>0$, which shows none of the $\left(1-zu^{deg(p)}\right)^{-1}$
factors contribute to a pole in $\widetilde{\mathcal{R}}$.
Also $(1-u)^{qz}$ is holomorphic in $\widetilde{\mathcal{R}}$ and this proves
$\widetilde{F_{z}}(u)$ is holomorphic inside $\widetilde{\mathcal{R}}$. We
determine the coefficient of $u^{n}$ in $\widetilde{{G}_{z}}(u)$ using
Cauchy’s integral formula and recover $\widetilde{{M}_{z}}(n)$ exactly as in
the proof of Theorem 1.1. We have that, if $|u|=r<q^{-1}$ (refer to the small
green circle in the same Fig-3 below), then using Cauchy’s residue formula on
(2.1) gives

(B.2) $\widetilde{M_{z}}(n)=\dfrac{1}{2\pi
i}\displaystyle\int\limits_{|u|=r}\widetilde{G_{z}}(u)\dfrac{du}{u^{n+1}}=\dfrac{1}{2\pi
i}\displaystyle\int\limits_{|u|=r}\zeta(u)^{z}\widetilde{F_{z}}(u)\dfrac{du}{u^{n+1}}.$

Figure 3. The contour appearing in the proof of Proposition
1.4${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\widetilde{\mathcal{H}^{\prime}}}$${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}|u|=1/q+\widetilde{\eta}}$${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}|u|=1/q}$${\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}|u|=r}$

Now we again want to collect the contribution coming from the singularity of
$\zeta(u)^{z}$ at $u=1/q$ to evaluate the above integral. We shift the contour
$|u|=r$ to a bigger circle $|u|=1/q+\widetilde{\eta}$ with a different choice
of $\widetilde{\eta}$ here (not the same choice for $\eta$ in Proposition 1.3)
and with $|z|\leqslant q^{2}-\delta$. Since the region of absolute convergence
for $\widetilde{F_{z}}(u)$ here is $\widetilde{\mathcal{R}}$, we have a
different set of constraints on $\widetilde{\eta}$ than before. Here we get
for $\widetilde{\eta}$,
$|zu^{2}|\leqslant(q^{-1}+\widetilde{\eta})^{2}(q^{2}-\delta)\leqslant 1$ and
$|u|=1/q+\widetilde{\eta}<q^{-\frac{1}{2}}$. This shows taking any
$0<\widetilde{\eta}<\min\\{1/\sqrt{q^{2}-\delta}-1/q,1/\sqrt{q}-1/q\\}$
suffices. We then plan to use Lemma 2.2 to evaluate the integral in (B.2)
with, $\widetilde{\eta}=\min\\{1/\sqrt{q^{2}-\delta}-1/q,1/\sqrt{q}-1/q\\}/2$
for $|z|\leqslant q^{2}-\delta$ just as we did in the proof of Proposition
1.3.

######  Remark B.1.

$F_{z}(u)$ was absolutely convergent in $\mathcal{R}$ which gave us the
appropriate choice for $\eta$. All the calculations are identical here with
$\widetilde{F_{z}}$ instead of $F_{z}$. The main difference is, here we have
$|z|\leqslant q^{2}-\delta$ instead of $|z|\leqslant q-\epsilon$. Earlier
${F}_{z}\left(\frac{1}{q}\right)$ had a pole at $z=q,q^{2},\ldots$ but we got
rid of the $z=q$ pole here. This is what essentially allows us to take
$|z|\leqslant q^{2}-\delta.$

We therefore get

$\displaystyle\widetilde{M}_{z}(n)$ $\displaystyle=\dfrac{1}{2\pi
i}\displaystyle\int\limits_{\\{|u|=\frac{1}{q}+\widetilde{\eta\\}}\cup\widetilde{\mathcal{H}^{\prime}}}\zeta(u)^{z}\widetilde{F}_{z}(u)\dfrac{du}{u^{n+1}}$
$\displaystyle=\widetilde{F}_{z}\left(\dfrac{1}{q}\right)q^{n}n^{z-1}\left(\dfrac{1}{\Gamma(z)}+O_{\delta}\left(\dfrac{1}{n}\right)\right)$
$\displaystyle=q^{n}n^{z-1}\left(zh(z)+O_{\delta}\left(\dfrac{1}{n}\right)\right),$

where

$h(z)=\dfrac{1}{z}\widetilde{F}_{z}\left(\dfrac{1}{q}\right)\dfrac{1}{\Gamma(z)}=\dfrac{1}{\Gamma(z+1)}\left(1-\dfrac{1}{q}\right)^{qz}\displaystyle\prod\limits_{p\in\mathcal{P}_{\geqslant
2}}\left(1-\frac{z}{q^{deg(p)}}\right)^{-1}\left(1-\frac{1}{q^{deg(p)}}\right)^{z}.$

Also we have
$h(z)=\frac{1}{\Gamma(z+1)}\widetilde{F}_{z}\left(\frac{1}{q}\right)$. Since,
$\widetilde{F}_{z}\left(\frac{1}{q}\right)$ is analytic in $|z|<q^{2}$, so is
$h$. ∎

###  B.2. An useful upper bound for $N^{\prime}(n,j)$.

See 4.2

###### Proof of Lemma 4.2.

We use Proposition 1.4 with $z=q+\eta$ and if $a_{j}(f)$ denotes the indicator
function of polynomials in $\widetilde{M_{n}}$ with $\Omega(f)=j$ then, we see
that every time $a_{j}=1$ occurs, it contributes an amount of
$\left(q+\eta\right)^{j}$ on the left hand side of the sum of Proposition 1.4
and all the other terms are positive. We have by the previous lemma $h(z)$ is
analytic in an open set containing the disc $|z|\leqslant q^{2}-\delta$. Since
the disk is compact and $h$ is continuous there, we have $h(z)\ll_{q,\delta}1$
for every $|z|\leqslant q^{2}-\delta$. Consequently for every $|z|\leqslant
q^{2}-\delta$, $|zh(z)|\leqslant|(q+\eta)h(q+\eta)|\ll_{q,\delta}1$. This
observation leads to an upper bound
$N^{\prime}(n,j)\ll_{q,\delta}q^{n}n^{q+\eta-1}\left(\frac{1}{q+\eta}\right)^{j}$.
∎

###  B.3. An uniform estimate for $N^{\prime}(n,j)$ when $j\leqslant eq\log n$

See 4.5

###### Proof of Lemma 4.5.

We use Proposition 1.4. The coefficient of $z^{j}$ in $\widetilde{M}_{z}(n)$
is what we want to evaluate. We have for $r<q^{2}$,

$N^{\prime}(n,j)=\dfrac{1}{2\pi
i}\displaystyle\int\limits_{|z|=r}\widetilde{M}_{z}(n)\dfrac{dz}{z^{j+1}}.$

We recall from Proposition 1.4
$\widetilde{M}_{z}(n)=\dfrac{q^{n}}{n}\bigg{\\{}zh(z)n^{z}+O\left(n^{z-1}\right)\bigg{\\}}.$
Plugging this back in the integral we get that

$\dfrac{n}{q^{n}}N^{\prime}(n,j)=\dfrac{1}{2\pi
i}\displaystyle\int_{|z|=r}zh(z)n^{z}\dfrac{dz}{z^{j+1}}+O(E_{0}),$

where $E_{0}$ is given by,
$\displaystyle\int_{|z|=r}\left|\dfrac{n^{z-1}}{z^{j+1}}\right||dz|.$ At this
point we choose $r=\frac{j}{\log n}\leqslant eq<q^{2}$ since by hypothesis
$j\leqslant eq\log n$ and $q\geqslant 3$.
Noting $e^{j}=n^{r}\iff j=r\log n$ and using Lemma 3.2, we get the term
$E_{0}$ is bounded by

$\ll\dfrac{r^{-j-1}e^{j}}{n}\displaystyle\int_{|z|=r}|n^{z-r}||dz|\ll\dfrac{r^{-j-1}e^{j}}{n}\dfrac{r}{j^{\frac{1}{2}}}\ll\dfrac{1}{n}\dfrac{(e\log
n)^{j}}{j^{j+\frac{1}{2}}}\ll\dfrac{1}{n}\dfrac{(\log n)^{j}}{j!},$

where the final step of bounding follows by Stirling. This is the same trick
that we used while bounding above $E$ on page 10 in the proof of Theorem 1.1.
We now return to the main term

$M_{0}=\dfrac{1}{2\pi
i}\displaystyle\int_{|z|=r}zh(z)n^{z}\dfrac{dz}{z^{j+1}}=\dfrac{1}{2\pi
i}\displaystyle\int_{|z|=r}h(z)n^{z}\dfrac{dz}{z^{j}},$

where $h(z)$ is an analytic function in the region $|z|<q^{2}$, so the
integrand has a pole at $z=0$ of order $j$. We evaluate this integral using
residue theorem and obtain

$M_{0}=\lim\limits_{z\to
0}\dfrac{1}{(j-1)!}\dfrac{d^{j-1}}{dz^{j-1}}h(z)n^{z}.$

Using binomial theorem for higher order differentiation of products of two
complex functions

$\displaystyle\dfrac{1}{(j-1)!}\dfrac{d^{j-1}}{dz^{j-1}}h(z)n^{z}\Bigg{|}_{z=0}$
$\displaystyle=\dfrac{1}{(j-1)!}\displaystyle\sum\limits_{m+\ell=j-1}\dfrac{(j-1)!}{m!\ell!}h^{(m)}(z)(n^{z})^{(\ell)}\Bigg{|}_{z=0}$
$\displaystyle=\displaystyle\sum\limits_{m+\ell=j-1}\dfrac{1}{m!\ell!}h^{(m)}(0)(\log
n)^{\ell}.$

where we have taken the limits inside the argument of the higher order
derivatives which is allowed because all the functions here are analytic and
hence infinitely differentiable. Plugging everything back we obtain the
desired result. ∎

###  B.4. A technical upper bound for $h(z)$, $Q_{j}(X)$ and their
derivatives.

See 4.6

###### Proof of Lemma 4.6.

From Proposition 1.4 we have that $h(z)$ is holomorphic for $|z|<q^{2}$ which
in particular implies $h(z)\ll_{q}1$ for $|z|\leqslant 2.9q$. Therefore we
have by Cauchy’s integral formula,

$h^{(m)}(0)/m!=\dfrac{1}{2\pi}\left|\displaystyle\int\limits_{|z|=2.9q}h(z)\dfrac{dz}{z^{m+1}}\right|\ll\left(\dfrac{1}{2.9q}\right)^{m}\quad\left(2.9q<q^{2}\text{
whenever }q\geqslant 3\right).$

We have from Lemma 4.4

$Q_{j}(X)=\displaystyle\sum\limits_{m+\ell=j-1}\dfrac{1}{m!\ell!}h^{(m)}(0)X^{\ell}\ll\displaystyle\sum\limits_{m+\ell=j-1}\left(\dfrac{1}{2.9q}\right)^{m}\dfrac{X^{\ell}}{\ell!}$

We now take out the top term $\frac{X^{j-1}}{(j-1)!}$ to bound the sum from
above and observe for each $m\geqslant 1$,
$\frac{X^{\ell}}{\ell!}=\frac{X^{j-m-1}}{(j-m-1)!}\leqslant(eq)^{m}\frac{X^{j-1}}{(j-1)!}$
which is true after cross multiplying whenever $j\leqslant eqX$ since
$(j-1)(j-2)\cdots(j-m)\leqslant j^{m}\leqslant(eqX)^{m}$. Hence we arrive at
the following upper bound,

$Q_{j}(X)\ll\dfrac{X^{j-1}}{(j-1)!}\displaystyle\sum\limits_{0\leqslant
m\leqslant j-1}\left(\dfrac{eq}{2.9q}\right)^{m}\ll\dfrac{X^{j-1}}{(j-1)!}.$

Likewise when $j\leqslant eqX,$

$\displaystyle Q_{j}^{\prime}(X)$
$\displaystyle=\displaystyle\sum\limits_{m+\ell=j-1}\dfrac{1}{m!(\ell-1)!}h^{(m)}(0)X^{\ell-1}$
$\displaystyle\ll\displaystyle\sum\limits_{m+\ell=j-1}\left(\dfrac{1}{2.9q}\right)^{m}\dfrac{X^{\ell-1}}{(\ell-1)!}$
$\displaystyle\ll\dfrac{X^{j-2}}{(j-2)!}\displaystyle\sum\limits_{0\leqslant
m\leqslant j-1}\left(\dfrac{eq}{2.9q}\right)^{m}$
$\displaystyle\ll\dfrac{X^{j-2}}{(j-2)!}.$

∎

###  B.5. One of the main ingredients of Proposition 4.7 and Theorem 1.2

See 4.4

###### Proof of Lemma 4.4.

By Lemma 4.5 we have that

(B.3)
$N^{\prime}(n+j-k,j)=\dfrac{q^{n+j-k}}{n+j-k}\Bigg{\\{}Q_{j}(\log(n+j-k))+O\left(\dfrac{(\log(n+j-k))^{j}}{j!(n+j-k)}\right)\Bigg{\\}}.$

We observe $n-k\geqslant n\left(1-\frac{1}{B}\right)\to\infty$ as
$n\to\infty$. We also note if $E_{1}=\frac{(\log(n-k))^{j+1}}{j!(n-k)^{2}}$
and $E_{2}=\frac{(\log(n+j-k))^{j}}{j!(n+j-k)^{2}}$ then as $n\to\infty$

$\displaystyle\dfrac{E_{2}}{E_{1}}$
$\displaystyle=\dfrac{1}{(\log(n-k))}\left(\dfrac{\log(n+j-k)}{\log(n-k)}\right)^{j}\dfrac{(n-k)^{2}}{(n+j-k)^{2}}$
$\displaystyle\leqslant\left(1+\dfrac{\log\left(1+\dfrac{j}{n-k}\right)}{\log(n-k)}\right)^{j}\dfrac{1}{(\log(n-k))}\to
0$ $\displaystyle\implies E_{2}=o(E_{1}),$

where we have at the second step the term inside the bracket is bounded,
because $\frac{j}{n-k}\leqslant\frac{eq\log(n-k)}{(n-k)}\to 0$ and hence for
$n$ large enough it is bounded by $(1+\log 2/\log(n-k))^{eq\log(n-k)}\leqslant
e^{eq\log 2}=2^{eq}$. Thus from (B.3) we arrive at

(B.4)
$N^{\prime}(n+j-k,j)=q^{n+j-k}\left\\{\dfrac{Q_{j}(\log(n+j-k))}{n+j-k}+O\left(E_{1}\right)\right\\}$

We show at a small cost it is possible to replace
$\frac{Q_{j}(\log(n+j-k))}{n+j-k}$ by $\frac{Q_{j}(\log(n-k))}{n-k}$. We use
mean value theorem to study the error.
Let $F(x):=\frac{Q_{j}(\log x)}{x}$ which is a regular function if $x>0$. The
difference caused by this replacement

$D=\dfrac{Q_{j}(\log(n+j-k))}{n+j-k}-\dfrac{Q_{j}(\log(n-k)}{n-k}=F(n+j-k)-F(n-k).$

By mean value theorem one can pick $y\in(n-k,n+j-k)$ such that

$D=jF^{\prime}(y)=j\dfrac{Q_{j}^{\prime}(\log y)-Q_{j}(\log
y)}{y^{2}}=\dfrac{j}{y^{2}}Q_{j}^{\prime}(\log y)-\dfrac{j}{y^{2}}Q_{j}(\log
y)=F_{1}+F_{2}.$

Therefore (B.4) implies

(B.5)
$N^{\prime}(n+j-k,j)=q^{n+j-k}\left\\{\frac{Q_{j}(\log(n-k))}{n-k}+F_{1}+F_{2}+O\left(E_{1}\right)\right\\}$

We apply Lemma 4.6 with the choice $X=\log y$. We note from the hypothesis
that $j\leqslant eqY\leqslant eq\log y$ and $y>n-k$, so that we must have
$X=\log y\to\infty$ with $n$. Using this observation, we upper bound the first
term of $F_{1}$ which gives $F_{1}=\frac{j}{y^{2}}Q_{j}^{\prime}(\log
y)\ll\frac{j}{y^{2}}\frac{(\log(n+j-k))^{j-2}}{(j-2)!}.$ Thus we obtain

$\displaystyle\dfrac{F_{1}}{E_{1}}$
$\displaystyle=\dfrac{(n-k)^{2}j!}{(\log(n-k))^{j+1}}\dfrac{j}{y^{2}}\dfrac{(\log(n+j-k))^{j-2}}{(j-2)!}$
$\displaystyle\leqslant\left(\dfrac{\log(n+j-k)}{\log(n-k)}\right)^{j-2}\dfrac{j^{2}(j-1)}{(\log(n-k))^{3}}$
$\displaystyle\ll 1,$

since $j\leqslant eq\log(n-k)$ and $y>n-k.$ Hence $F_{1}=O(E_{1})$ and
likewise from Lemma 4.6 one can show $|F_{2}|=\frac{j}{y^{2}}Q_{j}(\log
y)\ll\frac{j(\log(n+j-k))^{j-1}}{y^{2}(j-1)!}.$
Thus we infer

$\displaystyle\dfrac{|F_{2}|}{E_{1}}$
$\displaystyle=\dfrac{j!(n-k)^{2}}{(\log(n-k))^{j+1}}\dfrac{j(\log(n+j-k))^{j-1}}{y^{2}(j-1)!}$
$\displaystyle\leqslant\left(\dfrac{\log(n+j-k)}{\log(n-k)}\right)^{j-1}\dfrac{j^{2}}{(\log(n-k))^{2}}$
$\displaystyle\ll 1.$

The proof is now complete once we plug $F_{1}+F_{2}=O(E_{1})$ in (B.5). ∎

## References

  * [1] J. L. Nicolas, Sur la distribution des nombres entiers ayant une quantité fixée de facteurs premiers, Acta Arithmetica, 44, 191–200 (1984).
  * [2] E. Landau, Handbuch der Lehre von der Verteilung der Primzahlen, Chealsea Publishing Company (1953).
  * [3] S. Ramanujan, Collected Papers, Chealsea Publishing Company (1953).
  * [4] L.G. Sathe, On a problem of Hardy on the distribution of integers having a given number of prime factors, J. Indian Math Soc. 17 (1953), p. 63–141; 18 (1954); p. 27–81.
  * [5] A. Selberg, Note on a paper by L.G. Sathe, ibid. 18, J. Indian Math Soc., p. 83–87 (1954).
  * [6] S. Porrit, Character sums over products of prime polynomials, arXiv:2003.12002, (2020).
  * [7] M. Carr, Factorisation dans $F_{q}[X]$, C. R. Acad. Sci. Paris Sér. I Math., 294(4):147–150, (1982).
  * [8] R. Warlimont, Arithmetical semigroups. IV. Selberg’s analysis, Arch. Math. (Basel), 60 (1):58–72, (1993).
  * [9] H. K. Hwang, A poisson $\ast$ negative binomial convolution law for random polynomials over finite fields, Random Structures Algorithms, 13(1):17–47, (1998).
  * [10] A. Afshar, S. Porrit, The function field Sathe-Selberg formula in arithmetic progressions and ‘short intervals’, Acta Arith., 187(2):101–124, (2019).
  * [11] P.D.T.A. Elliot, Probabilistic Number Theory I et II, Springer Verlag , Grundlehren der mathematischen Wissenschaften (1980).
  * [12] M. Rosen, Number Theory in Function Fields, Springer-Verlag (2002).
  * [13] G. Tenenbaum, An Introduction to Analytic and Probabilistic Number Theory, Cambridge University Press (2015).
  * [14] D. Elboim, O. Gorodetsky Uniform estimates for almost primes over finite fields, arXiv:2008.05778v2, (2020).