Erdős Problem #330

Erdős Problem #330: positive-density private sums in a minimal basis

1) Statement and density convention

For an anchor $a\in A$, a private sum is an integer in \[(A+A)\setminus((A\setminus\{a\})+(A\setminus\{a\})). \] Positive upper density of private sums would imply that deleting $a$ destroys the basis property. The difficulty is to achieve this for every anchor while still covering all sufficiently large integers.

2) A finite private-sum block with a positive density ratio

Indeed, $F+F\subseteq[2,2M]$ lies below $W$, whereas $B+B$ lies at or above $2T$, above $W$. Any other representation would therefore be $w=c+b'$ with $c\in F$, $b'\in B$. Since $w\equiv0\pmod p$ and $b'\equiv-a\pmod p$, it would force $c\equiv a\pmod p$. The elements of $F$ are between 1 and $M<p$, so $c=a$ and then $b'=w-a$. In particular no diagonal exception has been omitted.

The interval defining $B$ has $T-a$ integers, so \[|W|=|B|\ge\frac{T-a}{p}-1. \] For fixed $F,a,p$, arbitrarily large choices of $T$ give \[\frac{|W|}{2T-1}\ge\frac1{2p}-o(1). \] The new basis elements themselves have the same finite-scale count. Any future elements strictly greater than $2T-1$ cannot occur in a representation of a member of $W$, so they preserve all of these witnesses.

3) Why this lemma is not yet the infinite construction

There is a second independent issue: adding sparse distant blocks does not guarantee that every sufficiently large integer becomes a two-term sum. Filling those gaps can create alternative representations of the planned witnesses. Thus preserving finitely many witnesses by moving future elements beyond them is valid, but does not alone establish either positive upper density for every anchor's full witness set or the asymptotic basis property.

4) A necessary restriction on lower density

5) Outcome and sources

Source: https://www.erdosproblems.com/330 and its discussion, checked 23 September 2026. The current source reports a construction by GPT 5.5 Pro prompted by Turturean, and a formalized resolution. This text does not reproduce that construction or claim to have verified its Lean proof. Its modular witness calculation is partial progress, not a new solution.

The estimate is a subjective assessment of the proved construction ingredients, not a probability.

6) COMPLETION ESTIMATE

1) FORMAL RESTATEMENT

A set $A\subseteq\mathbb N$ is an additive basis of order $2$ if there exists $N_0$ such that every $n\ge N_0$ can be written as $n=a+a'$ with $a,a'\in A$.

It is minimal (as an order-2 basis) if no proper subset of $A$ is an order-2 basis; equivalently, for every $a\in A$, the set $A\setminus\{a\}$ is not an order-2 basis.

Density convention. For $S\subseteq\mathbb N$ define the upper asymptotic density \[ \overline d(S):=\limsup_{N\to\infty}\frac{|S\cap\{1,\dots,N\}|}{N}. \]

For $a\in A$, define the "essential set" \[ E_a:=\{n\in\mathbb N: n\text{ cannot be represented as }b+c\text{ with }b,c\in A\setminus\{a\}\}. \] So $E_a$ is the set of integers whose representations as a sum of two elements of $A$ necessarily use the element $a$.

Problem: Does there exist a minimal order-2 basis $A$ with positive density (say $\overline d(A)>0$) such that for every $a\in A$, \[ \overline d(E_a)>0? \]

2) QUICK LITERATURE/CONTEXT CHECK

No external results are used; the statement attributes the question to Erdős and Nathanson.

3) ATTACK PLAN

I cannot construct such a set. I will instead:

$1$ Prove a clean equivalence between minimality and the infinitude of each $E_a$.

$2$ Give a concrete positive-density basis example $A=2\mathbb N\cup\{1\}$ and compute $E_a$ for different $a\in A$ to show why the requirement "$\overline d(E_a)>0$ for all $a$" is strong.

4) WORK

PHASE 1: FAST REALITY CHECK / SANITY EXAMPLE

Let \[ A:=2\mathbb N\cup\{1\}=\{1,2,4,6,8,\dots\}. \] Then $\overline d(A)=1/2$. Every sufficiently large even $n$ is a sum of two even numbers from $A$, and every sufficiently large odd $n$ is $1+$even. So $A$ is an order-2 basis of positive density.

However, as shown in Lemma 330.2, not every element is "density-essential": $E_1$ has density $1/2$, but $E_{2t}$ has density $0$ for each even element $2t$.

Lemma 330.1 (minimality $\Leftrightarrow$ every $E_a$ is infinite).

Let $A$ be an order-2 basis. Then $A$ is minimal if and only if $E_a$ is infinite for every $a\in A$.

Proof. ($\Rightarrow$) If $A$ is minimal, then for each $a\in A$ the set $A\setminus\{a\}$ is not an order-2 basis. So for each $a$ there are infinitely many integers that are not representable as a sum of two elements of $A\setminus\{a\}$. By definition, those integers form $E_a$. Thus $E_a$ is infinite.

($\Leftarrow$) Conversely, if $E_a$ is infinite for every $a\in A$, then removing any $a$ destroys the basis property (since infinitely many integers fail to be representable). Hence no proper subset obtained by deleting one element is a basis, so $A$ is minimal. $\square$

Lemma 330.2 (in the example $A=2\mathbb N\cup\{1\}$, only $1$ is density-essential).

Let $A=2\mathbb N\cup\{1\}$.

(a) $E_1$ is exactly the set of odd integers, so $\overline d(E_1)=1/2$.

(b) For any even element $2t\in A$, the set $E_{2t}$ is finite (hence $\overline d(E_{2t})=0$).

Proof. (a) If we remove $1$, the remaining set is $2\mathbb N$. Sums of two even numbers are even, so no odd integer is representable. Thus every odd integer lies in $E_1$. Conversely, every sufficiently large even integer is representable as a sum of two even numbers, so even integers are not in $E_1$ (beyond a finite initial segment that is irrelevant for density). Hence $E_1$ is the odd integers and has upper density $1/2$.

(b) Fix $t\ge 1$ and remove the element $2t$. We show that every sufficiently large even integer $n$ is still representable as a sum of two even elements of $A\setminus\{2t\}$. Indeed, for any even $n\ge 4t+6$, we have $n-2\ge 4t+4$ and $n-2\neq 2t$. Then \[ n = 2 + (n-2), \] where both summands are even and belong to $A\setminus\{2t\}$ (since $2\neq 2t$ and $n-2\neq 2t$ by the inequality above). Therefore, all sufficiently large even $n$ are not in $E_{2t}$. Also, all sufficiently large odd $n$ are representable as $1+$even without needing the removed even element. So $E_{2t}$ is contained in a finite initial segment, hence is finite and has density $0$. $\square$

5) VERIFICATION

-- Lemma 330.1: uses only definitions; "not a basis" means infinitely many failures, which is exactly infinitude of $E_a$.

-- Lemma 330.2(b): the representation $n=2+(n-2)$ avoids $2t$ for all $n\ge 4t+6$; the inequality ensures $n-2\ge 2t+?$, so it cannot equal $2t$.

6) FINAL

UNRESOLVED

(i) Strongest fully proved partial result obtained here.

* Minimality is equivalent to each $E_a$ being infinite (Lemma 330.1). * Example analysis: a positive-density basis can have some elements with $\overline d(E_a)=0$ (Lemma 330.2), showing the extra requirement "$\overline d(E_a)>0$ for all $a$" is genuinely stronger than minimality.

(ii) Exact first gap.

Construct (or rule out) a minimal order-2 basis $A$ with positive density such that every element is essential for a positive-density set of integers.

(iii) Top 3 next moves (concrete targets).

1. Attempt a construction by partitioning $\mathbb N$ into disjoint positive-density sets $E_{a_i}$ of decreasing densities and forcing each $a_i$ to be necessary for representing $E_{a_i}$. 2. Prove an impossibility theorem: show that in any positive-density basis, there must exist some $a\in A$ with $\overline d(E_a)=0$. 3. Study known constructions of minimal bases (if available) and compute/estimate $\overline d(E_a)$ for typical elements.

(iv) What a minimal counterexample would likely look like.

If such an $A$ does not exist, then every minimal basis of positive density would necessarily contain at least one "dispensable in density" element $a$ with $\overline d(E_a)=0$. A minimal counterexample (to a positive answer) would likely be a very rigid minimal basis where each element controls a positive-density residue-class-type obstruction.