\documentclass[CRMATH,Unicode,biblatex,XML]{cedram} \TopicFR{Théorie des nombres} \TopicEN{Number theory} \addbibresource{CRMATH_Gorodetsky_20230271.bib} \usepackage{amssymb} \usepackage{mathtools} \usepackage[capitalize]{cleveref} \crefname{coro}{Corollary}{Corollaries} \crefname{defi}{Definition}{Definitions} \crefname{lemm}{Lemma}{Lemmas} \crefname{prop}{Proposition}{Propositions} \crefname{rema}{Remark}{Remarks} \crefname{exam}{Example}{Examples} \crefname{nota}{Notation}{Notations} \crefname{theo}{Theorem}{Theorems} \crefname{conj}{Conjecture}{Conjectures} \crefname{ques}{Question}{Questions} \crefname{table}{Table}{Tables} \crefname{figure}{Figure}{Figure} %\newtheorem{theorem}{Theorem}[section] %\newtheorem{lemma}[theorem]{Lemma} %\newtheorem{corollary}[theorem]{Corollary} %\newtheorem{proposition}[theorem]{Proposition} %\theoremstyle{remark} %\newtheorem{remark}[theorem]{Remark} \newcommand{\R}{{\mathbb R}} \newcommand{\Z}{{\mathbb Z}} \newcommand{\N}{{\mathbb N}} \newcommand{\E}{{\mathbb E}} \newcommand{\CC}{{\mathbb{C}}} \renewcommand{\Re}{\mathop{\mathrm{Re}}} \newcommand{\Lrm}{\mathrm{L}} \newcommand{\dd}{\mathrm{d}} \DeclareMathOperator{\expe}{e} \let\tfrac\frac %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \makeatletter \let\save@mathaccent\mathaccent \newcommand*\if@single[3]{% \setbox0\hbox{${\mathaccent"0362{#1}}^H$}% \setbox2\hbox{${\mathaccent"0362{\kern0pt#1}}^H$}% \ifdim\ht0=\ht2 #3\else #2\fi } %The bar will be moved to the right by a half of \macc@kerna, which is computed by amsmath: \newcommand*\rel@kern[1]{\kern#1\dimexpr\macc@kerna} %If there's a superscript following the bar, then no negative kern may follow the bar; %an additional {} makes sure that the superscript is high enough in this case: \newcommand*\widebar[1]{\@ifnextchar^{{\wide@bar{#1}{0}}}{\wide@bar{#1}{1}}} %Use a separate algorithm for single symbols: \newcommand*\wide@bar[2]{\if@single{#1}{\wide@bar@{#1}{#2}{1}}{\wide@bar@{#1}{#2}{2}}} \newcommand*\wide@bar@[3]{% \begingroup \def\mathaccent##1##2{% %Enable nesting of accents: \let\mathaccent\save@mathaccent %If there's more than a single symbol, use the first character instead (see below): \if#32 \let\macc@nucleus\first@char \fi %Determine the italic correction: \setbox\z@\hbox{$\macc@style{\macc@nucleus}_{}$}% \setbox\tw@\hbox{$\macc@style{\macc@nucleus}{}_{}$}% \dimen@\wd\tw@ \advance\dimen@-\wd\z@ %Now \dimen@ is the italic correction of the symbol. \divide\dimen@ 3 \@tempdima\wd\tw@ \advance\@tempdima-\scriptspace %Now \@tempdima is the width of the symbol. \divide\@tempdima 10 \advance\dimen@-\@tempdima %Now \dimen@ = (italic correction / 3) - (Breite / 10) \ifdim\dimen@>\z@ \dimen@0pt\fi %The bar will be shortened in the case \dimen@<0 ! \rel@kern{0.6}\kern-\dimen@ \if#31 \overline{\rel@kern{-0.6}\kern\dimen@\macc@nucleus\rel@kern{0.4}\kern\dimen@}% \advance\dimen@0.4\dimexpr\macc@kerna %Place the combined final kern (-\dimen@) if it is >0 or if a superscript follows: \let\final@kern#2% \ifdim\dimen@<\z@ \let\final@kern1\fi \if\final@kern1 \kern-\dimen@\fi \else \overline{\rel@kern{-0.6}\kern\dimen@#1}% \fi }% \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax}% \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a %The following initialises \macc@kerna and calls \mathaccent: \if#31 \macc@nested@a\relax111{#1}% \else %If the argument consists of more than one symbol, and if the first token is %a letter, use that letter for the computations: \def\gobble@till@marker##1\endmarker{}% \futurelet\first@char\gobble@till@marker#1\endmarker \ifcat\noexpand\first@char A\else \def\first@char{}% \fi \macc@nested@a\relax111{\first@char}% \fi \endgroup } \makeatother \let\oldbar\bar \renewcommand*{\bar}[1]{\mathchoice{\widebar{#1}}{\widebar{#1}}{\widebar{#1}}{\oldbar{#1}}} \let\oldtilde\tilde \renewcommand*{\tilde}[1]{\mathchoice{\widetilde{#1}}{\widetilde{#1}}{\oldtilde{#1}}{\oldtilde{#1}}} \let\oldhat\hat \renewcommand*{\hat}[1]{\mathchoice{\widehat{#1}}{\widehat{#1}}{\oldhat{#1}}{\oldhat{#1}}} \renewcommand*{\to}{\mathchoice{\longrightarrow}{\rightarrow}{\rightarrow}{\rightarrow}} \let\oldmapsto\mapsto \renewcommand*{\mapsto}{\mathchoice{\longmapsto}{\oldmapsto}{\oldmapsto}{\oldmapsto}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand*{\mk}{\mkern -1mu} \newcommand*{\Mk}{\mkern -2mu} \newcommand*{\mK}{\mkern 1mu} \newcommand*{\MK}{\mkern 2mu} \hypersetup{urlcolor=purple, linkcolor=blue, citecolor=red} \newcommand*{\romanenumi}{\renewcommand*{\theenumi}{\roman{enumi}}} \newcommand*{\Romanenumi}{\renewcommand*{\theenumi}{\Roman{enumi}}} \newcommand*{\alphenumi}{\renewcommand*{\theenumi}{\alph{enumi}}} \newcommand*{\Alphenumi}{\renewcommand*{\theenumi}{\Alph{enumi}}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %jouer avec le \hsize pour avoir la bonne largeur des adresses \makeatletter \def\@setafterauthor{% \vglue1mm% \begingroup\hsize=13cm\advance\hsize\abstractmarginL\raggedright \noindent \begin{minipage}[t]{13cm} \leftskip\abstractmarginL \normalfont\Small \@afterauthor\par \end{minipage} \endgroup \vglue-2.5mm \vskip-2pt plus 3pt minus 1pt } \makeatother \title[Almost primes]{On Erd\H{o}s sums of almost primes} \alttitle{Sur les sommes d'Erdős de presque premiers} \author{\firstname{Ofir} \lastname{Gorodetsky}} \address{Mathematical Institute, University of Oxford, Oxford, OX2 6GG, UK} \address{Department of Mathematics, Technion -- Israel Institute of Technology, Haifa 3200003, Israel} \email{ofir.gor@technion.ac.il} \author{\firstname{Jared} \middlename{Duker} \lastname{Lichtman}\IsCorresp} % Address of record for the research reported here \address{Department of Mathematics, Stanford University, Stanford, CA, USA} \email{jared.d.lichtman@gmail.com} \author{\firstname{Mo} \middlename{Dick} \lastname{Wong}} % Address of record for the research reported here \address{Department of Mathematical Sciences, Durham University, Stockton Road, Durham DH1 3LE, UK} \email{mo-dick.wong@durham.ac.uk} \thanks{The first author is supported by funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 851318). The second author is supported by a Clarendon Scholarship at the University of Oxford. The second and third author acknowledge support by travel grants from the Heilbronn Institute for Mathematical Research (HIMR)} \CDRGrant[ERC]{851318} \subjclass{11N25, 11Y60, 11A05, 60G18, 60H25} \keywords{\kwd{Almost primes} \kwd{primitive set} \kwd{Dickman distribution} \kwd{recursive distributional equation}} \altkeywords{\kwd{Nombres presque premiers} \kwd{ensemble primitif} \kwd{loi de Dickman} \kwd{équation en loi récursive}} %\date{\today} \begin{abstract} In 1935, Erd\H{o}s proved that the sums $f_k=\sum_n 1/(n\log n)$, over integers $n$ with exactly $k$ prime factors, are bounded by an absolute constant, and in 1993 Zhang proved that $f_k$ is maximized by the prime sum $f_1=\sum_p 1/(p\log p)$. According to a 2013 conjecture of Banks and Martin, the sums $f_k$ are predicted to decrease monotonically in $k$. In this article, we show that the sums restricted to odd integers are indeed monotonically decreasing in $k$, sufficiently large. By contrast, contrary to the conjecture we prove that the sums $f_k$ increase monotonically in $k$, sufficiently large. Our main result gives an asymptotic for $f_k$ which identifies the (negative) secondary term, namely $f_k = 1 - (a+o(1))k^2/2^k$ for an explicit constant $a= 0.0656\cdots$. This is proven by a refined method combining real and complex analysis, whereas the classical results of Sathe and Selberg on products of $k$ primes imply the weaker estimate $f_k=1+O_{\varepsilon}(k^{\varepsilon-1/2})$. We also give an alternate, probability-theoretic argument related to the Dickman distribution. Here the proof reduces to showing a sequence of integrals converges exponentially quickly $\mathrm{e}^{-\gamma}$, which may be of independent interest. \end{abstract} \begin{altabstract} En 1935, Erd\H{o}s a prouvé que les sommes $f_k=\sum_n 1/(n\log n)$, portant sur les entiers $n$ ayant exactement $k$ facteurs premiers, sont majorées par une constante absolue, et en 1993, Zhang a prouvé que $f_k$ est maximisé par la somme sur les nombres premiers $f_1=\sum_p 1/(p\log p)$. Selon une conjecture de Banks et Martin de 2013, les sommes $f_k$ devraient être décroissantes en fonction de $k$. Dans cet article, nous démontrons que les sommes restreintes aux entiers impairs sont bien décroissantes pour $k$ suffisamment grand. En revanche, contrairement à la conjecture, nous prouvons que les sommes $f_k$ sont croissantes en fonction de $k$, suffisamment grand. Notre résultat principal donne une formule asymptotique pour $f_k$ qui identifie le terme secondaire (négatif), à savoir $f_k = 1 - (a+o(1))k^2/2^k$ pour une constante explicite $a= 0,0656\cdots$. Ceci est prouvé par une méthode raffinée combinant analyse réelle et complexe, alors que les résultats classiques de Sathe et Selberg sur les produits de $k$ nombres premiers impliquent l'estimation plus faible $f_k=1+O_{\varepsilon}(k^{\varepsilon-1 /2})$. De plus, nous donnons un argument probabiliste alternatif, lié à la distribution de Dickman. Ici, la preuve se réduit à démontrer qu'une suite d'intégrales converge exponentiellement rapidement vers $\mathrm{e}^{-\gamma}$, ce qui peut présenter un intérêt indépendant. \end{altabstract} \begin{document} \maketitle \newpage \section{Introduction} Let $\Omega(n)$ denote the number of prime factors of $n$, counted with repetition. If $\Omega(n)=k$, $n$ is called a $k$-almost prime. For each $k\ge1$ denote the series \begin{align*} f_k = \sum_{\Omega(n)=k}\frac{1}{n\log n}. \end{align*} Here $f_k$ is the {\it Erd\H{o}s sum} of $k$-almost primes, also called the $k^\textnormal{th}$ {\it fingerprint number}. In 1935 Erd\H{o}s~\cite{Erd} showed that $f_k = O(1)$ is bounded\footnote{Indeed, his result bounded Erd\H{o}s sums $f(A)=\sum_{n\in A}1/(n\log n)$ uniformly over any primitive set $A$.} and in 1993 Zhang~\cite{Zh2} proved the primes have maximal Erd\H{o}s sum, that is, $f_k \le f_1$ holds for all $k$. This had given initial evidence towards the Erd\H{o}s primitive set conjecture, now recently proven by the second author~\cite{LEPSC}. In 2013, Banks and Martin~\cite{BM} posed a vast generalization of the Erd\H{o}s primitive set conjecture (see~\cite{BM, LEPSC} for details and further discussion). In particular, they conjectured that the sums $f_k$ decrease monotonically in $k$. Denote the sum $f_{k,y}$ restricting $f_k$ to integers without prime factors $\le y$, that is, \begin{align*} f_{k,y}=\sum_{\substack{\Omega(n)=k\\ p\mid n\to p> y}} \frac{1}{n \log n}. \end{align*} Banks and Martin further conjectured that for any fixed $y \ge 1$, $f_{k,y}$ decrease monotonically. We prove that their conjecture holds for $y\ge2$ and $k$ sufficiently large. By contrast, we prove that $f_k=f_{k,1}$ increases monotonically in $k$, sufficiently large. \begin{theorem}\label{thm:monotonic} Let $y\ge2$. For $k$ sufficiently large, we have $f_{k-1}f_{k,y}$. \end{theorem} When $y\ge2$, we believe $f_{k-1,y}>f_{k,y}$ should hold for all $k>1$, in accordance with Banks--Martin~\cite{BM}. When $y=1$, we believe $f_{k-1}6$. These inequalities have been verified numerically up to $k\le 20$~\cite{Lalmost}. The classical Sathe--Selberg theorem gives asymptotics for the counting function of $k$-almost primes, and implies $f_k$ converges to 1 with square-root error. That is $f_k=1+O_{\varepsilon}(k^{\varepsilon-1/2})$, see~\cite[Theorem~4.1]{Lalmost}. We give an exponential refinement of this result, which identifies the (negative) secondary term to be $-a_1\, k^2/2^k$ for an explicit constant $a_1= 0.0656\cdots$. \begin{theorem}\label{thm:fkthm} For all $k\ge1$ we have \begin{align*} f_{k} = 1 - 2^{-k} \big(a_1k^2 + O\big(k \log(k+1)\big)\big), \end{align*} where $a_1=(d\log 2)/4$ and \begin{align}\label{def:d} d\coloneqq \frac{1}{4}\prod_{p > 2} \left( 1-\frac{2}{p}\right)^{-1} \left(1-\frac{1}{p}\right)^2 = 0.37869\cdots. \end{align} \end{theorem} To motivate the proof of Theorem~\ref{thm:fkthm}, we first handle the sifted Erd\H{o}s sums $f_{k,y}$, whose (positive) secondary term is of order $O_y(2^{-k})$ when $y\ge2$, and so converge more rapidly. \begin{theorem}\label{thm:fkck22k} Let $y\ge 2$. We have \begin{align*} f_{k,y} = \prod_{p \le y}\left(1-\frac{1}{p}\right) + a_y/2^k + O_y(k^3/3^{k}) \end{align*} uniformly for $k \ge 1$, where $a_y=c_yd_y$ for {\postdisplaypenalty1000000 \begin{align} c_y&= \gamma + \sum_{p \le y} \frac{\log p}{p-1}-\sum_{p>y}\frac{\log p}{(p-1)(p-2)}, \label{def:cy}\\ d_y &= d\prod_{2

y} \frac{z^{\Omega(n)}}{n^s} \] when $y=1$ and $y\ge2$. Namely, the singularity closest to $0$ when $y=1$ is at $z=2$ while for $y\ge2$ it is more distant. This provides a clean answer to the hitherto unexplained numerical observations up to $k\le 20$. \begin{remark} Our methods can also handle $\sum_{\omega(n)=k,\, p \mid n \to p>y}1/(n\log n)$, where $\omega(n)=\sum_{p \mid n}1$. For this problem, the analysis does not have a discrepancy between $y=1$ and $y\ge2$. Our methods should also handle the Dirichlet series $\sum_{\Omega(n)=k} n^{-t}$ for $t>1$. For these, striking work of Banks--Martin~\cite{BM} shows that $k=1$ is maximal if and only if $t>\tau$, where $\tau= 1.14\cdots$ is the unique solution to a certain functional equation involving the Riemann zeta function. When $t<\tau$ it is not understood which $k=k_t$ is maximal, also see~\cite{CLP2,CLPk}. Finally, one may also consider translated sums $\sum_{\Omega(n)=k} 1/(n(\log n+h))$ for $h\in\R$, where the author~\cite{Ltranslate} proved that $k=1$ is not maximal for $h>1.04\cdots$. In fact, $k=1$ is minimal if and only if $h>0.803\cdots$. \end{remark} \begin{remark} Hankel contours over the complex plane are used in the Selberg--Delange method, concerning asymptotics for the sums $\sum_{n \le x} z^{\Omega(n)}$, $z$ complex. Saddle point analysis is used in the Sathe--Selberg theorem, which extracts information on the counting function of $k$-almost primes from these sums. These devices are powerful but lead to poor savings. By contrast, our proofs contain neither saddle point analysis nor Hankel contours. Moreover, the Selberg--Delange method assumes a zero-free region for $\zeta(s)$, as well as a bound on $\log\zeta(s)$ to the left of $\Re(s)=1$. By contrast, our proofs make no complex-analytic assumptions about $\zeta(s)$ whatsoever. We only use the (very basic) Taylor expansion $\zeta(t)(t-1)= 1 + \gamma(t-1) + O((t-1)^2)$ for real $t\in(1,2)$. \end{remark} \subsection{A sequence of integrals} We also provide an alternate, probability-theoretic argument, which gives (weaker) exponential error $f_k=1 + O(k/2^{k/4})$, but which has potentially much wider applicability to other primitive sets beyond $k$-almost primes. We leave further development of this perspective to future work. The rough strategy is to first show an asymptotic relation \begin{equation}\label{eq:fksim} f_{k} \sim \expe^{\gamma} I_{\lfloor k/4\rfloor} \end{equation} for a certain sequence of iterated integrals $I_k$. Here $\gamma=0.5772\cdots$ is the Euler--Mascheroni constant. Specifically, let $I_0=1$ and for $k\ge 1$ let \begin{align} I_k=\int_{[0,1]^k} \frac{\dd x_1\, \dd x_2 \cdots \dd x_k}{1+x_1(1+x_2(\cdots(1+x_k)\cdots))}. \end{align} Let $P_1(n)$ be the largest prime factor of $n$. To connect $f_k$ to $I_k$, we use Mertens' theorem to show that $f_k$ is close to $\expe^{\gamma}$ times a \textit{weighted average} of $\log P_1(n)/\log n$ over integers $n$ with $\Omega(n)=k$, see~\eqref{eq:fk1uj0}. Then for each $n=p_1\cdots p_k$ ($p_1 \ge p_2 \ge \cdots$), the reciprocal of this ratio may be expressed as \begin{align*} \frac{\log n}{\log P_1(n)} &= 1 + \frac{\log p_2}{\log p_1}\left(1+\cdots\left(1+\frac{\log p_{j+1}}{\log p_j} \left(1+\frac{\log\left(p_{j+2}\cdots p_k\right)}{\log p_{j+1}}\right)\right)\cdots\right). \end{align*} Further, we show the consecutive ratios $\frac{\log p_{i+1}}{\log p_i}\in[0,1]$ are independent and uniformly distributed in $[0,1]$ (with respect to a certain probability measure) which ultimately leads to~\eqref{eq:fksim}. See~\eqref{eq:fk1uj0} and~\eqref{eq:f1kleIj}--\eqref{eq:f1kgeIj} for the precise quantitative formulation of~\eqref{eq:fksim}. Finally, we prove that $I_k$ converges exponentially quickly to $\expe^{-\gamma}$, which may be of independent interest. The qualitative convergence $I_k\to \expe^{-\gamma}$ may be deduced from work of Chamayou~\cite{Chamayou} (cf.~\cite[Proposition~2.1]{Molchanov}). \begin{theorem}\label{thm:iteratedIk} We have $I_k=\expe^{-\gamma} + O(2^{-k})$. \end{theorem} Our approach to \Cref{thm:iteratedIk} is self-contained and relies on a probabilistic reformulation of the problem, which turns out to be related to the Dickman--Goncharov distribution. See the extensive survey of Molchanov and Panov~\cite{Molchanov} for background on this distribution, which appears across probability and theoretical computer science~\cite{HT2002}. \subsection{Proof of monotonicity results} Here we quickly deduce Theorem~\ref{thm:monotonic} assuming Theorems~\ref{thm:fkthm} and~\ref{thm:fkck22k}: Indeed, for large $k$ we have \begin{align*} f_k - f_{k-1} &= \frac{\log 2}{4} d \big((k-1)^2/2^{k-1} - k^2/2^k \big) \ + \ o(k^2/2^k) \\ &= \frac{\log 2}{4} d k^2/2^k + o(k^2/2^k) \ > \ 0 \end{align*} by Theorem~\ref{thm:fkthm}. Similarly, by Theorem~\ref{thm:fkck22k} we have \begin{align*} f_{k-1,y} - f_{k,y} &= c_yd_y (1/2^{k-1} - 1/2^k ) \ + \ o(1/2^k) \\ &= c_yd_y/2^k + o(1/2^k) \ > \ 0. \end{align*} Here we used $c_y>0$ for $y\ge2$. Indeed, $c_y$ from~\eqref{def:cy} is clearly increasing in $y\ge2$, so $c_y\ge c_2>0$ since \begin{align*} \sum_{p>2}\frac{\log p}{(p-1)(p-2)} < .9 < 1.2 < \log 2 + \gamma. \end{align*} This completes the proof of Theorem~\ref{thm:monotonic}. \subsection{Proof method: permutations} As a short illustration of the proof method, we consider a permutation analogue of the sums $f_k$. This result also may be of independent interest. Namely, define $f_{k,\pi}$ by \begin{align*} f_{k,\pi}\coloneqq \sum_{m \ge 1} \frac{a_{m,k}}{m} \end{align*} where $a_{m,k}$ is the probability that a permutation, chosen uniformly at random from $S_m$, has exactly $k$ disjoint cycles. \begin{remark} To see the analogy with the original sum, given a permutation $\pi \in S_m$ let $C(\pi)$ be the number of disjoint cycles in $\pi$, $d(\pi)$ be $m$ and $|\pi|$ be $|S_m|=m!$. The sum $f_{k,\pi}$ may be expressed as \[ f_{k,\pi}=\sum_{\substack{C(\pi)=k\\\pi \in \cup_{m \ge 1} S_m}} \frac{1}{|\pi| d(\pi)}. \] The weight $1/(|\pi| d(\pi))$ is analogous to $1/(n\log n)$. \end{remark} Recall the Riemann zeta function $\zeta(s)=\sum_{n \ge 1}n^{-s}$. \begin{proposition} For any $k \ge 1$ we have \[ f_{k,\pi}= \zeta(k+1)=1+2^{-k-1}+O(3^{-k}). \] \end{proposition} \begin{proof} Consider the exponential generating function of $\sum_{\pi \in S_n} z^{C(\pi)}$: \begin{align*} F(u,z)\coloneqq \sum_{m\ge 0} \frac{1}{m!} \left(\sum_{\pi \in S_m} z^{C(\pi)}\right)u^m = 1+\sum_{k\ge1} z^k\sum_{m \ge 1} a_{m,k}u^m. \end{align*} The exponential formula for permutations shows \begin{align}\label{eq:expformpermut} F(u,z)=\exp\left(\sum_{n \ge 1}z \frac{u^n}{n}\right)=\exp\left(-z\log(1-u)\right). \end{align} The Taylor series for $\exp(-z\log(1-u))$ in $z$ is \[ \exp\left(-z\log(1-u)\right)= \sum_{k \ge0} \frac{z^k}{k!}\left(-\log(1-u)\right)^k, \] so extracting the coefficient of $z^k$ in $F(u,z)$ yields, by~\eqref{eq:expformpermut}, \begin{equation}\label{eq:zk coeff} \sum_{m \ge 1}a_{m,k}u^m = \frac{\left(-\log (1-u)\right)^k}{k!}. \end{equation} Since $1/m = \int_0^1 u^{m-1}\,\dd{u}$, we can integrate~\eqref{eq:zk coeff} over $u\in[0,1]$ to obtain \[ f_{k,\pi}=\sum_{m \ge 1 }\frac{a_{m,k}}{m} = \int_{0}^{1}\frac{\left(-\log(1-u)\right)^k}{k!}\frac{\dd u}{u} = \int_{0}^{\infty} \frac{x^k}{\Gamma(k+1)} \frac{\dd x}{\expe^x-1} = \zeta(k+1). \] This completes the proof. Here in the third equality we performed the change of variables $u=1-\expe^{-x}$, and in the fourth we applied Riemann's famous integral representation for $\zeta(s)$, with $s=k+1$, \[ \Gamma(s)\zeta(s)=\int_{0}^{\infty}\frac{x^{s-1}}{\expe^x-1}\dd x.\qedhere \] \end{proof} \begin{remark} In the same way that we shall relate $f_k$ to the sequence of integrals $I_k$ in Theorem~\ref{thm:iteratedIk}, one can relate $f_{k,\pi}$ to $I_k$ as well. \end{remark} \section{Sifted sums} \subsection{Preparation} We now collect a few analytic properties of the generating functions that will play central roles in the proof of Theorem~\ref{thm:fkck22k}. Let us start with the function \begin{align}\label{def:Fsz} F(s,z) \coloneqq \sum_{n\ge 1} \frac{z^{\Omega(n)}}{n^s} = \prod_p \Big(1-\frac{z}{p^s}\Big)^{-1}, \qquad s \in \mathbb{R}. \end{align} \begin{lemma}\label{lem:cont} The function $F(s,z)$ converges absolutely for $s>1$ and $|z|<2$. In this domain $F$ has a power series representation in $z$ and it defines a smooth function in $s$.\footnote{In this paper we will only need first and second derivatives with respect to $s$, which is always seen as a real-valued variable.} \end{lemma} \begin{proof} Observe that for $s \ge 1+\varepsilon$ and $|z| \le 2^{-\varepsilon}$ the $p$th factor in~\eqref{def:Fsz} is \[ \left(1-\frac{z}{p^s}\right)^{-1} = \exp\left(\sum_{i \ge 1}\frac{z^i}{ip^{si}}\right) = \exp\left(O_{\varepsilon}(|z|p^{-s})\right) \] and so the product in~\eqref{def:Fsz} is a uniform limit of power series in $z$ which are smooth in $s$. \end{proof} For $s>1$ and $|z|<2$ we define \begin{align*} G(s,z) \coloneqq F(s,z) (s-1)^z. \end{align*} The following lemma extends the range of definition of $G$. For any $y \ge 1$ denote by $y_1$ the smallest prime greater than $y$. \begin{lemma} For every prime $q$, $\prod_{p \le q}(1-z/p^s)G(s,z)$, as well as its derivatives in $s$, are smooth in $s \ge 1$ and have a power series expansion in $z$ with radius $q_1$. Moreover, for $s \ge 1$ and $k \ge 0$, the $k$th derivative of $G(s,z)$ with respect to $s$ has a meromorphic continuation to $z \in \CC$ with poles of order $k$ at $z=p^s$ for every prime $p$. This continuation satisfies \[ G(1,z) = \prod_{p} \left(1-\frac{z}{p}\right)^{-1} \left(1- \frac{1}{p}\right)^z. \] \end{lemma} \begin{proof} We write $G$ as \begin{equation}\label{eq:GF} G(s,z) = F(s,z) \zeta(s)^{-z} (\zeta(s)(s-1))^z . \end{equation} It is well known that $\lim_{s \to 1^+}\zeta(s)(s-1)=1$, and that extending $\zeta(s)(s-1)$ to $s=1$, by setting it to equal $1$ there, it is a smooth function in $s \ge 1$.\footnote{Throughout we identify $\zeta(s)(s-1)$ at $s=1$ with $1$. A function $f$ is smooth on $[1,\infty)$ if it belongs to $\bigcap_{k=0}^{\infty}C^k([1,\infty))$ where for $k \ge 1$, $C^k([1,\infty))\coloneqq \{ f\colon [1,\infty) \to \mathbb{R}, f \text{ is differentiable}, f' \in C^{k-1}([1,\infty))\}$ and differentiability at $1$ is defined via the right derivative. For $k=0$, $C^0([1,\infty))$ consists of continuous functions on $[1,\infty)$, with continuity at $1$ defined by right-continuity.} Hence, $(\zeta(s)(s-1))^z=\exp(z \log (\zeta(s)(s-1))$ is smooth in $s \ge 1$ and has a power series representation in $z$ with infinite radius of convergence: \begin{equation}\label{eq:inf} (\zeta(s)(s-1))^z = \sum_{i \ge 0} \frac{z^i}{i!}(\log (\zeta(s)(s-1)))^i. \end{equation} At $s=1$,~\eqref{eq:inf} is equal to $1$. It remains to consider $F(s,z)\zeta(s)^{-z}$. It has the following Euler product: \begin{equation}\label{eq:FE} F(s,z)\zeta(s)^{-z} = \prod_{p} \left( 1-\frac{z}{p^s}\right)^{-1} \left(1-\frac{1}{p^s}\right)^z. \end{equation} For every prime $q$, we can use the product in~\eqref{eq:FE} to define $F(s,z)\zeta(s)^{-z}$ as a product of the rational function $\prod_{p \le q}(1-z/p^s)^{-1}$ (which has simple poles in $z$ at $z=p^s$ for every prime $p \le q$, and is defined for $s\ge 1$) with a function that has a power series representation in $z$ with radius of convergence $q_1$ and is defined for $s \ge 1$. This is because if $|z| < q_1^{1-\varepsilon}$ and $p>q$ then the $p$th term in the right-hand side of~\eqref{eq:FE} equals \[ \exp\left( \sum_{i=2}^{\infty} \frac{z^i-z}{ip^{si}}\right) = \exp \left(O_{\varepsilon}\left((|z|^2+|z|)p^{-2 s}\right)\right), \] and the product over $p>q$ converges absolutely and uniformly. \end{proof} We also introduce \begin{align}\label{def:Fszy} F_y(s,z) \coloneqq \sum_{\substack{n \ge 1\\ p\mid n\to p> y}} \frac{z^{\Omega(n)}}{n^s} = \prod_{p >y} \left(1-\frac{z}{p^s}\right)^{-1} = \ \prod_{p \le y} \left(1-\frac{z}{p^s}\right)\,F(s,z), \end{align} and \begin{equation}\label{def:Gszy} \begin{split} G_y(s,z) {}\coloneqq{}& \prod_{p \le y} \left(1-\frac{z}{p^s}\right)\,G(s,z) \\ {}={}& \prod_{p\le y}\Big(1-\frac{1}{p^s}\Big)^{z}\prod_{p>y} \Big(1-\frac{z}{p^s}\Big)^{-1}\Big(1-\frac{1}{p^s}\Big)^{z}(\zeta(s)(s-1))^z. \end{split} \end{equation} For any smooth function $H(s,z)$, we shall denote by $H^{(a,b)}$ the mixed partial derivative \[ H^{(a,b)} =\frac{\partial^{a+b}}{\partial s^a \partial z^b} H. \] For every $j \ge 0$ and fixed $s\ge 1$, $G^{(j,0)}_y(s,z)$ has a meromorphic continuation to $\CC$ with poles at $z=p^s$ for every prime $p>y$ by Lemma~\ref{lem:cont}. Taking the logarithmic derivative of~\eqref{def:Gszy} with respect to $s$ gives \begin{align*} \frac{G_y^{(1,0)}}{G_y}(s,z)&=\frac{\partial}{\partial s}\big[\log G_y(s,z)\big] \\ &=\frac{\partial}{\partial s} \left[\sum_{p\le y}z\log\left(1-\frac{1}{p^s}\right) %\right.\\\left. +\sum_{p\ge y_1}\left(z\log\left(1-\frac{1}{p^s}\right)- \log\left(1-\frac{z}{p^s}\right)\right) + z\log \big(\zeta(s)(s-1)\big)\right] \end{align*} so that \begin{lemma} We have \begin{align}\label{eq:dlogGy} G_y^{(1,0)}(s,z)& = z G_y(s,z)\left(\sum_{p \le y}\frac{\log p}{p^s-1} -\sum_{p\ge y_1}\frac{(z-1)\log p}{(p^s-1)(p^s-z)} + (\log (\zeta(s)(s-1)))'\right). \end{align} \end{lemma} \begin{remark} These generating functions and their values have natural connections to related questions about $k$-almost primes~\cite{BKL,Ldissect}. In particular $G_2(1,2)=\tfrac{1}{4}\prod_{p>2}(1-\tfrac{2}{p})^{-1}(1-\tfrac{1}{p})^2 = d$ as in~\eqref{def:d} equals $2\beta_2$, from the main term of~\cite[Theorem~1.2]{BKL}. \end{remark} \subsection{Proof of Theorem~\ref{thm:fkck22k}}\label{sec:proof} Let $y \ge 1$, and let $y_1$ be the smallest prime greater than $y$. We have the integral representation \begin{equation}\label{eq:intrep} f_{k,y}=\sum_{\substack{\Omega(n)=k\\ p\mid n\to p> y}} \frac{1}{n \log n}=\int_{1}^{\infty} \sum_{\substack{\Omega(n)=k\\p\mid n\to p> y}} n^{-s}\, \dd s. \end{equation} The smallest number $n$ with $\Omega(n) = k$ and all prime factors greater than $y$ is $y_1^k$, so the contribution of $s \ge 2$ to~\eqref{eq:intrep} is \[ \int_{2}^{\infty} \sum_{\substack{\Omega(n)=k\\ p\mid n\to p> y} }n^{-s}\, \dd s = \sum_{\substack{\Omega(n)=k\\ p\mid n\to p> y}} \frac{1}{n^{2}\log n} \le \sum_{n \ge y_1^k} \frac{1}{n^{2}\log n} \ll \frac{1}{k} \int_{y_1^k - 1}^{\infty} \frac{\dd t}{t^{2}} \ll \frac{1}{k y_1^k}. \] Thus we have \begin{equation}\label{eq:fkyiky} f_{k,y} = I_{k,y} + O\left(\frac{1}{k y_1^{k}}\right), \end{equation} where $I_{k,y}$ is the corresponding integral over $s\in[1,2]$, namely, \begin{equation}\label{def:Iky} I_{k,y} \coloneqq \int_{1}^{2} \sum_{\substack{\Omega(n)=k\\ p\mid n\to p> y}} n^{-s}\dd s =\int_{1}^{2}\frac{1}{k!} F_y^{(0,k)}(s,0)\dd s. \end{equation} Here we term-wise differentiated $F_y(s,z)$ in~\eqref{def:Fszy} with respect to $z$, for $s > 1$. Next from the Taylor series \begin{equation}\label{eq:s1z} (s-1)^{-z} = \exp\left(-z\log(s-1)\right) = \sum_{i \ge0} \frac{\left(-\log(s-1)\right)^i}{i!}z^i, \end{equation} we apply the product rule to $F_y(s,z)=(s-1)^{-z}\,G_y(s,z)$, giving \[ \frac{1}{k!}F_y^{(0,k)}(s,0) = \sum_{i=0}^k \frac{\left(-\log(s-1)\right)^{k-i}}{(k-i)!} \frac{1}{i!} G_y^{(0,i)}(s,0). \] Thus~\eqref{def:Iky} becomes \begin{equation}\label{eq:Ikintegral} I_{k,y} =\sum_{i=0}^{k} \int_{1}^{2} \frac{\left(-\log(s-1)\right)^{k-i}}{(k-i)!} \frac{1}{i!}G_y^{(0,i)}(s,0)\, \dd s. \end{equation} Now we introduce a similar integral $I'_{k,y}$, given by evaluating $G^{(0,i)}(s,0)$ in the integrand at $s=1$, namely, \begin{equation}\label{eq:Ik1integral} I'_{k,y} \coloneqq \sum_{i=0}^{k} \frac{1}{i!}G_y^{(0,i)}(1,0) \int_{1}^{2} \frac{\left(-\log(s-1)\right)^{k-i}}{(k-i)!}\, \dd s. \end{equation} To handle $I'_{k,y}$, we substitute $s=1+\expe^{-t}$ and obtain, for any $j\ge 0$, \begin{equation}\label{eq:gamma} \int_{1}^{2} \frac{\left(-\log(s-1)\right)^{j}}{j!}\dd s = \int_{0}^{\infty} \frac{\expe^{-t}t^{j}}{j!}\dd t = \frac{\Gamma(j+1)}{j!}=1, \end{equation} as we are evaluating the Gamma function at $j+1$. Hence~\eqref{eq:Ik1integral} simplifies as \begin{equation}\label{eq:Ik1simpler} I'_{k,y} = \sum_{i=0}^{k} \frac{1}{i!}G_y^{(0,i)}(1,0). \end{equation} In the upcoming subsections, we shall estimate $I_{k,y}$ by means of the following lemmas for $I'_{k,y}$ and $I_{k,y}-I'_{k,y}$. \begin{lemma}\label{lem:I1minus1y} Let $y \ge 1$. We have $I'_{k,y}= G_y(1,1) + O_y(y_1^{-k})$. \end{lemma} \begin{lemma}\label{lem:IminusI2y} Let $y \ge 2$. We have $I_{k,y}=I'_{k,y} + G_y^{(1,0)}(1,2)/2^{k+1}+ O_y(k^3/3^{k})$. \end{lemma} \begin{proof}[Proof of Theorem~\ref{thm:fkck22k} assuming Lemmas~\ref{lem:I1minus1y} and~\ref{lem:IminusI2y}] Recalling~\eqref{eq:fkyiky}, we have \begin{equation}\label{eq:fkyGy} \begin{split} f_{k,y} & = I_{k,y} + O(1/(k y_1^{k})) \\ & = I'_{k,y} + G_y^{(1,0)}(1,2)/2^{k+1}+ O_y(k^3/3^{k}) \\ & = G_y(1,1) + G_y^{(1,0)}(1,2)/2^{k+1}+ O_y(k^3/3^{k}) \end{split} \end{equation} for $y \ge 2$. To compute the constants above, we first note $G_y(1,1) = \prod_{p\le y}(1-1/p)$. Next, by~\eqref{def:Gszy} and~\eqref{eq:dlogGy} with $(s,z)=(1,2)$ we have \begin{equation}\label{eq:Gy10} \begin{split} G_y(1,2)&=\prod_{p \le y} \left(1-\frac{1}{p}\right)^2 \prod_{p \ge y_1} \left(1-\frac{2}{p}\right)^{-1} \left(1-\frac{1}{p}\right)^2 = d_y, \\ G_y^{(1,0)}(1,2) &=2G_y(1,2) \left(\sum_{p \le y}\frac{\log p}{p-1} -\sum_{p\ge y_1}\frac{\log p}{(p-1)(p-2)} + \gamma\right) = 2d_yc_y \end{split} \end{equation} for $y \ge 2$. Here we used $(\log (\zeta(s)(s-1)))'|_{s=1}=\gamma$. Hence plugging~\eqref{eq:Gy10} and $G_y(1,1) = \prod_{p\le y}(1-1/p)$ back into~\eqref{eq:fkyGy}, we conclude \begin{equation} f_{k,y} = \prod_{p \le y}\left(1-\frac{1}{p}\right) + c_yd_y/2^{k}+ O_y(k^3/3^{k}). \qedhere\end{equation} \end{proof} \subsection{Proof of Lemma~\ref{lem:I1minus1y}} We use the notation $[z^n]A(z)=\frac{1}{n!} \big(\frac{\dd^n}{\dd z^n}A\big)(0)$ to denote the coefficient of $z^n$ in $A$, where $A$ is a function with Taylor series representation at $z=0$. From the representation of $I'_{k,y}$ in~\eqref{eq:Ik1simpler}, we have for all $k \ge 1$, \[ I'_{k,y} =[z^k] \frac{G_y(1,z)}{1-z} = \frac{1}{2\pi i} \int_{|z|=1/2}\frac{G_y(1,z)}{1-z} \frac{\dd z}{z^{k+1}}, \] using Cauchy's integral formula. Here the integral ranges over a circle centered around $z=0$, oriented counterclockwise, with radius $1/2$. The function $G_y(1,z)$ has simple poles at $z=p$ for every prime $p>y$; these are its only poles. The rational function $1/(1-z)$ has a simple pole at $z=1$. So recalling the smallest prime $y_1>y$, the only poles of $G_y(1,z)/(1-z)$ in the range $1/2<|z|2R$, then \begin{align*} \left| \left(1-\frac{1}{p}\right)^z\left(1-\frac{z}{p}\right)^{-1} \right| = \left|\exp\left( \sum_{i \ge 2} \frac{z^i-z}{ip^i} \right)\right| \le \exp\left( \sum_{i \ge 2} \frac{|z|^i}{p^i} \right)\le \exp\left(\frac{2R^2}{p^2}\right). \end{align*} Hence, recalling~\eqref{def:Gszy} with $s=1$ we obtain \begin{align*} \max_{|z|=R}\left|G_y(1,z)\right| & = \max_{|z|=R} \left| \prod_{p\le y}\left(1-\frac{1}{p}\right)^{z}\prod_{p\ge y_1}\left(1-\frac{1}{p}\right)^z\left(1-\frac{z}{p}\right)^{-1}\right| \\ &\le \prod_{p \le y} \left(1-\frac{1}{p}\right)^{-R} \prod_{p > 2R} \exp\Big(\frac{2R^2}{p^2}\Big) \, \cdot\max_{|z|=R} \prod_{y_1\le p\le 2R} \left|\left(1-\frac{1}{p}\right)^z\left(1-\frac{z}{p}\right)^{-1}\right| \ \ll_y \ 1. \end{align*} This proves the claim, and hence Lemma~\ref{lem:I1minus1y} follows. \subsection{Proof of Lemma~\ref{lem:IminusI2y}} By Taylor expansion at $s=1$, we have uniformly for $s \in [1,2]$ \[ G_y^{(0,i)}(s,0) = G_y^{(0,i)}(1,0) + (s-1) b_{i} + O\big( (s-1)^{2} c_{i}\big), \] for coefficients \begin{equation}\label{eq:bici} b_{i} \coloneqq G_y^{(1,i)}(1,0)\qquad\text{and}\qquad c_{i} \coloneqq \max_{s'\in [1,2]} \left| G_y^{(2,i)}(s',0)\right|. \end{equation} Thus subtracting~\eqref{eq:Ikintegral} from~\eqref{eq:Ik1integral}, we have \begin{equation}\label{eq:IminusI1} \begin{split} I_{k,y}-I'_{k,y} &= \sum_{i=0}^{k} \int_{1}^{2} \frac{\left(-\log(s-1)\right)^{k-i}}{(k-i)!} \frac{1}{i!} \left( G_y^{(0,i)}(s,0) - G_y^{(0,i)}(1,0)\right) \dd s \\ & = \sum_{i=0}^{k} \int_0^1 \frac{\left(-\log s\right)^{k-i}}{(k-i)!i!} \left( sb_{i} + O( s^{2} c_{i})\right) \dd s. \end{split} \end{equation} Substituting $s=\expe^{-t}$ shows that \begin{equation}\label{eq:IminusI1bi} \begin{split} \sum_{i=0}^{k}\frac{b_{i}}{i!(k-i)!}\int_0^1 (-\log s)^{k-i}s\, \dd s &= \sum_{i=0}^{k}\frac{b_i}{i!(k-i)!}\int_{0}^{\infty} t^{k-i}\expe^{-2t}\, \dd t \\ &=\sum_{i=0}^{k}\frac{b_{i} 2^{i-k-1}}{i!(k-i)!} \int_{0}^{\infty} v^{k-i}\expe^{-v}\, \dd v \ = \ \sum_{i=0}^{k} \frac{b_{i}}{i!} 2^{i-k-1} \end{split} \end{equation} and similarly \begin{align}\label{eq:IminusI1ci} \sum_{i=0}^{k}\frac{c_{i}}{i!(k-i)!} \int_0^1(-\log s)^{k-i} s^2\, \dd s = \sum_{i=0}^{k} \frac{c_{i}}{i!}3^{i-k-1}. \end{align} Plugging~\eqref{eq:IminusI1bi} and~\eqref{eq:IminusI1ci} back into~\eqref{eq:IminusI1} gives \begin{align} I_{k,y}-I'_{k,y} &= \sum_{i=0}^{k}\left( \frac{b_{i}}{i!} 2^{i-k-1} + O\left(\frac{c_{i}}{i!}3^{i-k-1}\right)\right). \end{align} So proceeding as in the proof of Lemma~\ref{lem:I1minus1y} (as in~\eqref{eq:I1lem3.1}), by Cauchy's integral formula and residue theorem, \begin{equation}\label{eq:zkGy101z} \begin{split} \sum_{i=0}^{k} \frac{b_{i}}{i!} 2^{i-k-1} &= 2^{-1}[z^k] \frac{G_y^{(1,0)}(1,z)}{1-\frac{z}{2}} = \frac{1}{4\pi i} \int_{|z|=1/2} \frac{G_y^{(1,0)}(1,z)}{1-\frac{z}{2}} \frac{\dd z }{z^{k+1}} \\ &= \frac{1}{2\pi i} \int_{|z|=R} \frac{G_y^{(1,0)}(1,z)}{2-z} \frac{\dd z }{z^{k+1}} + G_y^{(1,0)}(1,2)2^{-k-1} - \frac{\lim_{z \to y_1} (z-y_1)\,G_y^{(1,0)}(1,z)}{(2-y_1)y_1^{k+1}} \\ &= G_y^{(1,0)}(1,2)2^{-k-1} + O_y(y_1^{-k}) \end{split} \end{equation} holds where $R\coloneqq y_1+1/2$. Finally, we claim $c_i \ll_y i! (i+1)^2/y_1^i$, in which case \[ \sum_{i=0}^{k} \frac{c_{i}}{i!}3^{i-k-1}\ll \sum_{i=0}^{k}y_1^{-i}(i+1)^2 3^{i-k-1} \ll \sum_{i=0}^{k}(i+1)^2\,3^{-k} \ll_y k^3/3^{k} \] since $y_1\ge 3$ (as $y\ge2$). Thus combined with~\eqref{eq:zkGy101z}, we conclude \begin{align} I_{k,y}-I'_{k,y} = G_y^{(1,0)}(1,2)/2^{k+1} + O_y(k^3/3^{k}). \end{align} Hence to complete the proof of Lemma~\ref{lem:IminusI2y}, it suffices to show $c_i \ll_y i! (i+1)^2/y_1^i$, which by definition means that uniformly for $s \in [1,2]$, \begin{align}\label{eq:cibound} [z^i] G_y^{(2,0)}(s,z) \ll_y (i+1)^2/y_1^i. \end{align} To this end, recall $G_y^{(1,0)}(s,z) = zG_y(s,z) c(s)$ by~\eqref{eq:dlogGy}, where \begin{align*} c(s)=c_y(s,z) \coloneqq \sum_{p \le y}\frac{\log p}{p^s-1} -\sum_{p\ge y_1}\frac{(z-1)\log p}{(p^s-1)(p^s-z)} + (\log (\zeta(s)(s-1)))'. \end{align*} So differentiating again with respect to $s$ we obtain \begin{equation}\label{eq:Gy20} \begin{split} G_y^{(2,0)}(s,z) &= zG_y^{(1,0)}(s,z)c(s) + zG_y(s,z)c'(s) \\ &=G_y(s,z) \big(z^2c(s)^2 + zc'(s)\big). \end{split} \end{equation} The derivative of $c$ with respect to $s$ is \begin{align*} c'(s) &= -\sum_{p \le y}\frac{ p^s (\log p)^2}{(p^s-1)^2} \ + \ \sum_{p\ge y_1}\frac{(z-1)(\log p)^2(2p^{2s}-(z+1)p^s)}{(p^s-1)^2(p^s-z)^2} \ + \ \big(\log (\zeta(s)(s-1))\big)''. \end{align*} For fixed $s \in [1,2]$, note $c$ and $c'$ are meromorphic functions on $\CC$, with poles located only at $z=p^s$ for each $p \ge y_1$. Thus \begin{align*} G_y(s,z) &=\left(1-\frac{z}{y_1^s}\right)^{-1} H_{y,1}(s,z),\\ z^2c(s)^2 + zc'(s) &= \left(1-\frac{z}{y_1^s}\right)^{-2} H_{y,2}(s,z), \end{align*} for functions $H_{y,1}, H_{y,2}$, whose smallest pole is at $z=y_2^s$ where $y_2$ is the smallest prime larger than~$y_1$. Letting $H_{y}\coloneqq H_{y,1}H_{y,2}$, we see~\eqref{eq:Gy20} becomes \begin{equation}\label{eq:Gy201} G_y^{(2,0)}(s,z) = \left(1-\frac{z}{y_1^s}\right)^{-3} H_{y}(s,z). \end{equation} Note $H_{y}$ has no poles inside $|z| \le y_2^{s-\varepsilon}$ so $\max_{s\in[1,2]}|H_{y}(s,z)| \ll_{y,\varepsilon} 1$ uniformly for $|z| \le y_2^{s-\varepsilon}$, as we take the maximum of the continuous function $|H_y(s,z)|$ over the compact set $\{(s,z): 1 \le s \le 2, \, |z| \le y_2^{s-\varepsilon}\}$. Thus by Cauchy's integral formula, \[ [z^i] H_{y}(s,z) = \frac{1}{2\pi i} \int_{|z|=y_2^{s-\varepsilon}} \frac{H_{y}(s,z)}{z^{i+1}}\dd z \ll y_2^{-i(s-\varepsilon)}\max_{|z|=y_2^{s-\varepsilon}}|H_y(s,z)| \ll_{y,\varepsilon} y_2^{-i(1-\varepsilon)} \] uniformly for $s \in [1,2]$. By the binomial theorem, \[ [z^i]\left(1-\frac{z}{y_1^{s}}\right)^{-3} = y_1^{-is} \binom{i+2}{2} \ll (i+1)^2/y_1^{i} \] uniformly for $s \in [1,2]$ and $i \ge 0$. Hence by the product rule, from~\eqref{eq:Gy201} we conclude \[ [z^i] G_y^{(2,0)}(s,z) =\sum_{i_1+i_2=i} [z^{i_1}]\left(1-\frac{z}{y_1^{s}}\right)^{-3} [z^{i_2}] H_y(s,z)\ll_y (i+1)^2/y_1^{i}. \] This gives~\eqref{eq:cibound} as desired, which completes the proof. \begin{remark} By a similar proof as of~\eqref{eq:cibound} above, for any $y\ge2$, $m\ge0$, \begin{align}\label{eq:cimbound} [z^i] G_y^{(m,0)}(s,z) \ll_{m,y} (i+1)^m/y_1^i \end{align} holds uniformly for $s \in [1,2]$ and $i \ge 0$. \end{remark} \section{Proof of Theorem~\ref{thm:fkthm}} Recall $f_k = f_{k,1}$, $F=F_1$ and $G=G_1$. By~\eqref{eq:fkyiky} with $y=1$, we have \[ f_k = I_k + O\left(\frac{1}{k2^k}\right) \] where \[ I_{k}= \int_{1}^{2}\frac{1}{k!} F^{(0,k)}(s,0)\dd s. \] We apply the product rule to \[ F(s,z)=(s-1)^{-z}G(s,z)=(s-1)^{-z} \left(1-\frac{z}{2^s}\right)^{-1}G_2(s,z), \] giving \begin{align*} \frac{1}{k!}F^{(0,k)}(s,0) = \sum_{i+j+l = k} \frac{\left(-\log(s-1)\right)^{l}}{l!}2^{-js} \frac{1}{i!} G_2^{(0,i)}(s,0), \end{align*} using the power series in~\eqref{eq:s1z}, as well as $\left(1-\frac{z}{2^{s}}\right)^{-1} = \sum_{j \ge 0} 2^{-js}z^j$. Thus we have \begin{equation}\label{eq:Ikintegral2} I_{k} =\sum_{i+j+l= k} \int_{1}^{2} \frac{\left(-\log(s-1)\right)^{l}}{l!}2^{-js} \frac{1}{i!} G_2^{(0,i)}(s,0)\, \dd s. \end{equation} Now we introduce a similar integral $I'_{k}$, given by evaluating $G_2^{(0,i)}(s,0)$ in the integrand at $s=1$, namely, \begin{align}\label{eq:Ik1integral2} I'_{k} &=\sum_{i+j+l= k} \int_{1}^{2} \frac{\left(-\log(s-1)\right)^{l}}{l!}2^{-js} \frac{1}{i!} G_2^{(0,i)}(1,0)\, \dd s. \end{align} Hence to establish Theorem~\ref{thm:fkthm}, it suffices to prove the following lemmas for $I'_k$ and $I_{k}-I'_{k}$. \begin{lemma}\label{lem:I1minus1} We have $I'_k = 1 - \frac{\log 2}{4}2^{-k} \big(dk^2 +O(k\log (k+1))\big)$. \end{lemma} \begin{lemma}\label{lem:IminusI2} We have $I_{k}=I'_{k} + O(k/2^{k})$. \end{lemma} These are the $y=1$ analogues of Lemmas~\ref{lem:I1minus1y} and~\ref{lem:IminusI2y}. \subsection{Proof of Lemma~\ref{lem:IminusI2}} By the mean value theorem we have, uniformly for $s \in [1,2]$, \[ \Big|G_2^{(0,i)}(s,0) - G_2^{(0,i)}(1,0)\Big| \le (s-1)b_i \] for coefficients \begin{align*} b_{i} \coloneqq \max_{s'\in [1,2]} \Big| G_2^{(1,i)}(s',0) \Big|. \end{align*} Thus subtracting~\eqref{eq:Ikintegral2} from~\eqref{eq:Ik1integral2}, we find \begin{equation}\label{eq:IminusI12} \begin{split} \big| I_{k}-I'_{k} \big| &=\left| \sum_{i+j+l = k} \int_{1}^{2} \frac{\left(-\log(s-1)\right)^l}{l!}2^{-js} \frac{1}{i!} \left( G_2^{(0,i)}(s,0) - G_2^{(0,i)}(1,0)\right) \dd s \right| \\ & \le \sum_{i+j+l = k} \int_{1}^{2} \frac{\left(-\log(s-1)\right)^l}{l!}2^{-js} (s-1) \frac{b_i}{i!}\, \dd s. \end{split} \end{equation} By~\eqref{eq:cimbound}, we have uniformly for $t\in[1,2]$, \begin{align}\label{eq:bibound} \frac{1}{i!}G_2^{(1,i)}(t,0) = [z^i]G_2^{(1,0)}(t,z) \ll (i+1)3^{-i}. \end{align} Hence $\frac{b_i}{i!} \ll (i+1)3^{-i}$, so that~\eqref{eq:IminusI12} implies \begin{align*} I_k - I'_k &\ll \sum_{i+j+l= k} \int_{0}^{\infty} \frac{t^l}{l!} 2^{-j(1+\expe^{-t})} \expe^{-2t} (i+1) 3^{-i} \, \dd t\\ &\le \sum_{i+j+l= k} (i+1)3^{-i}2^{-j} \int_{0}^{\infty} \frac{t^l}{l!} \expe^{-2t} \, \dd t\\ & = \sum_{i+j+l= k} (i+1) 3^{-i} 2^{-j-l-1}\int_{0}^{\infty} \frac{u^l}{l!}\expe^{-u}\, \dd u \ = \ \sum_{i+j+l= k} (i+1) 3^{-i} 2^{-j-l-1} \end{align*} where the last equalities follow from substituting $u/2$ for $t$ and recalling the integral form~\eqref{eq:gamma} of the Gamma function. Hence we conclude \begin{align*} I_k - I'_k \ll \sum_{i\le k} (i+1) 3^{-i} 2^{i-k}\sum_{j\le k-i} 1 \le k2^{-k}\sum_{i\le k} (i+1) (2/3)^{i} \ll k2^{-k}. \end{align*} \subsection{Proof of Lemma~\ref{lem:I1minus1}} Recall \begin{align}\label{eq:ikprimerecall} I'_k&= \sum_{i=0}^{k}\frac{1}{i!} G_2^{(0,i)}(1,0) \sum_{j+l = k-i} \int_{1}^{2} \frac{\left(-\log(s-1)\right)^l}{l!}2^{-js} \, \dd s. \end{align} We will prove in the next subsection that \begin{lemma}\label{lem:tech} For $k \ge 1$, we have \begin{align*} \sum_{j+l=k} \int_{1}^{2} \frac{\left(-\log(s-1)\right)^l}{l!}2^{-sj} \, \dd s = 2 - \frac{\log 2}{4} 2^{-k}\Big(k^2+O\big((k+1)\log (k+2)\big)\Big). \end{align*} \end{lemma} \begin{remark} The relative saving is $k/\log k$ and it appears sharp. We find it to be an unusual saving. \end{remark} Using Lemma~\ref{lem:tech} we simplify the inner sum in~\eqref{eq:ikprimerecall} and find \begin{equation}\label{eq:Ik1B} \begin{split} I'_k &= \sum_{i=0}^{k}\frac{1}{i!} G_2^{(0,i)}(1,0) \left(2 - \frac{\log 2}{4} 2^{i-k}\Big((k-i)^2+O\big((k+1-i)\log (k+2-i)\big)\Big)\right) \\ &= 2I'_{k,2} - \frac{\log 2}{4}2^{-k} B \end{split} \end{equation} where \begin{align} I'_{k,2} &\coloneqq \sum_{i=0}^{k} \frac{1}{i!}G_2^{(0,i)}(1,0),\\ \label{eq:B}B&\coloneqq \sum_{i=0}^{k} \frac{2^{i}}{i!}\Big((k-i)^2+ O\big((k-i+1)\log(k-i+2)\big)\Big) G_2^{(0,i)}(1,0). \end{align} Lemma~\ref{lem:I1minus1y} with $y=2$ yields \[ I'_{k,2} =G_2(1,1)+O(3^{-k}) = \tfrac{1}{2} + O(3^{-k}). \] Similarly as in the proof of Lemma~\ref{lem:I1minus1y}, Cauchy's integral formula and residue theorem imply \begin{equation}\label{eq:B1} \begin{split} B' {}\coloneqq{}& \sum_{i=0}^{k}\frac{2^i}{i!} G_2^{(0,i)}(1,0) =[z^k] \frac{G_2(1,2z)}{1-z} \\ {}={}& \frac{1}{2\pi i} \int_{|z|=1/4} \frac{G_2(1,2z)}{1-z} \frac{\dd z }{z^{k+1}} \\ {}={}&\frac{1}{2\pi i} \int_{|z|=2} \frac{G_2(1,2z)}{1-z} \frac{\dd z }{z^{k+1}} + G_2(1,2) -\frac{\lim_{z \to 3/2} (z-3/2)\,G_y(1,2z)}{(1-3/2)(3/2)^{k+1}} \\ {}={}& d + O((3/2)^{-k}). \end{split} \end{equation} Here $G_2(1,2)=\tfrac{1}{4}\prod_{p>2}(1-\tfrac{2}{p})^{-1}(1-\tfrac{1}{p})^2 = d$. We also note $G_2(1,z)$ is meromorphic in $|z|<4$ with simple pole at $z=3$ (so $z=3/2$ is the smallest pole of $G_2(1,2z)$). In particular, \begin{align}\label{eq:ziG21z} \frac{1}{i!} G_2^{(0,i)}(1,0) = [z^i]G_2(1,z) \ll 3^{-i}. \end{align} Thus combining~\eqref{eq:B},~\eqref{eq:B1} and~\eqref{eq:ziG21z}, we obtain \begin{align*} B-k^2 B'&= \sum_{i=0}^{k} \frac{2^i}{i!} G_2^{(0,i)}(1,0) ((k-i)^2+O((k-i+1)\log(k-i+2))-k^2) \\ & \ll \sum_{i=0}^{ k} (2/3)^i (ik+O(k\log (k+1)))\ll k\log (k+1). \end{align*} Hence $B = dk^2 + O(k\log (k+1))$, so plugging back into~\eqref{eq:Ik1B} we conclude \begin{align} I'_k&= 1 - \frac{\log 2}{4}2^{-k} \big(dk^2 + O(k\log (k+1))\big). \end{align} \subsection{Proof of Lemma~\ref{lem:tech}} We may suppose $k \ge 2$. Multiplying through by $2^k$, we aim to prove \begin{align}\label{eq:Aklem} A_k = 2^{k+1}-\frac{\log 2}{4} k^2 + O(k\log k), \end{align} for \[ A_k \coloneqq 2^k\sum_{i+j=k} \int_{1}^{2} \frac{\left(-\log(s-1)\right)^{i}}{i!}2^{-js}\dd s = \sum_{i=0}^{k} \frac{2^i}{i!}J(i) \] where, substituting $s=1+\expe^{-u}$, \begin{align*} J(i) & \coloneqq \int_{1}^{2} \left(-\log(s-1)\right)^{i}2^{-(k-i)(s-1)}\dd s = \int_{0}^{\infty} u^i \expe^{-u} 2^{-(k-i)\expe^{-u}}\dd u. \end{align*} Note the trivial bound $J(i)\le i!$, using $2^{-(k-i)\expe^{-u}}\le 1$. In order to conclude~\eqref{eq:Aklem}, it suffices to prove the following two estimates and apply them with $T = 15\log k$: \begin{align} \sum_{0 \le i \le T} \frac{2^i}{i!}J(i) &= \sum_{0\le i\le T} 2^i + O(kT) &&\text{for} \quad k \ge T \ge \log k, \label{eq:smalli}\\ \sum_{T 2ea$, we have \begin{equation}\label{eq:smallu} \int_{0}^{ai} u^i \expe^{-u} 2^{-(k-i)\expe^{-u}}\dd u \ll_a i! 2^{-i}. \end{equation} For concreteness, we fix $a=0.21$. Now let $c\coloneqq a/3$. For $T1$. Consider the set of positive integers without prime factors smaller than $y$, and partition it according to the smallest prime factor $q\ge y$. This gives the disjoint union, \begin{align*} \big\{b\in\N : P^+(b)\ge y\big\} \ = \ \bigcup_{q\ge y}\big\{bq\in\N : P^-(b) \ge q\big\}. \end{align*} Taking the density of both sides, we find that \begin{align}\label{eq:iddensity} \prod_{p1}$, we have \begin{align} \sum_{q\ge P_1(a)^{\frac{1}{v}}}\dd({\Lrm }_{aq}) = v\,\dd({\Lrm }_a)\left(1+O\left( \tfrac{1}{\log P_1(a)}\right)\right). \end{align} \end{lemma}\begin{proof} Take $01$, we have \begin{align*} \sum_{\substack{\Omega(n)=k\\P_1(n)<\expe^y}}\frac{1}{n} \ \ll \ y^2 \,k/2^{k}. \end{align*} \end{lemma} \begin{proof} Observe that $2^k$ times our given sum is bounded by the following Euler product, \begin{align*} \sum_{\substack{\Omega(n)=k\\P_1(n)<\expe^y}}\frac{2^k}{n} & \le \prod_{p<\expe^y}\left(1 + \frac{2}{p}+\cdots+\frac{2^k}{p^k}\right)\\ & \le (k+1)\prod_{21$, we have \begin{align*} \sum_{\substack{\Omega(n)=k\\P_{j+1}(n)<\expe^{y}}} \frac{1}{n \log n} \ll \sum_{\substack{\Omega(n)=k\\P_{j+1}(n)<\expe^{y}}}\dd({\Lrm }_n) \ll y^2\, k\,2^{j-k}. \end{align*} \end{corollary} \begin{proof} First, for each $n$ with $\Omega(n)=k$, one can factor $n$ uniquely as $ab$ with $\Omega(b)=j$ and $p(b)\ge P_1(a)$ (namely take $b= \prod_{i=1}^{j}P_i(n)$ and $a=n/b$). Thus by~\eqref{eq:dLareduce} we have \begin{align*} \sum_{\substack{\Omega(n)=k\\P_{j+1}(n)<\expe^{y}}}\dd({\Lrm }_n) = \sum_{\substack{\Omega(a)=k-j\\P_1(a)<\expe^{y}}} \sum_{\substack{\Omega(b)=j\\p(b)\ge P_1(a)}}\dd({\Lrm }_{ab})= \sum_{\substack{\Omega(a)=k-j\\P_1(a)<\expe^{y}}}\dd({\Lrm }_a). \end{align*} On the right-hand side of the above identity we apply the simple bound $\dd({\Lrm }_a) \ll 1/a$, and on the left-hand side we apply $\dd({\Lrm }_n) \gg 1/(n \log n)$. This gives \begin{align*} \sum_{\substack{\Omega(n)=k\\P_{j+1}(n)<\expe^{y}}} \frac{1}{n \log n}\ll \sum_{\substack{\Omega(n)=k\\P_{j+1}(n)<\expe^{y}}}\dd({\Lrm }_n) \ll \sum_{\substack{\Omega(a)=k-j\\P_1(a)<\expe^{y}}}\frac{1}{a} \ll y^2\, k\,2^{j-k} \end{align*} by Lemma~\ref{lem:ErdSark} with $k$ replaced by $k-j$. \end{proof} \subsection{Proof of Proposition~\ref{prop:fkprob}} Let $k\ge1$ be sufficiently large. We shall choose $y=2^j$ for $j=\lfloor k/4\rfloor$, and $N=4^k$. Let $f'_k$ denote the sum $f_k$ restricted by $P_{j+1}(n)\ge \expe^{y}$. Thus by Corollary~\ref{cor:ksmooth}, \begin{align}\label{eq:fkfk1} f_k=\sum_{\Omega(n)=k}\frac{1}{n\log n} = f_k' + O(y^2 k 2^{j-k}) = f_k' + O(k/2^{k/4}) \end{align} where, by Mertens' product theorem, \begin{align} \label{eq:fk1uj0} f_k' &\coloneqq \sum_{\substack{\Omega(n)=k\\P_{j+1}(n)\ge \expe^{y}}}\frac{1}{n\log n} = \sum_{\substack{\Omega(n)=k\\P_{j+1}(n)\ge \expe^{y}}}\left(\expe^\gamma + \tfrac{O(1)}{\log P_1(n)}\right)\frac{\log P_1(n)}{\log n}\dd({\Lrm }_n). \end{align} Next, we rewrite the identity $n=P_1(n)\cdots P_k(n)$ as \begin{align*} \frac{\log n}{\log P_1(n)} &= 1 + \frac{\log P_2(n)}{\log P_1(n)}\left(1+\cdots\left(1+\frac{\log P_{j+1}(n)}{\log P_j(n)} \left(1+\frac{\log\big(P_{j+2}(n)\cdots P_k(n)\big)}{\log P_{j+1}(n)}\right)\right)\cdots\right). \end{align*} Taking the reciprocal of identity above gives \begin{align*} \frac{\log P_1(n)}{\log n} & = u_{j+1}\left(\tfrac{\log P_2(n)}{\log P_1(n)},\ldots,\tfrac{\log P_{j+1}(n)}{\log P_j(n)},\tfrac{\log(P_{j+2}(n)\cdots P_k(n))}{\log P_{j+1}(n)}\right), \end{align*} for the functions $u_j \colon \R^j\to\R$ given by \begin{align}\label{eq:ukdef} u_j(x_1,\ldots,x_j) \coloneqq \frac{1}{1+x_1(1+x_2(\cdots(1+x_j)\cdots))}. \end{align} In particular, from $P_1(n)\ge\cdots \ge P_k(n)$ we infer the inequalities \begin{align} \frac{\log P_1(n)}{\log n} & \le u_j\left(\frac{\log P_2(n)}{\log P_1(n)},\ldots,\frac{\log P_{j+1}(n)}{\log P_j(n)}\right), \label{eq:ujupper}\\ \frac{\log P_1(n)}{\log n} & \ge u_j\left(\frac{\log P_2(n)}{\log P_1(n)},\ldots,\frac{\log P_{j+1}(n)}{\log P_j(n)}(k-j)\right). \label{eq:lowerupper} \end{align} By~\eqref{eq:ujupper}, we see~\eqref{eq:fk1uj0} implies that \begin{align} \label{eq:fk1uj} f_k' \le \sum_{\substack{\Omega(a)=k-j\\P_1(a)\ge \expe^{y}}}\left(\expe^\gamma + \tfrac{O(1)}{\log P_1(a)}\right)\sum_{P_1(a) \le p_j\le \cdots\le p_1} u_j\left(\tfrac{\log p_2}{\log p_1},\ldots,\tfrac{\log P_1(a)}{\log p_j}\right)\dd ({\Lrm }_{ap_j\cdots p_1}). \end{align} \begin{lemma}\label{lem:inductmonotone} There is an absolute constant $C>1$ such that for any $a\in \Z_{>1}$, \begin{multline*} \sum_{P_1(a) \le p_j\le \cdots\le p_1} u_j\left(\tfrac{\log p_2}{\log p_1},\ldots,\tfrac{\log P_1(a)}{\log p_j}\right)\dd ({\Lrm }_{ap_j\cdots p_1}) \\ \le \frac{\left(1 + \tfrac{C}{\log P_1(a)}\right)^j}{N^j}\sum_{i_1,\ldots, i_j =1}^N u_j\left(\tfrac{i_1-1}{N},\ldots,\tfrac{i_j-1}{N}\right)\dd({\Lrm }_{a}). \end{multline*} \end{lemma} \begin{proof} For each $1\le r\le j$, it suffices to show that \begin{multline}\label{eq:inductmono} N^{1-r}\sum_{i_1,\ldots i_{r-1}=1}^N\sum_{P_1(a) \le p_j\le \cdots \le p_{r+1}\le p_r} u_j\left(\tfrac{i_1-1}{N},\ldots,\tfrac{i_{r-1}-1}{N},\tfrac{\log p_{r+1}}{\log p_r},\ldots,\tfrac{\log P_1(a)}{\log p_j}\right) \dd({\Lrm }_{ap_j\cdots p_r}) \\ \le N^{-r} \sum_{i_1,\ldots,i_r=1}^N \sum_{P_1(a) \le p_j\le \cdots\le p_{r+1}} u_j\left(\tfrac{i_1-1}{N},\ldots,\tfrac{i_{r}-1}{N},\tfrac{\log p_{r+2}}{\log p_{r+1}},\ldots,\tfrac{\log P_1(a)}{\log p_j}\right) \dd({\Lrm }_{ap_j\cdots p_{r+1}}) \\ \times \left(1 + \tfrac{C}{\log P_1(a)}\right) \end{multline} holds. Indeed, iterating~\eqref{eq:inductmono} (with each $r=1,2,\ldots, j$ in turn) completes the proof of the lemma. To show that~\eqref{eq:inductmono} holds, fix indices $i_1,\ldots i_{r-1}\le N$ and primes $p_j\le \cdots\le p_{r+1}$ ($p_j \ge P_1(a)$). Define $c_{i_r}$ and $d_{i_r}$ by \begin{align*} c_{i_r} &\coloneqq u_j\left(\tfrac{i_1-1}{N},\ldots,\tfrac{i_{r}-1}{N},\tfrac{\log p_{r+2}}{\log p_{r+1}},\ldots,\tfrac{\log P_1(a)}{\log p_j}\right)\\ d_{i_r} &\coloneqq \sum_{p_r\in [p_{r+1}^{N/i_r}, p_{r+1}^{N/(i_r-1)})}\, \dd({\Lrm }_{ap_j\cdots p_r}). \end{align*} (For $i_r=1$, the range of $p_r$ in the definition of $d_{i_r}$ is to be interpreted as $[p_{r+1}^{N},\infty)$.) Note for any $u\le N$, by Lemma~\ref{lem:vdLn} we have \begin{align*} \sum_{i_r=1}^u d_{i_r} = \sum_{p_r \ge p_{r+1}^{N/u}}\dd({\Lrm }_{ap_j\cdots p_r}) \le \frac{u}{N}\dd({\Lrm }_{ap_j\cdots p_{r+1}})\left(1 + \tfrac{C}{\log P_1(a)}\right) \eqqcolon D_u. \end{align*} In particular $D_{u}-D_{u-1} = \frac{1}{N}\, \dd({\Lrm }_{ap_j\cdots p_{r+1}})(1+C/\log P_1(a))$. Splitting up the sum over $p_r\ge p_{r+1}$ below according to the $i_r$ for which $p_r\in \big[p_{r+1}^{N/i_r}, p_{r+1}^{N/(i_{r}-1)}\big)$ holds, and then applying Lemma~\ref{lem:mass}, we find that \begin{equation}\label{eq:inductmonotone} \begin{split} \sum_{p_r\ge p_{r+1}} & u_j\left(\tfrac{i_1-1}{N},\ldots,\tfrac{i_{r-1}-1}{N},\tfrac{\log p_{r+1}}{\log p_r},\ldots,\tfrac{\log P_1(a)}{\log p_j}\right)\, \dd({\Lrm }_{ap_j\cdots p_r}) \\ & \le \sum_{i_r=1}^Nc_{i_r}\sum_{p_r\in [p_{r+1}^{N/i_r}, p_{r+1}^{N/(i_{r}-1)})} \dd({\Lrm }_{ap_j\cdots p_r}) = \sum_{i_r=1}^N c_{i_r}d_{i_r} \\ &\le \sum_{i_r=1}^N c_{i_r}(D_{i_r}-D_{i_r-1}) = \left(1 + \tfrac{C}{\log P_1(a)}\right)\frac{1}{N}\sum_{i_r=1}^N c_{i_r}\dd({\Lrm }_{ap_j\cdots p_{r+1}}) \\ & = \left(1 + \tfrac{C}{\log P_1(a)}\right)\frac{1}{N}\sum_{i_r=1}^N u_j\left(\tfrac{i_1-1}{N},\ldots,\tfrac{i_{r}-1}{N},\tfrac{\log p_{r+2}}{\log p_{r+1}},\ldots,\tfrac{\log P_1(a)}{\log p_j}\right)\, \dd({\Lrm }_{ap_j\cdots p_{r+1}}). \end{split} \end{equation} Summing~\eqref{eq:inductmonotone} over $i_1,\ldots, i_{r-1}\le N$ and $p_j\le \cdots\le p_{r+1}$, we obtain~\eqref{eq:inductmono} as desired. \end{proof} Plugging Lemma~\ref{lem:inductmonotone} into~\eqref{eq:fk1uj} we obtain that \begin{align} f_k' &\le \expe^\gamma\sum_{\substack{\Omega(a)=k-j\\P_1(a)\ge \expe^{y}}}\dd({\Lrm }_{a})\,\frac{\big(1 + C/y\big)^{j+1}}{N^j}\sum_{i_1,\ldots, i_j =1}^N u_j\left(\tfrac{i_1-1}{N},\ldots,\tfrac{i_j-1}{N}\right) \end{align} holds. By Corollary~\ref{cor:ksmooth} and~\eqref{eq:dLareduce} with $a=1$, \begin{align*} \sum_{\substack{\Omega(a)=k-j\\P_1(a)\ge \expe^{y}}}\dd({\Lrm }_a) = \sum_{\substack{\Omega(a)=k-j}}\dd({\Lrm }_a) + O(y^2 k 2^{j-k}) = 1 +O(k/2^{k/4}), \end{align*} recalling the definitions $y=2^j$, $j=\lfloor k/4\rfloor$. Thus \begin{align}\label{eq:f1kleIj0} f_k' &\le \expe^\gamma\,\frac{\big(1 + O(k/2^{k/4})\big)^{j+1}}{N^j}\sum_{i_1,\ldots, i_j =1}^N u_j\left(\tfrac{i_1-1}{N},\ldots,\tfrac{i_j-1}{N}\right). \end{align} By an analogous argument (using the lower bound in~\eqref{eq:lowerupper}, and $E_i = \frac{i}{N}\, \dd({\Lrm }_{p_2\cdots p_ja}) (1 - C/\log P_1(a))$ in Lemma~\ref{lem:mass} instead of $D_i$), we may obtain a similar lower bound \begin{align}\label{eq:f1kgeIj0} f_k' &\ge \expe^\gamma\frac{\big(1 - O(k/2^{k/4}))\big)^{j+2}}{N^j}\sum_{i_1,\ldots, i_j =1}^N u_j\left(\tfrac{i_1}{N},\ldots,\tfrac{i_j}{N}(k-j)\right). \end{align} Now for a sequence $(c_j)_j$, define the integral \begin{align}\label{eq:Ijcj} I_j(c_j) \coloneqq \int_{[0,1]^j} u_j(x_1,\ldots,x_{j-1},c_jx_j)\, \dd x_1\cdots \dd x_j. \end{align} Observe that the sum in~\eqref{eq:f1kleIj0} is the upper Riemann sum for the integral $I_j(1)$, noting that $u_j:[0,1]^j\to[0,1]$ is decreasing in each component. And since the upper and lower Riemann sums (which squeeze $I_j(1)$) overlap in $(N-1)^j$ points, their difference is $\ll (N^j - (N-1)^j) / N^j = 1-(1-1/N)^j \ll j/N$. In particular the sum in~\eqref{eq:f1kleIj0} equals $I_j(1) + O(j/N)$. Similarly~\eqref{eq:f1kleIj0} is the lower Riemann sum for $I_j(k-j)$. Thus we obtain \begin{align*} N^{-j}\sum_{i_1,\ldots, i_j =1}^N u_j\left(\tfrac{i_1-1}{N},\ldots,\tfrac{i_j-1}{N}\right) &= I_j(1) + O(j/N),\\ N^{-j}\sum_{i_1,\ldots, i_j =1}^N u_j\left(\tfrac{i_1}{N},\ldots,\tfrac{i_j}{N}(k-j)\right) &= I_j(k-j) + O(j/N). \end{align*} Recalling $N=4^k$ and $j=\lfloor k/4\rfloor$, we see that~\eqref{eq:f1kleIj0} and~\eqref{eq:f1kgeIj0} become \begin{align} f'_k &\le (\expe^{\gamma}+O(k/2^{k/4}))\,I_j(1), \label{eq:f1kleIj}\\ f'_k &\ge (\expe^{\gamma}-O(k/2^{k/4}))\, I_j(k-j).\label{eq:f1kgeIj} \end{align} In the next section, we shall establish the following quantitative result. \begin{theorem}\label{theo:problem1} Let $(c_j)_j$ be any nonnegative sequence. Then $I_j(c_j)$, as in~\eqref{eq:Ijcj}, satisfies \begin{align*} I_j(c_j) = \expe^{-\gamma} + O\left(2^{-j}\left(1 + c_j\right)\right). \end{align*} \end{theorem} \begin{remark} The qualitative result that $I_n(c_n)=\expe^{-\gamma}+o(1)$ may be established in the wider regime where $\limsup_{n \to \infty} \frac{1}{n} \log c_n < 1$ holds (see Lemma~\ref{lem:I_error} for more precise statement) but the bound above is sufficient for the purpose of this article. \end{remark} In particular, Theorem~\ref{theo:problem1} gives \begin{align*} I_j(1) &= \expe^{-\gamma}+O(2^{-j}),\\ I_j(k-j) &=\expe^{-\gamma}+O(k/2^{j}). \end{align*} Thus plugging into~\eqref{eq:f1kleIj} and~\eqref{eq:f1kgeIj} we obtain $f'_k= 1 +O(k/2^{k/4})$. Hence by~\eqref{eq:fkfk1} we conclude that \begin{align} f_k = f_k'+O(k/2^{k/4}) = 1 + O(k/2^{k/4}). \end{align} This completes the proof of Proposition~\ref{prop:fkprob}. \section{A sequence of integrals} In this section, we prove Theorem~\ref{theo:problem1}. This implies Theorem~\ref{thm:iteratedIk} for $I_j(1)$. Recalling $u_j$ in~\eqref{eq:ukdef}, we defined the following sequence of integrals, for a sequence $(c_j)_j$, \begin{align}\label{def:Incn} I_j = I_j(c_j) \coloneqq \int_{[0,1]^j} \frac{\dd x_1\, \dd x_2 \cdots \dd x_j}{1+x_1(1+x_2(\cdots(1+x_{j-1}(1+c_jx_j))\cdots))}. \end{align} This sequence of iterated integrals is closely related to the so-called Dickman--Goncharov distribution, the properties of which are well studied in the literature (see e.g.~\cite[Props.~2.1 and 2.4]{Molchanov},~\cite{Chamayou} and~\cite{PW2004}). Since we need small refinements of existing results, we will provide self-contained explanations for all the results below. Our approach will be based on techniques from random iterated functions/stochastic fixed-point equations. \subsection{Probabilistic setup} In the following, all random variables are assumed to live in a common reference probability space $(\Omega, \mathcal{F}, \mathbb{P})$. \begin{lemma}\label{lem:iteratedmap} Let $U, U_1, U_2, \dots$ be i.i.d. $\mathrm{Uniform}[0,1]$ random variables. Define \begin{align*} F_n(x) \coloneqq 1 + U_n x \qquad \forall x \in \R, \quad n \in \N, \end{align*} and consider the sequence of iterated random functions \begin{align}\label{eq:Sn} S_0(x)\coloneqq x, \qquad S_n(x) \coloneqq F_1 \circ F_2 \circ \dots \circ F_n(x) \qquad \forall n \in \N. \end{align} Then the following statements hold. \begin{enumerate}[label=(\roman*)] \item\label{lemma30_i} The random variable \begin{align}\label{eq:Sinfty} S_\infty \coloneqq \lim_{n \to \infty} S_n(1) = 1 + \sum_{j=1}^\infty \prod_{k=1}^j U_k \end{align} exists almost surely and satisfies $\mathbb{P}(1 \le S_\infty < \infty) = 1$. \item\label{lemma30_ii} Let $\theta \in (1, e)$. If $(V_n)_n$ is a sequence of random variables such that $\lim_{n \to \infty} \theta^{-n} |V_n| = 0$ almost surely, then \begin{align}\label{eq:S_conv} \lim_{n \to \infty} S_n(V_n) = S_\infty \qquad \text{almost surely}. \end{align} \end{enumerate} \end{lemma} \begin{remark} The composition of maps $S_n(x) \coloneqq F_1 \circ \cdots \circ F_n(x)$ in \Cref{lem:iteratedmap} may be identified with products of random matrices, i.e. \begin{align*} \begin{pmatrix} S_n(x) \\ 1\end{pmatrix} = \begin{pmatrix} U_1 & 1 \\ 0 & 1 \end{pmatrix} \cdots \begin{pmatrix} U_n & 1 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} x \\ 1 \end{pmatrix} \qquad \forall x \in \mathbb{R}, \quad n \in \mathbb{N}. \end{align*} \noindent We choose the current formulation because many results in this section have natural extensions to nonlinear random functions $F_n$ with similar assumptions on their Lipschitz constants. \end{remark} \begin{proof} By definition, \begin{align*} S_n(1) = 1 + \sum_{j=1}^n \prod_{k=1}^j U_k \end{align*} and it is immediate that $S_{n+1}(1) \ge S_n(1) \ge 1$ for all $n \in \N$. Therefore, the almost sure limit in~\eqref{eq:Sinfty} exists by monotone convergence and we have $\mathbb{P}(S_\infty \ge 1) = 1$. Moreover, \begin{align}\label{eq:ESinfty} \E[S_\infty] = 1 + \sum_{j=1}^\infty \E\left[\prod_{k=1}^j U_k\right] = 1 + \sum_{j=1}^\infty \E[U]^j =\sum_{j=0}^\infty 2^{-j} = 2 \end{align} which implies $\mathbb{P}(S_\infty < \infty) = 1$. Thus we have verified~\ref{lemma30_i}. Now suppose $\theta \in (1, e)$, and $(V_n)_n$ is a sequence of random variables such that $\theta^{-n} |V_n|$ converges almost surely to $0$ as $n \to \infty$. Since each of the functions $F_n$ is linear with Lipschitz constant $\|F_n\|_{\mathrm{Lip}} = U_n$, we have \begin{equation}\label{eq:uniformbd} \begin{split} |S_n(V_n) -S_n(1)| &= \left| F_1 \circ F_2 \circ \dots \circ F_n(V_n) - F_1 \circ F_2 \circ \dots \circ F_n(1)\right| \\ & = \left[\prod_{j=1}^n \|F_j\|_{\mathrm{Lip}}\right] |V_n-1| = \left[\prod_{j=1}^n U_n\right] |V_n-1| \\ & \le \exp\left(\sum_{j=1}^n \log U_j\right) (1 + |V_n|). \end{split} \end{equation} Since $\E[\log U_i] = \int_0^1 \log u\,\dd{u} = -1$, the strong law of large numbers gives \begin{align*} \frac{1}{n} \sum_{j=1}^n \log U_j \xrightarrow[n \to \infty]{a.s.} -1. \end{align*} In particular, if we choose $\varepsilon \in (0, 1 - \log \theta)$, then almost surely there exists some (random) $n_0 = n_0(\varepsilon) \in \N$ such that \begin{align*} \frac{1}{n} \sum_{j=1}^n \log U_j \le -1+\varepsilon \qquad \text{for all $n \ge n_0$.} \end{align*} Substituting this into~\eqref{eq:uniformbd}, we obtain \begin{align*} |S_n(V_n) -S_n(1)| & \le (\theta/\expe^{1-\varepsilon})^n \left[\theta^{-n} (1 + |V_n|)\right] = O\left(\theta^{-n} (1 + |V_n|)\right). \end{align*} The assumption on $V_n$ implies that $S_n(V_n)-S_n(1)$ converges to 0 almost surely. Since $S_n(1)$ converges to $S_\infty$ almost surely by~\ref{lemma30_i}, we conclude that~\ref{lemma30_ii} holds, i.e. $S_n(V_n)$ also converges to $S_\infty$ almost surely. \end{proof} \begin{corollary} For the integral $I_n$ as in~\eqref{def:Incn}, we have \begin{align*} I_n = \E\left[\frac{1}{S_{n-1}(1+c_n U_n )}\right]. \end{align*} In particular, for any sequence $(c_n)_n$ satisfying $0 \le c_n = o(\theta^n)$ for some $\theta \in (1, e)$, \begin{align*} \lim_{n \to \infty} I_n = \E[S_\infty^{-1}] \eqqcolon I_\infty. \end{align*} \end{corollary} \begin{proof} The probabilistic representation of the iterated integral $I_n$ follows immediately by construction. If we let $V_{n-1} \coloneqq 1+c_n U_n$, then $\theta^{-n} V_n$ converges to $0$ almost surely as $n \to \infty$, and by \Cref{lem:iteratedmap} we also obtain that $S_{n-1}(V_{n-1})$ converges almost surely to $S_\infty$. Since \begin{align*} \frac{1}{S_{n-1}(V_{n-1})} \le \frac{1}{S_{n-1}(1)} \le 1, \end{align*} we conclude by dominated convergence that \[ \lim_{n \to \infty} I_n=\lim_{n \to \infty} \E\left[\frac{1}{S_{n-1}(V_{n-1})}\right] = \E[S_\infty^{-1}].\qedhere \] \end{proof} The next step is a simple but crucial characterisation of the distribution of $S_\infty$. \begin{lemma}\label{lem:randrecursion} Let $U,X$ be two independent random variables such that $U \sim \mathrm{Uniform}[0, 1]$ and \begin{align}\label{eq:recursion} X \overset{(d)}{=} 1 + UX. \end{align} If\/ $\mathbb{P}(|X| < \infty) = 1$, then $X \overset{(d)}{=} S_\infty$. \end{lemma} \begin{remark}\label{rem:indep-probspace} \looseness-1 While \Cref{lem:randrecursion} is conveniently formulated in terms of random variables, the statement ultimately concerns the law of $X$ only and does not require the knowledge of the underlying probability space. For instance, the distributional equality~\eqref{eq:recursion} can be reformulated as \begin{align*} \mathbb{E}[g(X)] = \int_0^1 \mathbb{E}[g(1+uX)]\, \dd u \end{align*} for all suitable test functions $g$ (provided both sides are well defined), and the conclusion of the lemma says that we necessarily have $\mathbb{E}[g(X)] = \mathbb{E}[g(S_\infty)]$, or equivalently $\mathbb{P}(X \le x) = \mathbb{P}(S_\infty \le x)$ for any $x \in \mathbb{R}$. \end{remark} \begin{proof} Without loss of generality (by \Cref{rem:indep-probspace}), assume that $X$ is defined on the same probability space in \Cref{lem:iteratedmap} such that $X$ is independent of all the uniformly distributed random variables $U, U_1, U_2, U_3, \dots$; our goal is to verify the following two claims: \begin{enumerate}[label=(\arabic*)] \item The random variable $S_\infty \coloneqq \lim_{n \to \infty} S_n(1)$ satisfies the distributional equality~\eqref{eq:recursion}, i.e. $S_\infty \overset{(d)}{=} 1 + U S_\infty$. This is straightforward by a quick reordering of the underlying i.i.d. random variables/iterated maps. Indeed, \begin{align*} S_n(1) = F_1 \circ \dots \circ F_n(1) &\overset{(d)}{=} F_n \circ F_1 \circ F_2 \circ \dots \circ F_{n-1}(1)\\ & \overset{\phantom{(d)}}{=} 1 + U_n S_{n-1}(1) \xrightarrow[n \to \infty]{(d)} 1 + U S_\infty. \end{align*} \item If $X$ satisfies $\mathbb{P}(|X| < \infty)$ and~\eqref{eq:recursion}, then $X \overset{(d)}{=} S_\infty$. To establish this claim, observe that for any $n \in \N$ we have \begin{align*} X \overset{(d)}{=} F_1(X) \overset{(d)}{=} \cdots \overset{(d)}{=} F_1\circ F_2 \circ \dots \circ F_n (X) = S_n(X). \end{align*} Since $\mathbb{P}(|X| < \infty)$ and in particular $2^{-n} |X| \xrightarrow[n \to \infty]{a.s.} 0$, we apply \Cref{lem:iteratedmap} with $V_n=X$ and obtain $S_n(X) \xrightarrow[n \to \infty]{a.s.} S_\infty$. In other words, \begin{align*} X \overset{(d)}{=} S_\infty = 1 + \sum_{j =1}^{\infty} \prod_{k =1}^j U_k, \end{align*} which concludes the proof.\qedhere \end{enumerate} \end{proof} \subsection{Proof of \texorpdfstring{\Cref{theo:problem1}}{Theorem 28}} The recursive distributional equation~\eqref{eq:recursion} is a very convenient tool that helps us control the rate of convergence of $S_n(\cdot)$ and extract information about the statistical behaviour of $S_\infty$ at the same time. We first explain how to estimate the difference between $I_n(c_n)$ and its limit $I_\infty$. \begin{lemma}\label{lem:I_error} For any nonnegative sequence $(c_n)_n$, we have \begin{align} \label{eq:I_error} |I_n(c_n) - I_\infty| &\le 2^{1-n} + \E \left[\min\left(1, c_n \prod_{j \le n} U_j\right) \right] \ \le \ 2^{-n} (2+c_n). \end{align} \end{lemma} \begin{proof} Recall that $V_{n-1} \coloneqq 1+c_{n} U_{n}$ and \begin{align*} I_n(c_n) = \E\left[ \frac{1}{S_{n-1}(V_{n-1})}\right]. \end{align*} On the other hand, if we introduce a new random variable $T \overset{(d)}{=} S_\infty$ that is independent of all of the $U_j$'s, we see that \begin{align*} S_{n-1}(T) \overset{(d)}{=} S_\infty \qquad \text{and hence} \qquad I_\infty = \E[S_\infty^{-1}] = \E\left[\frac{1}{S_{n-1}(T)}\right] \end{align*} by the distributional fixed point equation~\eqref{eq:recursion}. Since $S_{n-1}(\cdot)$ is linear with Lipschitz constant $\|S_{n-1}\|_{\mathrm{Lip}} = \prod_{j \le n-1} U_j$, we have \begin{equation}\label{eq:IncnIinfty} \begin{split} |I_n(c_n) - I_\infty| &= \left|\E\left[\frac{1}{S_{n-1}(V_{n-1})} - \frac{1}{S_{n-1}(T)}\right]\right| \\ & \le \E\left[\frac{\|S_{n-1}\|_{\mathrm{Lip}}\left| V_{n-1} - T\right|}{S_{n-1}(V_{n-1}) S_{n-1}(T)}\right] \\ & \le \E\left[\frac{\|S_{n-1}\|_{\mathrm{Lip}}\left| T - 1\right|}{ S_{n-1}(T)}\right] + \E\left[\frac{\|S_{n-1}\|_{\mathrm{Lip}}\left| V_{n-1} - 1\right|}{S_{n-1}(V_{n-1})}\right]. \end{split} \end{equation} Since $\E[U_j]=1/2$, $\E[T]=\E[S_\infty]=2$ by~\eqref{eq:ESinfty} and $\mathbb{P}(T \ge 1) = \mathbb{P}(S_{n-1}(T) \ge 1) = \mathbb{P}(S_\infty \ge 1) = 1$, the first term on the right-hand side of~\eqref{eq:IncnIinfty} satisfies \begin{align*} \E\left[\frac{\|S_{n-1}\|_{\mathrm{Lip}}\left| T - 1\right|}{ S_{n-1}(T)}\right] & \le \E\left[\|S_{n-1}\|_{\mathrm{Lip}}\left| T - 1\right|\right] \\ & =\E\left[ \left(\prod_{j\le n-1} U_j\right)\left| T - 1\right|\right] = \E[T - 1]\prod_{j \le n-1}\E\left[ U_j\right] = 2^{1-n}. \end{align*} Next, observe that $V_{n-1}-1=c_nU_n$ and $S_{n-1}(x) \ge 1$ for any $x \ge 0$. This means \begin{align*} \frac{\|S_{n-1}\|_{\mathrm{Lip}}\left| V_{n-1} - 1\right|}{S_{n-1}(V_{n-1})} \le c_n\prod_{j \le n} U_j. \end{align*} On the other hand, $S_{n-1}(V_{n-1})\ge 1 + V_{n-1}\|S_{n-1}\|_{\mathrm{Lip}}\ge \|S_{n-1}\|_{\mathrm{Lip}}\left| V_{n-1} - 1\right|$, which leads to a slightly improved bound \begin{align*} \frac{\|S_{n-1}\|_{\mathrm{Lip}}\left| V_{n-1} - 1\right|}{S_{n-1}(V_{n-1})} \le \min\left(1, c_n\prod_{j \le n} U_j\right). \end{align*} Taking expectation both sides and plugging this back into~\eqref{eq:IncnIinfty} yields the first inequality in~\eqref{eq:I_error}, and the second inequality in~\eqref{eq:I_error} follows from $\E[c_n \prod_{j \le n} U_j] = 2^{-n} c_n$. \end{proof} It remains to show that the value of $I_\infty$ equals $\expe^{-\gamma}$. This will be achieved using the recursive distributional equation~\eqref{eq:recursion} with the help of Laplace transform $\phi(t) \coloneqq \E[\expe^{-tS_\infty}]$, which is intrinsically related to our problem because \begin{align}\label{eq:preLaplace} I_\infty = \E[S_\infty^{-1}] = \E \left[ \int_0^\infty \expe^{-t S_\infty}\dd t\right] = \int_0^\infty \phi(t) \,\dd t \end{align} by Fubini's theorem. Let us first highlight that: \begin{lemma} The Laplace transform $\phi(t) \coloneqq \E[\expe^{-tS_\infty}]$ satisfies \begin{align}\label{eq:ODE} t\expe^t \phi(t)= \int_0^t \phi(v) \,\dd v, \qquad t \ge 0. \end{align} In particular, \begin{align}\label{eq:preDickman} I_\infty = \lim_{t \to \infty} t \expe^t \phi(t). \end{align} \end{lemma} \begin{proof} From the recursive distribution equation~\eqref{eq:recursion}, we have \begin{align*} \phi(t) & \coloneqq \E[\expe^{-tS_\infty}] = \E[\expe^{-t(1+US_\infty)}]\\ & = \expe^{-t} \int_0^1 \E[\expe^{-tu S_\infty}] \, \dd u = \frac{\expe^{-t}}{t} \int_0^t \E[\expe^{-v S_\infty}] \, \dd v. \end{align*} Hence $t \expe^t \phi(t) = \int_0^t \phi(v)\dd v $, as claimed. In particular $\lim_{t \to \infty} t \expe^t \phi(t) = \int_0^\infty \phi(v)\, \dd v = I_\infty$. \end{proof} \begin{proof}[Proof of \Cref{theo:problem1}] Differentiating the equality~\eqref{eq:ODE} yields $t\expe^t\phi'(t)+(t\expe^t)'\phi(t)=\phi(t)$, which may be rewritten as \begin{align*} \frac{\phi'(t)}{\phi(t)} = \frac{1- (t\expe^t)'}{t\expe^t} = \frac{\expe^{-t} - 1}{t}-1. \end{align*} Since $\phi(0)=1$, we then obtain \begin{align*} \log \phi(x) & = \log \phi(x) - \log \phi(0) = \int_0^x \frac{\dd}{\dd u}\big[\log\phi(u)\big]\,\dd{u}= \int_0^x \frac{\phi'}{\phi}(u)\,\dd{u}\\ & = \int_0^x \left(\frac{\expe^{-u} - 1}{u}-1\right)\dd{u} = \int_0^x \left(\expe^{-u}-1\right)\frac{\dd u}{u}-x\\ & = \left[ (\expe^{-u} - 1) \log u \right]_0^x + \int_0^x \expe^{-u} \log u \,\dd u - x. \end{align*} From Euler's identity for $\gamma$~\cite[Equation~(2.2.8)]{Lagarias}, \begin{align*} \gamma = -\int_0^\infty \expe^{-u} \log u \,\dd u, \end{align*} we see as $x \to \infty$, \begin{align*} \log \phi(x) = - \log x - x - \gamma + o(1). \end{align*} Substituting this into~\eqref{eq:preDickman}, we obtain $I_\infty = \lim_{x \to \infty} x \expe^x \phi(x) = \expe^{-\gamma}$. Combining this with \Cref{lem:I_error}, we conclude that $I_n = \expe^{-\gamma} + O(2^{-n}(1+c_n))$. \end{proof} \section*{Acknowledgments} Collaboration for this paper stems in part from a problem session during the `50 Years of Number Theory and Random Matrix Theory Conference' at the Institute for Advanced Study (IAS) in Princeton. The authors would like to thank the conference organizers, as well as Paul Kinlaw and the anonymous referee for careful feedback. \section*{Declaration of interests} The authors do not work for, advise, own shares in, or receive funds from any organization that could benefit from this article, and have declared no affiliations other than their research organizations. \printbibliography \end{document}