Erdős Problem #326

Erdős Problem 326: a checked attempt

GPT_6_Astra_Ultra

25 September 2026

Current statement and scope

The earlier GPT-5.2 draft instead asked whether every basis has an irregular subbasis. That is not the current statement. We prove a necessary restriction $0<c\le\pi/8$, an exact unique-representation criterion for minimality, and consequences at the endpoint. Existence or nonexistence of the requested basis remains unresolved here. These are partial deductions, not a new solution or a reconstruction of Cassels' nonminimal example.

Basic count and the sharper regular-growth restriction

Now assume $a_k\sim ck^2$ with $c>0$. Let \[ R(x)=\#\{(i,j):a_i+a_j\le x\} \] count ordered pairs. We claim \[ R(x)\sim\frac{\pi}{4c}x. \tag{1} \] For any $0<\eta<c$, all but finitely many indices satisfy $(c-\eta)j^2\le a_j\le(c+\eta)j^2$. Pairs involving one of the exceptional indices contribute $O_\eta(\sqrt x)$, since $A(x)=O(\sqrt x)$. For the other pairs, sandwich $R(x)$ between the lattice counts \[ \#\{i,j\ge1:i^2+j^2\le x/(c+\eta)\} \quad\hbox{and}\quad \#\{i,j\ge1:i^2+j^2\le x/(c-\eta)\}, \] up to $O_\eta(\sqrt x)$. The count in a quarter disk of radius $T$ is $\pi T^2/4+O(T)$: unit squares give inner and outer disks whose radii differ by at most $\sqrt2$. Dividing by $x$, taking limits and then letting $\eta\downarrow0$ proves $1$.

Let $r_A(n)$ count unordered representations $n=a_i+a_j$ with $i\le j$. The diagonal pairs number $A(x/2)=O(\sqrt x)$, so $1$ implies \[ \sum_{n\le x}r_A(n)\sim\frac{\pi}{8c}x. \tag{2} \] A basis has $r_A(n)\ge1$ for all sufficiently large $n$. Therefore $\pi/(8c)\ge1$, proving the sharper necessary condition \[ 0<c\le\frac\pi8. \tag{3} \]

An exact criterion for minimality

For a fixed $a$, the witnesses in $4$ up to $x$ number at most $A(x-a)=O(\sqrt x)$ under regular growth. Thus minimality can depend on infinitely many witnesses of density zero. More generally, deleting a fixed finite set $F\subset A$ creates at most $|F|A(x)=O_F(\sqrt x)$ new failures up to $x$, because any lost representation uses an element of $F$. Such a deletion still represents a density-one set, but this does not make it an asymptotic basis, which requires only finitely many failures.

The endpoint and the remaining gap

The averaging restriction $3$ and the exact criterion $4$ are both necessary, but neither constructs a basis satisfying both nor proves that they are incompatible. The known existence of a regularly growing basis without the minimality requirement does not remove this gap. No thinning argument preserving all sufficiently large representations is supplied here.

Completion rate estimate: 30%.

1) FORMAL RESTATEMENT

A set $A\subseteq\mathbb N$ is an additive basis of order $2$ (an asymptotic basis of order $2$) if there exists an integer $N_0$ such that for every integer $n\ge N_0$ there exist $a,a'\in A$ with \[ n=a+a'. \]

Given such an $A$, the problem asks whether there must exist a subset \[ B=\{b_1<b_2<\cdots\}\subseteq A \] which is also an additive basis of order $2$ and for which the limit \[ \lim_{k\to\infty}\frac{b_k}{k^2} \] does not exist.

Edge cases. Any basis $A$ is infinite. The ratio $b_k/k^2$ is always nonnegative.

2) QUICK LITERATURE/CONTEXT CHECK

I use only what is in the statement: Erdős asked the stronger question with $B=A$, and Cassels produced a counterexample (a basis $A$ for which $a_k/k^2$ does converge). I do not use any other external facts.

3) ATTACK PLAN

I do not see a complete proof or disproof. I will provide basic necessary growth constraints for any order-2 basis, since the question is about the scale $k^2$.

Specifically:

$1$ Show that any basis $A$ must satisfy a lower bound on its counting function $A(x)=|A\cap\{1,\dots,x\}|$ of order $\gg\sqrt{x}$ for large $x$.

$2$ Convert that into an upper bound $a_k\ll k^2$ for the $k$th element $a_k$ of $A$.

These are problem-specific lemmas with complete proofs.

4) WORK

PHASE 1: FAST REALITY CHECK

There is no meaningful finite brute-force test for an infinite asymptotic basis. As a sanity check, note:

* $A=2\mathbb N\cup\{1\}$ is an order-2 basis (all large even numbers are even+even; all large odd numbers are $1+$even). * Cassels' example (mentioned in the statement) shows that the limit $a_k/k^2$ can exist for some bases.

Lemma 326.1 (counting function lower bound for any order-2 basis).

Let $A\subseteq\mathbb N$ be an additive basis of order $2$. Then there exists $X_0$ such that for all $x\ge X_0$, \[ |A\cap\{1,2,\dots,x\}|\ \ge\ \sqrt{\frac{x}{2}}. \]

Proof. Because $A$ is a basis of order $2$, there exists $N_0$ such that every $n\ge N_0$ can be written as $n=a+a'$ with $a,a'\in A$. Fix $T\ge N_0$. Then every integer $n\in[T,2T]$ can be written as $n=a+a'$ with $a,a'\in A$. In such a representation, necessarily $a\le n\le 2T$ and $a'\le n\le 2T$. So $a,a'\in A\cap\{1,\dots,2T\}$. Hence \[ [T,2T]\cap\mathbb Z \subseteq (A\cap\{1,\dots,2T\}) + (A\cap\{1,\dots,2T\}). \] The set on the right is the set of all sums of two elements from $A\cap\{1,\dots,2T\}$. The number of distinct sums is at most the number of ordered pairs, i.e. \[ \left| (A\cap\{1,\dots,2T\}) + (A\cap\{1,\dots,2T\}) \right|\ \le\ |A\cap\{1,\dots,2T\}|^2. \] But the left side contains all integers in $[T,2T]$, which are $T+1$ distinct integers. Therefore \[ |A\cap\{1,\dots,2T\}|^2 \ge T+1. \] Taking square roots gives \[ |A\cap\{1,\dots,2T\}|\ge \sqrt{T+1} \ge \sqrt{T}. \] Now set $x=2T$. For $x\ge 2N_0$ we have $T=x/2\ge N_0$, and thus \[ |A\cap\{1,\dots,x\}|\ge \sqrt{x/2}. \] So the claimed inequality holds for all $x\ge X_0:=2N_0$. $\square$

Lemma 326.2 (quadratic upper bound on the $k$th element of a basis).

Let $A\subseteq\mathbb N$ be an additive basis of order $2$, and enumerate it as $a_1<a_2<\cdots$. Then there exists $k_0$ such that for all $k\ge k_0$, \[ a_k\le 2k^2. \]

Proof. Let $X_0$ be as in Lemma 326.1. Take any $k$ such that $a_k\ge X_0$. Then \[ |A\cap\{1,\dots,a_k\}|\ge \sqrt{a_k/2}. \] But $|A\cap\{1,\dots,a_k\}|=k$ by definition of $a_k$. So $k\ge \sqrt{a_k/2}$, i.e. $a_k\le 2k^2$. Taking $k_0$ such that $a_{k_0}\ge X_0$ completes the proof. $\square$

5) VERIFICATION

-- Lemma 326.1: the crucial observation is that to represent $n\le 2T$ as a sum of two naturals, both summands are automatically $\le 2T$; hence restricting to $A\cap[1,2T]$ is valid.

-- Lemma 326.2: correctly inverts the counting bound by evaluating it at $x=a_k$.

6) FINAL

UNRESOLVED

(i) Strongest fully proved partial result obtained here.

* Any order-2 basis must have counting function $A(x)\gg\sqrt{x}$ (Lemma 326.1). * Consequently, its $k$th element satisfies $a_k\ll k^2$ (Lemma 326.2).

(ii) Exact first gap.

Given an arbitrary order-2 basis $A$, construct a subbasis $B\subseteq A$ whose growth oscillates enough that $b_k/k^2$ has no limit. I do not have a general method to thin an arbitrary basis while controlling representations so finely.

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

1. Develop a "thinning with stability" lemma: if $A$ is a basis, remove elements in blocks to force oscillation while preserving the basis property. 2. Investigate whether there exist minimal order-2 bases with a regular asymptotic $a_k\sim c k^2$; if such exist, they would obstruct this problem. 3. For model examples (e.g. $A=2\mathbb N\cup\{1\}$), explicitly construct subbases with nonconvergent $b_k/k^2$ to understand what ingredients are needed.

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

A counterexample would be a basis $A$ such that every subbasis $B\subseteq A$ has $b_k/k^2$ convergent. This would likely require $A$ to be "essentially minimal" (so there is very little freedom to delete elements) together with a strong rigidity forcing quadratic growth with a limiting constant.