%\usepackage{amsmath,amssymb,amsbsy,amsfonts,amsthm,latexsym, % amsopn,amstext,amsxtra,euscript,amscd,amsthm} \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}}} \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 Ratio of the Sum of Divisors and \\ \vskip .12in Euler's Totient Function I } \vskip 1cm \large Kevin A. Broughan and Daniel Delbourgo \\ Department of Mathematics \\ University of Waikato\\ Private Bag 3105, Hamilton \\ New Zealand\\ \href{mailto:kab@waikato.ac.nz}{\tt kab@waikato.ac.nz} \\ \href{mailto:delbourg@waikato.ac.nz}{\tt delbourg@waikato.ac.nz} \\ \end{center} \vskip .2 in \def\cN{\hat{\mathbb{N}}} \def\cP{{\mathcal P}} \def\cR{{\mathcal R}} \def\o{\omega} \def\cZ{{\mathcal Z}} \def\t{\theta} \def \P{\mathbb{P}} \def \R{\mathbb{R}} \def \Q{\mathbb{Q}} \def \N{\mathbb{N}} \def\Z{\mathbb{Z}} \def\lam{\lambda} \def\N{\mathbb{N}} \def\s{\sigma} \def\g{\gamma} \def\a{\alpha} \def\b{\beta} \def\c{\gamma} \def\e{\epsilon} \def\O{\Omega} \def\o{\omega} \def\mP{\mathbb{P}} \def\supp{{\rm supp}} \begin{abstract} We prove that the only solutions to the equation $\s(n)=2\cdot\phi(n)$ with at most three distinct prime factors are 3, 35 and 1045. Moreover, there exist at most a finite number of solutions to $\s(n)=2\cdot\phi(n)$ with $\O(n)\le k$, and there are at most $2^{2^k+k}-k$ squarefree solutions to $\phi(n) \big| \s(n)$ if $\o(n)=k$. Lastly the number of solutions to $\phi(n)\big| \s(n)$ as $x\rightarrow\infty$ is $O\left(x\exp\left(-\frac{1}{2}\sqrt{\log x} \, \right)\right)$. \end{abstract} \section{Introduction} \label{sec:introduction} Paul Erd\H{o}s was interested in common properties of the sum of divisors function $\s(n)$ and Euler's totient function $\phi(n)$ throughout his career, and (co-)authored many papers exploring this connection. For example, Erd\H{o}s \cite{erdos} states that both $\s(n)$ and $\phi(n)$, apart from a set of density zero, are divisible by every prime less than $(\log\log n)^{1-\e}$ and by ``relatively few" primes larger than $(\log\log n)^{1+\e}$. Aside from being multinomials in the prime power factors of $n$, and obeying the inequality $\s(n)/n\le n/\phi(n)$, at first glance these functions have very little in common. Nevertheless properties of one function are frequently mirrored by the properties of the other one. As an illustration, their average orders satisfy $$ \sum_{n\le x} \s(n) ~~\asymp~~ \sum_{n\le x} \phi(n) $$ while the normal order of $\o\big(\s(n)\big)$ is exactly equal to the normal order of $\o\big(\phi(n)\big)$, namely $(\log\log n)^2/2$. Moreover, the same is true \cite{erdos1, ford1} for the size of the sets of values $$ \#\big\{\s(n):n\le x\big\}\asymp\#\big\{\phi(n):n\le x\big\}. $$ Recently there has been much work on `joint properties' shared by these two functions. For instance there exists an infinite number of squarefree integers $n$ such that $\s(n)\cdot \phi(n)$ is a square \cite{broughan}. In a similar vein Ford, Luca, and Pomerance \cite{ford2} proved that the two functions have an infinite number of values in common, that is $\s(a)=\phi(a')$ for an infinite set of integer pairs $(a,a')$ (see also Ford and Pollack \cite{ford3, ford}). \begin{remark} (i) In this paper we focus exclusively on properties of the quotient $\s(n)\big/\phi(n)$. Because there are inequalities $$ \sum_{p|n}\log\left(1+\frac{1}{p}\right) \leq \log\left(\frac{\sigma(n)}{\phi(n)}\right) = \sum_{p|n}\log\left(\frac{p^2-p^{1-\nu_p(n)}}{(p-1)^2}\right) \leq 2\sum_{p|n}\log\left(1+\frac{1}{p-1}\right) $$ and the summation over all primes $p$ of $\log\left(1+\frac{1}{p}\right)$ diverges, it is easy to show that the values of this quotient are dense inside $(0,\infty)$. Furthermore $\s(n)/\phi(n)\ll (\log\log n)^2$, so its maximum value grows very slowly with $n$. (ii) It is also worthwhile to point out that $\phi(n)$ divides $\s(n)$ surprisingly often. We shall pay special attention to those values of $n$ where this quotient is 2, as well as obtaining some results for when the quotient is an arbitrary integer. (iii) Indeed, based on computer calculations for values of $n$ up to $10^{10}$ (i.e., quite a small data set), we now strongly suspect that it is possible for the quotient $\s(n)/\phi(n)$ to take on any positive integer value greater than one. \end{remark} \bigskip \noindent {\it Notation:} (a) The function $\phi(n)$ is Euler's totient function, $\s(n)$ the sum of divisors of $n$, $\o(n)$ the number of distinct prime divisors of $n$, $\O(n)$ the total number of prime divisors including multiplicity, $\nu_p(n)$ is the maximum power of the prime $p$ which divides $n$, $\supp(n)$ denotes the set of primes which divide $n$, and $a\|n$ means $a$ divides $n$ with the $\gcd(a, n/a)=1$. \medskip (b) The Landau Vinogradov symbols $o, O, \ll, \asymp$ each have their standard meaning, with all implied constants being absolute. \medskip (c) If $a>b$ are natural numbers satisfying $\gcd(a,b)=1$, then $\cR=\cR_{a/b}$ denotes the set of solutions to $\s(n)/\phi(n)=a/b$ with the convention that $\cR_a=\cR_{a/1}$. \medskip Here is a short plan of the article. Using elementary methods, we first establish that the only solutions to the equation $\s(n)=2\cdot\phi(n)$ with at most 3 distinct prime factors are 3, 35 and 1045 (Theorem \ref{thm:omega3}). We next use the so-called product compactification of the natural numbers $\widehat{\N}$ to demonstrate that there exist at most a finite number of solutions to $\s(n)=2\cdot\phi(n)$ with $\O(n)\le k$ (Theorem \ref{thm:Omega}). Applying an inequality of Heath-Brown developed for the perfect number problem, in Theorem \ref{thm:squarefree} we show there are less than $2^{2^k+k}-k$ squarefree solutions to $\phi(n)\big| \s(n)$ if $\o(n)=k$. Lastly in Theorem \ref{thm:density}, using an upper bound for the number of integers up to $x$ which have smooth values for $\phi(n)$, we show that the number of solutions to $\phi(n)\big| \s(n)$, as $x\rightarrow\infty$, is of order $O\left(x\exp\left(-\frac{1}{2}\sqrt{\log x}\right)\right)$. %================================================================================================ \section{Preliminary results} \label{sec:preliminary} We begin by collecting together some basic inequalities satisfied by all elements of $\cR_{a/b}$. If $n=\prod_{i=1}^m p_i^{\a_i}$ denotes an arbitrary solution to $\s(n)=a\cdot\phi(n)/b$, then \begin{equation} \label{eqn:1} \prod_{i=1}^m \left(1-\frac{1}{p_i^{\a_i+1}}\right)= \frac{a}{b}\cdot \prod_{i=1}^m \left(1-\frac{1}{p_i}\right)^2. \end{equation} Since the left hand side is less than 1 for $n>1$, one obtains the useful bounds \begin{equation} \label{eqn:2} \sqrt{\frac{b}{a}}> \prod_{i=1}^m \left(1-\frac{1}{p_i}\right)> 1- \sum_{i=1}^m \frac{1}{p_i}. \end{equation} Expanding the quadratic on the right of Equation (\ref{eqn:1}) yields in a similar manner \begin{equation} \label{eqn:3} \frac{1}{2}-\frac{b}{2a}< \sum_{i=1}^m \frac{1}{p_i}. \end{equation} Let us restrict to the case $b=1$, so the equation becomes $\s(n)=a\cdot \phi(n)$ with $a\ge 2$. \begin{lemma} If $n\in\cR_{a}$ then \begin{equation} \label{eqn:4} \frac{\log(a)}{4}\le \sum_{p\mid n}\frac{1}{p}\le \frac{a}{2}. \end{equation} \end{lemma} \begin{proof} One readily deduces $$ \prod_{i=1}^m\left(1-\frac{1}{p_i^2}\right)\le \prod_{i=1}^m\left(1-\frac{1}{p_i^{\a_i+1}}\right) \buildrel \text{by Eq(\ref{eqn:1})}\over{=} a\cdot \prod_{i=1}^m\left(1-\frac{1}{p_i}\right)^2 $$ in which case $$ \prod_{i=1}^m\left(1+\frac{1}{p_i}\right)\le a\cdot \prod_{i=1}^m\left(1-\frac{1}{p_i}\right). $$ It follows directly that $$ 2\cdot\sum_{i=1}^m \frac{1}{p_i}\le 2\cdot\sum_{i=1}^m \frac{1}{p_i-1}\le \prod_{i=1}^m\left(1+\frac{2}{p_i-1}\right)\le a. $$ Therefore one obtains the right-hand inequality predicted in the statement of the lemma. Now taking logarithms of Equation (\ref{eqn:1}) and rearranging implies $$ \sum_{i=1}^m \log\left(1-\frac{1}{p_i^{\a_i+1}}\right)-2\cdot\sum_{i=1}^m \log\left(1-\frac{1}{p_i}\right)=\log(a)> 0 $$ and upon noticing that the first sum is negative, we may conclude $$ \sum_{i=1}^m \frac{4}{p_i}\ge \sum_{i=1}^m \frac{2}{p_i-1}\ge -2\cdot\sum_{i=1}^m \log\left(1-\frac{1}{p_i}\right)\ge \log(a). $$ \end{proof} \begin{remark} For prime powers the best bounds we have been able to derive are as follows. For any odd prime $p\ge 5$ and exponent $\a\ge 1$, there are inequalities \begin{equation} \label{eqn:5} 1+\frac{1}{p} \le \frac{\s(p^\a)}{\phi(p^\a)}< \frac{1}{\left(1-\frac{1}{p}\right)^2}\le \frac{25}{16}. \end{equation} The proof of these is entirely elementary. \end{remark} The following result shows the quotient $\s(n)/\phi(n)$ is strictly monotonically increasing with respect to the partial ordering associated with division. \begin{lemma} \label{lem:monotone} Define the arithmetic function $h:\N\rightarrow \Q_{>0}$ by the rule $h(n):= \s(n)/\phi(n)$. If $a,b\in\N$ are such that $a$ is a proper divisor of $b$, then $h(a)0$. Then adapting Equation (\ref{eqn:1}), one calculates that the ratio $h(b)\big/h(a)$ equals \begin{equation*} \prod_{i=1,~\a_i=0}^m\left(\frac{1-\frac{1}{p_i^{\b_i+1}}}{\left(1-\frac{1}{p_i}\right)^2}\right)\cdot \prod_{i=1,~\a_i>0}^m\frac{\left(1-\frac{1}{p_i^{\b_i+1}}\right)\left(1-\frac{1}{p_i}\right)^2} {\left(1-\frac{1}{p_i}\right)^2\left(1-\frac{1}{p_i^{\a_i+1}}\right)} = \frac{\s(c)}{\phi(c)}\cdot\!\prod_{i=1,~\a_i>0}^m\frac{1-\frac{1}{p_i^{\b_i+1}}}{1-\frac{1}{p_i^{\a_i+1}}} \end{equation*} where $c :=\prod_{i=1,~\a_i=0}^m p_i^{\b_i}$. The right-hand side is greater than one unless both $c=1$ and $\a_i=\b_i$ at every $\a_i>0$, which corresponds precisely to the situation $a=b$. \end{proof} We shall also need an inequality of Heath-Brown and Nielsen \cite{heath-brown}. \begin{lemma} \label{lem:6} Let $r,a,b\in\N$ and $x_1,\ldots,x_r$ be integers with $11}\frac{1}{p},\qquad\sum_{|f(p)|\le 1}\frac{f(p)}{p}\quad\text{and}\quad\sum_{|f(p)|\le 1}\frac{f(p)^2}{p} $$ are convergent, where in these summations $p$ ranges through all of the prime numbers. The limiting distribution is continuous if and only if the sum $ \sum_{f(p)\neq 0} 1/p $ is divergent. \end{lemma} In the same section, we will also require a result of Banks, Friedlander, Pomerance and Shparlinski \cite[Theorem 3.1]{banks}. \begin{lemma} \label{lem:phi-values} Let $\e>0$ be given. If $y$ is chosen so that $(\log\log x)^{1+\e}\le y\le x$ and $u:= \log x/\log y\rightarrow \infty$, then $$ \Phi(x,y)\le x\exp\Big(-\big(1+o(1)\big)u\log\log u\Big) $$ where $\Phi(x,y):=\#\big\{n\le x: p\mid \phi(n)\text{ implies }p\le y\big\}$. \end{lemma} \section{Solutions for low values of $\o(n)$} \label{sec:low} Our first result is a prototype structure theorem for elements belonging to the set $\cR_2$. \begin{lemma} \label{lem:form1} (i) All solutions to $\s(n)\big/\phi(n)=2$ are odd. (ii) If $n=p^\a$ is a prime power solution, then $p=3$ and $\a=1$. (iii) If $n$ is a solution and $3\big| n$, then $n=3$. \end{lemma} \begin{proof} Suppose $\s(n)=2\phi(n)$ with $n=2^e\cdot\prod_{\text{odd $p|n$}}p^{\a_p}$. If $n>1$ and $e\ge 1$, then $$ (2^{e+1}-1)\cdot\prod_{\text{odd $p|n$}}\frac{p^{\a_p+1}-1}{p-1}= 2^e\cdot\prod_{\text{odd $p|n$}} (p-1)\cdot p^{\a_p-1}. $$ As a consequence $$ \frac{3}{2}\le \big(2-\frac{1}{2^e}\big)=\prod_{\text{odd $p|n$}}\frac{p^{\a_p}-p^{\a_p-1}}{p^{\a_p}+p^{\a_p-1}+\cdots + 1} \le 1 $$ hence $n$ must be odd, and (i) follows. Let $p$ denote an odd prime, and assume that $n=p^\a\in\cR_2$ is a solution with $\a\ge 1$. From the equation $2=\s(p^\a)/\phi(p^\a)$ one quickly discovers that $p^{\a+1}-1=2p^{\a-1}(p-1)^2$. The latter implies $p^{\a-1}\mid p^{\a+1}-1$, thus $\a=1$. However $p^2-1=2(p-1)^2$ can only be solved for the prime $p=3$, so (ii) is also true. To dispose of (iii), we shall now assume $\o(n)>1$. If $3^\a\|n$ then by Equation (\ref{eqn:1}), $$ \frac{1-\frac{1}{3^{\a+1}}}{4/9}\cdot F=2 \quad\text{for some rational $F>1$.} $$ In particular $\frac{9}{4}(1-\frac{1}{3^{\a+1}})<2$, implying $3^{\a+1}<9$ which is false. Therefore $n=3$. \end{proof} \begin{lemma} \label{lem:form2} If $n\in\cR_2$ and $\o(n)=2$, then $n=35$. \end{lemma} \begin{proof} Let $n=p^\a\cdot q^\b$. First note that the term $1/(1-1/p)$ is decreasing as $p$ increases. Therefore if both $p,q\ge 7$ one finds $$ 1.85\ge \frac{1}{(1-\frac{1}{p})^2(1-\frac{1}{q})^2} \ge \frac{(1-\frac{1}{p^{\a+1}})(1-\frac{1}{q^{\b+1}})}{(1-\frac{1}{p})^2(1-\frac{1}{q})^2} =2 $$ hence by Lemma \ref{lem:form1}, we can assume $5=p2$, whence $$ 5^{\a+1}> 5^{\a+1}-1>\frac{200\cdot 16}{121\cdot 25}\cdot 5^{\a+1}> 1.05 \cdot 5^{\a+1}> 5^{\a+1} $$ and the last statement is clearly false. The only remaining possibility is $p=5$ and $q=7$. If $\a=1$ then $$ \frac{5+1}{5-1}\cdot \frac{1-1/7^{\b+1}}{6^2/7^2}=2 $$ which means $\b=1$ (likewise if $\b=1$, we must have $\a=1$). However in the equation $$ \left(\frac{1-1/5^{\a+1}}{4^2/5^2}\right)\cdot\left(\frac{1-1/7^{\b+1}}{6^2/7^2}\right)=2 $$ both factors on the left are strictly increasing in $\a$ and $\b$ respectively, thus there can be no solutions with $\a>1$ or $\b>1$. \end{proof} \begin{lemma} \label{lem:omega3} If $n\in\cR_2$ and $\o(n)=3$, then $n=1045$. \end{lemma} \begin{proof} Let $p,q,r$ be distinct prime numbers and $\a,\b,\c$ be natural numbers such that $n=p^\a\cdot q^\b\cdot r^\c$ satisfies $\s(n)=2\phi(n)$. We first show $(p,q,r)$ lies in the set of triples \begin{align*} \big\{&(5,11,13),(5,11,17),(5,11,19),(5,11,23),(5,11,29),\\&(5,11,31),(5,13,17),(5,13,19),(5,13,23)\big\}. \end{align*} Note that if $(p,q,r)=(5,11,19)$ then $\a=\b=\c=1$ is certainly a solution. One may assume $p \left(1-\frac{1}{5}\right)\left(1-\frac{1}{11}\right)\left(1-\frac{1}{r}\right) $$ which implies $r< 37$, thence $13\le r\le 31$. We checked each prime triple $(p,q,r)$ with $p\frac{1}{\sqrt{2}}> \left(1-\frac{1}{p}\right)\left(1-\frac{1}{q}\right)\left(1-\frac{1}{r}\right) \ge \left(1-\frac{1}{7}\right)\left(1-\frac{1}{11}\right)\left(1-\frac{1}{13}\right)> 0.719 $$ so we must have $p=5$. (Alternatively simply note that in each of the nine solution classes derived above one always has $p=5$.) We now show how to eliminate each of the eight cases other than $(p,q,r)=(5,11,19)$. To illustrate the method consider $(p,q,r)=(5,11,13)$, and suppose that $n=p^\a\cdot q^\b\cdot r^\c$ solves $\s(n)=2\phi(n)$. Using Equation (\ref{eqn:1}) again, one discovers \begin{eqnarray*} & & -\log\left(1-\frac{1}{5^{\a+1}}\right)-\log\left(1-\frac{1}{11^{\b+1}}\right)- \log\left(1-\frac{1}{13^{\c+1}}\right)\\&=& -\log\left(2\left(1-\frac{1}{5}\right)^2\left(1-\frac{1}{11}\right)^2\left(1-\frac{1}{13}\right)^2\right) =0.103846=:\lambda \text{ say.} \\ \end{eqnarray*} However for $0-\log(1-x) $$ in which case $$ \frac{3}{5^{\min(\a,\b,\c)+1}-1}> \frac{1}{5^{\a+1}-1}+\frac{1}{11^{\b+1}-1}+\frac{1}{13^{\c+1}-1}>\lambda. $$ The latter implies $31>5^{\min(\a,\b,\c)+1}$, and further that $1=\min(\a,\b,\c)$. We next consider in turn each of the cases $\a=1$, $\b=1$ and $\c=1$ leaving the other variables free, thereby eliminating possibilities through a short tree walk. If $\a=1$ then $$ \frac{1}{24}+\frac{1}{11^{\b+1}-1}+\frac{1}{13^{\c+1}-1}>\lambda; $$ consequently $$ \frac{2}{11^{\min(\b,\c)+1}-1}> \lambda-\frac{1}{24} $$ yielding $11^{\min(\b,\c)+1}< 34$, so $\a=1$ is clearly impossible. If however $\b=1$, we obtain $$ 25\le 5^{\min(\a,\c)+1}<\frac{2}{\lam-\frac{1}{120}}+1<22, $$ and if $\c=1$ then $$ 25\le 5^{\min(\a,\b)+1}< \frac{2}{\lam-\frac{1}{168}}+1<22 $$ which is also impossible. Hence there cannot exist solutions with $(p,q,r)=(5,11,13)$. The other remaining seven cases for $(p,q,r)$ are eliminated via similar arguments. \end{proof} The previous three lemmas may be neatly summarised, as follows. \begin{theorem} \label{thm:omega3} If $n\in\cR_2$ has at most $3$ distinct prime factors, then $n=3$, $35$ or $1045$. \end{theorem} More generally, if we make some restrictions on the exponents occurring in the prime decomposition of a solution $n\in\cR_{a/b}$ (e.g., $\nu_p(n)\leq 1$ for all primes $p$), one can obtain explicit finiteness results on the number of solutions with a bounded value of $\o(n)$. \begin{lemma} \label{lem:7} Let $k,a,b$ be fixed natural numbers, and consider the set $\cR_{a/b}$. Then there are at most a finite number of squarefree $n$ satisfying $\s(n)=a\cdot \phi(n)\big/b$ with $\o(n)=k$. \end{lemma} \begin{proof} We assume $k\ge 2$. In Equation (\ref{eqn:1}) one chooses $m=k$, and for all $i$ take $\a_i=1$ since $n$ is squarefree. Now for $n=p_1\cdots p_k$ one can rewrite this equation as $$ \frac{b}{a}=\prod_{i=1}^k\left(1-\frac{2}{p_i+1}\right) < \prod_{i=1}^{k-1}\left(1-\frac{2}{p_i+1}\right). $$ If $n$ is odd then we apply Lemma \ref{lem:6}, and immediately conclude $$ b\cdot \prod_{i=1}^k \left(\frac{p_i+1}{2}\right) < (b+1)^{2^k} $$ which implies $n+k<2^k\cdot (b+1)^{2^k}/b$. If $n=2m$ is even then $\s(m)/\phi(m)=a/(3b)$ and $m$ is odd, hence $$ m+k-1\le\prod_{i=2}^k (p_i+1)< 2^{k-1}(3b+1)^{2^{k-1}}/(3b) $$ in which case $n+2k-2< 2^k(3b+1)^{2^{k-1}}/(3b)$. \end{proof} Setting $b=1$, and combining the bounds directly above for $n$ even/odd, we obtain \begin{theorem} \label{thm:squarefree} If a squarefree integer $n$ satisfies the divisibility $\phi(n)\big| \s(n)$ with $\o(n)=k$, then $$n< 2^{2^k+k}-k.$$ In particular, there exist at most a finite number of such $n$. \end{theorem} %====================================================================================================== \section{Applications of the product compactification of $\mathbf{\N}$} \label{sec:product-compactification} \def\hN{\widehat{\mathbb{N}}} \def\v{\nu} For each prime $p$, let $\mathbb{N}_p$ denote the one point compactification of $\mathbb{Z}_{\geq 0}$; in particular, each finite point $n\in\mathbb{Z}_{\geq 0}$ is itself an open set, and a basis for the neighborhoods of the point at infinity, $p^{\infty}$ say, is given by the open sets $U_p^{(\epsilon)}=\big\{n\in\mathbb{Z}_{\geq 0}:n\ge 1/\epsilon\big\}\cup\{p^{\infty}\}$ with $\epsilon>0$. If $\mP$ indicates the set of prime numbers, let us write $$ \widehat{\mathbb{N}} := \prod_{p\in\mP} \mathbb{N}_p $$ for the product of these indexed spaces, endowed with the standard product topology. Then $\hN$ is a compact metrizable space so it is sequentially compact, hence every sequence in $\hN$ has a convergent subsequence. Note the useful equivalence that $N_i\longrightarrow N_o$ in $\hN$ if and only if for all primes $p$, $\v_p(N_i)\rightarrow \v_p(N_o)$ in $\mathbb{N}_p$. If $N$ is a positive integer we write $\widehat{N}$ for the corresponding element of $\hN$, namely $(n_p:p\in\P)$ where $n_p=\v_p(N)$. For example, $\widehat{84}=(2,1,0,1,\ldots)$ and $\widehat{1}=(0,0,0,\ldots)$. Let $\mathbb{N}$ have the discrete topology; we shall identify $\N$ with its image in $\cN$ under the embedding $n\rightarrow \widehat{n}$, yielding a dense subset of $\hN$. If $h:\N\rightarrow\R$ is a multiplicative function, and if for $p\in\mP$ each sequence $\big(h(p^n)\big)_{n\in\Z_{\geq 0}}$ is Cauchy in neighborhoods $U_p^{(\epsilon)}$, one may extend $h$ to a function on $\widehat{\N}$ through the formula $$ h\big(\widehat{N}\big):= \lim_{\widehat{n}\rightarrow(\dots,\nu_p(N),\dots)}\left(\prod_{p\in\mP}h\big(p^{n_p}\big)\right) $$ providing the limit exists and the product converges, of course. \begin{remark} We shall call $\hN$ equipped with its topology the {\it product compactification of $\mathbb{N}$}. A nice account detailing some of the properties of this set-up, with the compactification called the `supernatural topology', is given by Pollack in \cite{SN}; it is used, for example, to explore the perfect number problem. The topology was first introduced by Steinitz \cite{steinitz} and used in a number of applications, including \cite{artjuhov} and \cite{borho}. \end{remark} \begin{lemma} \label{lem:continuity1} Let $\cP\subset \mP$ be a finite set of primes. Assume we are given a sequence of natural numbers $(N_i)$ such that $N_i\rightarrow N_o$ in $\cN$, and for all $i\in\N$ one has $\supp (N_i)\subset \cP$. Finally let $h:\mathbb{N}\rightarrow \mathbb{R}$ be a positive multiplicative function, such that for each $p\in\cP$ $$ h(p^\infty):= \lim_{n\rightarrow\infty} h(p^n) $$ exists in $(0,\infty]$, i.e. is strictly positive or infinity. Defining the disjoint sets $$ \mathcal{A}=\{p\in\cP:\v_p(N_o)<\infty\} \quad\text{and}\quad \mathcal{B}=\{p\in\cP: \v_p(N_o)=\infty\} $$ then inside $\mathbb{R}_{>0}\cup\{\infty\}$, $$ \lim_{i\rightarrow\infty} h(N_i)= h(A)\cdot h(B^\infty) $$ where $A:=\prod_{p\in \mathcal{A}} p^{\v_p(N_o)}$ and $B:=\prod_{p\in \mathcal{B}}p$. \end{lemma} \begin{proof} Firstly note that $\supp( N_o)\subset \cP$, so the sets of primes $\mathcal{A}$ and $\mathcal{B}$ are well-defined and finite. We can write $\cP=\mathcal{A}\cup \mathcal{B}$ as a disjoint union, and then decompose $$ N_i=\prod_{p\in\cP} p^{\v_p(N_i)}=\prod_{p\in \mathcal{A}} p^{\v_p(N_i)}\cdot\prod_{p\in \mathcal{B}} p^{\v_p(N_i)}. $$ Because $N_i\rightarrow N_o$ in $\cN$, for each prime $p$ we must have $\v_p(N_i)\rightarrow \v_p(N_o)$ in $\Z_{\geq 0}\cup \{\infty\}$. By assumption $h$ is multiplicative on $\N$, in which case $$ h(N_i)= \prod_{p\in\cP} h\big(p^{\v_p(N_i)}\big)= \prod_{p\in \mathcal{A}}h\big(p^{\v_p(N_i)}\big) \cdot \prod_{p\in \mathcal{B}}h\big(p^{\v_p(N_i)}\big). $$ Since $\mathcal{A}$ is a finite set, then at each $p\in \mathcal{A}$ and for all $i\ge i_1$ say, $\v_p(N_i)=\v_p(N_o)$. It follows that the first term on the right in the above expression is equal to $h(A)>0$. Now for every $p\in \mathcal{B}$, $\v_p(N_i)\rightarrow \infty$ hence $h\big(p^{\v_p(N_i)}\big)\rightarrow h(p^\infty)$. Therefore, as the limit of a product of a finite number of terms is the product of the limits, our hypotheses on $h$ ensure the indeterminate form $0\cdot\infty$ does not occur. As an immediate consequence the second term above must tend to $h(B^\infty)$, and the lemma is proved. \end{proof} \begin{lemma} \label{lem:equivalence} Let $h:\N\rightarrow\R$ be a multiplicative function, and assume $(N_i)\subset\N$ is a sequence of natural numbers such that $\widehat{N_i}\rightarrow \widehat{N_o}$ inside $\cN$, for some positive integer $N_o$. If for all sequences $(M_i)\subset\N$ such that $\widehat{M_i}\rightarrow \widehat{1}$ in $\cN$ we also have $h(M_i)\rightarrow 1$ inside $\R$, then $\lim_{i\rightarrow\infty}h(N_i)= h(N_o)$. \end{lemma} \begin{proof} Given that $\widehat{N_i}\rightarrow \widehat{N_o}$, one defines $\cP:=\supp(N_o)$ which is a finite set as $N_o\in\N$. Let us write $N_i=A_i\cdot M_i$ where $\supp(A_i)\subset \cP$, and $\supp(M_i)\cap \cP=\emptyset$ so that $\gcd(A_i,M_i)=1$. Since $\widehat{M_i}\rightarrow \widehat{1}$ thus $h(\widehat{M_i})\rightarrow 1$ and $\widehat{A_i}\rightarrow \widehat{N_o}$, and it therefore follows $$ h(N_i)=h(A_i)\cdot h(M_i)\longrightarrow h(\widehat{N_o})\cdot 1=h(N_o). $$ \end{proof} \begin{theorem} \label{thm:support} Let $\cP$ be a finite set of primes. Then there exist at most a finite number of positive integers $N\in\N$ with $\supp(N)\subset \cP$ such that $\s(N)\big/\phi(N)=2$. \end{theorem} \begin{proof} Let $\cN$ be endowed with the product topology, and suppose there exists an infinite sequence of distinct integers $(N_i)_{i\ge 1}$ in $\cR_2$ for which $\supp(N_i)\subset \cP$ for each $i\in\N$. Then there is a subsequence, also denoted $(N_i)$, and a limit $N_o\in\cN$ such that $N_i\rightarrow N_o$. Let $h(n):=\s(n)/\phi(n)$ for $n\in \mathbb{N}$ and $h(p^\infty):=p^2/(p-1)^2$, so that $h(p^n)\rightarrow h(p^\infty)$ for all $p\in\P$. If $N_o$ was divisible by a prime not in $\cP$, then we would have an $N_i$ divisible by that prime, which is false. Hence $N_o$ has finite support. By Lemma \ref{lem:continuity1} we can write $$ N_o=A\cdot B^\infty $$ where $A$ and $B$ each supported by $\cP$ are odd, have $\gcd(A,B)=1$, are such that $B$ is squarefree, and $h(N_i)\rightarrow h(A)\cdot h(B^\infty)$. However this means $2=h(A)\cdot h(B^\infty)$. Since $A\|N_o$ we must have $A\|N_i$ for all sufficiently large $i$, and because the $N_i$ are distinct, we must have $A=N_i$ for at most one $i$. Thus for $i\ge i_1$ say we have $A$ a proper unitary divisor of $N_i$. For such an $i$, put $N_i=A\cdot B_i$ so $B_i>1$. Let us write $B_i=\prod_{p|B_i}p^{e_{p,i}}$ where $e_{p,i}=\v_p(B_i)$ tends to $\v_p(B^{\infty})= +\infty$ with $i$. Indeed, by passing to a suitable subsequence, without loss of generality one can assume each exponent $e_{p,i}$ is monotonically increasing. In particular, $$ 2 = h(N_i) = h(A)\cdot h(B_i) = \frac{\s(A)}{\phi(A)}\cdot \prod_{p\mid B_i}\frac{p^2}{(p-1)^2}\cdot\!\left(1-\frac{1}{p^{e_{p,i}+1}}\right). $$ The right-hand side is monotonic increasing with $i$, whilst the left-hand side is constant; this yields an immediate contradiction, therefore no such infinite sequence $(N_i)$ can have existed in the first place. \end{proof} \begin{theorem} \label{thm:Omega} Let $k\ge 1$ be a given natural number. There exist at most a finite number of positive integers $n$ with $\Omega(n)\le k$ satisfying $\s(n)\big/\phi(n)=2$. \end{theorem} \begin{proof} Let $h:\N\rightarrow \R$ be defined by $h(n)=\s(n)/\phi(n)$. Suppose there exist an infinite number of distinct positive integers $N_i$ satisfying both the equality $2=h(N_i)$ and the constraint $\Omega(N_i)\le k$ for all $i$. By passing to a suitable subsequence, also denoted $(N_i)$, one can assume $N_i\rightarrow N_o$ in $\cN$. \begin{remark} (i) We must have $N_o$ supported by at most $k$ primes, otherwise this would apply to at least one $N_i$ yielding $\Omega(N_i)\ge \omega(N_i)>k$ which is false. (ii) Furthermore, all the components of $N_o$ in $\cN$ must be bounded above by $k$ since at each prime $p$, one has $k\ge \v_p(N_i)\rightarrow \v_p(N_o)$. (iii) It follows that this limit point $N_o$ must correspond to a natural number. \end{remark} \medskip For $i$ sufficiently large, we can therefore write $N_i=N_o\cdot B_i$ where $B_i$ is an integer supported by at most $k$ primes, and $\gcd(N_o,B_i)=1$. As there are at most a finite number of primes dividing $N_o$, we can assume for all $p\in\supp(N_o)$ that $\v_p(N_o)=\v_p(N_i)$ for all indices $i\ge i_o$ say. Then the support of $B_i$ consists of all primes dividing $N_i$ which do not divide $N_o$. We claim that there is a sequence of natural numbers $(x_i)_{i\ge 1}$ tending to infinity, such that $\supp(B_i)\subset [x_i, \infty)$. If not, then there exists a prime $q$ for which $\v_q(B_i)>0$ infinitely often, which would force $\v_q(N_o)$ to be positive even though $q\not\in\supp(N_o)$! Therefore our claim concerning $\supp(B_i)$ must be true, in which case $$ 1\le h(B_i)= \prod_{p\mid B_i}\left(\frac{1-\frac{1}{p^{\v_p(B_i)+1}}}{\left(1-\frac{1}{p}\right)^2}\right) < \prod_{p\mid B_i} \left(1-\frac{1}{p}\right)^{-2} \le \left(1-\frac{1}{x_i}\right)^{-2k} \longrightarrow 1. $$ By Lemma \ref{lem:equivalence} it follows $2=h(N_i)=h(N_o)\cdot h(B_i)\rightarrow h(N_o)$, and therefore $h(N_o)=2$. But the latter is impossible as the $N_i$ being distinct means $N_o$ is a proper divisor of $N_i$ for at least one $i$, thereby implying that $h(N_o)<2$ which gives us a contradiction. \end{proof} \section{Density of the union of the $\cR_a$'s} \label{sec:density} Paul Erd\H{o}s was very interested in the so-called {\bf primitive} sequences of natural numbers, i.e., sequences $A=(a_n)_{n\in\N}$ with $a_10$ let us define $A(x)= \sum_{a_n\le x} 1$. In 1935, Erd\H{o}s showed the lower natural density of $A$ was necessarily zero, namely that $$ \liminf_{x\rightarrow\infty} \frac{A(x)}{x}=0. $$ It follows from Lemma \ref{lem:monotone} that each sequence of solutions to $\s(n)=a\cdot \phi(n)$ yields a primitive sequence, and therefore the set $\cR_a$ itself has trivial lower density. \begin{remark} We have a further item of evidence that the density of $\cR_a$ is zero, via a theorem of Erd\H{o}s and Davenport from 1937. If for some sequence $(a_n)$ one has $$ \limsup_{x\rightarrow\infty}\frac{1}{\log x}\cdot\sum_{a_n\le x} \frac{1}{a_n}>0 $$ then there exists a subsequence $(a_{n_i})\subset(a_n)$ such that $a_{n_i}\big| a_{n_{i+1}}$ for all indices $i\in\N$. Hence if the $a_n$'s comprise all the elements in $\cR_a$ ordered by `$<$' say, then one deduces $$ \limsup_{x\rightarrow\infty}\frac{1}{\log x}\cdot\sum_{a_n\le x} \frac{1}{a_n}=0. $$ Thus $\cR_a$ has lower asymptotic density zero, and also upper logarithmic density zero. Unfortunately, in general, this alone is not sufficient to imply density zero for the set (see the much celebrated example of Besicovitch \cite{besi}). \end{remark} However the issue of whether solution sets have density zero can be easily resolved upon noting that by Lemma \ref{lem:erdos-winter}, $f(n):= \log \left(\s(n)/\phi(n)\right)$ has a continuous increasing distribution function, hence the same is true for $\s(n)/\phi(n)$. Therefore, for any given positive integers $a$ and $b$, the set $\cR_{a/b}$ has density zero. In fact much more than this is true in the case $b=1$, i.e., when $\phi(n)\mid \s(n)$. The authors are grateful to the referee for the following proof, based on ideas from \cite[Theorem 3.1]{banks} (which we labelled Lemma \ref{lem:phi-values}). \begin{theorem} \label{thm:density} If $N(x):= \#\{n\le x: \phi(n)\mid \s(n)\}$ then as $x\rightarrow\infty$, one has the bound $$ N(x)\ll x \exp\left(-\frac{1}{2}\sqrt{\log x}\right). $$ \end{theorem} \begin{proof} Let $n\le x$ satisfy $\phi(n)\mid \s(n)$, and write $p$ for the largest prime factor of $\phi(n)$. Assume that $p>y$ where $y>0$ is a large parameter to be chosen later, and write $A$ for the subset of such $n$ with $p\le y$. Now one has $p \mid \phi(n) \mid \sigma(n)$, therefore there exists a prime power $q^e \| n$ with $p \| \s(q^e)$. If $e=1$ then $p \mid q+1$; otherwise as $2q^e > \sigma(q^e) \ge p$ and $n\neq q^e$, the integer $n$ would have a proper prime power divisor $q^e$ say, with $q^e > p/2 > y/2$. Now using partial summation, the set of $n\le x$ with such a prime power divisor, $B$ say, is of size $O(x/\sqrt{y})$; exploiting the fact $p \mid \phi(n)$ and a similar argument, we see that either there is a prime $r \mid n$ with $p \mid r-1$, or instead $n$ belongs to an exceptional set, $C$ say, of size $O(x/y)$. Suppose $n\not\in A\cup B\cup C$. Then $n$ has prime factors $r\equiv 1 (\bmod p)$ and $q \equiv -1 (\bmod p)$, and the number of such $n \le x$ is bounded above by $x/(rq)$. Summing over both $r$ and $q$ in the given progressions shows that for a given $p$, the number of such $n$ is $O(x (\log x)^2/p^2)$; secondly, summing over primes $p > y$ implies the number of $n$ up to $x$ is $O(x (\log x)^2/y)$. Putting everything together, this argument establishes that the total number of $n \le x$ for which $\phi(n)\mid \s(n)$ satisfies the upper bound $$ N(x) \ll \#\big\{n\le x: \text{$\phi(n)$ has only prime factors $\le y$}\big\} + \frac{x}{\sqrt{y}} +\frac{ x}{y} + \frac{x (\log x)^2}{y}. $$ For $x$ and $u$ sufficiently large, by Lemma \ref{lem:phi-values} one has $\Phi(x,y)\le xe^{-u/2}$, and minimizing $$ xe^{-\frac{u}{2}}+ \frac{x}{\sqrt{y}} $$ we obtain at the minimum $$\frac{\log y}{2}+ \log\log x-2\log\log y= \frac{\log x}{2\log y}. $$ Neglecting the ``loglog" terms yields $\log y= \sqrt{\log x}$, $u=\sqrt{\log x}$ and $y=\exp(\sqrt{\log x})$. Checking these estimates, one then deduces $$ \Phi(x,y)\le x\exp(-(1+o(1))u\log\log u)\le x\exp(-\frac{u}{2})\le \frac{x}{\sqrt{y}} $$ so for $x$ sufficiently large, $N(x)\ll x \exp\big(\!-\frac{1}{2}\sqrt{\log x}\big)$. The result now follows. \end{proof} For a given $m\in\N$, the number of solutions $n$ to `$m=\s(n)=2\phi(n)$' seems very small. One might contrast this with the equation $m=\phi(n)$, where the number of solutions $c_m$ has been shown to satisfy $c_m>m^\delta$ for infinitely many $m$, and a range of values of $\delta$ \cite{woolridge, pomerance1}. \section{Unsolved problems} \label{sec:problems} \begin{enumerate} \item If $\s(n)=2\phi(n)$ then it seems likely that $d(n)\mid \s(n)$, and we have shown numerically that this is true for all $n$ up to $2.1\times 10^9$. The divisibility $d(n)\mid \s(n)$ follows easily when $n$ is squarefree, and most solutions to $\s(n)=2\phi(n)$ appear to have this shape. \item It seems that the number of solutions to $\s(n)=2\phi(n)$ is infinite. An easier problem would be to find an infinite set of integers $a$ such that $\s(n)=a\cdot\phi(n)$ for at least one $n$. \item No square satisfies $\s(n)=a\cdot\phi(n)$ for any $a\ge 2$. Along these lines it appears that perfect powers never satisfy this equation, nor even squarefull numbers. \item The number of solutions to $\s(n)=2\phi(n)$ with $n\le x$ is expected to be $x^{o(1)}$. \end{enumerate} \begin{thebibliography}{99} \bibitem{erdos} L. Alaoglu and P. Erd\H{o}s, A conjecture in elementary number theory, {\it Bull. Amer. Math. Soc.} {\bf 50} (1944), 881--882. \bibitem{artjuhov} M. M. Artjuhov, On problems in the theory of amicable numbers, {\it Acta. Arith.} {\bf 27} (1975), 281--291. \bibitem{banks} W. D. Banks, J. B. Friedlander, C. Pomerance, and I. E. Shparlinski, Multiplicative structure of values of the Euler function, in {\it High Primes and Misdemeanours: Lectures in Honour of the 60th Birthday of Hugh Cowie Williams}, Fields Inst. Commun., {\bf 41}, Amer. Math. Soc., 2004, pp.\ 29--47. \bibitem{besi} A. S. Besicovitch, On the density of a certain sequence of integers, {\it Math. Ann.} {\bf 10} (1935), 336--341. \bibitem{borho} W. Borho, Befreundete Zahlen mit gegebener Primteileranzahl, {\it Math. Ann.} {\bf 209} (1974), 183--193. \bibitem{broughan} K. A. Broughan, J. M. De Koninck, I. Katai, and F. Luca, On integers for which the sum of divisors is the square of the squarefree core, {\it J. Integer Sequences} {\bf 15} (2012), \href{https://cs.uwaterloo.ca/journals/JIS/VOL15/Broughan/broughan20.html}{Article 12.7.5}. \bibitem{delange} H. Delange, Sur les fonctions arithm\'etiques multiplicatives, {\it Ann. Sci. \'Ecole Norm. Sup.} {\bf 78} (1961), 273--304. \bibitem{delange2} H. Delange, Application de la m\'ethode du crible \`a l'\'etude des valeurs moyennes de certaines fonctions arithm\'etiques, {\it S\'eminaire Delange-Pisot}, {\bf 3} (1961/1962), Paris, 1963. \bibitem{elliot} P. D. T. A. Elliot, {\it Probabilistic Number Theory I}, Springer-Verlag, 1979. \bibitem{erdos1} P. Erd\H{o}s, On the normal number of prime factors of $p-1$ and some related problems concerning Euler's $\phi$-function, {\it Quart. J. Math.} {\bf 6} (1935), 205--213. \bibitem{erdos2} P. Erd\H{o}s, Some remarks on Euler's $\varphi$ function, {\it Acta Arith.} {\bf 4} (1958), 10--19. \bibitem{ford1} K. Ford, The distribution of totients, {\it Ramanujan J.} {\bf 2} (1998), 67--151. \bibitem{ford2} K. Ford, F. Luca, and C. Pomerance, Common values of the arithmetic functions $\phi$ and $\s$, {\it Bull. Lond. Math. Soc.} {\bf 42} (2010), 478--488. \bibitem{ford3} K. Ford and P. Pollack, On common values of $\phi(n)$ and $\s(n)$, I, {\it Acta Math. Hungarica} {\bf 133} (2011), 251--271. \bibitem{ford} K. Ford and P. Pollack, On common values of $\phi(n)$ and $\s(n)$, II, {\it Algebra Number Theory} {\bf 6} (2012), 1669--1696. \bibitem{guy} R. K. Guy, {\it Unsolved Problems in Number Theory}, 3rd edition, Springer, 2004. \bibitem{heath-brown} D. R. Heath-Brown, Odd perfect numbers, {\it Math. Proc. Camb. Phil. Soc.} {\bf 115} (1994), 191--196. \bibitem{nielsen} P. P. Nielsen, An upper bound for odd perfect numbers, {\it Integers: Electronic J. Comb. Number Theory} {\bf 3} (2003), \href{http://www.integers-ejcnt.org/vol3.html}{A14}. \bibitem{pomerance1} C. Pomerance, Popular values of Euler's function, {\it Mathematika} {\bf 27} (1980), 84--89. \bibitem{pomerance} C. Pomerance and A. S\'ark\"ozy, Combinatorial number theory, in R. L. Graham, M. Gr\"otschel, and L. Lov\`asz, eds., {\it Handbook of Combinatorics}, Vol.\ 1, Elsevier Science, 1995, pp.\ 967--1018. \bibitem{SN} P. Pollack, Finiteness theorems for perfect numbers and their kin, {\it Amer. Math. Monthly} {\bf 119} (2012), 670--681. \bibitem{steinitz} E. Steinitz, Algebraische Theorie der K\"orper, {\it J. Reine Angew. Math.} {\bf 137} (1910), 167--309. \bibitem{tenenbaum} G. Tenenbaum, {\it Introduction to Analytic and Probabilistic Number Theory}, Cambridge, 1995. \bibitem{woolridge} K. Woolridge, Values taken many times by Euler's phi-function, {\it Proc. Amer. Math. Soc.} {\bf 76} (1979), 229--234. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 11A25; Secondary 11A41, 54H99, 11N60, 11N25, 11N64. \noindent \emph{Keywords: } sum of divisors, Euler's totient function, product compactification. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A062699}, \seqnum{A068390}, and \seqnum{A104901}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received June 13 2013; revised versions received August 4 2013; September 19 2013; September 26 2013. Published in {\it Journal of Integer Sequences}, October 13 2013. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document} \end{document}