\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{amsfonts} \usepackage{latexsym} \usepackage{epsf} \usepackage{amsthm} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \def\RR{I\!\!R} \def\NN{I\!\! N} \def\ZZ{Z\!\!\!Z} \def\QQ{\mathbb Q} \newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm{\LARGE\bf {On the Distribution of Perfect Totients}} \vskip 1cm \large Florian~Luca\\ Instituto de Matem{\'a}ticas\\ Universidad Nacional Aut\'onoma de M{\'e}xico\\ C.P.~58089 \\ Morelia, Michoac{\'a}n \\ M{\'e}xico\\ \href{mailto:fluca@matmor.unam.mx}{\tt fluca@matmor.unam.mx}\\ \end{center} \vskip .2 in \begin{abstract} In this paper, we study the sum of iterates of the Euler function. \end{abstract} \renewcommand{\theequation}{\arabic{equation}} \renewcommand{\theequation}{\arabic{equation}} \newtheorem{prop}{Proposition} \newtheorem{lemma}[prop]{Lemma} \newtheorem{cor}{Corollary} \newtheorem{corollary}[cor]{Corollary} \newtheorem{conj}[prop]{Conjecture} \newtheorem{defi}[prop]{Definition} \newtheorem{theorem}[prop]{Theorem} \newtheorem{fac}[prop]{Fact} \newtheorem{facs}[prop]{Facts} \newtheorem{com}[prop]{Comments} \newtheorem{prob}{Problem} \newtheorem{problem}[prob]{Problem} \newtheorem{ques}{Question} \newtheorem{question}[ques]{Question} \newtheorem{remark}[prop]{Remark} \section{Introduction} For every positive integer $n$ we put $\phi(n)$ for the Euler function of $n$. If $k\ge 1$ we put $\phi^{(k)}(n)$ for the $k$th iterate of the Euler function evaluated in $n$ and $\kappa(n)$ for the smallest positive integer $n$ such that $\phi^{(\kappa(n))}(n)=1$. Let $$ F(n)=\sum_{k=1}^{\kappa(n)} \phi^{(k)}(n). $$ Positive integers $n$ such that $F(n)=n$ are called {\it perfect totients} and were introduced in \cite{MS} and studied also in \cite{Ian} and \cite{S}. Let ${\cal M}$ be the set of all perfect totients. This set contains all powers of $3$ so it is certainly infinite. In the recent paper \cite{S} it was shown that ${\cal M}$ is of asymptotic density zero. More precisely, if we write ${\cal M}(x)={\cal M}\cap [1,x]$, then it was shown in Theorem 2.2 in \cite{S} -- a little bit more than -- that the estimate \begin{equation} \label{eq:M(x)S} \#{\cal M}(x)\le \frac{x}{(\log x)^{1+o(1)}} \end{equation} holds as $x\to\infty$. The above estimate \eqref{eq:M(x)S} is too weak to allow one to decide whether the sum \begin{equation} \label{eq:sumofreciprocalsM} \sum_{m\in {\cal M}}\frac{1}{m} \end{equation} is finite. Here, we prove a stronger upper bound on $\#{\cal M}(x)$ than \eqref{eq:M(x)S} which in particular implies that the sum of the series \eqref{eq:sumofreciprocalsM} is convergent. \begin{theorem} \label{thm:1} The estimate \begin{equation} \label{eq:M(x)L} \#{\cal M}(x)\le \frac{x}{(\log x)^{2+o(1)}} \end{equation} holds as $x\to\infty$. \end{theorem} It was also shown in \cite{S} that the inequality \begin{equation} \label{eq:F(n)minusnS} |F(n)-n|>(\log n)^{\ln 2+o(1)} \end{equation} holds on a set of positive integers $n$ of asymptotic density $1$. Here, we improve this to: \begin{theorem} \label{thm:2} Let $\varepsilon(x)$ be any function defined on the positive real numbers $x$ with values in the positive real numbers which is decreasing for large $x$ and $\lim_{x\to\infty} \varepsilon(x)=0$. Then the inequality \begin{equation} \label{F(n)minusnL} n-F(n)>\varepsilon(n)n \end{equation} holds on a set of positive integers $n$ of asymptotic density $1$. \end{theorem} Let ${\cal U}(x)=\{F(n)\le x\}$. In \cite{S}, it was shown that $\#{\cal U}(x)\gg (\log x)^2$ and it was asked to show that $\log(\#{\cal U}(x))/\log\log x$ tends to infinity with $x$. We prove: \begin{theorem} \label{thm:3} The estimate \begin{equation} \label{eq:U(x)L} \log\left(\#{\cal U}(x)\right)\gg \frac{(\log\log x)^2}{\log\log\log\log x} \end{equation} holds for all positive integers $x$. \end{theorem} Throughout this paper, we use $\log x=\max\{\ln x, 1\}$, where $\ln $ is the natural logarithm. Further, if $k\ge 1$, we write $\log_k x$ for the $k$th fold iterate of the function $\log $. We omit the subscript when $k=1$. We use the Vinogradov symbols $\ll $, $\gg$ and $\asymp$, as well as the Landau symbols $O$ and $o$ with their regular meanings. The constants of convergence implied by them may depend on some fixed parameters such as $K$ (see Section \ref{sec:aux}). For a positive integer $n$, we use $P(n)$ for its largest prime factor with the convention that $P(1)=1$, $\omega(n)$ for the number of distinct prime factors of $n$ and $\nu_2(n)$ for the $2$-adic order of $n$; i.e., the largest non-negative integer $k$ such that $2^k\mid n$. We use $p,~q$ and $r$ to denote prime numbers and $c_0,~c_1,~\ldots$ to denote positive constants which are absolute. \section{Proof of Theorem 1} \label{sec:proofThm1} The proof of inequality \eqref{eq:M(x)S} in \cite{S} is based on the fact that if we put ${\cal V}(x)=\{\phi(n)\le x\}$, then $\#{\cal V}(x)\le x/(\log x)^{1+o(1)}$ (see \cite{Fo} and \cite{MP}) together with the observation that if $n\in {\cal M}(x)$, then $n=v+F(v)$ for some $v\in {\cal V}(x)$ (namely, $v=\phi(n)$). \medskip For our proof of Theorem \ref{thm:1}, we take a different approach and we exploit the numbers $\nu_2(\phi^{(2)}(n))$ and $\nu_2(\phi^{(3)}(n))$ for $n\in {\cal M}(x)$. Before we start, we record a result which might be of independent interest. \subsection{An auxiliary result} \label{sec:aux} Let $K>0$ be any fixed constant. Put $$ {\cal N}(K,x)=\{n\le x~:~\nu_2(\phi^{(2)}(n))\le K\log_2 x\}. $$ \begin{lemma} \label{lem:1} \begin{itemize} \item[(i)] The estimate $$ \sum_{n\in {\cal N}(K,x)}\frac{1}{n}=(\log x)^{o(1)} $$ holds as $x\to\infty$. \item[(ii)] Let $\pi(K,x)=\#\{p\le x~:~p-1\in {\cal N}(K,x)\}$. Then $$ \pi(K,x)\le \frac{x}{(\log x)^{2+o(1)}} $$ holds as $x\to\infty$. \end{itemize} \end{lemma} \begin{proof} (i) Put $L=10\log_2 x$. Let ${\cal N}_1$ be the set of $n\in {\cal N}(K,x)$ with $\omega(n)\ge L$ and note that \begin{eqnarray} \label{eq:S1} S_1 & = & \sum_{n\in {\cal N}_1}\frac{1}{n} \le \sum_{\substack{n\le x\\ \omega(n)\ge L}}\frac{1}{n} \le \sum_{k\ge L}\sum_{\substack{n\le x\\ \omega(n)=k}}\frac{1}{n} \le \sum_{k\ge L}\frac{1}{k!}\left(\sum_{p^{\alpha}\le x} \frac{1}{p^{\alpha}}\right)^k\nonumber\\ & \le & \sum_{k\ge L}\frac{1}{k!}\left(\log_2 x+c_0\right)^k \ll \sum_{k\ge L}\left(\frac{e\log_2 x+ec_0}{k}\right)^k\nonumber\\ & \le & \sum_{k\ge L}\left(\frac{e\log_2 x+ec_0}{L}\right)^k \ll \left(\frac{e\log_2 x+ec_0}{L}\right)^L \ll 1. \end{eqnarray} In the above inequalities, we used the multinomial formula, the unique factorization, the estimate $k!\gg (k/e)^k$ which follows from Stirling's formula, as well as the known fact that the estimate $$ \sum_{p\le x}\sum_{\alpha\ge 1}\frac{1}{p^{\alpha}}\le \log_2 x + c_0 $$ holds for all $x$ with some absolute constant $c_0$. \medskip Put $y=(\log x)^2$ and let ${\cal N}_2$ be the subset of $n\in {\cal N}(K,x)$ having two distinct prime factors $p$ and $q$ such that $\gcd(p-1,q-1)$ is a multiple of some prime $r>y$. Writing $n=pqm$ for some positive integer $m$, we see that the sum $S_2$ of the reciprocals of $n\in {\cal N}_2$ satisfies \begin{eqnarray} \label{eq:S2} S_2 & = & \sum_{n\in {\cal N}_2}\frac{1}{n}\le \sum_{yt}(n)$ for the number of distinct prime factors $p>t$ of $n$. Let $n\in {\cal N}_3$ and write it as $n=abc$, where \begin{itemize} \item[(i)] all prime factors of $a$ are $\le z$; \item[(ii)] all prime factors $p$ of $b$ are $>z$ but $\omega_{>y}(p-1)<\log_2 p/(\log_3 p)^2$; \item[(iii)] all prime factors $p$ of $c$ are $>z$ and $\omega_{>y}(p-1)\ge \log_2 p/(\log_3 p)^2$. \end{itemize} Note that if $p\mid c$, then $$ \omega_{>y}(p-1)\ge \frac{\log_2 p}{(\log_3 p)^2}\ge \frac{\log_2 z}{(\log_3 z)^2}> \frac{\log_2 x}{(\log_3 x)^3} $$ for large $x$. Further, for $t>2$ we have that $\omega_{>t}(n)\le\nu_2(\phi(n))$. Furthermore, since $n\not\in {\cal N}_2$, we have that \begin{eqnarray*} \sum_{p\, |\, c}\omega_{>y}(p-1) & \le & \sum_{p\, |\, n}\omega_{y}(p-1)= \omega_{>y}\left(\prod_{p\, |\, n} (p-1) \right)\\ & \le & \nu_2\left(\phi\left(\prod_{p\, |\, n} (p-1)\right)\right)\le \nu_2(\phi^{(2)}(n)) \le K\log_2 x. \end{eqnarray*} We thus get that $$ \omega(c)\frac{\log_2 x}{(\log_3 x)^3}<\sum_{p\, |\, c}\omega_{>y}(p-1) \le K\log_2 x, $$ therefore $$ \omega(c)< K(\log_3 x)^3. $$ Let ${\cal A},~{\cal B}$ and ${\cal C}$ be the subsets of all possible values of $a,~b$ and $c$, respectively. Thus, \begin{equation} \label{eq:S3} S_3=\sum_{n\in {\cal N}_3}\frac{1}{n}\le ABC, \end{equation} where \begin{equation} \label{eq:ABC} A=\sum_{a\in {\cal A}} \frac{1}{a},\qquad B=\sum_{b\in {\cal B}}\frac{1}{b}\qquad {\text{\rm and}}\qquad C=\sum_{c\in {\cal C}} \frac{1}{c}. \end{equation} Since the union of ${\cal N}_i$ for $i=1,~2$ and $3$ covers ${\cal N}(K,x)$ it follows, by estimates \eqref{eq:S1}, \eqref{eq:S2}, \eqref{eq:S3} and \eqref{eq:ABC}, that in order to establish (i) it suffices to show that \begin{equation} \label{eq:maxABC} \max\{A,B,C\}\le (\log x)^{o(1)}\qquad {\text{\rm as}}~x\to\infty. \end{equation} Clearly ${\cal A}\subset \{a\le x~:~P(a)\le z\}$ and ${\cal C}\subset \{c\le x~:~\omega(c)\le K(\log_3 x)^3\}$. Hence, \begin{eqnarray} \label{eq:A} A & \le & \prod_{p\le z}\left(\sum_{\alpha\ge 0}\frac{1}{p^{\alpha}}\right) \le \exp\left(\sum_{p\le z}\sum_{\alpha\ge 1}\frac{1}{p^{\alpha}}\right) \le \exp(\log_2 z+c_0)\nonumber\\ & \ll & \log z=(\log x)^{1/\log_3 x}=(\log x)^{o(1)} \qquad {\text{\rm as}}~x\to\infty, \end{eqnarray} while by an argument similar to the one used to bound $S_1$ (see estimate \eqref{eq:S1}), we get \begin{eqnarray} \label{eq:C} C & \le & \sum_{k\le K(\log_3 x)^3}\sum_{\substack{c\le x\\ \omega(c)=k}}\frac{1}{c} \le \sum_{k\le K(\log_3 x)^3}\left(\frac{e\log_2 x+ec_0}{k}\right)^k \nonumber\\ & \ll & (\log_3 x)^3(e\log_2 x+ec_0)^{K(\log_3 x)^3}\nonumber\\ & = & (\log x)^{O((\log_3 x)^4/\log_2 x)}= (\log x)^{o(1)}\qquad {\text{\rm as}}~x\to\infty. \end{eqnarray} For ${\cal B}$, let $f(t)=(\log t)^{3\log_3 t}$ and note that \begin{eqnarray*} f(z) = \exp(3\log_2 z\log_3 z) & > & \exp(2\log_2 z\log_3 x)=\exp(2\log_2 x)= (\log x)^2\\ & = & y\qquad {\text{\rm for~large}}~x, \end{eqnarray*} therefore all the primes $p$ dividing $b\in {\cal B}$ belong to the set $$ {\cal P}=\{p~:~\omega_{>f(p)}<\log_2 p/(\log_3 p)^2\} $$ for large values of $x$. We show that \begin{equation} \label{eq:sum1overP} \sum_{p\in {\cal P}}\frac{1}{p}=O(1). \end{equation} Note that once the above estimate \eqref{eq:sum1overP} is proved, then $$ B=\sum_{b\in {\cal B}}\frac{1}{b}\le \prod_{p\in {\cal P}} \left(\sum_{\alpha\ge 0}\frac{1}{p^{\alpha}}\right)\le \exp\left(\sum_{p\in {\cal P}}\sum_{\alpha\ge 1}\frac{1}{p^{\alpha}}\right) =\exp(O(1))=O(1), $$ which together with estimates \eqref{eq:A} and \eqref{eq:C} implies estimate \eqref{eq:maxABC} and completes the proof of (i). \medskip Thus, it remains to prove estimate \eqref{eq:sum1overP}. For this, let $t>0$ and put ${\cal P}(t)={\cal P}\cap [1,t]$. We estimate the counting function $\#{\cal P}(t)$ of ${\cal P}$. Let $p\in {\cal P}(t)$. Let ${\cal P}_1=\{p\le t~:~P(p-1)\le t^{1/\log_2 t}\}$. By results from \cite{CEP} (see also Chapter III.5 of \cite{Ten}), it follows that \begin{equation} \label{eq:P1} \#{\cal P}_1(t)\le t\exp(-(1+o(1))\log_2 t\log_3 t)= o\left(\frac{t}{(\log t)^2}\right)\qquad {\text{\rm as}}~t\to\infty. \end{equation} For $p\in {\cal P}_2={\cal P}(t)\backslash {\cal P}_1$, we write $p-1=q\ell$, where $q=P(p-1)$ and $\ell$ is some positive integer. Fix $\ell$. Then $q\le t/\ell$ is such that both linear forms $q$ and $q\ell+1$ are primes. By Brun's sieve (see, for example, Theorem 2.3 in \cite{HR}), the number of such primes $q$ is $$ \ll \frac{t}{\ell(\log(t/\ell))^2}\left(\frac{\ell}{\phi(\ell)}\right)^2 \le \frac{t(\log_2 t)^4}{\ell(\log t)^2}, $$ where we used the minimal order $\phi(\ell)/\ell\gg 1/\log_2 t$ of the Euler function in the interval $[1,t]$ as well as the fact that $$ \log\left(\frac{t}{\ell}\right)\ge \log q\ge \log(t^{1/\log_2 t})= \frac{\log t}{\log_2 t}. $$ Since $\ell$ is a divisor of $p-1$, we get that if we write $\ell=\ell_1 \ell_2$, where $P(\ell_1)\le f(t)$ and every prime factor of $\ell_2$ is $>f(t)$, then $$ \omega(\ell_2)=\omega_{>f(t)}(p-1) \le \omega_{(\log x)^2$ such that $q^2\mid n$. It is clear that the number of such positive integers does not exceed $$ \sum_{(\log x)^2(\log x)^2$ with the property that $q\mid \gcd(P-1,\phi(m))$. Since $n$ is not like in (ii), it follows that $q^2$ does not divide $n$. Thus, there must exist a prime factor $r$ of $m$ such that $q\mid r-1$. Fixing $q$, $r$ and $P$, we get that the number of $n\le x$ which are multiples of $Pr$ does not exceed $x/Pr$. Hence, the totality of such integers $n$ does not exceed \begin{eqnarray*} & & \sum_{(\log x)^2\le q\le x^{1/2}} \sum_{\substack{q\, |\, \gcd(P-1,r-1)\\ Pr\le x}}\frac{x}{Pr} \le x\sum_{(\log x)^2\le q\le x^{1/2}} \frac{1}{2}\left(\sum_{\substack{p\equiv 1 \pmod q\\ p\le x}}\frac{1}{p}\right)^2 \\ & & \ll x(\log_2 x)^2 \sum_{(\log x)^2\le q\le x^{1/2}}\frac{1}{q^2} \ll \frac{x\log_2 x}{(\log x)^2}. \end{eqnarray*} \item[(vi)] positive integers $n$ not of the form (i)--(v) such that if we write $n=Pm$ with $P=P(n)>P(m)$, then $m\equiv -1\pmod {2^{M}}$, where $M=\lfloor 5\log_2 x\rfloor$. For each such fixed $m$, the number of possible choices for $P\le x/m$ is $$ \pi\left(\frac{x}{m}\right)\le \frac{x}{m\log(x/m)}\le \frac{x}{m\log y}= \frac{x\log_2 x} {m\log x}. $$ Summing up over all the $m\le x$ of the form $m=2^{M}\lambda-1$ for some $\lambda\ge 1$, we get that the totality of such $n$ does not exceed \begin{eqnarray*} & & \frac{x\log_2 x}{\log x}\sum_{1\le \lambda\le x/2^M} \frac{1}{2^M\lambda-1}\ll \frac{x\log_2 x}{2^{M}\log x}\sum_{1\le \lambda\le x}\frac{1}{\lambda}\\ && \ll \frac{x\log_2 x}{2^M}\ll \frac{x\log_2 x}{(\log x)^{5\log 2}}= o\left(\frac{x}{(\log x)^2} \right)\qquad {\text{\rm as}}~x\to\infty. \end{eqnarray*} \end{itemize} From now on, we work with the set ${\cal M}'$ of the perfect totients $n\le x$ not satisfying any of the conditions (i)--(vi) above. Note that if $n>2$, then $F(n)$ is always odd. Hence, $n$ is odd. \medskip Let ${\cal M}_1$ be the subset of $n\in {\cal M}'$ such that $\nu_2(\phi^{(2)}(n))\ge 2M$. We now make the observation that if $m$ is an even number, then $\nu_2(\phi(m))\ge \nu_2(m)$ {\it except} when $m$ is a power of $2$. Further, note that if $\phi^{(\ell)}(m)$ is a power of $2$, then $\phi^{(\ell+i)}(m)$ is also a power of $2$ for all $i\ge 0$. Thus, letting $\kappa_1(n)$ be the largest positive integer $\ell\ge 2$ such that $\phi^{(\ell)}(n)$ is not a power of $2$, from the above remark we get that for $n\in {\cal M}_1$ we have $$ 2M\le \nu_2(\phi^{(2)}(n))\le \nu_2(\phi^{(3)}(n))\le \ldots \le \nu_2(\phi^{(\kappa_1(n)+1)}(n)). $$ Writing $\phi^{(\kappa_1(n)+1)}(n)=2^{\beta}$ with some $\beta\ge 2M$, we get $$ \sum_{k=\kappa_1(n)+1}^{\kappa(n)} \phi^{(k)}(n)=\sum_{i=0}^{\beta} 2^i=2^{\beta+1}-1. $$ Since $n$ is a perfect totient, we get the following congruence \begin{eqnarray} \label{eq:cong} n-\phi(n)+1 & = & 1+ \sum_{k=2}^{\kappa(n)}\phi^{(k)}(n) = 1+ \sum_{k=2}^{\kappa_1(n)}\phi^{\ell}(n)+ \sum_{k=\kappa_1(n)+1}^{\kappa(n)}\phi^{(k)}(n)\nonumber\\ & = & \sum_{\ell=2}^{\kappa_1(n)}\phi^{(k)}(n)+2^{\beta+1} \equiv 0 \pmod {2^{2M}}. \end{eqnarray} Write $n=Pm$, where $P>\max\{P(m),y\}$ for large $x$ because $n$ is neither as in (i) nor as in (ii). So $$ n-\phi(n)+1=Pm-(P-1)\phi(m)+1=P(m-\phi(m))+(\phi(m)+1). $$ Note that $m>2$ if $x$ is large enough. Indeed, since $n$ is odd we get that if $m\le 2$, then $m=1$ and $n=P$, therefore $$ P\ge \phi(P)+\phi(\phi(P))=P-1+\phi(P-1), $$ leading to $1\ge \phi(P-1)$; thus, $P\le 3$, which is impossible for large $x$ since $P>y$. Since $m>2$, we get that $m-\phi(m)>0$ and $\phi(m)+1$ is odd. Thus, for fixed odd $m>1$ the congruence $$ P(m-\phi(m))+\phi(m)+1\equiv 0\pmod {2^{2M}} $$ puts $P$ into a certain residue class $a_m$ modulo $2^{2M}$. Since $P\le x/m$, it follows that the number of possibilities for $P$ is $\pi(x/m;2^{2M},a_m)$. By a result of Montgomery and Vaughan \cite{MV}, we know that \begin{equation} \label{eq:pi} \pi(x/m;2^{2M},a_m)\le \frac{2x}{m\phi(2^{2M})\log(x/m2^{2M})}. \end{equation} Note that \begin{equation} \label{eq:2toM} \frac{x}{m2^{2M}}\ge \frac{y}{(\log x)^{10\ln 2}}>y^{1/2} \end{equation} if $x$ is sufficiently large. Hence, inequalities \eqref{eq:pi} and \eqref{eq:2toM} lead to \begin{equation} \label{eq:pi1} \pi(x/m;2^{2M},a_m)\ll \frac{x}{m2^{2M}\log y}\ll \frac{x\log_2 x} {m(\log x)^{1+10\ln 2}}. \end{equation} Summing up over all the possible choices for $m$ we get that \begin{eqnarray} \label{eq:M1} \#{\cal M}_1 & \le & \sum_{m\le x/y}\pi(x/m;2^{2M},a_m)\ll \frac{x\log_2 x}{(\log x)^{1+10\ln 2}}\sum_{m\le x/y} \frac{1}{m}\nonumber\\ & \ll & \frac{x\log_2 x}{(\log x)^{10\ln 2}} = o\left(\frac{x}{(\log x)^2}\right)\qquad {\text{\rm as}}~x\to\infty. \end{eqnarray} Now let ${\cal M}_2$ be the subset of $n\in {\cal M}'\backslash {\cal M}_1$ such that $\nu_2(\phi^{(3)}(n))<4M$. Let $n=mP$. Since $n\not\in {\cal M}_1$, it follows that $\nu_2(\phi^{(2)}(m)) \le \nu_2(\phi^{(2)}(n))<2M$. In particular, $m\in {\cal N}(10,x)$. Further, since $$ \log_2(x/m)\ge \log_2 y\ge (\log_2 x)/2 $$ holds for large $x$ and all $mP(m)$, and $P-1=Q\ell$, where $Q=P(P-1)$. Note that we again have $m\in {\cal N}(10, x)$. Observe also that $Q>z$ because $n$ is not like in (iii). Since $z>(\log x)^3>(\log x)^2$ for large $x$ and $n$ is not like in (iv) or (v), we get that $Q$ does not divide $\phi(m)\ell$. Let $d$ be the largest divisor of $P-1$ which is divisible only by primes dividing $\phi(m)$. Thus, $P(d)<(\log x)^2$ and $d$ is a divisor of $\ell$. Write $\ell=ds$. From now on we fix $m$, the number $d$ which consists only of prime factors of $\phi(m)$ smaller than $(\log x)^2$, and the number $s$ which is coprime to $d\phi(m)$. Notice that $\phi(n)=(P-1)\phi(m)=Qsd\phi(m)$, every prime factor of $d$ divides $\phi(m)$, and $Qs$ is coprime to $\phi(m)$. Thus, $\phi(\phi(n))=(Q-1)\phi(s) d\phi(\phi(m))$. \medskip An argument identical to the one used to derive congruence \eqref{eq:cong} gives $$ n-\phi(n)-\phi(\phi(n))+1\equiv 0\pmod {2^{4M}} $$ for $n\in {\cal M}_3$. Note that \begin{eqnarray*} & & n-\phi(n)-\phi(\phi(n))+1 \\ & & = P(m-\phi(m))+(\phi(m)+1)-(Q-1)\phi(s)d\phi(\phi(m))\\ & & = (Qsd+1)(m-\phi(m))+(\phi(m)+1)-(Q-1)\phi(s)d\phi(\phi(m))\\ & & = Q(sd(m-\phi(m))-\phi(s)d\phi(\phi(m)))+(m-\phi(m))+(\phi(m)+1) \\ & & + \phi(s)d\phi(\phi(m))\\ & & = Q(sd(m-\phi(m))-\phi(s)d\phi(\phi(m)))+(m+1+\phi(s)d\phi(\phi(m))). \end{eqnarray*} Put $$C_{m,d,s}=sd(m-\phi(m))-\phi(s)d\phi(\phi(m))\quad {\text{\rm and}}\quad D_{m,d,s}=m+1+\phi(s)d\phi(\phi(m)). $$ Observe that $C_{m,d,s}\ne 0$ for large $x$. Indeed, if $C_{m,d,s}=0$, we then get \begin{eqnarray} \label{eq:comp1} n-\phi(n)-\phi(\phi(n))+1 & = & m+1+\phi(s)d\phi(\phi(m))\nonumber\\ & = & m+1+sd(m-\phi(m)) \nonumber\\ & \le & m+(P-1)\frac{m}{Q}\le \frac{mP}{y}+\frac{mP}{z}\nonumber\\ & \le & \frac{2mP}{z}. \end{eqnarray} However, since $n\in {\cal M}(x)$, we get that \begin{equation} \label{eq:comp2} n-\phi(n)-\phi(\phi(n))+1\ge \phi(\phi(\phi(n)))\gg \frac{n}{(\log_2 x)^3} =\frac{mP}{(\log_2 x)^3}. \end{equation} The last inequality above follows from applying the minimal order of the Euler function in the interval $[1,x]$ three times as $$ \frac{\phi^{(3)}(n)}{n}\gg \frac{\phi^{(2)}(n)}{n\log_2 x}\gg \frac{\phi(n)}{n(\log_2 x)^2}\gg \frac{1}{(\log_2 x)^3} $$ for $n\le x$. Comparing estimates \eqref{eq:comp1} and \eqref{eq:comp2}, we get that $$ \frac{2mP}{z}\gg \frac{mP}{(\log_2 x)^3}, $$ leading to $z\ll (\log_2 x)^3$, which is impossible for large $x$. \medskip Hence, $C_{m,d,s}\ne 0$ and \begin{equation} \label{eq:congimportant} C_{m,d,s}Q+D_{m,d,s}\equiv 0\pmod {2^{4M}}. \end{equation} Let ${\cal M}_4$ be the subset of ${\cal M}_3$ such that $2^{2M}$ divides both $C_{m,d,s}$ and $D_{m,d,s}$. Then $2^{2M}$ divides also $C_{m,d,s}+D_{m,d,s}=sd(m-\phi(m))+m+1.$ Note that $m-\phi(m)$ is odd because $m>1$ is odd. Further, since $n$ is not like in (vi), it follows that if we write $m+1=2^{\alpha} m_1$ where $m_1$ is odd, then $\alpha\le M$. Since $sd(m-\phi(m))+m+1$ is a multiple of $2^{2M}$, we get that $sd=2^{\alpha}s_1d_1$, where $s_1$ and $d_1$ are both odd. Further note that if $m>3$, then $\phi(\phi(m))$ is even, therefore $d=2^{\alpha}d_1$ and $s=s_1$. If $m=3$, then $\phi(\phi(m))=1$, therefore $d=1$ and $s=2^{\alpha}s_1$. Fixing $m$ and $d$ (hence, also $\alpha$ and $d_1$) the congruence $sd(m-\phi(m))+m+1\equiv 0\pmod {2^{2M}}$ leads to $s_1d_1(m-\phi(m))+m_1\equiv 0\pmod {2^{2M-\alpha}}$. Hence, $s_1$ belongs to a certain odd residue class $b_{m,d}$ modulo $2^{M}$. We assume that $b_{m,d}$ is the smallest positive integer in this class. Since $P-1=2^{\alpha}d_1s_1Q$, $P\le x/m$ and both $P$ and $Q$ are primes, it follows, by Brun's method (see again Theorem 2.3 in \cite{HR}), that the number of possibilities for $Q\le x/(m2^{\alpha}s_1d_1)$ when $m,~d_1$ and $s_1$ are fixed is $$ \ll \frac{x}{m\phi(2^{\alpha}s_1d_1)(\log(x/msd))^2} $$ Since $x/msd\ge Q\ge z$, we get, by using again the minimal order of the Euler function in the interval $[1,x]$, that the above number is bounded from above by $$ \ll \frac{x\log_2 x}{msd(\log z)^2}\le \frac{x(\log_2 x)^5}{m2^{\alpha}s_1d_1(\log x)^2}\ll \frac{x(\log_2 x)^5}{ms_1d_1(\log x)^2}. $$ Note that $\alpha$ is uniquely determined by $m$ alone. Summing up first over all $m\le x/y$ and in ${\cal N}(10,x)$, then over all odd $d_1\mid \phi(m)$ such that $P(d_1)\le (\log x)^2$, and finally over those $s_1\le x/(2^{\alpha}zmd_1)$ with $s_1 \equiv b_{m,d}\pmod {2^{M}}$, we get \begin{eqnarray} \label{eq:M4} \#{\cal M}_4 & \ll & \frac{x(\log_2 x)^5}{(\log x)^2}\sum_{\substack{m\le x/y\\ m\in {\cal N}(5,x)}}\frac{1}{m}\sum_{\substack{d_1\, |\, \phi(m)\\ P(d_1)\le (\log x)^2}}\frac{1}{d_1} \sum_{0\le \lambda\le x/(2^{M+\alpha}ms_1d_1)} \frac{1}{b_{m,d}+\lambda 2^{M}}\nonumber\\ & \le & \frac{x(\log_2 x)^5}{(\log x)^2} \left(\sum_{m\in {\cal N}(10,x)}\frac{1}{m} \sum_{\substack{d_1\equiv 1\pmod 2\\ p\,|\, d_1 => p\,|\, \phi(m)}}\frac{1}{d_1}\right)\left(1+ \frac{1}{2^M}\sum_{1\le \lambda\le x}\frac{1}{\lambda}\right)\nonumber\\ & \le & \frac{x(\log_2 x)^5}{(\log x)^2} \left(\sum_{m\in {\cal N}(10,x)}\frac{1}{m}\frac{\phi(m)}{\phi(\phi(m))} \right)\left(1+O\left(\frac{\log x}{2^M}\right)\right)\nonumber\\ & \ll & \frac{x(\log_2 x)^6}{(\log x)^2}\sum_{m\in {\cal N}(10,x)}\frac{1}{m} \le \frac{x}{(\log x)^{2+o(1)}}\qquad {\text{\rm as}}~x\to\infty, \end{eqnarray} where in the above inequalities we used the obvious fact that if $m$ is a positive integer then \begin{equation} \label{eq:idphi} \sum_{\substack{d\ge 1\\ p\, |\, d=> p\,|\, m}}\frac{1}{d}= \prod_{p\, |\, m}\left(\sum_{\alpha\ge 0}\frac{1}{p^{\alpha}}\right) =\prod_{p\,|\,m}\left(1-\frac{1}{p}\right)^{-1}=\frac{m}{\phi(m)}, \end{equation} the inequality $\phi(m)/\phi(\phi(m))\ll \log_2 x$ which follows from the minimal order of the Euler function in the interval $[1,x]$, as well as Lemma \ref{lem:1} (i). \medskip Finally, let ${\cal M}_5={\cal M}_3\backslash {\cal M}_4$. If $n\in {\cal M}_5$, then $n=Pm,~P=P(n)>P(m)$, $P-1=Qsd$, and $\gamma=\nu_2(\gcd(C_{m,d,s},D_{m,d,s})) p\, |\, \phi(m)}}\frac{1}{d} \sum_{s\le x/(zmd)}\frac{1}{s}\nonumber\\ & \ll & \frac{x(\log_2 x)^6}{2^M \log x}\sum_{m\in {\cal N}(10,x)} \frac{1}{m}\frac{\phi(m)}{\phi(\phi(m))}\ll \frac{x(\log_2 x)^7}{2^M\log x} \sum_{m\in {\cal N}(10,x)}\frac{1}{m}\nonumber\\ & \ll & \frac{x}{(\log x)^{1+10\ln 2+o(1)}}= o\left(\frac{x}{(\log x)^{2}}\right) \qquad {\text{\rm as}}~x\to\infty. \end{eqnarray} In the above estimates, we used again identity \eqref{eq:idphi}, the minimal order of the Euler function in the interval $[1,x]$ as well as Lemma \ref{lem:1} (i). Since ${\cal M}_4$ and ${\cal M}_5$ cover ${\cal M}_3$, we get from estimates \eqref{eq:M4} and \eqref{eq:M5} that \begin{equation} \label{eq:M3} \#{\cal M}_3=o\left(\frac{x}{(\log x)^2}\right)\qquad {\text{\rm as}}~ x\to\infty. \end{equation} which together with the estimates \eqref{eq:M1}, \eqref{eq:M2} and (i)--(vi) completes the proof of Theorem \ref{thm:1}. \qed \section{Proof of Theorem \ref{thm:2}} Let $x$ be a large positive real number. Since $\varepsilon(x)$ decreases and tends to infinity arbitrarily slowly, we may assume that $\varepsilon(x)\ge 2/\log_3 x$ for if not we may replace $\varepsilon(x)$ by $\max\{\varepsilon(x), 2/\log_3 x\} $. It was shown in \cite{LP} that there exists a positive constant $c_1$ such that for all $n\le x$ except $o(x)$ of them $\phi(n)$ is a multiple of all the primes $p\le c_1\log_2 x/\log_3 x$. Thus, $$ \phi^{(2)}(n)\le e^{-\gamma}(1+o(1))\frac{\phi(n)}{\log_3 x}\qquad {\text{\rm as}}~x\to\infty $$ with $o(x)$ exceptions $n$. Here, $\gamma$ is the Euler constant. Since $\phi(m)\le m/2$ whenever $m$ is even, we get that $$ \sum_{k=2}^{\kappa(n)}\phi^{(k)}(n)\le \phi^{(2)}(n)\sum_{k=2}^{\kappa(n)} \frac{1}{2^{k-2}}< 2\phi^{(2)}(n)<\frac{2n}{\log_3 x} $$ holds for all $n\le x$ with $o(x)$ exceptions as $x\to\infty$. We thus get that $$ n-F(n)\ge (n-\phi(n))-\frac{2n}{\log_3 x}. $$ Since $n-\phi(n)$ counts the number of positive integers $k\le n$ which are not coprime to $n$, it follows that $n-\phi(n)\ge n/p(n)$ where $p(n)$ is the smallest prime factor of $n$. Since the number of $n\le x$ for which $p(n)>(2\varepsilon(x))^{-1}$ is $O(x/\log((2\varepsilon(x))^{-1}))=o(x)$ as $x\to\infty$, we get that $p(n)\le (2\varepsilon(x))^{-1}$ with $o(x)$ exceptions as $x\to\infty$. Thus, except for $o(x)$ such $n\le x$, we have $$ n-F(n)\ge \frac{n}{p(n)}-\frac{2n}{\log_3 x}\ge 2n \left(\varepsilon(x)-\frac{1}{\log_3 x}\right)\ge \varepsilon(x) n. $$ Since $n\log n\ge x$ holds for all $n\le x$ with $O(x/\log x)=o(x)$ exceptions and $\varepsilon(x)$ is decreasing, we get that the inequality $$ n-F(n)\ge \varepsilon(n\log n)n $$ holds on a set of $n$ of asymptotic density $1$, which implies the desired conclusion since the function $\varepsilon(x)$ is arbitrary, subject to the conditions that it is decreasing for large $x$ and tends to zero when $x$ tends to infinity. \qed \section{Proof of Theorem \ref{thm:3}} We let $x$ be large and put $s=c_2\log_2 x\log_3 x/\log_4 x$ where $c_2>0$ is some absolute constant to be chosen later. Let $L=\lfloor {\sqrt{\log x}}\rfloor$ and consider the set of integers $$ {\cal W}=\{\prod_{p\le s} p^{\alpha_p}~:~ \alpha_p\in [L,~2L]~{\text{\rm for~all}}~p\le s\}. $$ Let $M=\prod_{p\le s} p$. If $n\in {\cal W}$ then $$ n\le M^{2L}\le \exp((2+o(1))sL)=\exp(O((\log x)^{1/2}\log_2 x\log_3 x))= x^{o(1)}$$ as $x\to\infty$, therefore $$ F(n)=\sum_{k\ge 1}\phi^{(k)}(n)\le \phi(n)\sum_{k\ge 1}\frac{1}{2^{k-1}}\le 2n=x^{o(1)}\qquad {\text{\rm as}}~x\to\infty. $$ In particular $F({\cal W})\subset {\cal U}(x)$ holds for large $x$. Note also that $$ \#{\cal W}\ge (L+1)^{\pi(s)}=\exp((1+o(1))s\log L/\log s), $$ therefore $$ \log(\#{\cal W})\gg \frac{s\log L}{\log s}\gg \frac{(\log_2 x)^2}{\log_4 x}. $$ From the above considerations, it follows that Theorem 3 will follow provided that we can show that if $c_2>0$ is suitably chosen and $x$ is large, then $F$ restricted to ${\cal W}$ is one-to-one. \medskip We take a closer look at $F(n)$ for $n\in {\cal W}$. Note that as long as $M\mid \phi^{(k)}(n)$, we have that $\phi^{(k+1)}(n)=(\phi(M)/M) \phi^{(k)}(n)$. Since clearly $M\mid \phi^{(k)}(n)$ for all $k\le L-1$, it follows that if we put $\delta=M/\phi(M)$, then $$ \phi^{(k)}(n)=\frac{\phi(n)}{\delta^{k-1}}=\frac{n}{\delta^k} $$ holds for all $k=1,~2,\ldots,~L$. Thus, for $n\in {\cal W}$ we have \begin{eqnarray} \label{eq:Fn} F(n) & = & \sum_{k\le L}\phi^{(k)}(n)+\sum_{k>L}\phi^{(k)}(n)= n\sum_{k=1}^{L}\delta^{-k}+ O\left(\phi^{(L+1)}(n)\sum_{j\ge 0}\frac{1}{2^j}\right) \nonumber \\ & = & n\left(\frac{1-\delta^{-(L+1)}}{1-\delta^{-1}}\right)+ O\left(\frac{n}{\delta^L}\right)=n\left(\frac{1}{1-\delta^{-1}}+ O\left(\frac{1}{\delta^{L}}\right)\right). \end{eqnarray} Note that $\delta=\prod_{p\le s}(1-1/p)^{-1}\asymp \log s$. Suppose now that $F(n_1)=F(n_2)$ for two distinct integers $n_1,~n_2$ in ${\cal W}$. From the above relation \eqref{eq:Fn} we get that $$ \frac{1}{1-\delta^{-1}}(n_1-n_2)=O\left(\frac{n_1+n_2}{\delta^{L}} \right) $$ and since $\delta\to \infty$ when $x\to\infty$, we get that $1/2