On the Distribution of Perfect Totients

Florian Luca Instituto de Matemáticas Universidad Nacional Autónoma de México C.P. 58089 Morelia, Michoacán México

                     fluca@matmor.unam.mx

Abstract

In this paper, we study the sum of iterates of the Euler function.

1 Introduction

For every positive integer n we put ϕ(n) for the Euler function of n. If k ≥ 1 we put ϕ^{(k)}(n) for the kth iterate of the Euler function evaluated in n and κ(n) for the smallest positive integer n such that ϕ^{(κ(n))}(n) = 1. Let

F (n) = ∑_{k=1}^{κ(n)} ϕ^{(k)}(n).

Positive integers n such that F (n) = n are called perfect totients and were introduced in [10] and studied also in [6] and [12]. Let M be the set of all perfect totients. This set contains all powers of 3 so it is certainly infinite. In the recent paper [12] it was shown that M is of asymptotic density zero. More precisely, if we write M(x) = M ∩ [1, x], then it was shown in Theorem 2.2 in [12] – a little bit more than – that the estimate

#M(x) ≤ \frac{x}{(log x)^{1+o(1)}}  (1)

holds as x → ∞. The above estimate (1) is too weak to allow one to decide whether the sum

∑_{m∈M} \frac{1}{m}  (2)

is finite. Here, we prove a stronger upper bound on #M(x) than (1) which in particular implies that the sum of the series (2) is convergent.

Theorem 1. The estimate

#M(x) ≤ \frac{x}{(log x)^{2+o(1)}}  (3)

holds as x → ∞.

It was also shown in [12] that the inequality

|F (n) − n| > (log n)^{ln 2+o(1)}  (4)

holds on a set of positive integers n of asymptotic density 1. Here, we improve this to:

Theorem 2. Let ε(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→∞} ε(x) = 0. Then the inequality

n − F (n) > ε(n)n  (5)

holds on a set of positive integers n of asymptotic density 1.

Let U(x) = {F (n) ≤ x}. In [12], it was shown that #U(x) ≫ (log x)^{2} and it was asked to show that log(#U(x))/ log log x tends to infinity with x. We prove:

Theorem 3. The estimate

log (#U(x)) ≫ \frac{(log log x)^{2}}{log log log log x}  (6)

holds for all positive integers x.

Throughout this paper, we use log x = max{ln x, 1}, where ln is the natural logarithm. Further, if k ≥ 1, we write log_{k} x for the kth fold iterate of the function log. We omit the subscript when k = 1. We use the Vinogradov symbols ≪, ≫ and ≍, 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 2.1). For a positive integer n, we use P (n) for its largest prime factor with the convention that P (1) = 1, ω(n) for the number of distinct prime factors of n and ν_{2}(n) for the 2-adic order of n; i.e., the largest non-negative integer k such that 2^{k} | n. We use p, q and r to denote prime numbers and c_{0}, c_{1}, … to denote positive constants which are absolute.

2 Proof of Theorem 1

The proof of inequality (1) in [12] is based on the fact that if we put V(x) = {ϕ(n) ≤ x}, then #V(x) ≤ x/(log x)^{1+o(1)} (see [4] and [8]) together with the observation that if n ∈ M(x), then n = v + F (v) for some v ∈ V(x) (namely, v = ϕ(n)).

For our proof of Theorem 1, we take a different approach and we exploit the numbers ν_{2}(ϕ^{(2)}(n)) and ν_{2}(ϕ^{(3)}(n)) for n ∈ M(x). Before we start, we record a result which might be of independent interest.

2.1 An auxiliary result

Let K > 0 be any fixed constant. Put

N (K, x) = {n ≤ x : ν_{2}(ϕ^{(2)}(n)) ≤ K log_{2} x}.

Lemma 4. (i) The estimate

∑_{n∈N (K,x)} \frac{1}{n} = (log x)^{o(1)}

holds as x → ∞.

(ii) Let π(K, x) = #{p ≤ x : p − 1 ∈ N (K, x)}. Then

π(K, x) ≤ \frac{x}{(log x)^{2+o(1)}}

holds as x → ∞.

Proof. (i) Put L = 10 log_{2} x. Let N_{1} be the set of n ∈ N (K, x) with ω(n) ≥ L and note that

S_{1} = ∑_{n∈N_{1}} \frac{1}{n} ≤ ∑_{\begin{matrix}n≤x \\ ω(n)≥L \end{matrix}} \frac{1}{n} ≤ ∑_{k≥L} ∑_{\begin{matrix}n≤x \\ ω(n)=k \end{matrix}} \frac{1}{n} ≤ ∑_{k≥L} \frac{1}{k!} ( ∑_{p^{α}≤x} \frac{1}{p^{α}} )^{k}

≤ ∑_{k≥L} \frac{1}{k!} (log_{2} x + c_{0})^{k} ≪ ∑_{k≥L} (\frac{e log_{2} x + ec_{0}}{k} )^{k}

≤ ∑_{k≥L} (\frac{e log_{2} x + ec_{0}}{L} )^{k} ≪ (\frac{e log_{2} x + ec_{0}}{L} )^{L} ≪ 1.  (7)

In the above inequalities, we used the multinomial formula, the unique factorization, the estimate k! ≫ (k/e)^{k} which follows from Stirling’s formula, as well as the known fact that the estimate

∑_{p≤x} ∑_{α≥1} \frac{1}{p^{α}} ≤ log_{2} x + c_{0}

holds for all x with some absolute constant c_{0}.

Put y = (log x)^{2} and let N_{2} be the subset of n ∈ 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 ∈ N_{2} satisfies

S_{2} = ∑_{n∈N_{2}} \frac{1}{n} ≤ ∑_{y<r≤x} ∑_{\begin{matrix}p≤x, q≤x \\ r | gcd(p−1,q−1) \end{matrix}} ∑_{m≤x/pq} \frac{1}{pqm}

≤ ∑_{y<r≤x} \frac{1}{2} ( ∑_{\begin{matrix}p≤x \\ p≡1 (mod r) \end{matrix}} \frac{1}{p})^{2} (∑_{m≤x} \frac{1}{m}) ≪ log x(log_{2} x)^{2} ∑_{y<r} \frac{1}{r^{2}}

≪ \frac{log x(log_{2} x)^{2}}{y log y} = \frac{log_{2} x}{log x} ≪ 1,  (8)

where we used the known estimate

∑_{\begin{matrix}p≤t \\ p≡1 (mod b) \end{matrix}} \frac{1}{p} ≪ \frac{log_{2} t}{ϕ(b)}

which holds uniformly for 1 ≤ b ≤ t (see Lemma 1 of [1] or the inequality (3.1) in [3]), as well as the fact that

∑_{t≤p} \frac{1}{p^{2}} ≪ \frac{1}{t log t}

which follows by partial summation from the Prime Number Theorem.

Now we deal with the numbers n ∈ N_{3} = N (K, x)\(N_{1} ∪ N_{2}). Let z be such that log_{2} z = log_{2} x/ log_{3} x. For a positive integer n and a real number t write ω_{>t}(n) for the number of distinct prime factors p > t of n. Let n ∈ N_{3} and write it as n = abc, where

(i) all prime factors of a are ≤ z;

(ii) all prime factors p of b are > z but ω_{>y}(p − 1) < log_{2} p/(log_{3} p)^{2};

(iii) all prime factors p of c are > z and ω_{>y}(p − 1) ≥ log_{2} p/(log_{3} p)^{2}.

Note that if p | c, then

ω_{>y}(p − 1) ≥ \frac{log_{2} p}{(log_{3} p)^{2}} ≥ \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 ω_{>t}(n) ≤ ν_{2}(ϕ(n)). Furthermore, since n ∉ N_{2}, we have that

∑_{p | c} ω_{>y}(p − 1) ≤ ∑_{p | n} ω_{y}(p − 1) = ω_{>y} (∏_{p | n}(p − 1))

≤ ν_{2} (ϕ (∏_{p | n}(p − 1))) ≤ ν_{2}(ϕ^{(2)}(n)) ≤ K log_{2} x.

We thus get that

ω(c)\frac{log_{2} x}{(log_{3} x)^{3}} < ∑_{p | c} ω_{>y}(p − 1) ≤ K log_{2} x,

therefore

ω(c) < K(log_{3} x)^{3}.

Let A, B and C be the subsets of all possible values of a, b and c, respectively. Thus,

S_{3} = ∑_{n∈N_{3}} \frac{1}{n} ≤ ABC,  (9)

where

A = ∑_{a∈A} \frac{1}{a},  B = ∑_{b∈B} \frac{1}{b}  and C = ∑_{c∈C} \frac{1}{c}.  (10)

Since the union of N_{i} for i = 1, 2 and 3 covers N (K, x) it follows, by estimates (7), (8), (9) and (10), that in order to establish (i) it suffices to show that

max{A, B, C} ≤ (log x)^{o(1)} as x → ∞.  (11)

Clearly A ⊂ {a ≤ x : P (a) ≤ z} and C ⊂ {c ≤ x : ω(c) ≤ K(log_{3} x)^{3}}. Hence,

A ≤ ∏_{p≤z} (∑_{α≥0} \frac{1}{p^{α}} ) ≤ exp (∑_{p≤z} ∑_{α≥1} \frac{1}{p^{α}} ) ≤ exp(log_{2} z + c_{0})
≪ log z = (log x)^{1/ log_{3} x} = (log x)^{o(1)} as x → ∞,  (12)

while by an argument similar to the one used to bound S_{1} (see estimate (7)), we get

C ≤ ∑_{k≤K(log_{3} x)^{3}} ∑_{\begin{matrix}c≤x \\ ω(c)=k \end{matrix}} \frac{1}{c} ≤ ∑_{k≤K(log_{3} x)^{3}} (\frac{e log_{2} x + ec_{0}}{k} )^{k}

≪ (log_{3} x)^{3}(e log_{2} x + ec_{0})^{K(log_{3} x)^{3}}
= (log x)^{O((log_{3} x)^{4}/ log_{2} x)} = (log x)^{o(1)} as x → ∞.  (13)

For B, let f(t) = (log t)^{3 log_{3} t} and note that

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 for large x,

therefore all the primes p dividing b ∈ B belong to the set

P = {p : ω_{>f(p)} < log_{2} p/(log_{3} p)^{2}}

for large values of x. We show that

∑_{p∈P} \frac{1}{p} = O(1).  (14)

Note that once the above estimate (14) is proved, then

B = ∑_{b∈B} \frac{1}{b} ≤ ∏_{p∈P} (∑_{α≥0} \frac{1}{p^{α}} ) ≤ exp (∑_{p∈P} ∑_{α≥1} \frac{1}{p^{α}} ) = exp(O(1)) = O(1),

which together with estimates (12) and (13) implies estimate (11) and completes the proof of (i).

Thus, it remains to prove estimate (14). For this, let t > 0 and put P(t) = P ∩ [1, t]. We estimate the counting function #P(t) of P. Let p ∈ P(t). Let P_{1} = {p ≤ t : P (p − 1) ≤ t^{1/ log_{2} t}}. By results from [2] (see also Chapter III.5 of [13]), it follows that

#P_{1}(t) ≤ t exp(−(1 + o(1)) log_{2} t log_{3} t) = o (\frac{t}{(log t)^{2}} )  as t → ∞.  (15)

For p ∈ P_{2} = P(t)\P_{1}, we write p − 1 = qℓ, where q = P (p − 1) and ℓ is some positive integer. Fix ℓ. Then q ≤ t/ℓ is such that both linear forms q and qℓ + 1 are primes. By Brun’s sieve (see, for example, Theorem 2.3 in [5]), the number of such primes q is

≪ \frac{t}{ℓ(log(t/ℓ))^{2}} (\frac{ℓ}{ϕ(ℓ)})^{2} ≤ \frac{t(log_{2} t)^{4}}{ℓ(log t)^{2}} ,

where we used the minimal order ϕ(ℓ)/ℓ ≫ 1/ log_{2} t of the Euler function in the interval [1, t] as well as the fact that

log (\frac{t}{ℓ}) ≥ log q ≥ log(t^{1/ log_{2} t}) = \frac{log t}{log_{2} t}.

Since ℓ is a divisor of p − 1, we get that if we write ℓ = ℓ_{1}ℓ_{2}, where P (ℓ_{1}) ≤ f(t) and every prime factor of ℓ_{2} is > f(t), then

ω(ℓ_{2}) = ω_{>f(t)}(p − 1) ≤ ω_{<f(p)}(p − 1) ≤ \frac{log_{2} p}{(log_{3} p)^{2}} ≤ \frac{log_{2} t}{(log_{3} t)^{2}}

for large t. Hence, summing up over all possible ℓ’s we get

#P_{2}(t) ≤ \frac{t(log_{2} t)^{4}}{(log t)^{2}} L_{1}L_{2},  (16)

where

L_{1} = ∑_{P (ℓ_{1})≤f(t)} \frac{1}{ℓ_{1}}  and  L_{2} = ∑_{\begin{matrix}ℓ_{2}≤t \\ ω(ℓ_{2})≤log_{2} t/(log_{3} t)^{2} \end{matrix}} \frac{1}{ℓ_{2}} .  (17)

Clearly, by the argument used to bound A (see (12)), we have

L_{1} = ∑_{P (ℓ_{1})≤f(t)} \frac{1}{ℓ_{1}} ≤ exp ( ∑_{p≤f(t)} ∑_{α≥1} \frac{1}{p^{α}} ) ≤ exp (log_{2} f(t) + c_{0})
= exp(log_{3} t + log_{4} t + c_{0} + log 3) ≪ log_{2} t log_{3} t,  (18)

while by the argument used to bound S_{1} (see (7)) or C (see (13)) we have

L_{2} ≤ ∑_{ω(ℓ_{2})≤log_{2} t/(log_{3} t)^{2}} \frac{1}{ℓ_{2}} ≤ ∑_{k≤log_{2} t/(log_{3} t)^{2}} (\frac{e log_{2} t + ec_{0}}{k} )^{k}
≪ log_{2} t(e log_{2} t + ec_{0})^{log_{2} t/(log_{3} t)^{2}} = exp(O(log_{2} t/ log_{3} t))
= (log t)^{o(1)} as t → ∞.  (19)

Now estimates (18), (19) and (16) show that

#P_{2} ≤ \frac{t}{(log t)^{2+o(1)}}  as t → ∞,  (20)

and since P_{i} with i = 1 and 2 cover P(t), we get, by estimates (15) and (20), that

#P(t) ≤ #P_{1} + #P_{2} ≤ \frac{t}{(log t)^{2+o(1)}}  as t → ∞.  (21)

Estimate (14) follows now from the above estimate (21) by partial summation, which completes the proof of (i).

(ii) Let R(K, x) = {p ≤ x : p − 1 ∈ N (K, x)}. Let y = x^{1/ log_{2} x} and R_{1} = {p ≤ x : P (p − 1) ≤ y}. Estimate (15) shows that

#R_{1} ≤ x exp(−(1 + o(1)) log_{2} x log_{3} x) = o (\frac{x}{(log x)^{2}} )  as x → ∞.  (22)

For p ∈ R_{2} = R(K, x)\R_{1}, we write p − 1 = qℓ, where q = P (p − 1). The argument used in the proof of (i) to bound P_{2} shows that for a fixed ℓ the number of choices for q ≤ x/ℓ is

≪ \frac{x(log_{2} x)^{4}}{ℓ(log x)^{2}} .

Upon noticing that ℓ | p − 1 implies that ℓ ∈ N (K, x), we get, by using (i), that

#R_{2} ≤ \frac{x(log_{2} x)^{4}}{(log x)^{2}} ∑_{ℓ∈N (K,x)} \frac{1}{ℓ} = \frac{x}{(log x)^{2+o(1)}}  as x → ∞.  (23)

Since

π(K, x) ≤ #R_{1} + #R_{2},

(ii) follows from estimates (22) and (23).

2.2 The Proof of Theorem 1

We start by sieving off a few sets of positive integers n ≤ x of cardinalities O(x/(log x)^{2}). We ignore the following positive integers n ≤ x:

(i) positive integers n ≤ x with P (n) ≤ y = x^{1/ log_{2} x}. By the results from [2] or Theorem XX in [13] we get, as in the estimates of #P_{1} or #R_{1} in Lemma 4, that the number of such n does not exceed

x exp(−(1 + o(1)) log_{2} x log_{3} x) = o (\frac{x}{(log x)^{2}} ) as x → ∞.

(ii) positive integers n ≤ x for which there exists a prime q > (log x)^{2} such that q^{2} | n. It is clear that the number of such positive integers does not exceed

∑_{(log x)^{2}<q≤x^{1/2}} \frac{x}{q^{2}} ≪ \frac{x}{(log x)^{2} log_{3} x} = o (\frac{x}{(log x)^{2}} ) as x → ∞.

(iii) positive integers n ≤ x not satisfying (i) and (ii) above such that if we put z = y^{1/ log_{2} x}, then n = P m, where P = P (n), and P (p − 1) < z. Fix the number m. Since log P/ log z ≥ log P/ log z ≥ log_{2} x, it follows again by the results from [2] or Theorem XX in [13], that the number of possible values for P is

≤ \frac{x}{m} exp(−(1 + o(1)) log_{2} log_{3} x) = o (\frac{x}{m(log x)^{3}} ) as x → ∞

and uniformly in m ≤ x/P ≤ x/y. Thus, summing up over all the possible values of m ≤ x, we get that the total number of such integers n does not exceed

\frac{x}{(log x)^{3}} ∑_{m≤x} \frac{1}{m} ≪ \frac{x}{(log x)^{2}}

if x is sufficiently large.

(iv) positive integers n ≤ x not satisfying (i)–(iii) such that q^{2} | P −1 for some q ≥ (log x)^{3}, where P = P (n). Write again n = P m. For fixed values of m and q, the number of such choices for P ≤ x/m, even neglecting the fact that it is prime, is at most x/mq^{2}. This shows that the totality of such integers n does not exceed

∑_{m≤x/y} ∑_{(log x)^{3}≤q≤(x/m)^{1/2}} \frac{x}{mq^{2}} ≤ x (∑_{m≤x} \frac{1}{m}) ( ∑_{(log x)^{3}≤q} \frac{1}{q^{2}} )

≪ x log x ∫_{(log x)^{3}}^{∞} \frac{dt}{t^{2}} = O (\frac{x}{(log x)^{2}} ) as x → ∞.

(v) positive integers n ≤ x not of the form (i)–(iv) such that if we write again n = P m, where P = P (n), then there exists a prime q > (log x)^{2} with the property that q | gcd(P − 1, ϕ(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 | r − 1. Fixing q, r and P, we get that the number of n ≤ x which are multiples of P r does not exceed x/P r. Hence, the totality of such integers n does not exceed

∑_{(log x)^{2}≤q≤x^{1/2}} ∑_{\begin{matrix}q | gcd(P −1,r−1) \\ P r≤x \end{matrix}} \frac{x}{P r} ≤ x ∑_{(log x)^{2}≤q≤x^{1/2}} \frac{1}{2} ( ∑_{\begin{matrix}p≡1 (mod q) \\ p≤x \end{matrix}} \frac{1}{p})^{2}

≪ x(log_{2} x)^{2} ∑_{(log x)^{2}≤q≤x^{1/2}} \frac{1}{q^{2}} ≪ \frac{x log_{2} x}{(log x)^{2}}.

(vi) positive integers n not of the form (i)–(v) such that if we write n = P m with P = P (n) > P (m), then m ≡ −1 (mod 2^{M}), where M = ⌊5 log_{2} x⌋. For each such fixed m, the number of possible choices for P ≤ x/m is

π (\frac{x}{m}) ≤ \frac{x}{m log(x/m)} ≤ \frac{x}{m log y} = \frac{x log_{2} x}{m log x}.

Summing up over all the m ≤ x of the form m = 2^{M}λ − 1 for some λ ≥ 1, we get that the totality of such n does not exceed

\frac{x log_{2} x}{log x} ∑_{1≤λ≤x/2^{M}} \frac{1}{2^{M}λ − 1} ≪ \frac{x log_{2} x}{2^{M} log x} ∑_{1≤λ≤x} \frac{1}{λ}

≪ \frac{x log_{2} x}{2^{M}} ≪ \frac{x log_{2} x}{(log x)^{5 log 2}} = o (\frac{x}{(log x)^{2}} ) as x → ∞.

From now on, we work with the set M′ of the perfect totients n ≤ 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.

Let M_{1} be the subset of n ∈ M′ such that ν_{2}(ϕ^{(2)}(n)) ≥ 2M. We now make the observation that if m is an even number, then ν_{2}(ϕ(m)) ≥ ν_{2}(m) except when m is a power of 2. Further, note that if ϕ^{(ℓ)}(m) is a power of 2, then ϕ^{(ℓ+i)}(m) is also a power of 2 for all i ≥ 0. Thus, letting κ_{1}(n) be the largest positive integer ℓ ≥ 2 such that ϕ^{(ℓ)}(n) is not a power of 2, from the above remark we get that for n ∈ M_{1} we have

2M ≤ ν_{2}(ϕ^{(2)}(n)) ≤ ν_{2}(ϕ^{(3)}(n)) ≤ … ≤ ν_{2}(ϕ^{(κ_{1}(n)+1)}(n)).

Writing ϕ^{(κ_{1}(n)+1)}(n) = 2^{β} with some β ≥ 2M, we get

∑_{k=κ_{1}(n)+1}^{κ(n)} ϕ^{(k)}(n) = ∑_{i=0}^{β} 2^{i} = 2^{β+1} − 1.

Since n is a perfect totient, we get the following congruence

n − ϕ(n) + 1 = 1 + ∑_{k=2}^{κ(n)} ϕ^{(k)}(n) = 1 + ∑_{k=2}^{κ_{1}(n)} ϕ^{ℓ}(n) + ∑_{k=κ_{1}(n)+1}^{κ(n)} ϕ^{(k)}(n)

= ∑_{ℓ=2}^{κ_{1}(n)} ϕ^{(k)}(n) + 2^{β+1} ≡ 0 (mod 2^{2M}).  (24)

Write n = P m, where P > max{P (m), y} for large x because n is neither as in (i) nor as in (ii). So

n − ϕ(n) + 1 = P m − (P − 1)ϕ(m) + 1 = P (m − ϕ(m)) + (ϕ(m) + 1).

Note that m > 2 if x is large enough. Indeed, since n is odd we get that if m ≤ 2, then m = 1 and n = P, therefore

P ≥ ϕ(P) + ϕ(ϕ(P)) = P − 1 + ϕ(P − 1),

leading to 1 ≥ ϕ(P − 1); thus, P ≤ 3, which is impossible for large x since P > y. Since m > 2, we get that m − ϕ(m) > 0 and ϕ(m) + 1 is odd. Thus, for fixed odd m > 1 the congruence

P (m − ϕ(m)) + ϕ(m) + 1 ≡ 0 (mod 2^{2M})

puts P into a certain residue class a_{m} modulo 2^{2M}. Since P ≤ x/m, it follows that the number of possibilities for P is π(x/m; 2^{2M}, a_{m}). By a result of Montgomery and Vaughan [11], we know that

π(x/m; 2^{2M}, a_{m}) ≤ \frac{2x}{mϕ(2^{2M}) log(x/m2^{2M})}.  (25)

Note that

\frac{x}{m2^{2M}} ≥ \frac{y}{(log x)^{10 ln 2}} > y^{1/2}  (26)

if x is sufficiently large. Hence, inequalities (25) and (26) lead to

π(x/m; 2^{2M}, a_{m}) ≪ \frac{x}{m2^{2M} log y} ≪ \frac{x log_{2} x}{m(log x)^{1+10 ln 2}} .  (27)

Summing up over all the possible choices for m we get that

#M_{1} ≤ ∑_{m≤x/y} π(x/m; 2^{2M}, a_{m}) ≪ \frac{x log_{2} x}{(log x)^{1+10 ln 2}} ∑_{m≤x/y} \frac{1}{m}

≪ \frac{x log_{2} x}{(log x)^{10 ln 2}} = o (\frac{x}{(log x)^{2}} )  as x → ∞.  (28)

Now let M_{2} be the subset of n ∈ M′\M_{1} such that ν_{2}(ϕ^{(3)}(n)) < 4M. Let n = mP. Since n ∉ M_{1}, it follows that ν_{2}(ϕ^{(2)}(m)) ≤ ν_{2}(ϕ^{(2)}(n)) < 2M. In particular, m ∈ N (10, x). Further, since

log_{2}(x/m) ≥ log_{2} y ≥ (log_{2} x)/2

holds for large x and all m < x/y, we get

ν_{2}(ϕ^{(2)}(P − 1)) ≤ ν_{2}(ϕ^{(3)}(n)) < 4M ≤ 20 log_{2} x ≤ 40 log_{2}(x/m).

Thus, P ∈ N (40, x/m). Fixing m, it follows by Lemma 4 (ii) that the number of possibilities for P is

≤ \frac{x}{m(log(x/m))^{2+o(1)}} ≤ \frac{x}{m(log y)^{2+o(1)}} ≤ \frac{x}{m(log x)^{2+o(1)}} as x → ∞

uniformly in m ≤ x/y. Summing up over all m ∈ N (10, x) and using Lemma 4 (i), we get that

#M_{2} ≤ \frac{x}{(log x)^{2+o(1)}} ∑_{m∈N (10,x)} \frac{1}{m} ≤ \frac{x}{(log x)^{2+o(1)}}  as x → ∞.  (29)

From now on, we look at positive integers in M_{3} = M′\(M_{1}∪M_{2}). Note that if n ∈ M_{3} then 4M ≤ ν_{2}(ϕ^{(3)}(n)).

For n ∈ M_{3}, we write n = P m, where P = P (n) > P (m), and P − 1 = Qℓ, where Q = P (P − 1). Note that we again have m ∈ 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 ϕ(m)ℓ. Let d be the largest divisor of P − 1 which is divisible only by primes dividing ϕ(m). Thus, P (d) < (log x)^{2} and d is a divisor of ℓ. Write ℓ = ds. From now on we fix m, the number d which consists only of prime factors of ϕ(m) smaller than (log x)^{2}, and the number s which is coprime to dϕ(m). Notice that ϕ(n) = (P − 1)ϕ(m) = Qsdϕ(m), every prime factor of d divides ϕ(m), and Qs is coprime to ϕ(m). Thus, ϕ(ϕ(n)) = (Q − 1)ϕ(s)dϕ(ϕ(m)).

An argument identical to the one used to derive congruence (24) gives

n − ϕ(n) − ϕ(ϕ(n)) + 1 ≡ 0 (mod 2^{4M})

for n ∈ M_{3}. Note that

n − ϕ(n) − ϕ(ϕ(n)) + 1
= P (m − ϕ(m)) + (ϕ(m) + 1) − (Q − 1)ϕ(s)dϕ(ϕ(m))
= (Qsd + 1)(m − ϕ(m)) + (ϕ(m) + 1) − (Q − 1)ϕ(s)dϕ(ϕ(m))
= Q(sd(m − ϕ(m)) − ϕ(s)dϕ(ϕ(m))) + (m − ϕ(m)) + (ϕ(m) + 1)
+ϕ(s)dϕ(ϕ(m))
= Q(sd(m − ϕ(m)) − ϕ(s)dϕ(ϕ(m))) + (m + 1 + ϕ(s)dϕ(ϕ(m))).

Put

C_{m,d,s} = sd(m − ϕ(m)) − ϕ(s)dϕ(ϕ(m)) and D_{m,d,s} = m + 1 + ϕ(s)dϕ(ϕ(m)).

Observe that C_{m,d,s} ≠ 0 for large x. Indeed, if C_{m,d,s} = 0, we then get

n − ϕ(n) − ϕ(ϕ(n)) + 1 = m + 1 + ϕ(s)dϕ(ϕ(m))
= m + 1 + sd(m − ϕ(m))
≤ m + (P − 1)\frac{m}{Q} ≤ \frac{mP}{y} + \frac{mP}{z}
≤ \frac{2mP}{z} .  (30)

However, since n ∈ M(x), we get that

n − ϕ(n) − ϕ(ϕ(n)) + 1 ≥ ϕ(ϕ(ϕ(n))) ≫ \frac{n}{(log_{2} x)^{3}} = \frac{mP}{(log_{2} x)^{3}} .  (31)

The last inequality above follows from applying the minimal order of the Euler function in the interval [1, x] three times as

\frac{ϕ^{(3)}(n)}{n} ≫ \frac{ϕ^{(2)}(n)}{n log_{2} x} ≫ \frac{ϕ(n)}{n(log_{2} x)^{2}} ≫ \frac{1}{(log_{2} x)^{3}}

for n ≤ x. Comparing estimates (30) and (31), we get that

\frac{2mP}{z} ≫ \frac{mP}{(log_{2} x)^{3}} ,

leading to z ≪ (log_{2} x)^{3}, which is impossible for large x.

Hence, C_{m,d,s} ≠ 0 and

C_{m,d,s}Q + D_{m,d,s} ≡ 0 (mod 2^{4M}).  (32)

Let M_{4} be the subset of 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 − ϕ(m)) + m + 1. Note that m − ϕ(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^{α}m_{1} where m_{1} is odd, then α ≤ M. Since sd(m−ϕ(m))+m+1 is a multiple of 2^{2M}, we get that sd = 2^{α}s_{1}d_{1}, where s_{1} and d_{1} are both odd. Further note that if m > 3, then ϕ(ϕ(m)) is even, therefore d = 2^{α}d_{1} and s = s_{1}. If m = 3, then ϕ(ϕ(m)) = 1, therefore d = 1 and s = 2^{α}s_{1}. Fixing m and d (hence, also α and d_{1}) the congruence sd(m − ϕ(m)) + m + 1 ≡ 0 (mod 2^{2M}) leads to s_{1}d_{1}(m − ϕ(m)) + m_{1} ≡ 0 (mod 2^{2M−α}). 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^{α}d_{1}s_{1}Q, P ≤ x/m and both P and Q are primes, it follows, by Brun’s method (see again Theorem 2.3 in [5]), that the number of possibilities for Q ≤ x/(m2^{α}s_{1}d_{1}) when m, d_{1} and s_{1} are fixed is

≪ \frac{x}{mϕ(2^{α}s_{1}d_{1})(log(x/msd))^{2}}

Since x/msd ≥ Q ≥ 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

≪ \frac{x log_{2} x}{msd(log z)^{2}} ≤ \frac{x(log_{2} x)^{5}}{m2^{α}s_{1}d_{1}(log x)^{2}} ≪ \frac{x(log_{2} x)^{5}}{ms_{1}d_{1}(log x)^{2}} .

Note that α is uniquely determined by m alone. Summing up first over all m ≤ x/y and in N (10, x), then over all odd d_{1} | ϕ(m) such that P (d_{1}) ≤ (log x)^{2}, and finally over those s_{1} ≤ x/(2^{α}zmd_{1}) with s_{1} ≡ b_{m,d} (mod 2^{M}), we get

#M_{4} ≪ \frac{x(log_{2} x)^{5}}{(log x)^{2}} ∑_{\begin{matrix}m≤x/y \\ m∈N (5,x) \end{matrix}} \frac{1}{m} ∑_{\begin{matrix}d_{1} | ϕ(m) \\ P (d_{1})≤(log x)^{2} \end{matrix}} \frac{1}{d_{1}} ∑_{0≤λ≤x/(2^{M+α}ms_{1}d_{1})} \frac{1}{b_{m,d} + λ2^{M}}

≤ \frac{x(log_{2} x)^{5}}{(log x)^{2}} ( ∑_{m∈N (10,x)} \frac{1}{m} ∑_{\begin{matrix}d_{1}≡1 (mod 2) \\ p | d_{1}=>p | ϕ(m) \end{matrix}} \frac{1}{d_{1}} ) (1 + \frac{1}{2^{M}} ∑_{1≤λ≤x} \frac{1}{λ})

≤ \frac{x(log_{2} x)^{5}}{(log x)^{2}} ( ∑_{m∈N (10,x)} \frac{1}{m} \frac{ϕ(m)}{ϕ(ϕ(m))}) (1 + O (\frac{log x}{2^{M}}))

≪ \frac{x(log_{2} x)^{6}}{(log x)^{2}} ∑_{m∈N (10,x)} \frac{1}{m} ≤ \frac{x}{(log x)^{2+o(1)}}  as x → ∞,  (33)

where in the above inequalities we used the obvious fact that if m is a positive integer then

∑_{\begin{matrix}d≥1 \\ p | d=>p | m \end{matrix}} \frac{1}{d} = ∏_{p | m} (∑_{α≥0} \frac{1}{p^{α}} ) = ∏_{p | m} (1 − \frac{1}{p})^{−1} = \frac{m}{ϕ(m)},  (34)

the inequality ϕ(m)/ϕ(ϕ(m)) ≪ log_{2} x which follows from the minimal order of the Euler function in the interval [1, x], as well as Lemma 4 (i).

Finally, let M_{5} = M_{3}\M_{4}. If n ∈ M_{5}, then n = P m, P = P (n) > P (m), P − 1 = Qsd, and γ = ν_{2}(gcd(C_{m,d,s}, D_{m,d,s})) < M. Let C′ = C_{m,d,s}/2^{γ} and D′ = D_{m,d,s}/2^{γ}. Congruence (32) shows that C′Q + D′ ≡ 0 (mod 2^{M}), therefore Q is in a certain residue class e_{m,d,s} modulo 2^{M}. Assume that e_{m,d,s} is the smallest positive integer in this congruence class. Then Q = 2^{M}λ + e_{m,d,s} ≤ x/(mds) is a prime such that P = sdQ + 1 = 2^{M}sdλ + (sde_{m,d,s} + 1) is also a prime. By Brun’s method again, the number of such possibilities for fixed m, d and s is

≪ \frac{x}{mds2^{M}(log(x/(mds2^{M})))^{2}} (\frac{ϕ(sde_{m,d,s}(sde_{m,d,s} + 1))}{sde_{m,d,s}(sde_{m,d,s} + 1)})^{2} .

Using again the minimal order of the Euler function in the interval [1, x] as well as the fact that

\frac{x}{mds2^{M}} ≥ \frac{Q}{2^{M}} ≥ \frac{z}{2^{M}} ≥ z^{1/2}

for large x, we get that the above number is at most

≪ \frac{x(log_{2} x)^{2}}{mds2^{M}(log z)^{2}} ≪ \frac{x(log_{2} x)^{6}}{mds2^{M}(log x)^{2}} .

Summing up the above inequality over all the choices of m ≤ x/y in N (10, x), d a divisor of ϕ(m) with P (d) ≤ (log x)^{2}, and s ≤ x/(zmd) coprime to ϕ(m), we get that

#M_{5} ≪ \frac{x(log_{2} x)^{6}}{2^{M}(log x)^{2}} ∑_{\begin{matrix}m≤x/y \\ m∈N (10,x) \end{matrix}} \frac{1}{m} ∑_{\begin{matrix}d≥1 \\ p | d=>p | ϕ(m) \end{matrix}} \frac{1}{d} ∑_{s≤x/(zmd)} \frac{1}{s}

≪ \frac{x(log_{2} x)^{6}}{2^{M} log x} ∑_{m∈N (10,x)} \frac{1}{m} \frac{ϕ(m)}{ϕ(ϕ(m))} ≪ \frac{x(log_{2} x)^{7}}{2^{M} log x} ∑_{m∈N (10,x)} \frac{1}{m}

≪ \frac{x}{(log x)^{1+10 ln 2+o(1)}} = o (\frac{x}{(log x)^{2}} )  as x → ∞.  (35)

In the above estimates, we used again identity (34), the minimal order of the Euler function in the interval [1, x] as well as Lemma 4 (i). Since M_{4} and M_{5} cover M_{3}, we get from estimates (33) and (35) that

#M_{3} = o (\frac{x}{(log x)^{2}} )  as x → ∞.  (36)

which together with the estimates (28), (29) and (i)–(vi) completes the proof of Theorem 1.

3 Proof of Theorem 2

Let x be a large positive real number. Since ε(x) decreases and tends to infinity arbitrarily slowly, we may assume that ε(x) ≥ 2/ log_{3} x for if not we may replace ε(x) by max{ε(x), 2/ log_{3} x}. It was shown in [7] that there exists a positive constant c_{1} such that for all n ≤ x except o(x) of them ϕ(n) is a multiple of all the primes p ≤ c_{1} log_{2} x/ log_{3} x. Thus,

ϕ^{(2)}(n) ≤ e^{−γ}(1 + o(1))\frac{ϕ(n)}{log_{3} x} as x → ∞

with o(x) exceptions n. Here, γ is the Euler constant. Since ϕ(m) ≤ m/2 whenever m is even, we get that

∑_{k=2}^{κ(n)} ϕ^{(k)}(n) ≤ ϕ^{(2)}(n) ∑_{k=2}^{κ(n)} \frac{1}{2^{k−2}} < 2ϕ^{(2)}(n) < \frac{2n}{log_{3} x}

holds for all n ≤ x with o(x) exceptions as x → ∞. We thus get that

n − F (n) ≥ (n − ϕ(n)) − \frac{2n}{log_{3} x}.

Since n − ϕ(n) counts the number of positive integers k ≤ n which are not coprime to n, it follows that n − ϕ(n) ≥ n/p(n) where p(n) is the smallest prime factor of n. Since the number of n ≤ x for which p(n) > (2ε(x))^{−1} is O(x/ log((2ε(x))^{−1})) = o(x) as x → ∞, we get that p(n) ≤ (2ε(x))^{−1} with o(x) exceptions as x → ∞. Thus, except for o(x) such n ≤ x, we have

n − F (n) ≥ \frac{n}{p(n)} − \frac{2n}{log_{3} x} ≥ 2n (ε(x) − \frac{1}{log_{3} x}) ≥ ε(x)n.

Since n log n ≥ x holds for all n ≤ x with O(x/ log x) = o(x) exceptions and ε(x) is decreasing, we get that the inequality

n − F (n) ≥ ε(n log n)n

holds on a set of n of asymptotic density 1, which implies the desired conclusion since the function ε(x) is arbitrary, subject to the conditions that it is decreasing for large x and tends to zero when x tends to infinity.

4 Proof of Theorem 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 = ⌊\sqrt{log x}⌋ and consider the set of integers

W = {∏_{p≤s} p^{α_{p}} : α_{p} ∈ [L, 2L] for all p ≤ s}.

Let M = ∏_{p≤s} p. If n ∈ W then

n ≤ M^{2L} ≤ exp((2 + o(1))sL) = exp(O((log x)^{1/2} log_{2} x log_{3} x)) = x^{o(1)}

as x → ∞, therefore

F (n) = ∑_{k≥1} ϕ^{(k)}(n) ≤ ϕ(n) ∑_{k≥1} \frac{1}{2^{k−1}} ≤ 2n = x^{o(1)} as x → ∞.

In particular F (W) ⊂ U(x) holds for large x. Note also that

#W ≥ (L + 1)^{π(s)} = exp((1 + o(1))s log L/ log s),

therefore

log(#W) ≫ \frac{s log L}{log s} ≫ \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 W is one-to-one.

We take a closer look at F (n) for n ∈ W. Note that as long as M | ϕ^{(k)}(n), we have that ϕ^{(k+1)}(n) = (ϕ(M)/M)ϕ^{(k)}(n). Since clearly M | ϕ^{(k)}(n) for all k ≤ L − 1, it follows that if we put δ = M/ϕ(M), then

ϕ^{(k)}(n) = \frac{ϕ(n)}{δ^{k−1}} = \frac{n}{δ^{k}}

holds for all k = 1, 2, …, L. Thus, for n ∈ W we have

F (n) = ∑_{k≤L} ϕ^{(k)}(n) + ∑_{k>L} ϕ^{(k)}(n) = n ∑_{k=1}^{L} δ^{−k} + O (ϕ^{(L+1)}(n) ∑_{j≥0} \frac{1}{2^{j}} )

= n (\frac{1 − δ^{−(L+1)}}{1 − δ^{−1}} ) + O (\frac{n}{δ^{L}} ) = n (\frac{1}{1 − δ^{−1}} + O (\frac{1}{δ^{L}} )) .  (37)

Note that δ = ∏_{p≤s}(1 − 1/p)^{−1} ≍ log s. Suppose now that F (n_{1}) = F (n_{2}) for two distinct integers n_{1}, n_{2} in W. From the above relation (37) we get that

\frac{1}{1 − δ^{−1}} (n_{1} − n_{2}) = O (\frac{n_{1} + n_{2}}{δ^{L}} )

and since δ → ∞ when x → ∞, we get that 1/2 < n_{1}/n_{2} < 2 holds when x is sufficiently large. We now get that

|n_{1}n_{2}^{−1} − 1| ≪ δ^{−L}.  (38)

Note that n_{1}n_{2}^{−1} ≠ 1 is a rational number of the form ∏_{p≤s} p^{δ_{p}} with some integer exponents δ_{p} ∈ [−L, L]. Using a linear form in logarithms due to Matveev (see Corollary 2.3 of [9]), we get that

log |n_{1}n_{2}^{−1} − 1| ≥ −c_{3}^{π(s)}Ω log L,  (39)

where

Ω = ∏_{p≤s} log p ≤ (log s)^{π(s)}.

Taking logarithms in estimate (38) and using (39), we get

L log δ ≤ (c_{3} log s)^{π(s)} log L,

therefore

\sqrt{log x} ≤ (c_{3} log s)^{π(s)}(log_{2} x)^{2}.

Taking logarithms again we get

(log_{2} x)/2 − log_{3} x ≤ π(s) log_{2} s + O(1) ≤ (1 + o(1))\frac{s log_{2} s}{log s} + O(1).

Recalling the definition of s, we see that if we choose c_{2} = 1/3, then the above inequality is impossible for large enough values of x. This completes the proof of Theorem 3.

5 Acknowledgments

The author thanks Professor Igor E. Shparlinski for useful advice and the anonymous referee for comments which improved the quality of this paper. Work on this paper was done during a visit to CRM in Montreal during Spring 2006. The hospitality and support of this institution is gratefully acknowledged. During the preparation of this paper, the author was also supported in part by Grants SEP-CONACyT 46755, PAPIIT IN104005 and a Guggenheim Fellowship.

References

[1] N. L. Bassily, I. Kátai and M. Wijsmuller, On the prime power divisors of the iterates of the Euler function, Publ. Math. (Debrecen) 55 (1999), 17–32.

[2] E. R. Canfield, P. Erdős and C. Pomerance, On a problem of Oppenheim concerning “Factorisatio Numerorum”, J. Number Theory, 17 (1983), 1–28.

[3] P. Erdős, A. Granville, C. Pomerance and S. Spiro, On the normal behavior of the iterates of some arithmetic function, in Analytic Number Theory Birkhäuser, Boston, 1990, pp. 165–204.

[4] K. Ford, On the distribution of totients, Ramanujan J. 2 (1998), 67–151.

[5] H. Halberstam and H.-E. Richert, Sieve Methods, Academic Press, London, 1974.

[6] D. E. Iannucci, D. Moujie and G. L. Cohen, On perfect totients numbers, J. Integer Sequences 6 (2003), Article 03.4.5.

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

[8] H. Maier and C. Pomerance, On the number of distinct values of the Euler function, Acta Arith. 49 (1988), 263–275.

[9] E. M. Matveev, An explicit lower bound for a homogeneous rational linear form in logarithms of algebraic numbers II, Izv. Ross. Akad. Nauk. Ser. Math. 64 (2000), 125–180; English translation in Izv. Math. 64 (2000), 1217–1269.

[10] A. L. Mohan and D. Suryanarayana, Perfect totient numbers, in Number Theory (Proc. 3rd Matscience Conf. Misore 1981), Lect. Notes in Math. 938, Springer-Verlag, New York, 1982, 101–105.

[11] H. L. Montgomery and R. C. Vaughan, The large sieve, Mathematika 20 (1973), 119–134.

[12] I. E. Shparlinski, On the sum of iterations of the Euler function, J. Integer Sequences 9 (2006), Article 06.1.6.

[13] G. Tenenbaum, Introduction to Analytic and Probabilistic Number Theory, Cambridge Univ. Press, Cambridge, 1995.

2000 Mathematics Subject Classification: Primary 11N56; Secondary 11N37. Keywords: Euler function, iterations, congruences.

Received April 4 2006; revised version received August 4 2006. Published in Journal of Integer Sequences, September 7 2006.

Return to Journal of Integer Sequences home page.