#A65 INTEGERS 24 (2024)

ON THE DISTRIBUTION OF ϕ(σ(N ))

Anup B. Dixit
Institute of Mathematical Sciences (HBNI), Chennai, Tamil Nadu, India.
anupdixit@imsc.res.in

Saunak Bhattacharjee
Indian Institute of Science Education and Research Tirupati, Andhra Pradesh,
India.
saunakbhattacharjee@students.iisertirupati.ac.in

Received: 3/22/24, Accepted: 6/19/24, Published: 7/8/24

Abstract
Let ϕ(n) be the Euler totient function and σ(n) denote the sum of divisors of n. In
this note, we obtain explicit upper bounds on the number of positive integers n ≤ x
such that ϕ(σ(n)) > cn for any c > 0. This is a refinement of a result of Alaoglu
and Erdős.

1. Introduction

For any positive integer n, let ϕ(n) be the Euler-totient function given by
Y 1

ϕ(n) = n 1− ,
p
p|n

where p runs over distinct primes dividing n. Let σ(n) be the sum of divisors of n,
which is given by
X Y  1 − pk+1 
σ(n) = d=n .
k
1−p
d|n p ∥n

Here the notation pk ∥n means that pk is the largest power of p dividing n. In 1944,
L. Alaoglu and P. Erdős introduced the study of compositions of such arithmetic
functions. In particular, they showed that for any real number c > 0,

#{n ≤ x : ϕ (σ (n)) ≥ cn} = o(x) and #{n ≤ x : σ (ϕ (n)) ≤ cn} = o(x).

DOI: 10.5281/zenodo.12685741
INTEGERS: 24 (2024) 2

In [3], F. Luca and C. Pomerance obtained finer results on the distribution of

σ(ϕ(n)). The objective of this paper is to study the distribution of ϕ(σ(n)).

Denote by logk the k-fold iterated logarithm log log · · · log (k-times). We show the
following result.
Theorem 1. For every c > 0,
!
 π2 x x log3 x
# n ≤ x : ϕ (σ (n)) ≥ cn ≤ +O 1 ,
6c log4 x (log x) log3 x log4 x
where the implied constant only depends on c.
 
This implies that except for O log log xlog log x integers less than x, ϕ(σ(n)) < cn
for any c > 0. It is possible to replace the constant c above by a slowly decaying
function. For a non-decreasing real function f , define
 
n
Pf (x) := n ≤ x : ϕ (σ (n)) ≥ .
f (n)
Then, we prove the following.
Theorem 2. Suppose f : R+ → R+ is a non-decreasing function satisfying

f (x) = o (log4 x) .

Then, !
xf (x) x log3 x
|Pf (x)| = O + = o(x)
log4 x (log x) log13 x log x
4
n
as x → ∞. In other words, for almost all positive integers n, ϕ(σ(n)) < f (n) .

Choosing f (x) = log5 x in Theorem 2, we obtain the following corollary, which

is an improvement of the result of Alaoglu and Erdős [2].
 
Corollary 1. Except for O xlog log5 x
x positive integers n ≤ x,
4

n
ϕ(σ(n)) ≤ .
log5 n

2. Preliminaries

A necessary component of our proof is to estimate the number of positive integers

not greater than x which do not have certain prime factors. Such an estimate
requires an application of Brun’s sieve. For our purpose, we invoke the following
result by P. Pollack and C. Pomerance [4, Lemma 3].
INTEGERS: 24 (2024) 3

Lemma 1. Let P be a set of primes and for x > 1, let

X1
A(x) = .
p
p≤x
p∈P

Then uniformly for
all choices of P , the proportion of n ≤ x free of prime factors
from P is O e−A(x) .
We also recall the famous Siegel-Walfisz theorem (see [5, Corollary 11.21]).
Lemma 2 (Siegel-Walfisz). For (a, q) = 1, let π(x; q, a) denote the number of
primes p ≤ x such that p ≡ a(mod q). Let A > 0 be given. If q ≤ (log x)A , then
li(x)  p 
π(x; q, a) = + O x exp(−c log x) ,
ϕ(q)
Rx
where the implied constant only depends on A and li(x) := 2 log1 t dt.
For any prime p, define

Sp (x) := #{n ≤ x : p ∤ σ (n)}.

The main ingredient in the proof of Theorem 1, which is also interesting in its own
right, is an upper bound for Sp (x).
Lemma 3. For any prime p and x ≥ ep
  1 !
log log x p−1
Sp (x) = O x ,
log x
where the implied constant is absolute.
Proof. Note that for any prime q ≡ −1 mod p, all n such that q∥n satisfy p | σ(n).
Thus, to obtain an upper bound for Sp (x), it suffices to estimate the number of
n ≤ x such that either q ∤ n or q 2 | n for a subset of primes q ≡ −1(mod p). By
Lemma 2, for x > ep , we have
 
x x
π(x; p, −1) = +O ,
(p − 1) log x (log x)2
where the implied constant is absolute. Now suppose x is sufficiently large such
that log x > ep . Applying partial summation, we obtain
Z x
X 1 π(x; p, −1) π(log x; p, −1) π(t; p, −1)
= − + dt
q x log x log x t2
log x < q < x
q≡−1( mod p)
Z x  
1 1 1
= dt + O
p−1 log x t log t log2 x
 
1 1
= (log2 x − log3 x) + O .
p−1 log2 x
INTEGERS: 24 (2024) 4

Now, applying Lemma 1 with P being the set of primes q ≡ −1 mod p and log x <
q < x, we obtain that the number of n ≤ x free of prime factors from P is
  1 !
log2 x p−1
O x .
log x

Since
X 1 x
#{n ≤ x : q 2 | n for prime q ≡ −1 mod p and log x < q < x} ≪ x 2
≪ ,
q log x
log x<q<x

we have the lemma.

3. Proof of Theorems 1 and 2

Proof of Theorem 1. Note that

Y  1

ϕ (σ (n)) = σ (n) 1−
p
p|σ(n)
Q
Denote by P (y) := p, the product of all primes ≤ y. If P (y)|σ(n), then
p≤y

Y  1

ϕ(σ(n)) = σ(n) 1−
p
p|σ(n)
 
Y 1 σ(n)
≤ σ(n) 1− < ,
p log y
p≤y

where the last inequality follows from Merten’s theorem (see [5, Theorem 2.7 (e)]),
namely
Y 1

1
1− < .
p log y
p≤y

Thus, for any c > 0, the inequality ϕ(σ(n)) < cn holds if P (y) | σ(n), σ(n) < δn,
and (log y)−1 ≤ c/δ. We know that (see [1, Theorem 3.4])
X π2 2
σ(n) = x + O (x log x) .
12
n≤x

Using partial summation, we get

X σ(n) π2
x + O log2 x .


=
n 6
n≤x
INTEGERS: 24 (2024) 5

Hence,
X 1 X σ(n)
#{n ≤ x : σ (n) ≥ δn} = 1≤
δ n
n≤x n≤x
σ(n)≥δn

π2 log2 x
 
= x+O .
6δ δ
Therefore,  2 
π2
 
log x
#{n ≤ x : σ (n) < δn} ≥ x 1 − +O . (1)
6δ δ
From Lemma 3, we also have
X
#{n ≤ x : P (y) ∤ σ(n)} ≤ |Sp (x)|
p≤y
  y1 !
log2 x y
=O x .
log x log y

Hence,
  y1 !!
log2 x y
#{n ≤ x : P (y) | σ(n)} ≥ x 1 − O . (2)
log x log y
Choosing
y = log3 x and δ = c log4 x
in (1) and (2), we obtain
!
π2 x x log3 x
#{n ≤ x : ϕ(σ(n)) < cn} ≥ x − +O 1 .
6c log4 x (log x) log3 x log4 x
Hence,
!
 π2 x x log3 x
# n ≤ x : ϕ (σ (n)) ≥ cn ≤ +O 1 ,
6c log4 x (log x) log3 x log4 x
which proves Theorem 1.
Proof of Theorem 2. We use the exact same method as in the proof of Theorem 1,
with the choices
log4 x
y = log3 x and δ =
f (x)
in (1) and (2). This gives
  !
n xf (x) x log3 x
# n ≤ x : ϕ(σ(n)) < ≥x−O + .
f (n) log4 x (log x) log13 x log x
4

This proves Theorem 2.

INTEGERS: 24 (2024) 6

4. Concluding Remarks

The study of composition of multiplicative arithmetic functions seems to be a diffi-

cult theme in general. This has also received scant attention, except for a very few
instances such as [2] and [4]. For example, it is not clear if ϕ(σ(n)) has a normal
order. It would be desirable to develop a unified theory for such functions and per-
haps construct families of multiplicative functions whose compositions have a finer
distribution.

Acknowledgements. We thank Professor Jean-Marc Deshouillers for several fruit-

ful discussions. We also thank the referee for comments on an earlier version of this
paper.

References
[1] T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, New York-
Heidelberg, 1976.

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

[3] F. Luca and C. Pomerance, On some problems of Makowski-Schinzel and Erdős concerning
the arithmetical functions ϕ and σ, Colloq. Math. 92, no. 1, (2002), 111–130.

[4] P. Pollack and C. Pomerance, Phi, primorials, and Poisson, Illinois J. Math. 64, no. 3, (2020),
319-330.

[5] H. L. Montgomery, R. C. Vaughan, Multiplicative Number Theory I. Classical Theory, Cam-

bridge University Press, Cambridge, 2007.