---
abstract: |
    We establish new estimates for the number of $m$-friable polynomials of degree $n$ over a finite field ${\mathbb{F}}_q$, where the main term involves the number of $m$-friable permutations on $n$ elements. The range of $m$ in our results is $n \ge m \ge (1+\varepsilon)\log_q n$ and is optimal as these numbers are not comparable for smaller $m$. For $m \ge 4\log_q n$ the error term in our estimates decays faster than in all previous works.

    Our estimates imply that the probability that a random polynomial $f_n$ is $m$-friable is asymptotic to the probability that a random permutation $\pi_n$ is $m$-friable, uniformly for $m\ge (2+\varepsilon)\log_q n$ as $q^n \to \infty$. This should be viewed as an unconditional analogue of a result of Hildebrand (1984), saying that under the Riemann Hypothesis, the probability that a number $\le x$ is $y$-friable is of the order of magnitude of the Dickman $\rho$ function at $\log x/\log y$, uniformly for $\log y \ge (2+\varepsilon) \log\log x$. As opposed to Hildebrand's result, we actually obtain an asymptotic result.

    As an application of our estimates, we determine the rate of decay in the asymptotic formula for the expected degree of the largest prime factor of a random polynomial. This improves a previous estimate of Knopfmakher and Manstavičius (1997).
author:
- Ofir Gorodetsky
bibliography:
- 'references.bib'
title: Uniform estimates for friable polynomials over finite fields
---

Introduction
============

Given a positive integer $n$, we let $\pi_n$ be a permutation chosen uniformly at random from $S_n$. Given a prime power $q$, we let $f_n=f_{n,q} \in {\mathbb{F}}_q[T]$ be a polynomial chosen uniformly at random from ${\mathcal{M}_{n,q}}\subseteq {\mathbb{F}}_q[T]$, the set of monic polynomials of degree $n$ over the finite field ${\mathbb{F}}_q$.

We say that a permutation is $m$-friable (or -smooth) if all its cycles are of length at most $m$. Similarly, we say that a polynomial is $m$-friable if all its prime factors are of degree at most $m$. We define $$\psi_{\pi}(n,m) := \#\{ \pi \in S_n: \pi \text{ is }m\text{-friable}\}, \qquad \psi_q(n,m) := \#\{ f \in {\mathcal{M}_{n,q}}: f\text{ is }m\text{-friable}\},$$ so that ${\mathbb{P}}(\pi_n \text{ is }m\text{-friable})=\psi_{\pi}(n,m)/n!$ and ${\mathbb{P}}(f_n \text{ is }m\text{-friable}) = \psi_q(n,m)/q^n$.

Throughout the paper, $n \ge 2$, $1 \le m \le n$ and $$u := \frac{n}{m}.$$ Friability (or smoothness) probabilities in $S_n$ were studied extensively in the literature, dating back to Goncharov's 1944 work @goncharov1944, who studied ${\mathbb{P}}(\pi_n \text{ is }m\text{-friable})$ in the bounded $u$ regime; see @shepp1966 [@arratia2003] for generalizations. The bounded-$m$ regime received significant attention as well, see @chowla1951 [@moser1955; @wilf2006; @sachkov2007; @timashev2008; @amdeberhan2015]. Asymptotic results covering the entire range of $m$ were established by Manstavičius and Petuchovas @manstavicius2016.

Friability probabilities in ${\mathcal{M}_{n,q}}$ were studied extensively in the literature as well, starting with the work of Odlyzko @odlyzko1985, which was motivated by cryptography. Several cryptographic system are based on the difficulty of computing discrete logarithms in finite fields. Index-Calculus algorithms, invented in the late seventies, compute discrete algorithms in subexponential time. The complexity analysis of their running time, as well as the choice of parameters within the algorithm, are highly non-trivial. When the finite field is an extension of ${\mathbb{F}}_q$, the analysis requires the asymptotics of $\psi_q(n,m)$ in the range $n^{\varepsilon} \le m\le n^{1-\varepsilon}$. This is addressed, for $q=2$, in @odlyzko1985 [App. 1]. Subsequent works on $\psi_q$ include @warlimont1991 [@lovorn1992; @manstavicius1992; @manstavicius19922; @panario1998; @bender1998; @soundararajan; @arratia2003; @joux2006; @ha2014] and are expanded upon later.

Here we estimate friability probabilities in $\mathcal{M}_{n,q}$ by comparing it to the corresponding probabilities in $S_n$, uniformly in the parameters $n$ and $q$. Unless stated otherwise, constants, both implied and explicit, are absolute. For recent results where new function field estimates are obtained by comparing to a permutation quantity see @gorodetsky2017 [@elboim2020uniform].

\[thm:laplace\] If $m \ge 6\log n$, then $$\label{eq:main largen}
     \frac{{\mathbb{P}}(f_n \text{ is }m\text{-friable})}{{\mathbb{P}}(\pi_n \text{ is }m\text{-friable})} =1+ O\left(\frac{u \log (u+1)}{ mq^{\lceil \frac{m+1}{2}\rceil}}\right),  \qquad q^n \to \infty.$$

The previous asymptotic results for ${\mathbb{P}}(f_n \text{ is }m\text{-friable})$ in this range of $m$ achieved only the weaker error terms $u \log (u+1)/m$ (see and ) or $1/u$ (see §\[sec:saddle\]), but with perhaps simpler main terms. For smaller $m$, we prove

\[thm:saddle\] Fix $\varepsilon>0$. If $8\log n\ge m \ge (2+\varepsilon)\log_q n$, then $$\label{eq:main mediumn2}
    \frac{{\mathbb{P}}(f_n \text{ is }m\text{-friable})}{{\mathbb{P}}(\pi_n \text{ is }m\text{-friable})} = 1 + O_\varepsilon\left(  \frac{u n^{\frac{1+{a}}{m}}}{q^{\lceil \frac{m+1}{2} \rceil}}\right), \qquad q^n \to \infty,$$ where ${a}= \mathbf{1}_{2 \mid m}$

Once $m \ge 4\log_q n$, the error term in decays faster than $O(1/u)$, the existing error term in the asymptotic result for ${\mathbb{P}}(f_n \text{ is }m\text{-friable})$ in this range of $m$ (see §\[sec:saddle\]). In Theorem \[thm:saddle2\] below, the error term in both theorems is improved, at least if $m$ is not too close to $n$, by modifying the main term $1$.

Theorems \[thm:laplace\] and \[thm:saddle\] cover the entire range $n \ge m \ge  (2+\varepsilon)\log_q n$, and in particular show that $$\label{eq:akin}
    {\mathbb{P}}(f_n \text{ is }m\text{-friable}) \sim {\mathbb{P}}(\pi_n \text{ is }m\text{-friable})$$ holds as $q^n \to \infty$, uniformly in that range. When $n \to \infty$ and $m \le (1-\varepsilon)\log_q n$, the probabilities are no longer of the same order of magnitude. Concretely, for $n$ tending to $\infty$ and fixed $q$, we have $${\mathbb{P}}(f_n \text{ is }m\text{-friable}) = q^{-n+o_{q,\varepsilon}(n)}$$ for $m \sim (1-\varepsilon) \log_q n$ by @soundararajan [Thm. 1.4], while, in the same limit, $${\mathbb{P}}(\pi_n \text{ is }m\text{-friable}) = q^{-\frac{n}{1-\varepsilon} + o_{q,\varepsilon}(n)}$$ by Theorem \[thm:perm new\]. For $m=o(\log n)$ the situation is even worse: ${\mathbb{P}}(\pi_n \text{ is }m\text{-friable})$ decays superexponentially in $n$ by Theorem \[thm:perm new\], while ${\mathbb{P}}(f_n \text{ is }m\text{-friable}) \ge q^{-n}$ can never decay superexponentially.

We prove a comparative result where $m$ can be as small as $(1+\varepsilon) \log_q n$. It requires the introduction of some notation. Define $x=x_{n,m}>0$ by $$\label{eq:x def}
\sum_{j=1}^{m} x^j = n.$$ Observe that $1 \le x \le n^{1/m}$. In fact, from Lemma \[lem:lambda\] it follows that $x=\Theta(n^{1/m})$. Let $$G_q(z) := \prod_{\substack{P \in \mathcal{P} \\ \deg (P) \le m}}\left(1-\left(\frac{z}{q}\right)^{\deg (P)}\right)^{-1} \exp\left(-\sum_{i=1}^{m} \frac{z^i}{i}\right),$$ where $\mathcal{P}=\mathcal{P}_{q}$ is the set of monic irreducible polynomials over ${\mathbb{F}}_q$. By , $G_q(x) \ge 1$.

\[thm:saddle2\] Fix $\varepsilon>0$. If $(2-\varepsilon)\log_q n \ge m \ge (1+\varepsilon)\log_q n$ then $$\label{eq:main mediumn3}
    \frac{{\mathbb{P}}(f_n \text{ is }m\text{-friable})}{{\mathbb{P}}(\pi_n \text{ is }m\text{-friable})} =  G_q(x) \left( 1+ O_{\varepsilon}\left( n^{\max\{1-2\varepsilon,-\varepsilon\}}\right)\right)$$ as $n \to \infty$, where $x$ is defined in . If, instead, $n/(\log n \log^3 \log(n+1)) \ge m \ge (2+\varepsilon)\log_q n$, then $1\le G_q(x) \le C_{\varepsilon}$ and $$\label{eq:main mediumn32}
\frac{{\mathbb{P}}(f_n \text{ is }m\text{-friable})}{{\mathbb{P}}(\pi_n \text{ is }m\text{-friable})} =  G_q(x)  + O_{\varepsilon}\left(\frac{n^{\frac{1+{a}}{m}} \min\{m, \log u\}}{mq^{\lceil \frac{m+1}{2}\rceil}}  \right)$$ as $q^n \to \infty$, where ${a}= \mathbf{1}_{2 \mid m}$.

Estimate gives an asymptotic result as $n \to \infty$ whenever $m \ge (3/2+\varepsilon)\log_q n$, and otherwise gives a non-trivial upper bound for ${\mathbb{P}}(f_n \text{ is }m\text{-friable})$. Previous asymptotic results for the range of achieved only the weaker error terms $u \log (u+1)/m$ (see and ) or $1/u$ (see §\[sec:saddle\]).

Replacing the error term given in the right-hand side of , one can extend the validity of the estimate to include the transitational range $(2-\varepsilon)\log_q n \le m \le (2+\varepsilon)\log_q n$, see Theorem \[thm:saddle3\].

We conclude with the following uniform result, holding in the entire range, but most useful when $u$ is bounded.

\[prop:bndd unif\] For $n \ge m \ge 1$, $$0 \le {\mathbb{P}}(f_n \text{ is }m\text{-friable}) - {\mathbb{P}}(\pi_n \text{ is }m\text{-friable}) \le \frac{C}{m q^{\lceil \frac{m+1}{2} \rceil}}.$$

We stress that our proofs of all of our estimates are direct, in the sense that we do not make use of existing asymptotics of ${\mathbb{P}}(f_n \text{ is }m\text{-friable})$. Rather, we bound the differences $|{\mathbb{P}}(f_n \text{ is }m\text{-friable})-{\mathbb{P}}(\pi_n \text{ is }m\text{-friable})|$ and $|{\mathbb{P}}(f_n \text{ is }m\text{-friable})-G_q(x){\mathbb{P}}(\pi_n \text{ is }m\text{-friable})|$ themselves. In the very last step of each proof we plug existing lower bounds on ${\mathbb{P}}(\pi_n \text{ is }m\text{-friable})$ to convert our bounds to relative bounds.

Optimality
----------

Theorems \[thm:laplace\] and \[thm:saddle\] combined state $$\label{eq:combined}
\frac{{\mathbb{P}}(f_n \text{ is }m\text{-friable})}{{\mathbb{P}}(\pi_n \text{ is }m\text{-friable})} =1+ O_{\varepsilon}\left(\frac{u n^{\frac{1+{a}}{m}} \min\{ m ,\log(u+1)\}}{m q^{\lceil \frac{m+1}{2}\rceil}}\right), \qquad q^n \to \infty,$$ for $m \ge (2+\varepsilon)\log_q n$. This is essentially optimal in both the error term and the range. Indeed, from and the lower bound for $G_q(x)$ given in , we have a matching lower bound as long as $(2+\varepsilon)\log_q n \le m \le n/(\log n\log^3 \log(n+1))$ and $n \gg 1$.

We observe that for $m=n-1$, recovers the Prime Polynomial Theorem (PPT) with squareroot error term. Indeed, $$\begin{split}
        {\mathbb{P}}(f_n \text{ is }(n-1)\text{-friable}) &= 1-  {\mathbb{P}}(f_n \text{ is irreducible}), \\{\mathbb{P}}(\pi_n \text{ is }(n-1)\text{-friable}) &= 1-{\mathbb{P}}(\pi_n \text{ is an }n\text{-cycle}) = 1-\frac{1}{n},
    \end{split}$$ and so from $$\label{eq:ppt}
    \#\{ f \in \mathcal{M}_{n,q} : f \text{ is irreducible}\} = \frac{q^n}{n} + O\left(\frac{q^{\lfloor n/2\rfloor}}{n}\right).$$ We now explain why the range of is optimal. The constant $G_q(x)$ undergoes a change of behavior when $m\approx 2\log_q n$. Namely, for fixed $q$ and $n \to \infty$, we have $G_q(x) \sim 1$ if $m \sim (2+\varepsilon)\log_q n$ while $\log \log G_q(x) \sim \varepsilon \log n$ if $m \sim (2-\varepsilon)\log_q n$, see Lemma \[lem:gq growth\]. In view of this and of Theorem \[thm:saddle2\], the range of Theorem \[thm:saddle\] cannot be extended to $m \ge (2-\varepsilon)\log_q n$ for any particular $\varepsilon >0$.

Expected largest prime factor
-----------------------------

Let $L_{q}(f)$ be the largest degree of a prime polynomial dividing $f \in {\mathbb{F}}_q[T]$. Similarly, let $L(\pi)$ be the size of the longest cycle in the cycle decomposition of $\pi$.

Golomb @golomb1997 proved that ${\mathbb{E}}L(\pi_n)/n$ tends to a limit, known as the Golomb-Dickman constant, and approximated it as $0.624329\ldots$. Knopfmakher and Manstavičius @knopfmakher1997 proved that $$\label{eq:knopf}
{\mathbb{E}}L_q(f_n) - {\mathbb{E}}L(\pi_n) = O\left( \sqrt{\frac{n}{q\log n}}\right)$$ holds uniformly in $n$ and $q$. We prove the following estimate, which uncovers a transition around $\log q\asymp n\log n$.

\[thm:golomb\] As $q^n \to \infty$ we have $$c\exp(-C \max\{\sqrt{n\log n \log q}, \log q\}) \le{\mathbb{E}}L_q(f_n) - {\mathbb{E}}L(\pi_n)  \le C \exp(-c \max\{ \sqrt{n\log n \log q}, \log q\}).$$

To relate $L_q$ and $L$ with friable polynomials and permutations, observe that ${\mathbb{P}}(L_q(f_n) \le m)$ is equal to ${\mathbb{P}}(f_n \text{ is }m\text{-friable})$ and ${\mathbb{P}}(L(\pi_n) \le m)$ is equal to ${\mathbb{P}}(\pi_n \text{ is }m\text{-friable})$. The identity ${\mathbb{E}}X = 1+\sum_{i \ge 1}  (1-{\mathbb{P}}(X \le i))$ for ${\mathbb{N}}$-valued random variables shows that $$\label{eq:iden expected}
    {\mathbb{E}}L_q(f_n) - {\mathbb{E}}L(\pi_n) = \sum_{m=1}^{n}  \left( {\mathbb{P}}(f_n \text{ is }m\text{-friable}) - {\mathbb{P}}(\pi_n \text{ is }m\text{-friable}) \right).$$ By definition, the total variation distance between $L_q(f_n)$ and $L(\pi_n)$ is $$\begin{gathered}
    d_{TV}(L_q(f_ n), L(\pi_n)) = \sum_{m=1}^{n} | {\mathbb{P}}(f_n \text{ is }m\text{-friable}) - {\mathbb{P}}(\pi_n \text{ is }m\text{-friable}) \\- ({\mathbb{P}}(f_n \text{ is }(m-1)\text{-friable}) - {\mathbb{P}}(\pi_n \text{ is }(m-1)\text{-friable}))|.\end{gathered}$$ The fact that ${\mathbb{P}}(f_n \text{ is }m\text{-friable}) \ge {\mathbb{P}}(\pi_n \text{ is }m\text{-friable})$ (see Proposition \[prop:bndd unif\]) implies that $$\frac{1}{2}d_{TV}(L_q(f_n), L(\pi_n)) \le {\mathbb{E}}L_q(f_n) - {\mathbb{E}}L(\pi_n),$$ so Theorem \[thm:golomb\] yields an upper bound for $d_{TV}(L_q(f_n), L(\pi_n))$.

Previous works
--------------

### Dickman function and friability

To discuss previous results, we introduce the Dickman function $\rho \colon [0,\infty) \to (0,1]$. It is defined as $\rho(t)=1$ for $t \in [0,1]$, and for the rest of its range it is defined through the differential delay equation $$t\rho'(t)+\rho(t-1)=0.$$ It is a weakly-decreasing function, that decays superexponentially: $\rho(t)=t^{-t+o(t)}$ @tenenbaum2015 [p. 374]. It was introduced by Dickman @dickman1930 in his study of friable integers. We say that a number is $y$-friable if its prime factors are no larger than $y$. Dickman proved that, for any fixed $a>0$, $$\label{eq:dickman}
\#\{ 1 \le n \le x: n\text{ is }x^{1/a}\text{-friable}\} \sim x\rho(a)$$ as $x \to \infty$. Goncharov @goncharov1944 proved that $$\label{eq:gonch}
{\mathbb{P}}(\pi_n \text{ is }m\text{-friable}) =\rho(u)+o(1)$$ as $n/m$ tends to a positive constant; this is a permutation analogue of . From Proposition \[prop:bndd unif\] and Goncharov's result, we immediately obtain a polynomial analogue of his result: $${\mathbb{P}}(f_n \text{ is }m\text{-friable}) =\rho(u)+o(1) + O\left(\frac{1}{mq^{\lceil \frac{m+1}{2}\rceil}}\right) = \rho(u)+o(1)$$ as $n/m$ tends to a positive constant. This polynomial analogue was first established by Car @car1987, without making use of Goncharov's work. She established the quantitative version $${\mathbb{P}}\left( f_n \text{ is }m\text{-friable}\right) = \rho(u) + O\left( \frac{2^u}{m} \right).$$ This was later improved by Warlimont @warlimont1991 to $$\label{eq:warlimont}
{\mathbb{P}}\left( f_n \text{ is }m\text{-friable}\right) = \rho(u) + O\left( \frac{1}{m} \right).$$ A slightly weaker version of was proved independently by Panario, Gourdon and Flajolet @panario1998.

We explain how easily follows from our work. We first state a quantitative version of , proved in @manstavicius2016: $$\label{eq:pn transform}
{\mathbb{P}}(\pi_n \text{ is }m\text{-friable}) = \rho(u) \left(1+O\left( \frac{u \log (u+1)}{m}\right) \right)$$ for $m \ge \sqrt{n \log n}$. For $m \ge \sqrt{n \log n}$, follows at once from Proposition \[prop:bndd unif\] and , with an improved error term. For $m < \sqrt{n\log n}$, $1/m$ is greater than $c\rho(u)$, so amounts to ${\mathbb{P}}(f_n \text{ is }m\text{-friable})=O(1/m)$, which follows from Proposition \[prop:bndd unif\] and .

For $m \gg \sqrt{n \log n}$, Manstavičius proved @manstavicius1992 [Thm. 2] $$\label{eq:manstaerror}
{\mathbb{P}}\left( f_n \text{ is }m\text{-friable}\right) = \rho(u) \left( 1 +O\left(\frac{u\log(u+1)}{m}\right)\right).$$ This follows at once from and .

Under the Riemann Hypothesis, Hildebrand @hildebrand1984 proved that $$\#\{n \le x: n \text{ is }y\text{-friable}\} = x\rho\left(\frac{\log x}{\log y}\right)\exp\left(O_{\varepsilon}\left(\frac{\log\left(\frac{\log x}{\log y}+1\right)}{\log y}\right)\right)$$ as $x\to \infty$, uniformly for $\log y  \ge (2+\varepsilon)\log \log x$. In fact, this result also implies the Riemann Hypothesis. We find akin to Hildebrand's result, where in the polynomial setting, $\rho$ is replaced with ${\mathbb{P}}(\pi_n \text{ is }m\text{-friable})$. Note that our result is stronger: our error term goes to zero when $m\sim (2+\varepsilon)\log_q n$, while the error of term of Hildebrand does not if $\log y\sim (2+\varepsilon)\log \log x$.

It is natural to ask whether the approximation ${\mathbb{P}}(\pi_n \text{ is }m\text{-friable}) \sim \rho(u)$ holds beyond the range $m/\sqrt{n\log n}\to \infty$ implied by . In the appendix we show that $\rho$ is not an asymptotic approximation once $m/\sqrt{n \log n}$ is bounded from above.

### Saddle point analysis {#sec:saddle}

Odlyzko @odlyzko1985 used saddle point analysis to estimate ${\mathbb{P}}( f_n \text{ is }m\text{-friable})$ for $q=2$ and $n^{1/100} \le m\le n^{99/100}$. Lovorn @lovorn1992 extended this to general $q$ in his thesis. Note that the range $n^{1/100} \le m\le n^{99/100}$ is captured in full by Theorem \[thm:laplace\].

Manstavičius @manstavicius1992 [@manstavicius19922] extended the range of these results to the range $n \ge m\log m(\log \log m)^3$ with $m \to \infty$, and proved a relative error term of order $u^{-1} +mq^{-m}$. This result is an analogue of the work of Hildebrand and Tenenbaum @hildebrand19862, who estimated $\#\{1 \le n \le x : n \text{ is }y\text{-friable}\}$ uniformly in the range $2 \le y \le x$, with a relative error term of $\log y/\log x + \log y/y$. We do not give the full statements of these asymptotics for polynomials as they are somewhat complicated and are not needed here. For permutations, Manstavičius and Petuchovas obtained @manstavicius2016 $$\label{eq:pn saddle}
{\mathbb{P}}(\pi_n \text{ is }m\text{-friable}) = \frac{Q(x)}{\sqrt{2\pi \lambda}} \left( 1 + O\left(u^{-1}\right) \right)$$ where $Q(x) = \exp\left( \sum_{j=1}^{m} x^j/j\right)x^{-m}$ and $\lambda = \lambda(x) = \sum_{j=1}^{m} jx^j$. Here $x$ is as defined as in .

### Inequalities

Warlimont @warlimont1991 showed that ${\mathbb{P}}( f_n \text{ is }m\text{-friable}) \le C\exp(-cu)$, while Bender and Pomerance @bender1998 [Thm. 2.1] proved that ${\mathbb{P}}( f_n \text{ is }m\text{-friable})  \ge n^{-u}$ for $m\le \sqrt{n}$. In @joux2006 [App. A], Joux and Lercier prove $\log {\mathbb{P}}(f_n \text{ is }m\text{-friable}) \ge -(1+o_m(1)) u\log u$ for fixed $m$ and growing $q$ and $n$. Granville, Harper and Soundararajan @Granville2015 [Ex. 6] show that ${\mathbb{P}}( f_n \text{ is }m\text{-friable}) \ge \rho(n/m)$ and state, without proof, ${\mathbb{P}}( f_n \text{ is }m\text{-friable}) \ge \rho(n/m)\exp(cn/m^2)$. This implies the Dickman function is not a good approximation once $m/\sqrt{n}$ is bounded from above. In the appendix we make this optimal and show that the Dickman function is not an asymptotic approximation if $m/\sqrt{n \log n}$ is bounded.

### Soundararajan's work and a new result for permutations

In an unpublished manuscript[^1] Soundararajan @soundararajan [Thm. 1.1], building on Manstavičius @manstavicius1992 [@manstavicius19922], proved that $$\label{eq:sound1}
{\mathbb{P}}\left( f_n \text{ is }m\text{-friable}\right) = \rho(u) \exp\left(O\left(\frac{n\log n}{m^2} \right)\right)$$ uniformly for $ m \ge \log(n \log^2 n)/\log q$. For $m \le \log_q n$ he gives lower and upper bounds which are of different nature from , and are analogous to Ennola's work in the integer case @ennola1969. It would be interesting to adapt the work of de la Bretèche and Tenenbaum @dela2017, improving Ennola's results, to the polynomial and permutation settings as well.

Additionally, Soundararajan obtains an asymptotic formula for $\log \psi_q(n,m)$ uniformly in the full range $1\le m \le n$, with a relative error term $1/m + 1/\log n$.

Plugging in Proposition \[prop:bndd unif\] and letting $q \to \infty$ we obtain

\[thm:perm new\] Uniformly for $n \ge m \ge 1$ we have $$\label{eq:est perm}
{\mathbb{P}}(\pi_n \text{ is }m\text{-friable}) = \rho(u)\exp\left(O\left( \frac{n\log n}{m^2}\right) \right).$$

Although this does not give an asymptotic result for ${\mathbb{P}}(\pi_n \text{ is }m\text{-friable})$ itself if $m$ is relatively small, it does show that $\log {\mathbb{P}}(\pi_n \text{ is }m\text{-friable}) \sim \log \rho(u)$ as $n,m \to \infty$.

Very recently, Ford proved the upper bound ${\mathbb{P}}(\pi_n \text{ is }m\text{-friable}) \le e^{-u\log u+u}$ @ford2021cycle [Thm. 1.14] by elementary means, which for $m < c\log n/ \log \log (n+1)$ improves on the upper bound in .

### Some inaccuracies {#sec:inacc}

Let $\psi(x,y):=\#\{ 1 \le n \le x: n\text{ is }y\text{-friable}\}$. The Buchstab-de Bruijn identity states @granville2008 [Eq. (3.10)] $$\label{eq:bdidentity}
\psi(x,y) = 1+\sum_{p \le y} \psi\left( \frac{x}{p},p\right),$$ where the sum is over primes up to $y$. De Bruijn used it to prove that @debruijn1951 $$\psi(x,y) = x \rho(u) \left( 1 + O_{\varepsilon}\left(\frac{\log(\frac{\log x}{\log y}+1)}{\log y}\right)\right)$$ holds in the range $x \ge y \ge \exp((\log x)^{5/8+\varepsilon})$. We are not aware of a polynomial analogue of this identity. In the survey @granville2008, the identity $$\psi_q(n,m) - \psi_q(n,m-1)=\pi_q(m) \psi_q(n-m,m)$$ is suggested as an analogue of , where $\pi_q(m)$ is the number of monic irreducibles of degree $m$. However, this identity is false already for $n=4$, $m=2$ and $q=3$.

In @hildebrand1986, Hildebrand extended de Bruijn's result to the range $x \ge y \ge \exp((\log \log x)^{5/3+\varepsilon})$, by using the following identity: $$\psi(x,y)\log x=\int_{1}^{x} \frac{\psi(t,y)}{t}dt +\sum_{\substack{p^m \le x \\ p\le y}} \psi\left( \frac{x}{p^m},y\right)\log p,$$ where the sum is over $y$-friable prime powers up to $x$. Hildebrand's identity does have a simple polynomial analogue, namely $$\psi_q(n,m) n = \sum_{\substack{\deg (P^k) \le n \\ \deg(P) \le m}} \psi_q\left(n-\deg(P^k),m\right) \deg P.$$ It is proved in complete analogy with Hildebrand's original identity.

In @manstavicius1992 [Thm. 2] (cf. @knopfmakher1997 [Thm. A]) it is claimed that $$\label{eq:qmsave}
{\mathbb{P}}(f_n \text{ is }m\text{-friable}) = {\mathbb{P}}(\pi_n \text{ is }m\text{-friable}) \left( 1 + O_{\varepsilon}(q^{-m(1/2-\varepsilon)})\right)$$ holds uniformly in $m$ and $q$. This cannot hold as stated for small $m$, per the discussion in the introduction. In particular, a short computation shows that for $m = 1$, ${\mathbb{P}}(f_n \text{ is }1\text{-friable})/{\mathbb{P}}(\pi _n \text{ is }1\text{-friable}) \ge cn^2/q$, which contradicts if, say, $n \ge q$.

In @panario1998 an estimate similar to Warlimont's estimate is proved, but with an additional factor of $\log n$ in the numerator[^2]. Moreover, a proof is sketched of the following estimate, for every integer $k \ge 2$: $$\label{eq:flajolet}
    {\mathbb{P}}\left( f_n \text{ is }m\text{-friable}\right) = \rho(u) + O_k\left( \frac{\log n}{m^k} \right)$$ for $m <n/k$, as long as $m^k/\log n \to \infty$. However, this cannot hold as stated, even for bounded $u$ and $k=2$. Indeed, this violates the lower bound ${\mathbb{P}}( f_n \text{ is }m\text{-friable})  \ge \rho(u) + c\rho(u)u\log u/m$ (valid for $n/2 \ge m \ge \log n$) proven in the appendix.

Acknowledgements {#acknowledgements .unnumbered}
================

The author would like to thank Dor Elboim for useful discussions, Brad Rodgers and Gérald Tenenbaum for helpful comments on an earlier version of the manuscript, and Kannan Soundararajan for kindly sharing his unpublished manuscript. This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreements Nos. 786758 and 851318).

Preliminaries
=============

Primes
------

We denote by $\pi_q(n):=|\mathcal{P} \cap {\mathcal{M}_{n,q}}|$ the number of prime polynomials of degree $n$. From Gauss's identity @arratia1993 [Eq. (1.3)] $$\label{eq:gauss}
\sum_{d \mid n} d \pi_q(d) =q^n,$$ we obtain the estimate $$\label{eq:gaussbnd}
\frac{q^n}{2n} \le \pi_q(n) \le \frac{q^n}{n}$$ (cf. @pollack2013 [Lem. 4]) as well as the PPT .

Generating functions {#sec:gen}
--------------------

We define the following power series: $$\begin{split}
F(z)&:= 1+ \sum_{n \ge 1} {\mathbb{P}}( \pi_n \text{ is }m\text{-friable})z^n = 1+ \sum_{n \ge 1} \frac{\psi_{\pi}(n,m)}{n!}z^n,\\
F_q(z)&:= 1+ \sum_{n \ge 1} {\mathbb{P}}( f_n \text{ is }m\text{-friable})z^n = 1+ \sum_{n \ge 1} \frac{\psi_q(n,m)}{q^n}z^n.
\end{split}$$ Since ${\mathbb{P}}(\pi_n \text{ is }m\text{-friable})$ and ${\mathbb{P}}(f_n \text{ is }m\text{-friable})$ are between $0$ and $1$, these series converge absolutely in $|z|<1$ and define analytic function in the open disc. We shall show that they can be analytically continued to a larger region. The logarithm function will always be used with its principal branch.

\[lem:generating\] We have $$\label{eq:F form}
    F(z) = \exp\left( \sum_{i=1}^{m} \frac{z^i}{i} \right),$$ while for every prime power $q$ we have $$\label{eq:gqai}
    G_q(z) =  \frac{F_q(z)}{F(z)}= \exp\left( \sum_{i>m} \frac{a_i}{i} z^i\right), \qquad a_i = a_{i,m,q} := q^{-i}\sum_{d \mid i, \, d \le m} d\pi_q(d).$$ In particular, for all $i>m$ we have $$\label{eq:ai size}
    \frac{1}{2}q^{\max
        \{d\le m: \, d\textrm{ divides }i\}-i} \le a_i \le 2 q^{\min\{m,\lfloor i/2 \rfloor\}-i} \le 2q^{-\lceil i/2 \rceil}$$ and $F_q$ and $G_q$ are analytic in $|z|<q$.

The exponential formula for permutations @stanley1999enumerative [Cor. 5.1.9] states the following. Given a function $g\colon {\mathbb{N}}\to {\mathbb{C}}$, we construct a corresponding function on permutations (on arbitrary number of elements) as follows: $$G(\pi) = \prod_{C \in \pi} g(|C|),$$ where the product is over the disjoint cycles of $\pi$. We then have the following identity of formal power series: $$1+\sum_{i \ge 1} {\mathbb{E}}_{\pi \in S_i}  G(\pi) z^i = \exp\left(\sum_{j \ge 1} \frac{g(j)}{j}z^j\right).$$ Applying the identity with $g(j) = \mathbf{1}_{j \le m}$, we obtain . For $F_q$ we have, by unique factorization in ${\mathbb{F}}_q[T]$, $$F_q(z) = \prod_{\substack{P \in \mathcal{P}\\\deg(P) \le m}} \left( \sum_{i \ge 0} \left(\frac{z}{q}\right)^{\deg(P^i)}\right) =  \prod_{\substack{P \in \mathcal{P}\\\deg(P) \le m}} \left(1-\left(\frac{z}{q}\right)^{\deg(P)}\right)^{-1} = G_q(z)F(z)$$ and $$\begin{gathered}
    \log G_q(u) = \sum_{j \ge 1} \sum_{\deg(P) \le m} \frac{1}{j}\left(\frac{z}{q}\right)^{\deg(P)j} - \sum_{i=1}^{m} \frac{z^i}{i}\\ = \sum_{i \le m} \frac{z^i}{i} \bigg(q^{-i} \sum_{\substack{\deg(P)\le m\\\deg(P) \mid i}}\deg(P) - 1\bigg) + \sum_{i > m} \frac{z^i}{i} q^{-i} \sum_{\substack{\deg(P)\le m\\ \deg(P) \mid i}}\deg(P). 
    \end{gathered}$$ For $i \le m$ we have $\sum_{\deg(P)\le m,\, \deg(P) \mid i}\deg(P)/q^i = \sum_{d \mid i} d\pi_q(d)/q^i = 1$ by , proving . The bound now follows from .

Proof of Proposition \[prop:bndd unif\]
=======================================

We write $[z^n]H(z)$ the for the $n$th coefficient in a power series $H$. By definition, ${\mathbb{P}}(f_n \text{ is }m\text{-friable}) = [z^n]F(z)$ and ${\mathbb{P}}(\pi_n \text{ is }m\text{-friable}) = [z^n]F_q(z)$, where $F$ and $F_q$ are defined in §\[sec:gen\]. We are set out to prove $$0 \le [z^n](F_q-F) \le \frac{C}{ mq^{\lceil \frac{m+1}{2}\rceil}}.$$ By Lemma \[lem:generating\], $$F_q-F = F(G_q-1),$$ and both $F$ and $G_q-1$ have non-negative coefficients. This proves $[u^n](F_q-F) \ge 0$. For the upper bound we also use the non-negativity, which implies that $$[z^n](F_q-F) \le (\max_{0 \le i \le n} [z^i] F) (G_q(1)-1).$$ We have $$[z^i]F = {\mathbb{P}}(\pi_i \text{ is }m\text{-friable}) \le 1,$$ and so $[z^n](F_q-F) \le G_q(1)-1$. By , $$0 \le \sum_{i>m} \frac{a_i}{i} \le \frac{2}{m}\sum_{i>m}\frac{1}{q^{\lceil \frac{i}{2}\rceil}} \le \frac{C}{q^{\lceil \frac{m+1}{2}\rceil}m} \le C,$$ so that $$\label{eq:gq1}
    G_q(1) \le \exp\left(\frac{C}{mq^{\lceil \frac{m+1}{2}\rceil}}\right) = 1+O\left( \frac{1}{mq^{\lceil \frac{m+1}{2} \rceil}}\right)$$ and the required bound follows.

Analysis via Laplace transform
==============================

Here we shall use properties of the Laplace transform of $\rho$ to deduce Theorem \[thm:laplace\] in a limited range.

\[thm:laplace indeed\] If $n \ge m \ge C \sqrt{n \log n}$, then $$\label{eq:main largen2}
    \frac{{\mathbb{P}}(f_n \text{ is }m\text{-friable})}{{\mathbb{P}}(\pi_n \text{ is }m\text{-friable})} =1+ O\left(\frac{u \log (u+1)}{ mq^{\lceil \frac{m+1}{2}\rceil}}\right),  \qquad q^n \to \infty.$$

Asymptotics of parameters {#sec:i t}
-------------------------

We define $\xi \colon (1,\infty) \to (0,\infty)$ by $$\label{eq:def xi}
e^{\xi} = 1+u\xi.$$

@manstavicius2016 [Lem. 6]\[lem:xi size\] For $u>1$ we have $\log u < \xi \le 2 \log u$ and $\xi' \ge 1/u$.

Recall we have $$H_n:=\sum_{i=1}^{n} \frac{1}{i} = \log n + \gamma + O\left( \frac{1}{n} \right)$$ for the Euler-Mascheroni constant $\gamma$. Define $I(s)$ by $$I(s)=\int_{0}^{s} \frac{e^v-1}{v}\, dv, \qquad s \in {\mathbb{C}}.$$ Note that $I(\xi)$ grows faster than any polynomial in $\xi$.

@tenenbaum2015 [Ch. III.5, Thms. 7, 8]\[lem:rho i transform\] We have $$\label{eq:hat rho}
    \hat{\rho}(s) := \int_{0}^{\infty} e^{-sv}\rho(v)\, dv = \exp\left( \gamma + I(-s) \right)$$ for all $s \in {\mathbb{C}}$. Also, $$\label{eq:rho and i}
    \exp\left( \gamma-u\xi + I(\xi)\right) = \rho(u)\sqrt{\frac{2\pi}{\xi'}}\left(1 + O\left( \frac{1}{u}\right)\right).$$

@tenenbaum2015 [Ch. III.5, Lem. 8.2]\[lem:i bounds\] The following bounds hold for $s=-\xi+i\tau$, $\tau \in {\mathbb{R}}$: $$\hat{\rho}(s) = \begin{cases} O\left(\exp\left(I(\xi)-\frac{\tau^2u}{2\pi^2}\right)\right) & \mbox{if }|\tau| \le \pi,\\
    O\left(\exp\left(I(\xi)-\frac{u}{\pi^2+\xi^2}\right)\right) & \mbox{if }|\tau| \ge \pi,\\
    \frac{1}{s} + O\left( \frac{1+u \xi }{s^2} \right) & \mbox{if }|\tau| \ge 1+u\xi.\end{cases}$$

Define $T(s)$ by $$T(s)=\int_{0}^{s} \frac{e^v-1}{v}\left( \frac{v}{m} \frac{e^{v/m}}{e^{v/m}-1}-1\right)\, dv, \qquad s \in {\mathbb{C}}.$$

@manstavicius2016 [Lem. 11] \[lem:t\] Let $s=\eta+i\tau$, $0 \le \eta \le \pi m$ and $-\pi m \le \tau \le \pi m$. We have $$\left|T(s)+\frac{s}{2m}\right| \le \frac{4e^{\eta}}{m} + \frac{\tau^2}{12m^2}.$$

\[lem:gq exi\] Suppose $n \ge m \ge \sqrt{n \log n}$. If $n$ is sufficiently large we have $$0 \le G_q(e^{\xi/m})-1 \le \frac{C u \log(u+1)}{mq^{\lceil \frac{m+1}{2} \rceil}}.$$

By Lemma \[lem:xi size\] we have $e^{\xi}=1+u\xi  \le 1+2u\log u \le 1+2n\log n\le 1+2m^2 \le   q^{m/3}$, and so $e^{\xi/m}/\sqrt{q} \le q^{-1/6} \le 2^{-1/6}$. We have $$0 \le \sum_{i>m} \frac{a_i}{i} (e^{\xi/m})^i \le \frac{2}{m} \sum_{i > m} (e^{\xi/m})^i q^{-\lceil i/2 \rceil} \le \frac{C}{m} \left( \frac{e^{\xi(m+1)/m}}{q^{\lceil \frac{m+1}{2}\rceil}} + \frac{e^{\xi(m+2)/m}}{q^{\lceil \frac{m+2}{2}\rceil}} \right) \le \frac{C u \log(u+1)}{mq^{\lceil \frac{m+1}{2} \rceil}} \le C,$$ as needed.

\[lem:parts\] Let $A>0$. Suppose $m\pi \ge 1+u \xi$ and $u \ge \max\{A+1, 3\}$. Let $\Delta_2 =  \{ -\xi + i \tau: \tau \in [-m\pi,-(1+u\xi)]\cup[1+u\xi,m\pi]\}$. Then $$\int_{\Delta_2} e^{(u-A)s} \hat{\rho}(s)\, ds = O\left ( \exp(\xi A) \rho(u)\right).$$

Without loss of generality, we restrict our attention to $\Delta'_{2} = 
\{ -\xi + i\tau : \Im s \in [1+u\xi,m\pi]\} \subset \Delta_2$, and the other part is bounded in the same way. We integrate by parts: $$\int_{\Delta'_2} e^{(u-A)s} \hat{\rho}(s)\, ds = \frac{e^{(u-A)s}}{u-A}\hat{\rho}(s) \Biggr|_{-\xi+i(1+u\xi)}^{-\xi+im\pi} - \frac{1}{u-A}\int_{\Delta'_2} e^{(u-A)s} \hat{\rho}(s) \frac{e^{-s}-1}{s} \, ds.$$ Since $|\exp((u-A)s)| \le \exp(-\xi(u-A))$ and $\int_{\Delta'_2} |ds|/|s|^2 = O(1)$, the result follows by Lemmas \[lem:rho i transform\]–\[lem:i bounds\] and the triangle inequality.

Proof of Theorem \[thm:laplace indeed\]
---------------------------------------

Suppose $u \le M$. By (or Theorem \[thm:lower\]) and Proposition \[prop:bndd unif\], ${\mathbb{P}}(f_n \text{ is }m\text{-friable}) \ge c_M > 0$. Proposition \[prop:bndd unif\] now implies that $$\label{eq:main largen u bnd}
{\mathbb{P}}(f_n \text{ is }m\text{-friable}) = {\mathbb{P}}(\pi_n \text{ is }m\text{-friable}) \left(1 + O_M\left(\frac{1}{ mq^{\lceil \frac{m+1}{2}\rceil}}\right)\right),$$ which establishes the theorem in the case of bounded $u$. Hence, we may assume $u \gg 1$ in our argument.

Let $y:=e^{\xi/m}$, where $\xi$ is defined in . By Proposition \[prop:bndd unif\], $$\label{eq:bndd}
\frac{{\mathbb{P}}(f_n \text{ is }m\text{-friable})}{{\mathbb{P}}(\pi_n \text{ is }m\text{-friable})} = 1+ O_n\left(\frac{1}{q^{\lceil \frac{m+1}{2}\rceil}}\right)$$ and so we may assume that $n$ is sufficiently large. In particular, by Lemma \[lem:xi size\], $|y| \le e^{2\log u/m} \le e^{2\log n/\sqrt{n \log n}} \le 3/2 < q$ for sufficiently large $n$. Since $F$ and $F_q$ are analytic in $|z| < q$ by Lemma \[lem:generating\], we have, by Cauchy's integral formula, $${\mathbb{P}}(\pi_n \text{ is }m\text{-friable}) = \frac{1}{2\pi i} \int_{|z|=y} \frac{F(z)}{z^{n+1}}\, dz , \qquad {\mathbb{P}}(f_n \text{ is }m\text{-friable}) = \frac{1}{2\pi i} \int_{|z|=y} \frac{F_q(z)}{z^{n+1}}\, dz.$$ Using the parameterization $z=e^{-s/m}$ with $s=-\xi-i\tau$, $-m\pi \le \tau \le m\pi$, we obtain $${\mathbb{P}}(\pi_n \text{ is }m\text{-friable}) = \frac{1}{2\pi im} \int_{\Delta} e^{us} F(e^{-s/m}) \,ds, \qquad {\mathbb{P}}(f_n \text{ is }m\text{-friable}) = \frac{1}{2\pi im} \int_{\Delta} e^{us} F_q(e^{-s/m})\, ds$$ where $\Delta:=\{-\xi+i\tau: -m\pi \le \tau \le m\pi\}$. By Lemma \[lem:generating\], as in the proof of @manstavicius2016 [Cor. 3], $$\begin{gathered}
\label{eq:log f i t}
\log F(z) - H_m = \sum_{i=1}^{m} \frac{z^i-1}{i} = \int_{1}^{z} \sum_{i=1}^{m} t^{i-1}\,dt =\int_{1}^{z} \frac{t^m-1}{t-1}\, dt  \\= \int_{0}^{m\log z} \frac{e^v-1}{v}\frac{v}{m} \frac{dv}{1-e^{-v/m}} = I(m\log z) + T(m\log z)\end{gathered}$$ where $I$, $T$ are defined in §\[sec:i t\] and $z \ge 1$. Hence $$\label{eq:f h t}
F(e^{-s/m}) = \exp\big( H_m + I(-s) + T(-s)\big),$$ which holds for all $s \in \Delta$ (not only $s\le 0$) by the uniqueness principle. By and , $$F(e^{-s/m}) = \exp\big(H_m -\gamma + T(-s)\big)\hat{\rho}(s).$$ Hence, $$\label{eq:diff laplace}
{\mathbb{P}}(f_n \text{ is }m\text{-friable})-{\mathbb{P}}(\pi_n \text{ is }m\text{-friable}) = \frac{\exp\big(H_m -\gamma\big)}{2\pi im} \int_{\Delta} e^{us} \hat{\rho}(s) \exp(T(-s)) (G_q(e^{-s/m})-1)\,ds.$$ We have $|\exp(H_m -\gamma)/m| =O(1)$, and we turn to bound the integral in the right-hand side of . We partition $\Delta$ as $\Delta_0 \cup \Delta_1 \cup \Delta_2$, where $\Delta_0=\{-\xi+i\tau: -\pi \le \tau \le \pi\}$, $\Delta_1=\{-\xi+i\tau: \tau \in [-(1+u\xi),-\pi] \cup [\pi, 1+u\xi]\}$ and $\Delta_2 = \{-\xi+i\tau: \tau \in [-m\pi,-(1+u\xi)] \cup [1+u\xi,m\pi]\}$. We may assume that $m\pi > 1+u\xi > \pi$ since we can take $n\gg 1$ and $u \gg 1$. By Lemma \[lem:t\], $T(-s)$ is bounded in $\Delta$, and so $$\begin{split}
\big| \int_{\Delta_i} e^{us} \hat{\rho}(s) \exp(T(-s)) (G_q(e^{-s/m})-1)\,ds\big| &\le C \int_{\Delta_i} \big| e^{us} \hat{\rho}(s) \exp(T(-s)) (G_q(e^{-s/m})-1)\,ds\big|\\
& \le C \exp(-u\xi) (G_q(e^{\xi/m})-1) \int_{\Delta_i} |\hat{\rho}(s)| \, |ds|
\end{split}$$ for $i=0,1$. For $i=0$ we have by the first part of Lemma \[lem:i bounds\] $$\int_{\Delta_0} |\hat{\rho}(s)| \, |ds| \le C \exp\big( I(\xi)\big) \int_{-\pi}^{\pi} \exp(-\tau^2u/2\pi^2)\,d\tau \le   \frac{C\exp\big( I(\xi)\big)}{\sqrt{u}},$$ and so, by Lemmas \[lem:xi size\] and \[lem:rho i transform\], $$\big| \int_{\Delta_0} e^{us} \hat{\rho}(s) \exp(T(-s)) (G_q(e^{-s/m})-1)\,ds\big| \le C\rho(u)  (G_q(e^{\xi/m})-1).$$ Similarly, for $i=1$ we have by the second part of Lemma \[lem:i bounds\] $$\int_{\Delta_1} |\hat{\rho}(s)| \, |ds| \le C \exp\big( I(\xi)\big) \exp(-u/(\pi^2+\xi^2)) (1+u\xi) ,$$ and so, by Lemmas \[lem:xi size\] and \[lem:rho i transform\], $$\begin{split}
\big| \int_{\Delta_1} e^{us} \hat{\rho}(s) \exp(T(-s)) (G_q(e^{-s/m})-1)\,ds\big| &\le C\rho(u) \sqrt{u}\exp(-u/(\pi^2+\xi^2))(1+u\xi) (G_q(e^{\xi/m})-1)\\
&\le  C\rho(u) u^{3/2}\log(u+1)\exp(-cu/\log^2(u+1)) (G_q(e^{\xi/m})-1) \\
&\le C \rho(u)(G_q(e^{\xi/m})-1).
\end{split}$$ As $G_q(e^{\xi/m})-1 = O(u \log(u+1)/(mq^{\lceil (m+1)/2\rceil}))$ by Lemma \[lem:gq exi\], the integrals over $\Delta_0$ and $\Delta_1$ contribute at most $$\label{eq:size integral}
C\frac{\rho(u)u\log(u+1)}{mq^{\lceil (m+1)/2\rceil}}.$$ We wish to bound the integral over $\Delta_2$ by the same quantity. However, using the triangle inequality as before we will incur an extra factor of $\log m$ coming from the integral of $|\hat{\rho}(s)| = O(1/|s|)$ on $\Delta_2$. To remove this factor, we first replace $\exp(T(-s))$ by $1$ – a short calculation using Lemma \[lem:t\] shows that the error obtained is acceptable. It remains to bound $$\label{eq:delta2 int}
\int_{\Delta_2} e^{us} \hat{\rho}(s) (G_q(e^{-s/m})-1)\,ds.$$ Lemma \[lem:generating\] shows we may write $$G_q(e^{-s/m})-1 = \sum_{i=m+1}^{4m} \frac{a_i \left(e^{-s/m}\right)^{i}}{i} + O\left( \frac{e^{2\xi}}{q^{m}}\right)$$ with $a_i=O(q^{-\lceil i/2 \rceil})$. The integral $\int_{\Delta_2} |e^{us} \hat{\rho}(s) e^{2\xi}/q^{m} |ds$ is sufficiently small (smaller than ). The term corresponding to $i$ is bounded by Lemma \[lem:parts\]: $$\int_{\Delta_2} e^{us} \hat{\rho}(s)\frac{a_i \left(e^{-s/m}\right)^{i}}{i}\, ds =O\left( \exp\left( \xi i/m\right) \frac{\rho(u)}{mq^{\lceil \frac{i}{2} \rceil}}\right).$$ Summing over $m+1 \le i \le 4m$, we see that is smaller than . All in all, $${\mathbb{P}}(f_n \text{ is }m\text{-friable}) - {\mathbb{P}}(\pi_n \text{ is }m\text{-friable}) = O\big( \rho(u) \frac{u\log(u+1)}{ q^{\lceil \frac{m+1}{2}\rceil}m}\big).$$ By (or Theorem \[thm:lower\]), $\rho(u) \le C{\mathbb{P}}(\pi_n \text{ is }m\text{-friable})$, which gives the desired result.

Saddle point analysis {#saddle-point-analysis}
=====================

We shall deduce Theorems \[thm:saddle\] and \[thm:saddle2\] from the following

\[thm:saddle3\] If $\min\{n/(\log n \log^3\log  (n+1)), \, n/3\} \ge m \ge \log_q n$ then $$\label{eq:main mediumn4}
    \frac{{\mathbb{P}}(f_n \text{ is }m\text{-friable})}{{\mathbb{P}}(\pi_n \text{ is }m\text{-friable})} =  G_q(x)\left(1 + O\left( \frac{G_q''(x)x^2+G_q'(x)xm}{nmG_q(x)}\right)\right).$$

Asymptotics of parameters {#asymptotics-of-parameters}
-------------------------

Recall that $x$ is the positive constant defined by $\sum_{j=1}^{m} x^j = n$, and that $\lambda=\sum_{j=1}^{m} jx^j$.

@manstavicius2016 [Lem. 9] \[lem:lambda\] For $u>1$ we have $|\lambda - mn| \le mn/\log u$. For $u \ge 3$ we have $$\label{eq:x size}
    x^m = \Theta\left(n \min\left\{1, \frac{\log u}{m}\right\}\right).$$

\[lem:deriv\] Suppose $n/3 \ge m \ge (2+\varepsilon)\log_q n$ for some $\varepsilon>0$. Let ${a}= \mathbf{1}_{2 \mid m}$. Then $$\label{eq:gqx}
    1+\frac{cux^{1+{a}}}{q^{\lceil \frac{m+1}{2} \rceil}} \min\left\{1, \frac{\log u}{m}\right\} \le G_q(x) \le 1+ \frac{C_{\varepsilon}ux^{1+{a}}}{q^{\lceil \frac{m+1}{2} \rceil}} \min\left\{1, \frac{\log u}{m}\right\},$$ and in particular, $$\label{eq:gqx2}
    G_q(x) = 1+\Theta_{n,\varepsilon}\left( \frac{1}{q^{\lceil \frac{m+1}{2}\rceil}}\right).$$ Moreover, $$|G'_q(x)| \le C_{\varepsilon} \frac{nx^{{a}}}{q^{\lceil \frac{m+1}{2} \rceil}}\min\left\{1,\frac{\log u}{m}\right\},\qquad |G''_q(x)| \le C_{\varepsilon} \frac{nmx^{{a}-1}}{q^{\lceil \frac{m+1}{2} \rceil}} \min\left\{1, \frac{\log u}{m}\right\}.$$

By , $$\label{eq:ai aux}
     \sum_{i>m} \frac{a_i}{i}x^i \le \sum_{i>m}\frac{2x^i}{mq^{\lceil \frac{i}{2}\rceil}}.$$ and $$\label{eq:ai aux lower}
    G_q(x)-1 \ge \sum_{i>m} \frac{a_i}{i}x^i \ge \frac{cx^m}{m}(a_{m+1}x+a_{m+2}x^2) \ge \frac{cx^m x^{1+{a}}}{mq^{\lceil \frac{m+1}{2}\rceil}} .$$ As $1 \le x \le n^{1/m} \le q^{1/(2+\varepsilon)}$, the right-hand side of is at most $C_{\varepsilon}(x^m/m)x^{1+{a}}q^{-\lceil (m+1)/2\rceil}$ (consider even and odd $i$ separately). By this is $O_{\varepsilon}(1)$ (consider $\log u \ge m$ and $\log u \le m$ separately) and also proves the upper bound for $G_q(x)$ in . For the lower bound, guarantees that the right-hand side of is at least as stated.

As $C_\varepsilon ux^{1+{a}} =O_{n,\varepsilon}(1)$, we obtain . Similarly, as $x^m \le n$, $$\sum_{i>m} a_i x^{i-1} \le C_\varepsilon \left( \frac{x^m}{q^{\lceil \frac{m+1}{2} \rceil}} + \frac{x^{m+1}}{q^{\lceil \frac{m+2}{2}\rceil }} \right) \le C_\varepsilon \frac{nx^{{a}}}{q^{\lceil \frac{m+1}{2} \rceil}}\min\left\{1,\frac{\log u}{m}\right\} \le \frac{C_{\varepsilon}}{x},$$ yielding the bound on $G'_q(x)$. Considering separately $m<i \le 2m+1$ and $i \ge 2m+2$, $$\sum_{i>m} (i-1)a_i x^{i-2} \le C_\varepsilon m\left( \frac{x^{m-1}}{q^{\lceil \frac{m+1}{2} \rceil}} + \frac{x^m}{q^{\lceil \frac{m+2}{2} \rceil}}+ \frac{x^{2m}}{q^{m+1}} \right) \le C_\varepsilon \frac{nmx^{{a}-1}}{q^{\lceil \frac{m+1}{2} \rceil}} \min\left\{1, \frac{\log u}{m}\right\},$$ which yields the desired bound on $G''_q(x)$.

\[lem:small m\] Fix $\varepsilon>0$. Suppose $(2-\varepsilon) \log_q n \ge m \ge (1+\varepsilon)\log_q n$. Then $$\frac{G_q'(x)x}{G_q(x)} = O_{\varepsilon} \left( \frac{n^2}{q^m}\right), \, \frac{G_q''(x)x^2}{G_q(x)} = O_{\varepsilon} \left( \frac{n^4}{q^{2m}} + \frac{mn^2}{q^m}\right).$$

If $n$ is bounded, so are $m$ and $q$ and the bounds are trivial, so we may assume $n \gg_{\varepsilon} 1$. We have $$\frac{G_q'(x)x}{G_q(x)} = \sum_{i>m} a_i x^i \le C \sum_{i=m+1}^{2m} \frac{x^i}{q^{\frac{i}{2}}} + Cq^m\sum_{i=2m+1}^{\infty} \frac{x^i}{q^i}.$$ As $x \le n^{1/m} \le q^{1/(1+\varepsilon)}$ and by $x \ge n^{1/m}e^{-C/m} \ge q^{1/(2-\varepsilon/2)}$, the required bound follows. Similarly, $$\frac{G_q''(x)x^2}{G_q(x)} = \left( \sum_{i>m} a_i x^i \right)^2 + \sum_{i>m} a_ix^i(i-1) \le C_{\varepsilon}\left( \frac{n^2}{q^m}\right)^2+ Cm\sum_{i=m+1}^{2m} \frac{x^i}{q^{\frac{i}{2}}} + Cq^m\sum_{i=2m+1}^{\infty} \frac{ix^i}{q^i},$$ and the second bound follows as well.

\[lem:gq growth\] Fix $q$ and $\varepsilon \in (0,1)$. If $m \sim (2+\varepsilon)\log_q n$ as $n \to \infty$ then $G_q(x) \sim 1$. If $m \sim (2-\varepsilon)\log_q n$ then $\log \log G_q(x)\sim \varepsilon \log n$.

The first part follows from . For the second part, recall that $G_q(x) \ge \exp(a_{2m}x^{2m}/(2m))$ and $a_{2m} \ge 1/(2q^m)$ by . By Lemma \[lem:lambda\], $x^{2m}/(2m) \ge c_q n^2 /\log n$. Hence $\log \log G_q(x) \ge 2\log n -m \log q + o_q(\log n) = \varepsilon \log n+o_q(\log n)$. A matching upper bound follows from Lemma \[lem:small m\], since $\log G_q(x) \le G_q'(x)/(xG_q(x))$.

Proof of Theorem \[thm:saddle3\]
--------------------------------

Since $F$ is entire, we have, by Cauchy's integral formula, $${\mathbb{P}}(\pi_n \text{ is }m\text{-friable}) = \frac{1}{2\pi i} \int_{|z| = x} \frac{F(z)}{z^{n+1}}\, dz.$$ The parameterization $z=xe^{it}$, $t \in [-\pi,\pi]$ shows, by Lemma \[lem:generating\], that $$\begin{gathered}
{\mathbb{P}}(\pi_n \text{ is }m\text{-friable}) = \frac{1}{2\pi} \int_{-\pi}^{\pi} \exp\left( \sum_{j=1}^{m} \frac{x^j e^{itj}}{j} - n(it+\log x)\right) \, dt \\= \frac{Q(x)}{2\pi} \int_{-\pi}^{\pi} \exp\left( \sum_{j=1}^{m} \frac{x^j (e^{itj}-1)}{j}-int \right) \, dt.\end{gathered}$$ As $F_q$ is analytic in $|z|<q$, and $x < q$, we similarly have, by Lemma \[lem:generating\], that $${\mathbb{P}}(f_n \text{ is }m\text{-friable}) =\frac{1}{2\pi i} \int_{|z| = x} \frac{F_q(z)}{z^{n+1}}\, dz= \frac{Q(x)}{2\pi} \int_{-\pi}^{\pi} \exp\left( \sum_{j=1}^{m} \frac{x^j (e^{itj}-1)}{j} - int\right) G_q(xe^{it})\, dt.$$ Hence, $$\begin{gathered}
\label{eq:diff p}
{\mathbb{P}}(f_n \text{ is }m\text{-friable}) - {\mathbb{P}}(\pi_n \text{ is }m\text{-friable}) G_q(x)  \\=  \frac{Q(x)}{2\pi} \int_{-\pi}^{\pi} \exp\left( \sum_{j=1}^{m} \frac{x^j (e^{itj} - 1)}{j}-int\right)  (G_q(xe^{it}) - G_q(x))\, dt.\end{gathered}$$ By assumption, $u \ge 3$. Let $t_0=n^{-1/3}m^{-2/3}$ and $t_1 = 1/m$. We shall bound separately the contribution of $|t|\le t_0$, $t_0 \le |t|\le t_1$ and $t_1 \le |t| \le \pi$ to the right-hand side of . For $k=1,2,3$, let $$I_k = \int_{A_k}  \exp\left( \sum_{j=1}^{m} \frac{x^j (e^{itj} - 1)}{j}-int\right)  \left(G_q(xe^{it}) - G_q(x)\right)\, dt,$$ where $A_1 = [-t_0,t_0]$, $A_2 = [-t_1,t_1]\setminus A_1$ and $A_3 = [-\pi,\pi]\setminus A_2$. A second-order Taylor approximation shows that for $|t| \le \pi$, $$\label{eq:taylor g}
\begin{split}
G_q(xe^{it})-G_q(x) &= G'_q(x) (xe^{it}-x) + O\left(G''_q(x)\left|xe^{it}-x\right|^2\right) \\
&= iG'_q(x)xt  + O\left(\left(G''_q(x)x^2 + G'_q(x)x\right)t^2\right).
\end{split}$$ For $|t| =O(1/m)$ and $ 1\le j \le m$ we have $e^{itj}-1 = itj -(tj)^2/2 + O(|t|^3j^3)$, so that $$\label{eq:taylor sum}
\sum_{j=1}^{m} \frac{x^j (e^{itj} - 1)}{j}-int = it\left( \sum_{j=1}^{m} x^j - n\right) -\frac{t^2}{2} \sum_{j=1}^{m} x^j j + O\left(|t|^3 \sum_{j=1}^{m} x^j j^2\right) = - \frac{\lambda t^2}{2} + O\left( |t|^3 \lambda_2\right)$$ where $$\lambda_2 = \sum_{j=1}^{m} x^j j^2 \le m \sum_{j=1}^{m} x^j j = m \lambda.$$ In $A_1$ we have $|t|^3\lambda_2 = O(n^{-1}m^{-2}m\lambda)=O(1)$ by Lemma \[lem:lambda\]. By and , $$I_1 =  \int_{-t_0}^{t_0} \exp\left(-\frac{\lambda t^2}{2}\right) \left(iG'_q(x)xt + O\left(|t|^2 a + |t|^4 b\lambda_2 + |t|^5 a\lambda_2\right)\right)\, dt$$ for $a = G_q''(x)x^2+G_q'(x)x$, $b=G'_q(x)x$. We have $\int_{-t_0}^{t_0} \exp(-\lambda t^2/2) t \, dt= 0$ and $\int_{{\mathbb{R}}} \exp(-\lambda t^2/2) |t|^k\, dt \le C \lambda^{-(k+1)/2}$ for $k=2,4,5$. Hence $$|I_1| \le C \left( \lambda^{-3/2} a + \lambda^{-5/2}b\lambda_2 + \lambda^{-3} a \lambda_2\right) \le \frac{C}{\lambda^{3/2}} \left( a+bm  + \frac{am}{\sqrt{\lambda}}\right).$$ As $n \ge 3m$, we have $\lambda \ge cnm$ by Lemma \[lem:lambda\]. Thus $$\label{eq:i1 bnd}
|I_1| \le  \frac{C}{\sqrt{\lambda}}\frac{a+bm}{nm}.$$ We turn our attention to $I_2$. We have $1-\cos s \ge cs^2$ in $|s| \le \pi$, and so $$\left|\exp\left( \sum_{j=1}^{m} \frac{x^j (e^{itj} - 1)}{j}-int\right)\right| \le \exp\left( -c\lambda t^2 \right)$$ for $t \in A_2$. Moreover, $|G(x)-G(xe^{it})| \le Cb|t|$, yielding $$|I_2| \le Cb \int_{A_2} |t| \exp\left( -c\lambda t^2 \right)\, dt \le Cb \exp\left( -c\lambda t_0^2 \right) \int_{A_2} |t| \, dt \le \frac{Cb}{m^2}\exp\left( -c\lambda t_0^2 \right) \le \frac{C}{\sqrt{\lambda}} \frac{b}{n}.$$ We turn our attention to $I_3$. We first treat the case $m \ge 4$. We have $|G_q(xe^{it})-G_q(x)| \le CxG'_q(x)= Cb$ for $|t| \le \pi$. By @manstavicius2016 [Lem. 12], $$\max_{1/m \le |t| \le \pi} \Re \sum_{j=1}^{m} \frac{x^j (e^{itj} - 1)}{j} \le -\frac{1}{4\pi^2} \frac{u^{1-\frac{4}{m+1}}}{\log^2 u} + \frac{2}{m} + \frac{2}{\log u}$$ for $n/m \ge 3$. Hence $$\begin{split}
|I_3| &\le Cb \max_{1/m \le |t| \le \pi} \left|\exp\left( \sum_{j=1}^{m} \frac{x^j (e^{itj} - 1)}{j} - int\right)\right|  \\
& \le Cb \exp\left( -\frac{1}{4\pi^2} \frac{u^{1-\frac{4}{m+1}}}{\log^2 u} + \frac{2}{m} + \frac{2}{\log u} \right) \\
& =\frac{C b}{n\sqrt{\lambda}} \exp\left(\frac{\log \lambda}{2}+\log n -\frac{1}{4\pi^2} \frac{u^{1-\frac{4}{m+1}}}{\log^2 u} + \frac{2}{m} + \frac{2}{\log u} \right).
\end{split}$$ We want to show that the expression in the exponent is bounded by a constant from above, and then the upper bound for $|I_3|$ will match that of $|I_1|$. The terms $2/m$ and $2/\log u$ are already bounded. The term $\log \lambda /2$ is bounded by $C + (\log mn)/2$ by Lemma \[lem:lambda\]. So it suffices to bound $$S(m,u):=2\log m + \frac{3 \log u}{2} -\frac{1}{4\pi^2} \frac{u^{1-\frac{4}{m+1}}}{\log^2 u}.$$ We may also assume $n \gg 1$, since otherwise $S(m,u)$ is trivially bounded. As $ m\ge 4$, if $4\log u> m+1$ we have $$S(m,u) \le 2\log m + \frac{3\log u}{2} -\frac{1}{4\pi^2} \frac{u^{1-\frac{4}{5}}}{\log^2 u} \le 2\log (4 \log u-1) +  \frac{3\log u}{2} -\frac{1}{4\pi^2} \frac{u^{\frac{1}{5}}}{\log^2 u},$$ which is bounded for $u \ge 3$. If $4 \log u \le m+1$ and $n$ is sufficiently large, $$\frac{1}{4\pi^2} \frac{u^{1-\frac{4}{m+1}}}{\log^2 u} \ge \frac{cu}{\log^2 u} \ge \frac{c\log n\log^3\log(n+1)}{\log^2\log(n+1)} \ge \frac{5 \log n}{2} \ge 2\log m + \frac{3 \log u}{2}$$ using the condition $m \le n/(\log n\log^3\log(n+1))$, and so $S(m,u) \le 0$. All in all, $S(m,u)$ is bounded. If $1 \le m \le 3$, we run the same argument but with the naive bound $\Re \sum_{j=1}^{m}x^j (e^{itj} - 1)/j \le -cn^{1/m}/m$ for $1/m \le |t| \le \pi$ coming from considering only the first term in the sum. In summary, $$|I_3| \le \frac{Cb}{n\sqrt{\lambda}}.$$ By and our bounds on $I_i$, we find that $$\label{eq:diff p2}
\left| {\mathbb{P}}(f_n \text{ is }m\text{-friable}) - {\mathbb{P}}(\pi_n \text{ is }m\text{-friable}) G_q(x) \right| \le C \frac{Q(x)}{\sqrt{\lambda}}\frac{a+bm}{nm}.$$ By , $Q(x)/\sqrt{\lambda} \le C {\mathbb{P}}(\pi_n \text{ is }m\text{-friable})$, which yields the proof of .

Proof of Theorem \[thm:laplace\]
--------------------------------

For $m\ge C\sqrt{n\log n}$ this is Theorem \[thm:laplace indeed\], so it is left to deal with $C\sqrt{n\log n} \ge m \ge 6 \log n$. We may assume that $n\gg 1$ due to Proposition \[prop:bndd unif\]. The condition $C\sqrt{n\log n} \ge m$ implies $n / (\log n \log^2 \log(n+1)), n/3 \ge m$ (for $n \gg 1$), while the condition $m\ge 6\log n$ implies $x=\Theta(1)$ and $m \gg \log u$. Lemma \[lem:deriv\] now says that $G_q(x)=\Theta(1)$ and also gives upper bounds on $|G_q'(x)|$ and $|G_q''(x)|$. Plugging these in Theorem \[thm:saddle3\], we obtain $$\label{eq:gq 3delta}
    \frac{{\mathbb{P}}(f_n \text{ is }m\text{-friable})}{{\mathbb{P}}(\pi_n \text{ is }m\text{-friable})}= G_q(x) \left( 1+O\left( \frac{\log u}{mq^{\lceil \frac{m+1}{2}\rceil}}   \right)\right).$$ By , $G_q(x) = 1+ O(u\log u/(mq^{\lceil (m+1)/2 \rceil}))$, which yields .

Proof of Theorem \[thm:saddle\]
-------------------------------

The condition $8\log n\ge m$ implies $n / (\log n \log^2 \log(n+1)), n/3 \ge m$ as long as $n$ is sufficiently large. In this case, we have by Lemma \[lem:deriv\] that $1 \le G_q(x) \le C_{\varepsilon}$ and also upper bounds on $|G_q'(x)|$ and $|G_q''(x)|$. Plugging these in Theorem \[thm:saddle3\], we obtain $$\label{eq:gq 2delta}
\frac{{\mathbb{P}}(f_n \text{ is }m\text{-friable})}{{\mathbb{P}}(\pi_n \text{ is }m\text{-friable})}= G_q(x) \left( 1+O_{\varepsilon}\left( \frac{x^{1+{a}}}{q^{\lceil \frac{m+1}{2}\rceil}}   \right)\right).$$ By , $G_q(x) = 1+ O_{\varepsilon}(ux^{1+{a}}/q^{\lceil (m+1)/2 \rceil})$, which gives . For bounded $n$, the required result is immediate from and .

Proof of Theorem \[thm:saddle2\]
--------------------------------

The estimate is if $m \le 8\log u$ and is otherwise. Estimate follows from Theorem \[thm:saddle3\] and Lemma \[lem:small m\].

Proof of Theorem \[thm:golomb\]
===============================

We shall utilize identity . We shall also use the fact that ${\mathbb{P}}(f_n \text{ is }m\text{-friable}) \ge {\mathbb{P}}(\pi_n \text{ is }m\text{-friable})$, see Proposition \[prop:bndd unif\]. For $m=1$ we have strict inequality.

We first assume $n\log n \le \log q$. In this range we must prove $c/q^C \le {\mathbb{E}}L_q(f_n) - {\mathbb{E}}L(\pi_n) \le C/q^c$. Since $L_q(f_n)$ and $L(\pi_n)$ are bounded from above by $n$, we can bound the difference ${\mathbb{E}}L_q(f_n) - {\mathbb{E}}L(\pi_n)$ by $n$ times the total variation distance of the two random variables, which is known to be $O(1/q)$ @arratia1993 [Thm. 6.1], so we have $${\mathbb{E}}L_q(f_n) - {\mathbb{E}}L(\pi_n) = O\left( \frac{n}{q}\right).$$ This shows ${\mathbb{E}}L_q(f_n) - {\mathbb{E}}L(\pi_n) \le \log q/ q$. To produce a lower bound, we consider the contribution of $1$-friable polynomials and permutations to : $$\begin{gathered}
{\mathbb{E}}L_q(f_n) - {\mathbb{E}}L(\pi_n) \ge {\mathbb{P}}(f_n \text{ is }1\text{-friable}) -  {\mathbb{P}}(\pi_n \text{ is }1\text{-friable}) = \frac{\binom{q+n-1}{n}}{q^n}-\frac{1}{n!}\\ = \frac{1}{n!} \left( \prod_{i=1}^{n-1} \left(1+\frac{i-1}{q} \right) - 1\right) \ge cn^{-n} \frac{n^2}{q} \ge \frac{1}{q^2}.\end{gathered}$$ We turn to the case $n \log n \ge \log q$; we may assume $n\gg 1$. To prove an upper bound, we use Theorems \[thm:laplace\] and \[thm:saddle\], and the monotonicity of ${\mathbb{P}}(f_n \text{ is }m\text{-friable})$ in $m$ to obtain $$\begin{split}
\sum_{m=1}^{n}  \left( {\mathbb{P}}(f_n \text{ is }m\text{-friable}) - {\mathbb{P}}(\pi_n \text{ is }m\text{-friable}) \right) &\le M {\mathbb{P}}(f_n \text{ is }M\text{-friable}) + \sum_{n \ge m > M} \frac{n{\mathbb{P}}(\pi_n \text{ is }m\text{-friable})}{mq^{m/2}} \\
& \le CM {\mathbb{P}}(\pi_n \text{ is }M\text{-friable}) + \frac{Cn}{q^{M/2}}
\end{split}$$ for any $M \ge 3\log_q n$. We take $M=\lceil A\sqrt{n \log n/\log q} \rceil$ for large $A$ (admissible if $n \gg 1$). The term $Cn/q^{M/2}$ is $\le C\exp(-c\sqrt{ n\log n \log q})$. By Theorem \[thm:perm new\], so is $M{\mathbb{P}}(\pi_n \text{ is }M\text{-friable})$.

We now prove a lower bound for ${\mathbb{E}}L_q(f_n) - {\mathbb{E}}L(\pi_n)$. Considering only the term $m=M$ in , and using Theorem \[thm:saddle2\], we obtain $$\label{eq:ee diff}
{\mathbb{E}}L_q(f_n) - {\mathbb{E}}L(\pi_n)  \ge {\mathbb{P}}(\pi_n \text{ is }M\text{-friable}) \left( G_q(x) - 1+ O\left( \frac{x^{1+{a}}\min\{1, \frac{\log u}{M}\}}{q^{\lceil \frac{M+1}{2}\rceil}} \right)\right).$$ The term ${\mathbb{P}}(\pi_n \text{ is }M\text{-friable})$ is $\ge c\exp(-C\sqrt{n \log n \log q})$ by Theorem \[thm:perm new\]. By and , $$\label{eq:gq1 lower}
G_q(x) - 1 \ge c\frac{u x^{1+{a}}\min\{1, \frac{\log u}{M}\} }{q^{\lceil \frac{M+1}{2}\rceil}}.$$ As the right-hand side of dominates the error term in (if $n \gg 1$) and $1/q^{\lceil (M+1)/2\rceil}$ is bounded from below by $c\exp(-C\sqrt{n \log n \log q})$, we conclude the proof.

Limitation to approximation via the Dickman function {#sec:append}
====================================================

We define a quantity $\Delta(n,m)$ by $${\mathbb{P}}(\pi_n \text{ is }m\text{-friable}) = \rho(u)(1+\Delta(n,m)).$$ By , $\Delta(n,m) = O(u \log (u+1)/m)$ if $n\log n \le m^2$. We prove a matching lower bound.

\[thm:lower\] For $n>m$, $\Delta(n,m) > 0$. If furthermore $m \le n/2$, then $\Delta(n,m) \gg  u \log(u)/m$.

The inequality $\Delta>0$ is not new, see @Granville2015 [Ex. 6]. We expect a similar phenomenon to hold for friable integers, see @granville2008 [p. 274]. An asymptotic version of the integer analogue of $\Delta >0$ is known to hold asymptotically. Levin and Faĭnleĭb @Levin1967 (cf. Saias @Saias1989 and Granville @granville2008 [Eq. (1.25)]) gave an asymptotic series for $\#\{1\le n \le x: n \text{ is } y\text{-friable}\}/x$, whose first term is $\rho(\log x/\log y)$ while the second term is *positive*, namely $(1-\gamma)\rho(\log x/\log y - 1)/\log x$.

Note that if $m$ is close to $n$, we really do not expect the lower bound in Theorem \[thm:lower\] to hold, e.g. $\Delta(n,n-1) = O(1/n^2)$. We will be using Hildebrand's estimate @hildebrand1984 [Lem. 1] $$\label{eq:rho ratio}
    \frac{\rho(u-t)}{\rho(u)} = e^{t\xi}(1+O(u^{-1}))$$ uniformly for $0 \le t \le 1$ and $u \ge 1$. Here $\xi>0$ is as in , and satisfies $\xi = \log(u\log u)+O(\log \log u/\log u)$ as $u \to \infty$, see @hildebrand19862 [Lem. 1]. Our proof is inspired by @hildebrand1984, where Hildebrand was concerned with *upper bounds* on $\Delta$ in the integer setting. It would be interesting to see if some of the mentioned upper bounds on $\Delta$ (e.g. and ) can be proven using this method.

Preparatory lemmas
------------------

Let $$S_1(n,m) := \frac{1}{u\rho(u)} \left(\frac{1}{m} \sum_{i=1}^{m} \rho\left(u-\frac{i}{m}\right) - \int_{0}^{1} \rho(u-t)dt\right)=\frac{1}{n} \sum_{i=1}^{m} \frac{\rho(u-\frac{i}{m})}{\rho(u)} - 1,$$ where the second equality follows from the identity $\int_{0}^{1} \rho(u-t) dt = u\rho(u)$. Let $$S_2(n,m):= \frac{1}{n} \sum_{i=1}^{m} \frac{\rho(u-\frac{i}{m}) \Delta(n-i,m)}{\rho(u)}.$$

\[lem:s1s2\] For $n\ge m$ we have the relation $\Delta(n,m) = S_1(n,m) + S_2(n,m)$.

By differentiating and equating coefficients we have, for $n \ge m$, $$n{\mathbb{P}}(\pi_n \text{ is }m\text{-friable}) = \sum_{i=1}^{m} {\mathbb{P}}(\pi_{n-i} \text{ is }m\text{-friable}).$$ Rewriting this in terms of $\Delta(n,m)$ yields the result.

\[lem:pos\] If $n\ge m$ we have $S_1(n,m)\ge 0$ with equality if and only if $n=m$.

Since $\rho$ is strictly decreasing for $u \ge 1$, for each $1\le i\le m$ we have $$\frac{1}{m}\rho\left(u-\frac{i}{m}\right) \ge \int_{(i-1)/m}^{i/m} \rho(u-t)\,dt$$ with equality if and only if $u \le (i-1)/m +1$. The result follows by summing over $i=1,\ldots,m$.

\[lem:strong\] For positive $x$ let $F(x)=(1-e^{-x})^{-1} - x^{-1} \ge 1/2$. For $m \le n/2$ we have $$S_1(n,m) =(1+o_{u \to \infty}(1))\frac{\log u}{m} F\left(\frac{\log(u\log u)}{m}\right).$$ Moreover, the $1+o_{u \to \infty}(1)$ term is bounded away from $0$.

We write $$S_1(n,m) = \frac{1}{u\rho(u)} \sum_{i=1}^{m} \int_{(i-1)/m}^{i/m} \left(\rho\left( u - \frac{i}{m}\right) - \rho(u-t)\right) dt = \frac{-1}{u\rho(u)} \sum_{i=1}^{m} \int_{(i-1)/m}^{i/m} \int_{t}^{i/m}\rho'\left( u -  x\right) dx\,dt.$$ As $\rho'(u)=-\rho(u-1)/u$ and $\rho(u-1)>0$, this becomes $$S_1(n,m) = \frac{1+O(u^{-1})}{u^2\rho(u)} \sum_{i=1}^{m} \int_{(i-1)/m}^{i/m} \int_{t}^{i/m}\rho\left( u -  x-1\right) dx\,dt.$$ By , this is $$\begin{aligned}
 S_1(n,m) &= (1+O(u^{-1})) \frac{\log u}{u} \sum_{i=1}^{m} \int_{(i-1)/m}^{i/m} \int_{t}^{i/m}(u \log u)^{x} dx\,dt\\
        &= \frac{1+o_{u \to \infty}(1)}{\log(u \log u)} \frac{\log u}{u} \sum_{i=1}^{m} \int_{(i-1)/m}^{i/m} ((u\log u)^{i/m} - (u \log u)^{t}) dt\\
        &= \frac{1+o_{u \to \infty}(1)}{u} \left( \frac{u\log u-1}{m(1-(u\log u)^{-1/m})} - \frac{u\log u-1}{\log(u\log u)}\right)\\
        &= (1+o_{u \to \infty}(1))\frac{\log u}{m} F\left( \frac{\log(u\log u)}{m} \right)
    \end{aligned}$$ and the conclusion follows.

Proof of Theorem \[thm:lower\]
------------------------------

Positivity follows by direct induction from Lemmas \[lem:s1s2\] and \[lem:pos\]. Suppose $n/2 \ge m$. We introduce $$a(n) := \frac{\Delta(n,m)}{\log(n/m)/m}$$ which by the recurrence in Lemma \[lem:s1s2\] and the estimates and Lemma \[lem:strong\] satisfies the relation $$a(n) \ge  c + \frac{(1+o_{u \to \infty}(1))}{n}\sum_{i=1}^{m} a(n-i) (u\log u)^{i/m}$$ for $n/2 \ge m$. Moreover, $a(n) \gg 1$ by Lemma \[lem:strong\] and the non-negativity of $S_2$.

Observe that $\sum_{i=1}^{m} (u\log u)^{i/m} \ge n(1+o_{u\to\infty}(1))$. Hence, if $a(n),\ldots,a(n+m-1) \ge A$ then $a(n+m),\ldots,a(n+2m-1) \ge c + A(1+o_{u\to\infty}(1))\ge (c/2)+A$ for $u \gg 1$. Iterating this implication yields $a(n) \gg n/m$ for $u \gg 1$, implying $\Delta(n,m) \gg u (\log u)/m$, as needed.

<span style="font-variant:small-caps;">Mathematical Institute, University of Oxford, Oxford, OX2 6GG, UK</span>

*E-mail address:* `loribrown@example.com`

[^1]: Soundararajan's work is surveyed in @Odlyzko1993 [@granville2008]. In @Odlyzko2000 [@Schirokauer2002] it is explained that Soundararajan's work remained unpublished in view of the stronger result published in @panario1998; however, as shown in §\[sec:inacc\] that work is flawed.

[^2]: The result is stated as ${\mathbb{P}}(f_n \text{ is }m\text{-friable})=\rho(u) (1+O(\frac{\log n}{m}))$, but – as observed in Tenenbaum's review @tenenbaumreview - this should read ${\mathbb{P}}(f_n \text{ is }m\text{-friable})=\rho(u) +O(\frac{\log n}{m})$.

{'source': 'arXiv_out/2203'}