Linear equations involving iterates of σ(N)

Tomohiro Yamada

Abstract

We study integers N satisfying the equation σ(σ(N)) = Aσ(N)+ BN.

1 Introduction

We denote by σ(N) the sum of divisors of N. N is said to be perfect if σ(N) = 2N and multiperfect if σ(N) = kN for some integer k. It is not known whether or not an odd perfect/multiperfect number exists. There are many known conditions which must be satisfied by such a number. But these results are far from answering whether or not an odd perfect/multiperfect number exists.

Suryanarayana [7] called N to be superperfect if σ(σ(N)) = 2N and Pomerance [6] called N to be super multiply perfect if σ(σ(N)) = kN for some integer k. More generally, Cohen and te Riele [2] called N to be (m, k)-perfect if σ^{(m)}(N) = kN, where σ^{(m)}(N) denotes σ(σ^{(m−1)}(N)) with σ^{(0)}(N) = N.

We introduce another analogous notion of perfect/multiperfect numbers. We call N to be (n; a_{0} : …: a_{n})-perfect if ∑_{i=0}^{n} a_{n−i}σ^{(i)}(N) = 0 and (n; a_{1}, …, a_{n})-perfect if N is (n; −1 : a_{1} : …: a_{n})-perfect. N is (2; A, B)- perfect if σ(σ(N)) = Aσ(N) + BN.

We begin by noting that almost all integers are (2; A, B)-perfect for some integers A, B. This fact follows from Katai and Subbarao [3, Theorem 1]. They proved that for any fixed m ≥ 1, we have (N, σ^{(m)}(N)) = ∏_{p,p^{a}||N} p^{a}, where p runs over all primes below x_{2}^{m}, for all integers N ≤ x with o(x) exceptions (Here we use the notation x_{0} = x, x_{i+1} = max{1, log x_{i}} for all i ≥ 0, where log x is the natural logarithm of x, introduced in [4]). Hence, for almost all integers N, (N, σ(N)) divides σ^{(2)}(N), which implies that there exist some integers A, B such that σ(σ(N)) = Aσ(N) + BN.

On the other hand, we can show that for any fixed positive integers A, B, the set of (2; A, B)-perfect numbers has density zero.

Theorem 1.1. Let A, B, C be integers not all zero and satisfying AC ≤ 0. Then the number of (2; A : B : C)-perfect numbers below x is at most x exp(−(2^{−1/3} + o(1))(log x)^{1/3}(log log x)^{2/3}).

Our argument is similar to the argument of Pomerance [5] to study the distribution of integers n satisfying σ(n) ≡ a (mod n). His argument rests on the fact that almost all integers n can be written as mp, where p ∤ m is prime, large and uniquely determined by m except some special cases. Our argument adopts a factorization of p + 1 into lq with q large and (l, q) = 1, to show that q is uniquely determined by m and l under some condition.

We note that this result does not seem to apply to the case AC > 0. If p, 2p−1 are both prime, then n = 2p−1 satisfies 2σ(σ(n))−3σ(n)+6n = 0 and therefore n is (2; 2 : −3 : 6)-perfect. More generally, we can easily confirm the following result.

Theorem 1.2. Let R be an arbitrary positive integer. If p and N = Rp − 1 are both prime, then N is (2; R : −(R + 1)σ(R) : Rσ(R))-perfect.

Corollary 1.3. If R is a k-multiperfect number and p, N = Rp−1 are both prime, then N is (2; k(R + 1) : −kR)-perfect.

A well-known conjecture states that, for any even integer R, the number of primes p < x with Rp−1 also prime is asymptotically equal to cx/(log x)^{2} for some constant c > 0 depending on R, contrary to the above estimate O(x exp(−(2^{−1/3} + o(1))(log x)^{1/3} (log log x)^{2/3})).

2 Notations and Preliminary Lemmas

We denote by P (n), p(n) the largest and smallest prime factor of n respectively. For the positive real number x, let us denote x_{0} = x, x_{i+1} = max{1, log x_{i}} as mentioned in the previous section. We denote by c some positive constant not necessarily same at every occurence. Furthermore, we denote by x, y, z real numbers and we put u = log x/ log y and v = log y/ log z.

Lemma 2.1. Denote by Ψ(x, y) the number of integers n ≤ x divisible by no prime > y. If y > x_{1}^{2}, then we have Ψ(x, y) < x exp(−(1 + o(1))u log u) as x, u tend to infinity.

Proof. This follows from a well-known theorem of de Bruijn [1]. For details on the distribution of integers free from large prime factors, we refer the readers to [8, Chapter III. 5], where a simple proof of the lemma is also given.

Lemma 2.2. Let

s(x, k) = ∑_{p≤x,p≡−1 (mod k)} \frac{1}{p}.  (1)

Uniformly in k and x ≥ e^{2}, we have

s(x, k) ≪ \frac{x_{2}}{φ(k)}.  (2)

Proof. This inequality can be immediately obtained using partial summation and the Brun-Titchmarsh inequality. The complete proof is given in [4, Lemma 2].

Lemma 2.3. Let

S(x) = {n | n ≤ x, p^{a} | n for some p, a with p^{a} > y, a ≥ 2}.

Then we have #S(x) ≪ xy^{−1/2}.

Proof. Let Π(t) be the number of perfect powers below t. It is clear that Π(t) < t^{1/2} + t^{1/3} + … + t^{1/k} < t^{1/2} + ct^{1/3} log t ≪ t^{1/2}, where k = ⌊(log x)/(log 2)⌋.

Let us denote by γ_{p} the smallest integer γ for which p^{γ} > y and γ > 1. Clearly we have #S(x) ≤ x ∑_{p≤x} p^{−γ_{p}}. Since p^{γ_{p}} > y, we have by partial summation

∑_{p≤x} \frac{1}{p^{γ_{p}}} ≤ \frac{Π(x)}{x} − \frac{Π(y)}{y} + ∫_{y}^{x} \frac{Π(t)}{t^{2}}dt ≪ y^{−1/2}.  (3)

This prove the lemma.

Lemma 2.4. If y > z > 2x_{1}^{2} and v > x_{2}, then the number of integers ≤ x divisible by some prime p ≥ y with P (p + 1) < z is at most x exp(−(1 + o(1))v log v).

Proof. The number of such integers at most

∑_{y≤p≤x,P (p+1)<z} \frac{x}{p} ≤ x ∑_{y≤m≤x,P (m+1)<z} \frac{1}{m},  (4)

where p and m respectively run over primes and integers satisfying the described conditions. By partial summation, we find that the last sum is at most

\frac{Ψ(y, z)}{y} + ∫_{y}^{2x} \frac{Ψ(t, z)dt}{t^{2}}.  (5)

Since we have Ψ(t, z)/t < exp(−(1+o(1))v log v) uniformly for t ∈ [y, 2x] by Lemma 2.1, the last sum in (4) can be bounded from above by

exp(−(1 + o(1))v log v) (1 + ∫_{y}^{2x} \frac{dt}{t}) .  (6)

This integral is O(x_{1}) = O(exp v) since, by assumption, x_{2} < v. Thus we obtain

x ∑_{y<m≤x,P (m+1)<z} \frac{1}{m} = x exp(−(1 + o(1))v log v).  (7)

This completes the proof.

3 Proof of Theorem 1.1

Let y, z be real numbers and put u = log x/ log y and v = log y/ log z. We choose y, z later so that x > y > z > x_{1}^{2}, v > x_{2} and u, v, y, z tend to infinity as x does so.

Let

S_{1} = {n | n ≤ x, P (n) ≤ y}  (8)

and

S_{2} = {n | n ≤ x, p^{a} | n for some p, a with p^{a} ≥ z, a ≥ 2}.  (9)

We immediately obtain #S_{1} = O(x exp(−(1 + o(1))u log u)) by Lemma 2.1 and #S_{2} = O(x/z^{1/2}) by Lemma 2.3.

Denote by S_{3} the set of integers n ≤ x not in S_{1}∪S_{2} which can be written in the form mp, where p is a prime ≥ y, m is an integer not divisible by p and (σ(m), p + 1) is divisible by some prime q ≥ z.

Let n be an integer in S_{3} and write n = mp in the above way. Then q | σ(r^{a}) for some prime r dividing m and some integer a with r^{a} || m. Since q ≥ z, we have a = 1 by the assumption n ∉ S_{2}. Hence, m is divisible by some prime r congruent to −1 (mod q).

Since m ≤ x/p, the number of integers n satisfying n = mp, q | (σ(m), p+ 1) for some q ≥ z is at most

∑_{q≥z} ∑_{p≡−1 (mod q)} ∑_{r≡−1 (mod q)} \frac{x}{pr} ≤ ∑_{q≥z} \frac{cxx_{2}^{2}}{q^{2}} ≤ \frac{cxx_{2}^{2}}{z} ,  (10)

by Lemma 2.2. Hence, we have #S_{3} = O(xx_{2}^{2}/z).

Denote by S_{4} the set of integers n ≤ x divisible by some prime p ≥ y with P (p + 1) < z or q^{2} | (p + 1) for some q ≥ z. By Lemma 2.4, the number of integers n ≤ x divisible by some prime p ≥ y with P (p + 1) < z is O(x exp(−(1 + o(1))v log v)). The number of integers n ≤ x divisible by some prime p with q^{2} | (p + 1) for some q ≥ z is at most

x ∑_{q≥z} ∑_{p≡1 (mod q^{2})} \frac{1}{p} ≤ cxx_{2} ∑_{q≥z} \frac{1}{q^{2}} ≤ \frac{cxx_{2}}{zx_{1}^{1/3}} ≪ \frac{x}{z},  (11)

by the assumption that z > x_{1}^{2}.

Combining these estimates yield #S_{4} = O(x(1/z+exp(−(1+o(1))v log v))).

We may assume that at least one of A, C is nonzero since the equation Aσ(σ(N)) + Bσ(N) + CN = 0 does not hold if exactly one of A, B, C is nonzero. Now let us denote by T the set of (2; A : B : C)-perfect numbers n ≤ x belonging to none of S_{i}(i = 1, 2, 3, 4). We assume that n ∈ T. Since n ∉ S_{1} ∪ S_{2}, we have P (n) > y and P (n)^{2} ∤ n. Thus n can be expressed as n = mp, p > y and p ∤ m. Now it follows from n ∉ S_{3} that (σ(m), p + 1) has no prime factor ≥ z. Let T_{m} denote the set of such integers. Moreover, we write p + 1 = N_{1}N_{2} in the way P (N_{1}) < z ≤ p(N_{2}) and divide each of T_{m} into sets T_{m,N_{1}} according to the value of N_{1}. Since n ∉ S_{4}, we have p + 1 is divisible by some prime Q ≥ z exactly once. By the definition of N_{1}, N_{2}, we have N_{2} = N_{3}Q and T_{m,N_{1}} can be covered by sets T_{m,N_{1},N_{3}} according to the value of N_{3}.

We shall show each T_{m,N_{1},N_{3}} consists at most one element. We have σ(n) = σ(m)(p+1) and σ(σ(n)) = σ(M_{1}N_{1})σ(M_{2})σ(N_{2}), where M_{1}, M_{2} are uniquely determined by σ(m) = M_{1}M_{2}, P (M_{1}) < z ≤ p(M_{2}). Furthermore, noting that Q does not divide (p + 1)/Q by the assumption that n ∉ S_{4}, we obtain σ(N_{2}) = σ(N_{3})(Q + 1). Since Aσ(σ(n)) + Bσ(m)(p + 1) + Cmp = 0, we have

Aσ(M_{1}N_{1})σ(M_{2})σ(N_{3})(Q + 1) + (Bσ(m) + Cm)N_{1}N_{3}Q − Cm = 0. (12)

Denoting

C_{1} = Aσ(M_{1}N_{1})σ(M_{2})σ(N_{3}), C_{2} = (Bσ(m) + Cm)N_{1}N_{3}, C_{3} = Cm, (13)

this equation can be written

(C_{1} + C_{2})Q = (C_{3} − C_{1}).  (14)

Since AC ≤ 0, we have C_{1} ≠ C_{3} and therefore Q can be uniquely determined as

Q = \frac{C_{3} − C_{1}}{C_{1} + C_{2}} .  (15)

This is the crucial point where we use the assumption AC ≤ 0. The uniqueness of Q yields that #T_{m,N_{1},N_{3}} ≤ 1 for any m, N_{1}, N_{3}.

By the definition of T_{m,N_{1},N_{3}}, each element of T must belong to T_{m,N_{1},N_{3}} for at least one triple (m, N_{1}, N_{3}). Since N_{1}N_{3} = (p+1)/Q ≤ (x/m+1)/z ≤ 2x/(mz), we have

#T ≤ ∑_{m≤x/y} ∑_{N_{1}} ∑_{N_{3}} 1 ≤ ∑_{m≤x/y} \frac{2x}{mz} ≤ \frac{cxx_{1}}{z} ≤ \frac{cx}{z^{1/2}} .  (16)

Now we conclude that the number of (2; A, B)-perfect numbers ≤ x is at most #S_{1} + #S_{2} + #S_{3} + #S_{4} + #T, which is

O(x(z^{−1/2} + exp(−(1 + o(1))u log u) + exp(−(1 + o(1))v log v))) (17)

by those estimates for #S_{i}’s and #T given above.

In order to search the optimal estimate, we put log z = c_{1}x_{1}^{1/3}x_{2}^{2/3}, log y = c_{2}x_{1}^{2/3}x_{2}^{1/3} and we have u log u = (1 + o(1))c_{2}^{−1}x_{1}^{1/3}x_{2}^{2/3} and v log v = (1 + o(1))(c_{2}/c_{1})x_{1}^{1/3}x_{2}^{2/3}. We see that max{c_{1}/2, c_{2}/c_{1}, 1/c_{2}} ≥ 2^{−1/3} with the equality attained when we choose c_{1} = 2^{2/3}, c_{2} = 2^{1/3}. This choice gives the desired estimate. This completes the proof of Theorem 1.1.

We remark that (2; R : −(R+1)σ(R) : Rσ(R))-perfect numbers given in Theorem 1.2 correspond the case m = N_{1} = 1, C = Aσ(R) = −(B + C)R.

4 Acknowledgments

The author thanks Prof. Florian Luca for his advice on exceptional triples (A, B, C).

References

[1] N. G. de Bruijn, On the number of positive integers ≤ x and free of prime factors > y, Nederl. Akad. Wetensch. Proc. Ser. A 54 (1951), 50–60.

[2] G. L. Cohen and H. J. J. te Riele, Iterating the Sum-of-Divisors Function, Experiment. Math. 5 (1996), 91–100.

[3] I. Kátai and M. V. Subbarao, Some further remarks on the φ and σ functions, Annales Univ. Sci. Budapest. Sect. Comput. 26 (2006), 51–63.

[4] I. Kátai and M. Wijsmuller, On the iterates of the sum of unitary divisors, Acta Math. Hungar. 79(1998), 149–167.

[5] C. Pomerance, On the congruences σ(n) ≡ a (mod n) and n ≡ a (mod φ(n)), Acta Arith. 26 (1975), 265–272.

[6] C. Pomerance, On multiply perfect numbers with a special property, Pacific J. Math. 57 (1975), 511–517.

[7] D. Suryanarayana, Super perfect numbers, Elem. Math. 24 (1969), 16– 17.

[8] G. Tenenbaum, Introduction to analytic and probabilistic number theory, Cambridge University Press, 1995.

Tomohiro Yamada Department of Mathematics Faculty of Science Kyoto University Kyoto, 606-8502 Japan

e-mail: tyamada@math.kyoto-u.ac.jp