Erdős Problem #868

Erdős Problem 868: a checked attempt

GPT_6_Astra_Ultra

24 September 2026

Statement and current resolution

If an asymptotic additive basis $A\subseteq\mathbb N$ of order two has representation function tending to infinity, must it contain a minimal asymptotic basis? What if its representation function is at least $\varepsilon\log n$? Both assertions are false, by Daniel Larsen and Michael Larsen, Robust additive bases without minimal subbases, https://raw.githubusercontent.com/Larsen-Daniel/Erdos-868/main/868.pdf. This attempt proves the obstruction mechanism and a logarithmic random-basis estimate, but does not reconstruct the probabilistic surgery needed to combine them. Its proof status is therefore unresolved, despite the known negative resolution.

We use unordered representations $r_A(n)=|\{(a,b)\in A^2:a\le b,\ a+b=n\}|$. The ordered convention in the question lies between $r_A(n)$ and $2r_A(n)$ and gives the same divergence and positive-logarithmic-lower-bound questions.

A proved obstruction criterion

Suppose the sufficiently large integers are covered by two sets $B,C$, and $A$ is a basis with the following properties.

1. For each sufficiently large $c\in C$ choose at least three distinct unordered representations $c=a_i+a_i'$ in $A$. For every set $S$ formed by choosing one endpoint from all but one of these pairs, there is a witness $b=b(c,S)\in B$, with $b>2\max S$, such that the complete list of representations of $b$ in $A$ is $s+(b-s)$, $s\in S$.
2. The witnesses $b(c,S)$ tend to infinity uniformly as $c\to\infty$.
3. The smallest summand in any representation in $A$ of $b\in B$ tends to infinity as $b\to\infty$.

Then $A$ has no minimal subbasis. To prove this, let $D\subseteq A$ be any subbasis. If a large $c\in C$ had at most one representation in $D$, from every other selected representation choose an endpoint outside $D$. This gives a set $S\subseteq A\setminus D$, and therefore a witness $b$ with no representation in $D$, a contradiction when $c$ is large. Thus $r_D(c)\ge2$ eventually on $C$. Deleting any fixed $d\in D$ destroys at most one unordered representation of any integer, so $D\setminus\{d\}$ still represents the large members of $C$. By property 3 it also still represents the large members of $B$. It is consequently a basis, and $D$ is not minimal.

For a fixed sum, distinct unordered representation pairs are disjoint as sets of summands, apart from the harmless singleton diagonal pair. Thus the endpoint selections in this criterion are well defined; they do not tacitly require independent choices among overlapping pairs. The condition $b>2\max S$ makes their newly planted witness representations distinct.

Why the logarithmic scale is compatible with a sparse basis

Here is a complete elementary probability calculation. Select each integer $x$ independently with probability \[ p_x=\min\{1,K\sqrt{\log(x+1)/x}\}, \] where $K$ is a sufficiently large constant. For a large $n$, use the pairs $\{a,n-a\}$ with $\lceil n/3\rceil\le a< n/2$. These are disjoint, so their inclusion indicators are independent. There are at least $n/7$ such pairs, and each is included with probability at least $K^2\log n/(2n)$ once $n$ is large. Their expected count is at least $K^2\log n/14$. The elementary Chernoff estimate $\mathbb P(X<\mathbb EX/2)\le\exp(-\mathbb EX/8)$ gives \[ \mathbb P\left(r_A(n)<K^2\log n/28\right)\le n^{-K^2/112}. \] Choosing, for example, $K=40$ makes these probabilities summable. The union bound on tails (equivalently the first Borel--Cantelli lemma) shows that almost surely $r_A(n)\gg\log n$ for every sufficiently large $n$. Also \[ \mathbb E|A\cap[1,X]|\ll_K\sqrt{X\log(X+1)}: \] use $p_x\le K\sqrt{\log(X+1)}x^{-1/2}$ and $\sum_{x\le X}x^{-1/2}\le2\sqrt X$. Thus a logarithmic representation lower bound is naturally available before surgery.

The precise missing step

The random basis just constructed has not been shown to satisfy the obstruction criterion. Planting $b-S$ may introduce unwanted representations of other witnesses; deleting old representations of $b$ may destroy too many representations elsewhere. Larsen--Larsen address exactly these interactions on intervals $[X_j,X_{j+1})$, $X_j=2^{2^j}$: their Proposition 5 bounds simultaneous additive collisions, Lemma 7 bounds damage by $37$ representations, and Lemmas 9--10 provide the coverage and exact witness properties. Their construction gives the positive constant $15/(512\log2)$ in the unordered convention. These surgery estimates are reported as source results, not proved or silently assumed in this attempt.

The established progress is the complete implication from the witness mechanism to absence of minimal subbases, including deletion and quantifier checks, and the separate logarithmic random-basis estimate. The unproved compatibility of the two constructions prevents this file from claiming a complete independent counterexample.

Completion rate estimate: 65%.

FORMAL RESTATEMENT. Let $A\subseteq\mathbb{N}$ (here $\mathbb{N}=\{0,1,2,\dots\}$ or $\{1,2,3,\dots\}$; the distinction does not affect "all sufficiently large integers"). Say $A$ is an asymptotic additive basis of order $2$ if there exists $n_0$ such that every integer $n\ge n_0$ can be written as $n=a+a'$ with $a,a'\in A$. Let \[ r_A(n):=(1_A*1_A)(n)=\left|\{(a,a')\in A\times A: a+a'=n\}\right|, \] (the ordered representation function). A subset $B\subseteq A$ is a minimal asymptotic basis of order $2$ if $B$ is an asymptotic basis of order $2$ and for every $b\in B$, the set $(B\setminus\{b\})+(B\setminus\{b\})$ fails to contain infinitely many integers.

Question: If $A$ is an asymptotic basis of order $2$ and $r_A(n)\to\infty$ as $n\to\infty$, must $A$ contain a minimal asymptotic basis of order $2$? What if $r_A(n)\ge \varepsilon\log n$ for all large $n$?

QUICK LITERATURE/CONTEXT CHECK. The problem statement records:

• Erdős--Nathanson $1979$ proved the conclusion under the stronger hypothesis $r_A(n)>(\log(4/3))^{-1}\log n$ for all large $n$.
• Härtter $1956$ and Nathanson $1974$ constructed additive bases containing no minimal additive bases.
• Erdős--Nathanson $1989$ constructed, for any fixed $t$, bases $A$ with $r_A(n)\ge t$ for all large $n$ but containing no minimal asymptotic basis of order $2$.

(Per the project integrity constraints, I do not use or assert further literature beyond what is in the problem text.)

ATTACK PLAN.

• Prove basic implications of $r_A(n)\to\infty$, e.g. robustness under deleting finitely many elements.
• Try to formalize a Zorn/chain-minimization approach: show every descending chain of asymptotic bases inside $A$ has an intersection that is still an asymptotic basis, which would yield a minimal element.
• Disproof track: attempt to amplify known constructions with bounded $r_A(n)$ to force $r_A(n)\to\infty$ while still forbidding minimal subbases.

I only establish basic robustness lemmas; I do not resolve existence of a minimal subbasis.

WORK.

Lemma 868.1 (Finite deletions preserve the basis property under $r_A(n)\to\infty$). Assume $A$ is an asymptotic basis of order $2$ and $r_A(n)\to\infty$ as $n\to\infty$. Then for every finite set $F\subseteq A$, the set $A\setminus F$ is also an asymptotic basis of order $2$.

Proof. Fix a finite $F\subseteq A$ and put $m:=|F|$. For each integer $n$, let $R(n)$ be the set of ordered representations $(a,a')\in A\times A$ with $a+a'=n$, so $|R(n)|=r_A(n)$. Let $R_F(n)\subseteq R(n)$ be those representations that use at least one summand from $F$. If $f\in F$, then in an ordered representation $(a,a')$ of $n$ the condition $a=f$ forces $a'=n-f$ uniquely, and likewise $a'=f$ forces $a=n-f$ uniquely. Therefore, for each $n$, \[ |R_F(n)|\le 2m. \] Since $r_A(n)\to\infty$, there exists $n_1$ such that for all $n\ge n_1$, $r_A(n)>2m$. For such $n$, we have $|R(n)\setminus R_F(n)|\ge r_A(n)-2m\ge 1$, so there exists an ordered representation $(a,a')$ of $n$ with $a,a'\notin F$. Thus $n\in (A\setminus F)+(A\setminus F)$ for all $n\ge n_1$, i.e. $A\setminus F$ is an asymptotic basis of order $2$. $\square$

Lemma 868.2 (Minimality $\Leftrightarrow$ infinitely many "forced" representations). Let $B$ be an asymptotic basis of order $2$. Then $B$ is minimal (asymptotic) if and only if for every $b\in B$ there are infinitely many integers $n$ such that every representation of $n$ as $n=x+y$ with $x,y\in B$ satisfies $x=b$ or $y=b$.

Proof. Fix $b\in B$. If $B$ is minimal, then by definition $B\setminus\{b\}$ fails to represent infinitely many integers $n$. For each such $n$, every representation of $n$ using $B$ must involve $b$ (otherwise $n$ would still be representable after deleting $b$). Thus the "forced representation" property holds for infinitely many $n$.

Conversely, suppose the forced-representation property holds for $b$ on an infinite set $S\subseteq\mathbb{N}$. Then for each $n\in S$, there is no representation of $n$ using only $B\setminus\{b\}$, so $n\notin (B\setminus\{b\})+(B\setminus\{b\})$. Hence deleting $b$ creates infinitely many missing integers, so $B$ is minimal. $\square$

FAST REALITY CHECK (sanity examples).

• If $A=\mathbb{N}$, then $r_A(n)=n+1\to\infty$, and Lemma 868.1 correctly says deleting finitely many elements preserves being an asymptotic basis.
• Lemma 868.2 matches the intuition: in a minimal basis, each element must be essential for infinitely many target integers.

VERIFICATION.

• Lemma 868.1: the only nontrivial estimate is $|R_F(n)|\le 2|F|$, justified by the uniqueness of a partner for a fixed summand in an ordered sum representation.
• Lemma 868.2: both implications are direct unpacking of the definition, with no hidden compactness assumptions.

FINAL. UNRESOLVED

(i) Strongest proved partial result. If $A$ is an asymptotic basis of order 2 and $r_A(n)\to\infty$, then $A$ is robust under deleting any finite subset (Lemma 868.1). Minimality can be characterized by having infinitely many integers whose representations are forced to use each given element (Lemma 868.2).

(ii) First gap (crisp). Show that the family of asymptotic bases contained in $A$ has a minimal element under inclusion, e.g. by proving that the intersection of any descending chain of such bases is still an asymptotic basis. This is exactly where a Zorn-type approach would need a verified chain-intersection property.

(iii) Top 3 next moves.

• Attempt to prove a chain-intersection lemma under quantitative growth (e.g. $r_A(n)\ge \varepsilon\log n$): if $A=A_0\supseteq A_1\supseteq A_2\supseteq\cdots$ is a nested sequence of asymptotic bases with each $A_{m+1}=A_m\setminus\{a_m\}$, show $\bigcap_m A_m$ still represents all large $n$.
• Try to adapt (or reprove from scratch) the Erdős--Nathanson threshold $(\log(4/3))^{-1}\log n$ as an explicit "sufficient slack" for iterative deletions.
• Construct candidate counterexamples by building $A$ in blocks so that $r_A(n)$ grows slowly, but every purported subbasis can be thinned further without losing the basis property.

(iv) Minimal counterexample structure. A counterexample would be an asymptotic basis $A$ with $r_A(n)\to\infty$ but such that for every $B\subseteq A$ which is an asymptotic basis, there exists $b\in B$ with $B\setminus\{b\}$ still an asymptotic basis (so no minimal element). Such an $A$ would need representations to be plentiful yet "spread" so that no single element is forced infinitely often inside any subbasis.