Erdős Problem #741

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%.

Round-2 continuation for Erdős Problems 741, 749, 750

This is a genuine continuation of the previous round. I only use Round-1 material when explicitly indicated below, and I only re-prove statements when they are strengthened.

Conventions for this continuation: $\overline d(\cdot)$ and $\underline d(\cdot)$ denote upper and lower asymptotic density in $\mathbb N$, and when discussing Problem 750 it is enough to work with induced subgraphs, since deleting edges can only increase the independence number.

---

Problem 741

1) ROUND-2 OBJECTIVE

Path (C): isolate a sharp structural obstruction and convert the Round-1 heuristic into a rigorous theorem.

More precisely, Round-1 identified the following missing input: a positive-density family of sums with many disjoint representations would force a good 2-colouring of $A$. In this round I prove that this mechanism is rigorous, and that in fact the "disjointness" requirement from Round-1 is automatic once one counts distinct unordered representations. This gives a genuine conditional theorem and shows what any counterexample must look like.

2) Round-1 FOUNDATION USED

I use exactly the following Round-1 points.

• Round-1 already handled the easy dense case $\underline d(A)>0$.
• Round-1 isolated the key missing lemma: if a positive-density set of sums has many pairwise disjoint representations, then a random 2-colouring should leave positive density in both monochromatic sumsets.

I do not re-prove those Round-1 facts here.

3) NEW INSIGHT / TOOL (ROUND-2)

For a fixed integer $n$, distinct unordered representations of $n$ are automatically disjoint.

Indeed, if \[ a+b=n,\qquad c+d=n,\qquad a\le b,\ c\le d, \] and $\{a,b\}\cap\{c,d\}\neq\varnothing$, then necessarily $\{a,b\}=\{c,d\}$. So the only real input needed is not "many disjoint representations", but simply "many distinct unordered representations".

That converts the Round-1 heuristic into a clean quantitative theorem.

4) ATTACK PLAN (ROUND-2)

The gap left by Round-1 was:

Can one rigorously deduce a good partition from a positive-density set of sums with many representations?

I will prove the following.

Theorem 741.1. Let \[ S_R:=\{n\in\mathbb N : r_A^{\ast}(n)\ge R\}, \] where $r_A^{\ast}(n)$ denotes the number of distinct unordered representations \[ n=a+b,\qquad a,b\in A,\qquad a\le b. \] If $\overline d(S_R)=\delta>0$ for some integer $R\ge 3$, then there exists a partition \[ A=A_1\sqcup A_2 \] such that \[ \overline d(A_1+A_1)\ge \left(1-2(3/4)^R\right)\delta>0, \qquad \overline d(A_2+A_2)\ge \left(1-2(3/4)^R\right)\delta>0. \]

This overcomes the precise obstacle named in Round-1, and it yields the structural corollary that any counterexample to Problem 741 must have \[ \overline d\left(\{n:r_A^{\ast}(n)\ge 3\}\right)=0. \]

5) WORK (ROUND-2)

For $n\in\mathbb N$, define \[ r_A^{\ast}(n):=\left|\{(a,b)\in A^2:a\le b,\ a+b=n\}\right|. \]

Lemma 741.2. If $(a,b)$ and $(c,d)$ are two distinct unordered representations of the same integer $n$, then \[ \{a,b\}\cap\{c,d\}=\varnothing. \]

Proof. Suppose $a+b=c+d=n$ and $(a,b)\neq(c,d)$ with $a\le b$ and $c\le d$. If $a=c$, then $b=d$, contradiction. If $a=d$, then $b=c$, and since $a\le b$ and $c\le d$, this again forces $(a,b)=(c,d)$. The other possibilities are symmetric. Hence distinct unordered representations are disjoint. $\square$

Now colour each element of $A$ independently red or blue with probability $1/2$ each. Let $A_1$ be the red elements and $A_2$ the blue elements.

Fix $n\in S_R$. By definition $n$ has at least $R$ distinct unordered representations \[ n=a_1+b_1=\cdots=a_R+b_R, \] and by Lemma 741.2 the pairs $\{a_i,b_i\}$ are pairwise disjoint. For each $i$, let $E_i^{(1)}$ be the event that the $i$-th representation is monochromatic red, and let $E_i^{(2)}$ be the event that it is monochromatic blue.

If $a_i\neq b_i$, then \[ \mathbb P(E_i^{(1)})=\mathbb P(E_i^{(2)})=\frac14. \] If $a_i=b_i$, then the probability is $1/2$ for each colour, which is only better for us. Therefore, in every case, \[ \mathbb P\left(n\notin A_1+A_1\right)\le \left(\frac34\right)^R, \qquad \mathbb P\left(n\notin A_2+A_2\right)\le \left(\frac34\right)^R. \] Hence, for \[ p_R:=1-\left(\frac34\right)^R, \] we have \[ \mathbb P\left(n\in A_1+A_1\right)\ge p_R, \qquad \mathbb P\left(n\in A_2+A_2\right)\ge p_R. \]

For $N\ge 1$, define \[ X_N:=\frac1N\sum_{\substack{n\le N\\ n\in S_R}} \left(1_{n\in A_1+A_1}+1_{n\in A_2+A_2}\right). \] Taking expectations and using the bound above, \[ \mathbb E[X_N]\ge \frac{2p_R}{N}|S_R\cap[1,N]|. \]

Choose a sequence $N_j\to\infty$ such that \[ \frac{|S_R\cap[1,N_j]|}{N_j}\to \delta=\overline d(S_R). \] Then \[ \limsup_{j\to\infty}\mathbb E[X_{N_j}]\ge 2p_R\delta. \] Because $0\le X_{N_j}\le 2$, reverse Fatou gives \[ \mathbb E\!\left[\limsup_{j\to\infty}X_{N_j}\right] \ge \limsup_{j\to\infty}\mathbb E[X_{N_j}] \ge 2p_R\delta. \] Therefore there exists at least one colouring for which \[ \limsup_{j\to\infty}X_{N_j}\ge 2p_R\delta. \]

Fix such a colouring. Set \[ R_j:=\frac1{N_j}\left|S_R\cap(A_1+A_1)\cap[1,N_j]\right|, \qquad B_j:=\frac1{N_j}\left|S_R\cap(A_2+A_2)\cap[1,N_j]\right|. \] Then $X_{N_j}=R_j+B_j$, so \[ \limsup_{j\to\infty}(R_j+B_j)\ge 2p_R\delta. \] Let \[ r:=\limsup_{j\to\infty}R_j,\qquad b:=\limsup_{j\to\infty}B_j. \] Since $\limsup(x_j+y_j)\le \limsup x_j+\limsup y_j$, we get \[ r+b\ge 2p_R\delta. \] Also $r\le \delta$ and $b\le \delta$, because $R_j,B_j\le |S_R\cap[1,N_j]|/N_j$. If, say, $r<(2p_R-1)\delta$, then \[ b>2p_R\delta-r>\delta, \] contradiction. Hence \[ r\ge (2p_R-1)\delta,\qquad b\ge (2p_R-1)\delta. \] Since $2p_R-1=1-2(3/4)^R$, we conclude \[ r\ge \left(1-2(3/4)^R\right)\delta, \qquad b\ge \left(1-2(3/4)^R\right)\delta. \] Finally, \[ \overline d(A_1+A_1)\ge r,\qquad \overline d(A_2+A_2)\ge b, \] because $S_R\cap(A_i+A_i)\subseteq A_i+A_i$. This proves Theorem 741.1. $\square$

Corollary 741.3. If Problem 741$Q1$ had a counterexample, then \[ \overline d\left(\{n:r_A^{\ast}(n)\ge 3\}\right)=0. \]

Proof. Apply Theorem 741.1 with $R=3$. $\square$

6) ADVERSARIAL VERIFICATION

• Diagonal representations. If $n=2a$ has the representation $(a,a)$, then the monochromatic probability is $1/2$, not $1/4$. I used only the weaker upper bound $3/4$ for the failure probability, so this causes no problem.
• Independence. The only independence used is across the $R$ chosen representations of a fixed $n$. Lemma 741.2 guarantees disjointness, so the colour events are independent.
• A single colouring for infinitely many $N_j$. I did not optimize separately for each $N_j$; the reverse-Fatou argument produces one colouring whose limsup is large.
• Upper density rather than lower density. The argument only uses a subsequence $N_j$ witnessing $\overline d(S_R)$, so upper density is the correct notion here.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

Round-2 proves a genuine new theorem:

If a positive-density set of sums has at least $3$ distinct unordered representations each, then Problem 741$Q1$ has a positive answer.

Equivalently, any counterexample must be essentially near-Sidon on a positive-density set of represented integers: the set of $n$ with at least $3$ unordered representations must have upper density $0$.

This is a substantive obstruction that was absent in Round-1.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 45%

9) REFERENCES

• T. F. Bloom, Erdős Problem #741, erdosproblems.com.

---

Problem 741 (Burr--Erdős): splitting a set whose sumset has positive density

1) FORMAL RESTATEMENT

Let $\mathbb{N}:=\{1,2,3,\dots\}$ and for $A\subseteq \mathbb{N}$ write \[ A+A := \{a+a': a,a'\in A\}. \] For a set $S\subseteq \mathbb{N}$ define its upper and lower (asymptotic) densities by \[ \overline d(S):=\limsup_{N\to\infty}\frac{|S\cap [1,N]|}{N}, \qquad \underline d(S):=\liminf_{N\to\infty}\frac{|S\cap [1,N]|}{N}. \]

$Q1$ Assume $\overline d(A+A)>0$. Must there exist a partition $A=A_1\sqcup A_2$ such that \[ \overline d(A_1+A_1)>0 \quad\text{and}\quad \overline d(A_2+A_2)>0? \]

$Q2$ Call $A\subseteq \mathbb{N}$ an asymptotic basis of order $2$ if $A+A$ contains all sufficiently large integers. Is there such a basis $A$ with the Ramsey-type property that for every partition $A=A_1\sqcup A_2$, the sets $A_1+A_1$ and $A_2+A_2$ cannot both have bounded gaps? (Here "bounded gaps" means $S\subseteq \mathbb{N}$ is syndetic: $\exists L$ such that every interval of length $L$ contains an element of $S$.)

2) QUICK LITERATURE/CONTEXT CHECK

Web browsing available? YES.

• The problem is recorded as open on erdosproblems.com (Problem 741), and is attributed to Burr and Erdős.
• A related (stronger) direction in additive number theory: if $A$ is an asymptotic basis of order $2$ with sufficiently large representation function $r_{2,A}(n)$, then $A$ can be partitioned into two disjoint asymptotic bases (Erdős--Nathanson; see also Nathanson's survey on extremal problems for sumsets).

3) ATTACK PLAN

• Positive direction: Try to 2-color $A$ so that many sums $n$ have a monochromatic representation in each color. A natural attempt is a random 2-coloring plus a second-moment/LLL argument on the events $n\notin A_i+A_i$. This is more plausible when many $n$ have many representations $n=a+a'$ with $a,a'\in A$.
• Negative direction: Try to construct $A$ with $\overline d(A+A)>0$ but whose sum representations are so "fragile" that any partition destroys density of one monochromatic sumset. Such an $A$ would likely have very small representation counts $r_{A}(n)$ on a positive-density subset of $A+A$.
• Intermediate reductions: Identify extra hypotheses (e.g. $d(A)>0$, or large $r_A(n)$ on a dense set) under which $Q1$ is provable; and identify structural obstructions for $Q2$.

4) WORK

4.1 A warm-up case where $Q1$ is easy.

If $A$ itself has positive lower density, then one can force a partition with both monochromatic sumsets having positive density.

Lemma 4.1. If $\underline d(A)=\alpha>0$, then there exists a partition $A=A_1\sqcup A_2$ with $\underline d(A_1)\ge \alpha/3$ and $\underline d(A_2)\ge \alpha/3$. Consequently, \[ \underline d(A_1+A_1)>0 \quad\text{and}\quad \underline d(A_2+A_2)>0. \]

Sketch of proof. $1$ Build $A_1$ by a block construction: choose disjoint intervals $I_k=[N_k+1,N_k+M_k]$ with $M_k\to\infty$ and on each block select about one third of the points of $A\cap I_k$ into $A_1$, putting the rest in $A_2$. By arranging the blocks so that $|A\cap I_k|$ is close to $\alpha M_k$ (possible along a subsequence witnessing the liminf), one can ensure $\underline d(A_i)\ge \alpha/3$.

$2$ For any finite $B\subseteq [1,N]$, one has the elementary inequality in the integers: \[ |B+B|\ge 2|B|-1, \] because the sums $b_{\min}+B$ and $b_{\max}+B$ already cover an interval of length $|B|$ and these translate-intervals overlap in at most one point. Applying this with $B=A_i\cap[1,N]$ gives \[ |(A_i+A_i)\cap [2,2N]|\ge 2|A_i\cap[1,N]|-1. \] Divide by $2N$ and take $\liminf_{N\to\infty}$ to deduce $\underline d(A_i+A_i)\ge \underline d(A_i)>0$. $\square$

This does not resolve $Q1$, because $\overline d(A+A)>0$ does not force $\underline d(A)>0$ (e.g. one can have $|A\cap[1,N]|\asymp \sqrt N$).

4.2 Representation-count heuristics for the hard case.

Write the (ordered) representation function \[ r_A(n):=(\mathbf 1_A * \mathbf 1_A)(n)=|\{(a,a')\in A^2:\ a+a'=n\}|. \] If a positive-density set of $n$ have many representations, then a random 2-coloring of $A$ should, heuristically, leave many $n$ with at least one red-red representation and many $n$ with at least one blue-blue representation. However, without quantitative lower bounds on $r_A(n)$ on a positive-density set, a clean averaging argument seems out of reach.

4.3 Link to partitioning bases (motivation for Q2).

If $A$ is an asymptotic basis of order $2$ and $r_A(n)$ grows at least like a constant multiple of $\log n$ for all sufficiently large $n$, then one can partition $A$ into two disjoint asymptotic bases (Erdős--Nathanson-type results). In that regime, for that particular partition both $A_1+A_1$ and $A_2+A_2$ are cofinite, hence have bounded gaps. Therefore any example for $Q2$ must come from a basis with small (or highly irregular) representation function.

4.4 What a counterexample to $Q1$ would have to look like.

A counterexample would be a set $A$ with $\overline d(A+A)>0$ but for every $2$-coloring of $A$ (at the level of a partition) at least one monochromatic sumset has density $0$. Such a phenomenon would suggest that the sumset $A+A$ is "mostly" generated by cross-color pairs, so one would need $A$ where many sums are forced to use pairs from two different substructures. No explicit construction of this type is currently known to me.

5) VERIFICATION

• Checked that Lemma 4.1 uses only the elementary finite-set inequality $|B+B|\ge 2|B|-1$.
• The block-selection argument is standard for producing subsets of prescribed lower density along a liminf subsequence; it does not require any additivity structure.
• No step above claims to solve the Burr--Erdős question; it only isolates an easy case and clarifies why the sparse case is hard.

6) FINAL

UNRESOLVED.

• What I have: $Q1$ holds if $A$ itself has positive lower density (Lemma 4.1). For asymptotic bases with sufficiently large representation function, known results allow partitions into two bases, so $Q2$ fails in that regime.
• Where it breaks: When $A$ has density $0$ but $A+A$ has positive density, current arguments do not control how monochromatic representations distribute under a partition.
• Next moves:
  1. Prove a robust "many representations on a dense set" lemma from $\overline d(A+A)>0$ (or show this is false).
  2. Try a probabilistic coloring plus second-moment/LLL on a thinned set of sums where $r_A(n)$ is large.
  3. For $Q2$, attempt to build an asymptotic basis with representation function concentrated on cross-block pairs, forcing long gaps in at least one monochromatic sumset under any 2-coloring.
• Minimal lemma that would settle $Q1$ (one possible route): Find a constant $\eta>0$ and a subset $S\subseteq A+A$ with $\overline d(S)>0$ such that every $n\in S$ has at least $R$ pairwise disjoint representations $n=a_i+a_i'$ with $(a_i,a_i')$ using distinct elements of $A$. Then a random 2-coloring would make $n\in A_1+A_1$ with probability $\ge 1-(3/4)^R$ (similarly for $A_2$), and taking $R$ large would force positive density in both colors.

7) COMPLETION

COMPLETION: 25% (easy dense case + structural discussion; main problem remains open).

---