# Comptes Rendus
Mathématique

Yong-Gao Chen and Yuchen Ding

On a conjecture of Erdős

Volume 360 (2022), p. 971-974

https://doi.org/10.5802/crmath.345

<figure><img src="image_1.png" /></figure>

This article is licensed under the

CREATIVE COMMONS ATTRIBUTION 4.0 INTERNATIONAL LICENSE.

http://creativecommons.org/licenses/by/4.0/

<figure><img src="image_2.png" /></figure>

Les Comptes Rendus. Mathématique sont membres du
Centre Mersenne pour l'édition scientifique ouverte

www.centre-mersenne.org

e-ISSN : 1778-3569
<figure><img src="image_3.png" /></figure>

Number theory / Théorie des nombres

# On a conjecture of Erdős

Yong-Gao Chen<sup>a</sup> and Yuchen Ding<sup>* b</sup>

<sup>a</sup> School of Mathematical Sciences, Nanjing Normal University, Nanjing 210023,
People's Republic of China

<sup>b</sup> School of Mathematical Sciences, Yangzhou University, Yangzhou 225002, People's
Republic of China

E-mails: ygchen@njnu.edu.cn, ycding@yzu.edu.cn

**Abstract.** In this note, we confirm an old conjecture of Erdős.

**Mathematical subject classification (2010).** 11A41, 11A67.

**Funding.** The first author was supported by the National Natural Science Foundation of China, Grant No. 12171243. The second author was supported by the Natural Science Foundation of Jiangsu Province of China, Grant No. BK20210784. He was also supported by the foundations of the projects "Jiangsu Provincial Double-Innovation Doctor Program", Grant No. JSSCBS20211023 and "Golden Phoenix of the Green City-Yang Zhou" to excellent PhD, Grant No. YZLYJF2020PHD051.

Manuscript received 24 January 2022, revised 10 February 2022, accepted 11 February 2022.

## 1. Introduction

Let $\mathcal{P}$ denote the set of all primes. In 1950, Erdős [5] made the following anecdotal conjecture:

**Conjecture 1 (Erdős Conjecture).** Let $c$ be any constant and $x$ sufficiently large,

$$a_1 < a_2 < \cdots < a_t \le x, t > \log x.$$

Then there exists an integer $n$ so that the number of solutions of $n = p + a_i$ ($p \in \mathcal{P}$, $1 \le i \le t$) is greater than $c$.

Erdős [5] himself proved this conjecture for the case $a_i = 2^i$, which gives an affirmative answer to a question of Turán. In a former note [3], the second author proved this conjecture for the case $a_i | a_{i+1}$ with its quantitative form, which is a slight generalization of Erdős' result. In a subsequent note, the second author and Zhou [4] proved the conjecture for the case $a_i = 2^{p_i}$, where $p_i$ is the $i$-th prime. This case was conjectured by the first author [1] years ago. Shortly after, the authors of the present note recognized that the complete proof of Erdős' conjecture actually follows directly from a new achievement of the distributions of the primes established by Maynard-Tao [7, 8]. We keep record here as the closure of this longstanding conjecture.

<footnote>* Corresponding author.</footnote>
In this note, the following general results are proved. The Erdős Conjecture follows from Corollary 3.

**Theorem 2.** For any $\ell$ distinct integers $a_1, \dots, a_\ell$, there are infinitely many positive integers $n$ such that the number of solutions of $n = p + a_i$ ($p \in \mathcal{P}, 1 \le i \le \ell$) is greater than

$$ \frac{1}{8} \log \ell - 1.6. $$

From Theorem 2, we immediately have the following corollaries:

**Corollary 3.** Let $x \ge 2$ and

$$ a_1 < a_2 < \dots < a_t \le x, \ t > \log x. $$

Then there exist infinitely many integers $n$ so that the number of solutions of $n = p + a_i$ ($p \in \mathcal{P}, 1 \le i \le t$) is greater than

$$ \frac{1}{8} \log \log x - 1.6. $$

**Corollary 4.** Let $\mathcal{A} = \{a_i\}_{i=1}^\infty$ be an infinite set of integers and let

$$ f_{\mathcal{A}}(n) = \#\{(p, a) : n = p + a, p \in \mathcal{P}, a \in \mathcal{A}\}, $$

then

$$ \limsup_{n \to +\infty} f_{\mathcal{A}}(n) = +\infty. $$

## 2. Proofs

A set $\{b_1, \dots, b_k\}$ is called an admissible set if there is no a fixed integer $d > 1$ such that $d \mid (n+b_1)\cdots(n+b_k)$ for all integers $n$. It is equivalent that for any prime $p$, $\{b_1, \dots, b_k\}$ modulo $p$ occupies at most $p-1$ residues. We begin with the following deep result for the distribution of the primes due to Maynard-Tao ([8, Theorem 16]). We will use the following quantitative result which was given by Granville [6] basing on Maynard [7].

**Lemma 5.** [6, Theorem 6.2] For any given integer $m \ge 2$, let $k$ be a positive integer with $k \log k > e^{8m+4}$. For any admissible set $\{b_1, \dots, b_k\}$, there are infinitely many integers $n$ such that at least $m$ of $n+b_1, \dots, n+b_k$ are prime numbers.

**Lemma 6 ([2, Lemma 3]).** We have

$$ \prod_{3 \le p \le x} \left(1 - \frac{1}{p}\right)^{-1} \le 0.923 \log x, \quad x \ge 74, $$

where the product is taken over all primes $p$ with $3 \le p \le x$.

**Proof of Theorem 2.** If $\ell \le e^{12}$, then

$$ \frac{1}{8} \log \ell - 1.6 \le 0, $$

and Theorem 2 is trivial. In the following, we assume that $\ell > e^{12}$.

Let $p_i$ be the $i$th prime. Assume that $a_1, \dots, a_\ell$ are $\ell$ distinct integers. For $p_1$, one of residues modulo $p_1$ contains at most $\lfloor \ell/p_1 \rfloor$ of $a_1, \dots, a_\ell$. So at least $\ell - \lfloor \ell/p_1 \rfloor$ of $a_1, \dots, a_\ell$ occupy at most $p_1 - 1$ residues modulo $p_1$. Let $\ell_0 = \ell$ and $\ell_1 = \ell - \lfloor \ell/p_1 \rfloor$. Without loss of generality, we assume that $a_1, \dots, a_{\ell_1}$ occupy at most $p_1 - 1$ residues modulo $p_1$. Similarly, without loss of generality, we may assume that $a_1, \dots, a_{\ell_2}$ occupy at most $p_2 - 1$ residues modulo $p_2$, where $\ell_2 = \ell_1 - \lfloor \ell_1/p_2 \rfloor$. Continuing this process, at the $t$th step, we may assume that $a_1, \dots, a_{\ell_t}$ occupy at most $p_t - 1$ residues modulo $p_t$, where $\ell_t = \ell_{t-1} - \lfloor \ell_{t-1}/p_t \rfloor$. Since $\ell \ge \ell_1 \ge \dots$ and $p_1 < p_2 < \dots$, there exists $t$ with $\ell_t < p_{t+1}$. Let $s$ be the least integer with $\ell_s < p_{s+1}$. It is clear that $\{a_1, \dots, a_{\ell_s}\}$ is an admissible
set. Let $m$ be largest integer with $\ell_s \log \ell_s > e^{8m+4}$. If $m \ge 2$, then by Lemma 5, there are infinitely many integers $n$ such that at least $m$ of $n - a_1, \dots, n - a_{\ell_s}$ are prime numbers. Since there are infinitely many primes, it follows that there are infinitely many integers $n$ such that at least one of $n - a_1, \dots, n - a_{\ell_s}$ is prime number. So the conclusion is also true for $m \le 1$.

Now we establish an explicit relation between $\ell$ and $m$.

Since

$$ \ell_{i+1} = \ell_i - \left\lfloor \frac{\ell_i}{p_{i+1}} \right\rfloor \ge \ell_i - \frac{\ell_i}{p_{i+1}} = \ell_i \left(1 - \frac{1}{p_{i+1}}\right), \quad i = 0, 1, \dots, $$

it follows from the definition of $s$ that

$$ \begin{aligned} p_{s+1} > \ell_s \ge \ell_{s-1} \left(1 - \frac{1}{p_s}\right) &\ge \cdots \ge \ell \left(1 - \frac{1}{p_1}\right) \cdots \left(1 - \frac{1}{p_s}\right) \\ &> e^{12} \left(1 - \frac{1}{p_1}\right) \cdots \left(1 - \frac{1}{p_s}\right). \end{aligned} $$

This cannot hold for $s \le 100$. So $p_s \ge p_{100} = 541$. Thus, by Lemma 6,

$$ \ell_s \ge \ell \left(1 - \frac{1}{p_1}\right) \cdots \left(1 - \frac{1}{p_s}\right) \ge \frac{\ell}{2} \cdot \frac{1}{0.923 \log p_s} = \frac{\ell}{1.846 \log p_s}. $$

By the definition of $s$, $p_s \le \ell_{s-1}$. Thus,

$$ \ell_s \ge \left(1 - \frac{1}{p_s}\right) \ell_{s-1} \ge \left(1 - \frac{1}{p_s}\right) p_s = p_s - 1. $$

It follows that

$$ \ell_s \ge \frac{\ell}{1.846 \log p_s} \ge \frac{\log 540}{1.846 \log 541} \frac{\ell}{\log(p_s - 1)} > \frac{0.54\ell}{\log \ell_s}. $$

So $\ell_s \log \ell_s \ge 0.54\ell$. In view of the definition of $m$,

$$ e^{8m+12} \ge \ell_s \log \ell_s \ge 0.54\ell. $$

So

$$ m \ge \frac{1}{8} \log \ell - \frac{12}{8} + \frac{\log 0.54}{8} > \frac{1}{8} \log \ell - 1.6. $$

This completes the proof of Theorem 2. $\square$

<figure><img src="image_4.png" /></figure>

**Proof of Corollary 3.** Assume that

$$ 1 \le a_1 < \cdots < a_t \le x, \quad t > \log x. $$

By Theorem 2, there are infinitely many positive integers $n$ such that the number of solutions of $n = p + a_i$ ($p \in \mathcal{P}$, $1 \le i \le t$) is greater than

$$ \frac{1}{8} \log t - 1.6 > \frac{1}{8} \log \log x - 1.6. $$

This completes the proof of Corollary 3. $\square$

<figure><img src="image_5.png" /></figure>

**Proof of Corollary 4.** By Theorem 2, there is a positive integer $n$ such that the number of solutions of $n = p + a_i$ ($p \in \mathcal{P}$, $1 \le i \le \ell$) is greater than $\frac{1}{8} \log \ell - 1.6$. That is, $f_{\mathcal{A}}(n) \ge \frac{1}{8} \log \ell - 1.6$. Now Corollary 4 follows immediately. $\square$

<figure><img src="image_6.png" /></figure>

### 3. Remarks

It is known that there is a positive proportion of positive odd numbers that can be represented as $p+2^k$ with $k \in \mathbb{N}$ and $p \in \mathcal{P}$ (See Romanoff [9]) and there is an arithmetical progression of positive odd numbers none of which can be represented as $p+2^k$ with $k \in \mathbb{N}$ and $p \in \mathcal{P}$ (see Erdős [5]).

Since one can take $k \le c \exp\left((4 - \frac{28}{157})m\right)$ for some positive constant $c$ in Lemma 5 (see [8, Theorem 16]), it follows that $\frac{1}{8}$ in Theorem 2 and Corollary 3 can be improved to any constant less than $(4 - \frac{28}{157})^{-1}$.
References

[1] Y.-G. Chen, "Romanoff theorem in a sparse set", *Sci. China, Math.* **53** (2010), no. 9, p. 2195-2202.

[2] Y.-G. Chen, X.-G. Sun, "On Romanoff's constant", *J. Number Theory* **106** (2004), no. 2, p. 275-284.

[3] Y. Ding, "Extending an Erdős result on a Romanov type problem", *Arch. Math.* **118** (2022), p. 587-592.

[4] Y. Ding, G.-L. Zhou, "Some application of the admissible sets", preprint.

[5] P. Erdős, "On integers of the form $2^k + p$ and some related problems", *Summa Brasil. Math.* **2** (1950), p. 113-123.

[6] A. Granville, "Primes in intervals of bounded length", *Bull. Am. Math. Soc.* **52** (2015), no. 2, p. 171-222.

[7] J. Maynard, "Small gaps between primes", *Ann. Math.* **181** (2015), no. 1, p. 383-413.

[8] D. H. J. Polymath, "Variants of the Selberg sieve, and bounded intervals containing many primes", *Res. Math. Sci.* **1** (2014), article no. 12.

[9] N. P. Romanoff, "Über einige Sätze der additiven Zahlentheorie", *Math. Ann.* **109** (1934), p. 668-678.