Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-23T14:58:58.399Z Has data issue: false hasContentIssue false

Smooth permutations and polynomials revisited

Published online by Cambridge University Press:  11 December 2024

OFIR GORODETSKY*
Affiliation:
Department of Mathematics, Technion - Israel Institute of Technology, Haifa, 3200003, Israel. e-mail: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

We study the counts of smooth permutations and smooth polynomials over finite fields. For both counts we prove an estimate with an error term that 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.

We determine the order of magnitude of $\log(p_{n,m}/\rho(n/m))$ where $p_{n,m}$ is the probability that a permutation on n elements, chosen uniformly at random, is m-smooth.

We uncover a phase transition in the polynomial setting: the probability that a polynomial of degree n in $\mathbb{F}_q$ is m-smooth changes its behaviour at $m\approx (3/2)\log_q n$.

Type
Research Article
Creative Commons
Creative Common License - CCCreative Common License - BY
This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (https://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.
Copyright
© The Author(s), 2024. Published by Cambridge University Press on behalf of Cambridge Philosophical Society

1. Introduction

A permutation is said to be 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{-smooth})\]

be the probability that a permutation from $S_n$ chosen uniformly at random is m-smooth. 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'(t)+\rho(t-1) =0$ for $t \gt 1$ with initial conditions $\rho(t)=1$ for $t \le 1$ . It is weakly decreasing, and de Bruijn proved that it satisfies

(1·1) \begin{equation} \rho(u) = \exp\!\left( -u\log (u \log u)+ u + O\left(\frac{u \log \log u}{\log u}\right)\right)\end{equation}

for $u \ge 3$ [ Reference de Bruijn2 ]. Goncharov [ Reference Goncharov7 ] 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)$ . In an impressive work, Manstavičius and Petuchovas [ Reference Manstavičius and Petuchovas13 ] established asymptotic estimates for $p_{n,m}$ in the entire range $1 \le m \le n$ , including the estimate [ Reference Manstavičius and Petuchovas13 , theorem 4]

(1·2) \begin{equation} {}p_{n,m} = \rho(u) \left(1+ O\left( \frac{u \log (u+1)}{m}\right)\right)\end{equation}

which holds for $n \ge m \ge \sqrt{n \log n}$ . Recently, Ford [ Reference Ford6 , theorem 1·17] proved that

(1·3) \begin{equation} {}\rho\left( \frac{n}{m}\right) \le p_{n,m} \le \rho\left(\frac{n+1}{m+1}\right)\end{equation}

holds uniformly for $n \ge m \ge 1$ . This almost immediately leads to

(1·4) \begin{equation} {}p_{n,m} = \rho(u) \exp\!\left(O\left( \frac{u \log (u+1)}{m}\right)\right)\end{equation}

holding in $n \ge m \ge 1$ [ Reference Gorodetsky8 , proposition 1·8], extending (1·2). Theorems 1·11·2 below, whose proofs borrow heavily from [ Reference Manstavičius and Petuchovas13 ], improve on (1·4).

Theorem 1·1. Uniformly for $n \ge m \ge \sqrt{n \log n}$ we have

(1·5) \begin{equation} {}p_{n,m} = \rho\left(\frac{n}{m+\frac{1}{2}}\right)\left(1+O\left(\frac{\log(u+1)}{m}\right)\right).\end{equation}

Uniformly for $\sqrt{n\log n} \ge m \ge 1$ we have

\[ {} {}p_{n,m} = \rho\left(\frac{n}{m+\frac{1}{2}}\right) \exp\!\left(O\left(\frac{u\log^2(u+1)}{m^2} \right)\right).\]

We may combine both parts of Theorem 1·1 as

\[p_{n,m} = \rho\left(\frac{n}{m+\frac{1}{2}}\right) \exp\!\left(O\left(\frac{\log(u+1)}{m}+\frac{u\log^2(u+1)}{m^2} \right)\right)\]

uniformly for $n \ge m \ge 1$ . We see $p_{n,m} \sim \rho\left({n}/({m+\frac{1}{2}})\right)$ holds when $m/(n^{1/3}(\log n)^{2/3})$ $\to \infty$ .

The error term $O(\log(u+1)/m)$ in (1·5) is of particular importance, as we now explain. We say that a positive integer is y-smooth if all its prime factors are at most y, and we denote

\[\Psi(x,y) \;:\!=\; \#\{ 1\le n \le x: n \text{ is }y\text{-smooth}\}.\]

Setting $n'\;:\!=\;\log x$ , $m'\;:\!=\;\log y$ and $u'\;:\!=\;n'/m'$ , de Bruijn [ Reference de Bruijn4 ] showed that, in the range $n' \ge m' \ge n'^{5/8+\varepsilon}$ , the estimate

\[ \frac{\Psi(x,y)}{x} = \rho(u')\left(1+O_{\varepsilon}\left(\frac{\log (u'+1)}{m'}\right)\right)\]

holds. This error term, $O_{\varepsilon}\left({\log (u'+1)}/{m'}\right)$ , is analogous to (1·5).

Remark 1. The main term $\rho\left({n}/({m+\frac{1}{2}})\right)$ of Theorem 1·1 arises indirectly. We first prove an estimate with a more complicated main term, see Proposition 3·1. This term originally appeared in [ Reference Manstavičius and Petuchovas13 , corollaries 3, 5], where it serves as an approximation to $p_{n,m}$ in a narrow range and with a worse error term compared to Theorem 1·1. In Lemma 3·2 we simplify the complicated main term and show it may be replaced by $\rho\left({n}/(m+(\frac{1}{2})\right)$ at a negligible cost.

Remark 2. Ford’s proof of (1·3) avoids complex analysis and it will be interesting to have a similar argument estimating $p_{n,m}$ relative to $\rho\left({n}/({m+\frac{1}{2}})\right)$ .

Theorem 1·1 is weaker than (1·4) when $m=o(\log n)$ . We complement it with

Theorem 1·2. If $2\le m\le n$ satisfies $m=O(\log n)$ then

\[ {} {}p_{n,m} =\left( \frac{e}{n}\right)^u \exp\bigg( u \bigg(-\log\big(1-n^{-\frac{1}{m}}\big)+O\bigg( \frac{n^{-\frac{1}{m}}}{m} \bigg) \bigg)\bigg).\]

The proof of Theorem 1·2 relies on estimates from [ Reference Manstavičius and Petuchovas13 ]. Theorem 1·2 is only claimed for $m \ge 2$ , as it gives a wrong estimate if applied with $m=1$ . By Stirling’s approximation, $p_{n,1}=1/n! \asymp (e/n)^n n^{-1/2}$ if $m=1$ .

From (1·4) and Theorem 1·2 we see that $\log p_{n,m} \sim \log \rho(u)$ holds as $n\to \infty$ . Using Theorems 1·11·2 we determine the order of magnitude of $\log(p_{n,m}/\rho(u))$ :

Corollary 1·3. Define A via $p_{n,m}=\rho(u)\exp(A)$ . Uniformly for $n \ge m \ge 1$ ,

\[ A \asymp u \log \left(1 + \frac{\log u}{m}\right).\]

1·1. Results for smooth polynomials

A polynomial over a finite field $\mathbb{F}_q$ is said to be m-smooth if all its irreducible factors have degrees at most m. 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-smooth. Manstavičius [ Reference Manstavichyus11 , theorem 2] proved that

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

holds in range $n\ge m \ge \sqrt{n\log n}$ . Recently, the author proved that for fixed $\varepsilon \gt 0$ , the ratio $p_{n,m,q}/p_{n,m}$ satisfies

(1·6) \begin{equation} {}\frac{p_{n,m,q}}{p_{n,m}} =1+ O_{\varepsilon}\left(\frac{u n^{\frac{1+\mathbf{1}_{2 \mid m}}{m}} \min\{ m, \log(u+1)\}}{m q^{\lceil \frac{m+1}{2}\rceil}}\right)\end{equation}

for $n \ge m \ge (2+\varepsilon)\log_q n$ [ Reference Gorodetsky8 , theorems 1, 2]. The implied constant does not depend on q. From (1·6) and Theorem 1·1 we immediately obtain

Corollary 1·4. Uniformly for $n\ge m\ge \sqrt{n\log n}$ we have

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

Fix $\varepsilon \gt 0$ . Uniformly for $\sqrt{n\log n}\ge m \ge (2+\varepsilon)\log_q n $ we have

\[p_{n,m,q} = \rho\left(\frac{n}{m+\frac{1}{2}}\right) \exp\!\left( O_{\varepsilon}\left( \frac{u\log^2(u+1)}{m^2} \right)\right).\]

The rest of our results concern $p_{n,m,q}/p_{n,m}$ . To obtain estimates with better range and error than (1·6) we introduce a function $G_q(z)$ . The generating function of $\{p_{n,m,q}\}_{n \ge 0}$ is

(1·7) \begin{equation} {}F_q(z)\;:\!=\;\prod_{\substack{P \in \mathcal{P} \\[5pt] \deg(P) \le m}} \bigg(1- \bigg(\frac{z}{q}\bigg)^{\deg (P)}\bigg)^{-1},\end{equation}

where $\mathcal{P}=\mathcal{P}_{q}$ is the set of monic irreducible polynomials over $\mathbb{F}_q$ . It is analytic in $|z| \lt q$ . The generating function of $\{p_{n,m}\}_{n \ge 0}$ is the entire function [ Reference Manstavičius and Petuchovas13 ]

(1·8) \begin{equation} F(z)\;:\!=\;\exp\!\left(\sum_{i=1}^{m} \frac{z^i}{i}\right).\end{equation}

For $|z| \lt q$ we define

(1·9) \begin{equation}G_q(z) \;:\!=\; \frac{F_q(z)}{F(z)}.\end{equation}

The function $G_q$ is studied in [ Reference Gorodetsky8 , lemma 2·1]. By [ Reference Gorodetsky8 , theorem 1·3] we have

(1·10) \begin{equation} {}\frac{p_{n,m,q}}{p_{n,m}} = G_q(x) \bigg(1+ O_{\varepsilon}\bigg(\frac{n^{\frac{1+\mathbf{1}_{2 \mid m}}{m}} \min\{m, \log (u+1)\}}{mq^{\lceil \frac{m+1}{2}\rceil}} \bigg)\bigg)\end{equation}

in the range $n/(\log n \log^3 \log(n+1)) \ge m \ge (2+\varepsilon)\log_q n$ , where $x=x_{n,m}$ is the unique positive solution to

(1·11) \begin{equation} {}\sum_{i=1}^{m} x^i = n.\end{equation}

In that range, $G_q(x)$ is very close to 1, see [ Reference Gorodetsky8 , lemmas 5·3-5·4]. We complement (1·10) with a result for large m. We define $\xi(u)\ge 0$ by $e^{\xi(u)} = 1+u\xi(u)$ .

Theorem 1·5. If $n \ge m\ge \sqrt{10n \log n}$ then

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

Using Theorem 1·5 we are able to drop the condition $n/(\log n\log^3 \log(n+1)) \ge m$ present in (1·10):

Corollary 1·6. The estimate (1·10) holds uniformly for $n \ge m \ge (2+\varepsilon)\log_q n$ .

We turn to smaller m. In the range $(2-\varepsilon)\log_q n \ge m \ge (1+\varepsilon)\log_q n$ ,

\[ \log G_q(x) \asymp_{q,\varepsilon} \frac{n^2}{mq^m},\]

see [ Reference Gorodetsky8 , lemma 5·4]. In [ Reference Gorodetsky8 , theorem 1·3] it is shown that $p_{n,m,q}/p_{n,m} \sim G_q(x)$ holds as $n \to \infty$ as long as $m \ge (3/2+\varepsilon)\log_q n$ . Our next result shows that $p_{n,m,q}/p_{n,m}$ experiences a transition when m is close to $(3/2)\log_q n$ .

Theorem 1·7. Fix a prime power q and $\varepsilon \gt 0$ . There is a quantity $A \gt 0$ of order

\[ A \asymp_{q,\varepsilon} \frac{n^3}{mq^{2m}}\]

such that, for $(2-\varepsilon)\log_q n \ge m \ge (1+\varepsilon)\log_q n$ we have, as $n \to \infty$ ,

\[\frac{p_{n,m,q}}{p_{n,m}} \sim G_q(x)\exp( -A).\]

In particular, if $q^m=n^{\tau}$ where $\tau\in(1,2)$ then $A\asymp_{q,\varepsilon} ({n^{3-2\tau}}/{\log n})$ and so $A\gg_{q,\varepsilon}1$ if $q^m =O( n^{3/2}/(\log n)^{1/2})$ .

Conventions. The letters C,c shall denote absolute positive constants which may change between different instances. The notation $A \ll B$ means $|A| \le C B$ 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\asymp_{a,b,\ldots}B$ to indicate $cB \le A \le C B$ holds for $C,c \gt 0$ that may depend on $a,b,\ldots$ .

2. Auxiliary estimates and functions

2·1. Saddle point review

By [ Reference Manstavičius and Petuchovas13 , theorem 2 and corollary 5], uniformly for $n \ge m \ge 1$ we have

(2·1) \begin{equation} {}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),\end{equation}

where $x=x_{n,m}$ is the saddle point defined as the unique positive solution to (1·11), and $\lambda=\lambda_{n,m}$ is defined as

(2·2) \begin{equation} {}\lambda = \sum_{i=1}^{m} ix^i.\end{equation}

Lemma 2·1. Uniformly for $n \ge m \ge 1$ , the following estimates hold: $n^{1/m} \ge x \gg n^{1/m}$ , $nm \ge \lambda \gg nm$ and $\lambda= nm( 1+ O(1/\max\{ \log u,n^{1/m}\}))$ .

Proof. We study x. Considering only the $i=m$ term in (1·11) gives $x \le n^{1/m}$ . If $x \lt 1$ then $\sum_{i=1}^m x^i \lt m \le n$ , a contradiction, hence $x \ge 1$ . Consequently, by the definition of x, $mx^m \ge n$ holds, which implies

\[ {}x \ge n^{\frac{1}{m}} m^{-\frac{1}{m}} \ge n^{\frac{1}{m}}e^{-\frac{1}{e}}.\]

We turn to $\lambda$ . We have $\lambda \le m \sum_{i=1}^{m} x^i = nm$ . By [ Reference Manstavičius and Petuchovas13 , lemma 9],

(2·3) \begin{equation} {} {}\lambda = nm(1+O(1/\log u)) {}\end{equation}

uniformly for $u \gt 1$ . We also have $x^m \le n=\sum_{i=1}^{m} x^i \lt x^m/(1-x^{-1})$ and so

\[ {}mn(1-x^{-1}) \lt mx^m \le \sum_{i=1}^{m}ix^i = \lambda \le nm \]

implying $\lambda=nm(1+O(x^{-1}))=nm(1+O(n^{-1/m}))$ . The estimate (2·3) already shows $\lambda \gg nm$ when $u \ge C$ . If $u \lt C$ then, since $x \ge 1$ , we find $\lambda \ge \sum_{i=1}^{m} i \gg nm$ .

2·2. Dickman function review

We define $\xi \colon [1,\infty) \to [0,\infty)$ , a function of variable $u\ge 1$ , by

\[e^{\xi(u)} = 1+u\xi(u).\]

Lemma 2·2 [ Reference Hildebrand9 , lemma 1]. We have $\xi \sim \log u$ as $u \to \infty$ , and $\xi'=u^{-1}(1+O(1/\log u))$ for $u \ge 2$ .

Lemma 2·3 [ Reference Manstavičius and Petuchovas13 , lemma 6]. If $u \gt 1$ we have $\log u \lt \xi \le 2 \log u$ .

Let

\[ {}I(s) = \int_{0}^{s} \frac{e^t-1}{t} {\textrm{d}}t\]

which defines an entire function. Observe that

\[ I'(\xi) = \frac{e^{\xi}-1}{\xi}=u,\]

and a short computation shows $I''(\xi)=1/\xi'$ . The following lemma is proved by induction.

Lemma 2·4. For any $k \ge 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·5. For any fixed $k \ge 1$ we have $I^{(k)}(\xi) =(1+O_k(1/\log u))({e^{\xi}}/{\xi})\sim u$ as $u \to \infty$ , and $I^{(k)}(\xi+it) \ll_k \min\{u, e^{\xi(u)}/|\xi+it|\}$ uniformly for $t \in \mathbb{R}$ .

The function I arises when studying $\rho$ and its Laplace transform.

Lemma 2·6. [ Reference de Bruijn3 , equation (1·9)] [ Reference Alladi1 , equation (3·9)]. Let $\gamma$ be the Euler–Mascheroni constant. We have

\[ {}\hat{\rho}(s) \;:\!=\; \int_{0}^{\infty} e^{-sv}\rho(v)\, {\textrm{d}}v = \exp\!\left( \gamma + I(-s) \right)\]

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

(2·4) \begin{equation} {} {}\rho(u)=\frac{1}{\sqrt{2\pi I''(\xi)}}\exp\!\left( \gamma-u\xi + I(\xi)\right)(1 + O( u^{-1})). {}\end{equation}

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

Lemma 2·7. [ Reference Hildebrand and Tenenbaum10 , lemma 2·7] The following bounds hold for $s=-\xi(u)+it$ :

\[ {} {}\hat{\rho}(s) = \begin{cases} O\left(\exp\!\left(I(\xi)-\frac{t^2u}{2\pi^2}\right)\right) & \text{if }|t| \le \pi,\\[5pt] {} {} {}O\left(\exp\!\left(I(\xi)-\frac{u}{\pi^2+\xi^2}\right)\right) & \text{if }|t| \ge \pi,\\[5pt] {} {} {}\frac{1}{s} + O\left( \frac{1+u \xi }{|s|^2} \right) & \text{if }1+u\xi =O(|t|).\end{cases}\]

2·3. T

We define the following function, holomorphic in the strip $|\Im s | \lt 2\pi m$ :

\[ {}T(s) \;:\!=\; \int_{0}^{s} \frac{e^t-1}{t}\left( \frac{\frac{t}{m}}{1-e^{-t/m}}-1\right){\textrm{d}}t.\]

The Bernoulli numbers $B_i$ are defined by

\[\frac{s}{1-e^{-s}} = 1+\frac{s}{2} +\frac{s^2}{12}-\frac{s^4}{720}+ \ldots = \sum_{i\ge 0} B_i \frac{s^i}{i!}.\]

This series converges for $|\Im s| \lt 2\pi$ . It is known that $B_i \ll i!/(2\pi)^i$ . It is then easy to see, from the estimate $\int_{0}^{s} (e^t-1)t^{i-1} {\textrm{d}}t \ll |s|^{i-1} (|e^s|+|s|)$ which holds for $\Re s \ge 0$ and $i \ge 1$ , that

(2·5) \begin{equation} {}T(s) = \sum_{i=1}^{k} \frac{B_i}{m^i i!} \int_{0}^{s} (e^t-1)t^{i-1} {\textrm{d}}t + O\bigg( \frac{|s|^k (|e^{s}|+|s|)}{(2\pi m)^{k+1}} \bigg)\end{equation}

holds for $k \ge 0$ and $s=\sigma+it$ with $\sigma \in [0,\pi m]$ and $t \in [\!-\pi m,\pi m]$ . Applying (2·5) with $k=1$ we obtain

Corollary 2·8. [ Reference Manstavičius and Petuchovas13 , lemma 11]. For $s=\sigma+it$ with $\sigma\in [0,\pi m]$ and $t\in [\!-\pi m,\pi m]$ ,

\[ {}\left|T(s)+\frac{s}{2m}\right| \ll \frac{e^{\sigma}}{m} + \frac{t^2}{m^2}.\]

Applying (2·5) with $k=2$ and $s=\xi=\xi(u)$ we obtain

(2·6) \begin{equation}T(\xi) = \frac{(u-1)\xi}{2m} + \frac{e^{\xi}(\xi-1)-\frac{\xi^2}{2}+1}{12m^2} + O\bigg( \frac{u\log^3 (u+1)}{m^3}\bigg)\end{equation}

when $\xi(u) \le \pi m$ holds.

Lemma 2·9. Suppose $\xi=\xi(u) \le \pi m$ . For any $k \ge 1$ we have

(2·7) \begin{equation} {}\begin{split} {} {}T^{(k)}(\xi) &= I^{(k)}(\xi)\left( \frac{\xi/m}{1-e^{-\xi/m}}-1+O_k\left( \frac{1}{m}\right)\right) \\[5pt] {} {}&=\frac{e^{\xi}}{2m}\left(1+O_k\left(\frac{1}{\log(u+1)}+\frac{\log(u+1)}{m}\right)\right). {}\end{split} {}\end{equation}

If additionally $t \in [\!-\pi m, \pi m]$ then $T^{(k)}(\xi+it) \ll_k e^{\xi(u)}/m$ .

Proof. We have $T'(s) = I'(s) g(s/m)$ for $g(z)\;:\!=\;z/(1-e^{-z}) - 1$ . Repeated differentiation shows

(2·8) \begin{equation} {}T^{(k)}(s) = I^{(k)}(s) g(s/m)+O_k\bigg( \sum_{i=1}^{k-1}m^{-i} |I^{(k-i)}(s)g^{(i)}(s/m)|\bigg).\end{equation}

We suppose that $s=\xi(u) + it$ and that the inequalities $\xi(u)\le \pi m$ and $|t|\le \pi m$ are satisfied. From (2·8),

(2·9) \begin{equation} T^{(k)}(s) =I^{(k)}(s) g(s/m)+O_k\bigg( \frac{1}{m}\sum_{i=1}^{k-1} |I^{(k-i)}(s)|\bigg) {} {}\end{equation}

as our assumptions on s guarantee that $g^{(i)}(s/m)\ll_i 1$ . We first suppose $t=0$ and establish (2·7). Using (2·9) and the definition of g, the first equality in (2·7) will follow if we show that $I^{(k-i)}(\xi(u)) \ll_k I^{(k)}(\xi(u))$ , which is a consequence of Corollary 2·5. The second equality in (2·7) follows from another application of Corollary 2·5. Finally, the claim for $T^{(k)}(s)$ (when $|t|\le \pi m$ ) follows from (2·9) since $|I^{(k)}(s)| \ll_k e^{\xi(u)}/|s|$ and $|I^{(k-i)}(s)| \ll_k u$ ( $1\le i \le k-1$ ) by Corollary 2·5 and $|g(s/m)| \ll |s|/m$ .

2·4. $H_n$

Let $H_n\;:\!=\; \sum_{i=1}^{n} ({1}/{i})$ be the nth harmonic sum. By the Euler–Maclaurin formula,

(2·10) \begin{equation}H_n = \log n + \gamma + \frac{1}{2n} +O(n^{-2}).\end{equation}

3. Proof of Theorem 1·1

We break the theorem into a proposition and a lemma.

Proposition 3·1. Uniformly for $n \ge m \ge 1$ we have

(3·1) \begin{equation} {} {}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). {}\end{equation}

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

(3·2) \begin{equation}p_{n,m} = \rho(u) \exp\!\left( \frac{u\xi(u)}{2m}\right) \left(1 + O\left( \frac{\log (u+1)}{m}\right)\right).\end{equation}

In [ Reference Manstavičius and Petuchovas13 , corollaries 3, 5], (3·1) is proved in the narrower range $n \ge m \ge n^{1/3}(\log n)^{2/3}$ .

Lemma 3·2. Uniformly for $n \ge m \ge 1$ we have

(3·3) \begin{equation} \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)\end{equation}

and

(3·4) \begin{equation}\rho\left( u-\frac{u}{2m}\right) = \rho\left( \frac{n}{m+\frac{1}{2}}\right)\exp\!\left( O\left( \frac{u\log(u+1)}{m^2} \right)\right).\end{equation}

We prove (3·1) in Section 3·1, and (3·2) in Sections 3·23·3. The proof of Lemma 3·2 is given in Section 3·4. To deduce Theorem 1·1, we combine (3·2) and Lemma 3·2 if $m \ge \sqrt{n\log n}$ , and (3·1) and Lemma 3·2 if $m\le \sqrt{n\log n}$ . Here we use ${u}/{m^2}+{1}/{m} +{u\log(u+1)}/{m^2}\ll {\log(u+1)}/{m}$ when $m\ge \sqrt{n\log n}$ and ${1}/{u} + {u}/{m^2}+{1}/{m} +{u\log(u+1)}/{m^2}\ll {u\log^2(u+1)}/{m^2}$ when $m\le \sqrt{n\log n}$ .

3·1. Proof of the first part of Proposition 3·1

Here we prove (3·1). If $m=O(\log (u+1))$ then (3·1) follows from (1·4). Hence we suppose that $m \ge C \log (u+1)$ from now on. Similarly, if $u =O(1)$ then (3·1) is already in (1·4), so we suppose $u \ge C$ . We define a function

\[ D(z) \;:\!=\;z^{-n} \exp\!\left(\sum_{i=1}^{m} \frac{z^i}{i}\right), \]

so that x defined in (1·11) solves $D'(z)=0$ , and (2·1) can be written as

(3·5) \begin{equation} {}p_{n,m}= \frac{D(x)}{\sqrt{2 \pi \lambda}} (1+O( u^{-1})).\end{equation}

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 [ Reference Manstavičius and Petuchovas13 , equation (40)] for the details. We set

\[ \widetilde{\xi} \;:\!=\; m \log x\]

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

\[ \widetilde{u} \;:\!=\; \frac{e^{\widetilde{\xi}}-1}{\widetilde{\xi}}.\]

In this notation, (3·5) implies (using (2·4) with $\widetilde{u}$ in place of u, and (2·10)) that

\[ {}p_{n,m} = \rho(\widetilde{u}) \exp\!\left( (\widetilde{u}-u)\widetilde{\xi}\right) \exp \left(T(\widetilde{\xi})\right)\sqrt{ \frac{m^2 I''(\xi(\widetilde{u}))}{\lambda}}\exp\!\left( O\left(u^{-1}+ \widetilde{u}^{-1}+m^{-1}\right)\right)\]

for $u \ge C$ . A short computation shows that $u=I'(\xi)=(I+T)'(\widetilde{\xi})$ holds by the definition of $\xi$ , $\widetilde{\xi}$ and x. Since $T'(t) \ge 0$ for $t \ge 0$ we have $\widetilde{\xi}\le \xi$ and so, by the monotonicity of $I'(t)=(e^t-1)/t$ , it follows that

\[\widetilde{u}=I'(\widetilde{\xi})\le I'(\xi)=u.\]

By [ Reference Manstavičius and Petuchovas13 , equation (22)],

(3·6) \begin{equation}\widetilde{\xi} = \xi + O\left(\frac{\log (u+1)}{m}\right)\end{equation}

uniformly in $m \ge \log u \gt 0$ . From (3·6) we see that, uniformly in $m \ge \log u \gt 0$

(3·7) \begin{equation}\widetilde{u} = u + O\left( \frac{u\log(u+1)}{m}\right).\end{equation}

We will be using (3·6) and (3·7) frequently. For $m \ge \log u \gt 0$ we have

\[ \lambda = \frac{m^2}{\xi'(u)}\left(1+O\left( \frac{\log (u+1)}{m}\right)\right)\]

by [ Reference Manstavičius and Petuchovas13 , equation (23)]. Hence, since $I''(\xi(u))=1/\xi'(u)$ ,

\[ \sqrt{ \frac{m^2 I''(\xi(\widetilde{u}))}{\lambda }}=\sqrt{ \frac{m^2}{\lambda \xi'(\widetilde{u})}}=\sqrt{\frac{\xi'(u)}{\xi'(\widetilde{u})}} \exp\!\left(O\left(\frac{\log(u+1)}{m}\right)\right)\]

for $m \ge C\log (u+1) \gt 0$ . Since $\xi'(t)\asymp 1/t$ and $\xi''(t) =-\xi'(t)I^{(3)}(\xi(t))/I''(\xi(t))^2 \ll 1/t^2$ for $t \ge C$ ,

\[ \frac{\xi'(u)}{\xi'(\widetilde{u})} =1 +O\left( \frac{u-\widetilde{u}}{\widetilde{u}}\right) = \exp\!\left(O\left( \frac{\log(u+1)}{m}\right)\right)\]

holds for $m \ge C\log (u+1) \gt 0$ and $u \ge C$ and so

\[ \sqrt{ \frac{m^2I''(\xi(\widetilde{u}))}{\lambda}}= \exp\!\left(O\left(\frac{\log(u+1)}{m}\right)\right),\]

when $m \ge C\log (u+1) \gt 0$ and $u \ge C$ . At this point, we have established that

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

holds in our range. We have $\widetilde{\xi} \le \xi \le 2\log u \le \pi m$ by Lemma 2·3 and our assumption $m \ge C\log(u+1)$ . By (2·6), (3·6) and (3·7),

\[ {}T(\widetilde{\xi}) = \frac{\widetilde{u}\widetilde{\xi}}{2m} + O\bigg(\! \frac{u\log^2(u+1)}{m^2}+\frac{\log(u+1)}{m}\!\bigg)= \frac{u\xi(u)}{2m} + O\bigg( \!\frac{u\log^2(u+1)}{m^2} + \frac{\log(u+1)}{m}\!\bigg)\]

in this range. We now have

\[ {}p_{n,m} = \exp\bigg(\frac{u\xi(u)}{2m}\bigg)\rho(\widetilde{u}) \exp\big( (\widetilde{u}-u)\widetilde{\xi}\big) \exp\bigg( O\bigg(\frac{1}{u}+ \frac{u\log^2(u+1)}{m^2}\bigg)\bigg) \]

for $m \ge C\log (u+1)$ , $u \ge C$ . Let $r(t)=-\rho'(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){\textrm{d}}t\right).\]

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

\[ {}\int_{\widetilde{u}}^{u}r(t){\textrm{d}}t {}= (u-\widetilde{u})r(u) - \int_{\widetilde{u}}^{u} (t-\widetilde{u})r'(t) {\textrm{d}}t. \]

By [ Reference de la Bretèche and Tenenbaum5 , lemma 3·7], the estimates

(3·8) \begin{equation}r(v) = \xi(v) + O\left(v^{-1}\right), \qquad r'(v) = \xi'(v)+O\left(v^{-2}\right)\end{equation}

hold uniformly for $v \ge 1$ . Hence, using (3·6) and (3·7),

\begin{align*}\rho(\widetilde{u}) \exp( (\widetilde{u}-u)\widetilde{\xi}) &= \rho(u) \exp((u-\widetilde{u}) (r(u)-\xi(u)+\xi(u)-\widetilde{\xi}) \\[5pt] & \qquad - \int_{\widetilde{u}}^{u}(t-\widetilde{u})(r'(t)-\xi'(t)+\xi'(t)){\textrm{d}}t )\\[5pt] &=\rho(u) \exp\bigg( O\bigg(\frac{1}{u} + \frac{u\log^2(u+1)}{m^2}\bigg)-\int_{\widetilde{u}}^{u} (t-\widetilde{u})\xi'(t){\textrm{d}}t\bigg).\end{align*}

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

\[ \int_{\widetilde{u}}^{u}(t-\widetilde{u})\xi'(t){\textrm{d}}t\ll \int_{\widetilde{u}}^{u} \frac{t-\widetilde{u}}{t} {\textrm{d}}t = \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 \ge C\log (u+1)$ , using (3·6) and (3·7). The proof of (3·1) is completed.

3·2. Preliminary lemmas for second part of Proposition 3·1

The following consequence of Cauchy’s integral formula is implicit in the proofs of [ Reference Manstavičius and Petuchovas13 , theorems 2,4].

Lemma 3·3. 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)}{\textrm{d}}s.\]

The following lemma is implicit in the proof of [ Reference Manstavičius and Petuchovas13 , theorem 4].

Lemma 3·4. 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){\textrm{d}}s = \rho(u) +O\left( \frac{e^{-(u-1)\xi}}{n}\right).\]

A variant of the next lemma is implicit in the proof of [ Reference Manstavičius and Petuchovas13 , theorem 2].

Lemma 3·5. Suppose $\sqrt{n\log n}=O(m)$ and $1+u\xi \le A \le 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){\textrm{d}}s \ll \frac{e^{-u\xi}\log(u+1)}{m}. \]

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

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

\begin{multline*} {}\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} \\[5pt] -\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'(-s) e^{T(-s)-T(\xi)}\right){\textrm{d}}s.\end{multline*}

By Corollary 2·8, $T(-s)-T(\xi)$ is bounded in our range of integration. In fact, $T(-s)-T(\xi) \ll (e^{\xi}+|\Im s|)/m$ . Hence, the third case of Lemma 2·7 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}\]

which is acceptable. As for the integral, we rearrange it using the definition of T:

\begin{align*} {} {}\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'(-s) e^{T(-s)-T(\xi)}\right){\textrm{d}}s \\[5pt] {} {}&= {}\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){\textrm{d}}s. {}\end{align*}

By Corollary 2·8 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 last integral is

\begin{multline*} \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) |{\textrm{d}}s|\\[5pt] \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) |{\textrm{d}}s| \ll \frac{\log (u+1),}{m e^{u\xi}}\end{multline*}

where in the second inequality we used the third case of Lemma 2·7.

Lemma 3·6. Suppose $0 \le B \le A$ . Then, for every $k \ge 0$ ,

\[\frac{1}{2\pi i} \int_{-\xi+iB}^{-\xi+iA} \left| (s+\xi)^k e^{us} \hat{\rho}(s)\right|| {\textrm{d}}s| \ll_k \rho(u) \big( u^{-\frac{k}{2}} e^{-cuB^2} + A^{k+1}\sqrt{u}\exp\big(-\frac{u}{\xi^2+\pi^2}\big)\big).\]

The same is true if we integrate from $-\xi-iA$ to $-\xi-iB$ . In particular, for $B=0$ and $A\le \exp(c_k u/(\log (u+1))^2)$ ,

\[\frac{1}{2\pi i} \int_{-\xi-iA}^{-\xi+iA} \left| (s+\xi)^k e^{us} \hat{\rho}(s)\right|\left| {\textrm{d}}s\right| \ll_k \rho(u)u^{-\frac{k}{2}}.\]

Proof. Using the first two parts of Lemma 2·7, the triangle inequality shows that the integral is

\begin{multline*} {} {}\ll e^{-u\xi +I(\xi)} \int_{B}^{A} |t|^k \left(\exp(\!-cut^2)+\exp\big(-\frac{u}{\xi^2+\pi^2}\big)\right) {\textrm{d}}t\\[5pt] \ll_k e^{-u\xi +I(\xi)} \bigg( u^{-\frac{k+1}{2}} \exp(\!-cuB^2)+ A^{k+1}\exp\big(-\frac{u}{\xi^2+\pi^2}\big)\bigg), {}\end{multline*}

and we now use (2·4).

Lemma 3·7. Fix $k\ge 0$ . Let $\mu_m\;:\!=\;m!/((m/2)!2^{m/2})$ for even m. Suppose $\sqrt{n\log n}=O(m)$ and $C_k\sqrt{\log(u+1)/u}\le A \le \exp(c_ku/(\log (u+1))^2)$ . Then, for even k,

\[\frac{1}{2\pi i} \int_{-\xi-iA}^{-\xi+iA} (s+\xi)^ke^{us} \hat{\rho}(s){\textrm{d}}s = (1+O_k(u^{-1}))\rho(u) \mu_k (\!-\!1)^{\frac{k}{2}} \xi'^{\frac{k}{2}}\]

and for odd k,

\[\frac{1}{2\pi i} \int_{-\xi-iA}^{-\xi+iA} (s+\xi)^ke^{us} \hat{\rho}(s){\textrm{d}}s = (1+O_k(u^{-1}))\rho(u) \mu_{k+3} (\!-\!1)^{\frac{k+1}{2}} \xi'^{\frac{k+3}{2}} \frac{I^{(3)}(\xi)}{6}.\]

Proof. The contribution of $A \ge |\Im s| \ge C_k\sqrt{\log (u+1)/u}$ is acceptable by Lemma 3·6. We may now assume that $A=C_k\sqrt{\log (u+1)/u}$ . Recall $\hat{\rho}(s)=\exp(\gamma+I(-s))$ . We may Taylor-expand $I(\xi+it)$ using Corollary 2·5, obtaining that

\begin{align*} {} {}\frac{1}{2\pi i} &\int_{-\xi-iA}^{-\xi+iA} (s+\xi)^k e^{us} \hat{\rho}(s){\textrm{d}}s \\[5pt] {} {}&= i^{k} \frac{e^{\gamma-u\xi+I(\xi)}}{2\pi}\int_{-A}^{A} t^k \exp\!\left( -\frac{t^2}{2} I''(\xi) +i\frac{t^3}{6} I^{(3)}(\xi)+\frac{t^4}{24}I^{(4)}(\xi)+O_k\left(u|t|^5\right) \right){\textrm{d}}t\\[5pt] {} {}&= i^{k}\frac{e^{\gamma-u\xi+I(\xi)}}{2\pi} \int_{-A}^{A} t^k \exp\big(-\frac{t^2}{2} I''(\xi)\big) \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)\\[5pt] {} {}&\qquad \qquad \times \left(1+O_k\left( u|t|^5 + u^3 |t|^9\right)\right) {\textrm{d}}t. {}\end{align*}

Substituting $t^2 I''(\xi)=v^2$ , recalling $I''(\xi(u))=1/\xi'(u)$ and using (2·4), the last expression can be written as

\begin{multline*}= \rho(u)(1+O_k(u^{-1})) i^k \xi'^{k/2} \frac{1}{\sqrt{2\pi}}\int_{-A/\sqrt{\xi'}}^{A/\sqrt{\xi'}} v^k \exp(\!-v^2/2)\\[5pt] \times \bigg(1+i \frac{v^3 \xi'^{3/2}}{6} I^{(3)}(\xi) + \frac{v^4 \xi'^2 }{24}I^{(4)}(\xi) - \frac{v^6 \xi'^3}{72}I^{(3)}(\xi)^2 \bigg) \bigg( 1+ O_k\bigg( \frac{|v|^5 +|v|^9}{u^{3/2}} \bigg)\bigg) {\textrm{d}}v.\end{multline*}

To conclude we apply estimates of gaussian integrals: $\int_{-R}^{R} v^{2k+1}\exp(\!-v^2/2){\textrm{d}}v$ is 0, $\int_{\mathbb{R}}|v|^k \exp(\!-v^2/2){\textrm{d}}v \ll_k 1$ and $\int_{-R}^{R}v^{2k}\exp(\!-v^2/2){\textrm{d}}v =\sqrt{2\pi}\mu_{2k} + O_k(\exp(\!-R^2/4))$ .

3·3. Proof of the second part of Proposition 3·1

Here we prove (3·2) using the material in Section 3·2. If $1+u\xi \gt m \pi$ the result is already included in the first part of Proposition 3·1, so we assume from now on that $1+u\xi \le m \pi$ . From Lemma 3·3 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)}{\textrm{d}}s.\]

We have $\exp(H_m-\gamma)/m =1+1/(2m)+O(m^{-2})$ by (2·10), 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 (2·6). 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)}{\textrm{d}}s.\]

We separate the integral into 3 parts, $S_1+S_2+S_3$ , where

\begin{align*} {}S_1 &= \frac{1}{2\pi i} \int_{-\xi-im\pi}^{-\xi+im\pi} e^{us} \hat{\rho}(s) {\textrm{d}}s,\\[5pt] {}S_2 &= \frac{1}{2\pi i} \int_{-\xi-i(1+u\xi)}^{-\xi+i(1+u\xi)} \left(e^{T(-s)-T(\xi)}-1\right)e^{us} \hat{\rho}(s) {\textrm{d}}s,\\[5pt] {}S_3 &= \frac{1}{2\pi i} \left(\int_{-\xi-im\pi}^{-\xi-i(1+u\xi)}+\int_{-\xi+i(1+u\xi)}^{-\xi+im\pi}\right) \left(e^{T(-s)-T(\xi)} - 1 \right)e^{us} \hat{\rho}(s) {\textrm{d}}s.\end{align*}

The integral $S_1$ was estimated in Lemma 3·4 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·5 and it contributes $\ll e^{-u\xi}\log(u+1)/m$ . We now study $S_2$ . We use Lemma 2·9 to Taylor-expand $e^{T(-s)-T(\xi)}-1=e^{T(\xi-it)-T(\xi)}-1$ at 0:

(3·9) \begin{multline}e^{T(-s)-T(\xi)}-1 = -T'(\xi)(s+\xi) + \frac{(s+\xi)^2}{2}\left( T''(\xi)+T'(\xi)^2\right)\\[5pt] -(T^{(3)}(\xi)+3T'(\xi)T''(\xi)+(T'(\xi))^3) \frac{(s+\xi)^3}{6}+O\left( \frac{u\log(u+1)}{m} |s+\xi|^4\right)\end{multline}

for $|\Im s| \le 1+u\xi$ . Applying Lemma 3·6 with $k=4$ , $B=0$ and Lemma 3·7 with $k=1,2,3$ and collecting the terms gives

(3·10) \begin{multline} {}S_2 = \rho(u)\bigg(\frac{T'(\xi)(1+O(\log (u+1)^{-1}))-T''(\xi)(1+O(\log(u+1)^{-1}))}{2u} \\[5pt] + O\big( \frac{\log (u+1)}{n}+\frac{u\log^2(u+1)}{m^2}\big)\bigg). \end{multline}

All in all, since $T'(\xi)$ and $T''(\xi)$ are both $({u\log(u+1)}/{2m}) (1+o_{u\to\infty}(1))$ in our range by Lemma 2·9,

\[ p_{n,m} =\exp\big(\frac{u\xi}{2m}\big) \rho(u)\bigg( 1-\frac{\log(u+1)}{2m}(1+o_{u\to\infty}(1)) + O\bigg(\frac{u\log^2 (u+1)}{m^2}\bigg)\bigg). \]

We are done, as we established, in stronger form, the second part of Proposition 3·1.

3·4. Proof of Lemma 3·2

We first show (3·3). Let $r(t)=-\rho'(t)/\rho(t)\ge 0$ . We have

\[ {}\rho(u)= \rho\bigg( u-\frac{u}{2m}\bigg) \exp\bigg( -\int_{u-\frac{u}{2m}}^{u} r(t){\textrm{d}}t\bigg).\]

If u is bounded then the bound $r(t)\ll 1$ for $t \ll 1$ finishes the proof. If $u \ge C$ we may differentiate r (it is differentiable for $t \ge 2$ ) and obtain

\[ \rho(u) = \rho\bigg( u-\frac{u}{2m}\bigg) \exp\bigg( -\frac{ur(u)}{2m} + \int_{u-\frac{u}{2m}}^{u} \bigg(u-\frac{u}{2m}-t\bigg)r'(t) {\textrm{d}}t\bigg)\]

by integration by parts. To conclude, we use (3·8) to find

\[ {}-\frac{ur(u)}{2m} + \int_{u-\frac{u}{2m}}^{u} \bigg(u-\frac{u}{2m}-t\bigg)r'(t) {\textrm{d}}t = -\frac{u\xi(u)}{2m} + O\bigg( \frac{u}{m^2} + \frac{1}{m}\bigg).\]

It remains to show (3·4). Set $t_1 = n/(m+1/2)$ and $t_2=u-u/(2m)$ . It suffices to bound $\log (\rho(t_2)/\rho(t_1))$ . Observe $t_1\ge t_2$ . We have

\[ \log \rho(t_2)-\log \rho(t_1) = \int_{t_2}^{t_1} r(t)\textrm{d}t \le (t_1-t_2) \max_{t\in [t_2,t_1]} r(t) \ll \frac{n}{m^3} \log(u+1) = \frac{u\log(u+1)}{m^2} \]

since $r(t)\ll \log(t+1)$ by (3·8) and Lemma 2·2. This completes the proof.

4. Proof of Theorem 1·2 and Corollary 1·3

Let

\[ 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 \le i \le m-1).\]

Lemma 4·1. The estimate

\[ {}p_{n,m} = \frac{\exp\big( - u \log n + u + \sum_{i=1}^{m} d_{m,i} n^{1-\frac{i}{m}} + E\big)}{\sqrt{2\pi n m}} \bigg(1+O\bigg(\frac{1}{\max\{\log u, n^{1/m}\}}\bigg)\bigg)\]

holds uniformly for $n \gt m \ge 1$ , where E is a quantity satisfying

\[ 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}}}.\]

Lemma 4·1 is a minor improvement on [ Reference Manstavičius and Petuchovas13 , theorem 1], which treats $m\le \log n$ .

Proof. Recall the definitions of x and $\lambda$ given in (1·11) and (2·2). Following the proof of [ Reference Manstavičius and Petuchovas13 , theorem 1]Footnote 1 we have, borrowing the notation of [ Reference Manstavičius and Petuchovas13 , section 5],

\[ p_{n,m} = \frac{1}{\sqrt{2\pi \lambda}}\exp\!\big(\!-u\log n + u +\sum_{i=1}^{m} d_{m,i} n^{1-\frac{i}{m}} +E\big)\big( 1+ O\big(u^{-1}\big)\big)\]

for $E= R\big(n^{-\frac{1}{m}}\big)$ 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 [ Reference Manstavičius and Petuchovas13 , lemma 13] and estimated in [ Reference Manstavičius and Petuchovas13 , lemma 15]. In particular,

\[ h_i = \frac{i+m}{i}b_{i+m}\]

for $i \ge 1$ and

\[ b_i \ll \frac{m^{\frac{i}{m}}}{i}\]

for $i \ge 1$ . In the first displayed equation of [ Reference Manstavičius and Petuchovas13 , lemma 15] it is shown that $b_i \ll i^{\frac{i}{m}-1}/m$ for $m+1 \le i \le 2m-1$ . It implies

\[ {}b_i \ll \frac{i-m}{m} \]

in the same range. Hence

\begin{align*} R(z)&\ll \sum_{i=1}^{m-1} \frac{i+m}{m}|z|^i + \sum_{i=m}^{\infty} \frac{m}{i}( m^{\frac{1}{m}}|z|)^i + n\bigg(\sum_{i=m+1}^{2m-1} \frac{i-m}{m}|z|^i + \sum_{i=2m}^{\infty}\frac{1}{i}(m^{\frac{1}{m}}|z|)^i\bigg)\\[5pt] &\ll \sum_{i=1}^{m-1} |z|^{i} + \sum_{i=m}^{2m-1} \bigg( \frac{n(i-m)}{m} + m^{\frac{i}{m}}\bigg) |z|^i + \sum_{i=2m}^{\infty} \frac{n}{i} (m^{\frac{1}{m}}|z|)^i.\end{align*}

It follows that

\[ R(n^{-\frac{1}{m}}) \ll \frac{n^{-\frac{1}{m}}}{1-n^{-\frac{1}{m}}} + \frac{n^{-\frac{1}{m}}}{m(1-n^{-\frac{1}{m}})^2}+ \frac{\frac{m}{n}}{1-(\frac{m}{n})^{\frac{1}{m}}}\ll \frac{n^{-\frac{1}{m}}}{1-n^{-\frac{1}{m}}} + \frac{\frac{m}{n}}{1-(\frac{m}{n})^{\frac{1}{m}}}.\]

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

4·1. Proof of Theorem 1·2

Let

\[ S\;:\!=\;\sum_{i=1}^{m-1} d_{m,i} n^{1-\frac{i}{m}}.\]

In view of Lemma 4·1 we have

(4·1) \begin{equation} {}p_{n,m} = \left(\frac{e}{n}\right)^u \exp\!\left( S + O(\log n)\right),\end{equation}

when $m=O(\log n)$ , and it remains to estimate S. We have

\[\frac{1}{m-i} = \frac{1}{m} \left(1+O\left( \frac{i}{m-i}\right)\right), \qquad \frac{1}{\Gamma\left(1+\frac{i}{m}\right)} = 1+O\left( \frac{i}{m}\right)\]

uniformly for $1 \le i \le m-1$ . The estimate $\Gamma(x+y)/\Gamma(x) \in [x(x+y)^{y-1},x^y]$ for $y \in (0,1)$ [ Reference Wendel14 , equation (7)] implies

\[\frac{\Gamma\left(i+\frac{i}{m}\right)}{i!} =\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).\]

Hence,

\[d_{m,i}=\frac{i^{\frac{i}{m}}}{mi}\left(1+O\left( \frac{i}{m-i}\right)\right).\]

Since $i^{i/m}=1+O({i\log i}/{m})$ if $i \lt m/\log (m+1)$ , we may write S as $S= u(S_1+O(S_2+S_3))$ , where

\[S_1 =\sum_{i=1}^{m-1} \frac{n^{-\frac{i}{m}}}{i},\,\quad S_2=\sum_{1 \le i \lt \frac{m}{\log (m+1)}} \frac{n^{-\frac{i}{m}}}{i} \frac{i\log(i+1)}{m},\, \quad S_3=\sum_{\frac{m}{\log(m+1)} \le i \le m-1} (i/n)^{\frac{i}{m}}\frac{m}{i}.\]

We have

\[ S_1 = -\log(1-n^{-\frac{1}{m}}) + O\left( \frac{1}{nm}\frac{1}{1-n^{-\frac{1}{m}}}\right)\]

by bounding the tail of the Taylor series of $-\log(1-n^{-1/m})$ by a geometric series with ratio $n^{-1/m}$ . Similarly,

\[ S_2 \ll \frac{1}{m} \frac{1}{n^{\frac{1}{m}}-1}\ll \frac{n^{-\frac{1}{m}}}{m}\]

because the contribution of $i \in [2^k,2^{k+1})$ to $S_2$ is $\ll (k+1)n^{-2^k/m}/(m(1-n^{-1/m}))$ and $\sum_{k \ge 0}(k+1)n^{-2^k/m}\ll n^{-1/m}$ when $m\ll \log n$ . As for $S_3$ ,

\[S_3\ll m \sum_{\frac{m}{\log(m+1)}\le i \le m-1}\frac{1}{i} \max_{\frac{m}{\log(m+1)}\le i \le m-1} (i/n)^{i/m} \ll m\log \log (m+2) n^{-\frac{1}{\log(m+1)}} \]

since $i\mapsto (i/n)^{i/m}$ decreases for $i \le n/e$ . Both $S_3$ and the error term in $S_1$ are dominated by our bound for $S_2$ . It follows that

\[ S = u \big( -\log\big(1-n^{-\frac{1}{m}}\big) + O\big( \frac{n^{-\frac{1}{m}}}{m}\big)\big).\]

The error $O(\log n)$ in (4·1) is absorbed in the error term in S when $m \gt 1$ , and we are done.

4·2. Proof of Corollary 1·3

We first consider $n \ge m \gt n/2$ . For $m=n$ , $p_{n,n}=\rho(1)=1$ , so we may assume $m\le n-1$ . We have exact formulas: $p_{n,m}=1-\sum_{i=m+1}^{n}1/i$ and $\rho(u)=1-\log u$ . Hence

\[p_{n,m}-\rho(u)= \sum_{i=m+1}^{n}( \log i - \log(i-1) - \frac{1}{i}) \asymp \sum_{i=m+1}^{n} \frac{1}{i^2} \asymp \int_{m}^{n} \frac{{\textrm{d}}t}{t^2}.\]

We are done since, in our range,

\[\int_{m}^{n} \frac{{\textrm{d}}t}{t^2} =\frac{1}{m}-\frac{1}{n}\asymp\frac{n-m}{m^2} =\frac{u-1}{m}\asymp \frac{\log u}{m}.\]

We now suppose $n/2 \ge m \ge C \log n$ . We shall need the lower bound [ Reference Gorodetsky8 , theorem A·1]

(4·2) \begin{equation}p_{n,m} \ge \rho(u)\bigg(1+\frac{cu\log u}{m}\bigg)\end{equation}

which holds uniformly for $n/2 \ge m \ge 1$ . We may assume $n\ge C$ , since for bounded n we just want to show $B_2\rho(u) \ge p_{n,m}\ge B_1\rho(u)$ for constants $B_2\ge B_1 \gt 1$ which follows from (4·2) and (1·4). If u is sufficiently large then it follows from Proposition 3·1 that, using the same definition for A as in the statement of the corollary,

\[ {}A \asymp \frac{u\xi(u)}{m}\asymp \frac{u\log u}{m} \asymp u \log \left( 1+ \frac{\log u}{m}\right) \]

as needed. If $u=O(1)$ then the same argument establishes $A \le Cu\log ( 1+ (\log u)/m)$ and a matching lower bound in this range follows from (4·2).

Finally we suppose $m=O(\log n)$ . From (1·1) we have

(4·3) \begin{equation} {}\left(\frac{e}{n}\right)^u \frac{1}{\rho(u)} = \exp\!\left( u \left( \log\left( \frac{\log u}{m}\right) + O\left( \frac{\log \log u}{\log u}\right) \right)\right). {}\end{equation}

From Theorem 1·2 and (4·3),

\[ u^{-1}A = \log\left( \frac{\log n}{m}\right) - \log\left(1-n^{-\frac{1}{m}}\right) +O\left(\frac{\log \log n}{\log n}\right).\]

If n is sufficiently large and $1\le m\le C\log n$ ,

\[\log\bigg( \frac{\log n}{m}\bigg) - \log(1-n^{-\frac{1}{m}}) = \log \bigg( \frac{(\log n)/m}{1-e^{-(\log n)/m}}\bigg) \asymp \log\bigg(1+\frac{\log n}{m}\bigg)\]

since $t/(1-e^{-t}) \ge 1+c$ when $t=(\log n)/m\ge 1/C$ . This finishes the proof.

Remark 3. When $m=O(\log n)$ the proof above shows more: setting $t\;:\!=\;(\log n)/m$ ,

\[ A= u \left( \log \frac{t}{1-e^{-t}} +O\left ( \frac{\log\log (n+2)}{\log (n+2)}\right)\right)\]

holds, where A is as in the statement of Corollary 1·3.

5. Proofs of results in the polynomial setting

We recall we can write $G_q$ as

(5·1) \begin{equation} {}G_q(z) =\exp\!\left(\sum_{i=m+1}^{\infty} \frac{a_iz^i}{i}\right),\end{equation}

where $a_{i}$ are nonnegative numbers, depending on q, that are described in [ Reference Gorodetsky8 , lemma 2·1] and satisfy

(5·2) \begin{equation}a_i \ll \min\{q^{-\lceil i/2\rceil}, q^{m-i}\}.\end{equation}

5·1. Proof of Theorem 1.5

We suppose that $n \ge m \ge \sqrt{10n\log n}$ . This guarantees $2^{m/3} \gt 1+ m(\log 2)/3 \ge 1 + 2u\log u \ge 1+u\xi = e^{\xi}$ , where we used Lemma 2·3 in the last inequality. Hence

(5·3) \begin{equation}e^{\xi/m} \lt \sqrt[3]{2}.\end{equation}

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

(5·4) \begin{equation}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)}{\textrm{d}}s,\end{equation}

see [ Reference Manstavičius and Petuchovas13 , section 4]. In the same way,

(5·5) \begin{equation}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}) {\textrm{d}}s,\end{equation}

see e.g. [ Reference Gorodetsky8 , section 4]. Since $G_q$ has radius of convergence equal to q, we must ensure that $e^{\xi/m} \lt q$ in order for the last integral to be valid, and this holds by (5·3). By taking a linear combination of (5·4) and (5·5), and using (2·10) we have

\[ p_{n,m,q}-G_q(e^{\xi/m})p_{n,m} = G_q(e^{\xi/m}) \frac{1+O(m^{-1})}{2\pi i}X \]

for

\[ X\;:\!=\; \int_{-\xi-im\pi}^{-\xi+im\pi} \hat{\rho}(s)e^{us} e^{T(-s)} \bigg(\frac{G_q(e^{-s/m})}{G_q(e^{\xi/m})}-1\bigg) {\textrm{d}}s.\]

Since $p_{n,m} \gg \rho(u)$ for $m \ge \sqrt{10n\log n}$ by (1·4), it follows that

\[ \frac{p_{n,m,q}}{p_{n,m}}=G_q(e^{\xi/m})\bigg(1+O\bigg(\frac{|X|}{\rho(u)}\bigg)\bigg).\]

We must show $X \ll \rho(u) \log(u+1)/(mq^{\lceil(m+1)/2\rceil})$ . To bound X, we consider separately the contribution of $|\Re s| \le 1+u\xi$ and $m\pi \ge |\Re s| \ge 1+u\xi$ . We start with $|\Re s | \le 1+u\xi$ . Let

\[ H(s)\;:\!=\; \frac{G_q(e^{-s/m})}{G_q(e^{\xi/m})}-1, \qquad H_T(s)\;:\!=\; H(s) e^{T(-s)}\]

so that the integrand in X is $\hat{\rho}(s) e^{us} H_T(s)$ . We Taylor-expand $H_T(s)$ at $s=-\xi$ , where it attains 0: $H_T(s) = (s+\xi)b_1 + O(|s+\xi|^2 b_2)$ for

\[b_1= H_T'(-\xi) \qquad \text{and} \qquad b_2=\max_{|t| \le 1+u\xi} |H_T''(-\xi+it)|.\]

Applying Lemma 3·6 with $k=2$ , $B=0$ and Lemma 3·7 with $k=1$ , it follows that

\[ \int_{-\xi-i(1+u\xi)}^{-\xi+i(1+u\xi)} \hat{\rho}(s)e^{us} H_T(s) {\textrm{d}}s \ll \left(|b_1|+b_2\right)\frac{\rho(u)}{u}.\]

We now consider the contribution of $\pi m \ge |\Re s| \ge 1+u\xi$ . We focus on $m\pi \ge \Re s \ge 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·7. The contribution of $O(u\log (u+1)/|s|^2)$ is

\[ \ll \int_{-\xi+i(1+u\xi)}^{-\xi+i\pi m}|e^{us} \frac{u\log(u+1)}{s^2} H_T(s)| |{\textrm{d}}s|\ll b_3e^{-u\xi}, \]

where

\[ b_3 = \max_{|t| \le \pi m} |H_T(-\xi+it)|.\]

We study the last piece of the integral,

\[ \int_{-\xi+i(1+u\xi)}^{-\xi+i\pi m} \frac{e^{us}}{s} e^{T(-s)} H(s) {\textrm{d}}s .\]

We write $e^{T(-s)}$ as $1+(e^{T(-s)}-1)$ . When $s=-\xi+it$ for $1+u\xi \le t \le \pi m$ we have $e^{T(-s)}-1=O(|s|/m + |s|^2/m^2)$ by Corollary 2·8. Applying the triangle inequality we get

\[ \int_{-\xi+i(1+u\xi)}^{-\xi+i\pi m} \frac{e^{us}}{s} (e^{T(-s)}-1) H(s){\textrm{d}}s\ll b_4 \int_{-\xi+i(1+u\xi)}^{-\xi+i\pi m}\ \bigg| \frac{e^{us}}{s}\bigg| \bigg(\frac{|s|}{m}+\frac{|s|^2}{m^2}\bigg) |{\textrm{d}}s| \ll b_4 e^{-u\xi}, \]

where

\[ b_4 = \max_{|t| \le \pi m} |H(-\xi+it)|.\]

We estimate

(5·6) \begin{equation} \int_{-\xi+i(1+u\xi)}^{-\xi+i\pi m} \frac{e^{us}}{s} H(s) {\textrm{d}}s .\end{equation}

Using the notation in (5·1) and the bound in (5·2), it follows that

(5·7) \begin{equation} {}\begin{split}H(s) &= \log G_q(e^{-s/m}) - \log G_q(e^{\xi/m}) +O\left( \frac{u^2 \log^2(u+1)}{m^2 q^{2\lceil \frac{m+1}{2}\rceil}}\right)\\[5pt] &=\sum_{j=m+1}^{2m} \frac{a_j}{j}(e^{-js/m}-e^{j\xi/m}) + O\left(\frac{u^2\log^2(u+1)}{mq^{m+1}}\right).\end{split}\end{equation}

Hence the integral in (5·6) equals

\[ =\sum_{j=m+1}^{2m} \frac{a_j}{j} \int_{-\xi+i(1+u\xi)}^{-\xi+i\pi m} \frac{e^{us}}{s} (e^{-js/m}-e^{j\xi/m}) {\textrm{d}}s+O\left( \frac{u^2 \log^2(u+1) e^{-u\xi}\log(m+1)}{mq^{m+1}} \right).\]

If $u \lt 3$ then $G_q(e^{\xi/m})-1\ll 1/(mq^{\lceil (m+1)/2\rceil})$ , implying Theorem 1·5 is already in (1·6). From now on we assume $u \ge 3$ . We have the estimate

\[ \int_{-\xi+i(1+u\xi)}^{-\xi+i\pi m} \frac{e^{(u-j/m)s}}{s}{\textrm{d}}s \ll \frac{e^{-(u-j/m)\xi}}{(1+u\xi)|u-j/m|},\]

which is valid for all $2m\ge j \ge 0$ and $u \ge 3$ , and is established by integration by parts. It follows that the integral (5·6) contributes

\[\ll \frac{u^2 \log^2(u+1) e^{-u\xi}\log (m+1)}{mq^{m+1}} + \sum_{j=m+1}^{2m} \frac{a_j}{j} \frac{e^{-u\xi}}{1+u\xi} \frac{e^{j\xi/m}}{|u-j/m|} \ll \frac{e^{-u\xi}}{n q^{\lceil \frac{m+1}{2}\rceil}}.\]

Collecting the estimates,

(5·8) \begin{equation}X \ll \frac{\rho(u)}{u}(|b_1|+b_2)+(b_3+b_4) e^{-u\xi}+ \frac{e^{-u\xi}}{n q^{\lceil \frac{m+1}{2}\rceil}}.\end{equation}

Recall we want to show $X \ll \rho(u) \log(u+1)/(mq^{\lceil(m+1)/2\rceil})$ . We have $e^{-u\xi}\ll_k \rho(u) u^{-k}$ for any k by (2·4), showing that the last term in (5·8) is acceptable and that it suffices to show $b_i \ll u\log(u+1)/(mq^{\lceil(m+1)/2\rceil})$ for $i=1,2,3,4$ .

Since $T(-\xi+it)$ is bounded when $|t|\le \pi m$ by Corollary 2·8, it follows that $b_3 \ll b_4$ . By (5·7) and the triangle inequality, $b_4 \ll u\log(u+1)/(mq^{\lceil(m+1)/2\rceil})$ . To bound $b_1$ and $b_2$ we use the fact that T and its derivatives are bounded by Lemma 2·9 in order to reduce the problem to showing

\[ H^{(i)}(\!-\xi+it) \ll u \log(u+1)/(mq^{\lceil(m+1)/2\rceil})\]

holds for $i=0,1,2$ . For $i=0$ this is in (5·7), for $i=1$ we have

\[ H'(s) = -\frac{e^{-s/m}}{m} \frac{G_q'(e^{-s/m})}{G_q(e^{\xi/m})} \ll \frac{|G_q'(e^{-s/m})|}{m} \ll \frac{\sum_{i=m+1}^{\infty} a_i e^{(i-1)\xi/m}}{m} \ll \frac{u\log(u+1)}{mq^{\lceil(m+1)/2\rceil}}\]

and a similar computation holds for $i=2$ . This completes the proof of Theorem 1·5.

5·2. Proof of Corollary 1·6

Fix $\varepsilon \gt 0$ . We assume $n \ge m \ge (2+\varepsilon)\log_q n$ and we want to establish (1·10) in this range. We already know (1·10) holds in $n/(\log n \log^3\log(n+1)) \ge m \ge (2+\varepsilon)\log_q n$ , so we may suppose $n \ge m \gt n/(\log n \log^3\log(n+1))$ .

If $n=O(1)$ then (1·10) becomes $p_{n,m,q}=p_{n,m}G_q(x) + O_{n,\varepsilon}(G_q(x)/q^{\lceil (m+1)/2\rceil})$ . To establish this, recall $p_{n,m,q}=p_{n,m} + O(1/q^{\lceil (m+1)/2\rceil})$ by [ Reference Gorodetsky8 , proposition 1·5] and observe that $G_q(x) = 1+O_{n,\varepsilon}(1/q^{\lceil (m+1)/2\rceil})$ by (5·1) and (5·2).

From now on we may suppose n is sufficiently large. In particular, $n \gt \sqrt{10 n \log n}$ holds, and $n \ge m \gt n/(\log n \log^3\log(n+1))$ implies $n \ge m \ge \sqrt{10 n \log n}$ . We apply Theorem 1·5, and see that it suffices to show that

(5·9) \begin{equation} {}\frac{G_q(x)}{G_q(e^{\xi(u)/m})} = 1 +O\left( \frac{u\log^2 (u+1)}{m^2 q^{\lceil \frac{m+1}{2}\rceil}}\right)\end{equation}

holds for $n\ge m \ge \sqrt{10 n \log n}$ . First we verify that $x \lt \sqrt[3]{2}$ . Since $x \le n^{1/m}$ , it suffices to show that $2^m \gt n^3$ , which follows from $n \ge m \ge \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·6) 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}}\]

using (5·2), and (5·9) follows by exponentiating.

5·3. Auxiliary computation

Recall $F_q$ defined in (1·7). We define $x_q\;:\!=\;x_{n,m,q} \lt q$ as the unique positive solution to $z F_q'(z)/F_q(z) = n$ . The next lemma gives precise results on $x-x_q$ in certain ranges.

Lemma 5·1. If $n \ge m \ge 1$ then $x_q \le x$ . Fix q and $\varepsilon \gt 0$ . For $n \ge C_{q,\varepsilon}$ and $m \in [(3/4)\log_q n, (2-\varepsilon)\log_q n]$ ,

\[ C_{q,\varepsilon}\frac{\min\{n,q^m\}}{q^m m} \big(1-\frac{x_q}{q}\big)^{-1} \ge x-x_q \ge c_q \frac{\min\{n,q^m\}^{2}}{q^m nm}.\]

Proof. We shall use the form of $G_q$ given in (5·1). Let $f(z)\;:\!=\;z(\log F(z))' = \sum_{i=1}^{m} z^i$ and $g_q(z) \;:\!=\; z(\log G_q(z))'= \sum_{i=m+1}^{\infty}a_i z^i$ . By definition,

(5·10) \begin{equation} {}n = f(x)= f(x_q)+g_q(x_q).\end{equation}

Since f and $g_q$ have nonnegative coefficients, the first part of the lemma follows at once. We now assume $(2-\varepsilon)\log_q n \ge m \ge (3/4)\log_q n $ . We use (5·10) to determine the size of $x-x_q$ . By the mean value theorem,

\[ 0 \le x-x_q = f^{-1}(n) - f^{-1}(n-g_q(x_q)) = \frac{g_q(x_q)}{f'(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’ are monotone increasing we have $f'(f^{-1}(n-t)) \in [f'(x_q), f'(x)]$ and so

\[ {}x-x_q \in \left[ \frac{g_q(x_q)}{f'(x)}, \frac{g_q(x_q)}{f'(x_q)} \right]. \]

We have the trivial bounds $1 \le x\le n^{1/m} \ll_q 1$ and so $f'(x) = \lambda/x \asymp_q nm$ by Lemma 2·1. We also have

\[ g_q(x_q) \ge a_{2m}x_q^{2m} \gg q^{-m} x_q^{2m}\]

since $a_i \ge 0$ and $a_{2m} \gg q^{-m}$ by [ Reference Gorodetsky8 , lemma 2·1]. It follows that

\[ x-x_q \gg_q \frac{x_q^{2m}}{q^m nm}.\]

[ Reference Manstavičius12 , lemma 2 and theorem 2] estimate $x_q$ and yield that, when $2\log_q n \ge m \ge (3/4)\log_q n$ ,

(5·11) \begin{equation} {}x_q^m \asymp_q \min\{n,q^m\},\end{equation}

implying the desired lower bound on $x-x_q$ . To prove the upper bound, first observe that $m \le (2-\varepsilon)\log_q n$ implies, via (5·11), that $x_q \ge q^{1/2}(1+c_{q,\varepsilon})$ if n is sufficiently large, and so

\[ g_q(x_q) \ll \sum_{i=m+1}^{2m} \frac{x_q^i}{q^{i/2}}+q^m \sum_{i \ge 2m}\frac{x_q^i}{q^i} \ll_{q,\varepsilon} \frac{ x_q^{2m}}{q^m}\big(1-\frac{x_q}{q}\big)^{-1}\]

using the bounds in (5·2). To conclude we need to lower bound $f'(x_q)$ . We have $f'(x_q) = x_q^{-1} \sum_{i=1}^{m} i x_q^i \gg_{q} m x_q^m$ .

5·4. Proof of Theorem 1·7

Recall the functions F, $F_q$ and $G_q$ are defined in (1·8), (1·7) and (1·9). If $m \to \infty$ and $u\ge (\log \log m)^3 \log m$ , Manstavičius proved in [ Reference Manstavichyus11,Reference Manstavičius12 ] that

(5·12) \begin{equation} {}p_{n,m,q} = \frac{F_q(x_{q})}{x_q^n\sqrt{2\pi \lambda_q}}\left( 1+O_q\left( \frac{m}{n}+\frac{m}{q^m}\right)\right),\end{equation}

where

\[ \lambda_q\;:\!=\;\lambda_{n,m,q}= z \left(\frac{zF'_q(z)}{F_q(z)}\right)'|_{z=x_q}.\]

We divide (5·12) by (2·1), and use the fact that $\lambda$ is asymptotic to nm by Lemma 2·1 as long as $u \to \infty$ , and

(5·13) \begin{equation}\lambda_q \sim nm \left(1+ \frac{n}{q^m}\left(1-\frac{1}{q}\right)\right)\end{equation}

by [ Reference Manstavičius12 , theorem 2] as long as $u \to \infty$ and $m \to \infty$ , to obtain

(5·14) \begin{equation} \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^nF(x_{q})G_q(x_{q})}{x_q^nF(x)G_q(x)}\end{equation}

as $n \to \infty$ if $(2-\varepsilon)\log_q n \ge m \gt \log_q n$ . Letting

\[ H_q(z) \;:\!=\;\log F_q(z)-n\log z = \log F(z) + \log G_q(z)-n \log z,\]

we can write (5·14) as

(5·15) \begin{equation} \frac{p_{n,m,q}}{p_{n,m}G_q(x)} \sim \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}.\end{equation}

By definition, $H'_q(x_q)=0$ . By Taylor-expanding $H_q$ at $x_q$ ,

\[ H_q(x)-H_q(x_{q}) = \frac{H''_q(t)}{2}(x-x_q)^2 \]

for some $t \in [x_q,x]$ (recall $x_q \le x$ by Lemma 5·1). In the range $(2-\varepsilon)\log_q n \ge m \gt \log_q n$ we have $x\asymp_q x_q \asymp_q 1$ by Lemma 2·1 and (5·11). In the notation of (5·1),

\[ t^2 H_q''(t) = \sum_{i=2}^{m}(i-1)t^i + \sum_{i=m+1}^{\infty}(i-1)a_i t^i+ n \gt 0\]

is increasing for $t \gt 0$ since $a_i \ge 0$ . It follows that

\[ x_q^2 H_q''(x_q) \ll_q H_q''(t)\ll_q x^2 H_q''(x).\]

A short computation shows that $x_q^2 H_q''(x_q)=\lambda_q$ holds by the definition of $x_q$ and $\lambda_q$ . By (5·13) it then follows that $x_q^2 H_q''(x_q) \asymp_q nm$ when $(2-\varepsilon)\log_q n \ge m \gt \log_q n$ . In the same range we find that $x^2 H_q''(x) = \lambda +\sum_{i=m+1}^{\infty}(i-1)a_i x^i \ll_{q,\varepsilon} nm$ using Lemma 2·1 and the bounds in (5·2). Hence $H_q''(t) \asymp_{q,\varepsilon} nm$ and

\[ H_q(x)-H_q(x_q) \asymp_{q,\varepsilon} nm (x-x_q)^2 \asymp_{q,\varepsilon} \frac{n^3}{mq^{2m}},\]

where we used Lemma 5·1 in the second estimate. Plugging this estimate in (5·15), and observing that $(1+ ({n}/{q^m})(1-{1}/{q}))^{-1/2} \sim 1$ holds in the range $m\ge (1+\varepsilon)\log_q n$ considered in Theorem 1·7, concludes the proof.

5·5. A variant

We prove a variant of Theorem 1·7 with the main term $G_q(x)$ replaced by $G_q(x_q)$ .

Theorem 5·2. Fix q and $\varepsilon \gt 0$ . For $m \in [(3/4)\log_q n, (2-\varepsilon)\log_q n]$ we have

(5·16) \begin{equation} {} {}\begin{split} {} {} {}\frac{p_{n,m,q}}{p_{n,m}} &\le (1+o(1))G_q(x_q)\exp\!\left( \frac{C_{q,\varepsilon} \min\{n,q^m\}^2 n}{mq^{2m} } \left(1-\frac{x_q}{q}\right)^{-2}\right),\\[5pt] {} {} {}\frac{p_{n,m,q}}{p_{n,m}} &\ge (1+o(1)) G_q(x_q)\exp\!\left( \frac{c_{q,\varepsilon} \min\{n,q^m\}^5}{n^2 mq^{2m}}\right) {} {}\end{split} {}\end{equation}

as $n \to \infty$ . If furthermore $n \ge C_{q,\varepsilon}$ then

\[C_{q,\varepsilon}\frac{\min\{n,q^m\}^2}{mq^m}\big(1-\frac{x_q}{q}\big)^{-1} \ge \log G_q(x_q) \ge c_q \frac{\min\{n,q^m\}^2}{mq^m}.\]

Proof. In very much the same way (5·14) is proved, we also have

(5·17) \begin{equation} \frac{p_{n,m,q}}{p_{n,m}G_q(x_q)} \sim \frac{x^nF(x_{q})G_q(x_{q})}{x_q^nF(x)G_q(x_q)}\left(1+ \frac{n}{q^m}\left(1-\frac{1}{q}\right)\right)^{-1/2}\end{equation}

if $u \ge (\log \log m)^3 \log m$ and $m\to\infty$ . Letting

\[ H(z) \;:\!=\; \log F(z) -n \log z,\]

we can write (5·17) as

\[ \frac{p_{n,m,q}}{p_{n,m}G_q(x_q)} \sim \exp\!\left(H(x_q)-H(x)\right)\left(1+ \frac{n}{q^m}\left(1-\frac{1}{q}\right)\right)^{-1/2}.\]

By definition, $H'(x) = 0$ . By Taylor-expanding H at x,

\[ H(x_q)-H(x) = \frac{H''(t)}{2}(x-x_q)^2\]

for some $t \in [x_q,x]$ . Since $t^2 H''(t) = \sum_{i=2}^{m} (i-1)t^i +n$ is increasing in t, and $x \asymp_q x_q \asymp_q 1$ by Lemma 2·1 and (5·11), it follows that

\[ x_q^2 H''(x_q) \ll_q H''(t) \ll_q x^2 H''(x).\]

We have $x^2 H''(x)=\lambda \asymp nm$ by Lemma 2·1 when $(2-\varepsilon)\log_q n \ge m \ge (3/4)\log_q n$ . Lemma 5·1 bounds $x-x_q$ . This gives the first part of (5·16) (we bound the factor $(1+ ({n}/{q^m})(1-{1}/{q}))^{-1/2}$ by 1). We have $x_q^2 H''(x_q) \ge (m-1)x_q^m \gg_q m \min\{n,q^m\}$ by (5·11), which leads to the second part of (5·16) (we absorb $(1+ ({n}/{q^m})(1-{1}/{q}))^{-1/2}$ in the exponential factor in right-hand side of (5·16)).

It remains to estimate $G_q(x_q)$ . For a lower bound we use $\log G_q(x_q) \ge a_{2m} x_q^{2m}/(2m) \gg x_q^{2m}/(mq^m)$ . Here we used $a_i \ge 0$ and $a_{2m} \asymp q^{-m}$ [ Reference Gorodetsky8 , lemma 2·1]. This is simplified using (5·11). For the upper bound we use $a_{i} \ll \min\{q^{-\lceil i/2\rceil},q^{m-i}\}$ and $x_q \ge q^{1/2}(1+c_{q,\varepsilon})$ to obtain $\log G_q(x_q) \ll_{q,\varepsilon} x_q^{2m}/( mq^m(1-x_q/q))$ . We again simplify $x_q^m$ using (5·11).

Acknowledgements

We thank Andrew Granville for valuable comments on the presentation. We are grateful to the anonymous referees for helpful comments on exposition as well as a simplification of the proof of Lemma 2·1. 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).

Footnotes

1 We correct a few typos. The definition of D(x) in [ Reference Manstavičius and Petuchovas13 , p. 21] should be replaced by the one given in p. 4 of that paper. 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 on p. 23, the factor $n!$ that appears twice should be omitted.

References

Alladi, K.. The Turán-Kubilius inequality for integers without large prime factors. J. Reine Angew. Math. 335 (1982), 180196.Google Scholar
de Bruijn, N. G.. The asymptotic behaviour of a function occurring in the theory of primes. J. Indian Math. Soc. (N.S.) 15 (1951), 2532.Google Scholar
de Bruijn, N. G.. The asymptotic behaviour of a function occurring in the theory of primes. J. Indian Math. Soc. (N.S.) 15 (1951), 2532.Google Scholar
de Bruijn, N. G.. On the number of positive integers $\leq x$ and free of prime factors $ \gt y$ . Nederl. Acad. Wetensch. Proc. Ser. A. 54 (1951), 50–60.Google Scholar
de la Bretèche, R. and Tenenbaum, G.. Entiers friables: inégalité de Turán-Kubilius et applications. Invent. Math. 159(3) (2005), 531588.CrossRefGoogle Scholar
Ford, K.. Cycle type of random permutations: a toolkit. Discrete Anal. 9 (2022), 136.Google Scholar
Goncharov, V.. Über das Gebiet der kombinatorischen Analysis. Izv. Akad. Nauk SSSR, Ser. Mat. 8 (1944), 348.Google Scholar
Gorodetsky, O.. Uniform estimates for smooth polynomials over finite fields. Discrete Anal. 16 (2023), 131.Google Scholar
Hildebrand, A.. Integers free of large prime factors and the Riemann hypothesis. Mathematika 31(2) (1984), 258271.CrossRefGoogle Scholar
Hildebrand, A. and Tenenbaum, G.. Integers without large prime factors. J. Théor. Nombres Bordeaux 5(2) (1993), 411484.CrossRefGoogle Scholar
Manstavichyus, E.. Remarks on elements of semigroups that are free of large prime factors. Liet. Mat. Rink. 32(4) (1992), 512525.Google Scholar
Manstavičius, E.. Semigroup elements free of large prime factors. In New trends in probability and statistics, vol. 2 (Palanga, 1991) (VSP, Utrecht, 1992), pages 135–153.CrossRefGoogle Scholar
Manstavičius, E. and Petuchovas, R.. Local probabilities for random permutations without long cycles. Electron. J. Combin. 23(1), paper 1.58 (2016), 25.CrossRefGoogle Scholar
Wendel, J. G.. Note on the gamma function. Amer. Math. Monthly 55 (1948), 563564.CrossRefGoogle Scholar