# Friable permutations and polynomials revisited

Ofir Gorodetsky

###### Abstract

We prove various optimal estimates for the counts of friable (i.e. smooth)
permutations and friable polynomials over finite fields.

In particular, for both permutations and polynomials we prove a result with an
error term that, for the first time, matches the error term found in the
integer setting by de Bruijn more than 70 years ago. The main term is the
usual Dickman $\rho$ function, but with its argument shifted.

Additionally, for permutations, we determine the order of magnitude of
$\log(p_{n,m}/\rho(n/m))$ throughout the range $1\leq n\leq m$ where $p_{n,m}$
is the probability that a permutation on $n$ elements, chosen uniformly at
random, is $m$-friable.

We also uncover a phase transition in the polynomial setting. We show that the
probability that a polynomial of degree $n$ in $\mathbb{F}_{q}$ is $m$-friable
shifts its behavior at $m\approx(3/2)\log_{q}n$. Previously, phase transitions
were only known to occur at $m\approx 2\log_{q}n$ and $m\approx\log_{q}n$.

##  1 Introduction

###  1.1 Background on friable permutations

A permutation is said to be $m$-friable (or $m$-smooth) if it has no cycles of
length greater than $m$. Let

$p_{n,m}:=\mathbb{P}_{\pi\in S_{n}}(\pi\text{ is }m\text{-friable})$

be the probability that a permutation from $S_{n}$ chosen uniformly at random
is $m$-friable. Let

$u:=\frac{n}{m}$

and let $\rho\colon[0,\infty)\to(0,\infty)$ be the Dickman function, defined
via the delay differential equation

$t\rho^{\prime}(t)+\rho(t-1)=0$

for $t\geq 1$ with initial conditions $\rho(t)=1$ for $t\in[0,1]$. It is
decreasing, and de Bruijn proved that it satisfies

$\rho(u)=\exp\left(-u\log(u\log u)+u+O\left(\frac{u\log\log u}{\log
u}\right)\right)$ (1.1)

uniformly for $u\geq 3$ [dB51a]. Goncharov [Gon44] established a connection
between $p_{n,m}$ and $\rho$, showing that

$p_{n,m}\sim\rho(u)$

as $n\to\infty$ and $u=O(1)$.

Manstavičius and Petuchovas [MP16] established asymptotic results for
$p_{n,m}$ in the entire range $1\leq m\leq n$. Before their work, the only
asymptotic results on $p_{n,m}$, apart from Goncharov’s, concerned either
bounded $m$, or $u$ tending very slowly to $\infty$. We refer the reader to
the introductions of [MP16, For22] for surveys on $p_{n,m}$.

The main goal of this note is to improve and extend some of the results of
Manstavičius and Petuchovas and to draw various new conclusions. The
motivation for this is a recent work of the present author, which allows one
to reduce questions about friable polynomials to questions about friable
permutations [Gor22b]. Indeed, in §1.4 we draw new conclusions about friable
polynomials from our results on friable permutations. The secondary goal of
this note is to improve some of the results of [Gor22b]; see §1.4 for these.

We first survey the results of Manstavičius and Petuchovas and some related
recent works. In [MP16, Thm. 4] the authors showed using complex analytic
methods that

$p_{n,m}=\rho(u)\left(1+O\left(\frac{u\log(u+1)}{m}\right)\right)$ (1.2)

uniformly for $n\geq m\geq\sqrt{n\log n}$. Recently, Ford [For22, Thm. 1.17]
proved (with real analysis only) that

$\rho\left(\frac{n}{m}\right)\leq p_{n,m}\leq\rho\left(\frac{n+1}{m+1}\right)$
(1.3)

holds uniformly for $n\geq m\geq 1$, which almost immediately leads to the
following extension of (1.2):

$p_{n,m}=\rho(u)\exp\left(O\left(\frac{u\log(u+1)}{m}\right)\right),$ (1.4)

uniformly for $n\geq m\geq 1$, see [Gor22b, Prop. 1.8] for details.

The estimate (1.4) gives an asymptotic result only when $m/\sqrt{n\log n}$
tends to $\infty$. It turns out that (1.4) is optimal. Manstavičius and
Petuchovas have shown that

$p_{n,m}=\rho(u)\exp\left(\frac{u\xi(u)}{2m}\right)\left(1+O\left(\frac{u\log^{2}(u+1)}{m^{2}}+\frac{1}{u}\right)\right)$
(1.5)

holds for $m\geq n^{1/3}(\log n)^{2/3}$, where $\xi(u)$ is a function of $u$,
defined via $e^{\xi(u)}=1+u\xi(u)$, and it is asymptotic to $\log u$ as
$u\to\infty$; see Corollaries 3 and 5 in [MP16]. In particular,
$p_{n,m}\sim\rho(u)$ _does not_ hold for $m\asymp\sqrt{n\log n}$.

The phase transition at $m\asymp\sqrt{n\log n}$ was partially anticipated
before [MP16] by Example 6 of [GHS15], where the lower bound

$p_{n,m}\geq\rho(u)\exp\left(\frac{c\lfloor u\rfloor}{m}\right),$ (1.6)

uniformly in $n\geq m\geq 1$ for some $c>0$, is stated without proof. In
[Gor22b, App.] the present author showed, using real analysis, that

$p_{n,m}\geq\rho(u)\left(1+\frac{cu\log(u+1)}{m}\right)$ (1.7)

uniformly for $n/2\geq m\geq 1$. Note that (1.7) _does not_ follow from (1.5).
Indeed, in the range $m\gg n^{2/3}(\log n)^{1/3}$, (1.5) only tells us that
$p_{n,m}=\rho(u)(1+O(1/u))$.

For $1\leq m\leq\log n$, Manstavičius and Petuchovas proved the estimate
[MP16, Thm. 1]

$p_{n,m}=\frac{1}{\sqrt{2\pi nm}}\exp\left(-u\log
n+u+\sum_{i=1}^{m}d_{m,i}n^{1-\frac{i}{m}}\right)\left(1+O\left(n^{-1/m}\right)\right)$
(1.8)

where

$d_{m,m}=-\frac{1}{m}\sum_{j=2}^{m}\frac{1}{j},\qquad
d_{m,i}=\frac{\Gamma\left(i+\frac{i}{m}\right)}{(m-i)i!\Gamma\left(1+\frac{i}{m}\right)}\quad(1\leq
i\leq m-1).$

It gives an asymptotic result once $m=o(\log n)$.

Both (1.5) and (1.8) are consequences of their saddle point estimate for
$p_{n,m}$ [MP16, Thm. 2, Cor. 5], which states that

$p_{n,m}=\frac{\exp\left(\sum_{i=1}^{m}\frac{x^{i}}{i}\right)}{x^{n}\sqrt{2\pi\lambda}}\left(1+O\left(u^{-1}\right)\right)$
(1.9)

where $x=x_{n,m}$ is the saddle point defined as the unique positive solution
to

$\sum_{i=1}^{m}x^{i}=n$ (1.10)

and $\lambda=\lambda_{n,m}$ is defined as

$\lambda=\sum_{i=1}^{m}ix^{i}.$ (1.11)

If $m$ is sufficiently large, (1.9) simplifies to (1.5), while if $m$ is
sufficiently small it gives (1.8).

###  1.2 New results on permutations

We improve (1.5) in terms of error term and range.

######  Theorem 1.1.

Uniformly in $n\geq m\geq 1$ we have

$p_{n,m}=\rho(u)\exp\left(\frac{u\xi(u)}{2m}\right)\exp\left(O\left(\frac{u\log^{2}(u+1)}{m^{2}}+\frac{1}{u}\right)\right).$
(1.12)

If $\sqrt{n\log n}=O(m)$ then the following stronger estimate holds:

$p_{n,m}=\rho(u)\exp\left(\frac{u\xi(u)}{2m}\right)\left(1+O\left(\frac{\log(u+1)}{m}\right)\right).$
(1.13)

Our theorem recovers all the previous estimates that express $p_{n,m}$ in
terms of $\rho(u)$: (1.2), (1.4) and (1.5). The error term $O(\log(u+1)/m)$ in
(1.13) is of particular importance, as we now explain. We say that a positive
integer is $y$-friable if all its prime factors are at most $y$, and we set
$\Psi(x,y)=\\#\\{1\leq n\leq x:n\text{ is }y\text{-friable}\\}$. Setting
$n^{\prime}:=\log x$, $m^{\prime}:=\log y$ and
$u^{\prime}:=n^{\prime}/m^{\prime}$, de Bruijn [dB51b] showed that
$\Psi(x,y)=x\rho(u^{\prime})(1+O(\log(u^{\prime}+1)/m))$ in the range
$m^{\prime}\geq n^{\prime 5/8+\varepsilon}$. Estimate (1.13) is an analogue of
this, as it expresses $p_{n,m}$ in terms of the Dickman function with an error
term that matches that of de Bruijn. Past results that expressed $p_{n,m}$ in
terms of $\rho(u)$ had a worse error term by a factor of $u$. The proof of
Theorem 1.1 shows that the error term $O(\log(u+1)/m)$ is optimal, see (3.27).

We can restate Theorem 1.1 in a way that does not involve the function
$\xi(u)$, due to

######  Lemma 1.2.

Uniformly for $n\geq m\geq 1$ we have

$\rho\left(u\right)\exp\left(\frac{u\xi(u)}{2m}\right)=\rho\left(u-\frac{u}{2m}\right)\exp\left(O\left(\frac{u}{m^{2}}+\frac{1}{m}\right)\right).$
(1.14)

Consequently,

$p_{n,m}=\rho\left(\frac{n}{m}-\frac{n}{2m^{2}}\right)\left(1+O\left(\frac{\log(u+1)}{m}\right)\right)$

for $\sqrt{n\log n}=O(m)$, and

$p_{n,m}\sim\rho\left(\frac{n}{m}-\frac{n}{2m^{2}}\right)$ (1.15)

if $m/(n^{1/3}(\log n)^{2/3})\to\infty$. This is consistent with (1.3) in the
sense that $n/m-n/(2m^{2})$ lies between $(n+1)/(m+1)$ and $n/m$ if $u\gg 1$.

Next, we want to have a better understanding of $p_{n,m}$ in the regime
$m\asymp\log n$, and (1.8) falls just short of allowing that. Towards this, we
prove an extension of (1.8).

######  Lemma 1.3.

The estimate

$p_{n,m}=\frac{1}{\sqrt{2\pi nm}}\exp\left(-u\log
n+u+\sum_{i=1}^{m}d_{m,i}n^{1-\frac{i}{m}}+E\right)\left(1+O\left(\frac{1}{\max\\{\log
u,n^{1/m}\\}}\right)\right).$ (1.16)

holds uniformly for $n>m\geq 1$, where

$E\ll\frac{n^{-\frac{1}{m}}}{1-n^{-\frac{1}{m}}}+\frac{\frac{m}{n}}{1-\left(\frac{m}{n}\right)^{\frac{1}{m}}}.$

From Lemma 1.3 we are able deduce simple estimates for $p_{n,m}$ in the
regimes $m=o(\log n)$ and $m\asymp\log n$, with a multiplicative error of size
$\exp(o(u))$. Below and throughout, $\Theta(f)$ indicates a function $g$ such
that $cf\leq g\leq Cf$ for some positive constants $C>c>0$.

######  Corollary 1.4.

If $m=1$, then $p_{n,1}=(e/n)^{u}\exp(\Theta(\log n))$. If $2\leq m=o(\log n)$
as $n\to\infty$, then

$p_{n,m}=\left(\frac{e}{n}\right)^{u}\exp(\Theta(un^{-\frac{1}{m}}).$

If $2\leq m=O(\log n)$, then

$p_{n,m}=\left(\frac{e}{n}\right)^{u}\exp\left(u\left(-\log\left(1-n^{-\frac{1}{m}}\right)+o_{m\to\infty}(n^{-1/m})\right)\right).$
(1.17)

In particular, if $m=\Theta(\log n)$, then

$p_{n,m}=\left(\frac{e}{n}\right)^{u}\exp\left(u\left(-\log\left(1-n^{-\frac{1}{m}}\right)+o_{n\to\infty}(1)\right)\right)=\left(\frac{e}{n}\right)^{u}\exp(\Theta(u)).$

Here $o_{m\to\infty}(1)$ goes to $0$ as $m$ goes to $\infty$, and
$o_{m\to\infty}(n^{-1/m})=n^{-1/m}\cdot o_{m\to\infty}(1)$.

From (1.4) and Lemma 1.3 we see that $p_{n,m}$ experiences a phase transition
at $m\asymp\log n$: it is subexponential in $n$ if $m/\log n\to\infty$, decays
exponentially in $n$ if $m=\Theta(\log n)$ and decays superexponentially in
$n$ if $m=o(\log n)$.

Using Corollary 1.4 and Theorem 1.1 we are able determine the order of
magnitude of $\log(p_{n,m}/\rho(u))$. This is an optimal version of the
estimate (1.6) of Granville, Harper and Soundararajan.

######  Corollary 1.5.

Uniformly for $n\geq m\geq 1$ we have

$p_{n,m}=\rho(u)\exp\left(\Theta\left(u\log\left(1+\frac{\log
u}{m}\right)\right)\right).$

If $m=O(\log n)$ then, letting $t=(\log n)/m$, we have

$p_{n,m}=\rho(u)\exp\left(u\left(\log\frac{t}{1-e^{-t}}+o(1)\right)\right).$

###  1.3 Background on friable polynomials

A polynomial over a finite field $\mathbb{F}_{q}$ is said to be $m$-friable if
all its prime factors have degrees at most $m$. The study of friable
polynomials received much more attention than the permutation analogue due to
its connection with cryptography, see the introduction of [Gor22b] for a full
survey.

Let $\mathcal{M}_{n,q}$ be the set of monic polynomials of degree $n$ over
$\mathbb{F}_{q}$. We write $p_{n,m,q}$ for the probability that a polynomial
from $\mathcal{M}_{n,q}$ chosen uniformly at random is $m$-friable. As before,
we shall write $u$ for $n/m$. Manstavičius [Man92a, Thm. 2], improving on Car
[Car87] and Warlimont [War91], proved that

$p_{n,m,q}=\rho(u)\left(1+O\left(\frac{u\log(u+1)}{m}\right)\right)$ (1.18)

holds in range $n\geq m\geq\sqrt{n\log n}$. Recently, the author proved
several results comparing $p_{n,m,q}$ and $p_{n,q}$, which we explain below.
Fix $\varepsilon>0$. We have

$\frac{p_{n,m,q}}{p_{n,m}}=1+O_{\varepsilon}\left(\frac{un^{\frac{1+a}{m}}\min\\{m,\log(u+1)\\}}{mq^{\lceil\frac{m+1}{2}\rceil}}\right)$
(1.19)

uniformly for $n\geq m\geq(2+\varepsilon)\log_{q}n$, where
$a=\mathbf{1}_{2\mid m}$ by [Gor22b, Thms. 1, 2]. Let

$G_{q}(z):=\prod_{\begin{subarray}{c}P\in\mathcal{P}\\\ \deg(P)\leq
m\end{subarray}}\left(1-\left(\frac{z}{q}\right)^{\deg(P)}\right)^{-1}\exp\left(-\sum_{i=1}^{m}\frac{z^{i}}{i}\right),$
(1.20)

where $\mathcal{P}=\mathcal{P}_{q}$ is the set of monic irreducible
polynomials over $\mathbb{F}_{q}$. We have $G_{q}(z)\geq 1$ if $z\geq 0$. By
[Gor22b, Thm. 1.3] we have

$\frac{p_{n,m,q}}{p_{n,m}}=G_{q}(x)+O_{\varepsilon}\left(\frac{n^{\frac{1+a}{m}}\min\\{m,\log(u+1)\\}}{mq^{\lceil\frac{m+1}{2}\rceil}}\right)$
(1.21)

uniformly in the range $n/(\log n\log^{3}\log(n+1))\geq
m\geq(2+\varepsilon)\log_{q}n$, where $x=x_{n,m}$ is the saddle point defined
in (1.10). In this range, $G_{q}(x)=\Theta_{\varepsilon}(1)$. Moreover, by the
same theorem,.

$\frac{p_{n,m,q}}{p_{n,m}}=G_{q}(x)\left(1+O_{\varepsilon}\left(m\left(\frac{1}{q^{m/2}}+\frac{n^{3}}{q^{2m}}\right)\right)\right)$
(1.22)

uniformly for $(2+\varepsilon)\log_{q}n\geq m\geq(1+\varepsilon)\log_{q}n$
111Inspecting the proof, the error term that one gets is better if one
considers subranges of $(2+\varepsilon)\log_{q}n\geq
m\geq(1+\varepsilon)\log_{q}n$. In particular,
$p_{n,m,q}/p_{n,m}=G_{q}(x)(1+O_{\varepsilon}(n^{3}/(mq^{2m})))$ holds
uniformly in $(2-\varepsilon)\log_{q}n\geq m\geq(1+\varepsilon)\log_{q}n$..
Theorem 1.4 of [Gor22b] describes the behavior of $G_{q}(x)$. In particular,
$G_{q}(x)$ is asymptotic to $1$ if $m-2\log_{q}n$ tends to infinity and $\log
G_{q}(x)=\Theta_{q}(n^{\varepsilon+o(1)})$ if $m/\log_{q}n\to 2-\varepsilon$
as $n\to\infty$ $(\varepsilon\in(0,1)$). Lemma 5.4 of [Gor22b] shows more
precisely that $\log G_{q}(x)=\Theta_{q,\varepsilon}(n^{2}/(mq^{m}))$ for
$(1+\varepsilon)\log_{q}n\leq m\leq(2-\varepsilon)\log_{q}n$.

Beyond $m\approx\log_{q}n$, $p_{n,m,q}$ and $p_{n,m}$ are no longer
comparable: if $m\leq(1-\varepsilon)\log_{q}n$, the ratio $p_{n,m,q}/p_{n,m}$
is at least exponentially large in $n$.

We also mention that $p_{n,m,q}\geq p_{n,m}$ when $n\geq m\geq 1$ [Gor22b,
Prop. 1.5].

###  1.4 New results on polynomials

Due to (1.19), it follows immediately that our Theorem 1.1 and Lemma 1.2 imply

######  Corollary 1.6.

Uniformly for $n\geq m\geq(2+\varepsilon)\log_{q}n$ we have

$p_{n,m,q}=\rho\left(\frac{n}{m}-\frac{n}{2m^{2}}\right)\left(1+O\left(\frac{1}{u}+\frac{\log^{2}(u+1)}{m^{2}}\right)\right).$

If $\sqrt{n\log n}=O(m)$ then

$p_{n,m,q}=\rho\left(\frac{n}{m}-\frac{n}{2m^{2}}\right)\left(1+O\left(\frac{\log(u+1)}{m}\right)\right).$
(1.23)

Because the error in (1.13) is optimal, so is the error in (1.23). Again,
(1.23) matches, for the first time, the error term in de Bruijn’s work [dB51b]
in the integer setting, improving on [Car87, War91, Man92a].

We prove a new result for small $u$.

######  Theorem 1.7.

If $n\geq m\geq\sqrt{10n\log n}$ then

$\frac{p_{n,m,q}}{p_{n,m}}=G_{q}(e^{\xi/m})\left(1+O\left(\frac{\log(u+1)}{mq^{\lceil\frac{m+1}{2}\rceil}}\right)\right).$

In the range of Theorem 1.7 the quantities $G_{q}(x)$ and $G_{q}(e^{\xi/m})$
are very close:
$G_{q}(x)/G_{q}(e^{\xi/m})=1+O(u\log^{2}(u+1)/(m^{2}q^{\lceil(m+1)/2\rceil})$
(see (5.4)). It follows immediately that the condition $n/(\log
n\log^{3}\log(n+1))\geq m$ in (1.21) may be removed.

######  Corollary 1.8.

The estimate (1.21) holds uniformly for $n\geq m\geq(2+\varepsilon)\log_{q}n$.

Since
$G_{q}(x)-1=\Theta_{\varepsilon}(un^{(1+a)/m}\min\\{m,\log(u+1)\\}/(mq^{\lceil(m+1)/2\rceil}))$
uniformly for $n/3\geq m\geq(2+\varepsilon)\log_{q}n$ [Gor22b, Lem. 5.3], it
follows that the error term in (1.19) is optimal when $n\geq
m\geq(2+\varepsilon)\log_{q}n$ and $u\gg 1$.

In our next result we show that $p_{n,m,q}/p_{n,m}$ experiences a transition
in its behavior around $m\asymp(3/2)\log_{q}n$, and determine its behavior in
the range $(3/2)\log_{q}n\geq m\geq(1+\varepsilon)\log_{q}n$ which was not
treated in [Gor22b].

######  Theorem 1.9.

Fix a prime power $q$ and $\varepsilon>0$. For $(2-\varepsilon)\log_{q}n\geq
m\geq(1+\varepsilon)\log_{q}n$ we have

$\frac{p_{n,m,q}}{p_{n,m}}=(1+o(1))G_{q}(x)\exp\left(-\Theta_{q,\varepsilon}\left(\frac{n^{3}}{mq^{2m}}\right)\right)$
(1.24)

as $n\to\infty$.

In particular, if we fix $q$ then $p_{n,m,q}/p_{n,m}$ is asymptotic to
$G_{q}(x)$ if $m-(3/2)\log_{q}n+(1/2)\log_{q}\log n$ tends to $\infty$ and
this condition is optimal.

Our next result is a variation on Theorem 1.9 with a different main term,
namely $G_{q}(x_{q})$ instead of $G_{q}(x)$, where we now define $x_{q}$. Let

$F_{q}(z):=\prod_{\begin{subarray}{c}P\in\mathcal{P}\\\ \deg(P)\leq
m\end{subarray}}\left(1-\left(\frac{z}{q}\right)^{\deg(P)}\right)^{-1}$ (1.25)

be the generating function of $\\{p_{n,m,q}\\}_{n\geq 0}$, which is analytic
in $|z|<q$. We define $x_{q}:=x_{n,m,q}<q$ as the unique positive solution to
$zF_{q}^{\prime}(z)/F_{q}(z)=n$.

######  Theorem 1.10.

Fix a prime power $q$ and $\varepsilon>0$. For $(2-\varepsilon)\log_{q}n\geq
m\geq(1+\varepsilon)\log_{q}n$ we have

$\frac{p_{n,m,q}}{p_{n,m}}=(1+o(1))G_{q}(x_{q})\exp\left(\Theta_{q,\varepsilon}\left(\frac{n^{3}}{mq^{2m}}\right)\right)$
(1.26)

as $n\to\infty$, and

$\log G_{q}(x_{q})=\Theta_{q,\varepsilon}\left(\frac{n^{2}}{mq^{m}}\right).$

In the wider range $(2-\varepsilon)\log_{q}n\geq m\geq(3/4)\log_{q}n$ we have

$(1+o(1))G_{q}(x_{q})\exp\left(\frac{C_{q}(\min\\{n,q^{m}\\})^{2}n}{mq^{2m}}\frac{1}{\left(1-\frac{x_{q}}{q}\right)^{2}}\right)\geq\frac{p_{n,m,q}}{p_{n,m}}\geq(1+o(1))G_{q}(x_{q})\exp\left(\frac{c_{q}(\min\\{n,q^{m}\\})^{5}}{n^{2}mq^{2m}}\right)$

as $n\to\infty$, and

$\frac{(\min\\{n,q^{m}\\})^{2}}{mq^{m}}\frac{1}{1-\frac{x_{q}}{q}}\geq\log
G_{q}(x_{q})\geq\frac{(\min\\{n,q^{m}\\})^{2}}{mq^{m}}.$

######  Remark 1.

When $\log_{q}n>m\gg_{q}1$, Lemma 2.1 of [Man92b] shows
$1-x_{q}/q=\Theta_{q}(q^{m}/(nm))$.

In [Gor22b], we studied the ratio $p_{n,m,q}/p_{n,m}$ directly, with no
asymptotic input on either $p_{n,m,q}$ or $p_{n,m}$ themselves apart from a
lower bound on $p_{n,m}$. In Theorems 1.9 and 1.10 we need the saddle point
asymptotics for $p_{n,m}$ given in (1.9) and also the saddle point asymptotics
for $p_{n,m,q}$, investigated in [Man92b, Man92a].

Theorems 1.9 and 1.10 led the author to discover a similar transition in the
integer setting, see [Gor22a].

### Conventions

The letters $C,c$ shall denote absolute positive constants which may change
between different instances. The notation $A\ll B$ means $|A|\leq CB$ for some
absolute constant $C$, while $A\ll_{a,b,\ldots}B$ means $C$ may depend on the
parameters in the subscript. We write $A=\Theta_{a,b,\ldots}(B)$ to mean
$cB\leq A\leq CB$ where $C,c>0$ may depend on the parameters $a,b,\ldots$. The
notation $f\asymp_{a,b,\ldots}g$ is the same as $f=\Theta_{a,b,\ldots,}(g)$.

### Acknowledgements

This project has received funding from the European Research Council (ERC)
under the European Union’s Horizon 2020 research and innovation programme
(grant agreement No 851318).

##  2 Auxiliary functions

###  2.1 $\xi$, $I$ and $\hat{\rho}$

Recall we defined $\xi\colon(1,\infty)\to(0,\infty)$, a function of variable
$u>1$, by $e^{\xi}=1+u\xi$.

######  Lemma 2.1.

[Hil84, Lem. 1] We have $\xi\sim\log u$ as $u\to\infty$, and
$\xi^{\prime}=u^{-1}(1+O(1/\log u))$ for $u\geq 2$.

######  Lemma 2.2.

[MP16, Lem. 6] If $u>1$ we have $\log u<\xi\leq 2\log u$.

Let

$I(s)=\int_{0}^{s}\frac{e^{t}-1}{t}dt,$ (2.1)

which defines an entire function. Observe that

$I^{\prime}(\xi)=\frac{e^{\xi}-1}{\xi}=u,$

and a slightly longer computation shows that
$I^{\prime\prime}(\xi)=1/\xi^{\prime}$. The following lemma is proved by
direction induction.

######  Lemma 2.3.

For any $k\geq 1$ we have
$I^{(k)}(s)=(e^{s}P_{k-1}(s)-(-1)^{k-1}(k-1)!)/s^{k}$ for a monic polynomial
$P_{k-1}$ of degree $k-1$.

It has the following direct consequence.

######  Corollary 2.4.

For any fixed $k\geq 1$ we have $I^{(k)}(\xi)\sim e^{\xi}/u\sim\log u$ as
$u\to\infty$ and $I^{(k)}(\xi+it)\ll_{k}\log(u+1)$.

The function $I$ arises when studying the Laplace transform of $\rho$.

######  Lemma 2.5.

[Ten15, Ch. III.5, Thms. 7, 8] Let $\gamma$ be the Euler–Mascheroni constant.
We have

$\hat{\rho}(s):=\int_{0}^{\infty}e^{-sv}\rho(v)\,dv=\exp\left(\gamma+I(-s)\right)$
(2.2)

for all $s\in\mathbb{C}$. Uniformly for $u\geq 1$,

$\exp\left(\gamma-u\xi+I(\xi)\right)=\rho(u)\sqrt{\frac{2\pi}{\xi^{\prime}}}\left(1+O\left(u^{-1}\right)\right).$
(2.3)

We have the following bounds on $\hat{\rho}$.

######  Lemma 2.6.

[Ten15, Lem. III.5.12] The following bounds hold for $s=-\xi(u)+it$:

$\hat{\rho}(s)=\begin{cases}O\left(\exp\left(I(\xi)-\frac{t^{2}u}{2\pi^{2}}\right)\right)&\mbox{if
}|t|\leq\pi,\\\
O\left(\exp\left(I(\xi)-\frac{u}{\pi^{2}+\xi^{2}}\right)\right)&\mbox{if
}|t|\geq\pi,\\\ \frac{1}{s}+O\left(\frac{1+u\xi}{|s|^{2}}\right)&\mbox{if
}1+u\xi=O(|t|).\end{cases}$ (2.4)

The third case of Lemma 2.6 is usually stated in the range $1+u\xi\leq|t|$,
but the same proof works for $1+u\xi=O(|t|)$.

###  2.2 $T$

Let

$T(s):=\int_{0}^{s}\frac{e^{t}-1}{t}\left(\frac{\frac{t}{m}}{1-e^{-t/m}}-1\right)dt,$
(2.5)

which defines a holomorphic function in the strip $|\Im s|<2\pi m$.

######  Lemma 2.7.

[MP16, Lem. 11] Let $s=\xi+it$ and suppose that $\xi\leq\pi m$ and $-\pi m\leq
t\leq\pi m$. Then

$\left|T(s)+\frac{s}{2m}\right|\ll\frac{e^{\xi}}{m}+\frac{t^{2}}{m^{2}}.$
(2.6)

Since $s/(1-e^{-s})=1+s/2+s^{2}/12+s^{4}/720+\ldots=\sum_{i\geq
0}B_{i}s^{i}/i!$ for $|\Im s|<2\pi$ where $B_{i}$ are the Bernoulli numbers
which satisfy $B_{i}\ll i!/(2\pi)^{i}$, the following is immediate.

######  Lemma 2.8.

Uniformly for $k\geq 0$ and $\xi\leq\pi m$ we have

$T(\xi)=\sum_{i=1}^{k}m^{-i}\frac{B_{i}}{i!}\int_{0}^{\xi}(e^{t}-1)t^{i-1}dt+O\left(\frac{\int_{0}^{\xi}(e^{t}-1)t^{k}dt}{(2\pi
m)^{k+1}}\right)=\frac{(u-1)\xi}{2m}+O\left(\frac{u\log^{2}(u+1)}{m^{2}}\right).$

######  Lemma 2.9.

Suppose $\xi\leq\pi m$ and $-\pi m\leq t\leq\pi m$. For any $k\geq 1$ we have

$\displaystyle T^{(k)}(\xi)$
$\displaystyle=I^{(k)}(\xi)\left(\frac{\xi/m}{1-e^{-\xi/m}}-1+O_{k}\left(\frac{1}{m}\right)\right)=\frac{e^{\xi}}{2m}\left(1+O_{k}\left(\frac{1}{\log(u+1)}+\frac{\log(u+1)}{m}\right)\right),$
(2.7) $\displaystyle T^{(k)}(\xi+it)$ $\displaystyle\ll_{k}\frac{e^{\xi}}{m}.$
(2.8)

###### Proof.

We have

$T^{\prime}(s)=I^{\prime}(s)g(s/m)$

for $g(z):=z/(1-e^{-z})-1$. Repeated differentiation shows

$T^{(k)}(s)=I^{(k)}(s)g(s/m)+O_{k}\left(\sum_{i=1}^{k-1}m^{-i}|g^{(i)}(s/m)||I^{(k-i)}(s)|\right)$

and the lemma now follows from Lemma 2.3. ∎

###  2.3 $H_{n}$

Let

$H_{n}:=\sum_{i=1}^{n}\frac{1}{i}$

be the $n$th harmonic sum. The Euler–Maclaurin formula yields the following
asymptotic expansion for $H_{n}$ in powers of $1/n$:

$H_{n}=\log
n+\gamma+\frac{1}{2n}-\sum_{j=1}^{m}\frac{B_{2j}}{2jn^{2j}}+O_{m}(n^{-2m-2}).$
(2.9)

##  3 Proof of Theorem 1.1

###  3.1 First part of Theorem 1.1

If $m=O(\log(u+1))$ then (1.12) is the same as
$p_{n,m}=\rho(u)\exp(O(u\log(u+1)/m))$ which is already in (1.4). Hence we
suppose that $m\geq C\log(u+1)$ from now on. Similarly, if $u=O(1)$ then
(1.12) is already in (1.4), so we suppose $u\geq C$. We define a function
$D(z)$ as

$D(z)=z^{-n}\exp\left(\sum_{i=1}^{m}\frac{z^{i}}{i}\right),$

so that $x$ solves $D^{\prime}(z)=0$. We can write $\log D(x)$ as

$\log D(x)=-n\log x+\sum_{j=1}^{m}\frac{1}{j}+I(m\log x)+T(m\log x),$

see [MP16, Eq. (40)]. We set

$\widetilde{\xi}:=m\log x$

and define $\widetilde{u}\geq 1$ as

$\widetilde{u}:=\frac{e^{\widetilde{\xi}}-1}{\widetilde{\xi}}.$

In this notation, (1.9) implies that

$p_{n,m}=\rho(\widetilde{u})\exp\left(\widetilde{\xi}(\widetilde{u}-u)\right)\exp\left(T(\widetilde{\xi})\right)\sqrt{\frac{m^{2}}{\lambda\xi^{\prime}(\widetilde{u})}}\exp\left(O\left(u^{-1}+m^{-1}\right)\right)$
(3.1)

for $u\geq C$, where we used (2.3) and (2.9). Evidently,
$u=I^{\prime}(\xi)=(I+T)^{\prime}(\widetilde{\xi})$. Since $T(t)\geq 0$ for
$t\geq 0$ we have $\widetilde{\xi}\leq\xi$ and so, by the monotonicity of
$I^{\prime}(t)=(e^{t}-1)/t$, it follows that

$\widetilde{u}=I^{\prime}(\widetilde{\xi})\leq I^{\prime}(\xi)=u.$

By [MP16, Lem .10],

$\widetilde{\xi}=\xi+O\left(\frac{\log(u+1)}{m}\right)$ (3.2)

uniformly in $m\geq\log u>0$. By [MP16, Lem .9], for $m\geq\log u\geq\log 3$,

$\widetilde{\xi}=\log(u\log u)+O(1)=(1+o(1))\xi$ (3.3)

as $u\to\infty$. From (3.2) and (3.3) we see that, uniformly in $m\geq C\log
u$ and $u\geq C$,

$\widetilde{u}=u+O\left(\frac{u\log(u+1)}{m}\right).$ (3.4)

We will be using (3.2) and (3.4) often. For $m\geq\log u>0$ we have [MP16,
Lem. 10]

$\lambda=\frac{m^{2}}{\xi^{\prime}(u)}\left(1+O\left(\frac{\log(u+1)}{m}\right)\right).$

Hence,

$\sqrt{\frac{m^{2}}{\lambda\xi^{\prime}(\widetilde{u})}}=\sqrt{\frac{\xi^{\prime}(u)}{\xi^{\prime}(\widetilde{u})}}\exp\left(O\left(\frac{\log(u+1)}{m}\right)\right)$

for $m\geq C\log(u+1)$, $u\geq C$. Since $\xi^{\prime}(t)\ll 1/t$ and
$\xi^{\prime\prime}(t)\ll 1/t^{2}$,

$\frac{\xi^{\prime}(u)}{\xi^{\prime}(\widetilde{u})}=1+O\left(\frac{(u-\widetilde{u})}{\widetilde{u}}\right)=\exp\left(O\left(\frac{\log(u+1)}{m}\right)\right)$

and so

$\sqrt{\frac{m^{2}}{\lambda\xi^{\prime}(\widetilde{u})}}=\exp\left(O\left(\frac{\log(u+1)}{m}\right)\right)$

for $m\geq C\log(u+1)$, $u\geq C$. At this point, we have established that

$p_{n,m}=\rho(\widetilde{u})\exp\left(\widetilde{\xi}(\widetilde{u}-u)\right)\exp\left(T(\widetilde{\xi})\right)\exp\left(O\left(\frac{1}{u}+\frac{\log(u+1)}{m}\right)\right)$
(3.5)

in our range. We have $\widetilde{\xi}\leq\xi=(1+o(1))\log u\leq\pi m$ by our
assumptions $m\geq C\log(u+1)$ and $u\geq C$. By Lemma 2.8,

$T(\widetilde{\xi})=\frac{\widetilde{u}\widetilde{\xi}}{2m}+O\left(\frac{u\log^{2}(u+1)}{m^{2}}+\frac{\log(u+1)}{m}\right)=\frac{u\xi(u)}{2m}+O\left(\frac{u\log^{2}(u+1)}{m^{2}}+\frac{\log(u+1)}{m}\right)$
(3.6)

in this range, where in the second equality we used (3.2) and (3.4). We now
have

$p_{n,m}=\exp\left(\frac{u\xi(u)}{2m}\right)\rho(\widetilde{u})\exp\left(\widetilde{\xi}(\widetilde{u}-u)\right)\exp\left(O\left(\frac{1}{u}+\frac{u\log^{2}(u+1)}{m^{2}}\right)\right)$
(3.7)

for $m\geq C\log(u+1)$, $u\geq C$. Let $r(t)=-\rho^{\prime}(t)/\rho(t)$ be the
(negative of the) logarithmic derivative of $\log\rho$. We have

$\rho(\widetilde{u})=\rho(u)\exp\left(\int_{\widetilde{u}}^{u}r(t)dt\right).$

By integration by parts, we may write the integral in the exponent as

$\displaystyle\int_{\widetilde{u}}^{u}r(t)dt$
$\displaystyle=r(u)(u-\widetilde{u})-\int_{\widetilde{u}}^{u}(t-\widetilde{u})r^{\prime}(t)dt.$
(3.8)

In [dlBT05, Lem. 3.7], La Bretèche and Tenenbaum proved that

$r(v)=\xi(v)+O\left(v^{-1}\right),\qquad
r^{\prime}(v)=\xi^{\prime}(v)+O\left(v^{-2}\right)$ (3.9)

hold uniformly for $v\geq 1$. Hence, using (3.2) and (3.4),

$\displaystyle\rho(\widetilde{u})\exp\left(\widetilde{\xi}(\widetilde{u}-u)\right)$
$\displaystyle=\rho(u)\exp\left((r(u)-\xi(u)+\xi(u)-\widetilde{\xi})(u-\widetilde{u})-\int_{\widetilde{u}}^{u}(t-\widetilde{u})(r^{\prime}(t)-\xi^{\prime}(t)+\xi^{\prime}(t))dt\right)$
(3.10)
$\displaystyle=\rho(u)\exp\left(O\left(\frac{1}{u}+\frac{u\log^{2}(u+1)}{m^{2}}\right)-\int_{\widetilde{u}}^{u}(t-\widetilde{u})\xi^{\prime}(t)dt\right).$
(3.11)

To conclude the proof, it remains to bound
$\int_{\widetilde{u}}^{u}(t-\widetilde{u})\xi^{\prime}(t)dt$. Since
$\xi^{\prime}(t)\ll 1/t$,

$\int_{\widetilde{u}}^{u}(t-\widetilde{u})\xi^{\prime}(t)dt\ll\int_{\widetilde{u}}^{u}\frac{t-\widetilde{u}}{t}dt=\widetilde{u}\left(\frac{u}{\widetilde{u}}-1-\log\left(\frac{u}{\widetilde{u}}\right)\right)\ll\widetilde{u}\frac{(u-\widetilde{u})^{2}}{\widetilde{u}^{2}}\ll\frac{u\log^{2}(u+1)}{m^{2}}$

if $m\geq C\log(u+1)$, using (3.2) and (3.4). The proof of (1.12) is
completed.

###  3.2 Preliminary lemmas for second part of Theorem 1.1

The following is implicit in the proofs of [MP16, Thms. 2, 4], and is a
consequence of Cauchy’s integral formula.

######  Lemma 3.1.

We have

$p_{n,m}=\frac{\exp\big{(}H_{m}-\gamma\big{)}}{m}\frac{1}{2\pi i}\int_{-\xi-
im\pi}^{-\xi+im\pi}e^{us}\hat{\rho}(s)e^{T(-s)}ds.$

The following lemma is implicit in the proof of [MP16, Thm. 4].

######  Lemma 3.2.

Suppose $\sqrt{n\log n}=O(m)$. Then

$\frac{1}{2\pi i}\int_{-\xi-
im\pi}^{-\xi+im\pi}e^{us}\hat{\rho}(s)ds=\rho(u)+O\left(\frac{e^{-(u-1)\xi}}{n}\right).$

A variant of the next lemma, with $T(-s)$ in the exponent instead of
$T(-s)-T(\xi)$, is implicit in the proof of [MP16, Thm. 2].

######  Lemma 3.3.

Suppose $\sqrt{n\log n}=O(m)$ and $1+u\xi=O(A)$, $0\leq A\leq m\pi$. Then

$\frac{1}{2\pi
i}\int_{-\xi+iA}^{-\xi+im\pi}e^{us}\hat{\rho}(s)\left(e^{T(-s)-T(\xi)}-1\right)ds\ll\frac{e^{-u\xi}\log(u+1)}{m}.$
(3.12)

The same bound holds if we integrate from $-\xi-im\pi$ to $-\xi-iA$.

###### Proof.

We have $\hat{\rho}^{\prime}(s)=\rho(s)(e^{-s}-1)/s$. Integration by parts
shows that the integral is equal to

$\frac{1}{2\pi
i}\frac{e^{us}}{u}\hat{\rho}(s)\left(e^{T(-s)-T(\xi)}-1\right)\Big{|}^{s=-\xi+im\pi}_{s=-\xi+iA}\\\
-\frac{1}{2\pi
i}\int_{-\xi+iA}^{-\xi+im\pi}\frac{e^{us}}{u}\hat{\rho}(s)\left(\frac{e^{-s}-1}{s}\left(e^{T(-s)-T(\xi)}-1\right)-T^{\prime}(-s)e^{T(-s)-T(\xi)}\right)ds.$
(3.13)

By Lemma 2.7, $T(-s)-T(\xi)$ is bounded in our range of integration. In fact,
$T(-s)-T(\xi)\ll(e^{\xi}+|t|)/m$. Hence, the third case of Lemma 2.6 shows
that

$\frac{1}{2\pi
i}\frac{e^{us}}{u}\hat{\rho}(s)\left(e^{T(-s)-T(\xi)}-1\right)\Big{|}^{s=-\xi+im\pi}_{s=-\xi+iA}\ll\frac{e^{-u\xi}}{n}.$

As for the integral, we rearrange it:

$\displaystyle\frac{1}{2\pi i}$
$\displaystyle\int_{-\xi+iA}^{-\xi+im\pi}\frac{e^{us}}{u}\hat{\rho}(s)\left(\frac{e^{-s}-1}{s}\left(e^{T(-s)-T(\xi)}-1\right)-T^{\prime}(-s)e^{T(-s)-T(\xi)}\right)ds$
(3.14) $\displaystyle=\frac{1}{2\pi
i}\int_{-\xi+iA}^{-\xi+im\pi}\frac{e^{us}}{u}\frac{e^{-s}-1}{s}\hat{\rho}(s)\left(e^{T(-s)-T(\xi)}\frac{\frac{-s}{m}}{1-e^{s/m}}-1\right)ds.$
(3.15)

By Lemma 2.7 and the Taylor expansion $z/(1-e^{-z})=1+z/2+O(z^{2})$,

$e^{T(-s)-T(\xi)}\frac{\frac{-s}{m}}{1-e^{s/m}}-1\ll\frac{|s|^{2}}{m^{2}}+\frac{e^{\xi}}{m}$

in our range of integration. By the triangle inequality, the integral is

$\ll\frac{\log(u+1)}{e^{u\xi}}\int_{-\xi+iA}^{-\xi+im\pi}\frac{|\hat{\rho}(s)|}{|s|}\left(\frac{|s|^{2}}{m^{2}}+\frac{e^{\xi}}{m}\right)|ds|\\\
\ll\frac{\log(u+1)}{e^{u\xi}}\int_{-\xi+iA}^{-\xi+im\pi}\frac{1}{|s|^{2}}\left(\frac{|s|^{2}}{m^{2}}+\frac{e^{\xi}}{m}\right)|ds|\ll\frac{\log(u+1)}{me^{u\xi}}$
(3.16)

where in the second inequality we used the third case of Lemma 2.3. ∎

######  Lemma 3.4.

Suppose $0\leq B\leq A=O(1+u\xi)$. Then, for every $k\geq 0$,

$\frac{1}{2\pi
i}\int_{-\xi+iB}^{-\xi+iA}\left|(s+\xi)^{k}e^{us}\hat{\rho}(s)\right|\left|ds\right|\ll_{k}\rho(u)\left(u^{-\frac{k}{2}}\exp(-cuB^{2})+A^{k+1}\sqrt{u}\exp\left(-\frac{u}{\xi^{2}+\pi^{2}}\right)\right),$

and the same is true if we integrate from $-\xi-iA$ to $-\xi-iB$. In
particular, for $B=0$,

$\frac{1}{2\pi i}\int_{-\xi-
iA}^{-\xi+iA}\left|(s+\xi)^{k}e^{us}\hat{\rho}(s)\right|\left|ds\right|\ll_{k}\rho(u)u^{-\frac{k}{2}}.$

###### Proof.

Using the first two parts of Lemma 2.6, the triangle inequality shows that the
integral is

$\ll
e^{-u\xi+I(\xi)}\int_{B}^{A}|t|^{k}\left(\exp(-cut^{2})+\exp\left(-\frac{u}{\xi^{2}+\pi^{2}}\right)\right)dt\\\
\ll_{k}e^{-u\xi+I(\xi)}\left(u^{-\frac{k+1}{2}}\exp(-cuB^{2})+A^{k+1}\exp\left(-\frac{u}{\xi^{2}+\pi^{2}}\right)\right),$
(3.17)

and we now use (2.3). ∎

######  Lemma 3.5.

Suppose $\sqrt{n\log n}=O(m)$ and let $A\geq 0$ be a quantity of size
$\Theta(u\log(u+1))$. Then, for even $k\geq 0$,

$\frac{1}{2\pi i}\int_{-\xi-
iA}^{-\xi+iA}(s+\xi)^{k}e^{us}\hat{\rho}(s)ds=\rho(u)(1+O_{k}(u^{-1}))\frac{k!}{(k/2)!2^{k/2}}(-1)^{k/2}\xi^{\prime
k/2}$

and for odd $k\geq 1$,

$\frac{1}{2\pi i}\int_{-\xi-
iA}^{-\xi+iA}(s+\xi)^{k}e^{us}\hat{\rho}(s)ds=\rho(u)(1+O_{k}(u^{-1}))\frac{(k+3)!}{((k+3)/2)!2^{(k+3)/2}}(-1)^{(k+1)/2}\xi^{\prime(k+3)/2}\frac{I^{(3)}(\xi)}{6}.$

###### Proof.

Fix $k\geq 0$. Applying Lemma 3.4 with $B=\min\\{A,C_{k}\sqrt{(\log u)/u}\\}$
shows that the contribution of $|\Im s|\geq C_{k}\sqrt{(\log u)/u}$ is
acceptable. We may now assume that $A\leq C_{k}\sqrt{\log u/u}$. Recall
$\hat{\rho}(s)=\exp(\gamma+I(-s))$. We may Taylor-expand $I(\xi+it)$ using
Lemma 2.3, obtaining that

$\displaystyle\frac{1}{2\pi i}\int_{-\xi-iA}^{-\xi+iA}$
$\displaystyle(s+\xi)^{k}e^{us}\hat{\rho}(s)ds$ (3.18)
$\displaystyle=i^{k}\frac{e^{\gamma-u\xi+I(\xi)}}{2\pi}\int_{-A}^{A}t^{k}\exp\left(-\frac{t^{2}}{2}I^{\prime\prime}(\xi)+i\frac{t^{3}}{6}I^{(3)}(\xi)+\frac{t^{4}}{24}I^{(4)}(\xi)+O\left(u|t|^{5}\right)\right)dt$
(3.19)
$\displaystyle=i^{k}\frac{e^{\gamma-u\xi+I(\xi)}}{2\pi}\int_{-A}^{A}t^{k}\exp\left(-\frac{t^{2}}{2}I^{\prime\prime}(\xi)\right)\big{(}1+i\frac{t^{3}}{6}I^{(3)}(\xi)+\frac{t^{4}}{24}I^{(4)}(\xi)-\frac{t^{6}}{72}I^{(3)}(\xi)^{2}\big{)}$
(3.20)
$\displaystyle\qquad\qquad\cdot\left(1+O\left(u|t|^{5}+u^{3}|t|^{9}\right)\right)dt.$
(3.21)

Substituting $t^{2}I^{\prime\prime}(\xi)=v^{2}$, recalling
$I^{\prime\prime}(\xi)=1/\xi^{\prime}$ and using (2.3), the last expression
can be written as

$=\rho(u)(1+O(u^{-1}))i^{k}\xi^{\prime
k/2}\frac{1}{\sqrt{2\pi}}\int_{-A/\sqrt{\xi^{\prime}}}^{A/\sqrt{\xi^{\prime}}}v^{k}\exp\left(-\frac{v^{2}}{2}\right)\\\
\cdot\left(1+i\frac{v^{3}\xi^{\prime
3/2}}{6}I^{(3)}(\xi)+\frac{v^{4}\xi^{\prime
2}}{24}I^{(4)}(\xi)-\frac{v^{6}\xi^{\prime
3}}{72}I^{(3)}(\xi)^{2}\right)\left(1+O\left(\frac{|v|^{5}+|v|^{9}}{u^{3/2}}\right)\right)dv.$
(3.22)

The required estimate now follows from
$\int_{-R}^{R}v^{2k+1}\exp(-v^{2}/2)dv\equiv 0$,
$\int_{\mathbb{R}}|v|^{k}\exp(-v^{2}/2)dv\ll_{k}1$ and
$\int_{-R}^{R}v^{2k}\exp(-v^{2}/2)dv=\sqrt{2\pi}(2k)!/(2^{k}k!)+O_{k}(\exp(-R^{2}/4))$.
∎

###  3.3 Proof of second part of Theorem 1.1

From Lemma 3.1 we have

$p_{n,m}=\frac{\exp\big{(}H_{m}-\gamma\big{)}}{m}e^{T(\xi)}\frac{1}{2\pi
i}\int_{-\xi-im\pi}^{-\xi+im\pi}e^{us}\hat{\rho}(s)e^{T(-s)-T(\xi)}ds.$

We have $\exp(H_{m}-\gamma)/m=1+1/(2m)+O(m^{-2})$ by (2.9), and

$e^{T(\xi)}=e^{\frac{u\xi}{2m}}\left(1-\frac{\xi}{2m}+O\left(\frac{u\log^{2}(u+1)}{m^{2}}\right)\right)$

by Lemma 2.8. Hence,

$p_{n,m}=e^{\frac{u\xi}{2m}}\left(1+\frac{1-\xi}{2m}+O\left(\frac{u\log^{2}(u+1)}{m^{2}}\right)\right)\frac{1}{2\pi
i}\int_{-\xi-im\pi}^{-\xi+im\pi}e^{us}\hat{\rho}(s)e^{T(-s)-T(\xi)}ds.$

Let $A:=\min\\{m\pi,1+u\xi\\}$. We separate the integral into 3 parts,
$S_{1}+S_{2}+S_{3}$, where

$\displaystyle S_{1}$ $\displaystyle=\frac{1}{2\pi i}\int_{-\xi-
im\pi}^{-\xi+im\pi}e^{us}\hat{\rho}(s)ds,$ (3.23) $\displaystyle S_{2}$
$\displaystyle=\frac{1}{2\pi i}\int_{-\xi-
iA}^{-\xi+iA}\left(e^{T(-s)-T(\xi)}-1\right)e^{us}\hat{\rho}(s)ds,$ (3.24)
$\displaystyle S_{3}$ $\displaystyle=\frac{1}{2\pi i}\left(\int_{-\xi-
im\pi}^{-\xi-
iA}+\int_{-\xi+iA}^{-\xi+im\pi}\right)\left(e^{T(-s)-T(\xi)}-1\right)e^{us}\hat{\rho}(s)ds.$
(3.25)

The integral $S_{1}$ was estimated in Lemma 3.2 and it gives the main term
$\rho(u)$ as well an absolute error of size $\ll e^{-(u-1)\xi}/n\ll
e^{-u\xi}\log(u+1)/m$. The integral $S_{3}$ was estimated in Lemma 3.3 and it
contributes $\ll e^{-u\xi}\log(u+1)/m$. We now study $S_{2}$. We use Lemma 2.8
to Taylor-expand $e^{T(-s)-T(\xi)}-1$ at $-s=\xi$:

$e^{T(-s)-T(\xi)}-1=-T^{\prime}(\xi)(s+\xi)+\frac{(s+\xi)^{2}}{2}\left(T^{\prime\prime}(\xi)+T^{\prime}(\xi)^{2}\right)\\\
-(T^{(3)}(\xi)+3T^{\prime}(\xi)T^{\prime\prime}(\xi)+(T^{\prime}(\xi))^{3})\frac{(s+\xi)^{3}}{6}+O\left(\frac{u\log(u+1)}{m}|s+\xi|^{4}\right).$
(3.26)

Applying Lemma 3.4 with $k=4$, $B=0$ and Lemma 3.5 with $k=1,2,3$ and
collecting the terms gives

$S_{2}=\rho(u)\left(\frac{T^{\prime}(\xi)(1+o_{u\to\infty}(1))-T^{\prime\prime}(\xi)(1+o_{u\to\infty}(1))}{2u}+O\left(\frac{u\log^{2}(u+1)}{m^{2}}+\frac{\log(u+1)}{mu}\right)\right).$

All in all, since $T^{\prime}(\xi)$ and $T^{\prime\prime}(\xi)$ are both
$u\log(u+1)/(2m)(1+o_{u\to\infty}(1))$,

$p_{n,m}=\exp\left(\frac{u\xi}{2m}\right)\rho(u)\left(1-\frac{\log(u+1)}{2m}(1+o_{u\to\infty}(1))+O\left(\frac{u\log^{2}(u+1)}{m^{2}}\right)\right),$
(3.27)

establishing the theorem.

##  4 Proofs of corollaries and lemmas in the permutation setting

###  4.1 Parameter estimates

######  Lemma 4.1.

We have $x\gg n^{1/m}$, $\lambda=\Theta(nm)$ and $\lambda=nm(1+O(1/\max\\{\log
u,n^{1/m}\\}))$ uniformly for $n\geq m\geq 1$.

###### Proof.

We first study $x$. For bounded $n$ or bounded $u$, the trivial estimate
$x\geq 1$ already implies $x\gg n^{1/m}$, so we may assume $n$ is sufficiently
large and that $u\geq 3$. If $m=1$ we have $x=n$ by definition. If $\log n\geq
m\geq 2$, Lemma 16 of [MP16] says

$x=n^{\frac{1}{m}}-\frac{1}{m}-\sum_{i=2}^{m}\frac{\Gamma(i+(i-1)/m)}{(i-1)\Gamma(i+1)\Gamma((i-1)/m)}n^{-\frac{i-1}{m}}+\frac{n^{\frac{1}{m}-1}}{m}+O\left(n^{-1}\right).$
(4.1)

All the terms, except possibly for the $i$-sum, contribute $\ll 1/m$. Since
$\Gamma(i+(i-1)/m)\leq\Gamma(i+1)$ and $1/\Gamma((i-1)/m)\ll(i-1)/m$, we see
that the $i$-sum contributes $\ll n^{-1/m}/m$, implying $x=n^{1/m}+O(1/m)\gg
n^{1/m}$. If $u\geq 3$ and $m\geq\log n$, Lemma 9 of [MP16] shows

$x=(u\log
u)^{\frac{1}{m}}\left(1+O\left(m^{-1}\right)\right)=n^{\frac{1}{m}}\left(1+O\left(m^{-1}\right)\right)\left(\frac{\log
u}{m}\right)^{1/m}\gg n^{\frac{1}{m}}.$ (4.2)

We turn to $\lambda$. By [MP16, Lem. 9], $\lambda=nm(1+O(1/\log u))$ uniformly
for $u>1$. We now show $\lambda=mn(1+O(n^{-1/m}))$ in this range as well. We
have

$x^{m}\leq\sum_{i=1}^{m}x^{i}=n\leq\frac{x^{m}}{1-x^{-1}},$

and so

$mn(1-x^{-1})\leq mx^{m}\leq\lambda\leq m\sum_{i=1}^{m}x^{i}=nm$

implying $\lambda=nm(1+O(x^{-1}))=nm(1+O(n^{-1/m}))$. In view of the
asymptotic estimates, $\lambda=\Theta(nm)$ when $u\geq C$. For $u\leq C$,
$\lambda\leq nm$ as we have already seen and $\lambda\geq\sum_{i=1}^{m}i\gg
nm$, so $\lambda=\Theta(nm)$ holds always. ∎

###  4.2 Proof of Lemma 1.2

Letting $r(t)=-\rho^{\prime}(t)/\rho(t)$, we have

$\displaystyle\rho\left(u\right)$
$\displaystyle=\rho\left(u-\frac{u}{2m}\right)\exp\left(-\int_{u-\frac{u}{2m}}^{u}r(t)dt\right)$
(4.3)
$\displaystyle=\rho\left(u-\frac{u}{2m}\right)\exp\left(-\frac{ur(u)}{2m}+\int_{u-\frac{u}{2m}}^{u}\left(u-\frac{u}{2m}-t\right)r^{\prime}(t)dt\right)$
(4.4)

by integration by parts. Using (3.9) we find

$\displaystyle-\frac{ur(u)}{2m}+\int_{u-\frac{u}{2m}}^{u}\left(u-\frac{u}{2m}-t\right)r^{\prime}(t)dt=-\frac{u\xi(u)}{2m}+O\left(\frac{u}{m^{2}}+\frac{1}{m}\right),$
(4.5)

concluding the proof.

###  4.3 Proof of Lemma 1.3

Recall the definitions of $x$ and $\lambda$ given in (1.10) and (1.11).
Following the proof of Theorem 1 in [MP16]222We correct a few typos. The
definition of $D(x)$ in p. 21 of [MP16] deviates from the (correct) one in p.
4. The left-hand side of their equation (48) should be “$\log D(x)$”. In the
first displayed equation in p. 22, the sum of $h_{N}z^{N}$ should start at
$N=-r$ and not $N=-r+1$. In the second displayed equation in p. 23, the factor
$n!$ that appears twice should be omitted. we have, using the notation of
[MP16, Sec. 5],

$p_{n,m}=\frac{1}{\sqrt{2\pi\lambda}}\exp\left(\sum_{i=1}^{m}d_{m,i}n^{1-\frac{i}{m}}+R\left(n^{-\frac{1}{m}}\right)\right)\left(1+O\left(u^{-1}\right)\right)$

where

$R(z):=\sum_{i=1}^{\infty}h_{i}z^{i}-n\sum_{i=m+1}^{\infty}b_{i}z^{i}$

for certain coefficients $h_{i}$ and $b_{i}$ defined in Lemma 13 of [MP16] and
estimated in their Lemma 15. In particular,

$h_{i}=\frac{i+m}{i}b_{i+m}$

for $i\geq 1$ and

$b_{i}\ll\frac{m^{\frac{i}{m}}}{i}$

for $i\geq 1$. We also need an estimate implicit in the proof of [MP16, Lem.
15]:

$b_{i}\ll\frac{i^{\frac{i}{m}-1}}{m}\ll\frac{i-m}{m}$ (4.6)

for $m+1\leq i\leq 2m-1$. The authors of [MP16] showed that if $|z|\leq
e^{-1}$ then $R(z)\ll|z|+n|z|^{m+1}$ and so, if $m\leq\log n$, they obtain
$R(n^{-1/m})\ll n^{-1/m}$.333In the displayed equation following [MP16, Eq.
(49)] they seem to use (4.6) although they refer to the weaker $b_{i}\ll i/m$.
We have, without any assumption on $z$,

$\displaystyle R(z)$
$\displaystyle\ll\sum_{i=1}^{m-1}\frac{i+m}{m}|z|^{i}+\sum_{i=m}^{\infty}\frac{m}{i}\left(m^{\frac{1}{m}}|z|\right)^{i}+n\left(\sum_{i=m+1}^{2m-1}\frac{i-m}{m}|z|^{i}+\sum_{i=2m}^{\infty}\frac{1}{i}\left(m^{\frac{1}{m}}|z|\right)^{i}\right)$
(4.7)
$\displaystyle\ll\sum_{i=1}^{m-1}|z|^{i}+\sum_{i=m}^{2m-1}\left(\frac{n(i-m)}{m}+m^{\frac{i}{m}}\right)|z|^{i}+\sum_{i=2m}^{\infty}\frac{n}{i}\left(m^{\frac{1}{m}}|z|\right)^{i}.$
(4.8)

It follows that

$R\left(n^{-\frac{1}{m}}\right)\ll\frac{n^{-\frac{1}{m}}}{1-n^{-\frac{1}{m}}}+\frac{n^{-\frac{1}{m}}}{m\left(1-n^{-\frac{1}{m}}\right)^{2}}+\frac{\frac{m}{n}}{1-\left(\frac{m}{n}\right)^{\frac{1}{m}}}\ll\frac{n^{-\frac{1}{m}}}{1-n^{-\frac{1}{m}}}+\frac{\frac{m}{n}}{1-\left(\frac{m}{n}\right)^{\frac{1}{m}}}.$

To conclude, we input the estimates for $\lambda/(nm)$ given in Lemma 4.1.

###  4.4 Proof of Corollary 1.4

For any fixed $m$, the required estimate follows immediately from (1.8), since
the term $d_{m,1}n^{1-1/m}$ dominates the other terms ($d_{m,i}n^{1-i/m}$ for
$2\leq i\leq m$). We now assume that $C\leq m=O(\log n)$ for some large enough
$C$. Let

$S:=\sum_{i=1}^{m-1}d_{m,i}n^{1-\frac{i}{m}}.$

Uniformly for $1\leq i\leq m-1$ we have

$\displaystyle\frac{1}{m-i}$
$\displaystyle=\frac{1}{m}\left(1+O\left(\frac{i}{m-i}\right)\right),$ (4.9)
$\displaystyle\frac{1}{\Gamma\left(1+\frac{i}{m}\right)}$
$\displaystyle=1+O\left(\frac{i}{m}\right),$ (4.10)
$\displaystyle\frac{\Gamma\left(i+\frac{i}{m}\right)}{i!}$
$\displaystyle=\frac{1}{i}\frac{\Gamma\left(i+\frac{i}{m}\right)}{\Gamma(i)}=\frac{i^{\frac{i}{m}}}{i}\left(1+O\left(\frac{1}{m}\right)\right)=\frac{1}{i}\exp\left(\frac{O(1)+i\log
i}{m}\right),$ (4.11)

where in the last estimate we used the bounds

$x(x+y)^{y-1}\leq\frac{\Gamma(x+y)}{\Gamma(x)}\leq x^{y}$

applied with $x=i$ and $y=i/m\in[0,1]$, see [Wen48]. Hence,

$S=u\left(S_{1}+O(S_{2}+S_{3})\right)$

where

$\displaystyle S_{1}$
$\displaystyle:=\sum_{i=1}^{m-1}\frac{n^{-\frac{i}{m}}}{i}=-\log\left(1-n^{-\frac{1}{m}}\right)+O\left(\frac{1}{nm}\frac{1}{1-n^{-\frac{1}{m}}}\right),$
(4.12) $\displaystyle S_{2}$ $\displaystyle:=\sum_{1\leq
i<m/\log(m+1)}\frac{n^{-\frac{i}{m}}}{i}\frac{i\log(i+1)}{m}\ll\frac{\log(m+1)}{m}\frac{1}{n^{\frac{1}{m}}-1},$
(4.13) $\displaystyle S_{3}$ $\displaystyle:=\sum_{m/\log(m+1)\leq i\leq
m-1}\frac{n^{-\frac{i}{m}}}{i}mi^{\frac{i}{m}}\ll
n^{-\frac{1}{\log(m+1)}}m\log\log(m+2).$ (4.14)

Here the error terms in $S_{1}$ and $S_{2}$ were bounded in terms of a
geometric series with ratio $n^{-1/m}$, and in bounding $S_{3}$ we replaced
$(i/n)^{i/m}$ by its maximal possible value. If $m=O(\log n)$, both $S_{3}$
and the error term in $S_{1}$ are dominated by our bound for $S_{2}$. In view
of Lemma 1.3 we have

$\displaystyle p_{n,m}$
$\displaystyle=\left(\frac{e}{n}\right)^{u}\exp\left(S+d_{m,m}+O(\log
n)\right)$ (4.15)
$\displaystyle=\left(\frac{e}{n}\right)^{u}\exp\left(u\left(-\log\left(1-n^{-\frac{1}{m}}\right)+O\left(\frac{\log(m+1)}{m}\frac{1}{n^{\frac{1}{m}}-1}\right)\right)+O(\log
n)\right)$ (4.16)

which implies the remaining cases.

###  4.5 Proof of Corollary 1.5

We first consider $n\geq m\geq n/2$. We have exact formulas:
$p_{n,m}=1-\sum_{i=m+1}^{n}1/i$ and $\rho(u)=1-\log u$. Since
$\sum_{i=1}^{N}1/i=\log N+\gamma+1/(2N)+O(1/N^{2})$, we see that

$p_{n,m}=\rho(u)\left(1+\Theta\left(\frac{n-m}{n^{2}}\right)\right)=\rho(u)\left(1+\Theta\left(\frac{u-1}{m}\right)\right)=\rho(u)\exp\left(\Theta\left(\frac{\log
u}{m}\right)\right).$

We now suppose $n/2\geq m\geq 1$. Note that we may assume that $n$ is $\gg 1$,
because if $n$ is bounded then we just want to show
$p_{n,m}=\rho(u)\exp(\Theta(1))$ for $n/2\geq m\geq 1$ which follows from
(1.7) and (1.4). The rest of the proof is divided into three cases.

  1. 1.

Suppose $n/2\geq m\geq\sqrt{n}\log n$. It follows from the second part of
Theorem 1.1 that if $u\gg 1$ then

$p_{n,m}=\rho(u)\exp\left(\Theta\left(\frac{u\xi(u)}{m}\right)\right)\\\
=\rho(u)\exp\left(\Theta\left(\frac{u\log
u}{m}\right)\right)=\rho(u)\exp\left(\Theta\left(u\log\left(1+\frac{\log
u}{m}\right)\right)\right).$ (4.17)

However, if $u=O(1)$ we only establish the upper bound

$p_{n,m}\leq\rho(u)\exp\left(\frac{Cu\log
u}{m}\right)\leq\rho(u)\exp\left(Cu\log\left(1+\frac{\log
u}{m}\right)\right).$ (4.18)

Fortunately, a matching lower bound in this range follows from (1.7).

  2. 2.

Suppose $\sqrt{n}\log n\geq m\geq C\log n$ for sufficiently large $C$, chosen
in such a way that $u\xi(u)/(2m)$ is at least twice the error term in the
exponent in the right-hand side of (1.12). It follows directly from the first
part of first part of Theorem 1.1 that (4.17) holds in this range.

  3. 3.

Suppose $m=O(\log n)$. From (1.1) we have

$\left(\frac{e}{n}\right)^{u}\rho(u)^{-1}=\exp\left(u\left(\log\left(\frac{\log
u}{m}\right)+O\left(\frac{\log\log u}{\log u}\right)\right)\right).$ (4.19)

From Corollary 1.4 and (4.19),

$u^{-1}\log\left(p_{n,m}\rho(u)^{-1}\right)=\log\left(\frac{\log
n}{m}\right)-\log\left(1-n^{-\frac{1}{m}}\right)+o_{n\to\infty}(1)+o_{m\to\infty}(n^{-1/m}).$

To conclude, we just observe that, if $n$ is sufficiently large and $C\log
n\geq m\geq 1$,

$\log\left(\frac{\log
n}{m}\right)-\log\left(1-n^{-\frac{1}{m}}\right)+o_{n\to\infty}(1)+o_{m\to\infty}(n^{-1/m})\\\
=\log\left(\frac{(\log n)/m}{1-e^{-(\log
n)/m}}\right)+o_{n\to\infty}(1)+o_{m\to\infty}(n^{-1/m})=\Theta\left(\log\left(1+\frac{\log
n}{m}\right)\right)$ (4.20)

since $t/(1-e^{-t})\geq 1+c$ where $t=(\log n)/m\geq 1/C$.

##  5 Proofs of results in the polynomial setting

###  5.1 Auxiliary computation

######  Lemma 5.1.

Suppose that $n\geq m\geq\sqrt{10n\log n}$. Then $e^{\xi/m}<\sqrt[3]{2}$.
Moreover, uniformly for $s=-\xi+it$ ($t\in\mathbb{R}$) we have

$\displaystyle\left|\frac{G_{q}(e^{-s/m})}{G_{q}(e^{\xi/m})}-1\right|$
$\displaystyle\ll\frac{u\log(u+1)}{mq^{\lceil\frac{m+1}{2}\rceil}},$ (5.1)
$\displaystyle\left|\frac{G_{q}^{\prime}(e^{-s/m})}{G_{q}(e^{\xi/m})}\right|$
$\displaystyle\ll\frac{u\log(u+1)}{q^{\lceil\frac{m+1}{2}\rceil}},$ (5.2)

and

$\frac{G_{q}(e^{-s/m})}{G_{q}(e^{\xi/m})}-1=\sum_{i=m+1}^{3m}\frac{a_{i}}{i}(e^{-is/m}-e^{i\xi/m})+O\left(\frac{(u\log(u+1))^{3}}{mq^{2m+1}}\right)$
(5.3)

for some constants $a_{i}\ll q^{-\lceil i/2\rceil}$. We also have

$\frac{G_{q}(x)}{G_{q}(e^{\xi/m})}=1+O\left(\frac{u\log^{2}(u+1)}{m^{2}q^{\lceil\frac{m+1}{2}\rceil}}\right).$
(5.4)

###### Proof.

The condition $m\geq\sqrt{10n\log n}$ guarantees $2^{m/3}>1+m(\log 2)/3\geq
1+2u\log u\geq 1+u\xi=e^{\xi}$, where we used Lemma 2.2 in the last
inequality. Hence $e^{\xi/m}<\sqrt[3]{2}$. We can write $G_{q}$ as

$G_{q}(z)=\exp\left(\sum_{i=m+1}^{\infty}\frac{a_{i}z^{i}}{i}\right)$

where $a_{i}$ are non-negative numbers, depending on $q$, that are described
in [Gor22b, Lem. 2.1] and in particular satisfy $a_{i}\ll\min\\{q^{-\lceil
i/2\rceil},q^{m-i}\\}$. To study $G_{q}(e^{-s/m})/G_{q}(e^{\xi/m})$, observe
that

$\log
G_{q}(e^{-s/m})=\sum_{i=m+1}^{\infty}\frac{a_{i}}{i}e^{-is/m}\ll\sum_{i=m+1}^{\infty}\frac{a_{i}}{i}e^{i\xi/m}\ll\frac{e^{\xi}}{mq^{\lceil\frac{m+1}{2}\rceil}}\ll\frac{u\log(u+1)}{mq^{\lceil\frac{m+1}{2}\rceil}}.$

We deduce that

$\frac{G_{q}(e^{-s/m})}{G_{q}(e^{\xi/m})}-1\ll\sum_{i=m+1}^{\infty}\frac{a_{i}}{i}e^{i\xi/m}\ll\frac{u\log(u+1)}{mq^{\lceil\frac{m+1}{2}\rceil}},$

and a similar argument implies (5.3). To study
$G^{\prime}_{q}(e^{-s/m})/G_{q}(e^{\xi/m})$ observe
$G_{q}(e^{-s/m})=\Theta(1)$ and that
$G_{q}^{\prime}(z)/G_{q}(z)=\sum_{i=m+1}^{\infty}a_{i}z^{i-1}$. The bound
reduces to showing $\sum_{i=m+1}^{\infty}a_{i}e^{i\xi/m}\ll
u\log(u+1)/q^{\lceil(m+1)/2\rceil}$ which follows immediately from $a_{i}\ll
q^{-\lceil i/2\rceil}$.

We now show (5.4). First we verify that $x<\sqrt[3]{2}$. Since $x\leq
n^{1/m}$, it suffices to show that $2^{m}>n^{3}$, which follows from $n\geq
m\geq\sqrt{10n\log n}$. Now that we know $G_{q}$ converges absolutely at $x$
we proceed. The relation $x^{m}=e^{\xi}(1+O(\log(u+1)/m))$ from (3.2) implies

$\log G_{q}(x)-\log
G_{q}(e^{\xi/m})=\sum_{i=m+1}^{\infty}\frac{a_{i}(x^{i}-e^{\xi
i/m})}{i}\ll\frac{u\log^{2}(u+1)}{m^{2}q^{\lceil\frac{m+1}{2}\rceil}}$

and (5.4) follows by exponentiating. ∎

###  5.2 Proof of Theorem 1.7

An application of Cauchy’s integral formula allows us to express $p_{n,m}$ as

$p_{n,m}=\frac{\exp(H_{m}-\gamma)}{m}\frac{1}{2\pi i}\int_{-\xi-
im\pi}^{-\xi+im\pi}\hat{\rho}(s)e^{us}e^{T(-s)}ds,$ (5.5)

see [MP16, §4]. In the same way,

$p_{n,m,q}=\frac{\exp(H_{m}-\gamma)}{m}\frac{1}{2\pi i}\int_{-\xi-
im\pi}^{-\xi+im\pi}\hat{\rho}(s)e^{us}e^{T(-s)}G_{q}(e^{-s/m})ds,$ (5.6)

see e.g. [Gor22b]. Since $G_{q}$ has radius of convergence equal to $q$, we
must ensure that $e^{\xi/m}<q$ in order for the last integral to be valid, and
this is verified in Lemma 5.1. We have from (5.5) and (5.6)

$p_{n,m,q}-G_{q}(e^{\xi/m})p_{n,m}=G_{q}(e^{\xi/m})\frac{\left(1+O(m^{-1})\right)}{2\pi
i}\int_{-\xi-
im\pi}^{-\xi+im\pi}\hat{\rho}(s)e^{us}e^{T(-s)}\left(\frac{G_{q}(e^{-s/m})}{G_{q}(e^{\xi/m})}-1\right)ds.$
(5.7)

Since $p_{n,m}\gg\rho(u)$ for $m\geq\sqrt{10n\log n}$, it suffices to show
that the integral in (5.7) is
$\ll\rho(u)\log(u+1)/(mq^{\lceil(m+1)/2\rceil})$. To bound the integral, we
consider separately the contribution of $|\Re s|\leq 1+u\xi$ and $m\pi\geq|\Re
s|\geq 1+u\xi$. We start with $|\Re s|\leq 1+u\xi$. We Taylor-expand the
function

$H(s):=e^{T(-s)}\left(\frac{G_{q}(e^{-s/m})}{G_{q}(e^{\xi/m})}-1\right)$

at $s=-\xi$, where it attains $0$. We find

$H(s)=(s+\xi)a+O(|s+\xi|^{2}b)$

where

$\displaystyle a$
$\displaystyle:=\frac{e^{T(\xi)+\frac{\xi}{m}}}{m}\frac{G_{q}^{\prime}(e^{\xi/m})}{G_{q}(e^{\xi/m})},$
(5.8) $\displaystyle b$ $\displaystyle:=\max_{|t|\leq
1+u\xi}\left(\left|e^{T(-s)}\frac{G_{q}^{\prime}(e^{-s/m})}{mG_{q}(e^{\xi/m})}\right|+\left|T^{\prime}(-s)e^{T(-s)}\left(\frac{G_{q}(e^{-s/m})}{G_{q}(e^{\xi/m})}-1\right)\right|\right).$
(5.9)

Recall that $T$ is bounded by Lemma 2.7 and that $T^{\prime}(-s)\ll
u\log(u+1)/m$. Applying Lemma 3.4 with $k=2$, $B=0$ and Lemma 3.5 with $k=1$,
it follows that

$\frac{1}{2\pi
i}\int_{-\xi-i(1+u\xi)}^{-\xi+i(1+u\xi)}\hat{\rho}(s)e^{us}e^{T(-s)}\left(\frac{G_{q}(e^{-s/m})}{G_{q}(e^{\xi/m})}-1\right)ds\ll\frac{\rho(u)}{u}\left(|a|+b\right)\ll\frac{\rho(u)\log(u+1)}{mq^{\lceil\frac{m+1}{2}\rceil}}$

by Lemma 5.1, which is acceptable. We now consider the contribution of $\pi
m\geq|\Re s|\geq 1+u\xi$. We focus on $m\pi\geq\Re s\geq 1+u\xi$, and negative
$\Re s$ is handled the same say. We have
$\hat{\rho}(s)=1/s+O(u\log(u+1)/|s|^{2})$ in this range by the third part of
Lemma 2.6. We also have that $T(-s)$ is bounded, by Lemma 2.7. The
contribution of $O(u\log(u+1)/|s|^{2})$ is at most

$\ll\int_{-\xi+i(1+u\xi)}^{-\xi+i\pi
m}\left|\frac{u\log(u+1)}{s^{2}}\right|\left|\frac{G_{q}(e^{-s/m})}{G_{q}(e^{\xi/m})}-1\right||ds|\ll\max_{1+u\xi\leq
t\leq\pi m}\left|\frac{G_{q}(e^{-s/m})}{G_{q}(e^{\xi/m})}-1\right|,$

which is acceptable by Lemma 5.1. It remains to study

$\frac{1}{2\pi i}\int_{-\xi+i(1+u\xi)}^{-\xi+i\pi
m}\frac{e^{us}}{s}e^{T(-s)}\left(\frac{G_{q}(e^{-s/m})}{G_{q}(e^{\xi/m})}-1\right)ds.$

We write $e^{T(-s)}$ as $1+(e^{T(-s)}-1)$. Since
$e^{T(-s)}-1=O(|s|/m+|s|^{2}/m^{2})$ by Lemma 2.7, we have by the triangle
inequality

$\displaystyle\int_{-\xi+i(1+u\xi)}^{-\xi+i\pi
m}\frac{e^{us}}{s}\left(e^{T(-s)}-1\right)$
$\displaystyle\left(\frac{G_{q}(e^{-s/m})}{G_{q}(e^{\xi/m})}-1\right)ds$
(5.10) $\displaystyle\ll\max_{1+u\xi\leq t\leq\pi
m}\left|\frac{G_{q}(e^{-s/m})}{G_{q}(e^{\xi/m})}-1\right|\int_{-\xi+i(1+u\xi)}^{-\xi+i\pi
m}\
\left|\frac{e^{us}}{s}\right|\left(\frac{|s|}{m}+\frac{|s|^{2}}{m^{2}}\right)|ds|$
(5.11) $\displaystyle\ll\max_{1+u\xi\leq t\leq\pi
m}\left|\frac{G_{q}(e^{-s/m})}{G_{q}(e^{\xi/m})}-1\right|e^{-u\xi}$ (5.12)

which is acceptable by Lemma 5.1. It remains to estimate

$\int_{-\xi+i(1+u\xi)}^{-\xi+i\pi
m}\frac{e^{us}}{s}\left(\frac{G_{q}(e^{-s/m})}{G_{q}(e^{\xi/m})}-1\right)ds.$
(5.13)

We may replace the expression in the parenthesis with
$\sum_{j=m+1}^{2m}a_{j}(e^{-js/m}-e^{j\xi/m})/j$ and incur an acceptable
error, according to Lemma 5.1, where $a_{j}\ll q^{-\lceil j/2\rceil}$. If
$u\geq 3$, we apply the Perron-type estimate

$\int_{-\xi+i(1+u\xi)}^{-\xi+i\pi
m}\frac{e^{(u-j/m)s}}{s}ds\ll\frac{e^{-(u-j/m)\xi}}{(1+u\xi)|u-j/m|},$

which is valid for all $j\geq 0$ and established by integration by parts.
Multiplying it by $a_{j}/j$ and summing over $j$, we see that (5.13) is
acceptable. If $u\leq 3$, Theorem 1.7 is already in (1.19).

###  5.3 Size of $x-x_{q}$

######  Lemma 5.2.

If $n\geq m\geq 1$ then

$x_{q}\leq x.$

Fix a prime power $q$ and $\varepsilon>0$. Uniformly in
$(2-\varepsilon)\log_{q}n\geq m\geq(3/4)\log_{q}n$ we have

$\frac{\min\\{n,q^{m}\\}}{q^{m}m}\frac{1}{1-\frac{x_{q}}{q}}\gg_{q}x-x_{q}\gg_{q}\frac{(\min\\{n,q^{m}\\})^{2}}{q^{m}nm}.$

###### Proof.

Let

$F(z):=\exp\left(\sum_{i=1}^{m}\frac{z^{i}}{i}\right)$ (5.14)

be the generating function of $\\{p_{n,m}\\}_{n\geq 0}$, and recall the
definition of $F_{q}$ given in (1.25). In this notation, $G_{q}$ is simply
$F_{q}/F$. We can write $G_{q}$ as

$G_{q}(z)=\exp\left(\sum_{i=m+1}^{\infty}\frac{a_{i}z^{i}}{i}\right)$ (5.15)

where $a_{i}$ are non-negative numbers, depending on $q$, that are described
in [Gor22b, Lem. 2.1]. Let $f(z):=z(\log F(z))^{\prime}=\sum_{i=1}^{m}z^{i}$
and $g_{q}(z):=z(\log G_{q}(z))^{\prime}=\sum_{i=m+1}^{\infty}a_{i}z^{i}$. By
definition,

$n=f(x)=f(x_{q})+g_{q}(x_{q}).$ (5.16)

Since $f$ and $g_{q}$ have non-negative coefficients, the first part of the
lemma follows at once. We now assume $(2-\varepsilon)\log_{q}n\geq
m\geq(3/4)\log_{q}n$. We use (5.16) to determine the size of $x-x_{q}$. By the
mean value theorem,

$0\leq
x-x_{q}=f^{-1}(n)-f^{-1}(n-g_{q}(x_{q}))=\frac{g_{q}(x_{q})}{f^{\prime}(f^{-1}(n-t))}$

for some $t\in[0,g_{q}(x_{q})]$, where $f^{-1}$ is the inverse of $f$. Since
$f^{-1}$ and $f^{\prime}$ are monotone increasing we have
$f^{\prime}(f^{-1}(n-t))\in[f^{\prime}(x_{q}),f^{\prime}(x)]$ and so

$x-x_{q}\in\left[\frac{g_{q}(x_{q})}{f^{\prime}(x)},\frac{g_{q}(x_{q})}{f^{\prime}(x_{q})}\right].$
(5.17)

We have the trivial bounds $1\leq x\leq n^{1/m}\ll_{q}1$ and so
$f^{\prime}(x)=\lambda/x=\Theta_{q}(nm)$ by Lemma 4.1. We also have

$g_{q}(x_{q})\geq a_{2m}x_{q}^{2m}\gg q^{-m}x_{q}^{2m}$

since $a_{i}\geq 0$ and $a_{2m}\gg q^{-m}$ by [Gor22b, Lem. 2.1]. It follows
that

$x-x_{q}\gg_{q}\frac{x_{q}^{2m}}{q^{m}nm}.$

Lemma 2 and Theorem 2 of [Man92b] estimate $x_{q}$ and yield that, when
$2\log_{q}n\geq m\geq(3/4)\log_{q}n$,

$x_{q}^{m}=\Theta_{q}(\min\\{n,q^{m}\\}),$ (5.18)

implying the desired lower bound on $x-x_{q}$. To prove the upper bound,
observe

$g_{q}(x_{q})\ll_{\varepsilon}q^{m}\sum_{i\geq
2m}\frac{x_{q}^{i}}{q^{i}}\ll\frac{x_{q}^{2m}}{q^{m}}\frac{1}{1-\frac{x_{q}}{q}}$

since $a_{i}\ll\min\\{q^{-\lceil i/2\rceil},q^{m-i}\\}$ [Gor22b, Lem. 2.1]. To
conclude we use
$f^{\prime}(x_{q})=x_{q}^{-1}\sum_{i=1}^{m}ix_{q}^{i}\gg_{q}mx_{q}^{m}$. ∎

###  5.4 Proof of Theorems 1.9 and 1.10

Fix $q$. Recall the functions $F$ and $G_{q}$ as given in (5.14) and (5.15),
and the fact that $G_{q}=F_{q}/F$. If $m\to\infty$ and $u\geq(\log\log
m)^{3}\log m$, Manstavičius proved in [Man92b, Man92a] that

$p_{n,m,q}=\frac{F_{q}(x_{q})}{x_{q}^{n}\sqrt{2\pi\lambda_{q}}}\left(1+O\left(\frac{m}{n}+\frac{m}{q^{m}}\right)\right)$
(5.19)

where

$\lambda_{q}:=\lambda_{n,m,q}=z\left(\frac{zF^{\prime}_{q}(z)}{F_{q}(z)}\right)^{\prime}|_{z=x_{q}}.$

We divide (5.19) by (1.9), and use the fact that $\lambda$ is asymptotic $nm$
by Lemma 4.1 as long as $u\to\infty$, and

$\lambda_{q}\sim nm\left(1+\frac{n}{q^{m}}\left(1-\frac{1}{q}\right)\right)$

by Theorem 2 of [Man92b] as long as $u\to\infty$ and $m\to\infty$, to obtain

$\frac{p_{n,m,q}}{p_{n,m}G_{q}(x)}\sim\left(1+\frac{n}{q^{m}}\left(1-\frac{1}{q}\right)\right)^{-1/2}\frac{x^{n}F(x_{q})G_{q}(x_{q})}{x_{q}^{n}F(x)G_{q}(x)}=\exp\left(H_{q}(x_{q})-H_{q}(x)\right)\left(1+\frac{n}{q^{m}}\left(1-\frac{1}{q}\right)\right)^{-1/2}$
(5.20)

as $n\to\infty$ if $(2-\varepsilon)\log_{q}n\geq m>\log_{q}n$, where

$H_{q}(z):=\log F_{q}(z)-n\log z=\log F(z)+\log G_{q}(z)-n\log z.$

In the same way,

$\frac{p_{n,m,q}}{p_{n,m}G_{q}(x_{q})}\sim\frac{x^{n}F(x_{q})G_{q}(x_{q})}{x_{q}^{n}F(x)G_{q}(x_{q})}\left(1+\frac{n}{q^{m}}\left(1-\frac{1}{q}\right)\right)^{-1/2}=\exp\left(H(x_{q})-H(x)\right)\left(1+\frac{n}{q^{m}}\left(1-\frac{1}{q}\right)\right)^{-1/2}$
(5.21)

if $u\geq(\log\log m)^{3}\log m$ and $m\to\infty$, where

$H(z):=\log F(z)-n\log z.$

Both $\log F$ and $\log G_{q}$ have non-negative Taylor coefficients at $t=0$.
By definition,

$H^{\prime}_{q}(x_{q})=H^{\prime}(x)=0.$ (5.22)

Taylor-expanding $H_{q}$ and using $x_{q}\leq x$ (by Lemma 5.2), we have

$H_{q}(x)-H_{q}(x_{q})=\frac{H^{\prime\prime}_{q}(x_{q})}{2}(x-x_{q})^{2}+O\left(H^{(3)}_{q}(x)(x-x_{q})^{3}\right).$

The coefficients $a_{i}$, defined in (5.15), satisfy $a_{i}\ll
q^{\min\\{m-i,-\lceil i/2\rceil\\}}$ according to [Gor22b, Lem. 2.1]. Hence,
as long as $m\geq(1+\varepsilon)\log_{q}n$,

$H_{q}^{(3)}(x)=\sum_{i=1}^{m}(i-1)(i-2)x^{i-3}+\sum_{i=m+1}^{\infty}(i-1)(i-2)a_{i}x^{i-3}-\frac{2n}{x^{3}}\ll_{q,\varepsilon}nm^{2}.$

Moreover, since $H_{q}^{\prime\prime}(x_{q})=\lambda_{q}/x_{q}^{2}$, we have
$H_{q}^{\prime\prime}(x_{q})=\Theta_{q}(nm)$ in the same range. Using Lemma
5.2 it follows that $H_{q}(x)-H_{q}(x_{q})\sim
H_{q}^{\prime\prime}(x_{q})(x-x_{q})^{2}/2=\Theta_{q,\varepsilon}(n^{3}/(mq^{2m}))$
when $(2-\varepsilon)\log_{q}n\geq m\geq(1+\varepsilon)\log_{q}n$ and
$m\to\infty$. We plug this estimate in (5.20) to conclude the proof of Theorem
1.9.

We now suppose $(2-\varepsilon)\log_{q}n\geq m\geq(3/4)\log_{q}n$. Observe

$\frac{H^{\prime\prime}(x)}{2}(x-x_{q})^{2}\geq
H(x_{q})-H(x)\geq\frac{H^{\prime\prime}(x_{q})}{2}(x-x_{q})^{2}.$

We can lower bound $H^{\prime\prime}(x_{q})$ by
$(m-1)x_{q}^{m-2}\gg_{q}mx_{q}^{m}$, since $x_{q}<q$. We can upper bound
$H^{\prime\prime}(x)$ by $\ll_{q}nm$. We estimate $x_{q}^{m}$ using (5.18).
Lemma 5.2 bounds $x-x_{q}$. It remains to estimate $G_{q}(x_{q})$. For a lower
bound we use $\log G_{q}(x_{q})\geq a_{2m}x_{q}^{2m}/(2m)\gg
x_{q}^{2m}/(mq^{m})$. Here we used $a_{i}\geq 0$ and $a_{2m}=\Theta(q^{-m})$
[Gor22b, Lem. 2.1]. For the upper bound we use $a_{i}\ll\min\\{q^{-\lceil
i/2\rceil},q^{m-i}\\}$ to obtain $\log G_{q}(x_{q})\ll
x_{q}^{2m}/(m(1-x_{q}/q))$. When $m\geq(1+\varepsilon)\log_{q}n$, notice
$x_{q}\leq x\leq n^{1/m}\leq q^{\frac{1}{1+\varepsilon}}$ so
$1-x_{q}/q\gg_{\varepsilon,q}1$.

## References

  * [Car87] Mireille Car.  Théorèmes de densité dans ${\bf F}_{q}[X]$.  Acta Arith., 48(2):145–165, 1987.
  * [dB51a] N. G. de Bruijn.  The asymptotic behaviour of a function occurring in the theory of primes.  J. Indian Math. Soc. (N.S.), 15:25–32, 1951.
  * [dB51b] N. G. de Bruijn.  On the number of positive integers $\leq x$ and free of prime factors $>y$.  Nederl. Acad. Wetensch. Proc. Ser. A., 54:50–60, 1951.
  * [dlBT05] R. de la Bretèche and G. Tenenbaum.  Entiers friables: inégalité de Turán-Kubilius et applications.  Invent. Math., 159(3):531–588, 2005.
  * [For22] Kevin Ford.  Cycle type of random permutations: a toolkit.  Discrete Anal., 9:1–36, 2022.
  * [GHS15] Andrew Granville, Adam J. Harper, and Kannan Soundararajan.  Mean values of multiplicative functions over function fields.  Res. Number Theory, 1:Paper No. 25, 18, 2015.
  * [Gon44] V. Goncharov.  Über das Gebiet der kombinatorischen Analysis.  Izv. Akad. Nauk SSSR, Ser. Mat., 8:3–48, 1944.
  * [Gor22a] Ofir Gorodetsky.  Friable integers and the Dickman $\rho$ function.  arXiv preprint arXiv:2211.08973, 2022.
  * [Gor22b] Ofir Gorodetsky.  Uniform estimates for friable polynomials over finite fields.  2022 (accessed November 16, 2022).  To appear in Discrete Analysis. Available on https://people.maths.ox.ac.uk/gorodetsky/friable%20polynomials.pdf.
  * [Hil84] Adolf Hildebrand.  Integers free of large prime factors and the Riemann hypothesis.  Mathematika, 31(2):258–271 (1985), 1984.
  * [Hil86] Adolf Hildebrand.  On the number of positive integers $\leq x$ and free of prime factors $>y$.  J. Number Theory, 22(3):289–307, 1986.
  * [Man92a] E. Manstavichyus.  Remarks on elements of semigroups that are free of large prime factors.  Liet. Mat. Rink., 32(4):512–525, 1992.
  * [Man92b] E. Manstavičius.  Semigroup elements free of large prime factors.  In New trends in probability and statistics, Vol. 2 (Palanga, 1991), pages 135–153. VSP, Utrecht, 1992.
  * [MP16] Eugenijus Manstavičius and Robertas Petuchovas.  Local probabilities for random permutations without long cycles.  Electron. J. Combin., 23(1):Paper 1.58, 25, 2016.
  * [Ten15] Gérald Tenenbaum.  Introduction to analytic and probabilistic number theory, volume 163 of Graduate Studies in Mathematics.  American Mathematical Society, Providence, RI, third edition, 2015.  Translated from the 2008 French edition by Patrick D. F. Ion.
  * [War91] R. Warlimont.  Arithmetical semigroups. II. Sieving by large and small prime elements. Sets of multiples.  Manuscripta Math., 71(2):197–221, 1991.
  * [Wen48] J. G. Wendel.  Note on the gamma function.  Amer. Math. Monthly, 55:563–564, 1948.

Mathematical Institute, University of Oxford, Oxford, OX2 6GG, UK

E-mail address<EMAIL_ADDRESS>