Erdős Problem #32

Erdős Problem 32 --- Round 3 continuation and gap-closure

1. ROUND-3 OBJECTIVE

I pursue path (C): obstruction/correction. Round 2 established a real obstruction: any proof of an exact one-shift theorem \[ \mathcal P + A \supseteq [N_0,\infty) \quad\text{with}\quad A(x)=o((\log x)^2)\ \text{or}\ A(x)=O(\log x) \] that uses only coarse size information of the primes is impossible, because prime-like random sets of density $1/\log x$ already force a $(\log x)^2$ barrier.

The most promising strict advance is therefore to identify the nearest exact $O(\log x)$ theorem that is actually true after a minimal correction of the representation problem. The new goal in this round is to prove the following corrected statement:

Corrected exact theorem. There exists a set $T\subseteq \mathbb N$ with \[ T(x)=O(\log x) \] such that every sufficiently large integer $n$ can be written in the form \[ n=p+t_1+t_2 \qquad (p\in\mathcal P,\ t_1,t_2\in T). \]

This is an exact, cofinite-coverage theorem at the $O(\log x)$ scale, one extra thin summand away from the original open problem.

2. Round-2 FOUNDATION USED

I use the following Round 2 result as fixed input.

• Round-2 obstruction. There exist prime-like sets $P'\subseteq \mathbb N$ with \[ P'(x)\sim \frac{x}{\log x} \] for which every additive complement $B$ satisfies \[ \liminf_{x\to\infty}\frac{B(x)}{(\log x)^2}\ge 1. \] Hence any successful proof for the actual primes with $A(x)=o((\log x)^2)$ or $A(x)=O(\log x)$ must use arithmetic structure specific to the primes, not just counting-function information.

I also use the trivial monotonicity fact that if $S(x)=O(\log x)$ then $(S+1)(x)=O(\log x)$, and therefore \[ (S\cup(S+1))(x)=O(\log x). \]

3. NEW INSIGHT / TOOL (ROUND-3)

The new ingredient is a prime-specific theorem of Dai and Pan:

External Theorem (Dai--Pan). There exists a set $A\subseteq \mathcal P$ with \[ A(x)=O(\log x) \] such that every sufficiently large odd integer $n$ can be represented as \[ n=a_1+a_2+p \qquad (a_1,a_2\in A,\ p\in\mathcal P). \]

Round 3 adds a parity-shift observation to convert this odd-integer theorem into a cofinite theorem for all sufficiently large integers, still with only $O(\log x)$ many thin summands available.

4. ATTACK PLAN (ROUND-3)

After Round 2, the exact gap was this:

there was a rigorous barrier against density-only proofs of the original one-shift problem, but no positive theorem showing how close one can nevertheless get to an exact $O(\log x)$ statement.

The precise claim to prove now is:

Claim. There exists $T\subseteq\mathbb N$ with $T(x)=O(\log x)$ and an integer $N_1$ such that every $n\ge N_1$ satisfies \[ n\in \mathcal P+T+T. \]

The plan is to start from the Dai--Pan set $A\subseteq\mathcal P$, define \[ T:=A\cup (A+1), \] and then check separately the odd and even cases. Odd integers are covered directly by the external theorem; even integers are reduced to odd integers by subtracting $1$ and absorbing the shift into one of the two thin summands.

5. WORK (ROUND-3)

Step 1: Invoke the prime-specific theorem.

By the Dai--Pan theorem, there is a set $A\subseteq \mathcal P$ and an integer $N_0$ such that \[ A(x)=O(\log x) \] and every odd integer $m\ge N_0$ can be written as \[ m=a_1+a_2+p \qquad (a_1,a_2\in A,\ p\in\mathcal P). \] No extra hypotheses are needed; this is exactly the stated theorem.

Step 2: Define the corrected thin set.

Set \[ T:=A\cup (A+1). \] Then \[ T(x)\le A(x)+A(x-1)=O(\log x), \] so $T$ still has logarithmic counting function.

Step 3: Cover all sufficiently large odd integers.

Let $n\ge N_0$ be odd. By the theorem, \[ n=a_1+a_2+p \qquad (a_1,a_2\in A,\ p\in\mathcal P). \] Since $A\subseteq T$, this is already a representation \[ n=p+t_1+t_2 \qquad (t_1,t_2\in T). \] Thus every sufficiently large odd integer lies in $\mathcal P+T+T$.

Step 4: Cover all sufficiently large even integers.

Let $n\ge N_0+1$ be even. Then $n-1\ge N_0$ is odd, so again by the theorem, \[ n-1=a_1+a_2+p \qquad (a_1,a_2\in A,\ p\in\mathcal P). \] Hence \[ n=(a_1+1)+a_2+p. \] Now $a_1+1\in A+1\subseteq T$ and $a_2\in A\subseteq T$, so \[ n=p+t_1+t_2 \qquad (t_1,t_2\in T). \] Therefore every sufficiently large even integer also lies in $\mathcal P+T+T$.

Conclusion.

If we choose $N_1:=N_0+1$, then every integer $n\ge N_1$ belongs to $\mathcal P+T+T$, with \[ T(x)=O(\log x). \] This proves the corrected exact theorem.

Corollary (exact $O((\log x)^2)$ complement recovered from an $O(\log x)$ set). Let \[ C:=T+T. \] Then every sufficiently large integer belongs to $\mathcal P+C$, and \[ C(x)\le T(x)^2=O((\log x)^2) \] in the crude counting-function sense. So the classical Erdős-scale exact complement bound is recovered from a logarithmic set $T$ by one extra additive layer.

6. ADVERSARIAL VERIFICATION

Parity check.

Odd $n$ are covered directly. Even $n$ are handled by writing $n-1$ as an odd integer covered by the external theorem and shifting one thin summand by $+1$. No parity case is omitted.

Growth check.

Passing from $A$ to $A+1$ does not change the order of magnitude of the counting function, and taking the union preserves the estimate $O(\log x)$. Thus the corrected theorem genuinely remains at logarithmic scale.

Quantifier check.

The external theorem gives a single set $A$ and a single threshold $N_0$ working for all sufficiently large odd integers. From this we constructed a single set $T$ and a single threshold $N_1=N_0+1$ working for all sufficiently large integers. There is no hidden dependence on $n$.

Compatibility with Round 2.

There is no contradiction with the Round 2 barrier. Round 2 ruled out density-only approaches to the one-shift problem $\mathcal P+A$ with $A(x)=o((\log x)^2)$ or $O(\log x)$. The present result uses genuine prime-specific input and proves a different statement, namely coverage by \[ \mathcal P+T+T, \] not by $\mathcal P+T$.

Minimality claim.

I do not claim to have proved that adding one extra thin summand is logically minimal among all possible corrections. What has been proved is that this is the closest exact $O(\log x)$ correction supplied by the checked literature used here.

7. FINAL

UNRESOLVED (BUT STRICTLY ADVANCED)

Round 3 adds a rigorous positive theorem beyond the Round 2 obstruction:

There exists a set $T\subseteq\mathbb N$ with $T(x)=O(\log x)$ such that every sufficiently large integer is representable as \[ n=p+t_1+t_2 \qquad (p\in\mathcal P,\ t_1,t_2\in T). \]

Thus the nearest checked exact $O(\log x)$ variant currently available is true after adding one further thin summand. Combined with Round 2, this sharply isolates the frontier:

• exact one-shift coverage $\mathcal P+A$ at size $O(\log x)$ remains open,
• density-only methods cannot settle it,
• but exact two-thin-shift coverage $\mathcal P+T+T$ at size $T(x)=O(\log x)$ is already provable.

8. COMPLETION ESTIMATE

COMPLETION: 58%

9. REFERENCES

• {[DP14 }] Li-Xia Dai and Hao Pan, The additive complements of primes and Goldbach's problem, Acta Arithmetica 162 $2014$, 209--221.
• {[Ko96 }] Mihail N. Kolountzakis, On the additive complements of the primes and sets of similar growth, Acta Arithmetica 77 $1996$, 1--8.
• {[EP32 }] Erdős Problem #32, erdosproblems.com.

Erdős Problem #32: independent continuation

Date: 23 September 2026. Source versions read in full: 32.tex in gpt_pro_5.4.

1) OBJECTIVE AND SOURCE AUDIT

The target is a cofinite additive complement $A$ to the primes with $A(x)=o((\log x)^2)$, ideally $O(\log x)$. The supplied file proves a different, two-thin-summand conclusion using an external theorem. Its parity-shift step is valid, but replacing $A$ by $T+T$ restores the quadratic logarithmic bound. I do not count that as closing the original gap, and do not use its unverified random-model assertion as a theorem about primes.

2) WORK: A MULTIPLICITY OBSTRUCTION

Here is a precise condition that any near-minimal complement must evade. Let $A\subset\mathbb N_0$ be fixed and \[ r(n)=\#\{a\in A:n-a\text{ is prime}\},\qquad C(x)=\sum_{n\le x}\binom{r(n)}2. \] Suppose $r(n)\ge1$ for $n\ge n_0$, and suppose also that $r(n)\le K$ for these $n$, for a fixed integer $K\ge1$. Then \[ A(x)\pi(x)\ge x-O(1)+\frac{2C(x)}K-O(1). \] Indeed, interchange the order of summation to obtain $\sum_{n\le x}r(n)=\sum_{a\le x}\pi(x-a)\le A(x)\pi(x)$. For $1\le r\le K$, $\binom r2\le K(r-1)/2$. Summing this inequality over $n_0\le n\le x$ proves the assertion; the finitely many earlier values contribute constants. Consequently, if $C(x)\ge(\delta+o(1))x$ along a subsequence, then the prime number theorem gives \[ A(x)\ge\left(1+\frac{2\delta}{K}+o(1)\right)\log x \] along that subsequence. The unconditional elementary first-order bound is $A(x)\ge(1-o(1))\log x$, obtained without the multiplicity assumption.

The collision term has the exact form \[ C(x)=\sum_{\substack{a<b\\a,b\in A\cap[0,x]}} \#\{n\le x:n-a\text{ and }n-b\text{ are prime}\}. \] Thus an attempted construction close to the counting lower bound must control actual shifted-prime correlations. Cardinality estimates alone do not control this sum.

3) ADVERSARIAL VERIFICATION

The bounded multiplicity hypothesis is additional and has not been proved for an arbitrary thin complement. Nor have I proved a positive linear lower bound for $C(x)$. The displayed obstruction is therefore conditional on these two explicit assumptions, whereas the logarithmic lower bound is unconditional. It is not a disproof of an $O(\log x)$ complement.

7) FINAL AND REFERENCES

UNRESOLVED. This attempt provides a concrete overlap calculation for the original one-shift problem, but neither a sufficiently thin set nor a general obstruction to one. The supplied two-summand result remains a different problem. Literature check: Dai--Pan, Note on the additive complements of primes, https://arxiv.org/abs/1101.1653; the search record was checked, but no stronger theorem from it is used here. The direct official problem-page fetch was unavailable.

8) COMPLETION ESTIMATE

COMPLETION: 8% This is a subjective estimate of progress toward the entire stated problem, not a probability that the conjecture or an unverified proof is correct.

Round 2: Continuation & Gap-Closure (Erdős Problem #32)

1) ROUND-2 OBJECTIVE

Path (C): obstruction / correction.

Round-1 identified that (i) elementary finite obstructions (CRT and factorial blocks) do not by themselves yield the asymptotic lower bounds needed to settle the $o((\log N)^2)$ / $O(\log N)$ questions for the actual primes, and (ii) any successful improvement must exploit structure beyond mere density. In this round we prove a rigorous strategy barrier: there exist prime-like sets $\mathcal P'\subseteq\mathbb N$ with counting function $\mathcal P'(x)\sim x/\log x$ for which every additive complement $B$ must satisfy \[ \liminf_{x\to\infty}\frac{B(x)}{(\log x)^2}\ge 1. \] Consequently, any approach that uses only "PNT-scale" information (growth like $x/\log x$) cannot prove an $o((\log N)^2)$ complement for the actual primes; it would falsely apply to such $\mathcal P'$.

2) ROUND-1 FOUNDATION USED

We rely on the following Round-1 items (used only as foundations, not reproved here):

1. Definition: $A$ is an additive complement to primes if $\exists N_0$ such that every $n\ge N_0$ satisfies $n=p+a$ with $p\in\mathcal P$, $a\in A$.
2. Finite truncation principle (implicit in the Round-1 set-cover viewpoint): to cover $[M,x]$ by a sumset $P'+B$, it suffices to consider $B\cap[0,x]$, since if $p'+b\le x$ then $b\le x$.

3) NEW INSIGHT / TOOL (ROUND-2)

New input is a hard-to-complement theorem (Kolountzakis, 1996): for a suitable random prime-like set $\mathcal P'$, every additive complement $B$ must have size $\gtrsim(\log x)^2$. The proof uses:

1. a packing/greedy construction producing many disjoint truncated translates of $B$;
2. independence of membership events for $\mathcal P'$ on disjoint sets;
3. a union bound over all small $B\cap[0,x]$ and a Borel--Cantelli argument.

4) ATTACK PLAN (ROUND-2)

Round-1 gap addressed: show why arguments based only on coarse density information cannot improve the $(\log N)^2$ scale.

Plan: define a random set $\mathcal P'$ with inclusion probabilities $\mathbb P(n\in\mathcal P')=1/\log n$ (for $n\ge4$). Show that almost surely:

1. $\mathcal P'(x)\sim x/\log x$ (so $\mathcal P'$ is prime-like in growth);
2. if $B(x)\le C(\log x)^2$ infinitely often with some $C<1$, then $B$ cannot be an additive complement of $\mathcal P'$.

Thus, almost surely every additive complement satisfies $\liminf B(x)/(\log x)^2\ge1$.

5) WORK (ROUND-2)

5.1 Setup

Let $\mathbb N=\{0,1,2,\dots\}$. Define a random set $\mathcal P'\subseteq\{4,5,6,\dots\}$ by choosing each integer $n\ge4$ independently with probability \[ \mathbb P(n\in\mathcal P')=\frac1{\log n}. \] For $B\subseteq\mathbb N$ define $B(x):=|B\cap[0,x]|$.

We say $B$ is an additive complement of $\mathcal P'$ if $\exists N_0$ such that every $n\ge N_0$ can be written $n=p'+b$ with $p'\in\mathcal P'$, $b\in B$.

5.2 Main theorem (barrier)

Theorem. With probability $1$ (over the choice of $\mathcal P'$), every additive complement $B$ of $\mathcal P'$ satisfies \[ \liminf_{x\to\infty}\frac{B(x)}{(\log x)^2}\ge 1. \] In particular, for every fixed $C<1$ there is almost surely no additive complement $B$ such that $B(x)\le C(\log x)^2$ for infinitely many $x$.

5.3 Combinatorial packing lemma

Fix $x\in\mathbb N$ and finite $B\subseteq[0,x]$ with $m:=|B|=B(x)$. For $a\in[0,x]$ define $B_{\le a}:=B\cap[0,a]$ and \[ a-B_{\le a}:=\{a-b:\ b\in B_{\le a}\}. \]

Fix $\lambda\in(0,1)$ and set \[ s:=\left\lfloor \frac{\lambda x}{m}\right\rfloor. \]

Lemma 1 (many disjoint truncated translates). There exist integers $a_1,\dots,a_n\in[0,x]$ such that:

1. the sets $a_j-B_{\le a_j}$ are pairwise disjoint;
2. each $(a_j-B_{\le a_j})\cap[1,s]=\emptyset$;
3. and \[ n\ge \frac{(1-\lambda)x}{m^2}. \]

Proof. Choose a maximal family $a_1,\dots,a_n$ satisfying $1$--$2$. Let \[ G:=[1,s]\ \cup\ \bigcup_{j=1}^n (a_j-B_{\le a_j}). \] By maximality, for every $y\in[0,x]$ the set $y-B_{\le y}$ intersects $G$, so $y\in G+B$. Thus $[0,x]\subseteq G+B$ and hence \[ x+1 \le |G+B|\le |G|\cdot|B|\le (s+nm)m. \] Rearranging gives $n\ge (x+1)/m^2 - s/m \ge x/m^2 - s/m \ge (1-\lambda)x/m^2$ since $s\le \lambda x/m$. $\square$

5.4 A single-point coverage bound

Fix $x$, $B\subseteq[0,x]$ with $|B|=m$, and $s\ge4$. If $a\in[0,x]$ satisfies $(a-B_{\le a})\cap[1,s]=\emptyset$, then every positive element of $a-B_{\le a}$ is $>s$.

Lemma 2 (coverage probability bound). For any fixed $\varepsilon>0$, for all sufficiently large $s$ (depending on $\varepsilon$), \[ \mathbb P(a\in \mathcal P'+B)\ \le\ 1-\exp\!\left(-\frac{(1+\varepsilon)m}{\log s}\right). \]

Proof. The event $a\in \mathcal P'+B$ is equivalent to $(a-B_{\le a})\cap \mathcal P'\neq\emptyset$. Independence yields \[ \mathbb P(a\notin \mathcal P'+B)=\prod_{k\in a-B_{\le a}}\left(1-\frac1{\log k}\right). \] For positive $k\in a-B_{\le a}$ we have $k>s$ hence $\log k\ge\log s$ and \[ 1-\frac1{\log k}\ge 1-\frac1{\log s}. \] Also $|a-B_{\le a}|=|B_{\le a}|\le m$, so \[ $\mathbb P$$a\notin \mathcal P'+B$$\ge$

\left

(1-

\frac