Erdős Problem #237

Erdős Problem 237: many representations as a prime plus a set element

1) Statement and scope

Let $A\subseteq\mathbb N$ satisfy $|A\cap[1,N]|\gg\log N$. If $f_A(n)=\#\{a\in A:n-a\text{ is prime}\}$, must $\limsup_n f_A(n)=\infty$? The answer is yes, even for every infinite $A$. We reconstruct the reduction of Chen and Ding to the Maynard--Tao theorem. That sieve theorem is an explicit external input.

2) The external prime-tuple theorem

We use the following qualitative form: for each $m\geq1$ there exists an integer $k\geq m$ such that, for every admissible set of $k$ distinct integer shifts $h_1,\ldots,h_k$, infinitely many integers $t$ have at least $m$ primes among $t+h_1,\ldots,t+h_k$. Admissible means that, for every prime $p$, the shifts do not occupy every residue class modulo $p$. The theorem applies to fixed shifts, and the threshold $k$ depends only on $m$.

3) Extracting an admissible tuple from any infinite set

Fix $m$ and a corresponding $k$, and put $P=\prod_{p\leq k}p$. One residue class modulo $P$ contains infinitely many elements of $A$. Choose distinct $a_1,\ldots,a_k$ in that class. Take $T=\max_i a_i$ and $h_i=T-a_i$.

For any prime $p\leq k$, all the $h_i$ have the same residue modulo $p$, and so miss at least one class. For $p>k$, at most $k<p$ residue classes are occupied. Thus the tuple is admissible. For infinitely many $t$, at least $m$ numbers $t+T-a_i$ are prime. Setting $n=t+T$ gives $f_A(n)\geq m$. These $n$ are unbounded. Since $m$ was arbitrary, \[ \limsup_{n\to\infty}f_A(n)=\infty. \] The original growth hypothesis is used only to ensure that $A$ is infinite. The choices of $a_i$ may depend on $m$, which is consistent with the asserted limsup.

4) Attribution and dependencies

This is a reconstruction of the known solution, not a new sieve proof. The admissibility and quantifier arguments are supplied in full; the deep theorem about simultaneous prime shifts is used as stated.

Sources: https://www.erdosproblems.com/237; Y.-G. Chen and Y. Ding, On a conjecture of Erdős, including their prime-tuple lemma and its application: https://www.numdam.org/item/10.5802/crmath.345.pdf.

5) Completion estimate

The full statement follows, conditional only on the established Maynard--Tao theorem explicitly identified above. COMPLETION: 100%