On the Ratio of the Sum of Divisors and Euler’s Totient Function I

Kevin A. Broughan and Daniel Delbourgo Department of Mathematics University of Waikato Private Bag 3105, Hamilton New Zealand

                       kab@waikato.ac.nz
                    delbourg@waikato.ac.nz

Abstract We prove that the only solutions to the equation σ(n) = 2 · ϕ(n) with at most three distinct prime factors are 3, 35 and 1045. Moreover, there exist at most a finite number of solutions to σ(n) = 2 · ϕ(n) with Ω(n) ≤ k, and there are at most 2^{2^{k}+k} − k squarefree solutions to ϕ(n)|σ(n) if ω(n) = k. Lastly the number of solutions to ϕ(n)|σ(n) as x → ∞ is O (x exp (−\frac{1}{2} \sqrt{log x} )).

1 Introduction

Paul Erdős was interested in common properties of the sum of divisors function σ(n) and Euler’s totient function ϕ(n) throughout his career, and (co-)authored many papers exploring this connection. For example, Erdős [1] states that both σ(n) and ϕ(n), apart from a set of density zero, are divisible by every prime less than (log log n)^{1−ϵ} and by “relatively few” primes larger than (log log n)^{1+ϵ}.

Aside from being multinomials in the prime power factors of n, and obeying the inequality σ(n)/n ≤ n/ϕ(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

∑_{n≤x} σ(n) ≍ ∑_{n≤x} ϕ(n)

while the normal order of ω(σ(n)) is exactly equal to the normal order of ω(ϕ(n)), namely (log log n)^{2}/2. Moreover, the same is true [10, 12] for the size of the sets of values

#{σ(n) : n ≤ x} ≍ #{ϕ(n) : n ≤ x}.

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 σ(n) · ϕ(n) is a square [6]. In a similar vein Ford, Luca, and Pomerance [13] proved that the two functions have an infinite number of values in common, that is σ(a) = ϕ(a′) for an infinite set of integer pairs (a, a′) (see also Ford and Pollack [14, 15]). Remark 1. (i) In this paper we focus exclusively on properties of the quotient σ(n)/ϕ(n). Because there are inequalities

∑_{p|n} log (1 + \frac{1}{p}) ≤ log (\frac{σ(n)}{ϕ(n)}) = ∑_{p|n} log (\frac{p^{2} − p^{1−ν_{p}(n)}}{(p − 1)^{2}} ) ≤ 2 ∑_{p|n} log (1 + \frac{1}{p − 1})

and the summation over all primes p of log (1 + \frac{1}{p}) diverges, it is easy to show that the values of this quotient are dense inside (0, ∞). Furthermore σ(n)/ϕ(n) ≪ (log log n)^{2}, so its maximum value grows very slowly with n.

(ii) It is also worthwhile to point out that ϕ(n) divides σ(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 σ(n)/ϕ(n) to take on any positive integer value greater than one.

Notation: (a) The function ϕ(n) is Euler’s totient function, σ(n) the sum of divisors of n, ω(n) the number of distinct prime divisors of n, Ω(n) the total number of prime divisors including multiplicity, ν_{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.

(b) The Landau Vinogradov symbols o, O, ≪, ≍ each have their standard meaning, with all implied constants being absolute.

(c) If a > b are natural numbers satisfying gcd(a, b) = 1, then R = R_{a/b} denotes the set of solutions to σ(n)/ϕ(n) = a/b with the convention that R_{a} = R_{a/1}.

Here is a short plan of the article. Using elementary methods, we first establish that the only solutions to the equation σ(n) = 2 · ϕ(n) with at most 3 distinct prime factors are 3, 35 and 1045 (Theorem 11). We next use the so-called product compactification of the natural numbers ℕ̂ to demonstrate that there exist at most a finite number of solutions to σ(n) = 2 · ϕ(n) with Ω(n) ≤ k (Theorem 18).

Applying an inequality of Heath-Brown developed for the perfect number problem, in Theorem 13 we show there are less than 2^{2^{k}+k} − k squarefree solutions to ϕ(n)|σ(n) if ω(n) = k. Lastly in Theorem 21, using an upper bound for the number of integers up to x which have smooth values for ϕ(n), we show that the number of solutions to ϕ(n)|σ(n), as x → ∞, is of order O (x exp (−\frac{1}{2} \sqrt{log x})).

2 Preliminary results

We begin by collecting together some basic inequalities satisfied by all elements of R_{a/b}. If n = ∏_{i=1}^{m} p_{i}^{α_{i}} denotes an arbitrary solution to σ(n) = a · ϕ(n)/b, then

∏_{i=1}^{m} (1 − \frac{1}{p_{i}^{α_{i}+1}} ) = \frac{a}{b} · ∏_{i=1}^{m} (1 − \frac{1}{p_{i}} )^{2} .  (1)

Since the left hand side is less than 1 for n > 1, one obtains the useful bounds

\sqrt{\frac{b}{a}} > ∏_{i=1}^{m} (1 − \frac{1}{p_{i}} ) > 1 − ∑_{i=1}^{m} \frac{1}{p_{i}} .  (2)

Expanding the quadratic on the right of Equation (1) yields in a similar manner

\frac{1}{2} − \frac{b}{2a} < ∑_{i=1}^{m} \frac{1}{p_{i}} .  (3)

Let us restrict to the case b = 1, so the equation becomes σ(n) = a · ϕ(n) with a ≥ 2.

Lemma 2. If n ∈ R_{a} then

\frac{log(a)}{4} ≤ ∑_{p|n} \frac{1}{p} ≤ \frac{a}{2}.  (4)

Proof. One readily deduces

∏_{i=1}^{m} (1 − \frac{1}{p_{i}^{2}} ) ≤ ∏_{i=1}^{m} (1 − \frac{1}{p_{i}^{α_{i}+1}} ) =^{by Eq(1)} a · ∏_{i=1}^{m} (1 − \frac{1}{p_{i}} )^{2}

in which case

∏_{i=1}^{m} (1 + \frac{1}{p_{i}} ) ≤ a · ∏_{i=1}^{m} (1 − \frac{1}{p_{i}} ) .

It follows directly that

2 · ∑_{i=1}^{m} \frac{1}{p_{i}} ≤ 2 · ∑_{i=1}^{m} \frac{1}{p_{i} − 1} ≤ ∏_{i=1}^{m} (1 + \frac{2}{p_{i} − 1}) ≤ a.

Therefore one obtains the right-hand inequality predicted in the statement of the lemma. Now taking logarithms of Equation (1) and rearranging implies

∑_{i=1}^{m} log (1 − \frac{1}{p_{i}^{α_{i}+1}} ) − 2 · ∑_{i=1}^{m} log (1 − \frac{1}{p_{i}} ) = log(a) > 0

and upon noticing that the first sum is negative, we may conclude

∑_{i=1}^{m} \frac{4}{p_{i}} ≥ ∑_{i=1}^{m} \frac{2}{p_{i} − 1} ≥ −2 · ∑_{i=1}^{m} log (1 − \frac{1}{p_{i}} ) ≥ log(a).

Remark 3. For prime powers the best bounds we have been able to derive are as follows. For any odd prime p ≥ 5 and exponent α ≥ 1, there are inequalities

1 + \frac{1}{p} ≤ \frac{σ(p^{α})}{ϕ(p^{α})} < \frac{1}{(1 − \frac{1}{p})^{2}} ≤ \frac{25}{16}.  (5)

The proof of these is entirely elementary.

The following result shows the quotient σ(n)/ϕ(n) is strictly monotonically increasing with respect to the partial ordering associated with division.

Lemma 4. Define the arithmetic function h : ℕ → ℚ_{>0} by the rule h(n) := σ(n)/ϕ(n). If a, b ∈ ℕ are such that a is a proper divisor of b, then h(a) < h(b).

Proof. Let us suppose a = ∏_{i=1}^{m} p_{i}^{α_{i}} and b = ∏_{i=1}^{m} p_{i}^{β_{i}} with β_{i} ≥ α_{i} ≥ 0 and β_{i} > 0. Then adapting Equation (1), one calculates that the ratio h(b)/h(a) equals

∏_{i=1, α_{i}=0}^{m} (\frac{1 − _{\frac{1}{p_{i}^{β_{i}+1}}}}{(1 − \frac{1}{p_{i}} )^{2}} ) · ∏_{i=1, α_{i}>0}^{m} \begin{matrix}(1 − _{\frac{1}{p_{i}^{β_{i}+1}}} ) & (1 − \frac{1}{p_{i}} ) & 2 \\ (1 − \frac{1}{p_{i}} ) & 2 & (1 − _{\frac{1}{p_{i}^{α_{i}+1}}} ) \end{matrix} = \frac{σ(c)}{ϕ(c)} · ∏_{i=1, α_{i}>0}^{m} \frac{1 − _{\frac{1}{p_{i}^{β_{i}+1}}}}{1 − _{\frac{1}{p_{i}^{α_{i}+1}}}}

where c := ∏_{i=1, α_{i}=0}^{m} p_{i}^{β_{i}}. The right-hand side is greater than one unless both c = 1 and α_{i} = β_{i} at every α_{i} > 0, which corresponds precisely to the situation a = b.

We shall also need an inequality of Heath-Brown and Nielsen [17].

Lemma 5. Let r, a, b ∈ ℕ and x_{1}, …, x_{r} be integers with 1 < x_{1} < ⋯ < x_{r}. If

∏_{i=1}^{r} (1 − \frac{1}{x_{i}} ) ≤ \frac{b}{a} < ∏_{i=1}^{r−1} (1 − \frac{1}{x_{i}} )

then one has the strict inequality b · ∏_{i=1}^{r} x_{i} < (b + 1)^{2^{r}}.

The following well known theorem of Erdős and Wintner [9, Theorem 5.1] will be referred to in Section 5.

Lemma 6. A real additive function f(n) has a limiting distribution, if and only if the three series

∑_{|f(p)|>1} \frac{1}{p},  ∑_{|f(p)|≤1} \frac{f(p)}{p} and ∑_{|f(p)|≤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 ∑_{f(p)≠0} 1/p is divergent.

In the same section, we will also require a result of Banks, Friedlander, Pomerance and Shparlinski [3, Theorem 3.1].

Lemma 7. Let ϵ > 0 be given. If y is chosen so that (log log x)^{1+ϵ} ≤ y ≤ x and u := log x/ log y → ∞, then

Φ(x, y) ≤ x exp ( − (1 + o(1))u log log u)

where Φ(x, y) := #{n ≤ x : p | ϕ(n) implies p ≤ y}.

3 Solutions for low values of ω(n)

Our first result is a prototype structure theorem for elements belonging to the set R_{2}.

Lemma 8. (i) All solutions to σ(n)/ϕ(n) = 2 are odd.

(ii) If n = p^{α} is a prime power solution, then p = 3 and α = 1.

(iii) If n is a solution and 3|n, then n = 3.

Proof. Suppose σ(n) = 2ϕ(n) with n = 2^{e} · ∏_{odd p|n} p^{α_{p}}. If n > 1 and e ≥ 1, then

(2^{e+1} − 1) · ∏_{odd p|n} \frac{p^{α_{p}+1} − 1}{p − 1} = 2^{e} · ∏_{odd p|n}(p − 1) · p^{α_{p}−1}.

As a consequence

\frac{3}{2} ≤ (2 − \frac{1}{2^{e}} ) = ∏_{odd p|n} \frac{p^{α_{p}} − p^{α_{p}−1}}{p^{α_{p}} + p^{α_{p}−1} + ⋯ + 1} ≤ 1

hence n must be odd, and (i) follows.

Let p denote an odd prime, and assume that n = p^{α} ∈ R_{2} is a solution with α ≥ 1. From the equation 2 = σ(p^{α})/ϕ(p^{α}) one quickly discovers that p^{α+1} −1 = 2p^{α−1}(p−1)^{2}. The latter implies p^{α−1} | p^{α+1} − 1, thus α = 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 ω(n) > 1. If 3^{α}∥n then by Equation (1),

\frac{1 − \frac{1}{3^{α+1}}}{4/9} · F = 2 for some rational F > 1.

In particular \frac{9}{4}(1 − \frac{1}{3^{α+1}} ) < 2, implying 3^{α+1} < 9 which is false. Therefore n = 3.

Lemma 9. If n ∈ R_{2} and ω(n) = 2, then n = 35.

Proof. Let n = p^{α} · q^{β}. First note that the term 1/(1 − 1/p) is decreasing as p increases. Therefore if both p, q ≥ 7 one finds

1.85 ≥ \frac{1}{(1 − \frac{1}{p})^{2}(1 − \frac{1}{q})^{2}} ≥ \frac{(1 − \frac{1}{p^{α+1}} )(1 − \frac{1}{q^{β+1}} )}{(1 − \frac{1}{p})^{2}(1 − \frac{1}{q})^{2}} = 2

hence by Lemma 8, we can assume 5 = p < q.

Suppose that p = 5 and q ≥ 11, in which case

\frac{(5^{α+1} − 1)/4}{5^{α−1} · 4} · \frac{1 − \frac{1}{q^{β+1}}}{(1 − \frac{1}{q})^{2}} = 2.

Now the second term on the right is decreasing in q, so by Equation (5) is strictly bounded above by 1/(1 − 1/11)^{2} = 121/100. It follows that \frac{5^{α+1}−1}{16·5^{α−1}} · \frac{121}{100} > 2, whence

5^{α+1} > 5^{α+1} − 1 > \frac{200 · 16}{121 · 25} · 5^{α+1} > 1.05 · 5^{α+1} > 5^{α+1}

and the last statement is clearly false.

The only remaining possibility is p = 5 and q = 7. If α = 1 then

\frac{5 + 1}{5 − 1} · \frac{1 − 1/7^{β+1}}{6^{2}/7^{2}} = 2

which means β = 1 (likewise if β = 1, we must have α = 1). However in the equation

(\frac{1 − 1/5^{α+1}}{4^{2}/5^{2}} ) · (\frac{1 − 1/7^{β+1}}{6^{2}/7^{2}} ) = 2

both factors on the left are strictly increasing in α and β respectively, thus there can be no solutions with α > 1 or β > 1.

Lemma 10. If n ∈ R_{2} and ω(n) = 3, then n = 1045.

Proof. Let p, q, r be distinct prime numbers and α, β, γ be natural numbers such that n = p^{α} · q^{β} · r^{γ} satisfies σ(n) = 2ϕ(n). We first show (p, q, r) lies in the set of triples

{(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)}.

Note that if (p, q, r) = (5, 11, 19) then α = β = γ = 1 is certainly a solution.

One may assume p < q < r. By Lemmas 4, 8 and 9 we must have p ≥ 5 and q ≥ 11, and from Equation (2) with α = 2, β = 1 we find

\frac{1}{\sqrt{2}} > (1 − \frac{1}{5}) (1 − \frac{1}{11}) (1 − \frac{1}{r})

which implies r < 37, thence 13 ≤ r ≤ 31. We checked each prime triple (p, q, r) with p < q < r such that 5 ≤ p and r ≤ 31 against the inequalities in Equation (2), and obtained the nine (potential) solutions to σ(n) = 2ϕ(n) listed above, and nothing else. In the case α = β = γ = 1 the only solution was (5, 11, 19).

Let us write the equation σ(n) = 2ϕ(n) in the form

2 = (\frac{1 − \frac{1}{p^{α+1}}}{(1 − \frac{1}{p})^{2}} ) · (\frac{1 − \frac{1}{q^{β+1}}}{(1 − \frac{1}{q})^{2}} ) · (\frac{1 − \frac{1}{r^{γ+1}}}{(1 − \frac{1}{r})^{2}} )

and observe that each of the three factors is decreasing in p, q and r respectively, and increasing in α, β and γ. (By Lemma 4, because (5, 11, 19) is a solution there can be no other solution for this choice of primes with any one or more of α, β, γ greater than 1.)

Moreover, if p, q, r ≥ 7 then p ≥ 7, q ≥ 11 and r ≥ 13; therefore using Equation 2

0.707 > \frac{1}{\sqrt{2}} > (1 − \frac{1}{p}) (1 − \frac{1}{q}) (1 − \frac{1}{r}) ≥ (1 − \frac{1}{7}) (1 − \frac{1}{11}) (1 − \frac{1}{13}) > 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^{α} · q^{β} · r^{γ} solves σ(n) = 2ϕ(n). Using Equation (1) again, one discovers

− log (1 − \frac{1}{5^{α+1}} ) − log (1 − \frac{1}{11^{β+1}} ) − log (1 − \frac{1}{13^{γ+1}} )

= − log (2 (1 − \frac{1}{5})^{2} (1 − \frac{1}{11})^{2} (1 − \frac{1}{13})^{2}) = 0.103846 =: λ say.

However for 0 < x < 1 we have

\frac{x}{1 − x} > − log(1 − x)

in which case

\frac{3}{5^{min(α,β,γ)+1} − 1} > \frac{1}{5^{α+1} − 1} + \frac{1}{11^{β+1} − 1} + \frac{1}{13^{γ+1} − 1} > λ.

The latter implies 31 > 5^{min(α,β,γ)+1}, and further that 1 = min(α, β, γ).

We next consider in turn each of the cases α = 1, β = 1 and γ = 1 leaving the other variables free, thereby eliminating possibilities through a short tree walk. If α = 1 then

\frac{1}{24} + \frac{1}{11^{β+1} − 1} + \frac{1}{13^{γ+1} − 1} > λ;

consequently

\frac{2}{11^{min(β,γ)+1} − 1} > λ − \frac{1}{24}

yielding 11^{min(β,γ)+1} < 34, so α = 1 is clearly impossible. If however β = 1, we obtain

25 ≤ 5^{min(α,γ)+1} < \frac{2}{λ − \frac{1}{120}} + 1 < 22,

and if γ = 1 then

25 ≤ 5^{min(α,β)+1} < \frac{2}{λ − \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.

The previous three lemmas may be neatly summarised, as follows.

Theorem 11. If n ∈ R_{2} has at most 3 distinct prime factors, then n = 3, 35 or 1045.

More generally, if we make some restrictions on the exponents occurring in the prime decomposition of a solution n ∈ R_{a/b} (e.g., ν_{p}(n) ≤ 1 for all primes p), one can obtain explicit finiteness results on the number of solutions with a bounded value of ω(n).

Lemma 12. Let k, a, b be fixed natural numbers, and consider the set R_{a/b}. Then there are at most a finite number of squarefree n satisfying σ(n) = a · ϕ(n)/b with ω(n) = k.

Proof. We assume k ≥ 2. In Equation (1) one chooses m = k, and for all i take α_{i} = 1 since n is squarefree. Now for n = p_{1} ⋯ p_{k} one can rewrite this equation as

\frac{b}{a} = ∏_{i=1}^{k} (1 − \frac{2}{p_{i} + 1}) < ∏_{i=1}^{k−1} (1 − \frac{2}{p_{i} + 1}) .

If n is odd then we apply Lemma 5, and immediately conclude

b · ∏_{i=1}^{k} (\frac{p_{i} + 1}{2}) < (b + 1)^{2^{k}}

which implies n + k < 2^{k} · (b + 1)^{2^{k}}/b. If n = 2m is even then σ(m)/ϕ(m) = a/(3b) and m is odd, hence

m + k − 1 ≤ ∏_{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).

Setting b = 1, and combining the bounds directly above for n even/odd, we obtain

Theorem 13. If a squarefree integer n satisfies the divisibility ϕ(n)|σ(n) with ω(n) = k, then

n < 2^{2^{k}+k} − k.

In particular, there exist at most a finite number of such n.

4 Applications of the product compactification of ℕ

For each prime p, let ℕ_{p} denote the one point compactification of ℤ_{≥0}; in particular, each finite point n ∈ ℤ_{≥0} is itself an open set, and a basis for the neighborhoods of the point at infinity, p^{∞} say, is given by the open sets U_{p}^{(ϵ)} = {n ∈ ℤ_{≥0} : n ≥ 1/ϵ} ∪ {p^{∞}} with ϵ > 0. If ℙ indicates the set of prime numbers, let us write

ℕ̂ := ∏_{p∈ℙ} ℕ_{p}

for the product of these indexed spaces, endowed with the standard product topology. Then ℕ̂ is a compact metrizable space so it is sequentially compact, hence every sequence in ℕ̂ has a convergent subsequence. Note the useful equivalence that N_{i} ⟶ N_{o} in ℕ̂ if and only if for all primes p, ν_{p}(N_{i}) → ν_{p}(N_{o}) in ℕ_{p}.

If N is a positive integer we write N̂ for the corresponding element of ℕ̂, namely (n_{p} : p ∈ ℙ) where n_{p} = ν_{p}(N). For example, ˆ84 = (2, 1, 0, 1, …) and ˆ1 = (0, 0, 0, …). Let ℕ have the discrete topology; we shall identify ℕ with its image in ℕ̂ under the embedding n → n̂, yielding a dense subset of ℕ̂. If h : ℕ → ℝ is a multiplicative function, and if for p ∈ ℙ each sequence (h(p^{n}))_{n∈ℤ_{≥0}} is Cauchy in neighborhoods U_{p}^{(ϵ)}, one may extend h to a function on

ℕ̂ through the formula

h(N̂) := lim_{n̂→(...,ν_{p}(N),...)} (∏_{p∈ℙ} h(p^{n_{p}}))

providing the limit exists and the product converges, of course.

Remark 14. We shall call ℕ̂ equipped with its topology the product compactification of ℕ. A nice account detailing some of the properties of this set-up, with the compactification called the ‘supernatural topology’, is given by Pollack in [21]; it is used, for example, to explore the perfect number problem. The topology was first introduced by Steinitz [22] and used in a number of applications, including [2] and [5].

Lemma 15. Let P ⊂ ℙ be a finite set of primes. Assume we are given a sequence of natural numbers (N_{i}) such that N_{i} → N_{o} in ℕ̂, and for all i ∈ ℕ one has supp(N_{i}) ⊂ P. Finally let h : ℕ → ℝ be a positive multiplicative function, such that for each p ∈ P

h(p^{∞}) := lim_{n→∞} h(p^{n})

exists in (0, ∞], i.e. is strictly positive or infinity. Defining the disjoint sets

A = {p ∈ P : ν_{p}(N_{o}) < ∞} and B = {p ∈ P : ν_{p}(N_{o}) = ∞}

then inside ℝ_{>0} ∪ {∞},

lim_{i→∞} h(N_{i}) = h(A) · h(B^{∞})

where A := ∏_{p∈A} p^{ν_{p}(N_{o})} and B := ∏_{p∈B} p.

Proof. Firstly note that supp(N_{o}) ⊂ P, so the sets of primes A and B are well-defined and finite. We can write P = A ∪ B as a disjoint union, and then decompose

N_{i} = ∏_{p∈P} p^{ν_{p}(N_{i})} = ∏_{p∈A} p^{ν_{p}(N_{i})} · ∏_{p∈B} p^{ν_{p}(N_{i})}.

Because N_{i} → N_{o} in ℕ̂, for each prime p we must have ν_{p}(N_{i}) → ν_{p}(N_{o}) in ℤ_{≥0} ∪ {∞}. By assumption h is multiplicative on ℕ, in which case

h(N_{i}) = ∏_{p∈P} h(p^{ν_{p}(N_{i})}) = ∏_{p∈A} h(p^{ν_{p}(N_{i})}) · ∏_{p∈B} h(p^{ν_{p}(N_{i})}).

Since A is a finite set, then at each p ∈ A and for all i ≥ i_{1} say, ν_{p}(N_{i}) = ν_{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 ∈ B, ν_{p}(N_{i}) → ∞ hence h(p^{ν_{p}(N_{i})}) → h(p^{∞}). 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 · ∞ does not occur. As an immediate consequence the second term above must tend to h(B^{∞}), and the lemma is proved.

Lemma 16. Let h : ℕ → ℝ be a multiplicative function, and assume (N_{i}) ⊂ ℕ is a sequence of natural numbers such that N̂_{i} → N̂_{o} inside ℕ̂, for some positive integer N_{o}. If for all sequences (M_{i}) ⊂ ℕ such that M̂_{i} → ˆ1 in ℕ̂ we also have h(M_{i}) → 1 inside ℝ, then lim_{i→∞} h(N_{i}) = h(N_{o}).

Proof. Given that N̂_{i} → N̂_{o}, one defines P := supp(N_{o}) which is a finite set as N_{o} ∈ ℕ. Let us write N_{i} = A_{i} · M_{i} where supp(A_{i}) ⊂ P, and supp(M_{i}) ∩ P = ∅ so that gcd(A_{i}, M_{i}) = 1. Since M̂_{i} → ˆ1 thus h(M̂_{i}) → 1 and Â_{i} → N̂_{o}, and it therefore follows

h(N_{i}) = h(A_{i}) · h(M_{i}) ⟶ h(N̂_{o}) · 1 = h(N_{o}).

Theorem 17. Let P be a finite set of primes. Then there exist at most a finite number of positive integers N ∈ ℕ with supp(N) ⊂ P such that σ(N)/ϕ(N) = 2.

Proof. Let ℕ̂ be endowed with the product topology, and suppose there exists an infinite sequence of distinct integers (N_{i})_{i≥1} in R_{2} for which supp(N_{i}) ⊂ P for each i ∈ ℕ. Then there is a subsequence, also denoted (N_{i}), and a limit N_{o} ∈ ℕ̂ such that N_{i} → N_{o}.

Let h(n) := σ(n)/ϕ(n) for n ∈ ℕ and h(p^{∞}) := p^{2}/(p − 1)^{2}, so that h(p^{n}) → h(p^{∞}) for all p ∈ ℙ. If N_{o} was divisible by a prime not in P, then we would have an N_{i} divisible by that prime, which is false. Hence N_{o} has finite support. By Lemma 15 we can write

N_{o} = A · B^{∞}

where A and B each supported by P are odd, have gcd(A, B) = 1, are such that B is squarefree, and h(N_{i}) → h(A) · h(B^{∞}).

However this means 2 = h(A)·h(B^{∞}). 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 ≥ i_{1} say we have A a proper unitary divisor of N_{i}. For such an i, put N_{i} = A·B_{i} so B_{i} > 1. Let us write B_{i} = ∏_{p|B_{i}} p^{e_{p,i}} where e_{p,i} = ν_{p}(B_{i}) tends to ν_{p}(B^{∞}) = +∞ 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) · h(B_{i}) = \frac{σ(A)}{ϕ(A)} · ∏_{p|B_{i}} \frac{p^{2}}{(p − 1)^{2}} ·(1 − \frac{1}{p^{e_{p,i}+1}} ) .

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.

Theorem 18. Let k ≥ 1 be a given natural number. There exist at most a finite number of positive integers n with Ω(n) ≤ k satisfying σ(n)/ϕ(n) = 2.

Proof. Let h : ℕ → ℝ be defined by h(n) = σ(n)/ϕ(n). Suppose there exist an infinite number of distinct positive integers N_{i} satisfying both the equality 2 = h(N_{i}) and the constraint Ω(N_{i}) ≤ k for all i. By passing to a suitable subsequence, also denoted (N_{i}), one can assume N_{i} → N_{o} in ℕ̂.

Remark 19. (i) We must have N_{o} supported by at most k primes, otherwise this would apply to at least one N_{i} yielding Ω(N_{i}) ≥ ω(N_{i}) > k which is false.

(ii) Furthermore, all the components of N_{o} in ℕ̂ must be bounded above by k since at each prime p, one has k ≥ ν_{p}(N_{i}) → ν_{p}(N_{o}).

(iii) It follows that this limit point N_{o} must correspond to a natural number.

For i sufficiently large, we can therefore write N_{i} = N_{o}·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 ∈ supp(N_{o}) that ν_{p}(N_{o}) = ν_{p}(N_{i}) for all indices i ≥ 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≥1} tending to infinity, such that supp(B_{i}) ⊂ [x_{i}, ∞). If not, then there exists a prime q for which ν_{q}(B_{i}) > 0 infinitely often, which would force ν_{q}(N_{o}) to be positive even though q ∉ supp(N_{o})! Therefore our claim concerning supp(B_{i}) must be true, in which case

1 ≤ h(B_{i}) = ∏_{p|B_{i}} (\frac{1 − \frac{1}{p^{νp(B_{i})+1}}}{(1 − \frac{1}{p})^{2}} ) < ∏_{p|B_{i}} (1 − \frac{1}{p})^{−2} ≤ (1 − \frac{1}{x_{i}} )^{−2k} ⟶ 1.

By Lemma 16 it follows 2 = h(N_{i}) = h(N_{o}) · h(B_{i}) → 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.

5 Density of the union of the R_{a}’s

Paul Erdős was very interested in the so-called primitive sequences of natural numbers, i.e., sequences A = (a_{n})_{n∈ℕ} with a_{1} < a_{2} < a_{3} < ⋯ such that a_{i}|a_{j} only when i = j. For example, sequences of distinct numbers with exactly k prime factors are primitive.

For each x > 0 let us define A(x) = ∑_{a_{n}≤x} 1. In 1935, Erdős showed the lower natural density of A was necessarily zero, namely that

lim inf_{x→∞} \frac{A(x)}{x} = 0.

It follows from Lemma 4 that each sequence of solutions to σ(n) = a · ϕ(n) yields a primitive sequence, and therefore the set R_{a} itself has trivial lower density.

Remark 20. We have a further item of evidence that the density of R_{a} is zero, via a theorem of Erdős and Davenport from 1937. If for some sequence (a_{n}) one has

lim sup_{x→∞} \frac{1}{log x} · ∑_{a_{n}≤x} \frac{1}{a_{n}} > 0

then there exists a subsequence (a_{n_{i}}) ⊂ (a_{n}) such that a_{n_{i}} |a_{n_{i+1}} for all indices i ∈ ℕ. Hence if the a_{n}’s comprise all the elements in R_{a} ordered by ‘<’ say, then one deduces

lim sup_{x→∞} \frac{1}{log x} · ∑_{a_{n}≤x} \frac{1}{a_{n}} = 0.

Thus R_{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 [4]).

However the issue of whether solution sets have density zero can be easily resolved upon noting that by Lemma 6, f(n) := log (σ(n)/ϕ(n)) has a continuous increasing distribution function, hence the same is true for σ(n)/ϕ(n). Therefore, for any given positive integers a and b, the set R_{a/b} has density zero. In fact much more than this is true in the case b = 1, i.e., when ϕ(n) | σ(n). The authors are grateful to the referee for the following proof, based on ideas from [3, Theorem 3.1] (which we labelled Lemma 7).

Theorem 21. If N(x) := #{n ≤ x : ϕ(n) | σ(n)} then as x → ∞, one has the bound

N(x) ≪ x exp (−\frac{1}{2}\sqrt{log x}) .

Proof. Let n ≤ x satisfy ϕ(n) | σ(n), and write p for the largest prime factor of ϕ(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 ≤ y.

Now one has p | ϕ(n) | σ(n), therefore there exists a prime power q^{e}∥n with p∥σ(q^{e}). If e = 1 then p | q + 1; otherwise as 2q^{e} > σ(q^{e}) ≥ p and n ≠ 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 ≤ x with such a prime power divisor, B say, is of size O(x/\sqrt{y}); exploiting the fact p | ϕ(n) and a similar argument, we see that either there is a prime r | n with p | r − 1, or instead n belongs to an exceptional set, C say, of size O(x/y).

Suppose n ∉ A ∪ B ∪ C. Then n has prime factors r ≡ 1(modp) and q ≡ −1(modp), and the number of such n ≤ 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 ≤ x for which ϕ(n) | σ(n) satisfies the upper bound

N(x) ≪ #\{n ≤ x : ϕ(n) has only prime factors ≤ y\} + \frac{x}{\sqrt{y}} + \frac{x}{y} + \frac{x(log x)^{2}}{y} .

For x and u sufficiently large, by Lemma 7 one has Φ(x, y) ≤ 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

Φ(x, y) ≤ x exp(−(1 + o(1))u log log u) ≤ x exp(−\frac{u}{2}) ≤ \frac{x}{\sqrt{y}}

so for x sufficiently large, N(x) ≪ x exp (− \frac{1}{2} \sqrt{log x}). The result now follows.

For a given m ∈ ℕ, the number of solutions n to ‘m = σ(n) = 2ϕ(n)’ seems very small. One might contrast this with the equation m = ϕ(n), where the number of solutions c_{m} has been shown to satisfy c_{m} > m^{δ} for infinitely many m, and a range of values of δ [24, 19].

6 Unsolved problems

1. If σ(n) = 2ϕ(n) then it seems likely that d(n) | σ(n), and we have shown numerically that this is true for all n up to 2.1 × 10^{9}. The divisibility d(n) | σ(n) follows easily when n is squarefree, and most solutions to σ(n) = 2ϕ(n) appear to have this shape.

2. It seems that the number of solutions to σ(n) = 2ϕ(n) is infinite. An easier problem would be to find an infinite set of integers a such that σ(n) = a · ϕ(n) for at least one n.

3. No square satisfies σ(n) = a · ϕ(n) for any a ≥ 2. Along these lines it appears that perfect powers never satisfy this equation, nor even squarefull numbers.

4. The number of solutions to σ(n) = 2ϕ(n) with n ≤ x is expected to be x^{o(1)}.

References

[1] L. Alaoglu and P. Erdős, A conjecture in elementary number theory, Bull. Amer. Math. Soc. 50 (1944), 881–882.

[2] M. M. Artjuhov, On problems in the theory of amicable numbers, Acta. Arith. 27 (1975), 281–291.

[3] W. D. Banks, J. B. Friedlander, C. Pomerance, and I. E. Shparlinski, Multiplicative structure of values of the Euler function, in High Primes and Misdemeanours: Lectures in Honour of the 60th Birthday of Hugh Cowie Williams, Fields Inst. Commun., 41, Amer. Math. Soc., 2004, pp. 29–47.

[4] A. S. Besicovitch, On the density of a certain sequence of integers, Math. Ann. 10 (1935), 336–341.

[5] W. Borho, Befreundete Zahlen mit gegebener Primteileranzahl, Math. Ann. 209 (1974), 183–193.

[6] 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, J. Integer Sequences 15 (2012), Article 12.7.5.

[7] H. Delange, Sur les fonctions arithmétiques multiplicatives, Ann. Sci. École Norm. Sup. 78 (1961), 273–304.

[8] H. Delange, Application de la méthode du crible à l’étude des valeurs moyennes de certaines fonctions arithmétiques, Séminaire Delange-Pisot, 3 (1961/1962), Paris, 1963.

[9] P. D. T. A. Elliot, Probabilistic Number Theory I, Springer-Verlag, 1979.

[10] P. Erdős, On the normal number of prime factors of p − 1 and some related problems concerning Euler’s ϕ-function, Quart. J. Math. 6 (1935), 205–213.

[11] P. Erdős, Some remarks on Euler’s φ function, Acta Arith. 4 (1958), 10–19.

[12] K. Ford, The distribution of totients, Ramanujan J. 2 (1998), 67–151.

[13] K. Ford, F. Luca, and C. Pomerance, Common values of the arithmetic functions ϕ and σ, Bull. Lond. Math. Soc. 42 (2010), 478–488.

[14] K. Ford and P. Pollack, On common values of ϕ(n) and σ(n), I, Acta Math. Hungarica 133 (2011), 251–271.

[15] K. Ford and P. Pollack, On common values of ϕ(n) and σ(n), II, Algebra Number Theory 6 (2012), 1669–1696.

[16] R. K. Guy, Unsolved Problems in Number Theory, 3rd edition, Springer, 2004.

[17] D. R. Heath-Brown, Odd perfect numbers, Math. Proc. Camb. Phil. Soc. 115 (1994), 191–196.

[18] P. P. Nielsen, An upper bound for odd perfect numbers, Integers: Electronic J. Comb. Number Theory 3 (2003), A14.

[19] C. Pomerance, Popular values of Euler’s function, Mathematika 27 (1980), 84–89.

[20] C. Pomerance and A. Sárközy, Combinatorial number theory, in R. L. Graham, M. Grötschel, and L. Lovàsz, eds., Handbook of Combinatorics, Vol. 1, Elsevier Science, 1995, pp. 967–1018.

[21] P. Pollack, Finiteness theorems for perfect numbers and their kin, Amer. Math. Monthly 119 (2012), 670–681.

[22] E. Steinitz, Algebraische Theorie der Körper, J. Reine Angew. Math. 137 (1910), 167– 309.

[23] G. Tenenbaum, Introduction to Analytic and Probabilistic Number Theory, Cambridge, 1995.

[24] K. Woolridge, Values taken many times by Euler’s phi-function, Proc. Amer. Math. Soc. 76 (1979), 229–234.

2010 Mathematics Subject Classification: Primary 11A25; Secondary 11A41, 54H99, 11N60, 11N25, 11N64. Keywords: sum of divisors, Euler’s totient function, product compactification.

(Concerned with sequences \underline{A062699}, \underline{A068390}, and \underline{A104901}.)

Received June 13 2013; revised versions received August 4 2013; September 19 2013; September 26 2013. Published in Journal of Integer Sequences, October 13 2013.

Return to Journal of Integer Sequences home page.