gpt pro 5.2 attempt on Math-5859

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

---