Erdős Problem 741: splitting sumsets, and a basis with no bounded-gap split
1. Questions and outcome
For $A\subseteq\mathbb N$, write $A+A=\{a+b:a,b\in A\}$. The two questions are whether positive upper density of $A+A$ permits a partition $A=A_1\sqcup A_2$ with both self-sumsets of positive upper density, and whether some asymptotic basis of order two has no partition for which both self-sumsets have bounded gaps. Both answers are yes. If the first question instead requires existence of positive natural densities, its answer is no. We prove all three assertions. The upper-density argument and the natural-density construction come from the DeepMind work discussed on the problem page and the April 2026 note linked there; the bounded-gap construction is due to Alexeev, Putterman, Sawhney, Sellke and Valiant. These are reconstructions of known results, not new claims. No external structural theorem is needed in the proofs.
2. Positive upper density: an alternating partition
For a set $X$, let $X(N)=|X\cap[1,N]|$. Recall the elementary inequality $|D+D|\ge2|D|-1$ for a nonempty finite integer set $D=\{d_1<\cdots<d_r\}$: the strictly increasing sequence \[
d_1+d_1<d_1+d_2<\cdots<d_1+d_r<d_2+d_r<\cdots<d_r+d_r
\] has $2r-1$ terms. Applying this at scale $2N$ shows $\overline d(X+X)\ge\overline d(X)$. First suppose $\overline d(A)>0$. Choose $c>0$ with $A(N)\ge cN$ for infinitely many $N$. Recursively choose $M_{j+1}>M_j$ at such a scale with $A(M_j)\le cM_{j+1}/4$. Color the elements of $A$ in successive intervals $(M_j,M_{j+1}]$ alternately red and blue; assign the finite initial segment arbitrarily. At each block endpoint its color occupies at least $3cM_{j+1}/4$ elements below that endpoint. Both color classes therefore have positive upper density, and so do their self-sumsets. Now suppose $\overline d(A)=0$, while $\overline d(A+A)>0$. Put $a(N)=A(N)$ and $s(N)=|(A+A)\cap[1,N]|$. Choose $c>0$ such that $s(N)\ge cN$ infinitely often. Given $M_j$, choose one of those scales $M_{j+1}$ so large that \[
M_j a(M_{j+1})\le cM_{j+1}/4;
\] this is possible because $a(N)=o(N)$. Use the same alternating block coloring. At the endpoint $N=M_{j+1}$, all elements of the opposite color at most $N$ are at most $M_j$. Any represented sum at most $N$ that is missing from the current color's self-sumset uses one of these old elements. There are at most $M_j a(N)$ such sums, since each old value has at most $a(N)$ possible partners. Hence the current color's self-sumset contains at least $3cN/4$ integers up to $N$. Alternating endpoints prove positive upper density for both colors.
3. A basis for which one color always has long gaps
All intervals in this part are inclusive integer intervals. For $k\ge1$, put $Q_k=5^{k-1}$ and \[
c_k=4Q_k,\qquad B_k=[5Q_k,6Q_k-1],\qquad F_k=[10Q_k-1,15Q_k].
\] Define \[
A=[2,3]\cup\bigcup_{k\ge1}(\{c_k\}\cup B_k\cup F_k),
\qquad A^{(k)}=[2,3]\cup\bigcup_{i=1}^k(\{c_i\}\cup B_i\cup F_i).
\] We claim $[4,6\cdot5^k]\subseteq A^{(k)}+A^{(k)}$ for every $k\ge0$. The case zero is $[2,3]+[2,3]=[4,6]$. For the induction step let $Q=Q_k$ and note that $I=[2Q,3Q]$ lies in the previous stage (for $k=1$, in $[2,3]$). The following intervals are in the new sumset: \[
\begin{array}{c|c}
I+I &[4Q,6Q]\\
I+c_k &[6Q,7Q]\\
I+B_k &[7Q,9Q-1]\\
c_k+B_k &[9Q,10Q-1]\\
B_k+B_k &[10Q,12Q-2]\\
I+F_k &[12Q-1,18Q]\\
B_k+F_k &[15Q-1,21Q-1]\\
F_k+F_k &[20Q-2,30Q]
\end{array}
\] They cover every integer from $4Q$ to $30Q$; adjacent endpoints differing by one leave no integer gap. Together with the inductive interval $[4,6Q]$, they prove the claim. Thus $A+A$ contains $[4,\infty)$. Set $J_k=[9Q_k,10Q_k-1]$. Every representation of an integer in $J_k$ uses $c_k$. Indeed, earlier stages contain only numbers at most $3Q_k$, and later stages start at $20Q_k$. A sum of two earlier elements is at most $6Q_k$. An earlier element plus $c_k$ is at most $7Q_k$, and plus an element of $B_k$ is at most $9Q_k-1$. An earlier element plus $F_k$ is at least $10Q_k+1$, since every element of $A$ is at least $2$. Among pairs wholly in stage $k$, only $c_k+B_k$ meets $J_k$: $2c_k=8Q_k$, while $B_k+B_k$ starts at $10Q_k$ and the other possibilities are larger. In any two-coloring, one color contains $c_k$ for infinitely many $k$. The other color's self-sumset misses the entire corresponding intervals $J_k$, whose lengths $5^{k-1}$ tend to infinity. It therefore does not have bounded gaps. This proves the second assertion with a genuine order-two asymptotic basis.
4. Why strict natural density has a different answer
Work first in $\mathbb N_0$. Let $D$ consist of integers with only digits $0,1$ in base four and let $E=2D$. For every $u\ge1$, each integer below $4^u$ has a unique expression as $d+e$ with $d\in D\cap[0,4^u)$ and $e\in E\cap[0,4^u)$. This follows digit by digit from the unique decompositions $j=\epsilon+2\delta$ for $j\in\{0,1,2,3\}$ and $\epsilon,\delta\in\{0,1\}$. No carry occurs. Put $N_k=4^{3^k}$, let $I_k=[N_k,(k+1)N_k)\cap\mathbb N_0$, and take \[
A=D\cup E\cup\bigcup_{k\ge1}I_k.
\] Then $A+A=\mathbb N_0$. Suppose a partition $A=A_1\sqcup A_2$ gives both self-sumsets positive natural densities $\alpha_1,\alpha_2$. At the scale $N_k$, both digit sets have exactly $\sqrt{N_k}$ elements. Let $x_k,y_k$ be the proportions of $D\cap[0,N_k)$ and $E\cap[0,N_k)$ assigned to color one. The old intervals have total size \[
T_k=\sum_{j<k}jN_j\le k^2N_{k-1}=o(\sqrt{N_k}).
\] Sums involving them contribute at most $2T_k\sqrt{N_k}+T_k^2=o(N_k)$ distinct integers. Each digit self-sumset contributes at most $3^{3^k}=o(N_k)$ possibilities: there are three digitwise choices in $D+D$, and $E+E=2(D+D)$. The carry-free mixed sums are unique and all lie below $N_k$. Therefore \[
\alpha_1=x_ky_k+o(1),\qquad
\alpha_2=(1-x_k)(1-y_k)+o(1). \tag{1}
\] The common point $0$ of $D$ and $E$ has one consistent color; it does not invalidate either product count or the complementary proportions. For $0\le x,y\le1$, write $p=xy$ and $q=(1-x)(1-y)$. Then \[
pq=x(1-y)y(1-x)\le x(1-y)+y(1-x)=1-p-q.
\] By $1$, $\alpha_1+\alpha_2\le1-\alpha_1\alpha_2<1$. On the other hand partition the long interval $I_k$ into $U_k=A_1\cap I_k$ and $V_k=A_2\cap I_k$. The finite sumset inequality, valid with the weaker right side $-1$ also for an empty set, gives \[
|U_k+U_k|+|V_k+V_k|\ge2kN_k-2.
\] All these sums are below $L_k=2(k+1)N_k$. Divide by $L_k$ and use existence of the two natural densities to obtain $\alpha_1+\alpha_2\ge1$, a contradiction. Finally replace $A$ by $A+1$ to obtain a subset of positive integers; finite translation preserves all density conclusions.
5. Sources and verification
Sources:
https://www.erdosproblems.com/741 and its discussion,
https://www.erdosproblems.com/forum/thread/741;
A note on Erdős problem 741 (23 April 2026),
https://www.ulam.ai/research/erdos741.pdf; B. Alexeev, M. Putterman, M. Sawhney, M. Sellke and G. Valiant,
Short proofs in combinatorics and number theory,
https://arxiv.org/abs/2603.29961. The upper-density subsequences for the two colors need not coincide. The bounded-gap argument uses a single color missing infinitely many growing intervals, obtained by the infinite pigeonhole principle. The strict-density contradiction explicitly uses the existence of limits and makes no claim about the lower-density variant. No local Lean kernel verification is claimed.
6. Final assessment
SOLVED: both displayed questions have affirmative answers under the upper-density reading, and the strict natural-density reading has the proved counterexample above.
Completion rate estimate: 100%.