\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}} \usepackage{algorithm} \usepackage{algorithmic} \DeclareMathOperator{\Li}{Li} \newcommand{\ith}{^{\text{th}}} \newcommand{\sk}{\sigma_{k}} \newcommand{\skp}{\sigma_{k+1}} \newcommand{\sj}{\sigma_{j}} \newcommand{\sjp}{\sigma_{j+1}} \newcommand{\al}{\alpha} \newcommand{\gm}{\gamma} \newcommand{\bt}{\beta} \newcommand{\dt}{\delta} \newcommand{\lb}{\lambda} \newcommand{\veps}{\varepsilon} \newcommand{\cp}{{\cal P}} \newcommand{\upon}[2]{\genfrac{}{}{0pt}{}{#1}{#2}} \newcommand{\Pplus}{P^{+}} \newcommand{\lgd}{\log_2} \newcommand{\thmin}{\theta_{\mathrm{min}}} \newcommand{\dsm}[1]{\mbox{$\displaystyle #1 $}} \newcommand{\qtx}[1]{\quad\text{#1}\quad} \newcommand{\N}{\mathbb{N}} \newcommand{\intf}[2]{\left[#1,\, #2\right]} \newcommand{\intfg}[2]{\left[#1,\, #2\right)} \newcommand{\intfd}[2]{\left(#1,\, #2\right]} \newcommand{\set}[1]{\left\{#1\right\}} \newcommand{\abs}[1]{\left\lvert #1 \right\rvert} \newcommand{\gseq}{$G$-sequence} \newcommand{\bigo}[1]{O\!\left(#1\right)} \newcommand{\pfrac}[2]{\left(\frac{#1}{#2}\right)} \newcommand{\intfrac}[2]{\left\lfloor\frac{#1}{#2}\right\rfloor} \newcommand{\thd}{\theta_d} \renewcommand{\le}{\leqslant} \renewcommand{\ge}{\geqslant} \renewcommand{\labelitemi}{{\sl(\roman{itemi})}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf On the Largest Product of Primes with \\ \vskip .11in Bounded Sum } \vskip 1cm \large Marc Del\'{e}glise and Jean-Louis Nicolas\\ Institut Camille Jordan\\ Universit\'{e} de Lyon, CNRS\\ F-69622 Villeurbanne Cedex \\ France \\ \href{mailto:m.h.deleglise@gmail.com}{\tt m.h.deleglise@gmail.com} \\ \href{mailto:jlnicolas@in2p3.fr}{\tt jlnicola@in2p3.fr} \\ \end{center} \begin{abstract} Let $h(n)$ denote the largest product of primes whose sum is $\le n$, and $g(n)$ denote the Landau function, which is the largest product of powers of primes whose sum is $\le n$. In this article, several properties of $h(n)$ are given and compared to similar properties of $g(n)$. Special attention is paid to the behavior of the largest prime factor of $h(n)$. \end{abstract} \section{Introduction} If $n \ge 2$ is an integer, let us define $h(n)$ as the greatest product of a family of primes $q_1 < q_2 < \cdots < q_j$ the sum of which does not exceed $n$. Let $\ell$ be the additive function such that $\ell(p^{\al}) = p^{\al}$ for $p$ prime and $\al \ge 1$. In other words, if the standard factorization of $M$ into primes is \dsm{M = q_1^{\al_1} q_2^{\al_2} \cdots q_j^{\al_j}} we have $\ell(M) = q_1^{\al_1} + q_2^{\al_2} + \cdots + q_j^{\al_j}$ and $\ell(1) = 0$. If $\mu$ denotes the M\"{o}bius function, $h(n)$ can also be defined by \begin{equation}\label{hdef2} h(n) = \max_{\upon{\ell(M) \le n}{ \mu(M) \ne 0}} M. \end{equation} Note that \begin{equation}\label{ellLeh} \ell(h(n)) \le n. \end{equation} Landau \cite{LAN2} introduced the function $g(n)$ as the maximal order of an element in the symmetric group $S_n$; he showed that \begin{equation}\label{landau} g(n) = \max_{\ell(M) \le n} M. \end{equation} Sequences $(h(n))_{n\ge 1}$ and $(g(n))_{n \ge 1}$ are sequences \seqnum{A159685} and \seqnum{A000793} in the OEIS ({\it On-line Encyclopedia of Integer Sequences}). From Eqs.~\eqref{hdef2} and \eqref{landau}, it follows that \begin{equation}\label{hLeg} h(n) \le g(n), \quad (n \ge 0). \end{equation} In \cite{DNS} we gave some properties of $h(n)$ and an algorithm to compute $h(n)$ for large values of $n$. In Section~\ref{section2} below, these properties of $h(n)$ are recalled and compared to similar properties of $g(n)$. We also explain how the algorithm given in \cite{DNS} can be adapted to calculate $h(n)$ for all $n$ up to $10^{10}$. In Section~\ref{section3}, we recall various results about the distribution of primes. Section~\ref{section4} is devoted to effective and asymptotic estimates for $\log h(n)$, $\omega(h(n))$ and the differences $\log g(n)-\log h(n)$ and $\omega(h(n))-\omega(g(n))$. The last section, Section~\ref{section6}, studies the largest prime factor $\Pplus(h(n))$ of $h(n)$. This study uses the same tool (the so-called \gseq s) introduced by Grantham \cite{GRA}, and developed in \cite{DNS} to estimate $\Pplus(g(n))$. The \gseq s are described in Section~\ref{section5}. The last result of the paper is a comparison between $\Pplus(h(n))$ and $\log h(n)$. \subsection{Notation} \begin{enumerate} \item $p$ denotes a generic prime. For $i \ge 1$, $p_i$ is the $i\ith$ prime. \item $\pi(x) = \sum_{p \le x} 1$ is the number of primes $\le x$. \item $\theta(x)$ is the Chebyshev function \begin{equation}\label{defthetapsi} \theta(x) = \sum_{p \le x} \log p. \end{equation} \item $\Theta$ is the least upper bound of the real parts of the zeros of the Riemann $\zeta$ function. Under the Riemann hypothesis $\Theta = 1/2$. \item $\log_2 x$ represents the iterated logarithm $\log\log x$. \item $\Li(x)$, the integral logarithm of $x$, is defined for $x > 1$ by \[ \Li(x) = \lim_{\veps \to 0^+}\ \int_{0}^{1-\veps} + \int_{1+\veps}^{x} \frac{d t}{\log t}\ = \gm + \log_2 x + \sum_{n=1}^{+\infty} \frac{(\log x)^n}{n \cdot n!}, \] where $\gm = 0.577\cdots$ is Euler's constant. \item For each integer $N > 1$, $\Pplus(N)$ is the largest prime factor of $N$ and $\omega(N)=\sum_{p \mid N} 1$ is the number of prime factors of $N$. \end{enumerate} \noindent Let us write $\sigma_0 = 0$, $N_0 = 1$, and, for $j \ge 1$, \begin{equation}\label{def:Nj} N_j = p_1 p_2 \cdots p_j \qtx{ and } \sigma_j = p_1 + p_2 + \cdots + p_j = \ell(N_j). \end{equation} For $n \ge 0$, let $k = k(n)$ denote the integer $k \ge 0$ such that \begin{equation}\label{def:k(n)} \sigma_{k} = p_1 + p_2 + \cdots + p_{k} \le n < p_1 + p_2 + \cdots + p_{k+1} = \sigma_{k+1}. \end{equation} \section{General properties of \texorpdfstring{$h(n)$}{h(n)}}\label{section2} \subsection{Theoretical properties of \texorpdfstring{$h(n)$}{h(n)}} In this section we recall the properties of $h(n)$ that we will use \cite{DNS}. First of all (cf.\ \cite[Prop 3.1]{DNS}) for each nonnegative integer $j$, \begin{equation}\label{hsj} h(\sigma_j) = N_j. \end{equation} \begin{proposition}\label{Nknotsobad} Let $n$ be a nonnegative integer and $k=k(n)$. Then \begin{equation}\label{boundhn} \log N_k = \theta(p_k) \le \log h(n) \le \theta(p_{k+1})= \log N_{k+1}. \end{equation} \end{proposition} \begin{proof} From the definition of $k(n)$ we have $\sk \le n < \skp$. Using Eq.~\eqref{hsj} and the fact that $h$ is nondecreasing, this gives $N_k \le h(n) \le N_{k+1}$. Taking logarithms, we get Eq.~\eqref{boundhn}. \end{proof} From Eq.~\eqref{boundhn} we have $h(n) \ge N_k$ and, since $h(n)$ is squarefree, \begin{equation}\label{PplusGepk} \Pplus(h(n)) \ge p_{k(n)}. \end{equation} We also have $h(n) = \prod_{p \mid h(n)} p \le \prod_{p \le \Pplus(h(n))} p$ and thus \begin{equation}\label{Pplustheta} \log h(n) \le \theta(\Pplus(h(n))). \end{equation} In \cite[(1.9)]{DNS}, for $n \ge 0$, $h_j(n)$ is defined for each integer $j$ satisfying $0 \le j \le k(n)$ by: \begin{equation}\label{hj} h_j(n)=\max_{\substack{\ell(M) \leq n\\\mu(M)\neq 0,\;\omega(M)=j}} M, \end{equation} where $\omega(M)$ is the number of prime factors of $M$. The result \cite[Theorem 6.1]{DNS} implies that, for each $n$, the sequence $(h_j(n))_{0 \le j \le k(n)}$ is increasing, and therefore, \begin{equation*} h(n) = h_{k(n)}(n). \end{equation*} This result that could appear quite obvious at first sight, is not so easy to prove. It depends strongly on the distribution of prime numbers. It has an obvious consequence (cf.\ \cite[corollary (6.1)]{DNS}): \begin{theorem}\label{theorem:omega} The number of prime factors of $h(n)$, $\omega(h(n))$ is given by \begin{equation}\label{omegaequalk} \omega(h(n)) = k(n), \end{equation} where $k(n)$ is defined in Eq.~\eqref{def:k(n)}. \end{theorem} \renewcommand{\labelenumi}{{\sl(\roman{enumi})}} \begin{theorem}\label{thm:known} Let $j$ be a nonnegative integer. \begin{enumerate} \item We have $h(\sjp-1) = h(\sjp-2) = N_{j+1}/2$. \item If $q \le p_{j+1}$ is a prime, then $h(\sjp-q) = N_{j+1}/q$. \item If $j \ge 1$ and if $a$ is an even number satisfying $4 \le a < p_{j+1}$, we have \begin{equation}\label{fsiga} h(\sjp-a) = h(\sjp-a-1). \end{equation} \item The number $h(n)$ is odd when $n=\sjp-1$ or $n=\sjp-2$. It is even for $\sigma_j \le n \le \sigma_{j+1}-3$. \item For $n \ge 1$ the inequality $h(n) \le 2h(n-1)$ holds. \item We have \[ \liminf_{n \to \infty} \frac{h(n)}{h(n-1)}=1 \qtx{ and } \limsup_{n \to \infty} \frac{h(n)}{h(n-1)}=2. \] \end{enumerate} \end{theorem} \begin{proof} \begin{enumerate} \item is from \cite[Proposition 5.3]{DNS}. \item follows from \cite[Eqs.~(8.13) and (8.6)]{DNS}. \item is \cite[Proposition 5.1]{DNS}. \item The first part is implied by ({\sl i}). Now assume that $\sj \le n \le \sjp-3$. From Theorem~\ref{theorem:omega} we know that $\omega(h(n))=j$. If $2$ does not divide $h(n)$ we would have \[ \ell(h(n)) \ge 3+5+\cdots+p_{j+1} = \sjp-2, \] in contradiction with the inequality \eqref{ellLeh}, which proves ({\sl iv}). \item First let us consider the case $h(n)$ even; we then have $\ell(h(n)/2) = \ell(h(n))-2 \le n-2$, so that, by Eq.~\eqref{hdef2}, $h(n-1) \ge h(n)/2$ holds. If $h(n)$ is odd, from ({\sl iv}), we have $n=\sjp-1$ or $n=\sjp-2$ for some $j \ge 1$ and, from ({\sl i}) and ({\sl ii}), $h(\sjp-1) = h(\sjp-2) = N_{j+1}/2$ and $h(\sjp-3) = N_{j+1}/3$, which completes the proof of (v). Note that $h(n)=2h(n-1)$ implies $h(n-1)$ odd and $h(n)$ even. From ({\sl iv}), this occurs if and only if $n=\sj$ for some $j$. \item From the fact that $h$ is nondecreasing we get $h(n)/h(n-1) \ge 1$ while Eq.~\eqref{fsiga} shows that $h(n)=h(n-1)$ for infinitely many $n$, which gives the value of the $\liminf$. From ({\sl v}) we have $h(n)/h(n-1) \le 2$ for all $n \ge 1$. Moreover, from Eq.~\eqref{hsj} we have $h(\sjp) = N_{j+1}$, which, together with ({\sl i}), shows that $h(\sjp)/h(\sjp-1)= 2$ holds for infinitely many $j$'s and the proof of ({\sl vi}) is completed. \end{enumerate} \end{proof} \begin{remark} Properties \sl(iv), \sl(v) and \sl(vi) of $h(n)$ are analogous to the following properties of $g(n)$. \begin{itemize} \item[\sl(iv)] $g(n)$ is odd only for $n \in \set{3, 8, 15}$ (cf.\ \cite[p.~142]{TheseJLN}). \item[\sl(v)] For $n \ge 1$, we have $g(n) \le 2g(n-1)$ (cf.\ \cite[p.~143]{TheseJLN}). \item[(vi)] $\lim_{n \to \infty} g(n)/g(n-1) = 1$ is proved in \cite{CRASJLN}. \end{itemize} \end{remark} \begin{proposition}\label{propgamh} For $n \ge 1$, let $\gm_h(n)$ denote the cardinality of the set $\set{h(m); 1 \le m \le n}$. Then, with $k=k(n)$ defined by Eq.~\eqref{def:k(n)}, we have \begin{equation}\label{gamhk} \frac{(k+2)(k-1)}{2} \le \gm_h(n) \le n-\frac{\sk-k}{2}, \end{equation} and, when $n \to \infty$, \begin{equation}\label{gamhn} \frac{2n}{\log n} \lesssim \gm_h(n) \lesssim \frac{n}{2}. \end{equation} \end{proposition} \begin{proof} First, we observe that $\gm_h(n)$ is the number of $m \le n$ such that $h(m) > h(m-1)$ holds. From Theorem~\ref{thm:known} (ii), for $1 \le i \le j$ and $m=\sigma_j -p_i$ we have $\ell(h(m))= m$ and thus $h(m)>h(m-1)$ holds, so that \[ \gm_h(n) \ge \sum_{j=2}^{k} \left(\gm_h(\sigma_j-1) - \gm_h(\sigma_{j-1}-1)\right) \ge \sum_{j=2}^{k} j = \frac{(k+2)(k-1)}{2}. \] To prove the upper bound in Eq.~\eqref{gamhk}, we note that $n-\gm_h(n)$ is the number of $m \le n$ such that $h(m)=h(m-1)$. From Theorem \ref{thm:known} (i) and (iii), for $j \ge 2$ and $\sigma_j \le m < \sigma_{j+1}$, we have $h(m)=h(m-1)$ for $\sigma_{j+1}-m \in \set{1,4,6,\ldots,p_{j+1}-1}$, so that, as $h(0)=h(1)=1 < h(2)=2 < h(3)=3=h(4)$ we get \[ n-\gm_h(n) \ge 2 + \sum_{j=2}^{k-1} \frac{p_{j+1}-1}{2} = 2 + \frac{\sk-5}{2} - \frac{k-2}{2} \ge \frac{\sk-k}{2}. \] Finally, to prove \eqref{gamhn}, we use Lemma \ref{lem:Sequiv} below. We get \dsm{\sk=\sum_{p \le p_{k}} p \sim \frac{p_k^2}{2\log p_k}.} But, from the prime number theorem, we have $p_k \sim k \log k$ so that $\log p_k \sim \log k$, \[ \sk \sim\frac{k^2\log k}{2} \sim\skp, \quad n \sim \frac{k^2 \log k}{2}, \quad \log k \sim \frac{\log n}{2} \qtx{ and } k \sim 2 \sqrt{\frac{n}{\log n}} \] which, together with \eqref{gamhk}, proves \eqref{gamhn}. \end{proof} \begin{remark} The estimates for $\gamma_g(n)$ are weaker (cf.\ \cite[p.~162--164]{TheseJLN} and \cite[p.~218]{MPE}). However it seems difficult to show $\gm_h(n) \sim n/2$ which is probably true. \end{remark} \begin{proposition}\label{prop2.2} Let $k \ge 1$ and $n \ge 2$ satisfy $k(n)=k$ (defined by Eq.~\eqref{def:k(n)}), so that $\sk \le n < \skp$ holds. \begin{enumerate} \item If $\sk \le n <\sk+p_{k+1}-p_k$, then we have $h(n)=h(\sk) = N_k$ and $\Pplus(h(n))=p_k$. \item If $\sk+p_{k+1}-p_k \le n < \skp$, then we have $\Pplus(h(n)) \ge p_{k+1}$. \end{enumerate} \end{proposition} \begin{proof} From Theorem~\ref{thm:known} (ii), we have \begin{equation}\label{hak} h(\sk+p_{k+1}-p_k) = N_{k+1}/p_k > N_k. \end{equation} From Eq.~\eqref{omegaequalk}, we have $\omega(h(n))= k$, and from \eqref{PplusGepk} we get $\Pplus(h(n)) \ge p_k$. \begin{itemize} \item[-] If $\Pplus(h(n))=p_k$, then we have $h(n)=N_k$, which, from Eqs.~\eqref{hak} and \eqref{hdef2}, implies $n < \sk+p_{k+1} - p_k$. \item[-] If $\Pplus(h(n)) \ge p_{k+1}$, then, from Eq.~\eqref{ellLeh}, we have \[ n \ge \ell(h(n)) \ge \Pplus(h(n)) + p_1 + \cdots +p_{k-1} \ge \sk+p_{k+1} -p_k. \] \end{itemize} \end{proof} \begin{corollary} There exist arbitrary long intervals on which $h(n)$ is constant. \end{corollary} \begin{proof} Since the difference $p_{k+1}-p_k$ is not bounded, this follows from Proposition~\ref{prop2.2} (i) above. Nicolas proved a similar result for $g(n)$ in \cite[p.~158]{TheseJLN}. \end{proof} \subsection{Computation of \texorpdfstring{$h(n)$}{h(n)}} The algorithm given in \cite{DNS} was used to compute $h(10^k)$ for $1 \le k \le 35$. Let us recall a few facts. Let $k=k(n)$ be defined above by Eq.~\eqref{def:k(n)}. The value $h(n)$ may be written as the product of two terms: \[ h(n) = N_k \cdot G(p_k,n-\sk), \] where $G(p,m)$ is defined by \[ G(p,m)= \max\frac{Q_1Q_2\cdots Q_s}{q_1 q_2 \cdots q_s}, \] the maximum being taken over the primes $Q_1,Q_2,\ldots,Q_s,q_1,q_2,\ldots,q_s$, $s \ge 0$, satisfying \[ 2 \le q_s < q_{s-1} < \cdots < q_1 \le p < Q_1 < Q_2 < \cdots < Q_s \qtx{and} \sum_{i=1}^{s} (Q_i-q_i) \le m. \] The algorithm given in \cite{DNS} for computing an isolated value $h(n)$ is composed of two steps. \begin{enumerate} \item The first step is the computation of $k=k(n)$, $p_k$ and $\sk$. \item The second step is the computation of the fraction \mbox{$h(n)/N_k=G(p_k,n-\sk)$}, \end{enumerate} When computing $h(n)$ for an $n$ larger than, say $10^5$, most of the computation time is devoted to the first step. In this article we needed to compute the values of $h(n)$ for all $n$ up to $x$, for some values $x$, the largest of them being $x=10^{10}$ (this computation took about $100$ hours of one processor on an AMD Shanghai computer with 8 processors). In this case, the computation of $p_k$ and $\sk$ is done once and for all for the $n$ belonging to the same $\intfg{\sk}{\skp}$. So, working by slices on the successive $\intfg{\sk}{\skp}$, the time of computation is mostly devoted to the computation of $G(p_k,n-\sk)$. \section{About the distribution of primes}\label{section3} \subsection{Some lemmas} \begin{lemma}\label{lem:Sequiv} Let us write $S(x) = \sum_{p \le x} p$. When $x$ tends to infinity, \begin{equation}\label{eqsx} S(x) \sim \frac{x^2}{2 \log x}. \end{equation} \end{lemma} \begin{proof} Massias et al. \cite[Lemme B]{MNRAA} proved that $S(x) = \Li(x^2) + \bigo{x^2 e^{-a\sqrt{\log x}}}$ for some $a > 0$, which implies \eqref{eqsx}, since $\Li(t) \sim t/\log t$ when $t \to \infty$. \end{proof} Lemma \ref{lemPhi} below is \cite[Lemma 2]{MNRMC}. \begin{lemma}\label{lemPhi} Let $a$ be a nonnegative real number and $\Phi = \Phi_{a}$ the function defined by \[ \Phi(x) = \sqrt{x \log x} \left( 1 + \frac{\lgd x-a}{2 \log x}\right). \] Then $\Phi$ is increasing and concave for $x > 1$. \end{lemma} \noindent Proposition~\ref{mnr} is from \cite[Point (ii), Proposition 1, p.~672]{MNRMC}. \begin{proposition}\label{mnr} For $k \ge 4398$, that is $p_k \ge 42061$, and $b = 1.16$, we have \begin{equation}\label{minthetapk} \theta(p_k) \ge \Phi_{b}(\sigma_{k+1}) = \sqrt{\sigma_{k+1}\log \sigma_{k+1}} \left(1+\frac{\lgd \sigma_{k+1}-b}{2\log \sigma_{k+1}} \right). \end{equation} \end{proposition} \subsection{The error term in the prime number theorem} Let $\theta$ be the Chebyshev function defined in \eqref{defthetapsi}. \begin{enumerate} \item There is some $a > 0$ such that \begin{equation}\label{TNP1} \theta(x) = x + \bigo{x e^{-a\sqrt{\log x}}}. \end{equation} \item If $\Theta < 1$, we have \begin{equation}\label{TNP2} \theta(x) = x + \bigo{x^{\Theta} \log^2 x}. \end{equation} \item Under the Riemann hypothesis, we have \begin{equation}\label{TNP3} \abs{\theta(x)-x} \le \frac{1}{8\pi} \sqrt x \log^2 x, \qquad x \ge 599. \end{equation} \end{enumerate} Points (i) and (ii) may be found in \cite{INGHAM32} or \cite{EMF}, for instance. Point (iii) is proved in \cite[p.~337]{SCH76}. \subsection{Effective bounds} We shall use the following results of P. Dusart: \begin{align}\label{thetaxlx} &\theta(x) < x \text{ for } x \le 8\cdot10^{11} \quad \text{(cf.\ \cite[Table 6.6]{DUS10})}\\ \label{T2} &\theta(x) < x + \frac{x}{36\,260} \le 1.000\,028\,x\quad (x > 0) \ \text{(cf.\ \cite[Proposition 5.1]{DUS10})} \\ \label{T4} &\abs{\theta(x)-x} \le \frac{0.05\, x}{\log^2 x}\quad (x \ge 122\,568\,683) \ \text{(cf.\ \cite[Theorem 5.2]{DUS10})} \end{align} \subsection{Distances between primes}\label{ecartsp} \begin{enumerate} \item Dusart \cite[Proposition 6.8]{DUS10} has proved that, for $x \ge 396\, 738$, the interval \begin{equation}\label{label21} \intf{x}{x+\frac{x}{25 \log^2 x}} \end{equation} contains a prime number. This implies, for $p_i \ge 396\,833 = p_{33\,609}$, \begin{equation}\label{duspi} p_{i+1} \le p_i + \frac{p_i}{25\,\log^2 p_i}. \end{equation} \item Under the Riemann hypothesis, Formula \eqref{TNP3} implies that, for $x \ge 599$, the interval \dsm{\intf{x-\sqrt x \log^2 x/(4\pi)}{x}} contains a prime number. Still under the Riemann hypothesis, Cram\'{e}r \cite{CRA} proved that there exists $b$ such that the interval $\intf{x}{x+b\sqrt x \log x}$ contains a prime. Ramar\'{e} et al. \cite[Th. 1]{RAMSAO} have made effective this result by proving that, for $x \ge 2$, the interval \begin{equation}\label{craint} \intf{x-\frac{8}{5}\sqrt x \log x}{x} \end{equation} contains a prime number, which implies that, for $p_i \ge 3$, \begin{equation}\label{lab18} p_{i-1} \ge p_i - \frac85 \sqrt p_i \log p_i. \end{equation} In \cite{CRA}, the ``Cram\'{e}r Conjecture'' is stated as \begin{equation}\label{conjcra} p_{i+1} - p_i = \bigo{\log^2 p_i}. \end{equation} This conjecture is supported by numerical computations (cf., for example, \cite{Nicy}). \end{enumerate} \subsection{The \texorpdfstring{$\eta_k$}{eta} functions}\label{etasection} Let $k \ge 1$ be integer. By the prime number theorem, the quotient $p_{i-k}/p_{i}$ tends to $1$ when $i \to +\infty$. Thus, for $i_0 \ge k+1$ there is at most a finite number of $i$'s such that \dsm{\frac{p_{i-k}}{p_{i}} \le \frac{p_{i_0-k}}{p_{i_0}} < 1}, and the following definition makes sense. \begin{definition}\label{defetak} We define $\eta_k$ on the interval $\intfg{p_k}{+\infty}$ by \begin{equation}\label{eta1} \eta_k(x) = \min\set{\frac{p_{i-k}}{p_{i}} \ | \ p_i > x}. \end{equation} \end{definition} From \eqref{eta1} we see that $\eta_k$ is a nondecreasing and right-continuous step function whose discontinuity points are primes called \emph{$\eta_k$--champion numbers}. By convention, $p_k$ is considered as an $\eta_k$--champion. The following lemma is proved in \cite[\S 2.4]{DN} \begin{lemma}\label{lem:etak} \mbox{} \begin{enumerate} \item Let $x$ be $\ge p_k$. For all $y \ge x$, the interval $\intfd{ \eta_k(x)y}{y}$ contains at least $k$ prime numbers, and $\eta_k(x)$ is the largest real number $\lb$ such that \dsm{\intfd{\lb y}{y}} contains at least $k$ prime numbers for all $y \ge x$. \item Let $p$ be an $\eta_k$--champion. Then for all $x \ge p$ , $\eta_k(x) \ge \eta_k(p)$, in particular, the interval $\intfd{\eta_k(p) x}{x}$ contains at least $k$ prime numbers. \end{enumerate} \end{lemma} Tables of the first few $\eta_k$--champion numbers for $k=1,2,3$, may be found in \cite[Tables 3,4,5]{DN}, or on \cite{Htables} for more values. Proposition~\ref{propmin} (cf.\ \cite[Proposition 2.1]{DN} for more details) recalls some results that we shall use later. \begin{proposition}\label{propmin} \mbox{} \begin{enumerate} \item From \cite[p.~562]{BHP} there exists $a > 0$ such that, for $x \ge p_k$, we have \[ \eta_k(x) \ge 1-k \frac{a}{x^{0.475}}\,. \] \item Let $i_0$ be defined by $i_0 = 33\,609$. For $i$ close to $i_0$ the values of $p_i$ are \begin{center} \begin{tabular}{r|r|r|r|r|r} $i=$& $33\, 608$ & $33\,609$& $33\,610$& $33\,611$& $33\,612$\\ \hline $p_i=$& $396\,733$ & $396\,833$ & $396\,871$ & $396\,881$& $396\,883$\\ \end{tabular} \end{center} For $x \ge p_{i_0+k-1}$ we have from Eq.~\eqref{label21} that \begin{equation}\label{dus25} \eta_k(x) \ge 1-\frac{k}{25\log^2 x}. \end{equation} \item Under the Riemann hypothesis, for $x \ge \max(p_k,e^2)$, we have from \eqref{craint} \begin{equation}\label{eq:etaprox} \eta_k(x) \ge 1-\frac{8k}{5}\frac{\log x}{\sqrt x}. \end{equation} \item Under Cram\'{e}r's conjecture \eqref{conjcra}, there exists $a > 0$ such that, for $x \ge \max(p_k,e^2)$ \begin{equation}\label{etacra} \eta_k(x) \ge 1 - ka\frac{\log^2 x}{x}. \end{equation} \end{enumerate} \end{proposition} \subsection{The \texorpdfstring{$\thmin$, $\thd$, and $\dt_3$ functions}{thmin, thd and dt3}} In this subsection we introduce three functions, $\thmin$, $\thd$, $\dt_3$, defined on the real interval $\intfg{1}{+\infty}$. More information about them can be found in \cite[\S 2]{DN}. \begin{definition} \mbox{}\!The function $\thmin$ is the nondecreasing right-continuous step function defined by \begin{equation}\label{thmin} \thmin(y) = \inf_{x \ge y} \dfrac{\theta(x)}{x} = \inf_{p_i > y} \frac{\theta(p_{i-1})}{p_i}. \end{equation} \end{definition} A table of the first few $\thmin$--champion numbers $p$ and their rounded-down records $\thmin(p)$ may be found in \cite[Table 1]{DN} or on the web pages of the first author \cite[Tabulation de thetamin]{Htables}. If $p < q$ are two consecutive $\thmin$--champion numbers, then $\thmin$ is constant on $\intfg p q$ and equal to $\thmin(p) = \theta(q^-)/q$ where $q^-$ is the prime preceding $q$. If $x \ge p$, then $\theta(x)/x \ge \thmin(p)$ holds. \begin{definition} Let us define $\thd(y)$ for $y \ge 1$ by \[ \theta_d(y) = \sup_{x \ge y} \abs{\frac{\theta(x)}{x}-1}\log^2 x, \] so that, for $x \ge y$, we have \begin{equation}\label{propthetad} \abs{\frac{\theta(x)}{x}-1} \le \frac{\theta_d(y)}{\log^2 x}. \end{equation} \end{definition} A table of the first few $\thd$--champion numbers and records is given in \cite[Table 2]{DN}. A more extensive table may be found in \cite[Tabulation de thetad]{Htables}. If $p < q$ are two consecutive $\thd$--champion numbers, we have $\thd(p)= (1-\theta(q^-)/q)\log^2 q$ where $q^-$ is the prime preceding $q$. For $p \le x < q$, $\thd(x)=\thd(p)$ and, for $x \ne 1$, $1-\thd(p)/\log^2(x) \le \theta(x)/x$. \begin{definition} Let us define the function $\dt_3$, for $y \ge p_3 = 5$, by \[ \dt_3(y) = \sup_{x \ge y} (1-\eta_3(x))\log^2 x. \] \end{definition} \noindent For $x \ge y$, we have \begin{equation}\label{pd3} 1-\eta_3(x) \le \frac{\dt_3(y)}{\log^2(x)}. \end{equation} A table of the first few $\dt_3$--champion numbers is given in \cite[Table 6]{DN}. A more extensive table may be found in \cite[Tabulation de delta3]{Htables}. If $p < q$ are two consecutive $\dt_3$--champion numbers, we have $\dt_3(p) = (1-\eta_3(q^-))\log^2(q)$ where $q^-$ is the prime preceding $q$. For $p \le x < q$, $\dt_3(x)=\dt_3(p)$ and, for $x \ne 1$, $1-\dt_3(p)/\log^2(x) \le \eta_3(x) \le 1$. \section{Estimates for \texorpdfstring{$\log h(n)$}{h(n)} and \texorpdfstring{$\omega(h(n))$}{h(n)}}\label{section4} \subsection{An asymptotic equivalent of \texorpdfstring{$\log h(n)$}{h(n)}} \begin{theorem}\label{th2} When $n \to +\infty$, \dsm{\log h(n) \sim \sqrt{n\log n}.} \end{theorem} \begin{proof} Let be $k=k(n)$ defined by \eqref{def:k(n)}. From \eqref{boundhn} it is sufficient to prove that, when $n$ tends to infinity, $\log N_k \sim \sqrt{n\log n}$. When $k \to \infty$, $p_{k-1} \sim p_k$, and, from \eqref{eqsx}, $\sigma_{k-1} \sim \sigma_{k} \sim \dfrac{p_k^2}{2\log p_k}$. With \eqref{def:k(n)} this gives \dsm{ n \sim \dfrac{p_k^2}{2\log p_k}, } from which we infer \[ p_k \sim \sqrt{n \log n}, \] and, by the prime number theorem, $\log N_k = \theta(p_k) \sim p_k \sim \sqrt{n \log n}$. \end{proof} \subsection{Effective estimates of \texorpdfstring{$\log h(n)$}{h(n)}} \begin{theorem}\label{minlogh:theorem} The assertion \begin{equation} \label{min1.16} n \ge n(b) \implies \log h(n) > \sqrt{n \log n} \left( 1+\frac{\lgd n - b}{2\log n}\right) \end{equation} is true for the following pairs $(b,n(b))$ (where each $n(b)$ is optimal): \[ \begin{array}{|c|c|c|c|c|c|c|c|} \hline b& 2.0 & 1.8 & 1.6 & 1.4 & 1.20 & 1.18 & 1.16\\ \hline n(b)& 19\,491 & 57\,458 & 201\,460 & 1\,303\,470 & 29\,696\,383 & 44\,689\,942 & 77\,615\,268\\ \hline \end{array} \] \end{theorem} \begin{proof} First suppose that $b=1.16$ and $n \ge 87\, 179\, 593 = \sigma_{4398}$. Let $k = k(n)$ defined by \eqref{def:k(n)} so that $\sk \le n < \skp$ holds. From \eqref{boundhn}, Inequality \eqref{minthetapk} and Lemma \ref{lemPhi}, we may write \[ \log h(n) \ge \theta(p_k) \ge \Phi_{b}(\sigma_{k+1}) \ge \Phi_{b}(n). \] This proves that \eqref{min1.16} is true for $b=1.16$ with $n(b) = 87\, 179\, 593$. The computation, by the method described in \S 2.1, of all the values $h(n)$ for $n \le 87\, 179\, 592$ gives, for each value of $b$ the smallest value $n(b)$ such that Eq.~\eqref{min1.16} holds. \end{proof} \begin{corollary}\label{coroth2} We have \begin{equation}\label{largersqrtnlogn} \log h(n) > \sqrt{n\log n} \quad \text{ for } n \ge 7\,387. \end{equation} \end{corollary} \begin{proof} By using \eqref{min1.16} with $b=2$, if $n \ge 19\,491$ we may write \[ \log h(n) > \sqrt{n\log n} \left(1+\frac{\lgd n-2}{2\log n} \right) \ge\sqrt{n\log n} \] since $\lgd n \ge 2$. By computing $h(n)$ for $2 \le n \le 19\,490$, we prove that $7\,386$ is the largest integer such that $\log h(n) \le \sqrt{n\log n}$. \end{proof} \begin{theorem} The following inequality is satisfied \begin{equation}\label{L3} \log h(n) \le \sqrt{n \log n}\left(1+\frac{\log_2 n - 0.975}{2\log n} \right),\quad n \ge 3. \end{equation} \end{theorem} \begin{proof} This results from \eqref{hLeg} and \cite[Theorem 2]{MNRMC}. \end{proof} \begin{corollary}\label{thmajlogh} For each $n \ge 2$, \begin{equation}\label{majlogh} \frac{\log h(n)}{\sqrt{n\log n}} \le 1.0482016\cdots\!, \end{equation} the upper bound being attained for $n=38343860 = \sigma_{2989}= \ell(N_{2989})$. \end{corollary} \begin{proof} For $n \ge n_1 = 3.6\cdot10^9$, we have $\dfrac{\lgd n-0.975}{2\log n} \le 0.048$. Thus, by \eqref{L3}, Inequality \eqref{majlogh} is satisfied for $n \ge n_1$. The computation of the values $h(n)$ for $n$ up to $n_1$ shows that the maximum value is attained on $n=\sigma_{2989}$. \end{proof} It is possible to shorten the computation by using the trick described in \cite[\S 4]{Mas}. Let us recall briefly how it works. From Theorem~\ref{th2} and Corollary~\ref{coroth2}, we know that there exists $\lambda> 1$ such that \begin{equation} \label{hlam} \forall n \ge 1, \quad \log h(n) \le \lambda\sqrt{n \log n}, \end{equation} with equality for some $ n=n_0\ge 2$. Moreover, we have \begin{equation} \label{lhn0} \ell(h(n_0)) =n_0 \end{equation} since, if we should have $\ell(h(n_0)) \le n_0 -1$, we would have $h(n_0-1)=h(n_0)$ and $\log(h(n_0-1)/\sqrt{(n_0-1)\log (n_0-1)} > \lambda$, contradicting \eqref{hlam}. Now, let $M\ge 1$ be a squarefree integer. From (1.1) and \eqref{hlam}, we have \begin{equation} \label{logM<} \log M \le \log h(\ell(M)) \le \lambda \sqrt{\ell(M) \log \ell(M)} \end{equation} and, by setting $M_0=h(n_0)$, we get from \eqref{lhn0} \begin{equation} \label{logM0<} \log M_0=\lambda\sqrt{n_0 \log n_0}=\lambda \sqrt{\ell(M_0) \log \ell(M_0)}. \end{equation} The function $\phi: t\longrightarrow t\log t$ is a bijection from $(1,+\infty)$ to $(0,+\infty)$. Let us call $\phi^{-1}$ its inverse function. We set \[ u=u(M)=\phi^{-1} \left(\left( \frac{\log M}{\lambda}\right)^2\right),\quad u_0=u(M_0),\quad \rho=\frac{2\sqrt{u_0\log u_0}}{\lambda(1+\log u_0)}. \] We have $$\log M=\lambda\sqrt{\phi(u)}=\lambda\sqrt{u\log u}, \qquad \log M_0=\lambda\sqrt{u_0\log u_0}$$ so that \eqref{logM0<} yields $$u_0=\ell(M_0).$$ Now, we set \begin{equation} \label{f1f2} f_1=\ell(M)-u(M)\quad \text{ and } \quad f_2=u(M)-\rho \log M. \end{equation} As $\phi$ is increasing, $f_1\ge 0$ is equivalent to $\phi(\ell(M)) \ge \phi(u(M))$ which follows from \eqref{logM<}. Therefore, we have \begin{equation} \label{f1} f_1=\ell(M)-u(M)\ge 0=\ell(M_0)-u(M_0). \end{equation} We have $f_2=u-\lambda\rho \sqrt{u\log u}$ which is convex on $u > 1$ and whose derivative vanishes for $u=u_0$, due to the choice of $\rho$. Therefore, we have \begin{equation} \label{f2} f_2 \ge u_0-\lambda\rho \sqrt{u_0\log u_0}=\ell(M_0)-\rho\log M_0. \end{equation} By adding \eqref{f1} to \eqref{f2}, we deduce from \eqref{f1f2} \begin{equation} \label{lMrho} \forall \text{ squarefree } M \ge 1, \qquad \ell(M)-\rho \log M \ge \ell(M_0)-\rho\log M_0. \end{equation} Let $p$ be the largest prime factor of $M_0$ and assume that a prime $p' < p$ does not divide $M_0$; then applying \eqref{lMrho} for $M=M_0/p$ and for $M=M_0p'$ yields respectively $\rho \ge p/\log p$ and $\rho \le p'/\log p'$ whence $p/\log p < p'/\log p'$. The function $t\mapsto t/\log t$ being minimal for $t=\exp(1)$, this is only possible if $p=3$, $p'=2$ and $M_0=3$, which is impossible since $\log 3 < \sqrt{3 \log 3}$ holds. Therefore, there exists $k\ge 1$ such that $M_0=N_k$, $\ell(M_0)=\sk$ and \[ \lambda=\max _{j\ge 1,\; \sj \le 3.6 \; 10^9}\frac{\log N_j}{\sqrt{\sj\log \sj}}. \] \subsection{{An upper bound for \texorpdfstring{$\log g(n) - \log h(n)$}{log g(n)-log h(n)}}} \begin{theorem}\label{thm:logh-logg} There exists $C > 0$ such that, for $n \ge 1$, \begin{equation}\label{boundingg-h} \log g(n) - C (n\log n)^{1/4} \le \log h(n) \le \log g(n). \end{equation} We may choose $C = 5.68$. \end{theorem} \begin{proof} Given \eqref{hLeg}, it is sufficient to prove the left inequality of \eqref{boundingg-h}. Let $P=\Pplus(g(n))$ be the largest prime factor of $g(n)$. Then, by \cite[Theorem 5.1]{DN}, $P \le 1.27 \sqrt{n\log n}$. By Bertrand's postulate, there exists a prime $q$ such that \begin{equation}\label{majq} P < q \le 2.54 \sqrt{n \log n}. \end{equation} Let us write \[ g(n) = \prod_{p \le P} p^{a_p} \qtx{ where } a_p = v_p (g(n)), \] and \[ g(n) = A\cdot B \qtx{ with } A = \prod_{p \le P,\ a_p \ge 2} p^{a_p}, \quad B = \prod_{p \le P,\ a_p = 1} p^{a_p}. \] Then $B$ divides $g(n)$, so that $\ell(B) \le \ell(g(n))$ and, from \eqref{landau}, $\ell(g(n)) \le n$, which implies $\ell(B) \le n$. As $B$ is squarefree, it follows from \eqref{landau} that $h(n) \ge B = g(n)/A$ which implies \begin{equation}\label{minh} \log h(n) \ge \log g(n)-\log A. \end{equation} Let us find an upper bound for $A$. If $a_p \ge 2$, we have $p^{a_p} \le q + p^{a_p-1}$ (otherwise $N' = qg(n)/p$ would be such that $N' > g(n)$ and $\ell(N') = \ell(g(n)) + p^{a_p-1} + q -p^{a_p} < \ell(g(n) \le n$, contradicting the definition of $g(n)$). This gives $p^{a_p} \le q/(1-1/p) \le 2q$ and $p \le (2q)^{1/a_p} \le \sqrt{2q}$. From this we deduce $A \le (2q)^{\pi(\sqrt{2q})}$ and, by using the inequality $\pi(t) \le 1.26\, t/\log t$ (cf.\ \cite[(3.6)]{RS62}) and \eqref{majq}, we get \[ \log A \le 1.26 \frac{\sqrt{2q}}{\log\sqrt{2q}} \log (2q) = 2.52 \sqrt{2q} \le 5.68 (n \log n)^{1/4}, \] which, with \eqref{minh}, ends the proof. \end{proof} \subsection{Study of \texorpdfstring{$\omega(h(n))-\omega(g(n))$}{omega(h(n)-omega(g(n)}} \begin{theorem}\label{thm:omh-omg} There exists a constant $C$ such that, for $n \ge 2$, \begin{equation}\label{omh-omg} 0 \le \omega(h(n))-\omega(g(n)) \le C \frac{n^{1/4}}{(\log n)^{3/4}}. \end{equation} \end{theorem} \begin{proof} \mbox{\vphantom{X} }\newline \noindent{\bf The lower bound:} Let $n$ be a positive integer, and define $k=k(n)$ by \eqref{def:k(n)}. Therefore we have \begin{equation}\label{knk+1} \sk \le n < \skp \end{equation} and, by Theorem~\ref{theorem:omega}, $\omega(h(n))=k$. Further, from \eqref{landau} and \eqref{knk+1}, we have \[ \sigma_{\omega(g(n))} = p_1 + p_2 + \cdots + p_{\omega(g(n))} \le \sum_{p \mid g(n)} p \le \ell(g(n)) \le n < \skp \] whence $\omega(g(n)) \le k = \omega(h(n))$ and the lower bound of \eqref{omh-omg} is proved. \bigskip \noindent{\bf The upper bound.} Let $x_1 > 4$ be a real number and, for $i \ge 2$, $x_i$ be the unique number such that \dsm{\frac{x_i^{i}-x_{i}^{i-1}}{\log x_i} = \frac{x_1}{\log x_1}}. The sequence $(x_i)$ is decreasing and satisfies \begin{equation}\label{xi<} x_i < x_1^{1/i} \end{equation} so that $x_i < 2$ for $i > I = \intfrac{\log x_1}{\log 2}$. We set \begin{equation}\label{N1} N = N(x_1) = \prod_{i=1}^I \prod_{p \le x_i} p. \end{equation} Such an integer $N$ is called in \cite[\S 4]{DNZ} an $\ell$--superchampion number associated with $x_1$. Let $G$ denote the set of $\ell$--superchampion numbers. If $N \in G$, the set $\set{x_1; N(x_1)=N}$ is an interval of positive length. Thus we can choose a particular value of $x_1$ such that, for $i \ge 1$, $x_i$ is never prime (cf.\ \cite[Lemma 4, 3.]{DNZ}). With such a value of $x_1$ \eqref{N1} becomes \begin{equation}\label{N2} N = N(x_1) = \prod_{i=1}^{I}\prod_{p < x_i} p. \end{equation} Now, let us define $k_1$ and $k_2 \le k_1$ by \begin{equation}\label{k1k2} p_{k_1} < x_1 < p_{k_1+1} \qtx{ and } p_{k_2} < \sqrt{x_1} < p_{k_2+1}. \end{equation} It follows from \eqref{N2} and \eqref{xi<} that, for every prime $p$, we have \begin{equation}\label{pvpN} p^{v_{p(N)}} < x_1 \qtx{ and } v_{p}(N) = 1 \qtx{for} p_{k_2} < p \le p_{k_1}. \end{equation} Therefore, we get from \eqref{N2} and \eqref{k1k2} \begin{equation}\label{sigk1k2} \sigma_{k_1} = \sum_{p < x_1} p \le \ell(N) \le k_2 x_1 + \sigma_{k_1} \le \sigma_{k_1+k_2}. \end{equation} Let $n$ be an integer, $n \ge 12$, and $N=N(x_1) < N'= N'(x_1')$ two consecutive $\ell$--super\-champion numbers such that \[ \ell(N) \le n < \ell(N'). \] Since $N'/N$ is a prime $p'$ (cf.\ \cite[Lemma 4, 4.(i)]{DNZ}), from \eqref{N2}, either $p'=p_{k+1}$ or $x_1' < p_{k+1}$, and, from \eqref{pvpN}, $(p')^{v_{_{p'}(N')}} < x_1' < p_{k+1}$. In both cases, $\ell(N') \le \ell(N) + p_{k+1}$. Therefore, from \eqref{sigk1k2}, we get \begin{equation}\label{k1nk2} \sigma_{k_1} \le \ell(N) \le n < \ell(N') \le \ell(N) + p_{k+1} \le \sigma_{k_1+k_2+1}, \end{equation} and \eqref{omegaequalk} from Theorem~\ref{theorem:omega} yields \[ k_1 \le \omega(h(n)) \le k_1 + k_2. \] On the other hand, \cite[Lemma E]{MNRAA} gives \[ \omega(g(n)) = \omega(N) + \bigo{\frac{\sqrt{x_1}}{\log x_1}}. \] From \eqref{N2} and \eqref{k1k2}, we get $\omega(N)= k_1$, and from \eqref{k1k2} and the prime number theorem, we have \begin{equation}\label{k1k2equiv} k_1=\pi(x_1) \sim \frac{x_1}{\log x_1} \qtx{ and } k_2 = \pi(\sqrt{x_1}) \sim \frac{2\sqrt{x_1}}{\log x_1}. \end{equation} Thus, we get \begin{align}\label{Osqx1} \omega(h(n)) - \omega(g(n)) &\le k_1 + k_2 -\omega(N) + \bigo{\frac{\sqrt{x_1}}{\log x_1}}\\ &= k_2 + \bigo{\frac{\sqrt{x_1}}{\log x_1}} = \bigo{\frac{\sqrt{x_1}}{\log x_1}}. \end{align} Finally, from \eqref{k1k2equiv}, we have $k_1+k_2 \sim k_1 \sim \bigo{\dfrac{x_1}{\log x_1}}$, which, with \eqref{k1nk2} and Lemma \ref{lem:Sequiv}, yields $n \sim \sum_{p \le x_1} p \sim \dfrac{x_1^2}{2\log x_1}$. Therefore, $x_1 \sim \sqrt{n\log n}$ and $\log x_1 \sim (1/2) \log n$ holds, which completes the proof of Theorem~\ref{thm:omh-omg}. \end{proof} \subsection{Asymptotic estimates for \texorpdfstring{$\log h(n)$}{log h(n)} and \texorpdfstring{$\omega(h(n))$}{omega(h(n)}} \begin{theorem}\label{thm:asy_h} There exists $a > 0$ such that, when $n \to +\infty$, \begin{equation}\label{asym1} \log h(n) = \sqrt{\Li^{-1}(n)} + \bigo{\sqrt n e^{-a\sqrt{\log n}}}. \end{equation} If $\Theta > 1/2$ and $\xi < \Theta$, then \begin{equation}\label{asym2} \log h(n) = \sqrt{\Li^{-1}(n)} + \Omega_{\pm}\left((n\log n)^{\xi/2}\right). \end{equation} Under the Riemann hypothesis, i.e., $\Theta = 1/2$, we have \begin{align}\label{asym3} \log h(n) &= \sqrt{\Li^{-1}(n)} + \bigo{\left((n\log n)^{1/4}\right)}.\\ \log h(n) &< \sqrt{\Li^{-1}(n)} \qtx{ for $n$ large enough.} \end{align} \end{theorem} \begin{proof} The above theorem is proved in \cite[Theorem 1]{MNRAA} with $g(n)$ instead of $h(n)$, so that its proof follows from Theorem~\ref{thm:logh-logg}. \end{proof} \begin{theorem}\label{thm:om_hn} There exists $a > 0$ such that, when $n \to +\infty$, \begin{equation}\label{asymptlogh1} \omega(h(n)) = \Li\left(\sqrt{\Li^{-1}(n)}\right) + \bigo{\sqrt n e^{-a\sqrt{\log n}}}. \end{equation} If $\Theta > 1/2$ and $\xi < \Theta$, then \begin{equation}\label{asymptlogh2} \omega (h(n)) = \Li\left(\sqrt{\Li^{-1}(n)}\right) + \Omega_{\pm}\left((n\log n)^{\xi/2}\right). \end{equation} Under the Riemann hypothesis, i.e., $\Theta = 1/2$, we have \[ \omega(h(n)) = \Li\left(\sqrt{\Li^{-1}(n)}\right) + \bigo{n^{1/4} (\log n)^{-3/4}}. \] \end{theorem} \begin{proof} The proof follows from \cite[Th\'{e}or\`{e}me 2]{MNRAA} and from Theorem \ref{thm:omh-omg}. \end{proof} Note that the corollary of \cite[p.~225]{MNRAA} is also valid with $g(n)$ replaced by $h(n)$ to give an asymptotic expansion of $\log h(n)$ according to the powers of $1/\log n$. We hope to make more precise the behavior of $h(n)$ and $\omega((h(n))$ under the Riemann hypothesis in another paper. \section{G\--sequences, a tool for bounding above \texorpdfstring{$\Pplus(h(n))$}{Pplus(h(n))}}\label{section5} Lemma \ref{lemmapp} is \cite[Proposition 3.3]{DN}. Lemma~\ref{atmost} below is an obvious corollary. \begin{lemma}\label{lemmapp} Let $n \ge 2$ be an integer and $p$, $p'$ be distinct primes such that $p+p' \le \Pplus(h(n))$. Then, at least one of $p$, $p'$ divides $h(n)$. \end{lemma} \begin{lemma}\label{atmost} If $q$ is a prime divisor of $h(n)$, there exists at most one prime $\le q/2$ that does not divide $h(n)$. \end{lemma} \begin{definition} Let $\gm, \gm'$ be such that $0 < \gm < \gm'< 1$ and $\gm' < \dfrac{1+\gm^2}{2}$. We define \begin{equation}\label{defalphabeta} \al = 2\gm'-1 \qtx{and} \bt = \gm^2. \end{equation} Then $\al < \bt$ and the pair of intervals $(I,J)$ defined by \[ I(\gm,\gm') = \intfd{\al}{\beta} \text{ and } J(\gm,\gm') = \intfd{\gm}{\gm'}. \] is called the $G$-pair associated with $(\gm,\gm')$. \end{definition} Lemma~\ref{grantham} can be found in \cite[Lemma 2]{GRA}. (In \cite{GRA}, this result is enunciated in the case of the Landau function $g(n)$.) Let $I$ be an interval and $\lb$ be a real number. Let us write $\lb I = \set{\lb x; x \in I}$. \begin{lemma}\label{grantham} Let $(I,J)$ be a $G$-pair, $n \ge 2$ and $q$ a prime factor of $h(n)$. If \dsm{q I} contains \emph{at least} one prime divisor of $h(n)$, then \emph{at most} one prime in $qJ$ fails to divide $h(n)$. \end{lemma} \begin{proof} Let us remark that $\gm = \sqrt \beta$ and $\gm' = (1+\al)/2$. By contradiction, let us suppose that $p$, $p'$ in $qJ$ are distinct primes that do not divide $h(n)$. Let $q'$ be a prime in $qI$ dividing $h(n)$. Let $M = \dfrac{pp'}{qq'}h(n)$. Then \[ \ell(M) = p+p'-q-q' + \ell(h(n)) \le 2\gm' q - q -\al q + \ell(h(n)) = \ell(h(n)). \] But $pp' - qq' > (\sqrt{\beta}q)^2 - q(\bt q) = 0$, so $M > h(n)$, giving a contradiction. \end{proof} \begin{definition} A \emph{\gseq\ of length $\ell$}\ is a finite sequence \dsm{(\gm_j)_{0 \le j \le \ell+1}} satisfying $\gm_0 = 0$, $\gm_1 = \dfrac{1}{2}$ and, for $1 \le j \le \ell$ \begin{equation}\label{condgamma} 0 < \gm_j < 1 \text{\quad and \quad} \gm_j < \gm_{j+1}< \frac{1+\gm_j^2}{2}. \end{equation} Let us define $I_0=\intfd{0}{\frac{1}{4}}, $ $J_0 = \intfd{0}{\frac{1}{2}}$ and, for $1 \le j \le \ell$, $I_j$ and $J_j$ by \begin{equation}\label{defIJ} \al_j = 2\gm_{j+1}-1,\ \bt_j = \gm_j^2,\ I_j = \intfd{\al_j}{\bt_j} \text{ and } J_j = \intfd{\gm_j}{\gm_{j+1}}. \end{equation} \end{definition} From \eqref{defIJ} we have that, for $j \ge 1$, the pair $(\intfd{\al_j}{\bt_j}, \intfd{\gm_j}{\gm_{j+1}})$ is a $G$-pair. In Section~\ref{gsuiteuniforme} we study the \emph{uniform \gseq s} such that the quotient $\al_j/\bt_j$ is a constant. \begin{definition}\label{defadmiss} Let \dsm{\Gamma= (\gm_j)_{0 \le j \le \ell+1}} be a \gseq\ and $y \ge 12$. For $1 \le i \le \ell$ we let $m_i$ denote the cardinality of the set of indices $j \in \set{0,1,\ldots,\ell}$ such that $I_i \cap J_j \ne \emptyset$. The \gseq\ $\Gamma$ is \emph{$y$-admissible} if, for every $\lb \ge y$ and each $i$, $1 \le i \le \ell$, the interval $\lb I_i$ contains at least $m_i+1$ primes. \end{definition} \begin{remark}\label{m1rem} For every \gseq, by \eqref{defIJ}, $I_1 = \intfd{\al_1}{1/4} \subset J_0 = \intfd{0}{1/2}$; thus $m_1 = 1 $. Therefore, if $(\gm_j)_{0 \le j \le \ell+1}$ is admissible, the interval $y I_1 = \intfd{y \al_1}{y/4}$ contains at least $m_1+1=2$ primes. This needs $y/4 \ge 3$, i.e., $y \ge 12$. \end{remark} \begin{remark}\label{m2rem} By Lemma \ref{lem:etak} \sl(i), the \gseq\ $(\gm_j)_{0 \le j \le \ell+1}$ is $y$--admissible if and only, for $1 \le j \le \ell$, we have the inequality $\al_j / \bt_j \le \eta_{m_j+1}(y \bt_j)$. \end{remark} \begin{lemma}\label{lem:admiss} Let $\Gamma=(\gm_j)_{0 \le j \le \ell+1}$ be a \gseq\ of length $\ell$ and $m$ an integer such that $m \ge m_j+1$ for $1 \le j \le \ell$. Let us suppose that $y$ is a real number such that, \begin{equation}\label{eq:admiss} \al_j/\bt_j \le \eta_m(y \bt_j) \qtx{ for } 1 \le j \le \ell. \end{equation} Then $\Gamma$ is $y$--admissible. \end{lemma} \begin{proof} Since $(r,x) \mapsto \eta_r(x)$ is nonincreasing in $r$, we may write \[ \al_j/\bt_j \le \eta_m(y \bt_j) \le \eta_{m_j+1}(y \bt_j) \] and, by using the previous Remark \ref{m2rem}, $\Gamma$ is $y$--admissible. \end{proof} \begin{proposition}\label{propg} Let \dsm{\Gamma=(\gm_j)_{0 \le j \le \ell+1}} be a \gseq\ of length $\ell$, and $q$ a prime factor of $h(n)$. If \dsm{\Gamma} is $q$-admissible then, for all $j$, $0 \le j \le \ell$ the interval \dsm{qJ_j = q\intfd{\gm_j}{\gm_{j+1}}} contains at most one prime which does not divide $h(n)$. Moreover \begin{equation}\label{majqh} \theta(q\gm_{\ell+1}) - \ell\log q < \theta(q\gm_{\ell+1}) - \ell\log q -\sum_{j=1}^{\ell+1} \log\gm_j \le \log h(n). \end{equation} \end{proposition} \begin{proof} Let $\cp(j)$ be the property that \emph{ there exists at most one prime number in $qJ_j$ that does not divide $h(n)$.} If $j=0$, by Lemma \ref{atmost}, \dsm{q J_0 = \intfd{0}{q/2}} contains at most one prime which does not divide $h(n)$. So $\cp(0)$ is true. By Remark \ref{m1rem}, $m_1 = 1$. Thus, by Definition \ref{defadmiss}, $q I_1$ contains at least two primes, $p, p'$. Since the upper bound of $qI_1$ is $q/4$, by Lemma \ref{lemmapp} we have that $p$ or $p'$ divides $h(n)$, and, by Lemma \ref{grantham}, there is at most one prime in $qJ_1$ which does not divide $h(n)$. Thus $\cp(1)$ is true. Let $j \in \intf{2}{\ell}$ such that $\cp(r)$ is true for $r < j$. The upper bound of $I_j$ is \dsm{\beta_j = \gm_j^2 < \gm_j}. We thus have \dsm{ q I_j \subset \intfd{0}{q \gm_j} = \bigcup_{r=0}^{j-1}q J_{r}. } By the induction hypothesis, each of the intervals $q J_{r}$, ($0 \le r \le j-1$), contains at most one prime number which does not divide $h(n)$. Since $q I_j$ intersects $m_j$ of these intervals, it contains at most $m_j$ primes not dividing $h(n)$. But, by hypothesis, $q I_j$ contains at least $m_j+1$ primes. Thus, one of them divides $h(n)$ and, by Lemma \ref{grantham}, this implies that $q J_j$ contains at most one prime which does not divide $h(n)$. This is to say that $\cp(j)$ is true. So we have just proved that $h(n)$ is divisible by all the primes in $\intfd{0}{q\gm_{\ell+1}}$, but at most one prime $q_j \in q\intfd{\gm_{j}}{\gm_{j+1}}$ for each $j=0,1,2,\ldots,\ell$. Since $q$ divides $h(n)$ we have \[ h(n) \ge\; q\,\frac{\prod_{p \le q \gm_{\ell+1}} p}{\prod_{j=0}^{\ell}q_j}\; \ge\; q\,\,\frac{\prod_{p \le q \gm_{\ell+1}} p}{\prod_{j=0}^{\ell}q\gm_{j+1}}. \] Applying $\log$, this gives the second inequality in \eqref{majqh}. The first inequality comes from \dsm{\sum_{j=1}^{\ell+1}\log\gm_j < 0}. \end{proof} \begin{proposition}\label{prop3} Let $n_0$, $y$, $a$ be positive real numbers such that \[ 12 \le y \le a \sqrt{n_0 \log n_0} \] and $\ell \ge 1$, integer. We assume that $\Gamma=(\gm_j)_{0 \le j \le \ell+1}$, is a \gseq\ $y$-admissible of length $\ell$. Let us define \begin{equation}\label{denn} D_\ell =\gm_{\ell+1} \thmin(y\gm_{\ell+1})-\frac{\ell\log y + \sum_{j=1}^{\ell+1}\log \gm_j }{y}, \end{equation} and let us suppose that $D_\ell > 0$. Then, for $n \ge n_0$, we have \begin{align}\label{l48} \Pplus(h(n)) &\le \max(a,b) \sqrt{n \log n} \qtx{ with } b = \frac{1.0482017}{D_\ell}. \\ \label{den2n} \Pplus(h(n)) &\le \max(a,b') \sqrt{ n\log n} \qtx{ with } b' = \frac{1}{D_\ell}\left(1+\frac{\lgd n_0 - 0.975}{2\log n_0}\right). \end{align} The second upper bound is better than the first one for $n \ge 3\,259\,922\,785$. \end{proposition} \begin{proof} Let $n$ be an integer, $n \ge n_0$. Let us set, for simplification, $q = \Pplus(h(n))$. \begin{enumerate} \item If $q < y$, then, by hypothesis, we have \begin{equation}\label{maja} q < y \le a\sqrt{n_0 \log n_0} \le a \sqrt{n \log n}. \end{equation} \item If $q \ge y$, then $q\gm_{\ell+1}\ge y\gm_{\ell+1}$. With Equation \eqref{thmin} this gives\\ $\theta(q\gm_{\ell+1}) \ge q \gm_{\ell+1}\thmin(y\gm_{\ell+1})$. We remark that $\sum_{j=1}^{\ell+1} \abs{\log \gm_{j}} \le (\ell+1)\log 2 \le 2\ell\log 2$ which implies that \dsm{t \mapsto (\ell \log t + \sum_{j=1}^{\ell+1} \log \gm_j)/t} is decreasing for $t \ge 4e$. From this and Equation \eqref{denn} defining $D_{\ell}$, we infer that \begin{equation}\label{majDl} D_{\ell} \le \frac{\theta(q\gm_{\ell+1})}{q} - \frac{\ell\log q +\sum_{j=1}^{\ell+1} \log\gm_j}{q}. \end{equation} Since $q \ge y$, the sequence $\Gamma$ being $y$-admissible is a fortiori $q$--admissible. Then, by using Equation \eqref{majqh} of Proposition~\ref{propg}, Equation \eqref{majDl} gives \dsm{ 0 < q D_{\ell} \le \log h(n), } from which, by using \eqref{majlogh} and \eqref{L3} to get upperbounds for $\log h(n)$, we obtain \begin{equation}\label{majb} q=\Pplus(h(n)) \le \min(b,b') \sqrt{n\log n}. \end{equation} \end{enumerate} Inequalities \eqref{l48} and \eqref{den2n} follow from \eqref{maja} and \eqref{majb}. \end{proof} \subsection{The optimal \texorpdfstring{$y$-admissible \gseq}{y\--admissible $G$-seq}}\label{gsuite2} The upper bound \eqref{majqh} in Proposition~\ref{propg} leads us to construct $y$-admissible \gseq s with $\gm_j$ as large as possible. This is the subject of this section. Let $y$ be $\ge 12$ and $(\gm_0 = 0, \gm_1=1/2, \gm_2)$ be a \gseq\ $y$--admissible of length $1$. By \eqref{defIJ}, $\gm_2 = \dfrac{1+\al_1}{2}$; thus, the largest value of $\gm_2$ is obtained by giving to $\al_1$ the largest possible value. By Remark \ref{m1rem}, we have $m_1=1$ so that, by Remark \ref{m2rem}, the sequence $(\gm_0 = 0, \gm_1=1/2, \gm_2)$ is $y$--admissible if and only if $\al_1 \le \frac{1}{4} \eta_2\big(\frac{y}{4}\big)$. So, we get the largest value for $\gm_2$ by setting $\al_1 = \frac{1}{4} \eta_2\big(\frac{y}{4}\big)$ and $\gm_2 = \frac{1+\al_1}{2}$. Now let $(\gm_j)_{0 \le j \le \ell+1}$ be a \gseq\ $y$--admissible of length $\ell$, that we want to extend. Equation \dsm{\gm_{\ell+1} = \bt_{\ell+1}^2} determines $\bt_{\ell+1}$. Equality \dsm{\gm_{\ell+2} = \frac{1+\al_{\ell+1}}{2}} shows that the largest value of $\gm_{\ell+2}$ is got by choosing $\al_{\ell+1}$ as large as possible. We set $m=1$ and we try \begin{equation}\label{choixalpha} \al_{\ell+1} = \bt_{\ell+1}\eta_{m+1}(y \bt_{\ell+1}). \end{equation} \begin{itemize} \item[--] If $\al_{\ell+1} \le \al_\ell$ our construction fails because it is not possible to satisfy $\gm_{\ell+1} = \dfrac{1+\al_\ell}{2}< \dfrac{1+\al_{\ell+1}}{2} = \gm_{\ell+2}$. \item[--] If $\al_{\ell+1} > \al_{\ell}$ let us consider \dsm{ I_{\ell+1} = \intfd{\al_{\ell+1}}{\bt_{\ell+1}}\!. } If this interval meets at most $m$ intervals among $J_0, J_1, \dots, J_\ell$, we finish by choosing $\gm_{\ell+2} = (1+\al_{\ell+1})/2$. If $I_{\ell+1}$ meets $m' > m$ intervals among $J_0, J_1, \dots, J_{\ell}$, we have to choose again $\al_{\ell+1}$ by using formula \eqref{choixalpha} with $m$ replaced by $m+1$. \end{itemize} More formally this construction is described in Algorithm~\ref{algo1}. This algorithm is not guaranteed to terminate; however, for $y=1853.18$, it gives the $y$--admissible \gseq\ of length $10$ which we will use in Section~\ref{parmajo}. \floatname{algorithm}{Algorithm} \renewcommand{\algorithmicrepeat}{\textbf{Repeat}} \renewcommand{\algorithmicuntil}{\textbf{until}} \renewcommand{\algorithmicendif}{} \renewcommand{\algorithmicif}{\textbf{if}} \renewcommand{\algorithmicthen}{\textbf{then}} \renewcommand{\algorithmicelse}{\textbf{else}} \begin{algorithm} \caption{ Computes $\al_{\ell+1}, \bt_{\ell+1}, \gm_{\ell+2}$ from $\gm_{\ell+1}$, $\al_\ell$ and $y$} \label{algo1} \begin{algorithmic} \STATE $\bt_{\ell+1} = \gm_{\ell+1}^2, \quad m=1$\\ \REPEAT \STATE{$\al_{\ell+1} = \bt_{\ell+1} \eta_{m+1}(y \bt_{\ell+1})$}\\ \STATE{ {\bf if} $\al_{\ell+1} \le \al_{\ell}$ {\bf return} FAIL}\\ \STATE{{\bf else} $m = m+1$}\\ \UNTIL{ $\intfd{\al_{\ell+1}}{\bt_{\ell+1}}$ meets at most $m$ intervals $\intfd{0}{\gm_1}, \ldots,\intfd{\gm_{\ell}}{\gm_{\ell+1}}$} \STATE $\gm_{\ell+2} = (1+\al_{\ell+1})/2$\\ \end{algorithmic} \end{algorithm} \subsection{Uniform \gseq s}\label{gsuiteuniforme} The theoretical study of optimal \gseq s does not seem easy. In this section we introduce the \emph{uniform} \gseq s, less efficient for numerical computation, but simpler to study. \begin{definition}\label{suitecanonique} Let $\eta$ be a real number, $0 < \eta < 1$. We define $\gm_0 = 0$ and, for $j \ge 1$, \begin{equation}\label{ecan} \gm_j = \gm_j(\eta) = \frac{1+\eta\gm_{j-1}^2}{2}. \end{equation} \end{definition} \begin{remark}\label{gmcroit} Let us note that $\gm_j(\eta)$ is an increasing function of $j$ and $\eta$. Note also that \begin{equation}\label{alphaj} \alpha_j = 2 \gm_{j+1}-1 = \eta \gm_{j}^2 = \eta \beta_j. \end{equation} \end{remark} \begin{lemma}\label{lemeps} With the notation of Definition \ref{suitecanonique}, let us write $\veps = \veps(\eta) = 1-\eta$, and $L_{\veps} = \lim_{j \to +\infty} \gm_j$. then \begin{equation}\label{gmlim} L_{\veps} = \frac{1}{1+\sqrt\veps} \qtx{ and, for $j \ge 0$, } L_{\veps} - \gm_j \le L_{\veps}(1-\sqrt\veps)^j \le (1-\sqrt\veps)^j\!. \end{equation} For each integer $\ell \ge 1$, the sequence $(\gm_j(\eta))_{0 \le j \le \ell+1}$ defined by \eqref{ecan} is a \gseq. We call it the \emph{uniform} \gseq\ of parameter $\eta$ and length $\ell$. \end{lemma} \begin{proof} The proof is by induction. We have $\gm_0 = 0$, $\gm_1 = \dfrac{1+\eta\gm_0^2}{2} = \dfrac12$, and, for $j \ge 1$, \[ \gm_{j+1} = \frac{1+\eta\gm_j^2}{2} < \frac{1+\gm_j^2}{2}. \] Moreover $\gm_{j+1} = f(\gm_j)$ with \dsm{f = t \mapsto (1+(1-\veps)t^2)/2}. Function $f$ is increasing for $t \ge 0$ and has two fix points which are \dsm{\frac{1}{1+\sqrt\veps}} and \dsm{\frac{1}{1-\sqrt\veps}}. Since \dsm{\gm_0 < \gm_1}, the sequence $(\gm_j)$ is increasing with limit $L_{\veps}=\dfrac{1}{1+\sqrt\veps}$. Moreover, since $f'$ is increasing, \begin{eqnarray*} L_{\veps} - \gm_{j} &=& f(L_{\veps}) - f(\gm_{j-1}) < f'(L_{\veps}) (L_{\veps} - \gm_{j-1}) = (1-\sqrt\veps)(L_{\veps} -\gm_{j-1})\\ &\le& (1-\sqrt\veps)^j(L_{\veps} -\gm_{0}) = L_{\veps}(1-\sqrt\veps)^j. \end{eqnarray*} For each $\ell \ge 1$, the conditions of Definition \ref{condgamma} are satisfied and $(\gm_j)_{0 \le j \le \ell}$ is a \gseq. \end{proof} Throughout this section $\eta$ is a positive real number satisfying $0 < \eta < 1$, $\veps = 1-\eta$, $(\gm_j)$ is the uniform \gseq\ of parameter $\eta$, and $I_j = \intfd{\al_j}{\bt_j}$, $J_j = \intfd{\gm_j}{\gm_{j+1}}$ are the intervals associated with this \gseq\ (cf.\ Definition \ref{condgamma}). \begin{lemma}\label{lemgn1n} Let us write $u_j = L_{\veps}-\gm_j$. Then $(\gm_{j+1}-\gm_j)$ is a decreasing sequence, and, for every $j$ we have \[ \gm_{j+1} - \gm_j = \sqrt\veps u_j + \frac{u_j^2}{2}(1-\veps). \] In particular \dsm{\sqrt\veps (L_{\veps}-\gm_j) < \gm_{j+1} - \gm_j}. \end{lemma} \begin{proof} Indeed, since $\gm_j = L_{\veps}-u_j = \dfrac{1}{1+\sqrt\veps}-u_j$, we have, with $f(t)=(1-(1-\veps t^2))/2$, \begin{eqnarray*} 2(\gm_{j+1} - \gm_j) &=& 2f(\gm_j) - 2\gm_j = 1 + (1-\veps)\gm_j^2 - 2\gm_j\\ &=& 1+ (1-\veps)\left(\frac{1}{1+\sqrt\veps}-u_j\right)^2 -\frac{2}{1+\sqrt\veps}+2u_j\\ &=& 2\sqrt\veps u_j + (1-\veps)u_j^2 > 2\sqrt{\veps}u_j = 2\sqrt{\veps}(L_{\veps}-\gm_j). \end{eqnarray*} \end{proof} \begin{lemma}\label{lem2g} There is no pair $(i,j)$ such that \dsm{\intfd{\gm_i}{\gm_{i+1}} \subset \intfd{\al_j}{\bt_{j}}}. Therefore each interval $I_j$ meets at most two intervals $J_i$. \end{lemma} \begin{proof} Let us suppose \dsm{\intfd{\gm_i}{\gm_{i+1}} \subset \intfd{\al_j}{\bt_j} }. Then \[ \al_j \le \gm_i < \gm_{i+1} \le \bt_j = \gm_j^2 \] and \begin{equation}\label{lgmn} L_{\veps}-\gm_i > L_{\veps}-\gm_j^2 > L_{\veps}-L_{\veps}^2 = L_{\veps}(1-L_{\veps}) = \sqrt\veps L_{\veps}^2. \end{equation} By Lemma \ref{lemgn1n}, we also have \[ \sqrt\veps(L_{\veps}-\gm_i) < \gm_{i+1}-\gm_i \le \bt_j-\al_j = \veps\bt_j = \veps\gm_j^2 < \veps L_{\veps}^2 \] which implies \dsm{L_{\veps}-\gm_i < \sqrt\veps L_{\veps}^2}, contradicting \eqref{lgmn}. \end{proof} \section{Estimates of \texorpdfstring{$\Pplus(h(n))$}{Pplus(h(n))}}\label{section6} In this section, we study the behavior of $\Pplus(h(n))$ in terms of $n$. The results are similar to those obtained in \cite{DN} for $\Pplus(g(n))$, except for the numerical value of the constants. \subsection{Maximum of \texorpdfstring{$P^{+}(h(n))/\sqrt{n \log n}$}{Pplus(h(n))} for \texorpdfstring{$n \ge 4$}{n >= 4}.}\label{parmajo} \begin{theorem}\label{t1} For $n \ge 4$ we have \begin{equation}\label{th1.1} \frac{\Pplus(h(n))}{\sqrt{n \log n}} \le \frac{\Pplus(h(170))}{\sqrt{170 \log(170)}} = 1.38757162\cdots\!, \end{equation} the maximum being attained only for $n=170$ with $h(170) = 2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 \times 23 \times 29 \times 41 = N_{10} \times 41$ and $\Pplus(h(170)) = 41$. \end{theorem} \begin{proof} We use Proposition~\ref{prop3} with $n_0=150\,000$, $a = 1.386$ and $y = 1853.18$. Using Algorithm~\ref{algo1} we compute the first 10 terms of the optimal $y$--admissible \gseq. We get intervals \medskip \begin{center} \begin{small} \begin{tabular}{|l|l|l|l|l|l|} \hline $j$ & $\al_j$ & $\bt_j$ & $\gm_{j+1}$ & $\set{i}$ & $ D_j$\\ \hline $1$ & $0.2390\cdots$ & $0.2500\cdots$ & $0.619515\cdots$ & $0$ & $0.582374\cdots$\\ $2$ & $0.3722\cdots$ & $0.3837\cdots$ & $0.686121\cdots$ & $0$ & $0.641498\cdots$\\ $3$ & $0.4569\cdots$ & $0.4707\cdots$ & $0.728463\cdots$ &$0$ & $0.677646\cdots$\\ $4$ & $0.5150\cdots$ & $0.5306\cdots$ & $0.757531\cdots$ &$1$ & $0.701222\cdots$\\ $5$ & $0.5569\cdots$ & $0.5738\cdots$ & $0.778493\cdots$ &$1$ & $0.724454\cdots$\\ $6$ & $0.5882\cdots$ & $0.6060\cdots$ & $0.794120\cdots$ &$1$ & $0.737558\cdots$\\ $7$ & $0.6094\cdots$ & $0.6306\cdots$ & $0.804703\cdots$ &$1, 2$ & $0.745702\cdots$\\ $8$ & $0.6285\cdots$ & $0.6475\cdots$ & $0.814257\cdots$ &$2$ & $0.750926\cdots$\\ $9$ & $0.6435\cdots$ & $0.6630\cdots$ & $0.821764\cdots$ &$2$ & $0.754179\cdots$\\ $10$& $0.6554\cdots$ & $0.6752\cdots$ & $0.827725\cdots$ &$2$ & $0.755943\cdots$\\ \hline \end{tabular} \end{small} \end{center} Column $\set{i}$ contains the values $i$ for which $I_j$ meets $J_i$, so that $m_j$ is the number of integers appearing in the $j^{\text{th}}$ line of the column $\set{i}$. \medskip This gives $D_{10} = 0.755943\cdots$ and, with \eqref{l48}, $b = 1.386614\cdots > a$ which proves that $\Pplus(h(n)) < 1.3867 \sqrt{n \log n}$ for $n \ge 150\,000$. The computation of $h(n)$ for $4 \le n \le 150\,000$ shows that the maximum is obtained only once, for $n = 170$. \end{proof} \begin{lemma}\label{lem12} Let $q$ be a prime factor of $h(n)$ and $\eta \le \eta_3(q/4)$ ; let $\Gamma=(\gm_{j})_{0 \le j \le \ell+1}$ be the uniform \gseq\ of parameter $\eta$. This sequence is $q$--admissible, and \begin{equation}\label{eq11} \theta(q\gm_{\ell+1}) - \ell\log q \le \log h(n). \end{equation} \end{lemma} \begin{proof} By Lemma \ref{lem2g}, each interval $I_j$ meets at most $2$ intervals $J_j$. Thus, the integer $m_j$ introduced in Definition \ref{defadmiss} satisfies $m_j \le 2$ for every $j$. Equality \eqref{alphaj}, the inequality $\bt_1 = \dfrac{1}{4} \le \bt_j$ and the fact that $\eta_3$ is nondecreasing give \[ \al_j = \eta \bt_j \le \bt_j \eta_3(q/4) \le \bt_j \eta_3(q\bt_j). \] Thus Inequality~\eqref{eq:admiss} holds with $m=3$ and $y=q$, and Lemma \ref{lem:admiss} shows that the sequence $\Gamma$ is $q$-admissible. Therefore, from Proposition~\ref{propg}, Eq.~\eqref{eq11} holds. \end{proof} \begin{lemma}\label{qmaj} Let $n$ be an integer and $q$ the largest prime factor of $h(n)$. When $n$ tends to infinity, we have \begin{equation}\label{Pplusmaj} q = \Pplus(h(n)) \le \log h(n) (1+ \bigo{\veps}), \end{equation} with $\veps = \veps_1 + \sqrt\veps_2 \to 0$ and \begin{equation}\label{defeps1eps2} \veps_1 = \max_{x \ge \frac{q}{2}}\abs{\frac{\theta(x)}{x}-1}, \qquad \veps_2 = \max\left( 1-\eta_3\Big(\frac{q}{4}\Big), \pfrac{\log q}{\sqrt q}^2 \right) < 1. \end{equation} \end{lemma} \begin{proof} Let us write \begin{equation}\label{defl} \eta = 1-\veps_2 \qtx{ and } \ell=\intfrac{\log q}{\sqrt\veps_2}. \end{equation} When $n \to +\infty$, by \eqref{PplusGepk}, $q = \Pplus(h(n))$ tends to infinity, $\veps_1$ tends to $0$, $\eta_3(q/4)$ tends to $1$ (by Proposition~\ref{propmin}), $\veps_2$ and $\veps$ tend to $0$ and $\ell$ tends to infinity. Let $\Gamma = (\gm_{j})_{0 \le j \le \ell+1}$ be the uniform \gseq\ of parameter $\eta$ and length $\ell$. Since $\Gamma$ is increasing, we have $q\gm_{\ell+1} \ge q\gm_1 = q/2$. By the definition of $\veps_1$, it comes \dsm{ \frac{\theta(q\gm_{\ell+1})}{q\gm_{\ell+1}} \ge 1 - \veps_1, } therefore, with the notation of Lemma \ref{lemeps}, \begin{eqnarray}\nonumber \frac{\theta(\gm_ {\ell+1} q)}{q} &\ge& \gm_{\ell+1} - \gm_{\ell+1} \veps_1\\ &\ge& \gm_{\ell+1} - \veps_1 = 1 - \veps_1 - (1-L_{\veps_2}) - (L_{\veps_2}-\gm_{\ell+1}). \label{l121} \end{eqnarray} One use of Lemma \ref{lemeps} gives \begin{equation}\label{l122} 1-L_{\veps_2} = 1 - \frac{1}{1+\sqrt\veps_2} \le \sqrt\veps_2. \end{equation} By \eqref{defl}, $\ell+1 > \dfrac{\log q}{\sqrt\veps_2}$; then a second use of Lemma \ref{lemeps} gives \begin{equation*} L_{\veps_2} - \gm_{\ell+1} \le (1-\sqrt\veps_2)^{\ell+1} \le (1-\sqrt\veps_2)^{\frac{\log q}{\sqrt\veps_2}} \le \pfrac{1}{e}^{\log q} = \frac{1}{q}. \end{equation*} With \eqref{l121}, \eqref{l122} and the definition of $\veps$ we get \begin{equation}\label{qgkp1q} \frac{\theta(q\gm_{\ell+1})}{q} \ge 1 - \veps_1 - \sqrt\veps_2 - \frac{1}{q} = 1 - \veps - \frac{1}{q}. \end{equation} Definition \eqref{defl} of $\ell$ gives \dsm{ \ell \frac{\log q}{q} \le \dfrac{(\log q)^2}{q \sqrt\veps_2} . } With \eqref{qgkp1q}, this gives \[ \frac{\theta(q\gm_{\ell+1})}{q} - \ell \frac{\log q}{q} \ge 1-\veps - \dfrac{1}{q} - \frac{\log^2 q}{q\sqrt\veps_2}. \] By the definition of $\veps_2$, for $q \ge 3$, we have \dsm{\frac{1}{q} \le \frac{\log^2 q}{q} \le \veps_2 \le \sqrt{\veps_2}}, and therefore \begin{equation}\label{minden} \frac{\theta(q\gm_{\ell+1})}{q} - \ell \frac{\log q}{q}\ge 1 - \veps - \frac{1}{q} - \sqrt{\veps_2} \ge 1 - \veps -2\sqrt\veps_2 \ge 1 - 3\veps. \end{equation} By the definition of $\veps_2$ and $\eta$ (cf.\ \eqref{defeps1eps2}) and \eqref{defl}), we have \dsm{\eta \le \eta_3\left(\frac{q}{4}\right)}, so that Lemma \ref{lem12} applies to the \gseq\ $\Gamma$. Inequality \eqref{minden} shows that $\theta(q\gm_{\ell+1}) - \ell \log q$ is positive for $n$ large enough, so that, by using \eqref{eq11} and \eqref{minden}, we may write \[ q \le \frac{\log h(n)}{\frac{\theta(q\gm_{\ell+1})}{q} - \ell \frac{\log q}{q}} \le \frac{\log h(n)}{1-3\veps} = \log h(n)(1+\bigo{\veps}). \] \end{proof} \begin{proposition}\label{Pplusequiv} When $n$ tends to infinity, $\Pplus(h(n)) \sim \sqrt{n \log n}$. \end{proposition} \begin{proof} Let us write $q=\Pplus(h(n))$. By \eqref{PplusGepk}, $q$ tends to infinity with $n$. Using successively the prime number theorem and Inequality \eqref{Pplustheta}, we get \begin{equation*}\label{} q \sim\theta(q) \ge \log h(n). \end{equation*} With \eqref{Pplusmaj}, this gives $q \sim \log h(n)$, and ends the proof with Theorem~\ref{th2}. \end{proof} \subsection{Asymptotic upper bound for \texorpdfstring{$\Pplus(h(n))$}{Pplus(h(n))}} \begin{theorem}\label{t2} Let $P^{+}(h(n))$ be the largest prime factor of $h(n)$. When $n$ tends to infinity, $\Pplus(h(n))$ is bounded as follows: \begin{enumerate} \item Without any hypothesis, there exists $a > 0$ such that \begin{equation}\label{truemaj} \Pplus(h(n)) \le \sqrt{\Li^{-1}(n)} + \bigo{\sqrt n e^{-a\sqrt{\log n}}}. \end{equation} \item Under the Riemann Hypothesis: \begin{equation}\label{Riemanmaj} \Pplus(h(n)) \le \sqrt{\Li^{-1}(n)} + \bigo{n^{3/8}(\log n)^{7/8}}. \end{equation} \item Under the Riemann Hypothesis and the Cram\'{e}r conjecture (Equation \eqref{conjcra}): \begin{equation}\label{Pplusjcra} \Pplus(h(n)) \le \sqrt{\Li^{-1}(n)} + \bigo{n^{1/4}(\log n)^{9/4}}. \end{equation} \end{enumerate} \end{theorem} \begin{proof} Let us write $q=\Pplus(h(n))$. By Proposition~\ref{Pplusequiv} we have \begin{equation}\label{qequiv} q \sim \sqrt{n \log n} \qtx{ and } \log q \sim \frac{1}{2} \log n. \end{equation} We shall also use the relation \begin{equation}\label{L1equiv} \Li^{-1}(n) \sim n \log n. \end{equation} We will apply Lemma \ref{qmaj}, evaluating in the three cases the quantities $\veps_1$, $\veps_2$ and $\veps = \veps_1 + \sqrt{\veps_2}$. \begin{enumerate} \item By the prime number theorem \eqref{TNP1}, there is some $a_1 > 0$ such that \[ \veps_1 = \bigo{e^{-a_1\sqrt{\log n}}}. \] By Proposition~\ref{propmin}, ({\sl i}), we have \[ 1-\eta_3\left(\frac{q}{4}\right) = \bigo{q^{-0.475}}. \] Thus, by \eqref{qequiv}, \begin{equation*}\label{} \sqrt\veps_2 = \bigo{q^{-0.2375}} = \bigo{n^{-0.11875}} \end{equation*} and $\veps = \veps_1 + \sqrt{\veps_2} =\bigo{\exp(-a_1\sqrt{\log n}}$. Lemma \ref{qmaj} gives the inequality \begin{equation}\label{majq1} q \le (\log h(n)) \Big(1+ \bigo{\exp(-a_1\sqrt{\log n})} \Big). \end{equation} By \eqref{asym1} there is $a_2 > 0$ such that \[ \log h(n) = \sqrt{\Li^{-1}(n)} + \bigo{\sqrt ne^{-a_2\sqrt{\log n}}} \] which, with \eqref{majq1} and \eqref{L1equiv}, proves \eqref{truemaj} for $a < \min(a_1,a_2)$. \item Under the Riemann hypothesis, we have, by \eqref{TNP2}, \begin{equation}\label{majeps1R} \veps_1 = \bigo{\frac{\log^2 q}{\sqrt q}} \end{equation} and Inequality \eqref{eq:etaprox} of Proposition~\ref{propmin} gives \[ 1-\eta_3\pfrac{q}{4} = \bigo{\frac{\log q}{\sqrt q}}. \] We thus get \dsm{ \veps_2 = \bigo{\frac{\log q}{\sqrt q}} } and, by \eqref{qequiv} \[ \veps = \veps_1 + \sqrt{\veps_2} = \bigo{\frac{\sqrt{\log q}}{q^{1/4}}} = \bigo{\frac{(\log n)^{3/8}}{n^{1/8}}}, \] so that, by Lemma \ref{qmaj}, \begin{equation*} q \le \log h(n) \left(1 + \bigo{\frac{(\log n)^{3/8}}{n^{1/8}}}\right), \end{equation*} which, with \eqref{asym3} and \eqref{L1equiv}, yields \eqref{Riemanmaj}. \item Estimate \eqref{majeps1R} is still true, while the definition \eqref{defeps1eps2} of $\veps_2$ and Equation \eqref{etacra} for $k=3$ give $\veps_2 = \bigo{\dfrac{\log^2 q}{q}}$ and then \[ \veps = \bigo{\frac{\log^2 q}{\sqrt q}} = \bigo{\frac{(\log n)^{7/4}}{n^{1/4}}}, \] which, by Lemma \ref{qmaj}, \eqref{asym3} and \eqref{L1equiv}, proves \eqref{Pplusjcra}. Let us remark that \eqref{Pplusjcra} is still true if we replace Cram\'{e}r's conjecture \eqref{conjcra} by the weaker relation \dsm{ p_{i+1} - p_i = \bigo{\log^4 p_i}. } \end{enumerate} \end{proof} \subsection{Effective upper bound for \texorpdfstring{$\Pplus(h(n))$}{Pplus(h(n))}} \begin{theorem}\label{t3} $\Pplus(h(n))$ satisfies the following inequalities \begin{equation}\label{eqt3} \Pplus(h(n)) \le \log h(n) \bigg(1+\frac{1.012}{\log n}\bigg) \quad(n \ge 138\,940). \end{equation} \begin{equation}\label{eqt3bis} \Pplus(h(n)) \le \sqrt{n\log n}\left(1 + \frac{\lgd n+1.145}{2\log n}\right) \quad(n \ge 233\,089). \end{equation} \end{theorem} \begin{proof} The computation of $\Pplus(h(n))$ and $\log(h(n))$ for $2 \le n \le 10^{10}$, shows that Inequalities \eqref{eqt3} and \eqref{eqt3bis} are satisfied for these values of $n$. Let us suppose $n > 10^{10}$, and that $q=\Pplus(h(n))$ satisfies \begin{equation}\label{qsqrtn} q > \log h(n)\left(1+ \frac{1}{\log n}\right). \end{equation} Since $n \ge 10^{10}> 7387$, it results from \eqref{largersqrtnlogn} that \[ q > \sqrt{n \log n}\left(1+ \frac{1}{\log n}\right) = \sqrt{n} \left(\sqrt{\log n} + \frac{1}{\sqrt{\log n}} \right). \] Since $t \mapsto t + 1/t$ for $t \ge 1$ is increasing this gives \[ q > \sqrt{n}\left(\sqrt{\log 10^{10}}+ \frac{1}{\sqrt{\log 10^{10}}} \right) \ge 5.006923\sqrt{n} > 500\,692. \] \noindent Therefore, \begin{equation}\label{qnmin} q \ge 500\,693,\qquad 0.25\, q \ge 125\,173 \end{equation} and \begin{equation}\label{log25q} \log(0.25\, q) > \log (0.25 \times 5.00693\sqrt{n}) > \log(\sqrt{n}) = 0.5 \log n. \end{equation} Here we define $\eta$ and $\veps$ by \begin{equation}\label{defeta} \veps = \frac{0.4822}{\log^2 n} \qtx{ and } \eta = 1-\veps. \end{equation} From \eqref{defeta} we deduce \begin{equation}\label{minsqrteps} \frac{0.6944}{\log n} \le \sqrt{\veps} \le \frac{0.6945}{\log n} \end{equation} and, also, with $n \ge 10^{10}$, \begin{equation}\label{minunmoinseps} \veps < 0.00091 \qtx{ and } \eta = 1-\veps > 0.99909. \end{equation} From the table \cite[Tabulation de delta3]{Htables}, we get $\dt_3(85\,991)= 0.120544\cdots$, which, with the fact that $\dt_3$ is nonincreasing (cf.\ \S 3.6) and \eqref{qnmin}, implies $0.12055 \ge \dt_3(85\,991) \ge \dt_3(125\,173) \ge \dt_3(0.25 q)$. Therefore, Definition \eqref{defeta} of $\veps$ and the lower bound \eqref{log25q} give \begin{equation}\label{majeps} \veps = \frac{0.4822}{\log^2 n} \ge \frac{0.12055}{\left(\log(0.25\,q)\right)^2} \ge \frac{\dt_3(0.25\, q)}{\left(\log(0.25\,q)\right)^2}. \end{equation} From \eqref{majeps}, with \eqref{pd3}, (where we take $x=y=0.25\,q$), we get \[ \eta = 1 - \veps \le 1 - \frac{\dt_3(0.25\, q)}{\left(\log(0.25\,q)\right)^2} \le \eta_3\left(0.25\,q \right). \] The uniform \gseq\ of parameter $\eta$ satisfies the hypothesis of Lemma \ref{lem12}. We apply this lemma, choosing \begin{equation}\label{defkeff} \ell = \lfloor 2.5\,\log n \log_2 n \rfloor \ge\lfloor 2.5\,\log 10^{10} \log_2 10^{10} \rfloor = 180. \end{equation} We have seen (cf.\ Remark \ref{gmcroit}) that $\gm_j = \gm_j(\eta)$ is an increasing function of $\eta$ and $j$. Since, by \eqref{minunmoinseps}, $\eta > 0.99909$ and $\ell \ge 180$ we have $\gm_{\ell+1} \ge \gm_{180}(0.99909) > 0.9705$. By using \eqref{qnmin} and \eqref{log25q}, we get \[ q\gm_{\ell+1} \ge 0.9705 \cdot 500\,693\ge 485\,922 \qtx{ and } \log q\gm_{\ell+1} \ge \log 0.25\, q \ge 0.5 \log n. \] The table of $\thd$-champion numbers given in \cite[Tabulation de thetad]{Htables} yields $\thd(485\,922) \le 0.3644$, so that, from \eqref{propthetad}, we get \begin{equation}\label{thetaqq} \frac{\theta(q\gm_{\ell+1})}{q\gm_{\ell+1}} \ge 1 - \frac{\thd(485\,922)}{(\log q\gm_{\ell+1})^2} \ge 1 - \frac{0.3644}{(\log q\gm_{\ell+1})^2} \ge 1 - \frac{1.4576}{(\log n)^2}. \end{equation} Using $n \ge 10^{10}$, this gives \begin{equation}\label{minqgmq} \frac{\theta(q\gm_{\ell+1})}{q} \ge \left(1 - \frac{1.4576}{\log^2 n}\right)\gm_{\ell+1} \ge \left(1-\frac{0.0634}{\log n} \right)\gm_{\ell+1}. \end{equation} Now we have to get a lower bound for $\gm_{\ell+1}$. From \eqref{gmlim}, using \eqref{minsqrteps} and \eqref{defkeff}, we deduce \begin{eqnarray*} \gm_{\ell+1} &\ge& \frac{1}{1+\sqrt\veps} - \left(1-\sqrt{\veps}\right)^{\ell+1} \ge 1 - \sqrt{\veps} - \left(1-\frac{0.6944}{\log n} \right)^{\ell+1}\\ &\ge& 1-\sqrt{\veps} - \left(1-\frac{0.6944}{\log n} \right)^{2.5\, \log_2 n \log n} \\ &\ge& 1 - \sqrt{\veps} - \left[\left(1-\frac{0.6944}{\log n}\right)^{\frac{\log n}{0.6944}}\ \right]^{2.5\,\times 0.6944\, \log_2(n)}\\ &\ge& 1 - \frac{0.6945}{\log n} - \frac{1}{(\log n)^{2.5\times0.6944}} \ge 1-\frac{0.794}{\log n}. \end{eqnarray*} With \eqref{minqgmq}, this gives \begin{equation}\label{eq1f} \frac{\theta(q\gm_{\ell+1})}{q} \ge \left(1-\frac{0.0634}{\log n} \right) \left( 1-\frac{0.794}{\log n} \right) \ge 1 - \frac{0.8574}{\log n} + \frac{0.05034}{\log^2 n}. \end{equation} Since \dsm{\frac{\log t}{t}} is a decreasing function of $t$ for $t \ge e$, and $q \ge \sqrt{n\log n}$, we have \[ \frac{\log q}{q} \le \frac{1}{2}\frac{\log(n\log n)}{\sqrt{n\log n}}. \] Using\eqref{defkeff} and the fact that \dsm{t \mapsto (\log t)^{3/2} \log_2 t \log(t \log t)/\sqrt t} is decreasing for $t \ge 10^{10}$, this gives \begin{equation}\label{eq2f} \ell\frac{\log q}{q} \le 1.25\,\log n \log_2 n \frac{\log(n\log n)}{\sqrt{n\log n}} \le \frac{0.114}{\log n}. \end{equation} Since the inequality $\log n > 0.9714$ holds, Formula \eqref{eq11} of Lemma~\ref{lem12}, with \eqref{eq1f} and \eqref{eq2f} give \[ q \le \frac{\log h(n)}{1-\dfrac{0.9714}{\log n}+\dfrac{0.05034}{\log^2 n}}. \] On the interval $0 \le X \le 1/\log 10^{10}$, the fraction \dsm{\frac{0.9714 - 0.05034 X}{1-0.9714 X + 0.05034 X^2}} is increasing and less than $1.012$. This implies, for $n \ge 10^{10}$, \[ \frac{1}{1-\dfrac{0.9714}{\log n}+\dfrac{0.05034}{\log^2 n}} = 1 + \frac{\dfrac{0.9714}{\log n}-\dfrac{0.05034}{\log^2 n}}{1-\dfrac{0.9714}{\log n}+\dfrac{0.05034}{\log^2 n}} \le 1+\dfrac{1.012}{\log n} \] which, with \eqref{qsqrtn}, proves \eqref{eqt3}. Applying \eqref{L3}, we deduce from that \begin{eqnarray*} q &\le& \sqrt{n\log n} \left(1+\frac{\log_2 n-0.975}{2\log n} \right) \left(1+\dfrac{1.012}{\log n}\right) \\ &\le& \sqrt{n\log n} \left(1+\frac{\log_2 n+1.049}{2\log n} + \dfrac{1.012}{\log n}\frac{\log_2 n-0.975}{2\log n} \right)\\ &\le& \sqrt{n\log n} \left(1+\frac{\log_2 n+1.049}{2\log n} + \dfrac{1}{2\log n}\dfrac{1.012(\log_2 10^{10}-0.975)}{\log 10^{10}} \right) \end{eqnarray*} which completes the proof of \eqref{eqt3bis}. \end{proof} \subsection{Lower bound for \texorpdfstring{$\Pplus(h(n))$}{Pplus(h(n))}} \begin{lemma} For all $n \ge 7387$, we have \begin{equation}\label{minp2} \Pplus(h(n)) \ge \frac{\sqrt{n \log n}}{1.000028}. \end{equation} \begin{proof} From \eqref{Pplustheta} we have $\log h(n) \le \theta(\Pplus(h(n)))$. Inequalities \eqref{largersqrtnlogn} and \eqref{T2} end the proof. \end{proof} \end{lemma} \begin{theorem}\label{t4} For $n \ge 7\,992$ we have \begin{equation}\label{t51} \Pplus(h(n)) \ge \sqrt{n \log n}\left(1+\frac{\lgd n - 1.18}{2\log n} \right), \end{equation} and, for $n \ge 21$ \begin{equation}\label{t52} \Pplus(h(n)) \ge \sqrt{n \log n}. \end{equation} \end{theorem} \begin{proof} First, we compute $h(n)$ and $\Pplus(h(n))$ for $n \le 10^8$ and we verify that \eqref{t51} is true for $7\, 992 \le n \le 10^8$ and false for $n=7\,991$, and that \eqref{t52} is true for $21 \le n \le 10^8$ and false for $n=20$. Let us note that for $n > 10^8$ Eq.~\eqref{t52} is implied by Eq.~\eqref{t51}, since $\lgd n > \lgd 10^8 = 2.913\cdots > 1.17$. Thus it remains to prove that Eq.~\eqref{t51} is true for $n > 10^8$. Let us write $q=\Pplus(h(n))$. From Eq.~\eqref{Pplustheta}, we have $\log h(n) \le \theta(q)$. With Eq.~\eqref{min1.16} this gives \begin{equation}\label{more1.5e7} \sqrt{n \log n} \left(1 + \frac{\log_2 n-1.16}{2 \log n} \right) \le \log h(n) \le \theta(q). \end{equation} \begin{enumerate} \item If $n_0 = 10^8 < n \le n_1 = 6.6\times 10^{21}$, by Eq.~\eqref{th1.1}, we get \begin{equation}\label{8e11} q \le 1.388 \sqrt{n \log n} \le 8 \times 10^{11}. \end{equation} Thus, by Eq.~\eqref{T2} we have $\theta(q) < q$, which, with Eq.~\eqref{more1.5e7}, implies inequality~\eqref{t51}. \item If $ n > n_1 = 6.6\times 10^{21}$. By Eq.~\eqref{minp2}, $q = \Pplus(h(n))$ satisfies \[ q > 5.7 \times 10^{11}, \] and, by Eq.~\eqref{T4}, \[ \theta(q) - q \le 0.05 \frac{q}{\log^2q} < \frac{0.05}{\log(5.7\times 10^{11})}\frac{q}{\log q} < 0.002 \frac{q}{\log q}. \] With Eq.~\eqref{more1.5e7} this gives \begin{equation}\label{t53} \sqrt{n \log n}\left(1+\frac{\log_2 n-1.16}{2\log n}\right) < q + 0.002\frac{q}{\log q}. \end{equation} Using Eq.~\eqref{minp2} we have $q > \sqrt n$ and $\log q >(\log n)/2$. With Eq.~\eqref{th1.1}, we get \[ \frac{q}{\log q} < \frac{1.388\sqrt{n \log n}}{\log q} < \frac{1.388\sqrt{n\log n}}{\frac{1}{2} \log n} = 5.552\frac{\sqrt{n\log n}}{2\log n}. \] By noticing that $0.002 \times 5.552 < 0.02$, we deduce from Eq.~\eqref{t53} that, for $n \ge 6.6 \times 10^{21}$, we have \[ q = \Pplus(h(n)) > \sqrt{n \log n} \left(1+\frac{\log_2 n -1.18}{2\log n} \right), \] which ends the proof of Theorem~\ref{t4}. \end{enumerate} \end{proof} \begin{theorem}\label{t5} \begin{enumerate} \item There exists two positive constants $C$ and $a$ such that, for $n \ge 2$, \begin{equation}\label{t61} \Pplus(h(n)) \ge \sqrt{\Li^{-1}(n)} -C \sqrt{n} \exp(-a \sqrt{\log n}). \end{equation} \item Under the Riemann hypothesis, there exists a positive constant $C'$ such that \begin{equation}\label{t62} \Pplus(h(n)) \ge \sqrt{\Li^{-1}(n)} - C'n^{1/4}(\log n)^{9/4}. \end{equation} \end{enumerate} \end{theorem} \begin{proof} This is similar to the proof of \cite[Theorem 9.2]{DN} and follows by using Eqs.~\eqref{TNP1}, \eqref{TNP3}, and \eqref{Pplustheta}, and the lower bounds of $\log h(n)$ given in Eqs.~\eqref{asym1} and \eqref{asym3}. \end{proof} \subsection{Comparison of \texorpdfstring{$\Pplus(h(n))$}{Pplu(h(n))} and \texorpdfstring{$\log h(n)$}{log h(n)}} \begin{lemma}\label{lem osc} There exist infinitely many prime numbers $p$ such that $\theta(p) < p$ and infinitely many prime numbers $p$ such that $\theta(p) > p$. \end{lemma} \begin{proof} This is \cite[Lemma 10.1]{DN}, based on Littlewood's oscillation theorem. \end{proof} \begin{theorem}\label{thm:pplus_logh} There exist infinitely many values of $n$ such that $\Pplus(h(n)) > \log(h(n))$ and infinitely many values of $n$ such that $\Pplus(h(n)) < \log(h(n))$. \end{theorem} \begin{proof} Let us consider the values $n$ belonging to the sequence $(\sk)$. For such an $n$, $n=p_1+p_2+\cdots+p_{k}$, we have (cf.\ Eq.~\eqref{hsj}) \[ h(n) = N_k, \quad \log h(n) = \theta(p_k), \quad \Pplus (n) = p_{k}, \] so that $\Pplus(h(n)) - \log h(n) = p_k - \theta(p_k)$. By Lemma \ref{lem osc}, there are infinitely many values of $k$ for which this quantity is positive, and infinitely many values of $k$ for which it is negative. \end{proof} \begin{proposition}\label{prop:Ppluslt} Let $p_{k_0}$ be the smallest prime such that $\theta(p_{k_0}) > p_{k_{0}}$ holds, and $n_0$ the smallest integer such that $\Pplus(h(n_0)) < \log h(n_0)$. Then we have \begin{equation}\label{pk0n0} \sigma_{k_0-2} + p_{k_0} \le n_0 < \sigma_{k_0}. \end{equation} \end{proposition} \begin{proof} From Eqs.~\eqref{def:Nj} and \eqref{hsj}, we get \[ \log h(\sigma_{k_0}) = \theta(p_{k_{0}}) > p_{k_{0}} = \Pplus(N_{k_{0}}) = \Pplus(h(\sigma_{k_0}), \] which proves the upper bound $n_0 \le \sigma_{k_{0}}$. Now, let $n$ satisfy $n < \sigma_{k_0-1}$ so that $k=k(n)$ satisfies $k < k_0-1$, $\sk \le n < \skp$, $\theta(p_k) < p_k$ (as $\theta(p_k)$ is transcendental, it cannot be equal to $p_k$) and $\theta(p_{k+1}) < p_{k+1}$. If $\sk \le n < \skp-p_{k}$, by Proposition~\ref{prop2.2} (i), we get \[ \log h(n) = \log N_{k} = \theta(p_{k}) < p_{k} = \Pplus(N_k) = \Pplus(h(n)). \] If $\skp-p_k \le n< \skp$, by Eq.~\eqref{boundhn} and Proposition~\ref{prop2.2} (ii), we have \[ \log h(n) \le \log N_{k+1} = \theta(p_{k+1}) < p_{k+1} \le \Pplus(h(n)) \] which shows $n_0 \ge \sigma_{k_0-1}$. It remains to study the case $\sigma_{k_0-1} \le n < \sigma_{k_0-2} + p_{k_0}$. By Proposition~\ref{prop2.2} (i), we get $\log h(n) = \theta(p_{k_0-1}) < p_{k_0-1} = \Pplus(N_{k_0-1}) = \Pplus(h(n))$. \end{proof} \begin{corollary} For $n \le 11\,896\,693\,289\,932\,185\,243\,249$, we have $\log h(n) < \Pplus(h(n))$. \end{corollary} \begin{proof} The value of $p_{k_0}$ is still unknown. From Eq.~\eqref{thetaxlx}, we know that $p_{k_0} \ge p_{k_1} =800000000047$, the smallest prime exceeding $8 \cdot 10^{11}$. Therefore, we have $p_{k_1-2} = 799999999889$, $\sigma_{p_{k_1-2}} = 11896693289132185243203$ and \[ n_0 \ge \sigma_{k_1-2} + p_{k_1} = 11\,896\,693\,289\,932\,185\,243\,250. \] \end{proof} \begin{remark} There are $3\, 272$ numbers $\le 10^6$ such that $\Pplus(g(n)) > \log g(n)$ (cf.\ \cite[\S 10]{DN}). \end{remark} \begin{thebibliography}{10} \bibitem{BHP} R.~C. Baker, G.~Harman, and J.~Pintz, The difference between consecutive primes. {II}, {\em Proc. London Math. Soc.} {\bf 83} (2001), 532--562. \bibitem{CRA} Harald Cram{\'e}r, On the order of magnitude of the difference between consecutive prime numbers, {\em Acta Arith.} {\bf 2} (1936), 23--46. \bibitem{Htables} M. Del\'eglise, web pages, \url{http://math.univ-lyon1.fr/~deleglis/Htables.html}. \bibitem{DN} M.~Del{\'e}glise and J.-L. Nicolas, Le plus grand facteur premier de la fonction de {L}andau, {\em Ramanujan J.} {\bf 27} (2012), 109--145. \bibitem{DNS} Marc Del{\'e}glise and Jean-Louis Nicolas, Maximal product of primes whose sum is bounded, {\em Proc. Steklov Inst. Math.} {\bf 282} (Issue 1, Supplement) (2013), 73--102. \bibitem{DNZ} Marc Del{\'e}glise, Jean-Louis Nicolas, and Paul Zimmermann, Landau's function for one million billions, {\em J. Th\'eor. Nombres Bordeaux} {\bf 20} (2008), 625--671. \bibitem{DUS10} P.~Dusart, Estimates of some functions over primes without {R}. {H}., preprint, 2010, \url{http://arxiv.org/abs/1002.0442v1}. \bibitem{EMF} William~John Ellison, {\em Les Nombres Premiers}, Hermann, Paris, 1975. \newblock En collaboration avec Michel Mend{\`e}s France, Publications de l'Institut de Math{\'e}matique de l'Universit{\'e} de Nancago, No.~IX, Actualit{\'e}s Scientifiques et Industrielles, No. 1366. \bibitem{GRA} Jon Grantham, The largest prime dividing the maximal order of an element of {$S\sb n$}, {\em Math. Comp.} {\bf 64} (1995), 407--410. \bibitem{INGHAM32} A.~E. Ingham, {\em The Distribution of Prime Numbers}, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1990. \bibitem{LAN2} E.~Landau, \"{U}ber die Maximalordnung der Permutationen gegebenen Grades, {\em Archiv. der Math. und Phys.} {\bf 5} (1903), 92--103. \newblock {\em Handbuch der Lehre von der Verteilung der Primzahlen}, I, 2nd ed., Chelsea, 1953, pp.~222--229. \bibitem{MNRAA} J.-P. Massias, J.-L. Nicolas, and G.~Robin, \'{E}valuation asymptotique de l'ordre maximum d'un \'el\'ement du groupe sym\'etrique, {\em Acta Arith.} {\bf 50} (1988), 221--242. \bibitem{Mas} Jean-Pierre Massias, Majoration explicite de l'ordre maximum d'un \'el\'ement du groupe sym\'etrique, {\em Ann. Fac. Sci. Toulouse Math.} {\bf 6} (1984), 269--281. \bibitem{MNRMC} Jean-Pierre Massias, Jean-Louis Nicolas, and Guy Robin, Effective bounds for the maximal order of an element in the symmetric group, {\em Math. Comp.} {\bf 53} (188) (1989), 665--678. \bibitem{Nicy} Thomas~R. Nicely, New maximal prime gaps and first occurrences, {\em Math. Comp.} {\bf 68} (227) (1999), 1311--1315. \bibitem{TheseJLN} J.-L. Nicolas, Ordre maximum d'un \'{e}l\'{e}ment du groupe de permutations et highly composite numbers, {\em Bull. Soc. Math. France} {\bf 97} (1969), 129--191. \bibitem{CRASJLN} J.-L. Nicolas, Ordre maximal d'un \'{e}l\'{e}ment d'un groupe de permutations, {\em C.R. Acad. Sci. Paris} {\bf 270} (1970), 1473--1476. \bibitem{MPE} J.-L. Nicolas, On {L}andau's function $g(n)$. \newblock In Ronald~L. Graham and Jaroslav Ne{\v{s}}et{\v{r}}il, eds., {\em The Mathematics of Paul Erd\H os {I}}, Vol.~13 of {\em Algorithms and Combinatorics}, Springer-Verlag, 1997, pp.~207--220. \bibitem{RAMSAO} Olivier Ramar{\'e} and Yannick Saouter, Short effective intervals containing primes, {\em J. Number Theory} {\bf 98} (2003), 10--33. \bibitem{RS62} J.~Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, {\em Illinois J. Math.} {\bf 6} (1962), 64--94. \bibitem{SCH76} Lowell Schoenfeld, Corrigendum: ``{S}harper bounds for the {C}hebyshev functions {$\theta (x)$} and {$\psi (x)$}. {II}'', {\em Math. Comp.} {\bf 30} (136) (1976), 900. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 11A25; Secondary 11N37, 11N05, 11-04. \noindent \emph{Keywords: } distribution of primes, champion number, highly compostite number, Landau function. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A000793} and \seqnum{A159685}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received September 22 2014; revised version received January 15 2015. Published in {\it Journal of Integer Sequences}, January 25 2015. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document} .