2 The prototypes: $\unicode[STIX]{x1D6FF}$ , $r_{2}$ , $\bar{Q}_{2}$ , and relatives

The following result is an immediate consequence of (1.2) and Corollary 4.3 below.

Theorem 2.1. Let $\unicode[STIX]{x1D6FF}$ be given by (1.1). Then

$$\begin{eqnarray}\max _{n\leqslant x}\log \unicode[STIX]{x1D6FF}(\unicode[STIX]{x1D6FF}(n))=\frac{\sqrt{\log x}}{\log _{2}x}\biggl(\frac{c}{\sqrt{2}}+{\mathcal{O}}\biggl(\frac{\log _{3}x}{\log _{2}x}\biggr)\biggr),\end{eqnarray}$$

where $c$ is given in (1.4).

Incidentally, this implies a result for $r_{2}$ with no additional effort—even though $r_{2}$ is not multiplicative.

Proof. For $n\in \mathbb{N}$ , write $\unicode[STIX]{x1D6FF}(n)=2^{\unicode[STIX]{x1D708}}m(n)$ with some odd integer $m(n)$ . Then, using multiplicativity of $\unicode[STIX]{x1D6FF}$ and $\unicode[STIX]{x1D6FF}(2^{2+\unicode[STIX]{x1D708}})=1=\unicode[STIX]{x1D6FF}(2^{\unicode[STIX]{x1D708}})$ , we have

$$\begin{eqnarray}\displaystyle r_{2}(r_{2}(n)) & = & \displaystyle 4\unicode[STIX]{x1D6FF}(2^{2+\unicode[STIX]{x1D708}}m(n))=4\unicode[STIX]{x1D6FF}(2^{2+\unicode[STIX]{x1D708}})\unicode[STIX]{x1D6FF}(m(n))\nonumber\\ \displaystyle & = & \displaystyle 4\unicode[STIX]{x1D6FF}(2^{\unicode[STIX]{x1D708}})\unicode[STIX]{x1D6FF}(m(n))=4\unicode[STIX]{x1D6FF}(2^{\unicode[STIX]{x1D708}}m(n))=4\unicode[STIX]{x1D6FF}(\unicode[STIX]{x1D6FF}(n)).\nonumber\end{eqnarray}$$

Hence, $\log r_{2}(r_{2}(n))=\log \unicode[STIX]{x1D6FF}(\unicode[STIX]{x1D6FF}(n))+2\log 2$ and the assertion of the corollary follows from Theorem 2.1.◻

It turns out that our arguments are not just limited to the binary quadratic form $x^{2}+y^{2}$ appearing in (1.2). A more refined explanation can be found in the next section. Here we content ourselves with stating the next result in a very modest form.

Theorem 2.3. Fix $k\in \{2,3,5,11,17,41\}$ and let $f(n)$ be defined by one of the expressions

(2.1) $$\begin{eqnarray}\displaystyle & {\textstyle \frac{1}{4}}\#\{(x,y)\in \mathbb{Z}^{2}\mid x^{2}+y^{2}=n\}, & \displaystyle\end{eqnarray}$$

(2.2) $$\begin{eqnarray}\displaystyle & {\textstyle \frac{1}{2}}\#\{(x,y)\in \mathbb{Z}^{2}\mid x^{2}+2y^{2}=n\}, & \displaystyle\end{eqnarray}$$

(2.3) $$\begin{eqnarray}\displaystyle & {\textstyle \frac{1}{6}}\#\{(x,y)\in \mathbb{Z}^{2}\mid x^{2}+xy+y^{2}=n\}, & \displaystyle\end{eqnarray}$$

$$\begin{eqnarray}{\textstyle \frac{1}{2}}\#\{(x,y)\in \mathbb{Z}^{2}\mid x^{2}+xy+ky^{2}=n\},\end{eqnarray}$$

for all positive integers $n$ and put $f(0)=1$ . Then

$$\begin{eqnarray}\max _{n\leqslant x}\log f(f(n))=\frac{\sqrt{\log x}}{\log _{2}x}\biggl(\frac{c}{\sqrt{2}}+{\mathcal{O}}\biggl(\frac{\log _{3}x}{\log _{2}x}\biggr)\biggr),\end{eqnarray}$$

where $c$ is given in (1.4).

Certainly Theorem 2.3 implies Theorem 2.1 (see (2.1)). Moreover, it covers the choice $f=\bar{Q}_{2}$ with $\bar{Q}_{2}$ defined in (1.3) (see (2.3)). Corollary 2.2 allows one to drop the factor ${\textstyle \frac{1}{4}}$ in (2.1) and the same trick used for proving Corollary 2.2 can also be used to show that one can drop the factor ${\textstyle \frac{1}{2}}$ in (2.2).

3 Examples from algebraic number theory

Our next objective is to fit Theorem 2.3 into a broader context. We begin with some notation. Let $K$ be an arbitrary number field and $\mathscr{O}$ its ring of algebraic integers. The norm of an ideal $\mathfrak{a}\subseteq \mathscr{O}$ is denoted by $\text{N}\mathfrak{a}=\#(\mathscr{O}/\mathfrak{a}\mathscr{O})\in \mathbb{N}$ . Consider

(3.1) $$\begin{eqnarray}f_{K}(n)=\#\{\text{ideals }\mathfrak{a}\subseteq \mathscr{O}:\text{N}\mathfrak{a}=n\}.\end{eqnarray}$$

For two ideals $\mathfrak{a},\mathfrak{b}\subseteq \mathscr{O}$ their product $\mathfrak{ab}$ is defined elementwise and we have $\text{N}(\mathfrak{ab})=(\text{N}\mathfrak{a})(\text{N}\mathfrak{b})$ . On combining this with the classical facts that ideals of $\mathscr{O}$ admit a unique factorization into prime ideals and that the norm of a prime ideal is always a power of a prime in $\mathbb{N}$ , one easily deduces that $f_{K}:\mathbb{N}_{0}\rightarrow \mathbb{N}_{0}$ as defined above is multiplicative.

In order to understand the behaviour of $f_{K}$ on prime powers $p^{\unicode[STIX]{x1D708}}$ , we start by considering any ideal $\mathfrak{a}$ with $\text{N}\mathfrak{a}=p^{\unicode[STIX]{x1D708}}$ . By the multiplicativity of the norm, the factorization of $\mathfrak{a}$ consists only of prime ideals whose norm is again a power of $p$ . From algebraic number theory one knows that the number of prime ideals $\mathfrak{p}\subseteq \mathscr{O}$ with $p$ dividing $\text{N}\mathfrak{p}$ is finite. Thus, enumerating the prime ideals with said property by $\mathfrak{p}_{1},\ldots ,\mathfrak{p}_{k}$ , we may write $\mathfrak{a}=\mathfrak{p}_{1}^{\unicode[STIX]{x1D708}_{1}}\cdots \mathfrak{p}_{k}^{\unicode[STIX]{x1D708}_{k}}$ for some exponents $\unicode[STIX]{x1D708}_{1},\ldots ,\unicode[STIX]{x1D708}_{k}\in \mathbb{N}_{0}$ . The condition that $\text{N}\mathfrak{a}=n$ then takes the form

(3.2) $$\begin{eqnarray}\mathop{\sum }_{j=1}^{k}\unicode[STIX]{x1D708}_{j}\frac{\log \text{N}\mathfrak{p}_{j}}{\log p}=\unicode[STIX]{x1D708}.\end{eqnarray}$$

On the other hand, this argument also works in the opposite direction. Hence, the map

(3.3) $$\begin{eqnarray}\displaystyle \{(\unicode[STIX]{x1D708}_{1},\ldots ,\unicode[STIX]{x1D708}_{k})\in \mathbb{N}_{0}^{k}:\text{(3.2) holds}\} & \longrightarrow & \displaystyle \{\text{ideals }\mathfrak{a}\subseteq \mathscr{O}\text{with }\text{N}\mathfrak{a}=p^{\unicode[STIX]{x1D708}}\text{}\},\nonumber\\ \displaystyle (\unicode[STIX]{x1D708}_{1},\ldots ,\unicode[STIX]{x1D708}_{k}) & \longmapsto & \displaystyle \mathfrak{p}_{1}^{\unicode[STIX]{x1D708}_{1}}\cdots \mathfrak{p}_{k}^{\unicode[STIX]{x1D708}_{k}}\end{eqnarray}$$

is bijective. Moreover, one knows that the principal ideal $(p)=p\mathscr{O}$ factors as $(p)=\mathfrak{p}_{1}^{e_{1}}\cdots \mathfrak{p}_{k}^{e_{k}}$ , so that

(3.4) $$\begin{eqnarray}\mathop{\sum }_{j=1}^{k}e_{j}\frac{\log \text{N}\mathfrak{p}_{j}}{\log p}=\frac{\text{N}(p)}{\log p}=[K:\mathbb{Q}],\end{eqnarray}$$

where the right-hand side is the degree of the field extension $K/\mathbb{Q}$ .

If $[K:\mathbb{Q}]>2$ , then (3.2) allows for too much freedom in the choice of the exponents $\unicode[STIX]{x1D708}_{1},\ldots ,\unicode[STIX]{x1D708}_{k}$ . Consequently, the value of $f_{K}$ at prime powers $p^{\unicode[STIX]{x1D708}}$ may depend too loosely on the prime $p$ and the quick growth of $f_{K}(p^{\unicode[STIX]{x1D708}})$ as a function of $\unicode[STIX]{x1D708}$ poses additional problems. The situation becomes appreciably better if $K$ is a quadratic extension of $\mathbb{Q}$ and we shall henceforth restrict ourselves to this case. Then, by (3.4), for any prime $p$ , only one of the following three cases may occur:

1. (1) $p$ is ramified, that is, $(p)=\mathfrak{p}_{1}^{2}$ for some prime ideal $\mathfrak{p}_{1}$ of $\mathscr{O}$ with $\text{N}\mathfrak{p}=p$ ;

2. (2) $p$ is split, that is, $(p)=\mathfrak{p}_{1}\mathfrak{p}_{2}$ with some distinct prime ideals $\mathfrak{p}_{1},\mathfrak{p}_{2}\subseteq \mathscr{O}$ each having norm $p$ ;

3. (3) $p$ is inert, that is, $(p)=\mathfrak{p}_{1}$ is a prime ideal of $\mathscr{O}$ and $\text{N}\mathfrak{p}_{1}=\text{N}(p)=p^{2}$ .

From multiplicativity of $f_{K}$ in combination with the map in (3.3) being bijective, it follows that

(3.5) $$\begin{eqnarray}f_{K}(n)=\mathop{\prod }_{\substack{ \text{prime }p\mid n \\ p\text{ ramified}}}1\times \mathop{\prod }_{\substack{ \text{prime }q\mid n \\ q\text{ split}}}(\unicode[STIX]{x1D708}_{q}(n)+1)\times \mathop{\prod }_{\substack{ \text{prime }p\mid n \\ p\text{ inert}}}{\displaystyle \frac{1}{2}}(1+(-1)^{\unicode[STIX]{x1D708}_{p}(n)}).\end{eqnarray}$$

From this representation of $f_{K}(n)$ , we see that our results from §4 below can be applied to establish the following theorem.

Theorem 3.1. Suppose that $K$ is some fixed quadratic number field and let $f_{K}$ be given by (3.1). Then

$$\begin{eqnarray}\max _{n\leqslant x}\log f_{K}(f_{K}(n))=\frac{\sqrt{\log x}}{\log _{2}x}\biggl(\frac{c}{\sqrt{2}}+{\mathcal{O}}\biggl(\frac{\log _{3}x}{\log _{2}x}\biggr)\biggr),\end{eqnarray}$$

where the implied constant may depend on $K$ , and $c$ is given in (1.4).

The missing pieces for the proof of the above theorem are given in §5 below.

In the rest of this section we briefly sketch how to obtain Theorem 2.3 from Theorem 3.1. To this end, assume that $K$ is some imaginary quadratic number field with class number one. Then the value $f_{K}(n)$ can be viewed as the number of solutions to some binary quadratic equation. Indeed, the assumption about the class number implies that all ideals of $\mathscr{O}$ are principal and $K$ being imaginary quadratic implies that $\mathscr{O}$ has finitely many units. Therefore,

(3.6) $$\begin{eqnarray}f_{K}(n)=\frac{\#\{\unicode[STIX]{x1D709}\in \mathscr{O}:\text{N}(\unicode[STIX]{x1D709})=n\}}{\#\{\text{units in }\mathscr{O}\}}.\end{eqnarray}$$

The celebrated Baker–Heegner–Stark theorem gives a complete classification (up to isomorphism) of all imaginary quadratic number fields with class number one. Theorem 2.3 then follows immediately by going through that list, rewriting the norm equation $\text{N}(\unicode[STIX]{x1D709})=n$ with respect to some integral basis and applying Theorem 3.1; here the choice of the integral basis may affect the particular form one gets, but any such form can be readily checked to be equivalent to one of those implicit in Theorem 2.3 by using the well-known reduction theory for binary quadratic forms.

4 Hypotheses and the general results

In what follows, we give a description of a class of arithmetic functions for which the subsequent reasoning works. The imposed restrictions could be relaxed somewhat, but the model cases we primarily aim at are given in (1.2), (1.3) and (3.5). The important features here are that the arithmetic function $f$ to be iterated is multiplicative, acts affinely on the exponents of powers of primes $q$ from a certain subset of primes $Q\subseteq \mathbb{P}$ (e.g., $\text{primes}\equiv 1\hspace{0.2em}{\rm mod}\hspace{0.2em}4$ in the case $f=\unicode[STIX]{x1D6FF}$ , as seen in (1.2)), and takes only the values $0,1$ on powers of primes $p\in \mathbb{P}\setminus Q$ (subject to a rule which—under the assumptions below—turns out to irrelevant).

In [Reference Buttkewitz, Elsholtz, Ford and Schlage-Puchta4], the case $Q=\mathbb{P}$ with the multiplicative arithmetic function $d$ acting as $d(p^{\unicode[STIX]{x1D708}})=\unicode[STIX]{x1D708}+1$ is studied. In our approach, we assume that $f(q^{\unicode[STIX]{x1D708}})=g(\unicode[STIX]{x1D708})$ for powers of primes $q\in Q$ with a function $g$ satisfying suitable axioms as listed below. By elaborating on the method of [Reference Buttkewitz, Elsholtz, Ford and Schlage-Puchta4], we obtain upper and lower bounds on the maximal order of first iterates of arithmetic functions $f$ which enjoy similar properties to those observed for $d$ and $\unicode[STIX]{x1D6FF}$ ; see Theorems 4.1 and 4.2.

In detail, we start with a strictly increasing sequence of primes $(q_{j})_{j\geqslant 1}$ . By the prime number theorem, the sequence of all primes $(p_{j})_{j\geqslant 1}$ satisfies $p_{j}=j(\log j+\log (\log j)+{\mathcal{O}}(1))$ , so it seems reasonable to assume similar asymptotics for $(q_{j})_{j\geqslant 1}$ (see (A.1) below). Set $Q=\{q_{j}:j\in \mathbb{N}\}$ and let $\langle Q\rangle$ be the monoid (multiplicatively) generated by $Q$ . Furthermore, fix a map $g:\mathbb{N}_{0}\rightarrow \mathbb{N}$ with $g(0)=1$ and letFootnote ²

(4.1) $$\begin{eqnarray}g^{\dagger }(y)=\inf \{x\in \mathbb{N}:g(x)=y\}\in \mathbb{N}\cup \{+\infty \}.\end{eqnarray}$$

Finally, assume that:

1. (A.1) $(q_{j})_{j\geqslant 1}$ satisfies the asymptotic expansion

   $$\begin{eqnarray}q_{j}=\unicode[STIX]{x1D705}j(\log j+\log (\log j)+{\mathcal{O}}(1)),\end{eqnarray}$$
   where $\unicode[STIX]{x1D705}>0$ is some constant;

2. (A.2) $g$ is monotonically increasing;

3. (A.3) $g(\mathbb{N})\supseteq \langle Q\rangle$ ;

4. (A.4) $g^{\dagger }(b)+c_{\ast }bg^{\dagger }(a)\leqslant g^{\dagger }(ab)$ for all $a,b\in \langle Q\rangle$ such that $q_{1}\leqslant a\leqslant b$ , where $c_{\ast }>1/q_{1}$ is some constant;

5. (A.5) $g(i)/g(i-1)=1+{\mathcal{O}}(i^{-1/2-\unicode[STIX]{x1D716}})$ for some $\unicode[STIX]{x1D716}>0$ ;

6. (A.6) $g(x)\leqslant c_{f}x$ for all $x\in \mathbb{N}$ , where $c_{f}>0$ is some constant;

7. (A.7) $g^{\dagger }(q)=c_{\dagger }q+{\mathcal{O}}(q/\log q)$ as $Q\ni q\rightarrow \infty$ , where $c_{\dagger }>0$ is some constant. (Note that $g^{\dagger }(q)$ is finite due to (A.3).)

Now let $f$ be a multiplicative arithmetic function satisfying

(4.2) $$\begin{eqnarray}f(p^{\unicode[STIX]{x1D708}})\left\{\begin{array}{@{}ll@{}}=g(\unicode[STIX]{x1D708})\quad & \text{if }p\in Q,\\ \in \{0,1\}\quad & \text{if }p\notin Q,\end{array}\right.\end{eqnarray}$$

for a prime power $p^{\unicode[STIX]{x1D708}}\geqslant 1$ . Furthermore, let $f(0)=1$ . We write

(4.3) $$\begin{eqnarray}M(x)=\max _{n\leqslant x}\log f(f(n)).\end{eqnarray}$$

On writing $\log _{k}$ for the $k$ -fold iterate of the natural logarithm, our main results may now be stated as follows.

Theorem 4.1. Let $M$ be as in (4.3). Then

(4.4) $$\begin{eqnarray}M(x)\leqslant \frac{\sqrt{\log x}}{\log _{2}x}\biggl(\frac{C_{g}}{\sqrt{\unicode[STIX]{x1D705}c_{\dagger }}}+{\mathcal{O}}\biggl(\frac{\log _{3}x}{\log _{2}x}\biggr)\biggr),\end{eqnarray}$$

where the implied constant depends on $Q,f$ and

(4.5) $$\begin{eqnarray}C_{g}=\biggl(8\mathop{\sum }_{j=1}^{\infty }\biggl(\log \frac{g(j)}{g(j-1)}\biggr)^{2}\biggr)^{1/2}.\end{eqnarray}$$

Throughout this paper, $C_{g}$ always denotes the constant defined in (4.5). We also note in passing that throughout all implied constants may depend on the function $f$ and the set $Q$ and an $\unicode[STIX]{x1D716}$ , where obvious.

Theorem 4.2. Letting $g(\unicode[STIX]{x1D708})=\unicode[STIX]{x1D6FC}\unicode[STIX]{x1D708}+1$ and assuming the above hypotheses, the following inequality holds:

(4.6) $$\begin{eqnarray}M(x)\geqslant \frac{\sqrt{\log x}}{\log _{2}x}\biggl(\frac{C_{g}}{\sqrt{\unicode[STIX]{x1D705}/\unicode[STIX]{x1D6FC}}}+{\mathcal{O}}\biggl(\frac{\log _{3}x}{\log _{2}x}\biggr)\biggr).\end{eqnarray}$$

Combining Theorems 4.1 and 4.2, we immediately deduce the following corollary.

Corollary 4.3. Letting $g(\unicode[STIX]{x1D708})=\unicode[STIX]{x1D6FC}\unicode[STIX]{x1D708}+1$ for some $\unicode[STIX]{x1D6FC}\in \mathbb{N}$ , and on the above hypotheses, we have

$$\begin{eqnarray}M(x)=\frac{\sqrt{\log x}}{\log _{2}x}\biggl(\frac{C_{g}}{\sqrt{\unicode[STIX]{x1D705}/\unicode[STIX]{x1D6FC}}}+{\mathcal{O}}\biggl(\frac{\log _{3}x}{\log _{2}x}\biggr)\biggr).\end{eqnarray}$$

We note in passing that, for $Q=\mathbb{P}$ in the setting of Corollary 4.3, the function $f$ in (4.2) arises naturally as number of divisors of monic monomials, that is, $f(n)=d(n^{\unicode[STIX]{x1D6FC}})$ .

5 Proof of Theorem 3.1

We assume the notation of Theorem 3.1 and recall (3.5). In order to use Corollary 4.3 to obtain an asymptotic formula for

$$\begin{eqnarray}\max _{n\leqslant x}\log f_{K}(f_{K}(n)),\end{eqnarray}$$

it only remains to verify assumption (A.1), where $q_{j}$ therein is taken to be the $j$ th smallest prime which splits in $K$ . The next lemma furnishes a prime number theorem for such primes and can be used to verify that assumption (A.1) holds with $\unicode[STIX]{x1D705}=\frac{1}{2}$ and thereby finishes the proof of Theorem 3.1.

Lemma 5.1. Suppose that $K$ is some fixed quadratic number field. Then

$$\begin{eqnarray}\#\{\text{primes }q\leqslant x\text{ which are split in }K\}=\frac{1}{2}\frac{x}{\log x}(1+{\mathcal{O}}(1/\text{log}\,x))\end{eqnarray}$$

as $x\rightarrow \infty$ .

The above lemma is certainly well known. Nevertheless, we sketch a proof for the convenience of the reader.

Proof of Lemma 5.1.

By [Reference Ireland and Rosen13, Proposition 13.1.3] there is some integer $\unicode[STIX]{x1D6E5}$ such that

$$\begin{eqnarray}\displaystyle & & \displaystyle \#\{\text{primes }q\leqslant x\text{ which are split in }K\}\nonumber\\ \displaystyle & & \displaystyle \quad =\#\left\{\text{primes }q\leqslant x\text{ with }\biggl(\frac{\unicode[STIX]{x1D6E5}}{q}\biggr)=1\right\}+{\mathcal{O}}(d(\unicode[STIX]{x1D6E5}))\nonumber\\ \displaystyle & & \displaystyle \quad =\frac{1}{2}\#\{\text{primes }p\leqslant x\}+\frac{1}{2}\mathop{\sum }_{\text{primes }q\leqslant x}\biggl(\frac{\unicode[STIX]{x1D6E5}}{q}\biggr)+{\mathcal{O}}(d(\unicode[STIX]{x1D6E5})),\nonumber\end{eqnarray}$$

where $(\unicode[STIX]{x1D6E5}/q)$ denotes the Kronecker symbol. Consequently, the assertion of the lemma then follows from the prime number theorem and [Reference Iwaniec and Kowalski15, Corollary 5.29] (see also [Reference Iwaniec and Kowalski15, Exercise 6 in §3.5]).◻

6 Notation and auxiliary results

6.2 Auxiliary results

We would like to give the reader our perspective on the problem at hand. In order to keep the notation simple, let $Q=\mathbb{P}$ for the moment. Then, for any positive integer $n$ ,

$$\begin{eqnarray}\log f(f(n))=\mathop{\sum }_{\substack{ q\in Q \\ q\mid f(n)}}\log g(q^{\unicode[STIX]{x1D708}_{q}(f(n))}).\end{eqnarray}$$

Vaguely speaking, in order to give estimates on $M(x)$ , one needs to exhibit some control over the prime factors of integers $N$ , which appear as values $N=f(n)$ for $n\leqslant x$ . This sort of control is provided by Lemma 6.1.

Additionally, one might like to remove  $g$ from the above sum and perhaps also take advantage of the fact that (weighted) sums of $\unicode[STIX]{x1D708}_{q}(f(N))$ over  $q$ are more readily controlled than values of $\unicode[STIX]{x1D708}_{q}(f(N))$ for some individual  $q$ . Lemma 6.2 makes this happen and is the source of the main term in Theorems 4.1 and 4.2.

Finally, Lemma 6.3 is a technical tool used to handle the case when $N=f(n)$ does not have sufficiently many prime factors  $q$ with small exponent  $\unicode[STIX]{x1D708}_{q}(N)$ .

Lemma 6.1. For an $N\in \langle Q\rangle$ , let $m_{N}$ be the least positive integer $m$ such that $f(m)=N>1$ . Then the following assertions hold.

1. (1) The number $m_{N}$ factors as $m_{N}=q_{1}^{\unicode[STIX]{x1D708}_{1}}\cdots q_{r}^{\unicode[STIX]{x1D708}_{r}}$ with some $r\geqslant 1$ , exponents $\unicode[STIX]{x1D708}_{1}\geqslant \cdots \geqslant \unicode[STIX]{x1D708}_{r}$ and the primes $q_{1},q_{2},\ldots$ from §4.

2. (2) If $N^{\prime }$ divides $N$ , then $m_{N^{\prime }}\leqslant m_{N}$ .

3. (3) If $q_{j}>q_{r+1}^{1/s_{k}}$ for some $j\leqslant r$ , then $\unicode[STIX]{x1D6FA}(g(\unicode[STIX]{x1D708}_{j}))\leqslant k$ , where $s_{k}=c_{\ast }q_{1}^{k}$ .

Proof. Pick some $p\notin Q$ and let $\unicode[STIX]{x1D708}=\unicode[STIX]{x1D708}_{p}(m_{N})$ . Then $1<N=f(m_{N})=f(p^{\unicode[STIX]{x1D708}})f(m_{N}/p^{\unicode[STIX]{x1D708}})$ , so that $m_{N}=m_{N}/p^{\unicode[STIX]{x1D708}}$ . Hence, $\unicode[STIX]{x1D708}=0$ and $p\nmid m_{N}$ . Now, writing $m_{N}=q_{1}^{\unicode[STIX]{x1D708}_{1}}\cdots q_{r}^{\unicode[STIX]{x1D708}_{r}}$ , note that one can permute the exponents without changing the value under $f$ . Therefore, by minimality of $m_{N}$ , we must have $\unicode[STIX]{x1D708}_{1}\geqslant \cdots \geqslant \unicode[STIX]{x1D708}_{r}$ . This proves (1).

Turning to (2), if we write $m_{N}=q_{1}^{\unicode[STIX]{x1D708}_{1}}\cdots q_{r}^{\unicode[STIX]{x1D708}_{r}}$ , then, by (4.2),

(6.1) $$\begin{eqnarray}N=f(m_{N})=\mathop{\prod }_{j\leqslant r}g(\unicode[STIX]{x1D708}_{j}),\end{eqnarray}$$

and since $N^{\prime }\mid N$ there is a partition $\unicode[STIX]{x1D708}_{k}=\unicode[STIX]{x1D708}_{k,1}+\cdots +\unicode[STIX]{x1D708}_{k,r}$ such that $N_{j}^{\prime }=\prod _{k\leqslant s}q_{k}^{\unicode[STIX]{x1D708}_{k,j}}\mid g(\unicode[STIX]{x1D708}_{j})$ . By assumption (A.3) on $g$ , the value $N_{j}^{\prime }$ is attained by $g$ . Hence, we may look at $m_{\ast }=q_{1}^{\unicode[STIX]{x1D708}_{1}^{\prime }}\cdots q_{r}^{\unicode[STIX]{x1D708}_{r}^{\prime }}$ , where $\unicode[STIX]{x1D708}_{j}^{\prime }=g^{\dagger }(N_{j}^{\prime })$ . Clearly, $f(m_{\ast })=N^{\prime }$ , and, by monotonicity of $g$ , $\unicode[STIX]{x1D708}_{j}^{\prime }\leqslant \unicode[STIX]{x1D708}_{j}$ , so that $m_{N^{\prime }}\leqslant m_{\ast }\leqslant m_{N}$ .

To prove (3), let us assume for the sake of contradiction that $q_{j}>q_{r+1}^{1/s_{k}}$ , $\unicode[STIX]{x1D6FA}(g(\unicode[STIX]{x1D708}_{j}))>k$ . Using (6.1) and $N\in \langle Q\rangle$ , we have $\unicode[STIX]{x1D6FA}_{Q}(g(\unicode[STIX]{x1D708}_{j}))=\unicode[STIX]{x1D6FA}(g(\unicode[STIX]{x1D708}_{j}))>k$ , so that there is a decomposition $g(\unicode[STIX]{x1D708}_{j})=ab$ , where $a\geqslant q_{1}$ , $b\geqslant q_{1}^{k}$ . Recalling the definition of $g^{\dagger }$ in (4.1) and using that both $a$ and $b$ are contained in $\langle Q\rangle$ , we see that both $g^{\dagger }(a)$ and $g^{\dagger }(b)$ are finite and we may consider

$$\begin{eqnarray}m^{\ast }=q_{j}^{g^{\dagger }(b)}q_{r+1}^{g^{\dagger }(a)}\mathop{\prod }_{\substack{ i=1 \\ i\neq j}}^{r}q_{i}^{\unicode[STIX]{x1D708}_{i}}.\end{eqnarray}$$

Since (A.4) implies

$$\begin{eqnarray}g^{\dagger }(b)-\unicode[STIX]{x1D708}_{j}\leqslant g^{\dagger }(b)-g^{\dagger }(ab)=g^{\dagger }(b)\biggl(1-\frac{g^{\dagger }(ab)}{g^{\dagger }(b)}\biggr)\leqslant -c_{\ast }g^{\dagger }(a)b,\end{eqnarray}$$

which, by assumption, is less than or equal to $-c_{\ast }q_{1}^{k}$ , we infer

$$\begin{eqnarray}\frac{m^{\ast }}{m_{N}}=q_{j}^{g^{\dagger }(b)-\unicode[STIX]{x1D708}_{j}}q_{r+1}^{g^{\dagger }(a)}\leqslant q_{j}^{-c_{\ast }g^{\dagger }(a)b}q_{r+1}^{g^{\dagger }(a)}.\end{eqnarray}$$

However, this shows that $m^{\ast }<m_{N}$ , which contradicts the definition of $m_{N}$ , for we have

$$\begin{eqnarray}f(m^{\ast })=\underbrace{g(g^{\dagger }(b))g(g^{\dagger }(a))}_{=ab=g(\unicode[STIX]{x1D708}_{j})}\mathop{\prod }_{\substack{ i=1 \\ i\neq j}}^{r}g(\unicode[STIX]{x1D708}_{i})=\mathop{\prod }_{i\leqslant r}g(\unicode[STIX]{x1D708}_{i})=N.\end{eqnarray}$$

Hence, we conclude that $\unicode[STIX]{x1D6FA}_{Q}(g(\unicode[STIX]{x1D708}_{j}))\leqslant k$ .◻

Lemma 6.2. Let $\unicode[STIX]{x1D708}_{1},\ldots ,\unicode[STIX]{x1D708}_{t}$ be positive integers. Then

(6.2) $$\begin{eqnarray}\mathop{\sum }_{j\leqslant t}\log g(\unicode[STIX]{x1D708}_{j})\leqslant \frac{C_{g}}{2}\biggl(\mathop{\sum }_{j\leqslant t}j\unicode[STIX]{x1D708}_{j}\biggr)^{1/2},\end{eqnarray}$$

where $C_{g}$ is given by (4.5). If additionally $\unicode[STIX]{x1D708}_{t}\geqslant \unicode[STIX]{x1D708}$ , then

$$\begin{eqnarray}\mathop{\sum }_{j\leqslant t}\log g(\unicode[STIX]{x1D708}_{j})\ll \sqrt{\frac{1}{\unicode[STIX]{x1D708}^{2\unicode[STIX]{x1D716}}}+\frac{(\log g(\unicode[STIX]{x1D708}))^{2}}{\unicode[STIX]{x1D708}}}\biggl(\mathop{\sum }_{j\leqslant t}j\unicode[STIX]{x1D708}_{j}\biggr)^{1/2},\end{eqnarray}$$

with $\unicode[STIX]{x1D716}$ from (A.5).

Proof. (Compare [Reference Buttkewitz, Elsholtz, Ford and Schlage-Puchta4, Lemma 3.3].) First note that the right-hand side of (6.2) is minimal if the $\unicode[STIX]{x1D708}_{j}$ are decreasing. Hence, we may subsequently assume that $\unicode[STIX]{x1D708}_{1}\geqslant \unicode[STIX]{x1D708}_{2}\geqslant \cdots \geqslant \unicode[STIX]{x1D708}_{t}$ . Let $y_{i}=\#\{j:\unicode[STIX]{x1D708}_{j}\geqslant i\}$ and observe that

(6.3) $$\begin{eqnarray}\mathop{\sum }_{j\leqslant t}j\unicode[STIX]{x1D708}_{j}=\mathop{\sum }_{j\leqslant t}\mathop{\sum }_{i\leqslant \unicode[STIX]{x1D708}_{j}}j=\mathop{\sum }_{i=1}^{\infty }\mathop{\sum }_{j\leqslant y_{i}}j=\frac{1}{2}\mathop{\sum }_{i=1}^{\infty }y_{i}(y_{i}+1)\geqslant \frac{1}{2}\mathop{\sum }_{i=1}^{\infty }y_{i}^{2}.\end{eqnarray}$$

By partial summation,

(6.4) $$\begin{eqnarray}\mathop{\sum }_{j\leqslant t}\log g(\unicode[STIX]{x1D708}_{j})=\mathop{\sum }_{i=1}^{\infty }(y_{i}-y_{i+1})\log g(i)=\mathop{\sum }_{i=1}^{\infty }y_{i}\log \frac{g(i)}{g(i-1)}.\end{eqnarray}$$

The first claim now follows by applying the Cauchy–Schwarz inequality to the right-hand side, and taking (6.3) into account.

Moreover, if $\unicode[STIX]{x1D708}_{t}\geqslant \unicode[STIX]{x1D708}$ , then $y_{1}=y_{2}=\cdots =y_{\unicode[STIX]{x1D708}}$ and

$$\begin{eqnarray}\mathop{\sum }_{i\leqslant A}y_{i}\log \frac{g(i)}{g(i-1)}=y_{1}\log g(\unicode[STIX]{x1D708}).\end{eqnarray}$$

By splitting up the sum in (6.4) into sums over the ranges $i\leqslant \unicode[STIX]{x1D708}$ and $i>\unicode[STIX]{x1D708}$ , and applying the Cauchy–Schwarz inequality, we obtain

$$\begin{eqnarray}\mathop{\sum }_{j\leqslant t}\log g(\unicode[STIX]{x1D708}_{j})\leqslant \biggl(\mathop{\sum }_{i=1}^{\infty }y_{i}^{2}\biggr)^{1/2}\biggl(\frac{(\log g(\unicode[STIX]{x1D708}))^{2}}{\unicode[STIX]{x1D708}}+\mathop{\sum }_{i>\unicode[STIX]{x1D708}}\biggl(\log \frac{g(i)}{g(i-1)}\biggr)^{2}\biggr)^{1/2}.\end{eqnarray}$$

By (A.5) and $\log (1+1/i)<1/i$ , the second sum is $\ll \unicode[STIX]{x1D708}^{-2\unicode[STIX]{x1D716}}$ . In view of (6.3), we have established the second claim.◻

Lemma 6.3. For every $\unicode[STIX]{x1D700}>0$ , and $s:=\unicode[STIX]{x1D714}_{Q}(n)\geqslant 2$ ,

$$\begin{eqnarray}f(n)\ll \biggl(\frac{(c_{f}+\unicode[STIX]{x1D700})\log n}{s\log s}\biggr)^{s}.\end{eqnarray}$$

Proof. See [Reference Buttkewitz, Elsholtz, Ford and Schlage-Puchta4, Lemma 3.2] and, recalling that there $g$ is $x\mapsto x+1$ , use (A.6) instead of $x+1\leqslant 2x$ .◻

7 Proof of Theorem 4.1

Let $n$ be a positive integer such that $f(f(n))>1$ and $N=\unicode[STIX]{x1D6F1}_{Q}(f(n))$ . As before, $f(f(n))=f(N)$ .

We now write $N$ as a product of powers of elements in $Q$ and split these into two groups according to the size of their exponents. More precisely, we write $N=N^{\prime }N^{\prime \prime }$ , where

(7.1) $$\begin{eqnarray}N^{\prime }=u_{1}^{b_{1}}\cdots u_{w}^{b_{w}},\qquad N^{\prime \prime }=v_{1}^{a_{1}}\cdots v_{s}^{a_{s}}\end{eqnarray}$$

and $u_{1}<\cdots <u_{w}$ , $v_{1}<\cdots <v_{s}$ all belong to $Q$ , are all distinct, and $a_{i}\leqslant (\log _{2}n)^{K}$ and $b_{i}>(\log _{2}n)^{K}$ , for $K=\max \{6,2/\unicode[STIX]{x1D716}\}$ , with $\unicode[STIX]{x1D716}$ from (A.5).

Clearly, $\log f(N)=\log f(N^{\prime })+\log f(N^{\prime \prime })$ , so that it suffices to deal with $f(N^{\prime })$ and $f(N^{\prime \prime })$ separately. The main term in (4.4) comes from $\log f(N^{\prime \prime })$ (see (7.4)) and the term $\log f(N^{\prime })$ is seen to be somewhat smaller (see (7.2)).

7.1 Bounding $f(N^{\prime })$

Write $m_{N^{\prime }}=q_{1}^{\unicode[STIX]{x1D6FD}_{1}}\cdots q_{h}^{\unicode[STIX]{x1D6FD}_{h}}$ . Due to Lemma 6.1 (2), we have $m_{N^{\prime }}\leqslant m_{N}\leqslant n$ and, hence, $h\ll \log n$ . Lemma 6.1 (3) yields $\unicode[STIX]{x1D6FA}(g(\unicode[STIX]{x1D6FD}_{i}))\ll \log _{2}h\ll \log _{3}n$ for every $i$ . Therefore, there are $\gg b_{j}/\text{log}_{3}\,n$ values of $i$ such that $u_{j}\mid g(\unicode[STIX]{x1D6FD}_{i})$ . Furthermore, assuming, as we may, that $n$ is sufficiently large, Lemma 6.2 with $\unicode[STIX]{x1D708}=\lfloor (\log _{2}n)^{K}\rfloor$ shows that, for $\unicode[STIX]{x1D716}^{\prime }=K/2-2$ ,

$$\begin{eqnarray}\displaystyle \log f(N^{\prime })=\mathop{\sum }_{j\leqslant w}\log g(b_{j})\ll (\log _{2}n)^{-\text{min}\{\unicode[STIX]{x1D716}K,2\}}\biggl(\mathop{\sum }_{j\leqslant w}jb_{j}\biggr)^{1/2}. & & \displaystyle \nonumber\end{eqnarray}$$

Moreover,

$$\begin{eqnarray}\displaystyle \frac{1}{\log _{3}n}\mathop{\sum }_{j\leqslant w}jb_{j} & {\leqslant} & \displaystyle \mathop{\sum }_{j\leqslant w}\frac{u_{j}b_{j}}{\log _{3}n}\nonumber\\ \displaystyle & \ll & \displaystyle \mathop{\sum }_{i\leqslant h}\mathop{\sum }_{p\mid g(\unicode[STIX]{x1D6FD}_{i})}p\leqslant \mathop{\sum }_{i\leqslant h}g(\unicode[STIX]{x1D6FD}_{i})\nonumber\\ \displaystyle & \ll & \displaystyle \mathop{\sum }_{i\leqslant h}\unicode[STIX]{x1D6FD}_{i}\ll \log m_{N^{\prime }}\leqslant \log n.\nonumber\end{eqnarray}$$

Hence,

(7.2) $$\begin{eqnarray}\log f(N^{\prime })\ll \frac{\sqrt{(\log n)\log _{3}n}}{(\log _{2}n)^{2}}.\end{eqnarray}$$

7.2 Bounding $f(N^{\prime \prime })$

To estimate $f(N^{\prime \prime })$ we may assume that

(7.3) $$\begin{eqnarray}s>\frac{\sqrt{\log n}}{(\log _{2}n)^{K/2}},\end{eqnarray}$$

for otherwise Lemma 6.3 implies that

$$\begin{eqnarray}\log f(N^{\prime \prime })\ll \frac{\sqrt{\log n}}{(\log _{2}n)^{K/2-1}}.\end{eqnarray}$$

We shall prove the following proposition that is crucial for estimating $f(N^{\prime })$ ; it relates $m_{N^{\prime \prime }}$ with upper bounds as in Lemma 6.2.

Proposition 7.1. Let $K=\max \{6,2/\unicode[STIX]{x1D716}\}$ , with $\unicode[STIX]{x1D716}$ from (A.5). Suppose that $n$ is a positive integer with $f(f(n))>1$ and let $N=\unicode[STIX]{x1D6F1}_{Q}(f(n))=N^{\prime }N^{\prime \prime }$ as in (7.1). Moreover, assume that (7.3) holds. Then

$$\begin{eqnarray}\log m_{N^{\prime \prime }}\geqslant \biggl(1+{\mathcal{O}}\biggl(\frac{\log _{3}n}{\log _{2}n}\biggr)\biggr)c_{\dagger }\unicode[STIX]{x1D705}\frac{(\log _{2}n)^{2}}{4}\mathop{\sum }_{j\leqslant s}ja_{j}.\end{eqnarray}$$

Let us suppose for the moment that Proposition 7.1 is proved. We can conclude by Lemma 6.1 (2) that

$$\begin{eqnarray}\log n\geqslant \log m_{N^{\prime \prime }}\geqslant \biggl(1+{\mathcal{O}}\biggl(\frac{\log _{3}n}{\log _{2}n}\biggr)\biggr)c_{\dagger }\unicode[STIX]{x1D705}\frac{(\log _{2}n)^{2}}{4}\mathop{\sum }_{j\leqslant s}ja_{j}.\end{eqnarray}$$

Inequality (6.2) implies that

(7.4) $$\begin{eqnarray}\log f(N^{\prime \prime })\leqslant \frac{\sqrt{\log n}}{\log _{2}n}\biggl(\frac{C_{g}}{\sqrt{c_{\dagger }\unicode[STIX]{x1D705}}}+{\mathcal{O}}\biggl(\frac{\log _{3}n}{\log _{2}n}\biggr)\biggr),\end{eqnarray}$$

which concludes the proof of Theorem 4.1.

Proof of Proposition 7.1.

Write $m_{N^{\prime \prime }}=q_{1}^{\unicode[STIX]{x1D6FC}_{1}}\cdots q_{r}^{\unicode[STIX]{x1D6FC}_{r}}$ for the minimal element of $f^{-1}(N^{\prime \prime })$ , as in Lemma 6.1. Our first goal is to establish that $r$ cannot be too small. By Lemma 6.1, and letting $s_{0}=1$ for the moment, the last sum in

(7.5) $$\begin{eqnarray}\unicode[STIX]{x1D6FA}(N^{\prime \prime })=\mathop{\sum }_{j\leqslant s}a_{j}=\mathop{\sum }_{i\leqslant r}\unicode[STIX]{x1D6FA}(g(\unicode[STIX]{x1D6FC}_{i}))\end{eqnarray}$$

is seen to be

$$\begin{eqnarray}\mathop{\sum }_{k=1}^{\infty }k(\unicode[STIX]{x1D70B}_{Q}(q_{r+1}^{1/s_{k-1}})-\unicode[STIX]{x1D70B}_{Q}(q_{r+1}^{1/s_{k}}))=r+1+\mathop{\sum }_{k=1}^{\infty }\unicode[STIX]{x1D70B}_{Q}(q_{r+1}^{1/s_{k}})=:r+E.\end{eqnarray}$$

To handle $E$ , we split the term for $k=1$ from the sum and estimate the rest trivially, thereby obtaining $E\ll \unicode[STIX]{x1D70B}(q_{r+1}^{1/s_{1}})$ . Also, by (7.5), $\unicode[STIX]{x1D6FA}(N^{\prime \prime })\geqslant r$ , so that

$$\begin{eqnarray}\unicode[STIX]{x1D6FA}(N^{\prime \prime })=r+{\mathcal{O}}(\unicode[STIX]{x1D70B}(q_{r+1}^{1/c_{\ast }q_{1}})).\end{eqnarray}$$

Hence,

(7.6) $$\begin{eqnarray}r\leqslant \unicode[STIX]{x1D6FA}(N^{\prime \prime })\leqslant r+r^{\unicode[STIX]{x1D703}},\end{eqnarray}$$

where $\unicode[STIX]{x1D703}\in (1/c_{\ast }q_{1},1)$ is some constant (recall that by (A.4) this interval is non-empty). In particular, $r\gg s$ so that, by (7.3), $r$ must be large if $n$ is sufficiently large. The next goal is to determine $g(\unicode[STIX]{x1D6FC}_{i})$ for all $i$ in a suitable range. To this end, first note that, by Lemma 6.1 (3), we find that $g(\unicode[STIX]{x1D6FC}_{i})$ is prime for all $i>r^{\unicode[STIX]{x1D703}}$ . Let $\unicode[STIX]{x1D700}=(3K+1)(\log _{3}n)/\text{log}_{2}\,n$ , and assume that $n$ is sufficiently large to ensure that $\unicode[STIX]{x1D700}<1-\unicode[STIX]{x1D703}$ . By (7.3),

(7.7) $$\begin{eqnarray}2r^{\unicode[STIX]{x1D703}}\leqslant 2(\unicode[STIX]{x1D6FA}(N^{\prime \prime }))^{\unicode[STIX]{x1D703}}\leqslant 2(s(\log _{2}n)^{K})^{\unicode[STIX]{x1D703}}\leqslant s^{1-\unicode[STIX]{x1D700}}\leqslant \mathop{\sum }_{s-s^{1-\unicode[STIX]{x1D700}}<j<s}a_{j},\end{eqnarray}$$

for $n$ sufficiently large. Hence,

(7.8) $$\begin{eqnarray}\mathop{\sum }_{j\leqslant s-s^{1-\unicode[STIX]{x1D700}}}a_{j}\leqslant \unicode[STIX]{x1D6FA}(N^{\prime \prime })-2r^{\unicode[STIX]{x1D703}}\leqslant r-r^{\unicode[STIX]{x1D703}}.\end{eqnarray}$$

As explained above, $g(\unicode[STIX]{x1D6FC}_{i})$ is prime for all $i>r^{\unicode[STIX]{x1D703}}$ , and from (7.8) we know that this surely is the case for all $i\geqslant r-\sum _{k\leqslant j}a_{k}$ , where $j\leqslant s-s^{1-\unicode[STIX]{x1D700}}$ . Since, by Lemma 6.1 (1), the values $g(\unicode[STIX]{x1D6FC}_{i})$ are decreasing as $i$ increases, this yields that $g(\unicode[STIX]{x1D6FC}_{i})=v_{j}$ for $r-\sum _{k\leqslant j}a_{k}<i\leqslant r-\sum _{k<j}a_{k}$ . By (7.6) and (7.7),

(7.9) $$\begin{eqnarray}r-\mathop{\sum }_{k\leqslant j}a_{k}=r-\unicode[STIX]{x1D6FA}(N^{\prime \prime })+\mathop{\sum }_{k\leqslant s-j}a_{j+k}\geqslant s-j-r^{\unicode[STIX]{x1D703}}\geqslant \frac{1}{2}s^{1-\unicode[STIX]{x1D700}}.\end{eqnarray}$$

From (A.7) and (A.1) we deduce that

(7.10) $$\begin{eqnarray}g^{\dagger }(q_{j})\geqslant c_{\dagger }q_{j}+{\mathcal{O}}(q_{j}/\text{log}\,q_{j})\geqslant c_{\dagger }\unicode[STIX]{x1D705}j\log j\end{eqnarray}$$

for all sufficiently large $j$ . Hence, by (7.10) and (7.9),

$$\begin{eqnarray}\log m_{N^{\prime \prime }}\geqslant c_{\dagger }\unicode[STIX]{x1D705}\mathop{\sum }_{s^{1-\unicode[STIX]{x1D700}}\leqslant j\leqslant s-s^{1-\unicode[STIX]{x1D700}}}j(\log j)a_{j}(\log s+{\mathcal{O}}(\log _{3}n)).\end{eqnarray}$$

By (7.3), we find that the right-hand side above exceeds

$$\begin{eqnarray}\displaystyle & & \displaystyle \mathop{\sum }_{s^{1-\unicode[STIX]{x1D700}}\leqslant j\leqslant s-s^{1-\unicode[STIX]{x1D700}}}(1-\unicode[STIX]{x1D700})(\log s)^{2}ja_{j}\biggl(1+{\mathcal{O}}\biggl(\frac{\log _{3}n}{\log s}\biggr)\biggr)\nonumber\\ \displaystyle & & \displaystyle \quad \geqslant \mathop{\sum }_{s^{1-\unicode[STIX]{x1D700}}\leqslant j\leqslant s-s^{1-\unicode[STIX]{x1D700}}}(1+{\mathcal{O}}(\unicode[STIX]{x1D700}))(\log _{2}n)^{2}ja_{j}.\nonumber\end{eqnarray}$$

By the choice of $\unicode[STIX]{x1D700}$ , we get $s^{\unicode[STIX]{x1D700}}\gg (\log _{2}n)^{-K-1}$ . Also, $\sum _{j\leqslant s}ja_{j}\geqslant {\textstyle \frac{1}{2}}s^{2}$ . Now recalling that $a_{j}\leqslant (\log _{2}n)^{K}$ for every $j$ , we infer that

$$\begin{eqnarray}\displaystyle \mathop{\sum }_{s^{1-\unicode[STIX]{x1D700}}\leqslant j\leqslant s-s^{1-\unicode[STIX]{x1D700}}}ja_{j} & = & \displaystyle \mathop{\sum }_{j\leqslant s}ja_{j}+{\mathcal{O}}(s^{2-\unicode[STIX]{x1D700}}(\log _{2}n)^{K})\nonumber\\ \displaystyle & = & \displaystyle \biggl(1+{\mathcal{O}}\biggl(\frac{1}{\log _{2}n}\biggr)\biggr)\mathop{\sum }_{j\leqslant s}ja_{j},\nonumber\end{eqnarray}$$

thus completing the proof. ◻

8 Proof of Theorem 4.2

Recall that the main term in the upper bound in Theorem 4.1 stems from an application of Lemma 6.2. Given some large $x>1$ , we wish to find an integer $n$ smaller than $x$ , such that

$$\begin{eqnarray}\log f(f(n))=\mathop{\sum }_{\substack{ q\in Q \\ q\mid f(n)}}\log g(\unicode[STIX]{x1D708}_{q}(f(n)))\end{eqnarray}$$

is large. The idea is to realize equality in Lemma 6.2. Therefore, recalling that the inequality was obtained by applying the Cauchy–Schwarz inequality to (6.4), we would like to have

$$\begin{eqnarray}\#\{q\in Q:\unicode[STIX]{x1D708}_{q}(f(n))\geqslant i\}\approx \text{const}\times \log \frac{g(i)}{g(i-1)}\quad (i\geqslant 1)\end{eqnarray}$$

with some constant, independent of $i$ . Furthermore, to have suitable control over $f(n)$ it seems reasonable to choose $n$ such that the factorization of $f(n)$ is known. With this in mind, let $\unicode[STIX]{x1D700}=c_{\text{e}}(\log _{3}x/\text{log}_{2}\,x)$ for $c_{\text{e}}$ sufficiently large, where

$$\begin{eqnarray}t=\biggl\lfloor\biggl(\frac{8\log g(1)}{C_{g}}-\unicode[STIX]{x1D700}\biggr)\frac{\sqrt{\log x}}{\log _{2}x}\biggr\rfloor,\end{eqnarray}$$

and consider

$$\begin{eqnarray}\unicode[STIX]{x1D708}_{j}:=\biggl\lfloor1-\frac{1}{\unicode[STIX]{x1D6FC}}+\frac{1}{(\unicode[STIX]{x1D6FC}+1)^{j/t}-1}\biggr\rfloor\quad (1\leqslant j\leqslant t).\end{eqnarray}$$

Evidently,

(8.1) $$\begin{eqnarray}\unicode[STIX]{x1D708}_{j}=\frac{1}{\log (\unicode[STIX]{x1D6FC}+1)}\frac{t}{j}+{\mathcal{O}}(1).\end{eqnarray}$$

Letting

$$\begin{eqnarray}n=\mathop{\prod }_{j\leqslant t}\mathop{\prod }_{i\leqslant \unicode[STIX]{x1D708}_{j}}q_{\unicode[STIX]{x1D708}_{1}+\cdots +\unicode[STIX]{x1D708}_{j-1}+i}^{g^{\dagger }(q_{j})},\end{eqnarray}$$

we find that

$$\begin{eqnarray}f(n)=\mathop{\prod }_{j\leqslant t}g(g^{\dagger }(q_{j}))^{\unicode[STIX]{x1D708}_{j}}=\mathop{\prod }_{j\leqslant t}q_{j}^{\unicode[STIX]{x1D708}_{j}}.\end{eqnarray}$$

Now it remains to give a good lower bound on $\log f(f(n))$ and an upper bound on $n$ . To obtain the upper bound, let

(8.2) $$\begin{eqnarray}y_{i}=\#\{j:\unicode[STIX]{x1D708}_{j}\geqslant i\}=\biggl\lfloor\frac{t}{\log (\unicode[STIX]{x1D6FC}+1)}\log \biggl(1+\frac{1}{i-1+\unicode[STIX]{x1D6FC}^{-1}}\biggr)\biggr\rfloor.\end{eqnarray}$$

Observe that $\unicode[STIX]{x1D708}_{1}+\cdots +\unicode[STIX]{x1D708}_{t}\ll t\log t$ . Using (A.1), we find that

$$\begin{eqnarray}\log q_{\unicode[STIX]{x1D708}_{1}+\cdots +\unicode[STIX]{x1D708}_{t}}\leqslant \log t+2\log _{2}t+{\mathcal{O}}(1).\end{eqnarray}$$

Hence,

$$\begin{eqnarray}\displaystyle \log n & {\leqslant} & \displaystyle \mathop{\sum }_{j\leqslant t}\unicode[STIX]{x1D708}_{j}g^{\dagger }(q_{j})\log q_{\unicode[STIX]{x1D708}_{1}+\cdots +\unicode[STIX]{x1D708}_{j}}\nonumber\\ \displaystyle & {\leqslant} & \displaystyle \frac{\unicode[STIX]{x1D705}}{\unicode[STIX]{x1D6FC}}((\log t)^{2}+3(\log _{2}t)\log t+{\mathcal{O}}(\log t))\mathop{\sum }_{j\leqslant t}j\unicode[STIX]{x1D708}_{j}.\nonumber\end{eqnarray}$$

Since $y_{i}={\mathcal{O}}(t/i)$ and by (8.1) and (4.5),

$$\begin{eqnarray}\displaystyle \mathop{\sum }_{j\leqslant t}j\unicode[STIX]{x1D708}_{j} & = & \displaystyle \frac{1}{2}\mathop{\sum }_{i\leqslant \unicode[STIX]{x1D708}_{1}}y_{i}(y_{i}+1)\nonumber\\ \displaystyle & = & \displaystyle \frac{t^{2}}{2(\log (\unicode[STIX]{x1D6FC}+1))^{2}}\mathop{\sum }_{i=1}^{\infty }\biggl(\log \biggl(1+\frac{1}{i-1+\unicode[STIX]{x1D6FC}^{-1}}\biggr)\biggr)^{2}+{\mathcal{O}}(t\log t)\nonumber\\ \displaystyle & = & \displaystyle \frac{t^{2}C_{g}^{2}}{16(\log (\unicode[STIX]{x1D6FC}+1))^{2}}+{\mathcal{O}}(t\log t).\nonumber\end{eqnarray}$$

By the definition of $t$ , $\log t=\frac{1}{2}\log _{2}x-\log _{3}x+{\mathcal{O}}(1)$ and $\log _{2}t=\log _{3}x+{\mathcal{O}}(1)$ . By choosing $c_{\text{e}}$ sufficiently large, we get

$$\begin{eqnarray}\biggl(1+{\mathcal{O}}\biggl(\frac{\log _{3}x}{\log _{2}x}\biggr)\biggr)\biggl(1-\frac{C_{g}c_{\text{e}}}{8\log (\unicode[STIX]{x1D6FC}+1)}\frac{\log _{3}x}{\log _{2}x}\biggr)^{2}\leqslant 1.\end{eqnarray}$$

Thus, we infer

$$\begin{eqnarray}\log n\leqslant \frac{\unicode[STIX]{x1D705}}{\unicode[STIX]{x1D6FC}}\biggl(1+{\mathcal{O}}\biggl(\frac{\log _{3}x}{\log _{2}x}\biggr)\biggr)\biggl(1-\frac{\unicode[STIX]{x1D700}C_{g}}{8\log (\unicode[STIX]{x1D6FC}+1)}\biggr)^{2}\log x\end{eqnarray}$$

so that $n\leqslant x^{\unicode[STIX]{x1D705}/\unicode[STIX]{x1D6FC}}$ if $x$ is sufficiently large. Next, we estimate $\log f(f(n))$ : using partial summation and (8.2),

$$\begin{eqnarray}\displaystyle \log f(f(n)) & = & \displaystyle \mathop{\sum }_{j\leqslant t}\log g(\unicode[STIX]{x1D708}_{j})=\mathop{\sum }_{i=1}^{\infty }(y_{i}-y_{i+1})\log g(i)\nonumber\\ \displaystyle & = & \displaystyle \mathop{\sum }_{i=1}^{\infty }y_{i}\log \frac{g(i)}{g(i-1)}.\nonumber\end{eqnarray}$$

Due to the construction of $n$ , the last sum simplifies to

$$\begin{eqnarray}\displaystyle & & \displaystyle \mathop{\sum }_{i\leqslant \unicode[STIX]{x1D708}_{1}}y_{i}\log \frac{g(i)}{g(i-1)}\nonumber\\ \displaystyle & & \displaystyle \quad =\mathop{\sum }_{i\leqslant \unicode[STIX]{x1D708}_{1}}\biggl(\frac{t}{\log (\unicode[STIX]{x1D6FC}+1)}\biggl(\log \frac{g(i)}{g(i-1)}\biggr)^{2}+{\mathcal{O}}(1/i)\biggr)\nonumber\\ \displaystyle & & \displaystyle \quad =\frac{C_{g}^{2}}{8\log (\unicode[STIX]{x1D6FC}+1)}t+{\mathcal{O}}(\log t)\nonumber\\ \displaystyle & & \displaystyle \quad =\frac{\sqrt{\log x}}{\log _{2}x}\biggl(C_{g}+{\mathcal{O}}\biggl(\frac{\log _{3}x}{\log _{2}x}\biggr)\biggr).\nonumber\end{eqnarray}$$

Since $M(x^{\unicode[STIX]{x1D705}/\unicode[STIX]{x1D6FC}})\geqslant \log f(f(n))$ , we infer (4.6). This concludes the proof.