betaFeedback

WorksMathematics

On Erdős' last equation

Abstract

For a positive integer n≥2n\ge 2, we look at the number of solutions of the Diophantine equation n(x1+⋯+xn)=x1⋯xn. n(x_1+\cdots+x_n)=x_1\cdots x_n. Denoting by f(n)f(n) this number we show that lim inf⁡n→∞log⁡f(n)/log⁡n=0\liminf_{n\to\infty} \log f(n)/\log n=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⋯xnn(x_1+x_2+\cdots+x_n)=x_1\cdots x_n

1≤x1≤⋯≤xn1 \le x_1 \le\cdots\le x_n, where the xix_i are positive integers? Denote the number of solutions by f(n)f(n); f(n)>nεf(n)>n^\varepsilon for some ε>0\varepsilon>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

lim inf⁡n→∞log⁡f(n)log⁡n=0.\liminf_{n\to\infty}\frac{\log f(n)}{\log n}=0.

It is not hard to show that

lim sup⁡n→∞log⁡f(n)log⁡n≤2.\limsup_{n\to\infty}\frac{\log f(n)}{\log n}\le2.

We believe that

lim sup⁡n→∞log⁡f(n)log⁡n=1,(1)\limsup_{n\to\infty}\frac{\log f(n)}{\log n}=1, \tag*{(1)}

and we will present an heuristic supporting this conjecture. It is easy to show that

lim sup⁡n→∞log⁡f(n)log⁡n≥1.\limsup_{n\to\infty}\frac{\log f(n)}{\log n}\ge1.

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

lim inf⁡p→∞log⁡f(p)log⁡p=0,lim sup⁡p→∞log⁡f(p)log⁡p≤1andlim sup⁡p→∞log⁡f(p)log⁡p≥50259.\liminf_{p\to\infty}\frac{\log f(p)}{\log p}=0,\qquad\limsup_{p\to\infty}\frac{\log f(p)}{\log p}\le1\qquad\text{and}\qquad\limsup_{p\to\infty}\frac{\log f(p)}{\log p}\ge\frac{50}{259}.

In particular, writing for n≥2n\ge2, f(n)=nc(n)f(n)=n^{c(n)}, we have that lim inf⁡n→∞cn=0\liminf_{n\to\infty}c_n=0 and lim sup⁡n→∞cn∈[1,2]\limsup_{n\to\infty}c_n\in[1,2]. Thus, the set of cluster points of {cn}n≥1\{c_n\}_{n\ge1} is in [0,2][0,2]. We leave the question of describing the cluster points for {cn}n≥1\{c_n\}_{n\ge1} as a challenge to the reader.

Preliminary lemmas

We rewrite the equation as

xn=n(x1+⋯+xn−1)x1⋯xn−1−n.x_n=\frac{n(x_1+\cdots+x_{n-1})}{x_1\cdots x_{n-1}-n}.

Since xix_i are positive integers, it follows that m:=x1⋯xn−1−nm:=x_1\cdots x_{n-1}-n is a positive integer. We will find some bounds for mm.

Lemma 2.1. We have m<n(n−1)m<n(n-1) for n≥7n\ge7.

Proof. We have

x1+⋯+xn−1≤(n−1)xn.(2)x_1+\cdots+x_{n-1}\le(n-1)x_n. \tag*{(2)}

In particular, we have

xn=n(x1+⋯+xn−1)m≤n(n−1)xnm,x_n=\frac{n(x_1+\cdots+x_{n-1})}{m}\le\frac{n(n-1)x_n}{m},

which leads to m≤n(n−1)m\le n(n-1). The inequality is strict assuming that (2) is strict, which is the case except when x1=⋯=xn−1=xnx_1=\cdots=x_{n-1}=x_n. In this last case, denoting the common value of the xix_i’s by xx, we get

x=n(n−1)xxn−1−nx=\frac{n(n-1)x}{x^{n-1}-n}

which leads to xn−1=n+n(n−1)=n2x^{n-1}=n+n(n-1)=n^2.

Since x≥2x\ge2, we get n2≥2n−1n^2\ge2^{n-1}, which is false for n≥7n\ge7. Hence, the inequality is strict for n≥7n\ge7. □

We now show a different inequality for mm.

Lemma 2.2. Assume n≥7n\ge7. Let d:=gcd⁡(n,m)d:=\gcd(n,m). If m≥2dnm\ge2dn, then m<8nlog⁡nm<8n\log n.

Proof. Write n:=n1dn:=n_1d, m:=m1dm:=m_1d. Assume m1≥2nm_1\ge2n. Then

xn=n(x1+⋯+xn−1)m=n1(x1+⋯+xn−1)m1.x_n=\frac{n(x_1+\cdots+x_{n-1})}{m}=\frac{n_1(x_1+\cdots+x_{n-1})}{m_1}.

Hence, n1∣xnn_1\mid x_n and

m1(xnn1)=x1+⋯+xn−1.(3)m_1\left(\frac{x_n}{n_1}\right)=x_1+\cdots+x_{n-1}. \tag*{(3)}

We also have x1⋯xn−1=m+nx_1\cdots x_{n-1}=m+n. Let kk be the number of xix_i’s which are larger than 1. Putting j:=n−k−1j:=n-k-1, we have 1=x1=⋯=xj1=x_1=\cdots=x_j and 2≤xj+1≤⋯≤xn−12\le x_{j+1}\le\cdots\le x_{n-1}. Then

x1+⋯+xn−1=n−k−1+xj+1+⋯+xn−1(4)x_1+\cdots+x_{n-1}=n-k-1+x_{j+1}+\cdots+x_{n-1} \tag*{(4)}

is a multiple of m1m_1. This shows that

kxn−1≥xj+1+⋯+xn−1=(x1+⋯+xn−1)−(n−k−1)>m1−n≥m12,kx_{n-1} \ge x_{j+1}+\cdots+x_{n-1}=(x_1+\cdots+x_{n-1})-(n-k-1)>m_1-n\ge\frac{m_1}{2},

so

xn−1≥m12k.x_{n-1}\ge\frac{m_1}{2k}.

On the other hand, we have

mnxn=m1n1xn=x1+⋯+xn−1≤n−k−1+kxn−1≤n−k−1+kxn,\frac{m}{n}x_n=\frac{m_1}{n_1}x_n=x_1+\cdots+x_{n-1}\le n-k-1+kx_{n-1}\le n-k-1+kx_n,

which gives

(mn−k)xn≤n−k−1.(5)\left(\frac{m}{n}-k\right)x_n\le n-k-1. \tag*{(5)}

We have, by Lemma 2.1,

k≤log⁡(m+n)log⁡2≤log⁡(n2)log⁡2<4log⁡n.(6)k\le\frac{\log(m+n)}{\log2}\le\frac{\log(n^2)}{\log2}<4\log n. \tag*{(6)}

If m/n<8log⁡nm/n<8\log n, then we get what we want. Thus, we may assume on the contrary that m/n≥8log⁡n>2km/n\ge8\log n>2k, which together with (5) shows that

m12k≤xn−1≤xn≤2n(n−k−1)m<2nn1m1.\frac{m_1}{2k}\le x_{n-1}\le x_n\le\frac{2n(n-k-1)}{m}<\frac{2nn_1}{m_1}.

This gives

m12<4knn1<16nn1log⁡n.m_1^2<4knn_1<16nn_1\log n.

We thus get that

m1<4nn1log⁡n=4ndlog⁡n,m_1<4\sqrt{nn_1\log n}=\frac{4n}{\sqrt d}\sqrt{\log n},

which gives

m<4ndlog⁡n.(7)m<4n\sqrt d\sqrt{\log n}. \tag*{(7)}

However, we assumed that m≥2dnm\ge2dn. We thus get

2dn<4ndlog⁡nwhich givesd<2log⁡n,2dn<4n\sqrt d\sqrt{\log n}\quad\text{which gives}\quad\sqrt d<2\sqrt{\log n},

which together with (7) gives m<8nlog⁡nm<8n\log n, 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=pn=p is prime. Indeed, in this case, d∈{1,p}d\in\{1,p\}. If d=1d=1, then Lemma 2.2 shows that m<8plog⁡pm<8p\log p, while if d=pd=p, then Lemma 2.1 shows that m=pm1m=pm_1, where m1<p−1m_1<p-1 for p≥7p\ge7.

The proof

For a positive integer nn we write F(n)F(n) for the number of unordered factorizations of nn in factors >1>1 with the convention that F(1)=1F(1)=1. That is, for n>1n>1,

F(n):=#{2≤n1≤⋯≤nk:n1⋯nk=n}.F(n):=\#\{2\le n_1\le\cdots\le n_k:n_1\cdots n_k=n\}.

If we want to emphasize the number of factors in the factorization, we write Fk(n)F_k(n) for the number of factorizations of nn with exactly kk factors. Note that

F(n)=∑k≥1Fk(n).F(n)=\sum_{k\ge1}F_k(n).

In the above sum, Fk(n)F_k(n) is zero once k>Ω(n)k > \Omega(n). We now return to Erdős’ equation for n=pn=p. With the notation from the proof of Lemma 2.2, any solution is of the form

z=p(p−k−1+y1+⋯+yk)m(8)z = \frac{p(p-k-1+y_1+\cdots+y_k)}{m} \tag*{(8)}

where 2≤y1≤⋯≤yk2 \le y_1 \le\cdots\le y_k, y1⋯yk=p+my_1\cdots y_k=p+m. Here, y1,…,yky_1,\ldots,y_k are the integers denoted by xj+1,…,xpx_{j+1},\ldots,x_p in Lemma 2.2 and zz is the integer denoted xpx_p. We write

f(p)≔f1(p)+f2(p),f(p) \coloneqq f_1(p)+f_2(p),

where f1(p)f_1(p) accounts for those solutions for which gcd⁡(m,p)=1\gcd(m,p)=1 and f2(p)f_2(p) accounts for those solutions for which gcd⁡(m,p)=p\gcd(m,p)=p. For a large real number XX we will upper bound

Si(X)≔∑X/2≤p≤Xfi(p)for i=1,2.S_i(X) \coloneqq\sum_{X/2\le p\le X} f_i(p) \quad\text{for } i=1,2.

We will show that

Si(X)=X1+o(1)as X→∞.S_i(X)=X^{1+o(1)} \quad\text{as } X\to\infty.

This shows that

∑X/2≤p≤Xf(p)=S1(X)+S2(X)=X1+o(1)as X→∞.\sum_{X/2\le p\le X} f(p)=S_1(X)+S_2(X)=X^{1+o(1)} \quad\text{as } X\to\infty.

Since the interval [X/2,X][X/2,X] contains π(X)−π(X/2)=X1+o(1)\pi(X)-\pi(X/2)=X^{1+o(1)} primes, it follows that

min⁡X/2≤p≤Xf(p)≤Xo(1)=po(1)as X→∞,\min_{X/2\le p\le X} f(p)\le X^{o(1)}=p^{o(1)} \quad\text{as } X\to\infty,

which proves our theorem. It also shows that lim sup⁡p→∞log⁡f(p)/log⁡p≤1\limsup_{p\to\infty}\log f(p)/\log p\le1. Let’s get to work.

Estimating S1(X)S_1(X)

In this case, if p∈[X/2,X]p\in[X/2,X] and X≥14X\ge14, we then have m≤8plog⁡p≤8Xlog⁡Xm\le8p\log p\le8X\log X by Lemma 2.2. Thus, p+m≤p+8plog⁡p≤9Xlog⁡Xp+m\le p+8p\log p\le9X\log X for X≥14X\ge14. Fix kk, which is the number of terms larger than 1 in the factorization y1⋯yk=p+my_1\cdots y_k=p+m. Certainly, k≤Ω(p+m)=O(log⁡X)k\le\Omega(p+m)=O(\log X), where Ω(.)\Omega(.) counts the total number of prime factors with multiplicity. The number of such factorizations is Fk(p+m)F_k(p+m). In equation (8), we have that pp divides zz, so z=pz1z=pz_1 and

z1=p−k−1+y1+⋯+ykm=(p+m)−k−1+y1+⋯+ykm−1(9)z_1=\frac{p-k-1+y_1+\cdots+y_k}{m}=\frac{(p+m)-k-1+y_1+\cdots+y_k}{m}-1 \tag*{(9)}

so mm is a divisor of y1⋯yk−k−1+y1+⋯+yky_1\cdots y_k-k-1+y_1+\cdots+y_k. Note that this last number is positive as k≥1k\ge1 since y1⋯yk=p+m>1y_1\cdots y_k=p+m>1. This suggests that any pair (p,x1,…,xp)(p,x_1,\ldots,x_p) of solutions of the type participating in S1(X)S_1(X) of Erdős’ equations arises from the following parameters:

  1. A positive integer kk of size O(log⁡X)O(\log X).

  2. A positive integer ℓ(:=p+m)\ell(:=p+m) which is at most O(Xlog⁡X)O(X\log X).

  3. An unordered factorization y1⋯yk=ℓy_1\cdots y_k=\ell with kk factors larger than 1 of ℓ\ell.

  4. A proper divisor mm of the positive integer y1⋯yk−k−1+y1+⋯+yky_1\cdots y_k-k-1+y_1+\cdots+y_k.

The condition in (iv) that mm is a “proper” divisor is meant to insure that the number z1z_1 arising in equation (9) is not zero. Indeed, once (i)–(iv) are known, then p=ℓ−mp=\ell-m, and the solution is x1=⋯=xj=1x_1=\cdots=x_j=1, (xj+1,…,xp−1)=(y1,…,yk)(x_{j+1},\ldots,x_{p-1})=(y_1,\ldots,y_k) and xp=pz1x_p=pz_1, where z1z_1 is shown in (9). Note that this might not give rise to a genuine solution since the pp arising from this process is not necessarily prime. This shows that

S1(X)≪∑ℓ≤9Xlog⁡X∑k≤Ω(ℓ)∑2≤y1≤⋯≤yky1⋯yk=ℓτ(y1⋯yk−k−1+y1+⋯+yk).S_1(X) \ll\sum_{\ell\le9X \log X} \sum_{k \le\Omega(\ell)} \sum_{\substack{2 \le y_1 \le\cdots\le y_k \\ y_1 \cdots y_k = \ell}} \tau(y_1 \cdots y_k-k-1+y_1+\cdots+y_k).

where τ(⋅)\tau(\cdot) 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ℓ≤18Xlog⁡X\ell+ky_k \le\ell+k\ell/2^{k-1} \le2\ell\le18X\log X so each of these numbers is Xo(1)X^{o(1)} as X→∞X \to\infty and the number of them is Fk(ℓ)F_k(\ell). Thus,

S1(X)≤Xo(1)∑ℓ≤9Xlog⁡XF(ℓ).(10)S_1(X) \le X^{o(1)} \sum_{\ell\le9X\log X} F(\ell). \tag*{(10)}

By a well-known result of Szekeres and Turán [4], we have

1t∑n≤tF(n)=(1+o(1))exp⁡(2log⁡t)2π(log⁡t)3/4(11)\frac{1}{t}\sum_{n \le t}F(n)=(1+o(1))\frac{\exp(2\sqrt{\log t})}{2\sqrt{\pi}(\log t)^{3/4}} \tag*{(11)}

as t→∞t \to\infty.

Inserting (11) into (10) yields

S1(X)≪X1+o(1)(log⁡X)exp⁡(2log⁡(9Xlog⁡X))2π(log⁡(9Xlog⁡X))3/4=X1+o(1)S_1(X) \ll X^{1+o(1)}(\log X)\frac{\exp(2\sqrt{\log(9X\log X)})}{2\sqrt{\pi}(\log(9X\log X))^{3/4}}=X^{1+o(1)}

as X→∞X \to\infty, as desired.

Estimating S2(X)S_2(X)

We prove that f2(p)=3f_2(p)=3 for p≥3p \ge3. It is enough to verify the following lemma.

Lemma 3.1. Let pp be an odd prime number. The solutions (x1,…,xp)(x_1,\ldots,x_p) of the equation

p(x1+x2+⋯+xp)=x1x2⋯xpwithp∣x1x2⋯xp−1p(x_1+x_2+\cdots+x_p)=x_1x_2\cdots x_p \qquad\text{with} \qquad p \mid x_1x_2\cdots x_{p-1}

are (1,1,…,1,2p,3p−2)(1,1,\ldots,1,2p,3p-2), (1,1,…,1,2,p,2p−1)(1,1,\ldots,1,2,p,2p-1) and (1,1,…,1,3,p,p)(1,1,\ldots,1,3,p,p).

Proof. First we show that p∤x1x2⋯xp−2p \nmid x_1x_2\cdots x_{p-2} for p≥5p \ge5. Let us suppose on the contrary that p∣x1x2⋯xp−2p \mid x_1x_2\cdots x_{p-2}. Then p≤xp−2≤xp−1≤xpp \le x_{p-2} \le x_{p-1} \le x_p and x1+x2+⋯+xp<pxpx_1+x_2+\cdots+x_p < px_p. We then have

p2xp≤x1x2⋯xp−2xp−1xp=p(x1+x2+⋯+xp)<p2xp,p^2x_p \le x_1x_2\cdots x_{p-2}x_{p-1}x_p=p(x_1+x_2+\cdots+x_p)<p^2x_p,

a contradiction. So, we may assume that xp−1=kpx_{p-1}=kp for some positive integer kk. We verify that x1x2⋯xp−2≤3x_1x_2\cdots x_{p-2}\le3. Assume that A=x1x2⋯xp−2≥4A=x_1x_2\cdots x_{p-2}\ge4. Since

p(x1+x2+⋯+xp−2+kp+xp)=x1x2⋯xp−2kpxpp(x_1+x_2+\cdots+x_{p-2}+kp+x_p)=x_1x_2\cdots x_{p-2}kpx_p

then

x1+x2+⋯+xp−2+kp=(kA−1)xp.x_1+x_2+\cdots+x_{p-2}+kp=(kA-1)x_p.

Since

x1+x2+⋯+xp−2≤p−3+x1x2⋯xp−2=p−3+A,x_1+x_2+\cdots+x_{p-2}\le p-3+x_1x_2\cdots x_{p-2}=p-3+A,

we get

(kA−1)xp≤p−3+A+kp,that isxp≤p−3+A+kpkA−1.(kA-1)x_p\le p-3+A+kp,\qquad\text{that is}\qquad x_p\le\frac{p-3+A+kp}{kA-1}.

We get a contradiction if we show that

p−3+A+kpkA−1<p.\frac{p-3+A+kp}{kA-1}<p.

This is equivalent to A−3<p(k(A−1)−2)A-3<p(k(A-1)-2). This last inequality is equivalent to

A−3<pk(A−1)−2por2(p−1)<(A−1)(pk−1).A-3<pk(A-1)-2p \quad\text{or}\quad2(p-1)<(A-1)(pk-1).

The last inequality is equivalent to

A−1>2(p−1)pk−1,A-1>\frac{2(p-1)}{pk-1},

which holds for A≥4A\geq4, p≥2p\geq2, k≥1k\geq1. This contradiction shows that A∈{1,2,3}A\in\{1,2,3\}.

For A=1A=1, x1=x2=⋯=xp−2=1x_1=x_2=\cdots=x_{p-2}=1, and p(p−2+xp−1+xp)=xp−1xpp(p-2+x_{p-1}+x_p)=x_{p-1}x_p that is (xp−p)(xp−1−p)=p(2p−2)(x_p-p)(x_{p-1}-p)=p(2p-2), which yields the solution

(1,1,…,1,2p,3p−2).(1,1,\ldots,1,2p,3p-2).

For A=2A=2, x1=x2=⋯=xp−3=1x_1=x_2=\cdots=x_{p-3}=1, xp−2=2x_{p-2}=2 and p(p−1+xp−1+xp)=2xp−1xpp(p-1+x_{p-1}+x_p)=2x_{p-1}x_p that is (2xp−p)(2xp−1−p)=p(3p−2)(2x_p-p)(2x_{p-1}-p)=p(3p-2), which yields the solution

(1,1,…,1,2,p,2p−1).(1,1,\ldots,1,2,p,2p-1).

For A=3A=3, x1=x2=⋯=xp−3=1x_1=x_2=\cdots=x_{p-3}=1, xp−2=3x_{p-2}=3 and p(p+xp−1+xp)=3xp−1xpp(p+x_{p-1}+x_p)=3x_{p-1}x_p that is (3xp−p)(3xp−1−p)=4p2(3x_p-p)(3x_{p-1}-p)=4p^2, which yields the solution

(1,1,…,1,3,p,p).(1,1,\ldots,1,3,p,p).

By Lemma 3.1

S2(X)=∑X/2≤p≤Xf2(p)=∑X/2≤p≤X3≤3X≤X1+o(1)as X→∞,S_2(X)=\sum_{X/2\leq p\leq X}f_2(p)=\sum_{X/2\leq p\leq X}3\leq3X\leq X^{1+o(1)}\quad\text{as }X\to\infty,

as desired.

Comments

In this section, we justify some of the claims made in the introduction about the lim sup and lim inf of log⁡f(n)/log⁡n\log f(n)/\log n. To get an upper bound, we may proceed in the same way as in the proof of the theorem. Namely, let k≥1k\geq1 and y1⋯yk=n+my_1\cdots y_k=n+m be a factorization of ℓ=n+m\ell=n+m with kk factors larger than 1. Putting n∈[X/2,X]n\in[X/2,X] for X≥14X\geq14, we have n+m≤X2n+m\leq X^2 so k≤Ω(n+m)≤4log⁡Xk\leq\Omega(n+m)\leq4\log X. Next

z=n(n−k−1+∑i=1kyi)m=n((n+m)−k−1+∑i=1kyim−1).z=\frac{n(n-k-1+\sum_{i=1}^{k}y_i)}{m} =n\left(\frac{(n+m)-k-1+\sum_{i=1}^{k}y_i}{m}-1\right).

We have that m=dm1m=dm_1, where m1m_1 is a proper divisor of y1⋯yk−k−1+y1+⋯+yky_1\cdots y_k-k-1+y_1+\cdots+y_k, and dd is a divisor of both nn and mm; hence, of ℓ=n+m=y1⋯yk\ell=n+m=y_1\cdots y_k. Thus,

∑X/2≤n≤Xf(n)≪∑ℓ≤X2∑k≤4log⁡X∑2≤y1≤⋯≤yky1⋯yk=ℓτ(ℓ)τ(ℓ−k−1+y1+⋯+yk).\sum_{X/2\leq n\leq X}f(n)\ll \sum_{\ell\leq X^2}\sum_{k\leq4\log X} \sum_{\substack{2\leq y_1\leq\cdots\leq y_k\\y_1\cdots y_k=\ell}} \tau(\ell)\tau(\ell-k-1+y_1+\cdots+y_k).

Each of the terms of the inner summation is of size Xo(1)X^{o(1)} and the number of such terms is Fk(ℓ)F_k(\ell). Thus,

∑X/2≤n≤Xf(n)≪∑ℓ≤X2∑k≤4log⁡XFk(ℓ)≪X2+o(1),\sum_{X/2\leq n\leq X}f(n)\ll \sum_{\ell\leq X^2}\sum_{k\leq4\log X}F_k(\ell)\ll X^{2+o(1)},

This shows that f(n)≤n2+o(1)f(n)\leq n^{2+o(1)} as n→∞n\to\infty. This is perhaps not the right order since the range for mm seems to be too high. As we said, we believe f(n)≤n1+o(1)f(n)\leq n^{1+o(1)} holds as n→∞n\to\infty. Here is an heuristic. As we saw, any solution of Erdős’ equation is intimately related to unordered factorizations of the number ℓ:=n+m\ell:= n + m. After such a factorization y1⋯yk=n+my_1 \cdots y_k = n + m with kk factors larger than 1 is chosen, the quantity

n(n−k−1+∑i=1kyi)m\frac{n(n-k-1+\sum_{i=1}^{k}y_i)}{m}

needs to be an integer. Assuming that the probability that n(n−k−1+∑i=1kyi)n(n-k-1+\sum_{i=1}^{k}y_i) to be a multiple of mm to be 1/m1/m, it would seem that an upper bound on f(n)f(n) should be

≪∑m<n(n−1)F(n+m)m.\ll\sum_{m<n(n-1)} \frac{F(n+m)}{m}.

We split this sum in two ranges, namely m≤nm \le n and m>nm > n. In the lower range, we ignore the denominator mm and say that the above sum is bounded by

∑m≤nF(n+m)≤∑ℓ≤2nF(ℓ)≤n1+o(1)as n→∞.\sum_{m\le n} F(n+m) \le\sum_{\ell\le2n} F(\ell) \le n^{1+o(1)} \qquad\text{as } n\to\infty.

In the larger range m>nm > n, we have that m>(n+m)/2m > (n+m)/2, so the sum in this range is bounded by

≪∑n<m≤n2F(n+m)n+m≪∑ℓ≤n2F(ℓ)ℓ≪exp⁡(22log⁡ℓ)(log⁡ℓ)1/4,\ll\sum_{n<m\le n^2}\frac{F(n+m)}{n+m} \ll\sum_{\ell\le n^2}\frac{F(\ell)}{\ell} \ll\exp(2\sqrt{2\log\ell})(\log\ell)^{1/4},

where the last estimate follows by the Abel summation formula applied to (11). The right-hand side above is no(1)n^{o(1)} as n→∞n\to\infty. This seems to justify the claim that perhaps f(n)≤n1+o(1)f(n)\le n^{1+o(1)} as nn tends to infinity. To see why f(n)≥n1+o(1)f(n)\ge n^{1+o(1)} holds for infinitely many nn, we just take m=1m=1. Then

z:=n(n−k−1+∑i=1kyi)z:=n\left(n-k-1+\sum_{i=1}^{k}y_i\right)

and we see right away that indeed z:=xnz:=x_n is an integer and larger than any xix_i for i=1,…,n−1i=1,\ldots,n-1. Thus, f(n)≥F(n+1)f(n)\ge F(n+1). Now choose n+1n+1 to be a highly-factorable integer in the terminology of [1], namely a positive integer mm such that F(ℓ)<F(m)F(\ell)<F(m) for all ℓ<m\ell<m. The paper [1] shows that for such numbers, F(m)=mL(m)−1+o(1)F(m)=mL(m)^{-1+o(1)} as m→∞m\to\infty, where

L(m):=exp⁡(log⁡mlog⁡log⁡log⁡mlog⁡log⁡m)=mo(1)as m→∞.L(m):=\exp\left(\frac{\log m\log\log\log m}{\log\log m}\right)=m^{o(1)} \qquad\text{as }m\to\infty.

In particular, f(n)≥n1+o(1)f(n)\ge n^{1+o(1)} as nn tends to infinity in such a way that n+1n+1 is highly-factorable. Finally, let us look at lim sup⁡p→∞log⁡f(p)/log⁡p\limsup_{p\to\infty}\log f(p)/\log p. If there were infinitely many primes pp such that p+1p+1 is highly-factorable, then we would have that f(p)≥p1+o(1)f(p)\ge p^{1+o(1)} holds as pp 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 XX be large and choose a highly-factorable number mm. By Linnik’s result, there is a prime pp of size O(mL)O(m^L) such that m∣p+1m\mid p+1 where LL is Linnik’s constant. This shows that f(p)≥F(p+1)≥F(m)=m1/L+o(1)f(p)\ge F(p+1)\ge F(m)=m^{1/L+o(1)}. The best (smallest) exponent LL is due to Xylouris [6] and is <5<5; hence, 1/L>1/5=0.21/L>1/5=0.2. To justify the details, we first take y:=C1X1/Ly:=C_1X^{1/L}, where C1C_1 is an appropriate positive constant to guarantee that if m≤ym\le y is any positive integer then there is a prime p≤Xp\le X such that p≡−1(modm)p\equiv-1\pmod m, and next we use the fact that there is a highly-factorable number in [y/2,y][y/2,y] (see (2) on page 25 in [1]). This justifies that f(p)≥p0.2f(p) \ge p^{0.2} holds as pp 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

Email address: [email protected]

Institute of Mathematics, University of Debrecen, P. O. Box 400, H-4002 Debrecen, Hungary

Email address: [email protected]

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

Email address: [email protected]

References

  1. [1]E. R. Canfield, P. Erdős, and C. Pomerance, “On a problem of Oppenheim concerning “Factorization Numerorum””, J. Number Theory 17 (1983), 1–28.
  2. [2]R. K. Guy, Unsolved Problems in Number Theory, 3rd ed., New York: Springer–Verlag, 2004.
  3. [3]F. Luca, I. Pink, and C. Sándor, “On the largest value of the solutions of Erdős’ last equation”, Internat. J. Number Theory, to appear.
  4. [4]G. Szekeres and P. Turán, “Über das zweite Hauptproblem der ”Factorisatio Numerorum””, Acta Litt. Sci. Szeged 6 (1933), 143–154.
  5. [5]P. Shiu, “On Erdős’s last equation”, Amer. Math. Monthly 126 (2019), no. 9, 802–808.DOI
  6. [6]T. Xylouris, “Linnik’s constant is less than 5”, Chebyshevskii Sb 19 (2018), 80–94.

Paper details

vlnc:W_xjcfaxu2
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 3

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents