For a positive integer n≥2, we look at the number of solutions of the Diophantine equation n(x1+⋯+xn)=x1⋯xn. Denoting by f(n) this number we show that liminfn→∞logf(n)/logn=0.
Introduction
On 19 August 1996, a month before his death, Paul Erdős formulated the following question in a letter to Richard Guy [2]: “Do you know anything about the equation
n(x1+x2+⋯+xn)=x1⋯xn
1≤x1≤⋯≤xn, where the xi are positive integers? Denote the number of solutions by f(n); f(n)>nε for some ε>0 seems to be true? . . . ”.
This equation has been called Erdős’ last equation. It has been studied in a couple of papers (see [3] and [5]). Yet, none of these papers addressed Erdős’ claim. In this paper, we show that the answer to Erdős’ question is in the negative. We have the following result.
Theorem 1.1.We have
n→∞liminflognlogf(n)=0.
It is not hard to show that
n→∞limsuplognlogf(n)≤2.
We believe that
n→∞limsuplognlogf(n)=1,(1)
and we will present an heuristic supporting this conjecture. It is easy to show that
n→∞limsuplognlogf(n)≥1.
and we will indicate a quick proof of this, so for (1) one only needs to show that the limsup is at most 1. Restricting to primes, we prove that
In particular, writing for n≥2, f(n)=nc(n), we have that liminfn→∞cn=0 and limsupn→∞cn∈[1,2]. Thus, the set of cluster points of {cn}n≥1 is in [0,2]. We leave the question of describing the cluster points for {cn}n≥1 as a challenge to the reader.
Preliminary lemmas
We rewrite the equation as
xn=x1⋯xn−1−nn(x1+⋯+xn−1).
Since xi are positive integers, it follows that m:=x1⋯xn−1−n is a positive integer. We will find some bounds for m.
Lemma 2.1. We have m<n(n−1) for n≥7.
Proof. We have
x1+⋯+xn−1≤(n−1)xn.(2)
In particular, we have
xn=mn(x1+⋯+xn−1)≤mn(n−1)xn,
which leads to m≤n(n−1). The inequality is strict assuming that (2) is strict, which is the case except when x1=⋯=xn−1=xn. In this last case, denoting the common value of the xi’s by x, we get
x=xn−1−nn(n−1)x
which leads to xn−1=n+n(n−1)=n2.
Since x≥2, we get n2≥2n−1, which is false for n≥7. Hence, the inequality is strict for n≥7. □
We now show a different inequality for m.
Lemma 2.2. Assume n≥7. Let d:=gcd(n,m). If m≥2dn, then m<8nlogn.
Proof. Write n:=n1d, m:=m1d. Assume m1≥2n. Then
xn=mn(x1+⋯+xn−1)=m1n1(x1+⋯+xn−1).
Hence, n1∣xn and
m1(n1xn)=x1+⋯+xn−1.(3)
We also have x1⋯xn−1=m+n. Let k be the number of xi’s which are larger than 1. Putting j:=n−k−1, we have 1=x1=⋯=xj and 2≤xj+1≤⋯≤xn−1. Then
If m/n<8logn, then we get what we want. Thus, we may assume on the contrary that m/n≥8logn>2k, which together with (5) shows that
2km1≤xn−1≤xn≤m2n(n−k−1)<m12nn1.
This gives
m12<4knn1<16nn1logn.
We thus get that
m1<4nn1logn=d4nlogn,
which gives
m<4ndlogn.(7)
However, we assumed that m≥2dn. We thus get
2dn<4ndlognwhich givesd<2logn,
which together with (7) gives m<8nlogn, which is what we wanted. □
The combination of Lemma 2.1 and 2.2 gives good information about the shape of the solutions to Erdős’ equation when n=p is prime. Indeed, in this case, d∈{1,p}. If d=1, then Lemma 2.2 shows that m<8plogp, while if d=p, then Lemma 2.1 shows that m=pm1, where m1<p−1 for p≥7.
The proof
For a positive integer n we write F(n) for the number of unordered factorizations of n in factors >1 with the convention that F(1)=1. That is, for n>1,
F(n):=#{2≤n1≤⋯≤nk:n1⋯nk=n}.
If we want to emphasize the number of factors in the factorization, we write Fk(n) for the number of factorizations of n with exactly k factors. Note that
F(n)=k≥1∑Fk(n).
In the above sum, Fk(n) is zero once k>Ω(n). We now return to Erdős’ equation for n=p. With the notation from the proof of Lemma 2.2, any solution is of the form
z=mp(p−k−1+y1+⋯+yk)(8)
where 2≤y1≤⋯≤yk, y1⋯yk=p+m. Here, y1,…,yk are the integers denoted by xj+1,…,xp in Lemma 2.2 and z is the integer denoted xp. We write
f(p):=f1(p)+f2(p),
where f1(p) accounts for those solutions for which gcd(m,p)=1 and f2(p) accounts for those solutions for which gcd(m,p)=p. For a large real number X we will upper bound
Si(X):=X/2≤p≤X∑fi(p)for i=1,2.
We will show that
Si(X)=X1+o(1)as X→∞.
This shows that
X/2≤p≤X∑f(p)=S1(X)+S2(X)=X1+o(1)as X→∞.
Since the interval [X/2,X] contains π(X)−π(X/2)=X1+o(1) primes, it follows that
X/2≤p≤Xminf(p)≤Xo(1)=po(1)as X→∞,
which proves our theorem. It also shows that limsupp→∞logf(p)/logp≤1. Let’s get to work.
Estimating S1(X)
In this case, if p∈[X/2,X] and X≥14, we then have m≤8plogp≤8XlogX by Lemma 2.2. Thus, p+m≤p+8plogp≤9XlogX for X≥14. Fix k, which is the number of terms larger than 1 in the factorization y1⋯yk=p+m. Certainly, k≤Ω(p+m)=O(logX), where Ω(.) counts the total number of prime factors with multiplicity. The number of such factorizations is Fk(p+m). In equation (8), we have that p divides z, so z=pz1 and
z1=mp−k−1+y1+⋯+yk=m(p+m)−k−1+y1+⋯+yk−1(9)
so m is a divisor of y1⋯yk−k−1+y1+⋯+yk. Note that this last number is positive as k≥1 since y1⋯yk=p+m>1. This suggests that any pair (p,x1,…,xp) of solutions of the type participating in S1(X) of Erdős’ equations arises from the following parameters:
A positive integer k of size O(logX).
A positive integer ℓ(:=p+m) which is at most O(XlogX).
An unordered factorization y1⋯yk=ℓ with k factors larger than 1 of ℓ.
A proper divisor m of the positive integer y1⋯yk−k−1+y1+⋯+yk.
The condition in (iv) that m is a “proper” divisor is meant to insure that the number z1 arising in equation (9) is not zero. Indeed, once (i)–(iv) are known, then p=ℓ−m, and the solution is x1=⋯=xj=1, (xj+1,…,xp−1)=(y1,…,yk) and xp=pz1, where z1 is shown in (9). Note that this might not give rise to a genuine solution since the p arising from this process is not necessarily prime. This shows that
where τ(⋅) counts the number of positive divisors. In the inner sum, all numbers whose number of divisors is being calculated are at most ℓ+kyk≤ℓ+kℓ/2k−1≤2ℓ≤18XlogX so each of these numbers is Xo(1) as X→∞ and the number of them is Fk(ℓ). Thus,
S1(X)≤Xo(1)ℓ≤9XlogX∑F(ℓ).(10)
By a well-known result of Szekeres and Turán [4], we have
We prove that f2(p)=3 for p≥3. It is enough to verify the following lemma.
Lemma 3.1. Let p be an odd prime number. The solutions (x1,…,xp) of the equation
p(x1+x2+⋯+xp)=x1x2⋯xpwithp∣x1x2⋯xp−1
are (1,1,…,1,2p,3p−2), (1,1,…,1,2,p,2p−1) and (1,1,…,1,3,p,p).
Proof. First we show that p∤x1x2⋯xp−2 for p≥5. Let us suppose on the contrary that p∣x1x2⋯xp−2. Then p≤xp−2≤xp−1≤xp and x1+x2+⋯+xp<pxp. We then have
In this section, we justify some of the claims made in the introduction about the lim sup and lim inf of logf(n)/logn. To get an upper bound, we may proceed in the same way as in the proof of the theorem. Namely, let k≥1 and y1⋯yk=n+m be a factorization of ℓ=n+m with k factors larger than 1. Putting n∈[X/2,X] for X≥14, we have n+m≤X2 so k≤Ω(n+m)≤4logX. Next
Each of the terms of the inner summation is of size Xo(1) and the number of such terms is Fk(ℓ). Thus,
X/2≤n≤X∑f(n)≪ℓ≤X2∑k≤4logX∑Fk(ℓ)≪X2+o(1),
This shows that f(n)≤n2+o(1) as n→∞. This is perhaps not the right order since the range for m seems to be too high. As we said, we believe f(n)≤n1+o(1) holds as n→∞. Here is an heuristic. As we saw, any solution of Erdős’ equation is intimately related to unordered factorizations of the number ℓ:=n+m. After such a factorization y1⋯yk=n+m with k factors larger than 1 is chosen, the quantity
mn(n−k−1+∑i=1kyi)
needs to be an integer. Assuming that the probability that n(n−k−1+∑i=1kyi) to be a multiple of m to be 1/m, it would seem that an upper bound on f(n) should be
≪m<n(n−1)∑mF(n+m).
We split this sum in two ranges, namely m≤n and m>n. In the lower range, we ignore the denominator m and say that the above sum is bounded by
m≤n∑F(n+m)≤ℓ≤2n∑F(ℓ)≤n1+o(1)as n→∞.
In the larger range m>n, we have that m>(n+m)/2, so the sum in this range is bounded by
where the last estimate follows by the Abel summation formula applied to (11). The right-hand side above is no(1) as n→∞. This seems to justify the claim that perhaps f(n)≤n1+o(1) as n tends to infinity. To see why f(n)≥n1+o(1) holds for infinitely many n, we just take m=1. Then
z:=n(n−k−1+i=1∑kyi)
and we see right away that indeed z:=xn is an integer and larger than any xi for i=1,…,n−1. Thus, f(n)≥F(n+1). Now choose n+1 to be a highly-factorable integer in the terminology of [1], namely a positive integer m such that F(ℓ)<F(m) for all ℓ<m. The paper [1] shows that for such numbers, F(m)=mL(m)−1+o(1) as m→∞, where
L(m):=exp(loglogmlogmlogloglogm)=mo(1)as m→∞.
In particular, f(n)≥n1+o(1) as n tends to infinity in such a way that n+1 is highly-factorable. Finally, let us look at limsupp→∞logf(p)/logp. If there were infinitely many primes p such that p+1 is highly-factorable, then we would have that f(p)≥p1+o(1) holds as p tends to infinity through such numbers. But this is not known. However, we can use known results on Linnik’s problem which asks for the first (smallest) prime in an arithmetic progression. For this, let X be large and choose a highly-factorable number m. By Linnik’s result, there is a prime p of size O(mL) such that m∣p+1 where L is Linnik’s constant. This shows that f(p)≥F(p+1)≥F(m)=m1/L+o(1). The best (smallest) exponent L is due to Xylouris [6] and is <5; hence, 1/L>1/5=0.2. To justify the details, we first take y:=C1X1/L, where C1 is an appropriate positive constant to guarantee that if m≤y is any positive integer then there is a prime p≤X such that p≡−1(modm), and next we use the fact that there is a highly-factorable number in [y/2,y] (see (2) on page 25 in [1]). This justifies that f(p)≥p0.2 holds as p tends to infinity through some infinite subset of all the primes.
Mathematics Division, Stellenbosch University, Stellenbosch, South Africa
Max Planck Institute for Software Systems, Saarbrücken, Germany
Department of Computer Science, Oxford University, UK
Department of Stochastics, Institute of Mathematics, Budapest University of Technology and Economics, Műegyetem rkp. 3., H-1111 Budapest, Hungary; HUN-REN Alfréd Rényi Institute of Mathematics, Reáltanoda utca 13–15., H-1053 Budapest, Hungary
MTA–HUN-REN RI Lendület “Momentum” Arithmetic Combinatorics Research Group, Reáltanoda utca 13–15., H-1053 Budapest, Hungary