1 Introduction
Let
$b(n)$
be the characteristic function of integers that are representable as a sum of two squares and let
$$\begin{eqnarray}B(x)=\mathop{\sum }_{n\leqslant x}b(n)\end{eqnarray}$$
be the number of such integers up to
$x$
. Landau’s theorem [Reference Landau14] gives an asymptotic formula for
$B(x)$
:
$$\begin{eqnarray}B(x)=K\frac{x}{\sqrt{\ln x}}+O\biggl(\frac{x}{\ln ^{3/2}x}\biggr),\quad x\rightarrow \infty ,\end{eqnarray}$$
where
$$\begin{eqnarray}K=\frac{1}{\sqrt{2}}\mathop{\prod }_{p\equiv 3\hspace{0.2em}{\rm mod}\hspace{0.2em}4}(1-p^{-2})^{-1/2}\approx 0.764\end{eqnarray}$$
is the Landau–Ramanujan constant.
A polynomial analogue of the function
$B(x)$
, which we describe below, was studied by Bary-Soroker et al [Reference Bary-Soroker, Smilansky and Wolf3]. Let
$q$
be an odd prime power, and
$\mathbb{F}_{q}$
denote the field of
$q$
elements. Denote by
${\mathcal{M}}_{n,q}$
the set of monic polynomials in
$\mathbb{F}_{q}[T]$
of degree
$n$
, by
${\mathcal{M}}_{q}=\bigcup _{n\geqslant 0}{\mathcal{M}}_{n,q}$
the set of all monic polynomials in
$\mathbb{F}_{q}[T]$
and by
${\mathcal{P}}_{q}$
the set of monic irreducible polynomials in
$\mathbb{F}_{q}[T]$
.
For a polynomial
$f\in {\mathcal{M}}_{n,q}$
we define the characteristic function
$$\begin{eqnarray}b_{q}(f)=\left\{\begin{array}{@{}ll@{}}1\quad & f=A^{2}+TB^{2}\text{ for }A,B\in \mathbb{F}_{q}[T],\\ 0\quad & \text{otherwise},\end{array}\right.\end{eqnarray}$$
and the counting function
$$\begin{eqnarray}B(n,q)=\mathop{\sum }_{f\in M_{n,q}}b_{q}(f).\end{eqnarray}$$
In [Reference Bary-Soroker, Smilansky and Wolf3, Theorems 1.2 and 1.3], the asymptotic behaviour of
$B(n,q)$
was studied in two limits, fixed
$n$
and large
$q$
and fixed
$q$
and large
$n$
,
$$\begin{eqnarray}\displaystyle B(n,q) & = & \displaystyle \frac{\binom{2n}{n}}{4^{n}}\cdot q^{n}+O_{n}(q^{n-1}),\quad q\rightarrow \infty ,\end{eqnarray}$$
$$\begin{eqnarray}\displaystyle B(n,q) & = & \displaystyle \frac{K_{q}}{\sqrt{\unicode[STIX]{x1D70B}}}\cdot \frac{q^{n}}{\sqrt{n}}+O_{q}\biggl(\frac{q^{n}}{n^{3/2}}\biggr),\quad n\rightarrow \infty ,\end{eqnarray}$$
where
$$\begin{eqnarray}\displaystyle K_{q}=(1-q^{-1})^{-1/2}\mathop{\prod }_{P\in {\mathcal{P}}_{q}:(P/T)=-1}(1-q^{-2\deg P})^{-1/2}=1+O\biggl(\frac{1}{q}\biggr). & & \displaystyle\end{eqnarray}$$
The asymptotic formula (1.6) is proved using elementary combinatorial considerations, while (1.7) is proved using complex analysis. In a recent preprint, Matei [Reference Matei17] extended (1.6) by writing
$B(n,q)$
as a polynomial in
$q$
and proving that the coefficients have a certain structure and a cohomological interpretation.
The authors of [Reference Bary-Soroker, Smilansky and Wolf3] write “We do not know of an asymptotic formula for
$B(n,q)$
in any more general sub-limits of
$q^{n}\rightarrow \infty$
”. We prove an asymptotic formula in the most general limit
$q^{n}\rightarrow \infty$
.
Theorem 1.1. We have
$$\begin{eqnarray}B(n,q)=K_{q}\cdot \binom{n-\frac{1}{2}}{n}\cdot q^{n}+O\biggl(\frac{q^{n-1}}{n^{3/2}}\biggr),\quad q^{n}\rightarrow \infty ,\end{eqnarray}$$
and the implied constant is absolute.
We also investigate the constant
$K_{q}$
, which turns out to be an analytic function of
$q^{-1}$
.
Remark 1.2. To see that Theorem 1.1 is consistent with (1.6) and (1.7), note that
$$\begin{eqnarray}\binom{n-\frac{1}{2}}{n}=\frac{\binom{2n}{n}}{4^{n}}\sim \frac{1}{\sqrt{\unicode[STIX]{x1D70B}n}},\quad n\rightarrow \infty ,\end{eqnarray}$$
and that by (1.8),
$K_{q}=1+O(1/q)$
.
Our methods differ from those used in [Reference Bary-Soroker, Smilansky and Wolf3], and are based on explicit estimates for the coefficients of a certain class of generating functions. Another advantage of our methods, is that they apply to other problems, see §2.
2 Further applications
2.1 Prime factors of even degree
Suppose we want to count “ordinary” sums of two squares in
$\mathbb{F}_{q}[T]$
, i.e. elements of the form
$A^{2}+B^{2}$
. If
$q\equiv 1\,\text{mod}\,4$
, then
$\sqrt{-1}\in \mathbb{F}_{q}$
. Given
$f\in \mathbb{F}_{q}[T]$
, we have
$f=((f-1)/2\sqrt{-1})^{2}+((f+1)/2)^{2}$
, and so every polynomial is of the form
$A^{2}+B^{2}$
. If
$q\equiv 3\hspace{0.6em}{\rm mod}\hspace{0.2em}4$
, Leahey [Reference Leahey15] has shown that the polynomials of the form
$A^{2}+B^{2}$
are those whose prime factors of odd degree appear only with even multiplicity. Imitating Leahey’s proof, one sees that if
$q$
is an odd prime power and
$$\begin{eqnarray}\unicode[STIX]{x1D6FC}\in \mathbb{F}_{q}^{\times }\setminus (\mathbb{F}_{q}^{\times })^{2},\end{eqnarray}$$
then the monic polynomials of the form
$A^{2}-\unicode[STIX]{x1D6FC}B^{2}$
(
$A,B\in \mathbb{F}_{q}[T]$
) are also characterized by the property that their prime factors of odd degree appear with even multiplicity. This raises the problem of estimating the number of monic polynomials of a given degree in the following set, which makes sense for any prime power
$q$
:
$$\begin{eqnarray}S_{1}(q)=\{f\in {\mathcal{M}}_{q}:P\mid f\text{ and }2\nmid \deg P\;\Longrightarrow \;2\mid v_{P}(f)\},\end{eqnarray}$$
where
$v_{P}(f)$
is the multiplicity of
$P$
in
$f$
. Let
$$\begin{eqnarray}B_{1}(2n,q)=\#\{f\in S_{1}(q):\deg f=2n\}.\end{eqnarray}$$
Chuang et al [Reference Chuang, Kuan and Yu5] considered two natural variations on
$S_{1}(q)$
. The first is the subset of
$S_{1}(q)$
of polynomials with no odd-degree prime factors:
$$\begin{eqnarray}\begin{array}{@{}rcl@{}}\displaystyle S_{2}(q)\ & =\ & \{f\in {\mathcal{M}}_{q}:P\mid f\;\Longrightarrow \;2\mid \deg P\},\\ \displaystyle B_{2}(2n,q)\ & =\ & \#\{f\in S_{2}(q):\text{deg}\,f=2n\}.\end{array}\end{eqnarray}$$
The second is the subset of squarefree polynomials in
$S_{2}(q)$
:
$$\begin{eqnarray}\begin{array}{@{}rcl@{}}\displaystyle S_{3}(q)\ & =\ & \{f\in {\mathcal{M}}_{q}:P\mid f\;\Longrightarrow \;2\mid \deg P\text{ and }P^{2}\nmid f\},\\ \displaystyle B_{3}(2n,q)\ & =\ & \#\{f\in S_{3}(q):\deg f=2n\}.\end{array}\end{eqnarray}$$
The motivation for studying
$S_{2}(q)$
,
$S_{3}(q)$
is the following. Assume that
$q$
is odd. As observed by Artin [Reference Artin1] in his study of quadratic extensions of
$\mathbb{F}_{q}(T)$
, the analogue over
$\mathbb{F}_{q}[T]$
of a fundamental discriminant is a squarefree monic polynomial
$D$
. The negative Pell equation asks for the solubility of
$$\begin{eqnarray}X^{2}-DY^{2}=\unicode[STIX]{x1D6FE}_{q}\quad \text{with }X,Y\in \mathbb{F}_{q}[T],\end{eqnarray}$$
where
$\unicode[STIX]{x1D6FE}_{q}$
is a generator of
$\mathbb{F}_{q}^{\times }$
. By considering (2.6) modulo a prime factor
$P$
of
$D$
, we find
$$\begin{eqnarray}\biggl(\frac{\unicode[STIX]{x1D6FE}_{q}}{P}\biggr)=1,\end{eqnarray}$$
where
$(\frac{\bullet }{P})$
is the Legendre symbol modulo
$P$
. By quadratic reciprocity, equation (2.7) implies that
$P$
has even degree. Thus, the negative Pell equation has no solution for a given fundamental discriminant
$D$
of degree
$2N$
unless
$D$
is among those
$B_{3}(2N,q)$
polynomials counted in (2.5).
The problem of estimating, in the limit
$n\rightarrow \infty$
, the proportion in
$B_{3}(2n,q)$
of the discriminants
$D$
for which (2.6) is soluble, is an open problem studied by Bae and Jung [Reference Bae and Jung2, Theorem 1.5]. Their work is motivated by the number field setting, studied by Stevenhagen [Reference Stevenhagen21, Conjecture 1.2] and Fouvry and Klüners [Reference Fouvry and Klüners8, Theorem 1].
The asymptotics of
$B_{2}(2n,q)$
,
$B_{3}(2n,q)$
in the limit
$n\rightarrow \infty$
are given in[Reference Chuang, Kuan and Yu5, Theorems 1 and 2]:
$$\begin{eqnarray}\begin{array}{@{}rcl@{}}\displaystyle B_{2}(2n,q)\ & =\ & \displaystyle C_{q,2}\frac{q^{2n}}{\sqrt{\unicode[STIX]{x1D70B}n}}+O_{q}\biggl(\frac{q^{2n}}{n^{3/2}}\biggr),\quad n\rightarrow \infty ,\\ \displaystyle B_{3}(2n,q)\ & =\ & \displaystyle C_{q,3}\frac{q^{2n}}{\sqrt{\unicode[STIX]{x1D70B}n}}+O_{q}\biggl(\frac{q^{2n}}{n^{3/2}}\biggr),\quad n\rightarrow \infty ,\end{array}\end{eqnarray}$$
where
$C_{q,2}$
and
$C_{q,3}$
are positive constants, given explicitly in [Reference Chuang, Kuan and Yu5, Theorems 1 and 2] as infinite products.
We modify the main term of (2.8) to obtain an asymptotic formula in the general limit
$q^{n}\rightarrow \infty$
.
Theorem 2.1. For any positive integer
$n$
,
$$\begin{eqnarray}\displaystyle B_{1}(2n,q) & = & \displaystyle C_{q,1}\cdot \binom{n-\frac{1}{2}}{n}\cdot q^{2n}+O\biggl(\frac{q^{2n-1}}{n^{3/2}}\biggr),\quad q^{n}\rightarrow \infty ,\end{eqnarray}$$
$$\begin{eqnarray}\displaystyle B_{2}(2n,q) & = & \displaystyle C_{q,2}\cdot \binom{n-\frac{1}{2}}{n}\cdot q^{2n}+O\biggl(\frac{q^{2n-1}}{n^{3/2}}\biggr),\quad q^{n}\rightarrow \infty ,\end{eqnarray}$$
$$\begin{eqnarray}\displaystyle B_{3}(2n,q) & = & \displaystyle C_{q,3}\cdot \binom{n-\frac{1}{2}}{n}\cdot q^{2n}+O\biggl(\frac{q^{2n-1}}{n^{3/2}}\biggr),\quad q^{n}\rightarrow \infty ,\end{eqnarray}$$
where the implied constants are absolute. Moreover,
$C_{q,i}=1+O(1/q)$
.
2.2 Higher genus
We consider a higher genus analogue of the sets
$S_{1}(q)$
,
$S_{2}(q)$
and
$S_{3}(q)$
. Consider a function field
$K$
with finite constant field
$\mathbb{F}_{q}$
, i.e.
$K$
is a finitely generated field extension of transcendence degree one over
$\mathbb{F}_{q}$
and
$\mathbb{F}_{q}$
is algebraically closed in
$K$
. Let
$\mathfrak{Q}$
be a fixed place of
$K$
. Let
$\mathbb{P}_{K}$
be the set of places of
$K$
.
For each place
$\mathfrak{P}$
of
$K$
, the corresponding valuation
$K\rightarrow \mathbb{Z}\cup \{\infty \}$
is denoted by
$v_{\mathfrak{P}}$
. The residue field at
$\mathfrak{P}$
is denoted by
$\mathbb{F}_{\mathfrak{P}}$
. The degree
$\deg _{K}\mathfrak{P}$
of
$\mathfrak{P}$
is
$[\mathbb{F}_{\mathfrak{P}}:\mathbb{F}_{q}]$
. Let
$\text{Div}(K)$
be the divisor group of
$K$
. Every element
$D$
in
$\text{Div}(K)$
may be written uniquely as
$$\begin{eqnarray}D=\mathop{\sum }_{\mathfrak{P}\in \mathbb{P}_{K}}v_{\mathfrak{P}}(D)\cdot \mathfrak{P}.\end{eqnarray}$$
Given
$D\in \text{Div}(K)$
, we define the degree of
$D$
as
$$\begin{eqnarray}\deg D=\mathop{\sum }_{\mathfrak{P}\in \mathbb{P}_{K}}v_{\mathfrak{P}}(D)\cdot \deg _{K}\mathfrak{P}.\end{eqnarray}$$
The set
$$\begin{eqnarray}\text{Div}_{0,\mathfrak{Q}}(K)=\{D\in \text{Div}(k):\deg D=0,v_{\mathfrak{P}}(D)<0\;\Longrightarrow \;\mathfrak{P}=\mathfrak{Q}\}\end{eqnarray}$$
is a higher genus analogue of the set
${\mathcal{M}}_{q}\subseteq \mathbb{F}_{q}[T]$
: If
$K=\mathbb{F}_{q}(T)$
and
$\mathfrak{Q}$
is the prime at
$1/T$
, then the map
${\mathcal{M}}_{q}\rightarrow \text{Div}_{0,\mathfrak{Q}}(K)$
given by
$f\mapsto \text{div}(f)$
is a bijection. Similarly, the function
$\deg _{\mathfrak{Q}}:\text{Div}_{0,\mathfrak{Q}}(K)\rightarrow \mathbb{Z}$
given by
$$\begin{eqnarray}\deg _{\mathfrak{Q}}\biggl(\mathop{\sum }_{\mathfrak{P}}n_{\mathfrak{P}}\cdot \mathfrak{P}\biggr)=\mathop{\sum }_{\mathfrak{P}:n_{\mathfrak{P}}<0}(-n_{\mathfrak{P}})\cdot \deg \mathfrak{P}=-n_{\mathfrak{Q}}\cdot \deg \mathfrak{Q}\end{eqnarray}$$
is a higher genus analogue of a degree of a polynomial.
Given positive integers
$n\geqslant 1$
,
$\ell \geqslant 1$
,
$r\geqslant 2$
, we consider the following sets of divisors, which are analogues of
$S_{1}(q)$
,
$S_{2}(q)$
and
$S_{3}(q)$
:
$$\begin{eqnarray}\displaystyle S_{1}(r,K) & = & \displaystyle \biggl\{D\in \text{Div}_{0,\mathfrak{Q}}(K):v_{\mathfrak{P}}(D)>0\;\Longrightarrow \;\frac{r}{\gcd (r,\deg _{K}\mathfrak{P})}\bigg|v_{\mathfrak{P}}(D)\biggr\},\nonumber\\ \displaystyle & & \displaystyle\end{eqnarray}$$
$$\begin{eqnarray}\displaystyle S_{2}(r,K) & = & \displaystyle \{D\in \text{Div}_{0,\mathfrak{Q}}(K):v_{\mathfrak{P}}(D)>0\;\Longrightarrow \;r\mid \deg _{K}\mathfrak{P}\},\end{eqnarray}$$
$$\begin{eqnarray}\displaystyle S_{3}(r,\ell ,K) & = & \displaystyle \{\!D\in \text{Div}_{0,\mathfrak{Q}}(K):v_{\mathfrak{P}}(D)>0\nonumber\\ \displaystyle & & \displaystyle \quad \;\Longrightarrow \;r\mid \deg _{K}\mathfrak{P}\text{ and }v_{\mathfrak{P}}(D)\leqslant \ell \!\}.\end{eqnarray}$$
We elaborate on the algebraic meaning of the sets
$S_{1}$
,
$S_{2}$
,
$S_{3}$
. Let
$K_{r}$
be the fixed constant field extension over
$K$
of degree
$r$
. We have the following relation between primes of
$K_{r}$
and
$K$
.
Proposition 2.2 [Reference Rosen18, Proposition 8.13].
Let
$\mathfrak{P}$
be a prime of
$K$
. Then
$\mathfrak{P}$
splits into
$\gcd (r,\deg _{K}\mathfrak{P})$
primes in
$K_{r}$
. Let
$\mathfrak{P}_{r}$
be a prime of
$K_{r}$
lying over
$\mathfrak{P}$
. Denote by
$f(\mathfrak{P}_{r}/\mathfrak{P})$
the relative degree of
$\mathfrak{P}_{r}$
over
$\mathfrak{P}$
. Then
$$\begin{eqnarray}\deg _{K_{r}}\mathfrak{P}_{r}=\frac{\deg _{K}\mathfrak{P}}{\gcd (r,\deg _{K}\mathfrak{P})},\qquad f(\mathfrak{P}_{r}/\mathfrak{P})=\frac{r}{\gcd (r,\deg _{K}\mathfrak{P})}.\end{eqnarray}$$
In particular, primes of
$K$
of degree divisible by
$r$
are exactly those that split completely in
$K_{r}$
, which gives an algebraic meaning to
$S_{2}$
and
$S_{3}$
. We may define the (linear) norm map [Reference Chevalley4, Ch. IV.7]
$$\begin{eqnarray}N_{K_{r}/K}:\text{Div}(K_{r})\rightarrow \text{Div}(K)\end{eqnarray}$$
by
$$\begin{eqnarray}\mathfrak{P}_{r}\mapsto f(\mathfrak{P}_{r}/\mathfrak{P})\cdot \mathfrak{P},\end{eqnarray}$$
where
$\mathfrak{P}_{r}$
is a prime of
$K_{r}$
lying over
$\mathfrak{P}$
, a prime of
$K$
. By Proposition 2.2, the image of
$N_{K_{r}/K}$
is spanned by
$$\begin{eqnarray}\biggl\{\frac{r}{\gcd (r,\deg _{K}\mathfrak{P})}\mathfrak{P}:\mathfrak{P}\in \mathbb{P}_{K}\biggr\}.\end{eqnarray}$$
Intersecting the image
$N_{K_{r}/K}(K_{r})$
with
$\text{Div}_{0,\mathfrak{Q}}(K)$
, we recover the set
$S_{1}(r,K)$
. When
$r=2$
,
$K=\mathbb{F}_{q}(T)$
and
$\mathfrak{Q}$
is the prime at
$1/T$
, we obtain
$S_{1}(r,K)=S_{1}(q)$
. Hence, counting divisors of
$S_{1}(r,K)$
is a generalization of Landau’s problem over
$\mathbb{F}_{q}[T]$
. The asymptotics of
$$\begin{eqnarray}B_{i}(rn,r,K)=\#\{D\in S_{i}(r,K):\deg _{\mathfrak{Q}}(D)=rn\}\quad (i=1,2)\end{eqnarray}$$
and
$$\begin{eqnarray}B_{3}(rn,r,\ell ,K)=\#\{D\in S_{3}(r,\ell ,K):\deg _{\mathfrak{Q}}(D)=rn\}\end{eqnarray}$$
in a very general range of parameters are given in the following theorem.
Theorem 2.3. Let
$K$
be a function field with constant field
$\mathbb{F}_{q}$
. Fix a prime
$\mathfrak{Q}$
of
$K$
. Let
$g_{K}$
be the genus of
$K$
, and define
$$\begin{eqnarray}M_{K,\mathfrak{Q}}=\max \{g_{K},\deg \mathfrak{Q}\}.\end{eqnarray}$$
Let
$n\geqslant 1$
,
$\ell \geqslant 1$
,
$r\geqslant 2$
be given integers. If
$\deg _{K}\mathfrak{Q}\nmid rn$
, we have
$$\begin{eqnarray}B_{1}(rn,r,K)=B_{2}(rn,r,K)=B_{3}(rn,r,\ell ,K)=0.\end{eqnarray}$$
Otherwise, we have
$$\begin{eqnarray}\displaystyle B_{1}(rn,r,K) & = & \displaystyle \binom{n+\displaystyle \frac{1}{r}-1}{n}\cdot q^{rn}\nonumber\\ \displaystyle & & \displaystyle \cdot \,\biggl(C_{1,r,K}+O\biggl(\frac{\exp (150(M_{K,\mathfrak{Q}}/rq^{r/2}))(M_{K,\mathfrak{Q}}/rq^{r/2})}{n}\biggr)\biggr),\nonumber\\ \displaystyle & & \displaystyle\end{eqnarray}$$
$$\begin{eqnarray}\displaystyle B_{2}(rn,r,K) & = & \displaystyle \binom{n+\displaystyle \frac{1}{r}-1}{n}\cdot q^{rn}\nonumber\\ \displaystyle & & \displaystyle \cdot \,\biggl(C_{2,r,K}+O\biggl(\frac{\exp (150(M_{K,\mathfrak{Q}}/rq^{r/2}))(M_{K,\mathfrak{Q}}/rq^{r/2})}{n}\biggr)\biggr),\nonumber\\ \displaystyle & & \displaystyle\end{eqnarray}$$
$$\begin{eqnarray}\displaystyle B_{3}(rn,r,\ell ,K) & = & \displaystyle \binom{n+\displaystyle \frac{1}{r}-1}{n}\cdot q^{rn}\nonumber\\ \displaystyle & & \displaystyle \cdot \,\biggl(C_{r,\ell ,K}+O\biggl(\frac{\exp (150(M_{K,\mathfrak{Q}}/rq^{r/2}))(M_{K,\mathfrak{Q}}/rq^{r/2})}{n}\biggr)\biggr),\nonumber\\ \displaystyle & & \displaystyle\end{eqnarray}$$
as long as
$$\begin{eqnarray}n\gg 1+\frac{M_{K,\mathfrak{Q}}}{r^{2}\ln (q)}\ln \biggl(\frac{M_{K,\mathfrak{Q}}}{r^{2}\ln (q)}+1\biggr).\end{eqnarray}$$
In addition, the constants
$C_{1,r,K},C_{2,r,K},C_{r,\ell ,K}$
may be estimated by
$$\begin{eqnarray}C_{1,r,K},C_{2,r,K},C_{r,\ell ,K}=\exp \biggl(O\biggl(\frac{M_{K,\mathfrak{Q}}}{rq^{r/2}}\biggr)\biggr).\end{eqnarray}$$
A variant of the functions
$B_{2}(rn,r,K)$
,
$B_{3}(rn,r,\ell ,K)$
, where a prime
$\mathfrak{Q}$
was not included in the definition, was studied in [Reference Chuang, Kuan and Yu5, Theorem 4]. The results obtained there are meaningful only in the limit
$n\rightarrow \infty$
.
We also investigate the constants
$C_{1,r,K}$
,
$C_{2,r,K}$
,
$C_{r,\ell ,K}$
and provide an expression for them, involving an infinite product over primes of
$\mathbb{P}_{K}$
.
Remark 2.4. In the limit
$n\rightarrow \infty$
, the expression
$\binom{n+1/r-1}{n}$
appearing in Theorem 2.3 may be replaced with
$(n^{1/r-1}/\unicode[STIX]{x1D6E4}(1/r))(1+O(1/rn))$
: by [Reference Jameson10, equation 14],
$$\begin{eqnarray}\begin{array}{@{}rcl@{}}\displaystyle \binom{n+\displaystyle \frac{1}{r}-1}{n}\ & {\leqslant}\ & \displaystyle \frac{n^{1/r-1}}{\unicode[STIX]{x1D6E4}(1/r)},\quad \text{and}\\ \displaystyle \binom{n+\displaystyle \frac{1}{r}-1}{n}\ & {\geqslant}\ & \displaystyle \frac{(n+1/r)^{1/r-1}}{\unicode[STIX]{x1D6E4}(1/r)}=\frac{n^{1/r-1}}{\unicode[STIX]{x1D6E4}(1/r)}\biggl(1+\frac{1}{rn}\biggr)^{1/r-1}\\ \ & {\geqslant}\ & \displaystyle \frac{n^{1/r-1}}{\unicode[STIX]{x1D6E4}(1/r)}\biggl(1+\frac{1}{rn}\biggr)^{-1}\geqslant \frac{n^{1/r-1}}{\unicode[STIX]{x1D6E4}(1/r)}\biggl(1-\frac{1}{rn}\biggr).\end{array}\end{eqnarray}$$
2.3 Prime factors in an arithmetic progression
Let
$a,m\in \mathbb{F}_{q}[T]$
be a pair of coprime polynomials with
$m$
monic of positive degree. Let
$G_{a,m}\subseteq \mathbb{F}_{q}[T]$
be the set of monic polynomials whose monic prime factors are in the arithmetic progression
$a(T)\,\text{mod}\,m(T)$
. Let
$$\begin{eqnarray}S(n;a,m)=\#\{f\in G_{a,m}:\deg (f)=n\},\end{eqnarray}$$
be the number of polynomials of degree
$n$
in the semigroup
$G_{a,m}$
. What bounds are satisfied by
$S(n;a,m)$
?
Although studying
$S(n;a,m)$
is interesting for its own sake, the case
$a=1$
is an important ingredient in the proof of the following theorem of Thorne [Reference Thorne22, Theorem 1.2], which is a function field analogue of a theorem of Shiu [Reference Shiu20, Theorem 1].
Theorem 2.5 (Thorne).
Let
$a,m\in \mathbb{F}_{q}[T]$
with
$\gcd (a,m)=1$
and
$\deg m\,>\,0$
,
$m$
monic. There exists a constant
$D^{\prime }$
(depending on
$q$
and
$m$
) such that for any
$D>D^{\prime }$
there exists a string of consecutive monic primes
$$\begin{eqnarray}p_{r+1}\equiv p_{r+2}\cdots \equiv p_{r+k}\equiv a\hspace{0.2em}{\rm mod}\hspace{0.2em}m\end{eqnarray}$$
of degree at most
$D$
, where
$k$
satisfies
$$\begin{eqnarray}k\gg _{q}\frac{1}{\unicode[STIX]{x1D719}(m)}\biggl(\frac{\log D}{(\log \log D)^{2}}\biggr)^{1/\unicode[STIX]{x1D719}(m)}.\end{eqnarray}$$
Here “consecutive” is to be understood with respect to lexicographic order. Thorne’s proof uses the following asymptotic formula, corollary of a result of Manstavičius and Skrabutėnas [Reference Manstavičius and Skrabutėnas16, Theorem 1]:
$$\begin{eqnarray}\displaystyle S(n;1,m)\sim C_{1,m}\cdot \frac{n^{-1+1/\unicode[STIX]{x1D719}(m)}}{\unicode[STIX]{x1D6E4}(1/\unicode[STIX]{x1D719}(m))}\cdot q^{n},\quad n\rightarrow \infty , & & \displaystyle\end{eqnarray}$$
where
$$\begin{eqnarray}\displaystyle C_{a,m} & = & \displaystyle \lim _{u\rightarrow 1/q^{-}}(1-qu)^{1/\unicode[STIX]{x1D719}(m)}\mathop{\prod }_{P\in {\mathcal{P}}_{q}:P\equiv a\,\text{mod}\,m}(1-u^{\deg P})^{-1}.\end{eqnarray}$$
As remarked after [Reference Thorne22, Lemma 3.5], making (2.36) effective allows one to determine the constant
$D^{\prime }$
appearing in Theorem 2.5. We establish the following version of (2.36).
Theorem 2.6. Let
$a,m\in \mathbb{F}_{q}[T]$
be a pair of coprime polynomials with
$\deg m>0$
and
$m$
monic. For
$$\begin{eqnarray}n\geqslant 1+5(6\deg m+30)\ln (6\deg m+30),\end{eqnarray}$$
we have
$$\begin{eqnarray}\displaystyle S(n;a,m) & = & \displaystyle \binom{n+\displaystyle \frac{1}{\unicode[STIX]{x1D719}(m)}-1}{n}\cdot q^{n}\nonumber\\ \displaystyle & & \displaystyle \cdot \,\biggl(C_{a,m}+O\biggl(\frac{\exp (3(\deg m+3)/\sqrt{q})((\deg m+3)/\sqrt{q})}{n}\biggr)\biggr),\nonumber\\ \displaystyle & & \displaystyle\end{eqnarray}$$
where the implied constant is (at most)
$48$
.
3 Methods
Let
$q$
be a prime power, and let
$\mathbb{F}_{q}[T]$
be the polynomial ring over the finite field
$\mathbb{F}_{q}$
. Denote by
$\unicode[STIX]{x1D70B}_{q}(n)$
the number of irreducible monic polynomials in
$\mathbb{F}_{q}[T]$
of degree
$n$
.
Let
$G\subseteq \mathbb{F}_{q}[T]$
be a multiplicative semigroup generated by (possibly infinitely many) mutually coprime monic polynomials. Let
$g(n)$
be the number of generators of degree
$n$
. The coefficients of the generating function
$$\begin{eqnarray}\displaystyle F_{G}(x) & := & \displaystyle \mathop{\prod }_{n\geqslant 1}(1+x^{n}+x^{2n}+\cdots \,)^{g(n)}\nonumber\\ \displaystyle & = & \displaystyle \mathop{\prod }_{n\geqslant 1}(1-x^{n})^{-g(n)}\end{eqnarray}$$
count how many polynomials in
$G$
are of a specified degree. By writing
$F_{G}(x)=\exp (\ln F_{G}(x))$
, we may express
$F_{G}(x)$
as the formal power series
$$\begin{eqnarray}\exp \biggl(\mathop{\sum }_{n\geqslant 1}\frac{\unicode[STIX]{x1D713}_{G}(n)x^{n}}{n}\biggr),\end{eqnarray}$$
where
$$\begin{eqnarray}\unicode[STIX]{x1D713}_{G}(n):=\mathop{\sum }_{d\mid n}d\cdot g(d).\end{eqnarray}$$
For instance, when
$G={\mathcal{M}}_{q}\subseteq \mathbb{F}_{q}[T]$
is the semigroup of monic polynomials, generated by monic irreducible polynomials, the corresponding function
$\unicode[STIX]{x1D713}_{{\mathcal{M}}_{q}}$
is the weighted prime-counting function
$\unicode[STIX]{x1D713}_{{\mathcal{M}}_{q}}(n)=\sum _{d\mid n}d\cdot \unicode[STIX]{x1D70B}_{q}(d)$
, which satisfies [Reference Rosen18, Proposition 2.1]
$$\begin{eqnarray}\unicode[STIX]{x1D713}_{{\mathcal{M}}_{q}}(n)=\mathop{\sum }_{d\mid n}d\cdot \unicode[STIX]{x1D70B}_{q}(d)=q^{n}.\end{eqnarray}$$
It turns out that for many semigroups that occur in counting problems,
$\unicode[STIX]{x1D713}_{G}$
satisfies the following bound, where
$\unicode[STIX]{x1D6FC},\unicode[STIX]{x1D6FD},c_{1},c_{2}$
are some real numbers satisfying
$\unicode[STIX]{x1D6FC}>\unicode[STIX]{x1D6FD}>0$
:
$$\begin{eqnarray}\displaystyle |\unicode[STIX]{x1D713}_{G}(n)-c_{1}\unicode[STIX]{x1D6FD}^{-n}|\leqslant c_{2}\unicode[STIX]{x1D6FC}^{-n}. & & \displaystyle\end{eqnarray}$$
The bound (3.5) insures that we can write
$F_{G}$
as a product of two analytic functions, with radii of convergence at most
$\unicode[STIX]{x1D6FC}$
and exactly
$\unicode[STIX]{x1D6FD}$
, respectively:
$$\begin{eqnarray}\displaystyle F_{G}(x) & = & \displaystyle \exp \biggl(\mathop{\sum }_{n\geqslant 1}\frac{e_{n}x^{n}}{n}\biggr)\cdot \exp \biggl(\mathop{\sum }_{n\geqslant 1}\frac{c_{1}\unicode[STIX]{x1D6FD}^{-n}x^{n}}{n}\biggr)\nonumber\\ \displaystyle & = & \displaystyle \exp \biggl(\mathop{\sum }_{n\geqslant 1}\frac{e_{n}x^{n}}{n}\biggr)\cdot \biggl(1-\frac{x}{\unicode[STIX]{x1D6FD}}\biggr)^{-c_{1}},\end{eqnarray}$$
where
$$\begin{eqnarray}e_{n}=\unicode[STIX]{x1D713}_{G}(n)-c_{1}\unicode[STIX]{x1D6FD}^{-n}.\end{eqnarray}$$
In particular, the radii of convergence are distinct.
The problem of estimating the coefficients of a product of two functions with different radii of convergence has been studied previously. First, we introduce a useful piece of notation. For a power series
$f(x)=\sum _{i\geqslant 0}f_{i}x^{i}$
,
$[x^{n}]f(x)$
denotes the coefficient of
$x^{n}$
in
$f$
, i.e.
$f_{n}$
.
We mention two classical results. The first is [Reference Flajolet and Sedgewick6, Theorem VI.12].
Theorem 3.1. Let
$a(x)=\sum a_{n}x^{n}$
and
$b(x)=\sum b_{n}x^{n}$
be two power series with radii of convergence
$\unicode[STIX]{x1D6FC}>\unicode[STIX]{x1D6FD}\geqslant 0$
, respectively. Assume that
$b_{n-1}/b_{n}\rightarrow \unicode[STIX]{x1D6FD}$
as
$n$
tends to
$\infty$
, and that
$a(\unicode[STIX]{x1D6FD})\neq 0$
. Then the coefficients of the product
$f(x)=a(x)\cdot b(x)$
satisfy the following, as
$n$
tends to
$\infty$
:
$$\begin{eqnarray}[x^{n}]f(x)\sim a(\unicode[STIX]{x1D6FD})\cdot b_{n}.\end{eqnarray}$$
Theorem 3.1 is proved using calculus. Applying Theorem 3.1, we solve the problem of estimating
$[x^{n}]F_{G}(x)$
as
$n$
tends to
$\infty$
and
$q$
is fixed, under assumption (3.5):
$$\begin{eqnarray}\displaystyle [x^{n}]F_{G}(x) & {\sim} & \displaystyle \exp \biggl(\mathop{\sum }_{n\geqslant 1}\frac{e_{n}\unicode[STIX]{x1D6FD}^{n}}{n}\biggr)\cdot \binom{-c_{1}}{n}\cdot \biggl(-\frac{1}{\unicode[STIX]{x1D6FD}}\biggr)^{n}\nonumber\\ \displaystyle & = & \displaystyle \exp \biggl(\mathop{\sum }_{n\geqslant 1}\frac{e_{n}\unicode[STIX]{x1D6FD}^{n}}{n}\biggr)\cdot \binom{n+c_{1}-1}{n}\cdot \unicode[STIX]{x1D6FD}^{-n}.\end{eqnarray}$$
Theorem 3.1 does not give information on the rate of convergence. A method, due to Darboux, gives a more informative estimate for certain
$b$
(see [Reference Henrici9, Theorem 11.10b]).
Theorem 3.2. Let
$a(x)=\sum a_{n}x^{n}$
and
$b(x)=(1-x/\unicode[STIX]{x1D6FD})^{-c_{1}}=\sum b_{n}x^{n}$
$(c_{1}\in \mathbb{C}\setminus \mathbb{Z})$
be two power series with radii of convergence
$\unicode[STIX]{x1D6FC}>\unicode[STIX]{x1D6FD}\geqslant 0$
, respectively. Fix an integer
$m\geqslant 0$
. Then the coefficients of the product
$f(x)=a(x)\cdot b(x)$
satisfy the following, as
$n$
tends to
$\infty$
:
$$\begin{eqnarray}\displaystyle [x^{n}]f(x)=b_{n}\cdot \left(a(\unicode[STIX]{x1D6FD})+\mathop{\sum }_{k=1}^{m}\frac{\binom{k-c_{1}}{k}}{\binom{n+c_{1}-1}{k}}\frac{\unicode[STIX]{x1D6FD}^{k}}{k!}a^{(k)}(\unicode[STIX]{x1D6FD})+O_{a,b,m}\biggl(\frac{1}{n^{m+1}}\biggr)\right). & & \displaystyle\end{eqnarray}$$
Most proofs of Theorem 3.2 use contour integration, although an elementary proof was found by Knuth and Wilf [Reference Knuth and Wilf13]. Using (3.6), Theorem 3.2 gives an asymptotic expansion of
$[x^{n}]F_{G}(x)$
, as
$n$
tends to
$\infty$
, in all of this paper’s applications.
Methods similar to Theorem 3.2 were used to study semigroup counting problems related to finite fields in the limit
$n\rightarrow \infty$
and
$q$
fixed, see the papers [Reference Manstavičius and Skrabutėnas16, Reference Warlimont24] and the monographs [Reference Knopfmacher11, Reference Knopfmacher and Zhang12].
Our objective is to establish results on the magnitude of
$[x^{n}]F_{G}(x)$
in the limit
$q^{n}\rightarrow \infty$
, for which Theorem 3.2 is not suitable. To do so, we need to work out the dependency of the error term in (3.10) on the parameters
$a$
,
$b$
. This is done in the following theorem, under additional restrictions influenced by (3.5).
Theorem 3.3. Let
$a(x)=\exp (\sum _{n\geqslant 1}(\widetilde{a_{n}}x^{n}/n))=\sum a_{n}x^{n}$
and
$b(x)=(1-x/\unicode[STIX]{x1D6FD})^{-c_{1}}=\sum b_{n}x^{n}$
$(c_{1}\in (0,1))$
be two power series, with radii of convergence at least
$\unicode[STIX]{x1D6FC}$
and exactly
$\unicode[STIX]{x1D6FD}$
, respectively. Assume that
$\unicode[STIX]{x1D6FC}>\unicode[STIX]{x1D6FD}>0$
. Assume that
$$\begin{eqnarray}r=\frac{\unicode[STIX]{x1D6FD}}{\unicode[STIX]{x1D6FC}}\leqslant \frac{1}{\sqrt{2}}.\end{eqnarray}$$
Further assume that there is a positive number
$c_{2}$
such that
$$\begin{eqnarray}\displaystyle |\widetilde{a_{n}}|\leqslant \frac{c_{2}}{\unicode[STIX]{x1D6FC}^{n}}. & & \displaystyle\end{eqnarray}$$
Fix an integer
$m\geqslant 0$
. For an integer
$n>m$
, write the
$n$
th coefficient
$f_{n}$
of
$f(x)=a(x)\cdot b(x)$
as
$$\begin{eqnarray}[x^{n}]f(x)=b_{n}\cdot \left(a(\unicode[STIX]{x1D6FD})+\mathop{\sum }_{k=1}^{m}\frac{\binom{k-c_{1}}{k}}{\binom{n+c_{1}-1}{k}}\frac{\unicode[STIX]{x1D6FD}^{k}}{k!}a^{(k)}(\unicode[STIX]{x1D6FD})+E\right).\end{eqnarray}$$
Then
$$\begin{eqnarray}\displaystyle & & \displaystyle |E|~\ll _{m}~\exp (3c_{2}r)\biggl(\biggl(\frac{r}{n}\biggr)^{m+1}(c_{2}+m)_{m+1}+\binom{n+c_{2}-1}{n}\frac{4n^{2}}{c_{1}}r^{n}\biggr)\end{eqnarray}$$
$$\begin{eqnarray}\displaystyle & & \displaystyle \ll _{m,c_{1},c_{2}}~\biggl(\frac{r}{n}\biggr)^{m+1},\end{eqnarray}$$
where
$(x)_{n}:=x(x-1)\cdots (x-(n-1))$
is the falling factorial. For
$m=0$
, the implicit constant in (3.14) is (at most)
$24$
.
We also establish the following effective corollary.
Corollary 3.4. Let
$a$
,
$b$
,
$\unicode[STIX]{x1D6FC}$
and
$\unicode[STIX]{x1D6FD}$
be as in Theorem 3.3, and assume that they satisfy (3.11) and (3.12). Let
$f(x)=a(x)\cdot b(x)$
. For
$n$
large enough, specifically
$$\begin{eqnarray}n\geqslant \max \biggl\{5\biggl(\frac{2c_{2}+4}{\ln (1/r)}+1\biggr)\ln \biggl(\frac{2c_{2}+4}{\ln (1/r)}+1\biggr)+1,2\frac{\ln (c_{1}^{-1})}{\ln (1/r)}+1\biggr\},\end{eqnarray}$$
we have
$$\begin{eqnarray}[x^{n}]f(x)=b_{n}\cdot \biggl(a(\unicode[STIX]{x1D6FD})+O\biggl(\frac{\exp (3c_{2}r)c_{2}r}{n}\biggr)\biggr),\end{eqnarray}$$
where the implied constant is (at most)
$48$
.
Remark 3.5. In all of our applications, the Riemann hypothesis for function fields shows that
$\unicode[STIX]{x1D6FD}^{-1}$
is of the form
$q^{c}$
for some positive integer
$c$
depending on the application and
$\unicode[STIX]{x1D6FC}^{-1}$
is the square root of
$\unicode[STIX]{x1D6FD}^{-1}$
. Thus,
$r=\unicode[STIX]{x1D6FD}/\unicode[STIX]{x1D6FC}=q^{-c/2}$
, which has two implications. First, equation (3.11) is satisfied. Second,
$$\begin{eqnarray}\lim _{q\rightarrow \infty }\frac{r}{n}=0,\end{eqnarray}$$
which by (3.15) shows that as
$q$
tends to
$\infty$
, the relative error term
$E$
tends to zero.
Remark 3.6. Assumption (3.12) implies that
$$\begin{eqnarray}\begin{array}{@{}rcl@{}}\displaystyle |a(\unicode[STIX]{x1D6FD})|\ & {\geqslant}\ & \exp \biggl(\mathop{\sum }_{n\geqslant 1}\frac{-|\widetilde{a_{n}}|\unicode[STIX]{x1D6FD}^{n}}{n}\biggr)\geqslant \exp \biggl(\mathop{\sum }_{n\geqslant 1}\frac{-c_{2}r^{n}}{n}\biggr)=(1-r)^{c_{2}},\\ \displaystyle |a(\unicode[STIX]{x1D6FD})|\ & {\leqslant}\ & \exp \biggl(\mathop{\sum }_{n\geqslant 1}\frac{|\widetilde{a_{n}}|\unicode[STIX]{x1D6FD}^{n}}{n}\biggr)\leqslant \exp \biggl(\mathop{\sum }_{n\geqslant 1}\frac{c_{2}r^{n}}{n}\biggr)=(1-r)^{-c_{2}}.\end{array}\end{eqnarray}$$
In particular, we obtain the bound
$a(\unicode[STIX]{x1D6FD})=\exp (O(c_{2}r))$
.
4 Landau’s theorem over
$\mathbb{F}_{q}[T]$
, for
$A^{2}+TB^{2}$
We begin with an overlook of the proof of Theorem 1.1, leaving the more technical details to §4.1. Let
$G_{q}\subseteq \mathbb{F}_{q}[T]$
be the set of monic polynomials of the form
$A^{2}+TB^{2}$
. By [Reference Bary-Soroker, Smilansky and Wolf3, Theorem 2.5], a monic irreducible polynomial
$f$
is in
$G_{q}$
if and only if the multiplicity of any monic irreducible polynomial
$P$
of the form
$(P/T)=-1$
in the factorization of
$f$
is even. In other words,
$G_{q}$
is the semigroup generated by the following set of mutually coprime polynomials:
$$\begin{eqnarray}\displaystyle & & \displaystyle \biggl\{P\in \mathbb{F}_{q}[T]:P\text{ is monic irreducible satisfying }\biggl(\frac{P}{T}\biggr)=1\biggr\}\nonumber\\ \displaystyle & & \displaystyle \qquad \bigcup \biggl\{P^{2}:P\in \mathbb{F}_{q}[T]\text{ is monic irreducible satisfying }\biggl(\frac{P}{T}\biggr)=-1\biggr\}\bigcup \{T\}.\nonumber\\ \displaystyle & & \displaystyle\end{eqnarray}$$
Let
$\unicode[STIX]{x1D712}_{2}:\mathbb{F}_{q}[T]\rightarrow \mathbb{C}$
denote the quadratic character modulo
$T$
:
$$\begin{eqnarray}\unicode[STIX]{x1D712}_{2}(f)=\biggl(\frac{f}{T}\biggr).\end{eqnarray}$$
For any subset
$S\subseteq \{-1,0,1\}$
, let
$\unicode[STIX]{x1D70B}_{q}(n;\unicode[STIX]{x1D712}_{2},S)$
count the monic irreducible polynomials
$P$
of degree
$n$
in
$\mathbb{F}_{q}[T]$
such that
$\unicode[STIX]{x1D712}_{2}(f)\in S$
. For
$s\in \{-1,0,1\}$
, we write
$\unicode[STIX]{x1D70B}_{q}(n;\unicode[STIX]{x1D712}_{2},s)$
for
$\unicode[STIX]{x1D70B}_{q}(n;\unicode[STIX]{x1D712}_{2},\{s\})$
. It follows that the generating function
$F_{G_{q}}$
of
$B(n,q)$
is
$$\begin{eqnarray}\displaystyle F_{G_{q}}(x) & = & \displaystyle \mathop{\sum }_{n\geqslant 0}B(n,q)x^{n}\nonumber\\ \displaystyle & = & \displaystyle \mathop{\prod }_{n\geqslant 1}(1-x^{n})^{-\unicode[STIX]{x1D70B}_{q}(n;\unicode[STIX]{x1D712}_{2},\{0,1\})}(1-x^{2n})^{-\unicode[STIX]{x1D70B}_{q}(n;\unicode[STIX]{x1D712}_{2},-1)}.\end{eqnarray}$$
If we set
$$\begin{eqnarray}g(n)=\left\{\begin{array}{@{}ll@{}}\unicode[STIX]{x1D70B}_{q}(n;\unicode[STIX]{x1D712}_{2},\{0,1\})\quad & 2\nmid n,\\ \displaystyle \unicode[STIX]{x1D70B}_{q}(n;\unicode[STIX]{x1D712}_{2},\{0,1\})+\unicode[STIX]{x1D70B}_{q}\biggl(\frac{n}{2};\unicode[STIX]{x1D712}_{2},-1\biggr)\quad & 2\mid n,\end{array}\right.\end{eqnarray}$$
then
$F_{G_{q}}$
assumes the form
$$\begin{eqnarray}F_{G_{q}}(x)=\mathop{\prod }_{n\geqslant 1}(1-x^{n})^{-g(n)}.\end{eqnarray}$$
As before, one sees that
$$\begin{eqnarray}F_{G_{q}}(x)=\exp \biggl(\mathop{\sum }_{n\geqslant 1}\frac{\unicode[STIX]{x1D713}_{G_{q}}(n)x^{n}}{n}\biggr),\end{eqnarray}$$
where
$$\begin{eqnarray}\unicode[STIX]{x1D713}_{G_{q}}(n)=\mathop{\sum }_{d\mid n}d\cdot g(d).\end{eqnarray}$$
In §4.1 we obtain a closed-form expression for
$\unicode[STIX]{x1D713}_{G_{q}}(n)$
. In particular, we find that
$$\begin{eqnarray}e_{n}=\unicode[STIX]{x1D713}_{G_{q}}(n)-\frac{q^{n}}{2}\end{eqnarray}$$
satisfies
$$\begin{eqnarray}e_{n}=O(q^{\lfloor n/2\rfloor }),\end{eqnarray}$$
and, as we saw in (3.6), we may write
$F_{G_{q}}$
as a product of two power series with distinct radii of convergence:
$$\begin{eqnarray}F_{G_{q}}(x)=\exp \biggl(\mathop{\sum }_{n\geqslant 1}\frac{e_{n}x^{n}}{n}\biggr)\cdot (1-qx)^{-1/2}.\end{eqnarray}$$
Theorem 3.3 with
$$\begin{eqnarray}a(x)=\exp \biggl(\mathop{\sum }_{n\geqslant 1}\frac{e_{n}x^{n}}{n}\biggr),\qquad b(x)=(1-qx)^{-1/2}\end{eqnarray}$$
gives the asymptotics of
$B(n,q)$
.
4.1 Proof of Theorem 1.1
First, we obtain an explicit formula for
$e_{n}$
. We write the (formal) zeta function of
$\mathbb{F}_{q}[T]$
and its Euler product:
$$\begin{eqnarray}\displaystyle {\mathcal{Z}}_{\mathbb{F}_{q}[T]}(u) & = & \displaystyle \mathop{\sum }_{f\in {\mathcal{M}}_{q}}u^{\deg f}=(1-qu)^{-1}\nonumber\\ \displaystyle & = & \displaystyle \mathop{\prod }_{P\in {\mathcal{P}}_{q}}(1-u^{\deg P})^{-1}=\mathop{\prod }_{n\geqslant 1}(1-u^{n})^{-\unicode[STIX]{x1D70B}_{q}(n)}.\end{eqnarray}$$
We have
$\unicode[STIX]{x1D70B}_{q}(n)=\unicode[STIX]{x1D70B}_{q}(n;\unicode[STIX]{x1D712}_{2},\{0,1\})+\unicode[STIX]{x1D70B}_{q}(n;\unicode[STIX]{x1D712}_{2},-1)$
, and so logarithmic differentiation of (4.12) gives
$$\begin{eqnarray}q^{n}=\mathop{\sum }_{d\mid n}d\cdot (\unicode[STIX]{x1D70B}_{q}(d;\unicode[STIX]{x1D712}_{2},\{0,1\})+\unicode[STIX]{x1D70B}_{q}(d;\unicode[STIX]{x1D712}_{2},-1)).\end{eqnarray}$$
We consider the (formal) L-function of the quadratic character
$\unicode[STIX]{x1D712}_{2}$
:
$$\begin{eqnarray}{\mathcal{L}}_{\mathbb{F}_{q}[T]}(u,\unicode[STIX]{x1D712}_{2})=\mathop{\sum }_{f\in {\mathcal{M}}_{q}}\unicode[STIX]{x1D712}_{2}(f)u^{\deg f}.\end{eqnarray}$$
On the one hand,
${\mathcal{L}}_{\mathbb{F}_{q}[T]}(u,\unicode[STIX]{x1D712}_{2})$
is actually the constant polynomial
$1$
, as half of the elements of
$\mathbb{F}_{q}^{\times }$
are squares and half are non-squares (cf. [Reference Rosen18, Proposition 4.3]):
$$\begin{eqnarray}{\mathcal{L}}_{\mathbb{F}_{q}[T]}(u,\unicode[STIX]{x1D712}_{2})=1.\end{eqnarray}$$
On the other hand, since
$\unicode[STIX]{x1D712}_{2}$
is completely multiplicative,
${\mathcal{L}}_{\mathbb{F}_{q}[T]}(u,\unicode[STIX]{x1D712}_{2})$
admits the following Euler product:
$$\begin{eqnarray}\displaystyle {\mathcal{L}}_{\mathbb{F}_{q}[T]}(u,\unicode[STIX]{x1D712}_{2}) & = & \displaystyle \mathop{\prod }_{P\in {\mathcal{P}}_{q}:\unicode[STIX]{x1D712}_{2}(P)=1}(1-u^{\deg P})^{-1}\mathop{\prod }_{P\in {\mathcal{P}}_{q}:\unicode[STIX]{x1D712}_{2}(P)=-1}(1+u^{\deg P})^{-1}\nonumber\\ \displaystyle & = & \displaystyle \mathop{\prod }_{n\geqslant 1}(1-u^{n})^{-\unicode[STIX]{x1D70B}_{q}(n;\unicode[STIX]{x1D712}_{2},1)}\mathop{\prod }_{n\geqslant 1}(1+u^{n})^{-\unicode[STIX]{x1D70B}_{q}(n;\unicode[STIX]{x1D712}_{2},-1)}\nonumber\\ \displaystyle & = & \displaystyle \mathop{\prod }_{n\geqslant 1}(1-u^{n})^{-\unicode[STIX]{x1D70B}_{q}(n;\unicode[STIX]{x1D712}_{2},\{0,1\})}\mathop{\prod }_{n\geqslant 1}(1+u^{n})^{-\unicode[STIX]{x1D70B}_{q}(n;\unicode[STIX]{x1D712}_{2},-1)}\cdot (1-u).\nonumber\\ \displaystyle & & \displaystyle\end{eqnarray}$$
Comparing (4.15) and (4.16), we have the following identity:
$$\begin{eqnarray}\frac{1}{1-u}=\mathop{\prod }_{n\geqslant 1}(1-u^{n})^{-\unicode[STIX]{x1D70B}_{q}(n;\unicode[STIX]{x1D712}_{2},\{0,1\})}\mathop{\prod }_{n\geqslant 1}(1+u^{n})^{-\unicode[STIX]{x1D70B}_{q}(n;\unicode[STIX]{x1D712}_{2},-1)}.\end{eqnarray}$$
We take the logarithmic derivative of (4.17), and obtain the following by comparing coefficients:
$$\begin{eqnarray}1=\mathop{\sum }_{d\mid n}d\cdot (\unicode[STIX]{x1D70B}_{q}(d;\unicode[STIX]{x1D712}_{2},\{0,1\})+\unicode[STIX]{x1D70B}_{q}(d;\unicode[STIX]{x1D712}_{2},-1)(-1)^{n/d}).\end{eqnarray}$$
Using (4.13), we simplify (4.18):
$$\begin{eqnarray}\mathop{\sum }_{d\mid n,2d\nmid n}d\cdot \unicode[STIX]{x1D70B}_{q}(d;\unicode[STIX]{x1D712}_{2},-1)=\frac{q^{n}-1}{2}.\end{eqnarray}$$
Let
$v_{2}(n)$
be the exponent of the greatest power of two that divides
$n$
. To compute
$\sum _{d\mid n}d\cdot \unicode[STIX]{x1D70B}_{q}(d;\unicode[STIX]{x1D712}_{2},-1)$
, we plug
$n,n/2,\ldots ,n/2^{v_{2}(n)}$
for
$n$
in (4.19) and sum:
$$\begin{eqnarray}\mathop{\sum }_{d\mid n}d\cdot \unicode[STIX]{x1D70B}_{q}(d;\unicode[STIX]{x1D712}_{2},-1)=\mathop{\sum }_{i=0}^{v_{2}(n)}\frac{q^{n/2^{i}}-1}{2}.\end{eqnarray}$$
Using (4.13) and (4.20), we find
$$\begin{eqnarray}\mathop{\sum }_{d\mid n}d\cdot \unicode[STIX]{x1D70B}_{q}(d;\unicode[STIX]{x1D712}_{2},\{0,1\})=\frac{q^{n}+1}{2}-\mathop{\sum }_{i=1}^{v_{2}(n)}\frac{q^{n/2^{i}}-1}{2}.\end{eqnarray}$$
Now we can calculate
$\sum _{d\mid n}d\cdot g(d)$
, using (4.4), (4.20) and (4.21):
$$\begin{eqnarray}\displaystyle \mathop{\sum }_{d\mid n}d\cdot g(d) & = & \displaystyle \mathop{\sum }_{d\mid n}d\cdot \unicode[STIX]{x1D70B}_{q}(d;\unicode[STIX]{x1D712}_{2},\{0,1\})+\mathop{\sum }_{2\mid d\mid n}d\cdot \unicode[STIX]{x1D70B}_{q}\left(\frac{d}{2};\unicode[STIX]{x1D712}_{2},-1\right)\nonumber\\ \displaystyle & = & \displaystyle \mathop{\sum }_{d\mid n}d\cdot \unicode[STIX]{x1D70B}_{q}(d;\unicode[STIX]{x1D712}_{2},\{0,1\})+2\mathop{\sum }_{2d^{\prime }\mid n}d^{\prime }\cdot \unicode[STIX]{x1D70B}_{q}(d^{\prime };\unicode[STIX]{x1D712}_{2},-1)\nonumber\\ \displaystyle & = & \displaystyle \frac{q^{n}+1}{2}-\mathop{\sum }_{i=1}^{v_{2}(n)}\frac{q^{n/2^{i}}-1}{2}+2\mathop{\sum }_{i=0}^{v_{2}(n/2)}\frac{q^{n/2^{i+1}}-1}{2}\nonumber\\ \displaystyle & = & \displaystyle \frac{q^{n}+1}{2}+\mathop{\sum }_{i=1}^{v_{2}(n)}\frac{q^{n/2^{i}}-1}{2}.\end{eqnarray}$$
By (4.22), the exact value of
$e_{n}$
, as defined in (4.8), is
$$\begin{eqnarray}e_{n}=\frac{1}{2}+\mathop{\sum }_{i=1}^{v_{2}(n)}\frac{q^{n/2^{i}}-1}{2}.\end{eqnarray}$$
In particular,
$e_{n}$
satisfies
$$\begin{eqnarray}{\textstyle \frac{1}{2}}\leqslant e_{n}\leqslant q^{\lfloor n/2\rfloor }.\end{eqnarray}$$
We establish Theorem 1.1 with
$$\begin{eqnarray}K_{q}=a(q^{-1}),\end{eqnarray}$$
and show that this is the same
$K_{q}$
defined in (1.8). For
$n=1$
, Theorem 1.1 is immediate since
$B(1,q)=(q+1)/2$
and, by (4.24),
$$\begin{eqnarray}\displaystyle K_{q} & = & \displaystyle a(q^{-1})=\exp \biggl(\mathop{\sum }_{n\geqslant 1}\frac{e_{n}\cdot q^{-n}}{n}\biggr)\nonumber\\ \displaystyle & = & \displaystyle \exp \biggl(\mathop{\sum }_{n\geqslant 1}\frac{O(q^{\lfloor n/2\rfloor -n})}{n}\biggr)=\exp \biggl(O\biggl(\frac{1}{q}\biggr)\biggr)=O(1),\end{eqnarray}$$
and so
$$\begin{eqnarray}B(1,q)=K_{q}\cdot \binom{1-\frac{1}{2}}{1}\cdot q+O(1),\end{eqnarray}$$
as needed. Now assume that
$n>1$
. We may use Theorem 3.3 with
$m=1$
and the functions
$a$
,
$b$
as defined in (4.11), which satisfy
$a\cdot b=F_{G_{q}}$
as we have seen in (4.10). By (4.24), the parameters for Theorem 3.3 are
$$\begin{eqnarray}c_{1}={\textstyle \frac{1}{2}},\qquad c_{2}=1,\qquad \unicode[STIX]{x1D6FC}=q^{-1/2},\qquad \unicode[STIX]{x1D6FD}=q^{-1}.\end{eqnarray}$$
We obtain the following estimate for
$B(n,q)$
:
$$\begin{eqnarray}\frac{B(n,q)}{\binom{n-1/2}{n}\cdot q^{n}}=a(q^{-1})+\frac{1}{2n-1}\frac{a^{\prime }(q^{-1})}{q}+O\biggl(\frac{1}{qn^{2}}\biggr).\end{eqnarray}$$
Theorem 1.1 follows once we show
$a^{\prime }(q^{-1})=O(1)$
. Note (4.24) implies that
$$\begin{eqnarray}\frac{a^{\prime }(q^{-1})}{a(q^{-1})}=\mathop{\sum }_{n\geqslant 1}e_{n}\cdot q^{1-n}=\mathop{\sum }_{n\geqslant 1}O(q^{1+\lfloor n/2\rfloor -n})=O(1).\end{eqnarray}$$
By (4.26) and (4.30),
$a^{\prime }(q^{-1})=O(1)$
is established, as needed. From (4.29) we see that
$\lim _{n\rightarrow \infty }\big(B(n,q)/(\binom{n-1/2}{n}\cdot q^{n})\big)=a(q^{-1})$
, while (1.7) implies that
$\lim _{n\rightarrow \infty }\big(B(n,q)/\big(\binom{n-1/2}{n}\cdot q^{n}\big)\big)$
equals the constant
$K_{q}$
defined in (1.8). Hence,
$K_{q}$
defined in (1.8) coincides with
$K_{q}$
defined in (4.25), as claimed.
Remark 4.1. We show that
$B(n,q)$
is a polynomial in
$q$
of degree
$n$
, and explain how to compute its first
$d$
coefficients. From (4.3) and (4.10), we obtain
$$\begin{eqnarray}\displaystyle B(n,q) & = & \displaystyle [x^{n}]\biggl((1-qx)^{-1/2}\cdot \exp \biggl(\mathop{\sum }_{j\geqslant 1}\frac{e_{j}x^{j}}{j}\biggr)\biggr)\nonumber\\ \displaystyle & = & \displaystyle \mathop{\sum }_{i=0}^{n}q^{n-i}\binom{n-i-\frac{1}{2}}{n-i}\cdot [x^{i}]\exp \biggl(\mathop{\sum }_{j\geqslant 1}\frac{e_{j}x^{j}}{j}\biggr).\end{eqnarray}$$
From (4.23) we see that
$e_{n}$
is a polynomial in
$q$
of degree
${\leqslant}\lfloor n/2\rfloor$
. Thus, the
$n$
th coefficient of
$$\begin{eqnarray}\exp \biggl(\mathop{\sum }_{j\geqslant 1}\frac{e_{j}x^{j}}{j}\biggr)=\mathop{\sum }_{i\geqslant 0}\frac{1}{i!}\biggl(\mathop{\sum }_{j\geqslant 1}\frac{e_{j}x^{j}}{j}\biggr)^{i}\end{eqnarray}$$
is also a polynomial in
$q$
of degree at most
$\lfloor n/2\rfloor$
. Hence, for any
$i\leqslant n$
,
$$\begin{eqnarray}\deg _{q}\biggl(q^{n-i}\binom{n-i-\frac{1}{2}}{n-i}\cdot [x^{i}]\exp \biggl(\mathop{\sum }_{j\geqslant 1}\frac{e_{j}x^{j}}{j}\biggr)\biggr)\leqslant n-i+\biggl\lfloor\frac{i}{2}\biggr\rfloor=n-\lceil \frac{i}{2}\rceil ,\end{eqnarray}$$
and if
$i=0$
, then equality holds in (4.33). Hence, (4.33) implies that
$B(n,q)$
is a polynomial in
$q$
of degree
$n$
. If one only wants the first
$d$
coefficients of
$B(n,q)$
, then only the first
$2d-1$
coefficients of
$\exp (\sum _{j\geqslant 1}(e_{j}x^{j}/j))$
are needed, as may be seen from the following identity, which follows from (4.31) and (4.33):
$$\begin{eqnarray}B(n,q)=\mathop{\sum }_{i=0}^{2d-2}q^{n-i}\binom{n-i-\frac{1}{2}}{n-i}\cdot [x^{i}]\exp \biggl(\mathop{\sum }_{j\geqslant 1}\frac{e_{j}x^{j}}{j}\biggr)+O_{n}(q^{n-d}).\end{eqnarray}$$
4.2 The constant
$K_{q}$
We study the constant
$K_{q}$
appearing in the main term of Theorem 1.1. In (1.8), the constant is expressed as the following Euler product:
$$\begin{eqnarray}K_{q}=(1-q^{-1})^{-1/2}\mathop{\prod }_{P\in {\mathcal{P}}_{q}:(P/T)=-1}(1-q^{-2\deg P})^{-1/2}.\end{eqnarray}$$
We provide another expression, which is the polynomial analogue of the following similar expression obtained in the integer setting independently in [Reference Flajolet and Vardi7, Reference Shanks19]:
$$\begin{eqnarray}K=\frac{1}{\sqrt{2}}\mathop{\prod }_{n\geqslant 1}\biggl(\biggl(1-\frac{1}{2^{2^{n}}}\biggr)\frac{\unicode[STIX]{x1D701}(2^{n})}{L(2^{n},\unicode[STIX]{x1D712})}\biggr)^{1/2^{n+1}},\end{eqnarray}$$
where
$\unicode[STIX]{x1D701}(s)=\sum _{n\geqslant 1}n^{-s}$
,
$L(s,\unicode[STIX]{x1D712})=\sum _{n\geqslant 1}(\unicode[STIX]{x1D712}(n)/n^{s})$
and where
$\unicode[STIX]{x1D712}$
is the principal character modulo 4.
Although the method of derivation of (4.36) applies mutatis mutandis to the polynomial setting, we do it slightly differently. In the process we obtain a functional equation for
$F_{G_{q}}(x)$
.
Lemma 4.2. Let
$A(x)=\exp (\sum _{n\geqslant 1}(a_{n}x^{n}/n))$
be a formal power series. Let
$$\begin{eqnarray}b_{n}=\left\{\begin{array}{@{}ll@{}}a_{n}-a_{n/2}\quad & 2\mid n\\ a_{n}\quad & 2\nmid n\end{array}\right.\quad \text{and}\quad B(x)=\exp \biggl(\mathop{\sum }_{n\geqslant 1}\frac{b_{n}x^{n}}{n}\biggr).\end{eqnarray}$$
Then
$$\begin{eqnarray}A(x)=\mathop{\prod }_{k\geqslant 0}B(x^{2^{k}})^{2^{-k}},\end{eqnarray}$$
where each of the roots
$B(x^{2^{k}})^{2^{-k}}$
is chosen so that the constant term is
$1$
.
In particular,
$$\begin{eqnarray}\frac{A^{2}(x)}{A(x^{2})}=B^{2}(x).\end{eqnarray}$$
Proof. Assertion (4.38) follows from (4.37). We have
$$\begin{eqnarray}\displaystyle \mathop{\prod }_{k\geqslant 0}B(x^{2^{k}})^{2^{-k}} & = & \displaystyle \mathop{\prod }_{k\geqslant 0}\exp \biggl(\mathop{\sum }_{n\geqslant 1}\frac{b_{n}x^{2^{k}n}}{2^{k}n}\biggr)\nonumber\\ \displaystyle & = & \displaystyle \exp \biggl(\mathop{\sum }_{n\geqslant 1}\frac{\big(\mathop{\sum }_{i=0}^{v_{2}(n)}b_{n/2^{i}}\big)x^{n}}{n}\biggr),\end{eqnarray}$$
so it suffices to show
$$\begin{eqnarray}a_{n}=\mathop{\sum }_{i=0}^{v_{2}(n)}b_{n/2^{i}},\end{eqnarray}$$
which follows from the definition of
$b_{n}$
.◻
Applying Lemma 4.2 to
$A=F_{G_{q}}$
, we find
$$\begin{eqnarray}\displaystyle \frac{F_{G_{q}}^{2}(x)}{F_{G_{q}}(x^{2})}=h^{2}(x), & & \displaystyle\end{eqnarray}$$
where
$$\begin{eqnarray}h(x)=\exp \left(\mathop{\sum }_{n\geqslant 1}\biggl(\unicode[STIX]{x1D713}_{G_{q}}(n)-\underbrace{\unicode[STIX]{x1D713}_{G_{q}}\biggl(\frac{n}{2}\biggr)}_{=0\,\text{if}\,2\nmid n}\biggr)\frac{x^{n}}{n}\right).\end{eqnarray}$$
Using the formula
$\unicode[STIX]{x1D713}_{G_{q}}(n)=(q^{n}+1)/2+\sum _{i=1}^{v_{2}(n)}((q^{n/2^{i}}-1)/2)$
(see (4.23)) we find
$$\begin{eqnarray}\unicode[STIX]{x1D713}_{G_{q}}(n)-\underbrace{\unicode[STIX]{x1D713}_{G_{q}}\biggl(\frac{n}{2}\biggr)}_{=0\,\text{if}\,2\nmid n}=\frac{q^{n}-(-1)^{n}}{2},\end{eqnarray}$$
thus,
$$\begin{eqnarray}h(x)=\sqrt{\frac{1+x}{1-qx}},\end{eqnarray}$$
and
$$\begin{eqnarray}\displaystyle \frac{F_{G_{q}}^{2}(x)}{F_{G_{q}}(x^{2})}=\frac{1+x}{1-qx}. & & \displaystyle\end{eqnarray}$$
This functional equation determines
$F_{G_{q}}(x)$
uniquely, assuming
$F_{G_{q}}$
is a power series with
$F_{G_{q}}(0)\neq 0$
.
Applying Lemma 4.2 to
$A(x)=a(x)=\exp (\sum _{n\geqslant 1}(e_{n}x^{n}/n))$
, we find
$$\begin{eqnarray}\exp \biggl(\mathop{\sum }_{n\geqslant 1}\frac{e_{n}x^{n}}{n}\biggr)=\mathop{\prod }_{k\geqslant 0}\widetilde{h}(x^{2^{k}})^{2^{-k}},\end{eqnarray}$$
where
$$\begin{eqnarray}\widetilde{h}(x)=\frac{\sqrt{1+x}}{\sqrt[4]{1-qx^{2}}}.\end{eqnarray}$$
Plugging
$x=q^{-1}$
in (4.46) gives the following identity:
$$\begin{eqnarray}K_{q}=\mathop{\prod }_{k\geqslant 0}\frac{\sqrt[2^{k+1}]{1+q^{-2^{k}}}}{\sqrt[2^{k+2}]{1-q^{1-2^{k+1}}}}=\frac{\sqrt{1+q^{-1}}}{\sqrt[4]{1-q^{-1}}}\frac{\sqrt[4]{1+q^{-2}}}{\sqrt[8]{1-q^{-3}}}\frac{\sqrt[8]{1+q^{-4}}}{\sqrt[16]{1-q^{-7}}}\cdots \,,\end{eqnarray}$$
which shows that
$K_{q}$
is an analytic function of
$q^{-1}$
.
Next we discuss the analogy between (4.48) and (4.36). Define
$|f|=q^{\deg f}$
, and put
$$\begin{eqnarray}\begin{array}{@{}rcl@{}}\unicode[STIX]{x1D701}_{\mathbb{F}_{q}[T]}(s)\ & =\ & \displaystyle \mathop{\sum }_{f\in {\mathcal{M}}_{q}}|f|^{-s}=\frac{1}{1-q^{1-s}},\\ L_{\mathbb{F}_{q}[T]}(s,\unicode[STIX]{x1D712}_{2})\ & =\ & \displaystyle \mathop{\sum }_{f\in {\mathcal{M}}_{q}}\unicode[STIX]{x1D712}_{2}(f)|f|^{-s}=1.\end{array}\end{eqnarray}$$
One may rearrange the terms of the product in (4.48) in a way that gives an expression which is analogous to (4.36):
$$\begin{eqnarray}\displaystyle K_{q}=\frac{1}{\sqrt{1-q^{-1}}}\mathop{\prod }_{n\geqslant 1}\biggl(\biggl(1-\frac{1}{q^{2^{n}}}\biggr)\frac{\unicode[STIX]{x1D701}_{\mathbb{F}_{q}[T]}(2^{n})}{L_{\mathbb{F}_{q}[T]}(2^{n},\unicode[STIX]{x1D712}_{2})}\biggr)^{1/2^{n+1}}. & & \displaystyle\end{eqnarray}$$
4.3 Second-order term for fixed
$q$
In the integer setting, Shanks [Reference Shanks19] computed numerically the coefficient
$c$
appearing in the following expansion:
$$\begin{eqnarray}\mathop{\sum }_{n\leqslant x}b(n)=K\frac{x}{\sqrt{\ln x}}\biggl(1+\frac{c}{\ln x}+O\biggl(\frac{1}{\ln ^{2}x}\biggr)\biggr),\end{eqnarray}$$
and found that
$c\approx 0.581\,948\,659$
. We study a similar problem in the polynomial setting.
Equation (4.29) shows that in the limit
$n\rightarrow \infty$
, we may expand
$B(n,q)$
as follows:
$$\begin{eqnarray}B(n,q)=K_{q}\cdot \binom{n-\frac{1}{2}}{n}\cdot q^{n}\biggl(1+\frac{a^{\prime }(q^{-1})}{2q\cdot a(q^{-1})}\frac{1}{n}+O\biggl(\frac{1}{qn^{2}}\biggr)\biggr).\end{eqnarray}$$
We give a formula for the constant
$$\begin{eqnarray}c_{q}=\frac{a^{\prime }(q^{-1})}{2q\cdot a(q^{-1})}=\frac{1}{2}\mathop{\sum }_{i\geqslant 1}e_{i}q^{-i},\end{eqnarray}$$
using the exact formula (4.23) for
$e_{n}$
:
$$\begin{eqnarray}\displaystyle c_{q} & = & \displaystyle \frac{1}{2}\mathop{\sum }_{i\geqslant 1}e_{i}q^{-i}=\frac{1}{4}\mathop{\sum }_{i\geqslant 1}\biggl(q^{-i}+\mathop{\sum }_{k=1}^{v_{2}(i)}(q^{i/2^{k}-i}-q^{-i})\biggr)\nonumber\\ \displaystyle & = & \displaystyle \frac{1}{4}\biggl(\frac{1}{q-1}+\mathop{\sum }_{j\geqslant 1}\mathop{\sum }_{i^{\prime }\geqslant 1}q^{i^{\prime }(1-2^{j})}-q^{-i^{\prime }2^{j}}\biggr)\nonumber\\ \displaystyle & = & \displaystyle \frac{1}{4}\biggl(\frac{1}{q-1}+\mathop{\sum }_{j\geqslant 1}\biggl(\frac{1}{q^{2^{j}-1}-1}-\frac{1}{q^{2^{j}}-1}\biggr)\biggr).\end{eqnarray}$$
In particular, equation (4.54) gives the following estimate for
$c_{q}$
:
$$\begin{eqnarray}c_{q}=\frac{1}{2q}+O\biggl(\frac{1}{q^{2}}\biggr).\end{eqnarray}$$
5 Landau’s theorem over
$\mathbb{F}_{q}[T]$
, for
$A^{2}-\unicode[STIX]{x1D6FC}B^{2}$
5.1 Proof of Theorem 2.1
We only prove estimate (2.9), as (2.10), (2.11) are proven mutatis mutandis.
Let
$q$
be a prime power. As explained in the beginning of §2, given a non-square element
$\unicode[STIX]{x1D6FC}\in \mathbb{F}_{q}$
, the set
$S_{1}(q)$
defined in (2.2) is the set of monic polynomials of the form
$A^{2}-\unicode[STIX]{x1D6FC}B^{2}$
. By definition,
$S_{1}(q)$
is the multiplicative semigroup of
$\mathbb{F}_{q}[T]$
generated by the following set of mutually coprime polynomials:
$$\begin{eqnarray}\displaystyle & & \displaystyle \{P\in \mathbb{F}_{q}[T]:P\text{ is monic irreducible of even degree}\}\nonumber\\ \displaystyle & & \displaystyle \qquad \bigcup \{P^{2}:P\in \mathbb{F}_{q}[T]\text{ is monic irreducible of odd degree}\}.\end{eqnarray}$$
It follows that the generating function of
$B_{1}(2n,q)$
(counting function of
$S_{1}(q)$
, defined in (2.3)) is
$$\begin{eqnarray}\displaystyle F_{S_{1}(q)}(x) & = & \displaystyle \mathop{\sum }_{n\geqslant 0}B_{1}(2n,q)x^{n}\nonumber\\ \displaystyle & = & \displaystyle \mathop{\prod }_{P\in {\mathcal{P}}_{q}:2\mid \deg P}(1-x^{\deg P/2})^{-1}\mathop{\prod }_{P\in {\mathcal{P}}_{q}:2\nmid \deg P}(1-x^{\deg P})^{-1}\nonumber\\ \displaystyle & = & \displaystyle \mathop{\prod }_{n\geqslant 1}(1-x^{n})^{-\unicode[STIX]{x1D70B}_{q}(2n)}(1-x^{2n-1})^{-\unicode[STIX]{x1D70B}_{q}(2n-1)}.\end{eqnarray}$$
If we set
$$\begin{eqnarray}h(n)=\left\{\begin{array}{@{}ll@{}}\unicode[STIX]{x1D70B}_{q}(2n)+\unicode[STIX]{x1D70B}_{q}(n)\quad & 2\nmid n,\\ \unicode[STIX]{x1D70B}_{q}(2n)\quad & 2\mid n,\end{array}\right.\end{eqnarray}$$
then
$F_{S_{1}(q)}$
assumes the form
$$\begin{eqnarray}F_{S_{1}(q)}(x)=\mathop{\prod }_{n\geqslant 1}(1-x^{n})^{-h(n)}.\end{eqnarray}$$
As before, one sees that
$$\begin{eqnarray}F_{S_{1}(q)}(x)=\exp \biggl(\mathop{\sum }_{n\geqslant 1}\frac{\unicode[STIX]{x1D713}_{S_{1}(q)}(n)x^{n}}{n}\biggr),\end{eqnarray}$$
where
$$\begin{eqnarray}\unicode[STIX]{x1D713}_{S_{1}(q)}(n)=\mathop{\sum }_{d\mid n}d\cdot h(d).\end{eqnarray}$$
We evaluate
$\unicode[STIX]{x1D713}_{S_{1}(q)}(n)$
. Let
$v_{2}(n)$
be the exponent of the greatest power of 2 that divides
$n$
. By (5.6), we have
$$\begin{eqnarray}\displaystyle \unicode[STIX]{x1D713}_{S_{1}(q)}(n) & = & \displaystyle \mathop{\sum }_{d\mid n}d\cdot \unicode[STIX]{x1D70B}_{q}(2d)+\mathop{\sum }_{d\mid n,\,2\nmid d}d\cdot \unicode[STIX]{x1D70B}_{d}(d)\nonumber\\ \displaystyle & = & \displaystyle \frac{1}{2}\biggl(\mathop{\sum }_{d^{\prime }\mid 2n}d^{\prime }\cdot \unicode[STIX]{x1D70B}_{q}(d^{\prime })-\mathop{\sum }_{d^{\prime }\mid 2n,\,2\nmid d^{\prime }}d^{\prime }\cdot \unicode[STIX]{x1D70B}_{q}(d^{\prime })\biggr)+\mathop{\sum }_{d\mid n,\,2\nmid d}d\cdot \unicode[STIX]{x1D70B}_{q}(d)\nonumber\\ \displaystyle & = & \displaystyle \frac{1}{2}\biggl(\mathop{\sum }_{d^{\prime }\mid 2n}d^{\prime }\cdot \unicode[STIX]{x1D70B}_{q}(d^{\prime })\biggr)+\frac{1}{2}\biggl(\mathop{\sum }_{d^{\prime }\mid n,\,2\nmid d^{\prime }}d^{\prime }\cdot \unicode[STIX]{x1D70B}_{q}(d^{\prime })\biggr)\nonumber\\ \displaystyle & = & \displaystyle \frac{1}{2}\biggl(\mathop{\sum }_{d^{\prime }\mid 2n}d^{\prime }\cdot \unicode[STIX]{x1D70B}_{q}(d^{\prime })\biggr)+\frac{1}{2}\biggl(\mathop{\sum }_{d^{\prime }\mid (n/2^{v_{2}(n)})}d^{\prime }\cdot \unicode[STIX]{x1D70B}_{q}(d^{\prime })\biggr).\end{eqnarray}$$
$$\begin{eqnarray}\unicode[STIX]{x1D713}_{S_{1}(q)}(n)=\frac{q^{2n}}{2}+\frac{q^{(n/2^{v_{2}(n)})}}{2}.\end{eqnarray}$$
If we define
$$\begin{eqnarray}f_{n}=\unicode[STIX]{x1D713}_{S_{1}(q)}(n)-\frac{q^{2n}}{2},\end{eqnarray}$$
we see by (5.7) that
$$\begin{eqnarray}f_{n}=\frac{q^{(n/2^{v_{2}(n)})}}{2}=O(q^{n}).\end{eqnarray}$$
As we saw in (3.6), we may write
$F_{S_{1}(q)}$
as a product of two power series with distinct radii of convergence:
$$\begin{eqnarray}F_{S_{1}(q)}(x)=\exp \biggl(\mathop{\sum }_{n\geqslant 1}\frac{f_{n}x^{n}}{n}\biggr)\cdot (1-q^{2}x)^{-1/2}.\end{eqnarray}$$
We may apply Theorem 3.3 with
$m=0$
and
$$\begin{eqnarray}a(x)=\exp \biggl(\mathop{\sum }_{n\geqslant 1}\frac{f_{n}x^{n}}{n}\biggr),\qquad b(x)=(1-q^{2}x)^{-1/2}.\end{eqnarray}$$
By (5.10), the parameters for Theorem 3.3 are
$$\begin{eqnarray}c_{1}={\textstyle \frac{1}{2}},\qquad c_{2}={\textstyle \frac{1}{2}},\qquad \unicode[STIX]{x1D6FC}=q^{-1},\qquad \unicode[STIX]{x1D6FD}=q^{-2}.\end{eqnarray}$$
By Theorem 3.3 we find
$$\begin{eqnarray}B_{1}(2n,q)=\binom{n-\frac{1}{2}}{n}\cdot q^{2n}\cdot \biggl(a(q^{-2})+O\biggl(\frac{1}{qn}\biggr)\biggr).\end{eqnarray}$$
This establishes (2.9) with
$$\begin{eqnarray}C_{q,1}=a(q^{-2}).\end{eqnarray}$$
By Remark 3.6,
$$\begin{eqnarray}C_{q,1}=1+O\biggl(\frac{1}{q}\biggr),\end{eqnarray}$$
which concludes the proof.
5.2 The constant
$C_{q,1}$
We study the constant appearing in the main term of (2.9),
$C_{q,1}$
. First, we show how we may express it as a product over primes. By (5.11), (5.12) and (5.13),
$$\begin{eqnarray}a(x)=\frac{F_{S_{1}(q)}(x)}{b(x)}\end{eqnarray}$$
for any
$|x|<q^{-2}$
. Letting
$x\rightarrow (q^{-2})^{-}$
in (5.17) and using (5.15), we obtain
$$\begin{eqnarray}C_{q,1}=\lim _{x\rightarrow (q^{-2})^{-}}\frac{F_{S_{1}(q)}(x)}{b(x)}.\end{eqnarray}$$
For
$0<x<q^{-2}$
,
$b$
has the following Euler product:
$$\begin{eqnarray}\displaystyle b(x) & = & \displaystyle (1-q^{2}x)^{-1/2}=(1-q\sqrt{x})^{-1/2}(1+q\sqrt{x})^{-1/2}\nonumber\\ \displaystyle & = & \displaystyle {\mathcal{Z}}_{\mathbb{F}_{q}[T]}^{1/2}(\sqrt{x})\cdot {\mathcal{Z}}_{\mathbb{F}_{q}[T]}^{1/2}(-\sqrt{x})\nonumber\\ \displaystyle & = & \displaystyle \mathop{\prod }_{P\in {\mathcal{P}}_{q}}(1-x^{\deg P/2})^{-1/2}\cdot \mathop{\prod }_{P\in {\mathcal{P}}_{q}}(1-(-1)^{\deg P}x^{\deg P/2})^{-1/2},\end{eqnarray}$$
where
${\mathcal{Z}}_{\mathbb{F}_{q}[T]}(x)$
is defined in (4.12). By considering odd-degree and even-degree primes separately, equation (5.19) shows
$$\begin{eqnarray}b(x)=\mathop{\prod }_{P\in {\mathcal{P}}_{q}:2\mid \deg P}(1-x^{\deg P/2})^{-1}\mathop{\prod }_{P\in {\mathcal{P}}_{q}:2\nmid \deg P}(1-x^{\deg P})^{-1/2}.\end{eqnarray}$$
By (5.18), (5.20) and the Euler product for
$F_{S_{1}(q)}$
given in (5.2), we obtain the following expression for
$C_{q,1}$
:
$$\begin{eqnarray}\displaystyle C_{q,1} & = & \displaystyle \!\lim _{x\rightarrow (q^{-2})^{-}}\!\frac{\mathop{\prod }_{P\in {\mathcal{P}}_{q}:2\mid \deg P}(1-x^{\deg P/2})^{-1}\mathop{\prod }_{P\in {\mathcal{P}}_{q}:2\nmid \deg P}(1-x^{\deg P})^{-1}}{\mathop{\prod }_{P\in {\mathcal{P}}_{q}:2\mid \deg P}(1-x^{\deg P/2})^{-1}\mathop{\prod }_{P\in {\mathcal{P}}_{q}:2\nmid \deg P}(1-x^{\deg P})^{-1/2}}\nonumber\\ \displaystyle & = & \displaystyle \lim _{x\rightarrow (q^{-2})^{-}}\mathop{\prod }_{P\in {\mathcal{P}}_{q}:2\nmid \deg P}(1-x^{\deg P})^{-1/2}\nonumber\\ \displaystyle & = & \displaystyle \mathop{\prod }_{P\in {\mathcal{P}}_{q}:2\nmid \deg P}(1-q^{-2\deg P})^{-1/2}.\end{eqnarray}$$
We provide another expression for
$C_{q,1}$
. Applying Lemma 4.2 to
$A(x)=\exp (\sum _{n\geqslant 1}(f_{n}x^{n}/n))$
, we find
$$\begin{eqnarray}\exp \biggl(\mathop{\sum }_{n\geqslant 1}\frac{f_{n}x^{n}}{n}\biggr)=\mathop{\prod }_{k\geqslant 0}B(x^{2^{k}})^{2^{-k}},\end{eqnarray}$$
where
$$\begin{eqnarray}\displaystyle B(x) & = & \displaystyle \exp \biggl(\mathop{\sum }_{2\nmid n}\frac{q^{n}x^{n}}{2n}\biggr)=\frac{\exp \left(\mathop{\sum }_{n\geqslant 1}(q^{n}x^{n}/2n)\right)}{\exp \left(\mathop{\sum }_{2\mid n}(q^{n}x^{n}/2n)\right)}\nonumber\\ \displaystyle & = & \displaystyle \frac{(1-qx)^{-1/2}}{(1-q^{2}x^{2})^{-1/4}}=\biggl(\frac{1+qx}{1-qx}\biggr)^{1/4}.\end{eqnarray}$$
Plugging
$x=q^{-2}$
in (5.22) and using (5.15), we obtain
$$\begin{eqnarray}C_{q,1}=\mathop{\prod }_{k\geqslant 0}\biggl(\frac{1+q^{1-2^{k+1}}}{1-q^{1-2^{k+1}}}\biggr)^{-2^{-k-2}}.\end{eqnarray}$$
Next we discuss the analogy between (5.24) and (4.36). Let
$\unicode[STIX]{x1D702}:\mathbb{F}_{q}[T]\rightarrow \mathbb{C}$
be the (generalized) Dirichlet character
$\unicode[STIX]{x1D702}(f)=(-1)^{\deg (f)}$
, and define
$|f|=q^{\deg f}$
. Let
$\unicode[STIX]{x1D701}_{\mathbb{F}_{q}[T]}$
be as in (4.49) and
$$\begin{eqnarray}L_{\mathbb{F}_{q}[T]}(s,\unicode[STIX]{x1D702})=\mathop{\sum }_{f\in {\mathcal{M}}_{q}}\unicode[STIX]{x1D702}(f)|f|^{-s},\end{eqnarray}$$
which equals
$$\begin{eqnarray}L_{\mathbb{F}_{q}[T]}(s,\unicode[STIX]{x1D702})=\mathop{\sum }_{n\geqslant 0}(-1)^{n}q^{n}q^{-ns}=\frac{1}{1+q^{1-s}}.\end{eqnarray}$$
The identity (5.24) may be written differently as an expression which is analogous to (4.36):
$$\begin{eqnarray}\displaystyle C_{q,1}=\mathop{\prod }_{n\geqslant 1}\biggl(\frac{\unicode[STIX]{x1D701}_{\mathbb{F}_{q}[T]}(2^{n})}{L_{\mathbb{F}_{q}[T]}(2^{n},\unicode[STIX]{x1D702})}\biggr)^{1/2^{n+1}}. & & \displaystyle\end{eqnarray}$$
5.3 Second-order term for fixed
$q$
Consider the functions
$a$
,
$b$
defined in (5.12). By (5.11), the product
$a\cdot b$
is the generating function of
$B_{1}(2n,q)$
. Hence, if we apply Theorem 3.3 with
$m=1$
to the functions
$a$
,
$b$
, we find that in the limit
$n\rightarrow \infty$
, we may expand
$B_{1}(2n,q)$
as follows:
$$\begin{eqnarray}B_{1}(2n,q)=C_{q,1}\cdot \binom{n-\frac{1}{2}}{n}\cdot q^{2n}\biggl(1+\frac{a^{\prime }(q^{-2})}{2q^{2}\cdot a(q^{-2})}\frac{1}{n}+O\biggl(\frac{1}{q^{2}n^{2}}\biggr)\biggr).\end{eqnarray}$$
We give a formula for the constant
$c_{q}^{\prime }=a^{\prime }(q^{-2})/(2q^{2}\cdot a(q^{-2}))=(1/2)\sum _{i\geqslant 1}f_{i}q^{-2i}$
using the exact formula (5.9) for
$f_{n}$
:
$$\begin{eqnarray}c_{q}^{\prime }=\frac{1}{2}\mathop{\sum }_{i\geqslant 1}f_{i}q^{-2i}=\frac{1}{4}\mathop{\sum }_{i\geqslant 1}q^{(i/2^{v_{2}(i)})-2i}.\end{eqnarray}$$
In particular, equation (5.29) gives the following estimate for
$c_{q}^{\prime }$
:
$$\begin{eqnarray}c_{q}^{\prime }=\frac{1}{4q}+O\biggl(\frac{1}{q^{3}}\biggr).\end{eqnarray}$$
6 Counting divisors over function fields
Here we prove Theorem 2.3. First, we prove an auxiliary lemma.
6.1 Counting primes
Lemma 6.1. Let
$K$
be a function field with finite constant field
$\mathbb{F}_{q}$
, i.e.
$K$
is a finitely generated field extension of transcendence degree one over
$\mathbb{F}_{q}$
and
$\mathbb{F}_{q}$
is algebraically closed in
$K$
. Fix a prime
$\mathfrak{Q}$
of
$K$
. For any
$n\geqslant 1$
, let
$$\begin{eqnarray}\unicode[STIX]{x1D70B}_{K,\mathfrak{Q}}(n)=\#\{\text{Primes of degree }n\text{ in }K\}\setminus \{\mathfrak{Q}\}.\end{eqnarray}$$
Given integers
$r\geqslant 2$
,
$\ell \geqslant 1$
, define the following functions:
$$\begin{eqnarray}\displaystyle \unicode[STIX]{x1D713}_{r,K}(n) & = & \displaystyle \mathop{\sum }_{d\mid n}d\cdot \unicode[STIX]{x1D70B}_{K,\mathfrak{Q}}(rd),\end{eqnarray}$$
$$\begin{eqnarray}\displaystyle f_{r,\ell ,K}(n) & = & \displaystyle \unicode[STIX]{x1D70B}_{K,\mathfrak{Q}}(rn)-\underbrace{\unicode[STIX]{x1D70B}_{K,\mathfrak{Q}}\biggl(\frac{rn}{\ell +1}\biggr)}_{=0\,\mathit{if}\,\ell +1\nmid rn},\end{eqnarray}$$
$$\begin{eqnarray}\displaystyle \unicode[STIX]{x1D713}_{r,\ell ,K}(n) & = & \displaystyle \mathop{\sum }_{d\mid n}d\cdot f_{r,\ell ,K}(d),\end{eqnarray}$$
$$\begin{eqnarray}\displaystyle \unicode[STIX]{x1D709}_{r,K}(n) & = & \displaystyle \mathop{\sum }_{d\mid nr}\frac{d\cdot \unicode[STIX]{x1D70B}_{K,\mathfrak{Q}}(d)}{(d,r)}.\end{eqnarray}$$
Denote by
$g_{K}$
the genus of
$K$
and let
$$\begin{eqnarray}M_{K,\mathfrak{Q}}=\max \{g_{K},\deg \mathfrak{Q}\}.\end{eqnarray}$$
Then
$$\begin{eqnarray}\displaystyle \unicode[STIX]{x1D713}_{r,K}(n) & = & \displaystyle \frac{q^{rn}}{r}+O\biggl(\frac{M_{K,\mathfrak{Q}}}{r}q^{rn/2}\biggr),\end{eqnarray}$$
$$\begin{eqnarray}\displaystyle \unicode[STIX]{x1D713}_{r,\ell ,K}(n) & = & \displaystyle \frac{q^{rn}}{r}+O\biggl(\frac{M_{K,\mathfrak{Q}}}{r}q^{rn/2}\biggr),\end{eqnarray}$$
$$\begin{eqnarray}\displaystyle \unicode[STIX]{x1D709}_{r,K}(n) & = & \displaystyle \frac{q^{rn}}{r}+O\biggl(\frac{M_{K,\mathfrak{Q}}}{r}q^{rn/2}\biggr),\end{eqnarray}$$
where the implied constants are (at most)
$16$
,
$42$
and
$50$
, respectively.
Proof. Let
$$\begin{eqnarray}\unicode[STIX]{x1D70B}_{K}=\#\{\text{Primes of degree }n\text{ in }K\}.\end{eqnarray}$$
The zeta function of
$K$
is
$$\begin{eqnarray}\displaystyle \unicode[STIX]{x1D701}_{K}(u) & = & \displaystyle \mathop{\sum }_{D\in \text{Div}_{{\geqslant}0}(K)}u^{\deg D}=\mathop{\prod }_{n\geqslant 1}(1-u^{n})^{-\unicode[STIX]{x1D70B}_{K}(n)}\nonumber\\ \displaystyle & = & \displaystyle \mathop{\prod }_{n\geqslant 1}(1-u^{n})^{-\unicode[STIX]{x1D70B}_{K,\mathfrak{Q}}(n)}\cdot (1-u^{\deg \mathfrak{Q}})^{-1}.\end{eqnarray}$$
The function
$\unicode[STIX]{x1D701}_{K}(u)$
is a rational function in
$u$
of the form
$$\begin{eqnarray}\unicode[STIX]{x1D701}_{K}(u)=\frac{L_{K}(u)}{(1-u)(1-qu)},\end{eqnarray}$$
where
$L_{K}$
is a polynomial with
$L_{K}(0)=1$
and of degree twice the genus of
$K$
,
$2g_{K}$
. The Riemann hypothesis for
$\unicode[STIX]{x1D701}_{K}$
, proved by Weil, shows that the absolute value of the roots of
$L_{K}$
is
$q^{-1/2}$
(see [Reference Rosen18, Theorem A.7]). Hence, taking the logarithmic derivative of (6.11), (6.12) and equating coefficients, we find
$$\begin{eqnarray}\mathop{\sum }_{d\mid n}d\cdot \unicode[STIX]{x1D70B}_{K,\mathfrak{Q}}(d)=q^{n}+1-\deg \mathfrak{Q}\cdot 1_{ deg\mathfrak{Q}\mid n}+O(g_{K}q^{n/2})=q^{n}+O(M_{K,\mathfrak{Q}}q^{n/2}),\end{eqnarray}$$
with implied constant (at most) 3. We estimate
$\unicode[STIX]{x1D713}_{r,K}(n)$
as follows, using (6.13):
$$\begin{eqnarray}\displaystyle \mathop{\sum }_{d\mid n}d\cdot \unicode[STIX]{x1D70B}_{K,\mathfrak{Q}}(rd) & = & \displaystyle \frac{1}{r}\mathop{\sum }_{d\mid n}rd\cdot \unicode[STIX]{x1D70B}_{K,\mathfrak{Q}}(rd)\nonumber\\ \displaystyle & = & \displaystyle \frac{1}{r}\biggl(\mathop{\sum }_{d^{\prime }\mid rn}d^{\prime }\cdot \unicode[STIX]{x1D70B}_{K,\mathfrak{Q}}(d^{\prime })-\mathop{\sum }_{r\nmid d^{\prime }\mid rn}d^{\prime }\cdot \unicode[STIX]{x1D70B}_{K,\mathfrak{Q}}(d^{\prime })\biggr)\nonumber\\ \displaystyle & = & \displaystyle \frac{1}{r}\biggl(q^{rn}+O(M_{K,\mathfrak{Q}}q^{rn/2})-\mathop{\sum }_{r\nmid d^{\prime }\mid rn}d^{\prime }\cdot \unicode[STIX]{x1D70B}_{K,\mathfrak{Q}}(d^{\prime })\biggr),\end{eqnarray}$$
where the implied constant is
$3$
. If
$d^{\prime }$
is an integer dividing
$nr$
but not divisible by
$r$
, it means
$d^{\prime }\mid (nr/p)$
for some prime
$p$
dividing
$nr$
. Hence, using (6.13), we see that the sum
$\sum _{r\nmid d^{\prime }\mid nr}d^{\prime }\cdot \unicode[STIX]{x1D70B}_{K,\mathfrak{Q}}(d^{\prime })$
is at most
$$\begin{eqnarray}\displaystyle \mathop{\sum }_{r\nmid d^{\prime }\mid nr}d^{\prime }\cdot \unicode[STIX]{x1D70B}_{K,\mathfrak{Q}}(d^{\prime }) & {\leqslant} & \displaystyle \mathop{\sum }_{p\mid nr}\mathop{\sum }_{d^{\prime }\mid (nr/p)}d^{\prime }\cdot \unicode[STIX]{x1D70B}_{K,\mathfrak{Q}}(d^{\prime })\nonumber\\ \displaystyle & {\leqslant} & \displaystyle \mathop{\sum }_{p\mid nr}(q^{nr/p}+3M_{K,\mathfrak{Q}}q^{nr/2p})\nonumber\\ \displaystyle & {\leqslant} & \displaystyle q^{\lfloor nr/2\rfloor }\biggl(\mathop{\sum }_{i\geqslant 0}q^{-i}\biggr)+3M_{K,\mathfrak{Q}}q^{\lfloor nr/2\rfloor /2}\biggl(\mathop{\sum }_{i\geqslant 0}q^{-i/2}\biggr)\nonumber\\ \displaystyle & {\leqslant} & \displaystyle \frac{1}{1-q^{-1}}q^{\lfloor nr/2\rfloor }+3M_{K,\mathfrak{Q}}\frac{1}{1-q^{-1/2}}q^{\lfloor nr/2\rfloor }\nonumber\\ \displaystyle & {\leqslant} & \displaystyle \biggl(2+\frac{3M_{K,\mathfrak{Q}}}{1-2^{-1/2}}\biggr)q^{nr/2}\leqslant 13M_{K,\mathfrak{Q}}q^{nr/2}.\end{eqnarray}$$
Combining (6.14) and (6.15), we obtain (6.7) with an implied constant
$3+13=16$
. We now prove (6.8). Note that (6.13) implies
$$\begin{eqnarray}\unicode[STIX]{x1D70B}_{K,\mathfrak{Q}}(n)\leqslant \frac{4}{n}M_{K,\mathfrak{Q}}q^{n}.\end{eqnarray}$$
If
$\ell +1\nmid rn$
, then
$\unicode[STIX]{x1D713}_{r,\ell ,K}(n)=\unicode[STIX]{x1D713}_{r,K}(n)$
, and (6.8) is established. Otherwise, by (6.16),
$$\begin{eqnarray}\displaystyle \mathop{\sum }_{d\mid n,\,\ell +1\mid rd}d\cdot \unicode[STIX]{x1D70B}_{K,\mathfrak{Q}}\biggl(\frac{rd}{\ell +1}\biggr) & {\leqslant} & \displaystyle 4M_{K,\mathfrak{Q}}\frac{\ell +1}{r}\mathop{\sum }_{d\mid n,\,\ell +1\mid rd}q^{rd/(\ell +1)}\nonumber\\ \displaystyle & {\leqslant} & \displaystyle 4M_{K,\mathfrak{Q}}\frac{\ell +1}{r}q^{rn/(\ell +1)}\mathop{\sum }_{i\geqslant 0}q^{-i}\nonumber\\ \displaystyle & {\leqslant} & \displaystyle 8M_{K,\mathfrak{Q}}\frac{\ell +1}{r}q^{rn/(\ell +1)}.\end{eqnarray}$$
If
$\ell =1$
, then (6.17) gives
$$\begin{eqnarray}\mathop{\sum }_{d\mid n,\ell +1\mid rd}d\cdot \unicode[STIX]{x1D70B}_{K,\mathfrak{Q}}\biggl(\frac{rd}{\ell +1}\biggr)\leqslant 16\frac{M_{K,\mathfrak{Q}}}{r}q^{rn/2}.\end{eqnarray}$$
By (6.18) and (6.7), estimate (6.8) is established with the absolute constant
$16+16=32$
.
If
$\ell >1$
, then (6.17) gives
$$\begin{eqnarray}\mathop{\sum }_{d\mid n,\,\ell +1\mid rd}d\cdot \unicode[STIX]{x1D70B}_{K,\mathfrak{Q}}\biggl(\frac{rd}{\ell +1}\biggr)\leqslant \frac{8M_{K,\mathfrak{Q}}}{r}\cdot rn\cdot q^{rn/3}.\end{eqnarray}$$
Note that for any positive
$x$
,
$$\begin{eqnarray}x=\frac{6}{e\ln 2}\cdot e\cdot \frac{\ln 2}{6}x\leqslant \frac{6}{e\ln 2}\cdot e\cdot \exp \biggl(\biggl(\frac{\ln 2}{6}x\biggr)-1\biggr)=\frac{6}{e\ln 2}\cdot 2^{x/6}\leqslant \frac{6}{e\ln 2}\cdot q^{x/6}.\end{eqnarray}$$
Using (6.20) with
$x=rn$
in (6.19), we obtain
$$\begin{eqnarray}\mathop{\sum }_{d\mid n,\ell +1\mid rd}d\cdot \unicode[STIX]{x1D70B}_{K,\mathfrak{Q}}\biggl(\frac{rd}{\ell +1}\biggr)\leqslant \frac{8\cdot (6/e\ln 2)M_{K,\mathfrak{Q}}}{r}q^{rn/2}.\end{eqnarray}$$
By (6.18) and (6.7), estimate (6.8) is established with the absolute constant
$16+8\cdot (6/e\ln 2)\leqslant 42$
. We now prove (6.9). From (6.2) and (6.5), we have
$$\begin{eqnarray}\displaystyle |\unicode[STIX]{x1D709}_{r,K}(n)-\unicode[STIX]{x1D713}_{r,K}(n)| & {\leqslant} & \displaystyle \mathop{\sum }_{d\mid nr,d\neq nr}\frac{d}{(d,r)}\cdot \unicode[STIX]{x1D70B}_{K,\mathfrak{Q}}(d)\nonumber\\ \displaystyle & {\leqslant} & \displaystyle \mathop{\sum }_{d\leqslant nr/3}d\cdot \unicode[STIX]{x1D70B}_{K,\mathfrak{Q}}(d)+1_{2\mid rn}\cdot \frac{rn/2}{(rn/2,r)}\cdot \unicode[STIX]{x1D70B}_{K,\mathfrak{Q}}(rn/2).\nonumber\\ \displaystyle & & \displaystyle\end{eqnarray}$$
From (6.16) and (6.20), we obtain
$$\begin{eqnarray}\displaystyle \mathop{\sum }_{d\leqslant nr/3}d\cdot \unicode[STIX]{x1D70B}_{K,\mathfrak{Q}}(d) & {\leqslant} & \displaystyle 4M_{K,\mathfrak{Q}}\mathop{\sum }_{d\leqslant nr/3}q^{d}\leqslant 8M_{K,\mathfrak{Q}}q^{rn/3}\nonumber\\ \displaystyle & {\leqslant} & \displaystyle 8M_{K,\mathfrak{Q}}\frac{6}{e\ln 2}\frac{1}{rn}q^{rn/2}\leqslant \frac{26M_{K,\mathfrak{Q}}}{r}q^{rn/2}.\end{eqnarray}$$
From (6.16), we also have
$$\begin{eqnarray}1_{2\mid rn}\cdot \frac{rn/2}{(rn/2,r)}\cdot \unicode[STIX]{x1D70B}_{K,\mathfrak{Q}}(rn/2)\leqslant n\cdot \frac{8}{rn}M_{K,\mathfrak{Q}}q^{rn/2}=\frac{8M_{K,\mathfrak{Q}}}{r}q^{rn/2}.\end{eqnarray}$$
From (6.22), (6.23), (6.24) and (6.7), we arrive at estimate (6.9) with the absolute implied constant
$16+26+8=50$
.◻
6.2 Proof of Theorem 2.3
We first treat the case
$\deg _{K}\mathfrak{Q}\nmid rn$
. The divisors counted by
$B_{i}(rn,rk)$
and
$B_{3}(rn,r,\ell ,K)$
satisfy
$$\begin{eqnarray}\deg _{\mathfrak{Q}}(D)=rn.\end{eqnarray}$$
By (2.15), the condition (6.25) is equivalent to
$$\begin{eqnarray}v_{\mathfrak{Q}}=-\frac{rn}{\deg _{K}\mathfrak{Q}}.\end{eqnarray}$$
The right-hand side of (6.26) is not integral when
$\deg _{K}\mathfrak{Q}\nmid rn$
, hence
$$\begin{eqnarray}B_{1}(rn,r,K)=B_{2}(rn,r,K)=B_{3}(rn,r,\ell ,K)=0.\end{eqnarray}$$
From now on we assume
$$\begin{eqnarray}\deg _{K}\mathfrak{Q}\mid rn.\end{eqnarray}$$
Given a divisor
$D=\sum _{\mathfrak{P}\in \mathbb{P}_{K}}v_{\mathfrak{P}}(D)\cdot \mathfrak{P}\in \text{Div}_{0,\mathfrak{Q}}(K)$
, we define
$$\begin{eqnarray}D_{0}=\mathop{\sum }_{\mathfrak{Q}\neq \mathfrak{P}\in \mathbb{P}_{K}}v_{\mathfrak{P}}(D)\cdot \mathfrak{P},\qquad D_{\infty }=-v_{\mathfrak{Q}}(D)\cdot \mathfrak{Q}.\end{eqnarray}$$
Note that
$D=D_{0}-D_{\infty }$
. A divisor
$D\in \text{Div}_{0,\mathfrak{Q}}(K)$
is counted by
$B_{1}(rn,r,K)/B_{2}(rn,r,K)/B_{3}(rn,r,\ell ,K)$
if and only if
$$\begin{eqnarray}D_{\infty }=\frac{rn}{\deg _{K}\mathfrak{Q}}\cdot \mathfrak{Q}\end{eqnarray}$$
and
$$\begin{eqnarray}\displaystyle D_{0} & \in & \displaystyle \left\{\mathop{\sum }_{\mathfrak{Q}\neq \mathfrak{P}\in \mathbb{P}_{K}}n_{\mathfrak{P}}\cdot \mathfrak{P},n_{\mathfrak{P}}\geqslant 0:n_{\mathfrak{P}}>0\right.\nonumber\\ \displaystyle & & \displaystyle \left.\quad \;\Longrightarrow \;\left\{\begin{array}{@{}ll@{}}\displaystyle \frac{r}{(r,\deg _{K}\mathfrak{P})}\bigg|n_{\mathfrak{P}}\quad & (B_{1}(rn,r,K))\\ r\mid \deg _{K}\mathfrak{P}\quad & (B_{2}(rn,r,K))\\ r\mid \deg _{K}\mathfrak{P}\text{ and }n_{\mathfrak{P}}\leqslant \ell \quad & (B_{3}(rn,r,\ell ,K))\end{array}\right.\right\}.\end{eqnarray}$$
Note that condition (6.31) does not depend on
$\deg _{K}\mathfrak{Q}$
, so we may assume
$\deg _{K}\mathfrak{Q}=1$
without loss of generality. The generating function of
$\{B_{1}(rn,r,K)\}_{n\geqslant 0}$
is, by definition,
$$\begin{eqnarray}\displaystyle G_{r,K}(x) & = & \displaystyle \mathop{\prod }_{\mathfrak{P}\in \mathbb{P}_{K}\setminus \{\mathfrak{Q}\}}(1-x^{\deg _{K}\mathfrak{P}/(r,\deg _{K}\mathfrak{P})})^{-1}\nonumber\\ \displaystyle & = & \displaystyle \mathop{\prod }_{d\mid r}\mathop{\prod }_{\substack{ \mathfrak{P}\in \mathbb{P}_{K}\setminus \{\mathfrak{Q}\} \\ (r,\deg _{K}\mathfrak{P})=d}}(1-x^{\deg _{K}\mathfrak{P}/d})^{-1}\nonumber\\ \displaystyle & = & \displaystyle \exp \left(\mathop{\sum }_{d\mid r}\mathop{\sum }_{m\geqslant 1}\frac{x^{m}}{m}\frac{\mathop{\sum }_{\substack{ \mathfrak{P}\in \mathbb{P}_{K}\setminus \{\mathfrak{Q}\} \\ (\deg _{K}\mathfrak{P},r)=d \\ \deg _{K}\mathfrak{P}\mid md}}\deg _{K}\mathfrak{P}}{d}\right)\nonumber\\ \displaystyle & = & \displaystyle \exp \biggl(\mathop{\sum }_{m\geqslant 1}\frac{\unicode[STIX]{x1D709}_{r,K}(m)x^{m}}{m}\biggr).\end{eqnarray}$$
The generating function
$F_{r,K}$
of
$\{B_{2}(rm,r,K)\}_{m\geqslant 0}$
is, by definition,
$$\begin{eqnarray}\displaystyle F_{r,K}(x) & = & \displaystyle \mathop{\prod }_{m\geqslant 1}(1+x^{m}+x^{2m}+\cdots \,)^{\unicode[STIX]{x1D70B}_{K,\mathfrak{Q}}(rm)}\nonumber\\ \displaystyle & = & \displaystyle \mathop{\prod }_{m\geqslant 1}(1-x^{m})^{-\unicode[STIX]{x1D70B}_{K,\mathfrak{Q}}(rm)}\nonumber\\ \displaystyle & = & \displaystyle \exp \biggl(\mathop{\sum }_{m\geqslant 1}\frac{\unicode[STIX]{x1D713}_{r,K}(m)x^{m}}{m}\biggr),\end{eqnarray}$$
where
$\unicode[STIX]{x1D70B}_{K,\mathfrak{Q}}$
is defined in (6.1) and
$\unicode[STIX]{x1D713}_{r,K}$
is defined in (6.2). The generating function
$F_{r,\ell ,K}$
of
$\{B_{3}(rm,r,\ell ,K)\}_{n\geqslant 0}$
is, by definition,
$$\begin{eqnarray}\displaystyle F_{r,\ell ,K}(x) & = & \displaystyle \mathop{\prod }_{m\geqslant 1}(1+x^{m}+\cdots +x^{m\ell })^{\unicode[STIX]{x1D70B}_{K,\mathfrak{Q}}(rm)}\nonumber\\ \displaystyle & = & \displaystyle \mathop{\prod }_{m\geqslant 1}\biggl(\frac{1-x^{m(\ell +1)}}{1-x^{m}}\biggr)^{\unicode[STIX]{x1D70B}_{K,\mathfrak{Q}}(rm)}.\end{eqnarray}$$
We may rearrange (6.34) as follows:
$$\begin{eqnarray}F_{r,\ell ,K}(x)=\mathop{\prod }_{m\geqslant 1}(1-x^{m})^{-f_{r,\ell ,K}(m)}=\exp \biggl(\mathop{\sum }_{m\geqslant 1}\frac{\unicode[STIX]{x1D713}_{r,\ell ,K}(m)x^{m}}{m}\biggr),\end{eqnarray}$$
where
$f_{r,\ell ,K}$
and
$\unicode[STIX]{x1D713}_{r,\ell ,K}$
are defined in (6.3) and (6.4), respectively. The estimates (6.7), (6.8) and (6.9) of Lemma 6.1 show that we may write
$G_{r,K}$
,
$F_{r,K}$
and
$F_{r,\ell ,K}$
as
$$\begin{eqnarray}\begin{array}{@{}rcl@{}}G_{r,K}\ & =\ & a_{1}\cdot b,\\ F_{r,K}\ & =\ & a_{2}\cdot b,\\ F_{r,\ell ,K}\ & =\ & a_{3}\cdot b,\end{array}\end{eqnarray}$$
where
$$\begin{eqnarray}\begin{array}{@{}rcl@{}}b(x)\ & =\ & \displaystyle \exp \biggl(\mathop{\sum }_{m\geqslant 1}\frac{q^{rm}x^{m}}{m}\biggr)=(1-q^{r}x)^{-1/r},\\ a_{1}\ & =\ & \displaystyle \frac{G_{r,K}}{b}=\exp \biggl(\mathop{\sum }_{m\geqslant 1}\frac{\widetilde{a_{1,m}}x^{m}}{m}\biggr),\\ a_{2}\ & =\ & \displaystyle \frac{F_{r,K}}{b}=\exp \biggl(\mathop{\sum }_{m\geqslant 1}\frac{\widetilde{a_{2,m}}x^{m}}{m}\biggr),\\ a_{3}\ & =\ & \displaystyle \frac{F_{r,\ell ,K}}{b}=\exp \biggl(\mathop{\sum }_{m\geqslant 1}\frac{\widetilde{a_{3,m}}x^{m}}{m}\biggr),\end{array}\end{eqnarray}$$
$$\begin{eqnarray}i=1,2,3:|\widetilde{a_{i,m}}|=O\biggl(\frac{M_{K,\mathfrak{Q}}}{r}q^{rm/2}\biggr),\end{eqnarray}$$
where the implied constant in (6.38) is (at most) 50.
We apply Corollary 3.4 to the pairs
$(a_{1},b)$
,
$(a_{2},b)$
and
$(a_{3},b)$
with the following parameters, given by (6.37) and (6.38):
$$\begin{eqnarray}c_{1}=\frac{1}{r},\qquad c_{2}\leqslant \frac{50M_{K,\mathfrak{Q}}}{r},\qquad \unicode[STIX]{x1D6FC}=q^{-r/2},\qquad \unicode[STIX]{x1D6FD}=q^{-r}.\end{eqnarray}$$
We obtain that the estimates (2.27), (2.28) and (2.29) of Theorem 2.3 hold with an absolute implied constant, as long as
$$\begin{eqnarray}\displaystyle n & {\geqslant} & \displaystyle \max \{5\cdot \biggl(\frac{(4\cdot 50\cdot M_{K,\mathfrak{Q}})/r+8}{r\ln q}+1\biggr)\nonumber\\ \displaystyle & & \displaystyle \times \,\ln \biggl(\frac{(4\cdot 50\cdot M_{K,\mathfrak{Q}})/r+8}{r\ln q}+1\biggr)+1,\frac{4}{\ln q}\frac{\ln r}{r}+1\},\end{eqnarray}$$
and the constants
$C_{1,r,K},C_{2,r,K},C_{r,\ell ,K}$
are given by
$$\begin{eqnarray}C_{1,r,K}=a_{1}(q^{-r}),\qquad C_{2,r,K}=a_{2}(q^{-r}),\qquad C_{r,\ell ,K}=a_{3}(q^{-r}).\end{eqnarray}$$
By Remark 3.6,
$$\begin{eqnarray}C_{1,r,K},C_{2,r,K},C_{r,\ell ,K}=\exp \biggl(O\biggl(\frac{M_{K,\mathfrak{Q}}}{rq^{r/2}}\biggr)\biggr)=1+O_{M_{K,\mathfrak{Q}}}\biggl(\frac{1}{rq^{r/2}}\biggr).\end{eqnarray}$$
Since
$$\begin{eqnarray}\frac{4}{\ln q}\frac{\ln r}{r}+1=O(1)\quad \text{and}\quad \frac{(4\cdot 50\cdot M_{K,\mathfrak{Q}})/r+8}{r\ln q}+1=O\biggl(\frac{M_{K,\mathfrak{Q}}}{r^{2}\ln q}+1\biggr),\end{eqnarray}$$
we get that the range (6.40) may be replaced with the range (2.30) of Theorem 2.3, as needed.
6.3 The constants
$C_{1,r,K},C_{2,r,K},C_{r,\ell ,K}$
Here we give an expression for the constants
$C_{1,r,K}$
,
$C_{2,r,K}$
and
$C_{r,\ell ,K}$
, involving a product over primes of
$K$
. The Euler products for the generating functions
$G_{r,K},F_{r,K},F_{r,\ell ,K}$
defined in §6.2 are given by
$$\begin{eqnarray}\begin{array}{@{}rcl@{}}G_{r,K}(x)\ & =\ & \displaystyle \mathop{\prod }_{\mathfrak{Q}\neq \mathfrak{P}\in \mathbb{P}_{K},}(1-x^{\deg _{K}\mathfrak{P}/(r,\deg _{K}\mathfrak{P})})^{-1},\\ F_{r,K}(x)\ & =\ & \displaystyle \mathop{\prod }_{\mathfrak{Q}\neq \mathfrak{P}\in \mathbb{P}_{K},r\mid \deg _{K}\mathfrak{P}}(1-x^{\deg _{K}\mathfrak{P}/r})^{-1},\\ F_{r,\ell ,K}(x)\ & =\ & \displaystyle \mathop{\prod }_{\mathfrak{Q}\neq \mathfrak{P}\in \mathbb{P}_{K},r\mid \deg _{K}\mathfrak{P}}\frac{1-x^{\deg _{K}\mathfrak{P}(\ell +1)/r}}{1-x^{\deg _{K}\mathfrak{P}/r}}.\end{array}\end{eqnarray}$$
Let
$K_{r}$
be the constant field extension of
$K$
of degree
$r$
, and let
$$\begin{eqnarray}{\mathcal{Z}}_{K_{r}}(u)=\mathop{\prod }_{\mathfrak{P}\in \mathbb{P}_{K_{r}}}(1-u^{\deg _{K_{r}}\mathfrak{P}})^{-1}\end{eqnarray}$$
be its zeta function. When
$r=1$
,
${\mathcal{Z}}_{K_{r}}={\mathcal{Z}}_{K}$
is just the zeta function of
$K$
. By [Reference Rosen18, Lemma 8.14 and Theorem 8.15],
$$\begin{eqnarray}{\mathcal{Z}}_{K_{r}}(u^{r})=\mathop{\prod }_{\unicode[STIX]{x1D714}:\unicode[STIX]{x1D714}^{r}=1}{\mathcal{Z}}_{K}(\unicode[STIX]{x1D714}u)=\mathop{\prod }_{\mathfrak{P}\in \mathbb{P}_{K}}(1-u^{r\deg _{K}\mathfrak{P}/(r,\deg _{K}\mathfrak{P})})^{-(r,\deg _{K}\mathfrak{P})}.\end{eqnarray}$$
We separate the product in (6.45) into a product over primes of degree divisible by
$r$
and the rest, and replace
$u^{r}$
with
$x$
:
$$\begin{eqnarray}\displaystyle {\mathcal{Z}}_{K_{r}}(x) & = & \displaystyle \mathop{\prod }_{\mathfrak{P}\in \mathbb{P}_{K},r\mid \deg _{K}\mathfrak{P}}(1-x^{\deg _{K}\mathfrak{P}/r})^{-r}\nonumber\\ \displaystyle & & \displaystyle \times \mathop{\prod }_{\mathfrak{P}\in \mathbb{P}_{K},r\nmid \deg _{K}\mathfrak{P}}(1-x^{\deg _{K}\mathfrak{P}/(r,\deg _{K}\mathfrak{P})})^{-(r,\deg _{K}\mathfrak{P})}.\end{eqnarray}$$
Let
${\mathcal{Z}}_{K_{r}}(x)^{1/r}$
be chosen so that the constant term is
$1$
. By (6.46),
$$\begin{eqnarray}\displaystyle {\mathcal{Z}}_{K_{r}}(x)^{1/r} & = & \displaystyle \mathop{\prod }_{\mathfrak{P}\in \mathbb{P}_{K},r\mid \deg _{K}\mathfrak{P}}(1-x^{\deg _{K}\mathfrak{P}/r})^{-1}\nonumber\\ \displaystyle & & \displaystyle \times \mathop{\prod }_{\mathfrak{P}\in \mathbb{P}_{K},r\nmid \deg _{K}\mathfrak{P}}(1-x^{\deg _{K}\mathfrak{P}/(r,\deg _{K}\mathfrak{P})})^{-(r,\deg _{K}\mathfrak{P})/r}.\end{eqnarray}$$
Dividing the expressions in (6.43) by (6.47), we obtain
$$\begin{eqnarray}\begin{array}{@{}rcl@{}}\displaystyle \frac{G_{r,K}(x)}{{\mathcal{Z}}_{K_{r}}(x)^{1/r}}\ & =\ & \displaystyle (1-x^{\deg _{K}\mathfrak{Q}/(r,\deg _{K}\mathfrak{Q})})\\ \ & \ & \displaystyle \cdot \mathop{\prod }_{\mathfrak{P}\in \mathbb{P}_{K},r\nmid \deg _{K}\mathfrak{P}}(1-x^{\deg _{K}\mathfrak{P}/(r,\deg _{K}\mathfrak{P})})^{(r,\deg _{K}\mathfrak{P})/r-1},\\ \displaystyle \frac{F_{r,K}(x)}{{\mathcal{Z}}_{K_{r}}(x)^{1/r}}\ & =\ & \displaystyle \mathop{\prod }_{\mathfrak{P}\in \mathbb{P}_{K},r\nmid \deg _{K}\mathfrak{P}}(1-x^{\deg _{K}\mathfrak{P}/(r,\deg _{K}\mathfrak{P})})^{(r,\deg _{K}\mathfrak{P})/r}\\ \ & \ & \displaystyle \cdot \left\{\begin{array}{@{}ll@{}}1\quad & r\nmid \deg _{K}\mathfrak{Q},\\ (1-x^{\deg _{K}\mathfrak{Q}/r})\quad & r\mid \deg _{K}\mathfrak{Q},\end{array}\right.\\ \displaystyle \frac{F_{r,\ell ,K}(x)}{{\mathcal{Z}}_{K_{r}}(x)^{1/r}}\ & =\ & \displaystyle \mathop{\prod }_{\mathfrak{P}\in \mathbb{P}_{K},r\nmid \deg _{K}\mathfrak{P}}(1-x^{\deg _{K}\mathfrak{P}/(r,\deg _{K}\mathfrak{P})})^{(r,\deg _{K}\mathfrak{P})/r}\\ \ & \ & \displaystyle \cdot \left\{\begin{array}{@{}ll@{}}1\quad & r\nmid \deg _{K}\mathfrak{Q},\\ (1-x^{\deg _{K}\mathfrak{Q}/r})\quad & r\mid \deg _{K}\mathfrak{Q}\end{array}\right.\\ \ & \ & \displaystyle \cdot \mathop{\prod }_{\mathfrak{Q}\neq \mathfrak{P}\in \mathbb{P}_{K},r\mid \deg _{K}\mathfrak{P}}(1-x^{\deg _{K}\mathfrak{P}(\ell +1)/r}).\end{array}\end{eqnarray}$$
From [Reference Rosen18, Theorem 5.9] we know that
${\mathcal{Z}}_{K_{r}}(x)$
is a rational function of
$x$
of the form
$$\begin{eqnarray}{\mathcal{Z}}_{K_{r}}(x)=\frac{L_{K_{r}}(x)}{(1-q^{r}x)(1-x)},\end{eqnarray}$$
where
$L_{K_{r}}$
is a polynomial of degree
$2g_{K_{r}}=2g_{K}$
satisfying
$$\begin{eqnarray}L_{K_{r}}(u)=L_{K_{r}}\biggl(\frac{1}{q^{r}u}\biggr)(q^{r}u^{2})^{g_{K}}\end{eqnarray}$$
and
$$\begin{eqnarray}L_{K_{r}}(q^{-r})=q^{-r\cdot g_{K}}L_{K_{r}}(1)=q^{-r\cdot g_{K}}h_{K_{r}},\end{eqnarray}$$
where
$h_{K_{r}}$
is the class number of
$K_{r}$
. Combining (6.48) and (6.49), we obtain
$$\begin{eqnarray}\begin{array}{@{}rcl@{}}G_{r,K}(x)\ & =\ & \displaystyle (1-q^{r}x)^{-1/r}\biggl(\frac{L_{K_{r}}(x)}{1-x}\biggr)^{1/r}\cdot (1-x^{\deg _{K}\mathfrak{Q}/(r,\deg _{K}\mathfrak{Q})})\\ \ & \ & \displaystyle \cdot \mathop{\prod }_{\mathfrak{P}\in \mathbb{P}_{K},r\nmid \deg _{K}\mathfrak{P}}(1-x^{\deg _{K}\mathfrak{P}/(r,\deg _{K}\mathfrak{P})})^{(r,\deg _{K}\mathfrak{P})/r-1}\\ F_{r,K}(x)\ & =\ & \displaystyle (1-q^{r}x)^{-1/r}\biggl(\frac{L_{K_{r}}(x)}{1-x}\biggr)^{1/r}\\ \ & \ & \displaystyle \cdot \mathop{\prod }_{\mathfrak{P}\in \mathbb{P}_{K},r\nmid \deg _{K}\mathfrak{P}}(1-x^{\deg _{K}\mathfrak{P}/(r,\deg _{K}\mathfrak{P})})^{(r,\deg _{K}\mathfrak{P})/r}\\ \ & \ & \displaystyle \cdot \left\{\begin{array}{@{}ll@{}}1\quad & r\nmid \deg _{K}\mathfrak{Q},\\ (1-x^{\deg _{K}\mathfrak{Q}/r})\quad & r\mid \deg _{K}\mathfrak{Q},\end{array}\right.\\ F_{r,\ell ,K}(x)\ & =\ & \displaystyle (1-q^{r}x)^{-1/r}\biggl(\frac{L_{K_{r}}(x)}{1-x}\biggr)^{1/r}\\ \ & \ & \displaystyle \cdot \mathop{\prod }_{\mathfrak{P}\in \mathbb{P}_{K},r\nmid \deg _{K}\mathfrak{P}}(1-x^{\deg _{K}\mathfrak{P}/(r,\deg _{K}\mathfrak{P})})^{(r,\deg _{K}\mathfrak{P})/r}\\ \ & \ & \displaystyle \cdot \left\{\begin{array}{@{}ll@{}}1\quad & r\nmid \deg _{K}\mathfrak{Q},\\ (1-x^{\deg _{K}\mathfrak{Q}/r})\quad & r\mid \deg _{K}\mathfrak{Q}\end{array}\right.\\ \ & \ & \cdot \displaystyle \mathop{\prod }_{\mathfrak{Q}\neq \mathfrak{P}\in \mathbb{P}_{K},r\mid \deg _{K}\mathfrak{P}}(1-x^{\deg _{K}\mathfrak{P}(\ell +1)/r}).\end{array}\end{eqnarray}$$
We deduce that the functions
$a_{1},a_{2},a_{3}$
defined in (6.36) are given by
$$\begin{eqnarray}\begin{array}{@{}rcl@{}}a_{1}(x)\ & =\ & \displaystyle \biggl(\frac{L_{K_{r}}(x)}{1-x}\biggr)^{1/r}\cdot (1-x^{\deg _{K}\mathfrak{Q}/(r,\deg _{K}\mathfrak{Q})})\\ \ & \ & \displaystyle \cdot \mathop{\prod }_{\mathfrak{P}\in \mathbb{P}_{K},r\nmid \deg _{K}\mathfrak{P}}(1-x^{\deg _{K}\mathfrak{P}/(r,\deg _{K}\mathfrak{P})})^{(r,\deg _{K}\mathfrak{P})/r-1},\\ a_{2}(x)\ & =\ & \displaystyle \biggl(\frac{L_{K_{r}}(x)}{1-x}\biggr)^{1/r}\mathop{\prod }_{\mathfrak{ P}\in \mathbb{P}_{K},r\nmid \deg _{K}\mathfrak{P}}(1-x^{\deg _{K}\mathfrak{P}/(r,\deg _{K}\mathfrak{P})})^{(r,\deg _{K}\mathfrak{P})/r}\\ \ & \ & \displaystyle \cdot \left\{\begin{array}{@{}ll@{}}1\quad & r\nmid \deg _{K}\mathfrak{Q},\\ (1-x^{\deg _{K}\mathfrak{Q}/r})\quad & r\mid \deg _{K}\mathfrak{Q},\end{array}\right.\\ a_{3}(x)\ & =\ & \displaystyle \biggl(\frac{L_{K_{r}}(x)}{1-x}\biggr)^{1/r}\cdot \mathop{\prod }_{\mathfrak{ P}\in \mathbb{P}_{K},r\nmid \deg _{K}\mathfrak{P}}(1-x^{\deg _{K}\mathfrak{P}/(r,\deg _{K}\mathfrak{P})})^{(r,\deg _{K}\mathfrak{P})/r}\\ \ & \ & \displaystyle \cdot \left\{\begin{array}{@{}ll@{}}1\quad & r\nmid \deg _{K}\mathfrak{Q},\\ (1-x^{\deg _{K}\mathfrak{Q}/r})\quad & r\mid \deg _{K}\mathfrak{Q}\end{array}\right.\\ \ & \ & \displaystyle \cdot \mathop{\prod }_{\mathfrak{Q}\neq \mathfrak{P}\in \mathbb{P}_{K},r\mid \deg _{K}\mathfrak{P}}(1-x^{\deg _{K}\mathfrak{P}(\ell +1)/r}).\end{array}\end{eqnarray}$$
From (6.53) and (6.51), we get that the constants
$C_{1,r,K},C_{2,r,K},C_{r,\ell ,K}$
defined in (6.41) are given by
$$\begin{eqnarray}\begin{array}{@{}rcl@{}}C_{1,r,K}\ & =\ & \displaystyle a_{1}(q^{-r})=q^{-g_{K}}\sqrt[r]{\frac{h_{K}}{1-q^{-r}}}\cdot (1-q^{-r\cdot \deg _{K}\mathfrak{Q}/(r,\deg _{K}\mathfrak{Q})})\\ \ & \ & \displaystyle \cdot \mathop{\prod }_{\mathfrak{P}\in \mathbb{P}_{K},r\nmid \deg _{K}\mathfrak{P}}(1-q^{-r\cdot \deg _{K}\mathfrak{P}/(r,\deg _{K}\mathfrak{P})})^{(r,\deg _{K}\mathfrak{P})/r-1},\\ C_{2,r,K}\ & =\ & \displaystyle a_{2}(q^{-r})=q^{-g_{K}}\sqrt[r]{\frac{h_{K}}{1-q^{-r}}}\\ \ & \ & \displaystyle \cdot \mathop{\prod }_{\mathfrak{P}\in \mathbb{P}_{K},r\nmid \deg _{K}\mathfrak{P}}(1-q^{-r\cdot \deg _{K}\mathfrak{P}/(r,\deg _{K}\mathfrak{P})})^{(r,\deg _{K}\mathfrak{P})/r}\\ \ & \ & \displaystyle \cdot \left\{\begin{array}{@{}ll@{}}1\quad & r\nmid \deg _{K}\mathfrak{Q},\\ (1-q^{-\!\deg _{K}\mathfrak{Q}})\quad & r\mid \deg _{K}\mathfrak{Q},\end{array}\right.\\ C_{r,\ell ,K}\ & =\ & \displaystyle a_{3}(q^{-r})=q^{-g_{K}}\sqrt[r]{\frac{h_{K}}{1-q^{-r}}}\\ \ & \ & \displaystyle \cdot \mathop{\prod }_{\mathfrak{P}\in \mathbb{P}_{K},r\nmid \deg _{K}\mathfrak{P}}(1-q^{-r\cdot \deg _{K}\mathfrak{P}/(r,\deg _{K}\mathfrak{P})})^{(r,\deg _{K}\mathfrak{P})/r}\\ \ & \ & \displaystyle \cdot \left\{\begin{array}{@{}ll@{}}1\quad & r\nmid \deg _{K}\mathfrak{Q},\\ (1-q^{-\text{deg}_{K}\,\mathfrak{Q}})\quad & r\mid \deg _{K}\mathfrak{Q}\end{array}\right.\\ \ & \ & \displaystyle \cdot \mathop{\prod }_{\mathfrak{Q}\neq \mathfrak{P}\in \mathbb{P}_{K},r\mid \deg _{K}\mathfrak{P}}(1-q^{-(\ell +1)\cdot \deg _{K}\mathfrak{P}}).\end{array}\end{eqnarray}$$
7 Polynomials with prime factors in an arithmetic progression
Let
$a,m\in \mathbb{F}_{q}[T]$
be a pair of coprime polynomials with
$\deg m>0$
,
$m$
monic. Let
$G_{a,m}\subseteq \mathbb{F}_{q}[T]$
be the set of monic polynomials whose monic prime factors lie in the arithmetic progression
$a(T)\,\text{mod}\,m(T)$
. Let
$\unicode[STIX]{x1D70B}_{q}(n;a,m)$
count the number of monic primes of degree
$n$
in the arithmetic progression
$a(T)\,\text{mod}\,m(T)$
. The generating function of
$S(n;a,m)$
(counting function of
$G_{a,m}$
, defined in (2.33)) is
$$\begin{eqnarray}F_{G_{a,m}}(x)=\mathop{\prod }_{n\geqslant 1}(1-x^{n})^{-\unicode[STIX]{x1D70B}_{q}(n;a,m)}.\end{eqnarray}$$
As before, one sees that
$$\begin{eqnarray}F_{G_{a,m}}(x)=\exp \biggl(\mathop{\sum }_{n\geqslant 1}\frac{\unicode[STIX]{x1D713}_{G_{a,m}}(n)x^{n}}{n}\biggr),\end{eqnarray}$$
where
$$\begin{eqnarray}\unicode[STIX]{x1D713}_{G_{a,m}}(n)=\mathop{\sum }_{d\mid n}d\cdot \unicode[STIX]{x1D70B}_{q}(d;a,m).\end{eqnarray}$$
We estimate
$\unicode[STIX]{x1D713}_{G_{a,m}}(n)$
. By a result of Wan [Reference Wan23, Theorem 5.1],
$$\begin{eqnarray}\displaystyle \biggl|n\cdot \unicode[STIX]{x1D70B}_{q}(n;a,m)-\frac{q^{n}}{\unicode[STIX]{x1D719}(m)}\biggr|\leqslant (\deg (m)+1)q^{n/2}. & & \displaystyle\end{eqnarray}$$
Hence,
$$\begin{eqnarray}\displaystyle \biggl|\unicode[STIX]{x1D713}_{G_{a,m}}(n)-\frac{q^{n}}{\unicode[STIX]{x1D719}(m)}\biggr|\leqslant (\deg (m)+1)q^{n/2}+\mathop{\sum }_{d\mid n,d<n}d\cdot \unicode[STIX]{x1D70B}_{q}(d;a,m). & & \displaystyle\end{eqnarray}$$
The tail
$\sum _{d\mid n,d<n}d\cdot \unicode[STIX]{x1D70B}_{q}(d;a,m)$
is easily bounded:
$$\begin{eqnarray}\displaystyle \mathop{\sum }_{d\mid n,d<n}d\cdot \unicode[STIX]{x1D70B}_{q}(d;a,m) & {\leqslant} & \displaystyle \mathop{\sum }_{d\mid n,d<n}d\cdot \unicode[STIX]{x1D70B}_{q}(d)\leqslant \mathop{\sum }_{d\mid n,d<n}q^{d}\nonumber\\ \displaystyle & {\leqslant} & \displaystyle q^{n/2}\frac{1}{1-q^{-1}}\leqslant 2q^{n/2}.\end{eqnarray}$$
$$\begin{eqnarray}\biggl|\unicode[STIX]{x1D713}_{G_{a,m}}(n)-\frac{q^{n}}{\unicode[STIX]{x1D719}(m)}\biggr|\leqslant (\deg (m)+3)q^{n/2}.\end{eqnarray}$$
Hence, we may write
$$\begin{eqnarray}F_{G_{a,m}}(x)=a(x)\cdot b(x),\end{eqnarray}$$
where
$$\begin{eqnarray}\begin{array}{@{}rcl@{}}a(x)\ & =\ & \displaystyle \exp \biggl(\mathop{\sum }_{n\geqslant 1}\frac{\widetilde{a_{n}}x^{n}}{n}\biggr),\\ |\widetilde{a_{n}}|\ & {\leqslant}\ & (\deg (m)+3)q^{n/2},\\ b(x)\ & =\ & (1-qx)^{-1/\unicode[STIX]{x1D719}(m)}.\end{array}\end{eqnarray}$$
The conditions of Corollary 3.4 then hold with the following parameters:
$$\begin{eqnarray}\unicode[STIX]{x1D6FC}=\frac{1}{\sqrt{q}},\qquad \unicode[STIX]{x1D6FD}=\frac{1}{q},\qquad c_{1}=\frac{1}{\unicode[STIX]{x1D719}(m)}\geqslant q^{-\text{deg}\,m},\qquad c_{2}=\deg (m)+3,\end{eqnarray}$$
and so estimate (2.39) holds with an implied constant at most 48, whenever
$$\begin{eqnarray}n\geqslant \max \biggl\{5\biggl(\frac{2(2c_{2}+4)}{\ln (q)}+1\biggr)\ln \biggl(\frac{2(2c_{2}+4)}{\ln (q)}+1\biggr)+1,4\frac{\ln (c_{1}^{-1})}{\ln q}+1\biggr\}.\end{eqnarray}$$
By plugging the parameters (7.10) in (7.11), and replacing
$\ln (q)$
with the lower bound
$\ln (2)$
, the range (7.11) may be replaced with the smaller range
$$\begin{eqnarray}\displaystyle n & {\geqslant} & \displaystyle \max \{\!5\biggl(\frac{4\deg (m)+20+\ln (2)}{\ln (2)}\biggr)\nonumber\\ \displaystyle & & \displaystyle \quad \qquad \times \,\ln \biggl(\frac{4\deg (m)+20+\ln (2)}{\ln (2)}\biggr)+1,4\deg (m)+1\!\}.\end{eqnarray}$$
Replacing
$(4\deg (m)+20+\ln (2))/\!\ln (2)$
with the upper bound
$6\deg (m)+30$
, Theorem 2.6 follows.
8 Asymptotics
Here we prove Theorem 3.3, a theorem in analysis on which we relied in previous sections, and whose proof implies Corollary 3.4. We break the proof into several auxiliary lemmas.
8.1 Basic identities and inequalities
Lemma 8.1. For any
$c_{1}\notin \mathbb{Z}$
and integers
$n\geqslant i\geqslant 0$
, the following identity holds:
$$\begin{eqnarray}(-1)^{i}\frac{\binom{-c_{1}}{n-i}}{\binom{-c_{1}}{n}}=\mathop{\sum }_{k=0}^{i}\frac{\binom{i}{k}\binom{k-c_{1}}{k}}{\binom{n+c_{1}-1}{k}}.\end{eqnarray}$$
Proof. Define the forward difference operator
$\unicode[STIX]{x1D6E5}(f)(x):=f(x+1)-f(x)$
, acting on
$\mathbb{C}[x]$
. For
$f(x)=\binom{x}{n}$
we have
$\unicode[STIX]{x1D6E5}(f)(x)=\binom{x}{n-1}$
(Pascal’s identity
$\binom{x+1}{n}-\binom{x}{n}=\binom{x}{n-1}$
) and so, by induction, we arrive at
$$\begin{eqnarray}\unicode[STIX]{x1D6E5}(f)^{(i)}(x)=\binom{x}{n-i}.\end{eqnarray}$$
On the other hand, we have in general
$$\begin{eqnarray}\unicode[STIX]{x1D6E5}(f)^{(i)}(x)=\mathop{\sum }_{k=0}^{i}\binom{i}{k}(-1)^{i-k}f(x+k).\end{eqnarray}$$
Plugging
$x=-c_{1}$
in (8.2), (8.3) and comparing the results, we obtain
$$\begin{eqnarray}\binom{-c_{1}}{n-i}=\mathop{\sum }_{k=0}^{i}\binom{i}{k}(-1)^{i-k}\binom{k-c_{1}}{n}.\end{eqnarray}$$
Dividing both sides of (8.4) by
$(-1)^{i}\binom{-c_{1}}{n}$
, we obtain
$$\begin{eqnarray}(-1)^{i}\frac{\binom{-c_{1}}{n-i}}{\binom{-c_{1}}{n}}=\mathop{\sum }_{k=0}^{i}\binom{i}{k}(-1)^{k}\frac{\binom{k-c_{1}}{n}}{\binom{-c_{1}}{n}}.\end{eqnarray}$$
The proof concludes by observing
$$\begin{eqnarray}\displaystyle (-1)^{k}\frac{\binom{k-c_{1}}{n}}{\binom{-c_{1}}{n}}=\frac{\binom{k-c_{1}}{k}}{\binom{n+c_{1}-1}{k}}. & & \displaystyle\end{eqnarray}$$
◻
Before the next lemma we recall that
$(x)_{n}$
stands for
$x(x-1)\cdots (x-(n-1))$
, the falling factorial.
Lemma 8.2. The following bound holds for any
$m<i\leqslant n$
and
$c_{1}\in (0,1)$
:
$$\begin{eqnarray}\mathop{\sum }_{k=m+1}^{i}\frac{\binom{i}{k}\binom{k-c_{1}}{k}}{\binom{n+c_{1}-1}{k}}\leqslant \left\{\begin{array}{@{}ll@{}}\displaystyle \frac{(i)_{m+1}}{(n+c_{1}-1)_{m+1}}(i-m)\quad & i<n,\\ \displaystyle n\biggl(\ln (n-m)+\frac{2}{c_{1}}\biggr)\quad & i=n.\end{array}\right.\end{eqnarray}$$
Proof. Since
$\binom{k-c_{1}}{k}=\prod _{i=1}^{k}(1-c_{1}/i)\leqslant 1$
, we can bound the left-hand side of (8.7) from above by
$$\begin{eqnarray}\displaystyle \mathop{\sum }_{k=m+1}^{i}\frac{\binom{i}{k}\binom{k-c_{1}}{k}}{\binom{n+c_{1}-1}{k}} & {\leqslant} & \displaystyle \mathop{\sum }_{k=m+1}^{i}\frac{(i)_{k}}{(n+c_{1}-1)_{k}}\end{eqnarray}$$
$$\begin{eqnarray}\displaystyle & = & \displaystyle \frac{(i)_{m+1}}{(n+c_{1}-1)_{m+1}}\mathop{\sum }_{k=m+1}^{i}\frac{(i-m-1)_{k-m-1}}{(n+c_{1}-m-2)_{k-m-1}}.\end{eqnarray}$$
The case
$i<n$
follows by observing that each of the terms in the sum in (8.9) is at most
$1$
.
For the case
$i=n$
, note that the right-hand side of (8.8) is equal to
$$\begin{eqnarray}\mathop{\sum }_{k=m+1}^{n}\frac{\binom{n}{k}}{\binom{n+c_{1}-1}{k}}.\end{eqnarray}$$
The term
$k=n$
in (8.10) gives
$\binom{n}{k}/\binom{n+c_{1}-1}{k}=(n/c_{1})\big(1/\binom{n+c_{1}-1}{n-1}\big)\leqslant n/c_{1}$
. The sum of the rest of the terms is bounded from above by
$$\begin{eqnarray}\displaystyle \mathop{\sum }_{k=m+1}^{n-1}\frac{\binom{n}{k}}{\binom{n-1}{k}} & = & \displaystyle \mathop{\sum }_{k=m+1}^{n-1}\frac{n}{n-k}=n\mathop{\sum }_{i=1}^{n-m-1}\frac{1}{i}\leqslant n(\ln (n-m)+1)\nonumber\\ \displaystyle & {\leqslant} & \displaystyle n\biggl(\ln (n-m)+\frac{1}{c_{1}}\biggr),\end{eqnarray}$$
as needed.◻
Lemma 8.3. Let
$a(x)=\exp (\sum _{n\geqslant 1}(\widetilde{a_{n}}x^{n}/n))=\sum a_{n}x^{n}$
be a power series satisfying (3.12) for some
$\unicode[STIX]{x1D6FC},c_{2}>0$
. We have the following for any
$i\geqslant 0$
and any
$0\leqslant x<\unicode[STIX]{x1D6FC}$
:
$$\begin{eqnarray}|a^{(i)}(x)|\leqslant \unicode[STIX]{x1D6FC}^{-i}(c_{2}+i-1)_{i}\biggl(1-\frac{x}{\unicode[STIX]{x1D6FC}}\biggr)^{-c_{2}-i}.\end{eqnarray}$$
Proof. Property (3.12) allows us to bound
$|a^{(i)}(x)|$
from above by
$|G^{(i)}(x)|$
for
$0\leqslant x<\unicode[STIX]{x1D6FC}$
, where
$$\begin{eqnarray}G(x)=\exp \biggl(\mathop{\sum }_{n\geqslant 1}\frac{c_{2}\unicode[STIX]{x1D6FC}^{-n}x^{n}}{n}\biggr)=\exp \biggl(-c_{2}\log \biggl(1-\frac{x}{\unicode[STIX]{x1D6FC}}\biggr)\biggr)=\biggl(1-\frac{x}{\unicode[STIX]{x1D6FC}}\biggr)^{-c_{2}}.\end{eqnarray}$$
By repeated differentiation and using
$(-c_{2})_{i}=(c_{2}+i-1)_{i}(-1)^{i}$
, we find
$$\begin{eqnarray}|G^{(i)}(x)|=\unicode[STIX]{x1D6FC}^{-i}(c_{2}+i-1)_{i}\biggl(1-\frac{x}{\unicode[STIX]{x1D6FC}}\biggr)^{-c_{2}-i},\end{eqnarray}$$
as needed.◻
Lemma 8.4. Let
$t>0$
. If
$n$
is a positive integer satisfying
$$\begin{eqnarray}n\geqslant 1+5(t+1)\ln (t+1),\end{eqnarray}$$
then the inequality
$$\begin{eqnarray}\frac{n-1}{\ln (n)+1}\geqslant t\end{eqnarray}$$
holds.
Proof. Let
$f(x)=(x-1)/(\ln (x)+1)$
. Note
$f$
is monotone increasing on
$[1,\infty )$
:
$$\begin{eqnarray}f^{\prime }(x)=\frac{\ln (x)+1/x}{(\ln (x)+1)^{2}}>0.\end{eqnarray}$$
Thus, to prove (8.16), it is enough to show that
$$\begin{eqnarray}f(1+5(t+1)\ln (t+1))\geqslant t,\end{eqnarray}$$
that is,
$$\begin{eqnarray}\frac{5(t+1)\ln (t+1)}{\ln (1+5(t+1)\ln (t+1))+1}\geqslant t.\end{eqnarray}$$
Let
$$\begin{eqnarray}g(t)=(t+1)\ln (t+1).\end{eqnarray}$$
Note that
$g(t)-t$
is monotone increasing for
$t>0$
, since
$$\begin{eqnarray}\text{for all}~t>0:(g(t)-t)^{\prime }=\ln (t+1)>0.\end{eqnarray}$$
In particular, equation (8.21) implies
$$\begin{eqnarray}\text{for all}~t\geqslant 0:g(t)\geqslant t+g(0)=t\end{eqnarray}$$
and
$g(t)$
is monotone increasing in
$[0,\infty )$
. We split the proof of (8.19) into two cases. If
$t\leqslant 4$
, then by (8.22) we obtain
$$\begin{eqnarray}\frac{5(t+1)\ln (t+1)}{\ln (1+5(t+1)\ln (t+1))+1}\geqslant \frac{5t}{\ln (1+5(4+1)\ln (4+1))+1}\geqslant t.\end{eqnarray}$$
If
$t\geqslant 4$
, then
$5(t+1)\ln (t+1)\geqslant 1$
. In particular, using
$\ln (t+1)\leqslant t<t+1$
, we obtain the following when
$t\geqslant 4$
:
$$\begin{eqnarray}\displaystyle \frac{5(t+1)\ln (t+1)}{\ln (1+5(t+1)\ln (t+1))+1} & {\geqslant} & \displaystyle \frac{5t\ln (t+1)}{\ln (10(t+1)\ln (t+1))+1}\nonumber\\ \displaystyle & {\geqslant} & \displaystyle \frac{5t\ln (t+1)}{\ln (10(t+1)^{2})+1}\nonumber\\ \displaystyle & = & \displaystyle 5t\biggl(\frac{1}{2}-\frac{\ln (10)+1}{4\ln (t+1)+2\ln (10)+2}\biggr)\nonumber\\ \displaystyle & {\geqslant} & \displaystyle 5t\biggl(\frac{1}{2}-\frac{\ln (10)+1}{4\ln (4+1)+2\ln (10)+2}\biggr)\geqslant t,\nonumber\\ \displaystyle & & \displaystyle\end{eqnarray}$$
as needed.◻
8.2 Main sum inequality
Lemma 8.5. Let
$a(x)=\exp (\sum _{n\geqslant 1}(\widetilde{a_{n}}x^{n}/n))=\sum a_{n}x^{n}$
be a power series satisfying (3.12) for some
$\unicode[STIX]{x1D6FC},c_{2}>0$
. Let
$\unicode[STIX]{x1D6FD}>0$
be a real number such that
$r=\unicode[STIX]{x1D6FD}/\unicode[STIX]{x1D6FC}$
satisfies (3.11). Let
$0\leqslant m<n$
and define
$$\begin{eqnarray}S_{1}=\mathop{\sum }_{i=m+1}^{n}\unicode[STIX]{x1D6FD}^{i}\left(\mathop{\sum }_{k=m+1}^{i}\frac{\binom{i}{k}\binom{k-c_{1}}{k}}{\binom{n+c_{1}-1}{k}}\right)\frac{a^{(i)}(0)}{i!}.\end{eqnarray}$$
Then
$$\begin{eqnarray}\displaystyle & & \displaystyle |S_{1}|~\ll _{m}~\binom{n+c_{2}-1}{n}r^{n}\biggl(n\ln (n)+\frac{2n}{c_{1}}\biggr)\nonumber\\ \displaystyle & & \displaystyle +\,\biggl(\frac{r}{n}\biggr)^{m+1}(c_{2}+m)_{m+1}(1-r)^{-c_{2}}(1+c_{2}r).\end{eqnarray}$$
For
$m=0$
, the implicit constant in (8.26) is (at most)
$24$
.
Proof. We split
$S_{1}=S^{\prime }+S^{\prime \prime }$
into two parts, according to
$i=n$
and
$i<n$
:
$$\begin{eqnarray}\displaystyle S^{\prime } & = & \displaystyle \unicode[STIX]{x1D6FD}^{n}\left(\mathop{\sum }_{k=m+1}^{n}\frac{\binom{n}{k}\binom{k-c_{1}}{k}}{\binom{n+c_{1}-1}{k}}\right)\frac{a^{(n)}(0)}{n!},\end{eqnarray}$$
$$\begin{eqnarray}\displaystyle S^{\prime \prime } & = & \displaystyle \mathop{\sum }_{i=m+1}^{n-1}\unicode[STIX]{x1D6FD}^{i}\left(\mathop{\sum }_{k=m+1}^{i}\frac{\binom{i}{k}\binom{k-c_{1}}{k}}{\binom{n+c_{1}-1}{k}}\right)\frac{a^{(i)}(0)}{i!}.\end{eqnarray}$$
By Lemmas 8.2 and 8.3, we obtain
$$\begin{eqnarray}\displaystyle |S^{\prime }| & {\leqslant} & \displaystyle \unicode[STIX]{x1D6FD}^{n}\biggl(n\ln (n)+\frac{2n}{c_{1}}\biggr)\frac{\unicode[STIX]{x1D6FC}^{-n}(c_{2}+n-1)_{n}}{n!}\nonumber\\ \displaystyle & = & \displaystyle \binom{n+c_{2}-1}{n}r^{n}\biggl(n\ln (n)+\frac{2n}{c_{1}}\biggr).\end{eqnarray}$$
If
$m=n-1$
, we have
$S^{\prime \prime }=0$
. Otherwise, Lemmas 8.2 and 8.3 give
$$\begin{eqnarray}\displaystyle |S^{\prime \prime }| & {\leqslant} & \displaystyle \frac{1}{(n+c_{1}-1)_{m+1}}\mathop{\sum }_{i=m+1}^{n-1}\unicode[STIX]{x1D6FD}^{i}(i)_{m+1}(i-m)\unicode[STIX]{x1D6FC}^{-i}\binom{c_{2}+i-1}{i}\nonumber\\ \displaystyle & = & \displaystyle \frac{1}{(n+c_{1}-1)_{m+1}}\mathop{\sum }_{i=m+1}^{n-1}r^{i}(i)_{m+1}(i-m)\binom{c_{2}+i-1}{i}.\end{eqnarray}$$
We bound the sum in (8.30) from above by the infinite series
$$\begin{eqnarray}\mathop{\sum }_{i=m+1}^{\infty }r^{i}(i)_{m+1}(i-m)\binom{c_{2}+i-1}{i}.\end{eqnarray}$$
We can compute (8.31). We differentiate the identity
$$\begin{eqnarray}\mathop{\sum }_{i\geqslant 0}(-x)^{i}\binom{c_{2}+i-1}{i}=(1+x)^{-c_{2}}\end{eqnarray}$$
$m+1$
times, multiply by
$x^{m+1}$
and obtain
$$\begin{eqnarray}\mathop{\sum }_{i\geqslant m+1}(-x)^{i}(i)_{m+1}\binom{c_{2}+i-1}{i}=(-c_{2})_{m+1}x^{m+1}(1+x)^{-c_{2}-m-1}.\end{eqnarray}$$
We apply the linear operator
$f\mapsto x\cdot f^{\prime }-m\cdot f$
to both sides of (8.33):
$$\begin{eqnarray}\displaystyle & & \displaystyle \mathop{\sum }_{i\geqslant m+1}(-x)^{i}(i)_{m+1}(i-m)\binom{c_{2}+i-1}{i}\nonumber\\ \displaystyle & & \displaystyle =(-c_{2})_{m+1}x^{m+1}(1+x)^{-c_{2}-m-1}\biggl(1-(c_{2}+m+1)\frac{x}{1+x}\biggr).\end{eqnarray}$$
We plug
$x=-r$
in (8.34) and find the following formula for (8.31):
$$\begin{eqnarray}(-c_{2})_{m+1}(-r)^{m+1}(1-r)^{-c_{2}-m-1}\biggl(1+\frac{r}{1-r}(c_{2}+m+1)\biggr).\end{eqnarray}$$
Dividing (8.35) by the denominator appearing in (8.30), we obtain the following upper bound on
$|S^{\prime \prime }|$
:
$$\begin{eqnarray}|S^{\prime \prime }|\leqslant \frac{(c_{2}+m)_{m+1}}{(n+c_{1}-1)_{m+1}}\biggl(\frac{r}{1-r}\biggr)^{m+1}(1-r)^{-c_{2}}\biggl(1+\frac{r}{1-r}(c_{2}+m+1)\biggr).\end{eqnarray}$$
Using (3.11) and the estimate
$(n+c_{1}-1)_{m+1}=\unicode[STIX]{x1D6FA}_{m}(n^{m+1})$
, we may simplify (8.36) as
$$\begin{eqnarray}|S^{\prime \prime }|~\ll _{m}~\biggl(\frac{r}{n}\biggr)^{m+1}(c_{2}+m)_{m+1}(1-r)^{-c_{2}}(1+c_{2}r).\end{eqnarray}$$
By combining (8.29) and (8.37), we establish (8.26).
Now we assume that
$m=0$
. If
$n=1$
, we have
$S^{\prime \prime }=0$
. Otherwise, plugging
$m=0$
in (8.36), we obtain
$$\begin{eqnarray}|S^{\prime \prime }|\leqslant \frac{c_{2}r}{n}(1-r)^{-c_{2}}\frac{n}{n+c_{1}-1}\frac{1+c_{2}r}{(1-r)^{2}}.\end{eqnarray}$$
Since
$n/(n+c_{1}-1)\leqslant 2$
and (3.11) implies that
$(1+c_{2}r)/(1-r)^{2}\leqslant (1+c_{2}r)/(1-1/\sqrt{2})^{2}\leqslant 12(1+c_{2}r)$
, equation (8.38) implies that
$$\begin{eqnarray}|S^{\prime \prime }|\leqslant 24\frac{c_{2}r}{n}(1-r)^{-c_{2}}(1+c_{2}r).\end{eqnarray}$$
By (8.29) and (8.39), we find that the implicit constant in (8.26) is at most 24, as needed. ◻
8.3 Integral bound
Lemma 8.6. Let
$a(x)=\exp (\sum _{n\geqslant 1}(\widetilde{a_{n}}x^{n}/n))=\sum a_{n}x^{n}$
be a power series satisfying (3.12) for some
$\unicode[STIX]{x1D6FC},c_{2}>0$
. Let
$\unicode[STIX]{x1D6FD}>0$
be a real number such that
$r=\unicode[STIX]{x1D6FD}/\unicode[STIX]{x1D6FC}$
satisfies (3.11). Let
$0\leqslant m<n$
. Define
$$\begin{eqnarray}S_{2}=\mathop{\sum }_{k=0}^{m}\frac{\binom{k-c_{1}}{k}}{\binom{n+c_{1}-1}{k}}\frac{\unicode[STIX]{x1D6FD}^{k}}{k!}\int _{0}^{\unicode[STIX]{x1D6FD}}\frac{(\unicode[STIX]{x1D6FD}-x)^{n-k}}{(n-k)!}a^{(n+1)}(x)\,dx.\end{eqnarray}$$
Then
$$\begin{eqnarray}|S_{2}|~\ll _{m}~\binom{n+c_{2}-1}{n}r^{n}(1+c_{2}r)(1-r)^{-c_{2}}.\end{eqnarray}$$
For
$m=0$
, the implicit constant in (8.41) is (at most)
$12$
.
Proof. In (8.40), we replace
$\binom{k-c_{1}}{k}$
by the upper bound
$1$
and
$\binom{n+c_{1}-1}{k}$
by the lower bound
$\binom{n-1}{k}$
:
$$\begin{eqnarray}\displaystyle |S_{2}| & {\leqslant}\mathop{\sum }_{k=0}^{m}\frac{1}{\binom{n-1}{k}}\frac{\unicode[STIX]{x1D6FD}^{n}}{k!}\int _{0}^{\unicode[STIX]{x1D6FD}}\frac{(1-x/\unicode[STIX]{x1D6FD})^{n-k}}{(n-k)!}|a^{(n+1)}(x)|\,dx. & \displaystyle\end{eqnarray}$$
We use Lemma 8.3 to replace the number
$|a^{(n+1)}(x)|$
appearing in the integrand of (8.42) with
$(c_{2}+n)_{n+1}(1-x/\unicode[STIX]{x1D6FC})^{-c_{2}-n-1}\unicode[STIX]{x1D6FC}^{-n-1}$
:
$$\begin{eqnarray}\displaystyle |S_{2}| & {\leqslant} & \displaystyle \mathop{\sum }_{k=0}^{m}\frac{1}{\binom{n-1}{k}}\frac{\unicode[STIX]{x1D6FD}^{n}}{k!}\int _{0}^{\unicode[STIX]{x1D6FD}}\frac{(1-x/\unicode[STIX]{x1D6FD})^{n-k}}{(n-k)!}(c_{2}+n)_{n+1}\unicode[STIX]{x1D6FC}^{-n-1}\biggl(1-\frac{x}{\unicode[STIX]{x1D6FC}}\biggr)^{-c_{2}-n-1}\,dx\nonumber\\ \displaystyle & = & \displaystyle \mathop{\sum }_{k=0}^{m}\frac{(c_{2}+n)_{n+1}}{\binom{n-1}{k}k!(n-k)!}\unicode[STIX]{x1D6FD}^{n}\unicode[STIX]{x1D6FC}^{-n-1}\int _{0}^{\unicode[STIX]{x1D6FD}}\biggl(1-\frac{x}{\unicode[STIX]{x1D6FD}}\biggr)^{n-k}\biggl(1-\frac{x}{\unicode[STIX]{x1D6FC}}\biggr)^{-c_{2}-n-1}\,dx.\nonumber\\ \displaystyle & & \displaystyle\end{eqnarray}$$
We simplify the expression outside the integral:
$$\begin{eqnarray}\displaystyle \frac{(c_{2}+n)_{n+1}}{\binom{n-1}{k}k!(n-k)!}\unicode[STIX]{x1D6FD}^{n}\unicode[STIX]{x1D6FC}^{-n-1} & = & \displaystyle \binom{c_{2}+n}{n+1}(n+1)n\cdot r^{n+1}\cdot \frac{\unicode[STIX]{x1D6FD}^{-1}}{n-k}\nonumber\\ \displaystyle & = & \displaystyle \binom{n+c_{2}-1}{n}n((n+c_{2})r)\cdot r^{n}\cdot \frac{\unicode[STIX]{x1D6FD}^{-1}}{n-k}\nonumber\\ \displaystyle & {\leqslant} & \displaystyle \binom{n+c_{2}-1}{n}(1+c_{2}r)n^{2}\cdot r^{n}\cdot \frac{\unicode[STIX]{x1D6FD}^{-1}}{n-k}.\end{eqnarray}$$
Plugging (8.44) back in (8.43), we see
$$\begin{eqnarray}\displaystyle |S_{2}| & {\leqslant} & \displaystyle \binom{n+c_{2}-1}{n}(1+c_{2}r)n^{2}\nonumber\\ \displaystyle & & \displaystyle \cdot \,r^{n}\mathop{\sum }_{k=0}^{m}\int _{0}^{\unicode[STIX]{x1D6FD}}\frac{1}{n-k}\biggl(1-\frac{x}{\unicode[STIX]{x1D6FD}}\biggr)^{n-k}\biggl(1-\frac{x}{\unicode[STIX]{x1D6FC}}\biggr)^{-c_{2}-n-1}\frac{dx}{\unicode[STIX]{x1D6FD}}.\end{eqnarray}$$
We perform the change of variables
$s:=x/\unicode[STIX]{x1D6FD}$
in the right-hand side of (8.45), and obtain
$$\begin{eqnarray}\displaystyle |S_{2}| & {\leqslant} & \displaystyle \binom{n+c_{2}-1}{n}(1+c_{2}r)n^{2}\nonumber\\ \displaystyle & & \displaystyle \cdot \,r^{n}\mathop{\sum }_{k=0}^{m}\int _{0}^{1}\frac{(1-s)^{n-k}}{n-k}(1-rs)^{-c_{2}-n-1}\,ds.\end{eqnarray}$$
We rewrite the integrand
$((1-s)^{n-k}/(n-k))(1-rs)^{-c_{2}-n-1}$
as
$$\begin{eqnarray}\frac{1}{n-k}\biggl(\frac{1-s}{1-rs}\biggr)^{n-k}(1-rs)^{-c_{2}-k-1}.\end{eqnarray}$$
We apply two basic inequalities to (8.47), which hold for
$s\in [0,1]$
:
$0\leqslant (1-s)/(1-rs)\leqslant 1+s(r-1)$
and
$(1-rs)^{-1}\leqslant (1-r)^{-1}$
. This allows us to bound the right-hand side of (8.46) from above by
$$\begin{eqnarray}\binom{n+c_{2}-1}{n}(1+c_{2}r)n^{2}\cdot r^{n}\mathop{\sum }_{k=0}^{m}\frac{1}{n-k}(1-r)^{-c_{2}-k-1}\int _{0}^{1}(1+s(r-1))^{n-k}\,ds.\end{eqnarray}$$
The integral in (8.48) can be evaluated precisely as
$((1-r^{n-k+1})/(1-r))(1/(n-k+1))$
, which we bound from above by
$1/(1-r)(n-k+1)$
. Thus, we obtain
$$\begin{eqnarray}\displaystyle |S_{2}| & {\leqslant} & \displaystyle \binom{n+c_{2}-1}{n}(1+c_{2}r)n^{2}\nonumber\\ \displaystyle & & \displaystyle \cdot \,r^{n}\mathop{\sum }_{k=0}^{m}\frac{1}{(n-k)(n-k+1)}(1-r)^{-c_{2}-k-2}.\end{eqnarray}$$
Since
$k\leqslant m$
, we may replace
$(1-r)^{-c_{2}-k-2}$
in (8.49) by
$(1-r)^{-c_{2}-m-2}$
:
$$\begin{eqnarray}\displaystyle |S_{2}| & {\leqslant} & \displaystyle \binom{n+c_{2}-1}{n}(1+c_{2}r)n^{2}\nonumber\\ \displaystyle & & \displaystyle \cdot \,r^{n}(1-r)^{-c_{2}-m-2}\mathop{\sum }_{k=0}^{m}\frac{1}{(n-k)(n-k+1)}.\end{eqnarray}$$
The sum in (8.50) telescopes as follows:
$$\begin{eqnarray}\displaystyle \mathop{\sum }_{k=0}^{m}\frac{1}{(n-k)(n-k+1)} & = & \displaystyle \mathop{\sum }_{k=0}^{m}\biggl(\frac{1}{n-k}-\frac{1}{n-k+1}\biggr)\nonumber\\ \displaystyle & = & \displaystyle \frac{1}{n-m}-\frac{1}{n+1}=\frac{1+m}{(n-m)(n+1)}.\end{eqnarray}$$
Thus, equation (8.50) becomes
$$\begin{eqnarray}|S_{2}|\leqslant \binom{n+c_{2}-1}{n}(1+c_{2}r)\frac{n(1+m)}{n-m}r^{n}(1-r)^{-c_{2}-m-2}.\end{eqnarray}$$
Since
$n(1+m)/(n-m)\leqslant (1+m)^{2}~\ll _{m}~1$
and
$r\leqslant 1/\sqrt{2}$
by (3.11), the bound (8.52) may be simplified as
$$\begin{eqnarray}|S_{2}|~\ll _{m}~\binom{n+c_{2}-1}{n}r^{n}(1+c_{2}r)(1-r)^{-c_{2}},\end{eqnarray}$$
where the implied constant is
$(1+m)^{2}(1-1/\sqrt{2})^{-m-2}$
. This establishes (8.41). For
$m=0$
, the implied constant is less than
$12$
.◻
8.4 Proof of Theorem 3.3
Proof. Recall
$b_{n}=[x^{n}](1-x/\unicode[STIX]{x1D6FD})^{-c_{1}}=(-1/\unicode[STIX]{x1D6FD})^{n}\binom{-c_{1}}{n}=\unicode[STIX]{x1D6FD}^{-n}\binom{n+c_{1}-1}{n}$
. We have
$$\begin{eqnarray}\displaystyle f_{n} & = & \displaystyle \mathop{\sum }_{i=0}^{n}a_{i}b_{n-i}=\mathop{\sum }_{i=0}^{n}\frac{a^{(i)}(0)}{i!}\cdot \biggl(-\frac{1}{\unicode[STIX]{x1D6FD}}\biggr)^{n-i}\binom{-c_{1}}{n-i}\nonumber\\ \displaystyle & = & \displaystyle \biggl(-\frac{1}{\unicode[STIX]{x1D6FD}}\biggr)^{n}\binom{-c_{1}}{n}\mathop{\sum }_{i=0}^{n}\biggl(-\frac{1}{\unicode[STIX]{x1D6FD}}\biggr)^{-i}\frac{\binom{-c_{1}}{n-i}}{\binom{-c_{1}}{n}}\frac{a^{(i)}(0)}{i!}\nonumber\\ \displaystyle & = & \displaystyle b_{n}\cdot \left(\mathop{\sum }_{i=0}^{n}\unicode[STIX]{x1D6FD}^{i}(-1)^{i}\frac{\binom{-c_{1}}{n-i}}{\binom{-c_{1}}{n}}\frac{a^{(i)}(0)}{i!}\right).\end{eqnarray}$$
By Lemma 8.1, we may replace
$(-1)^{i}\big(\binom{-c_{1}}{n-i}/\binom{-c_{1}}{n}\big)$
in (8.54) with
$\sum _{k=0}^{i}\big(\binom{i}{k}\binom{k-c_{1}}{k}/\binom{n+c_{1}-1}{k}\big)$
and split the sum according to small and large
$k$
:
$$\begin{eqnarray}\displaystyle f_{n} & = & \displaystyle b_{n}\cdot \mathop{\sum }_{i=0}^{n}\unicode[STIX]{x1D6FD}^{i}\left(\mathop{\sum }_{k=0}^{i}\frac{\binom{i}{k}\binom{k-c_{1}}{k}}{\binom{n+c_{1}-1}{k}}\right)\frac{a^{(i)}(0)}{i!}\nonumber\\ \displaystyle & = & \displaystyle b_{n}\cdot \mathop{\sum }_{i=0}^{n}\unicode[STIX]{x1D6FD}^{i}\left(\mathop{\sum }_{k=0}^{m}\frac{\binom{i}{k}\binom{k-c_{1}}{k}}{\binom{n+c_{1}-1}{k}}\right)\frac{a^{(i)}(0)}{i!}\nonumber\\ \displaystyle & & \displaystyle +\,b_{n}\cdot \mathop{\sum }_{i=m+1}^{n}\unicode[STIX]{x1D6FD}^{i}\left(\mathop{\sum }_{k=m+1}^{i}\frac{\binom{i}{k}\binom{k-c_{1}}{k}}{\binom{n+c_{1}-1}{k}}\right)\frac{a^{(i)}(0)}{i!}.\end{eqnarray}$$
We denote the first sum by
$S_{0}$
and the second sum by
$S_{1}$
:
$$\begin{eqnarray}\begin{array}{@{}rcl@{}}S_{0}\ & =\ & \displaystyle \mathop{\sum }_{i=0}^{n}\unicode[STIX]{x1D6FD}^{i}\left(\mathop{\sum }_{k=0}^{m}\frac{\binom{i}{k}\binom{k-c_{1}}{k}}{\binom{n+c_{1}-1}{k}}\right)\frac{a^{(i)}(0)}{i!},\\ S_{1}\ & =\ & \displaystyle \mathop{\sum }_{i=m+1}^{n}\unicode[STIX]{x1D6FD}^{i}\left(\mathop{\sum }_{k=m+1}^{i}\frac{\binom{i}{k}\binom{k-c_{1}}{k}}{\binom{n+c_{1}-1}{k}}\right)\frac{a^{(i)}(0)}{i!}.\end{array}\end{eqnarray}$$
We rearrange the terms of
$S_{0}$
as follows:
$$\begin{eqnarray}\displaystyle S_{0} & = & \displaystyle \mathop{\sum }_{k=0}^{m}\frac{\binom{k-c_{1}}{k}}{\binom{n+c_{1}-1}{k}}\mathop{\sum }_{i=k}^{n}\binom{i}{k}\frac{a^{(i)}(0)}{i!}\unicode[STIX]{x1D6FD}^{i}\nonumber\\ \displaystyle & = & \displaystyle \mathop{\sum }_{k=0}^{m}\frac{\binom{k-c_{1}}{k}}{\binom{n+c_{1}-1}{k}}\frac{\unicode[STIX]{x1D6FD}^{k}}{k!}\mathop{\sum }_{j=0}^{n-k}\frac{a^{(j+k)}(0)}{j!}\unicode[STIX]{x1D6FD}^{j}.\end{eqnarray}$$
Let
$$\begin{eqnarray}\begin{array}{@{}rcl@{}}M\ & =\ & \displaystyle \mathop{\sum }_{k=0}^{m}\frac{\binom{k-c_{1}}{k}}{\binom{n+c_{1}-1}{k}}\frac{\unicode[STIX]{x1D6FD}^{k}}{k!}a^{(k)}(\unicode[STIX]{x1D6FD}),\\ S_{2}\ & =\ & \displaystyle \mathop{\sum }_{k=0}^{m}\frac{\binom{k-c_{1}}{k}}{\binom{n+c_{1}-1}{k}}\frac{\unicode[STIX]{x1D6FD}^{k}}{k!}\int _{0}^{\unicode[STIX]{x1D6FD}}\frac{(\unicode[STIX]{x1D6FD}-x)^{n-k}}{(n-k)!}a^{(n+1)}(x)\,dx.\end{array}\end{eqnarray}$$
By the integral formula for the remainder in a Taylor series, we may replace
$\sum _{j=0}^{n-k}(a^{(j+k)}(0)/j!)\unicode[STIX]{x1D6FD}^{j}$
in (8.57) with
$$\begin{eqnarray}a^{(k)}(\unicode[STIX]{x1D6FD})-\int _{0}^{\unicode[STIX]{x1D6FD}}\frac{(\unicode[STIX]{x1D6FD}-x)^{n-k}}{(n-k)!}a^{(n+1)}(x)\,dx,\end{eqnarray}$$
and obtain
$$\begin{eqnarray}S_{0}=M-S_{2}.\end{eqnarray}$$
Summarizing (8.55) and (8.59), we see
$$\begin{eqnarray}\displaystyle f_{n}=b_{n}\cdot (M+S_{1}-S_{2}). & & \displaystyle\end{eqnarray}$$
Note that
$b_{n}\cdot M$
is the main term of (3.13). The expression
$E$
, as defined in (3.13), equals
$S_{1}-S_{2}$
. The sums
$S_{1}$
,
$S_{2}$
are bounded in Lemmas 8.5 and 8.6, respectively, and these bounds give
$$\begin{eqnarray}\displaystyle |E| & ~\ll _{m}\ & \displaystyle \biggl(\frac{r}{n}\biggr)^{m+1}(1-r)^{-c_{2}}(1+c_{2}r)(c_{2}+m)_{m+1}\nonumber\\ \displaystyle & & \displaystyle +\,\binom{n+c_{2}-1}{n}r^{n}\biggl(n\ln (n)+\frac{2n}{c_{1}}+(1-r)^{-c_{2}}(1+c_{2}r)\biggr).\end{eqnarray}$$
We simplify (8.61) using the following two inequalities:
$$\begin{eqnarray}1+c_{2}r\leqslant \exp (c_{2}r),\end{eqnarray}$$
and, since
$-\!\ln (1-r)\leqslant 2r$
for
$0\leqslant r\leqslant 1/\sqrt{2}$
by simple calculus, we have
$$\begin{eqnarray}(1-r)^{-c_{2}}=\exp (-c_{2}\ln (1-r))\leqslant \exp (2c_{2}r).\end{eqnarray}$$
Plugging (8.62) and (8.63) into (8.61), we obtain
$$\begin{eqnarray}\displaystyle |E| & ~\ll _{m}\ & \displaystyle \biggl(\frac{r}{n}\biggr)^{m+1}\exp (3c_{2}r)(c_{2}+m)_{m+1}\nonumber\\ \displaystyle & & \displaystyle +\,\binom{n+c_{2}-1}{n}r^{n}\biggl(n\ln (n)+\frac{2n}{c_{1}}+\exp (3c_{2}r)\biggr).\end{eqnarray}$$
We note that
$$\begin{eqnarray}n\ln (n)+\frac{2n}{c_{1}}+\exp (3c_{2}r)\leqslant \exp (3c_{2}r)\frac{4n^{2}}{c_{1}}.\end{eqnarray}$$
Plugging (8.65) into (8.64), we obtain
$$\begin{eqnarray}|E|~\ll _{m}~\exp (3c_{2}r)\biggl(\biggl(\frac{r}{n}\biggr)^{m+1}(c_{2}+m)_{m+1}+\binom{n+c_{2}-1}{n}\frac{4n^{2}}{c_{1}}r^{n}\biggr),\end{eqnarray}$$
as needed. For
$m=0$
, the implied coefficient is the maximum of the two implied constants of Lemmas 8.5 and 8.6, i.e. 24.◻
8.5 Proof of Corollary 3.4
We apply Theorem 3.3 with
$m=0$
, and obtain
$$\begin{eqnarray}|E|\ll \exp (3c_{2}r)\biggl(\frac{c_{2}r}{n}+\binom{n+c_{2}-1}{n}\frac{4n^{2}}{c_{1}}r^{n}\biggr),\end{eqnarray}$$
where the implied constant is 24. We find a range of
$n$
where the first term of the right-hand side of (8.67) dominates the error, i.e. we want to solve
$$\begin{eqnarray}\frac{c_{2}r}{n}\geqslant \binom{n+c_{2}-1}{n}\frac{4n^{2}}{c_{1}}r^{n}.\end{eqnarray}$$
For
$n$
for which (8.68) holds, equation (3.17) holds with an implied constant (at most)
$24+24=48$
. We find a range of
$n$
for which (8.68) holds by making several simplifications. Note that
$$\begin{eqnarray}\displaystyle \binom{n+c_{2}-1}{n}n^{2} & = & \displaystyle \binom{n+c_{2}-1}{n-1}c_{2}n=\mathop{\prod }_{i=1}^{n-1}\biggl(1+\frac{c_{2}}{i}\biggr)c_{2}n\nonumber\\ \displaystyle & {\leqslant} & \displaystyle \exp \biggl(c_{2}\mathop{\sum }_{i=1}^{n-1}\frac{1}{i}\biggr)c_{2}n\leqslant \exp (c_{2}(\ln (n)+1))c_{2}n\nonumber\\ \displaystyle & = & \displaystyle (ne)^{c_{2}+1}\frac{c_{2}}{e},\end{eqnarray}$$
so we may replace (8.68) by the following stricter inequality:
$$\begin{eqnarray}\frac{r}{n}\geqslant (ne)^{c_{2}+1}\frac{1}{c_{1}}\frac{4}{e}r^{n},\end{eqnarray}$$
or, equivalently,
$$\begin{eqnarray}\biggl(\frac{1}{r}\biggr)^{n-1}\geqslant (ne)^{c_{2}+2}\frac{1}{c_{1}}\frac{4}{e^{2}}.\end{eqnarray}$$
Inequality (8.71) holds when the following two inequalities hold simultaneously:
$$\begin{eqnarray}\biggl(\frac{1}{r}\biggr)^{(n-1)/2}\geqslant (ne)^{c_{2}+2},\qquad \biggl(\frac{1}{r}\biggr)^{(n-1)/2}\geqslant \frac{1}{c_{1}}.\end{eqnarray}$$
The first inequality of (8.72) holds whenever
$(n-1)/(\ln (n)+1)\geqslant (2c_{2}+4)/\ln (1/r)$
, which, by Lemma 8.4, is satisfied when
$$\begin{eqnarray}n\geqslant 1+5\biggl(\frac{2c_{2}+4}{\ln (1/r)}+1\biggr)\ln \biggl(\frac{2c_{2}+4}{\ln (1/r)}+1\biggr).\end{eqnarray}$$
The second inequality of (8.72) holds whenever
$n\geqslant 2\ln (c_{1}^{-1})/\!\ln (1/r)+1$
. This establishes Corollary 3.4.
Acknowledgements
I thank my advisor, Lior Bary-Soroker, for introducing me to Landau’s theorem, for helpful discussions and for teaching me, patiently, how to write. Also, I thank Amotz Oppenheim and Zeév Rudnick for their useful comments on this paper, Mikhail Sodin for a helpful discussion related to the analytic part of the paper, and the anonymous referee for her/his valuable remarks. This research was partially supported by the Israel Science Foundation grants no. 952/14 and no. 382/15.
