Erdős Problem #881

Erdős Problem 881 --- collection record

PROVENANCE AND STATUS

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/881.tex.

REUSED SOURCE 1

Let $A\subset\mathbb{N}$ be an additive basis of order $k$ which is minimal, in the sense that if $B\subset A$ is any infinite set then $A\backslash B$ is not a basis of order $k$. Must there exist an infinite $B\subset A$ such that $A\backslash B$ is a basis of order $k+1$?

1) FORMAL RESTATEMENT

Ambiguity note: “additive basis of order $k$” is used in the literature both for an exact basis (every $n\in\mathbb N$ is a sum of $k$ elements) and for an asymptotic basis (all sufficiently large $n$ are such sums). The problem statement uses the common Erdős-problems convention “basis of order $k$” in the asymptotic sense; I adopt that as the minimal corrected statement.

Definitions and conventions used below: - $\mathbb N:=\{1,2,3,\dots\}$. - For a set $A\subset\mathbb N$ and integer $k\ge 1$, write \[kA:=\{a_1+\cdots+a_k: a_i\in A\}.\] (Summands may repeat.) - $A$ is an (asymptotic) additive basis of order $k$ if $\exists N_0\in\mathbb N$ such that $[N_0,\infty)\cap\mathbb N\subset kA$. - $A$ is “minimal in the strong sense” if for every infinite $B\subset A$, the set $A\setminus B$ is not an additive basis of order $k$, i.e. \[\forall\, B\subset A\ (B\text{ infinite})\ \forall N\ \exists n\ge N\text{ with }n\notin k(A\setminus B).\]

Question (corrected statement): Given $k\ge 1$ and $A\subset\mathbb N$ an additive basis of order $k$ that is minimal in the above strong sense, must there exist an infinite $B\subset A$ such that $A\setminus B$ is an additive basis of order $k+1$?

2) QUICK LITERATURE/CONTEXT CHECK

The problem text itself does not cite results for #881. I therefore avoid using any external theorems here. I only note that the “strong minimality” condition (removing any infinite subset destroys order-$k$ basishood) is strictly stronger than the more common notion “removing any single element destroys basishood”.

3) ATTACK PLAN

Proof track ideas: - First handle the edge case $k=1$ (where order-1 bases are cofinite) and try to explicitly delete an infinite subset while keeping order 2. - For general $k$, prove unconditional structural constraints on any order-$k$ basis (growth lower bounds, etc.) that might constrain possible counterexamples.

Disproof track ideas: - Try to construct an order-$k$ basis $A$ with representations so “rigid” that deleting infinitely many elements destroys even order-$(k+1)$ representation. This would likely require encoding infinitely many “critical” integers whose representations force use of specific elements.

I proceed with the $k=1$ proof (complete) and then record partial structural lemmas for general $k$.

4) WORK

Lemma 881.1 (Order-$1$ bases are cofinite). If $A\subset\mathbb N$ is an additive basis of order $1$ (asymptotic), then there exists $N_0$ such that $\{N_0,N_0+1,N_0+2,\dots\}\subset A$.

Proof. By definition of “basis of order 1”, there exists $N_0$ such that every integer $n\ge N_0$ lies in $1A=A$. Equivalently, $[N_0,\infty)\cap\mathbb N\subset A$. $\square$

Lemma 881.2 (For $k=1$, one can delete an infinite set and keep an order-$2$ basis). Assume $A\subset\mathbb N$ is an additive basis of order $1$. Then there exists an infinite $B\subset A$ such that $A\setminus B$ is an additive basis of order $2$.

Proof. By Lemma 881.1, fix $N_0$ with $[N_0,\infty)\subset A$.

Construct an infinite $B\subset A$ satisfying: (i) $B\subset \{N_0+2,N_0+3,\dots\}$, (ii) $B$ contains no two consecutive integers.

This is always possible; for example, let $B:=\{N_0+2, N_0+4, N_0+6, \dots\}$. Set $C:=A\setminus B$.

Claim: $C$ is an additive basis of order $2$. Let $m\ge 2N_0+3$. Consider the two integers \[x:=m-N_0\quad\text{and}\quad y:=m-(N_0+1)=x-1.\] Both satisfy $x\ge N_0+3$ and $y\ge N_0+2$, hence $x,y\in A$ (since $A$ contains all integers $\ge N_0$).

If $x\notin B$, then $x\in C$ and also $N_0\in C$ (because $B\subset\{N_0+2,\dots\}$), so $m=N_0+x$ is a sum of two elements of $C$.

If $x\in B$, then $y=x-1\notin B$ by property (ii) (no two consecutive elements in $B$). Hence $y\in C$ and $N_0+1\in C$, so $m=(N_0+1)+y$ is a sum of two elements of $C$.

Thus every $m\ge 2N_0+3$ belongs to $2C$, i.e. $C$ is an order-$2$ asymptotic basis. Since $B$ is infinite, this completes the proof. $\square$

Lemma 881.3 (A counting lower bound for an order-$k$ basis). Let $k\ge 1$ and let $A\subset\mathbb N$ be an asymptotic additive basis of order $k$. Let \[A(x):=|A\cap\{1,2,\dots,x\}|.\] Then there exists $x_0$ such that for all integers $x\ge x_0$, \[A(x)^k \ge x/2,\quad\text{hence}\quad A(x)\ge (x/2)^{1/k}. \]

Proof. Since $A$ is an order-$k$ asymptotic basis, there exists $N_0$ such that every integer $n\ge N_0$ lies in $kA$. Fix an integer $x\ge 2N_0$. Then all integers in the interval $[N_0,x]$ (which has $x-N_0+1\ge x/2$ integers) lie in $kA$.

Any representation $n=a_1+\cdots+a_k$ with $a_i\in A$ and $n\le x$ forces each $a_i\le n\le x$, so $a_i\in A\cap[1,x]$. Therefore the set $k(A\cap[1,x])$ contains $[N_0,x]$, so \[|k(A\cap[1,x])|\ge x-N_0+1\ge x/2.\] On the other hand, the number of ordered $k$-tuples from $A\cap[1,x]$ is $A(x)^k$, so the number of distinct sums in $k(A\cap[1,x])$ is at most $A(x)^k$. Combining gives $A(x)^k\ge x/2$, hence $A(x)\ge (x/2)^{1/k}$. $\square$

FAST REALITY CHECK (computation). Take $A=\mathbb N$ (order-$1$ basis) and delete $B=\{2^t:t\ge 0\}$. A brute check for $m\le 500$ shows that every $m\ge 8$ can be written as a sum of two positive integers not in $B$. The only failures up to $500$ were $m\in\{1,2,3,4,5,7\}$. (So $\mathbb N\setminus\{2^t\}$ is indeed an order-$2$ asymptotic basis.)

5) VERIFICATION

- Lemma 881.2: I used only that $A$ contains all integers $\ge N_0$ and that $B$ has no consecutive elements above $N_0+1$. Both are explicitly ensured. - The threshold $2N_0+3$ was chosen so that both candidates $m-N_0$ and $m-(N_0+1)$ are $\ge N_0+2$, i.e. lie in the “tail” where $A$ is complete. - Lemma 881.3: The key check is that any $k$-term representation of $n\le x$ must use summands $\le x$ (true because summands are positive integers). No other hidden assumptions.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result. - The statement is TRUE for $k=1$: every order-$1$ basis $A$ admits an infinite $B\subset A$ such that $A\setminus B$ is an order-$2$ asymptotic basis (Lemma 881.2). - Any order-$k$ asymptotic basis satisfies the counting lower bound $A(x)\ge (x/2)^{1/k}$ for all large $x$ (Lemma 881.3).

(ii) First gap (crisp). For $k\ge 2$, given a strongly minimal order-$k$ basis $A$, prove or disprove: \[\exists\,\text{infinite }B\subset A\text{ such that }[N,\infty)\subset (k+1)(A\setminus B)\text{ for some }N.\]

(iii) Top 3 next moves. 1. Try to prove a “robustness” lemma: from any order-$k$ basis $A$ extract a co-infinite subset $A'\subset A$ that is still an order-$(k+1)$ basis. 2. Attempt a probabilistic thinning: delete each element independently with small probability and prove (or disprove) that $(k+1)$-fold sums still cover all large integers. 3. Search for a counterexample construction via block/scale separation where each block contains elements essential even for $(k+1)$-term representations.

(iv) Minimal counterexample structure. A counterexample (for some fixed $k\ge 2$) would be a strongly minimal order-$k$ basis $A$ such that every co-infinite subset $A'\subset A$ fails to be an order-$(k+1)$ basis; equivalently, for every infinite $B\subset A$ there are infinitely many integers not in $(k+1)(A\setminus B)$. One expects such an $A$ (if it exists) to have highly constrained representation structure, likely via widely separated “blocks” forcing near-unique use of certain elements.

COMPLETION ESTIMATE

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

Let $A\subset\mathbb{N}$ be an additive basis of order $k$ which is minimal, in the sense that if $B\subset A$ is any infinite set then $A\backslash B$ is not a basis of order $k$. Must there exist an infinite $B\subset A$ such that $A\backslash B$ is a basis of order $k+1$?

1) FORMAL RESTATEMENT

Ambiguity note: “additive basis of order $k$” is used in the literature both for an exact basis (every $n\in\mathbb N$ is a sum of $k$ elements) and for an asymptotic basis (all sufficiently large $n$ are such sums). The problem statement uses the common Erdős-problems convention “basis of order $k$” in the asymptotic sense; I adopt that as the minimal corrected statement.

Definitions and conventions used below: - $\mathbb N:=\{1,2,3,\dots\}$. - For a set $A\subset\mathbb N$ and integer $k\ge 1$, write \[kA:=\{a_1+\cdots+a_k: a_i\in A\}.\] (Summands may repeat.) - $A$ is an (asymptotic) additive basis of order $k$ if $\exists N_0\in\mathbb N$ such that $[N_0,\infty)\cap\mathbb N\subset kA$. - $A$ is “minimal in the strong sense” if for every infinite $B\subset A$, the set $A\setminus B$ is not an additive basis of order $k$, i.e. \[\forall\, B\subset A\ (B\text{ infinite})\ \forall N\ \exists n\ge N\text{ with }n\notin k(A\setminus B).\]

Question (corrected statement): Given $k\ge 1$ and $A\subset\mathbb N$ an additive basis of order $k$ that is minimal in the above strong sense, must there exist an infinite $B\subset A$ such that $A\setminus B$ is an additive basis of order $k+1$?

2) QUICK LITERATURE/CONTEXT CHECK

The problem text itself does not cite results for #881. I therefore avoid using any external theorems here. I only note that the “strong minimality” condition (removing any infinite subset destroys order-$k$ basishood) is strictly stronger than the more common notion “removing any single element destroys basishood”.

3) ATTACK PLAN

Proof track ideas: - First handle the edge case $k=1$ (where order-1 bases are cofinite) and try to explicitly delete an infinite subset while keeping order 2. - For general $k$, prove unconditional structural constraints on any order-$k$ basis (growth lower bounds, etc.) that might constrain possible counterexamples.

Disproof track ideas: - Try to construct an order-$k$ basis $A$ with representations so “rigid” that deleting infinitely many elements destroys even order-$(k+1)$ representation. This would likely require encoding infinitely many “critical” integers whose representations force use of specific elements.

I proceed with the $k=1$ proof (complete) and then record partial structural lemmas for general $k$.

4) WORK

Lemma 881.1 (Order-$1$ bases are cofinite). If $A\subset\mathbb N$ is an additive basis of order $1$ (asymptotic), then there exists $N_0$ such that $\{N_0,N_0+1,N_0+2,\dots\}\subset A$.

Proof. By definition of “basis of order 1”, there exists $N_0$ such that every integer $n\ge N_0$ lies in $1A=A$. Equivalently, $[N_0,\infty)\cap\mathbb N\subset A$. $\square$

Lemma 881.2 (For $k=1$, one can delete an infinite set and keep an order-$2$ basis). Assume $A\subset\mathbb N$ is an additive basis of order $1$. Then there exists an infinite $B\subset A$ such that $A\setminus B$ is an additive basis of order $2$.

Proof. By Lemma 881.1, fix $N_0$ with $[N_0,\infty)\subset A$.

Construct an infinite $B\subset A$ satisfying: (i) $B\subset \{N_0+2,N_0+3,\dots\}$, (ii) $B$ contains no two consecutive integers.

This is always possible; for example, let $B:=\{N_0+2, N_0+4, N_0+6, \dots\}$. Set $C:=A\setminus B$.

Claim: $C$ is an additive basis of order $2$. Let $m\ge 2N_0+3$. Consider the two integers \[x:=m-N_0\quad\text{and}\quad y:=m-(N_0+1)=x-1.\] Both satisfy $x\ge N_0+3$ and $y\ge N_0+2$, hence $x,y\in A$ (since $A$ contains all integers $\ge N_0$).

If $x\notin B$, then $x\in C$ and also $N_0\in C$ (because $B\subset\{N_0+2,\dots\}$), so $m=N_0+x$ is a sum of two elements of $C$.

If $x\in B$, then $y=x-1\notin B$ by property (ii) (no two consecutive elements in $B$). Hence $y\in C$ and $N_0+1\in C$, so $m=(N_0+1)+y$ is a sum of two elements of $C$.

Thus every $m\ge 2N_0+3$ belongs to $2C$, i.e. $C$ is an order-$2$ asymptotic basis. Since $B$ is infinite, this completes the proof. $\square$

Lemma 881.3 (A counting lower bound for an order-$k$ basis). Let $k\ge 1$ and let $A\subset\mathbb N$ be an asymptotic additive basis of order $k$. Let \[A(x):=|A\cap\{1,2,\dots,x\}|.\] Then there exists $x_0$ such that for all integers $x\ge x_0$, \[A(x)^k \ge x/2,\quad\text{hence}\quad A(x)\ge (x/2)^{1/k}. \]

Proof. Since $A$ is an order-$k$ asymptotic basis, there exists $N_0$ such that every integer $n\ge N_0$ lies in $kA$. Fix an integer $x\ge 2N_0$. Then all integers in the interval $[N_0,x]$ (which has $x-N_0+1\ge x/2$ integers) lie in $kA$.

Any representation $n=a_1+\cdots+a_k$ with $a_i\in A$ and $n\le x$ forces each $a_i\le n\le x$, so $a_i\in A\cap[1,x]$. Therefore the set $k(A\cap[1,x])$ contains $[N_0,x]$, so \[|k(A\cap[1,x])|\ge x-N_0+1\ge x/2.\] On the other hand, the number of ordered $k$-tuples from $A\cap[1,x]$ is $A(x)^k$, so the number of distinct sums in $k(A\cap[1,x])$ is at most $A(x)^k$. Combining gives $A(x)^k\ge x/2$, hence $A(x)\ge (x/2)^{1/k}$. $\square$

FAST REALITY CHECK (computation). Take $A=\mathbb N$ (order-$1$ basis) and delete $B=\{2^t:t\ge 0\}$. A brute check for $m\le 500$ shows that every $m\ge 8$ can be written as a sum of two positive integers not in $B$. The only failures up to $500$ were $m\in\{1,2,3,4,5,7\}$. (So $\mathbb N\setminus\{2^t\}$ is indeed an order-$2$ asymptotic basis.)

5) VERIFICATION

- Lemma 881.2: I used only that $A$ contains all integers $\ge N_0$ and that $B$ has no consecutive elements above $N_0+1$. Both are explicitly ensured. - The threshold $2N_0+3$ was chosen so that both candidates $m-N_0$ and $m-(N_0+1)$ are $\ge N_0+2$, i.e. lie in the “tail” where $A$ is complete. - Lemma 881.3: The key check is that any $k$-term representation of $n\le x$ must use summands $\le x$ (true because summands are positive integers). No other hidden assumptions.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result. - The statement is TRUE for $k=1$: every order-$1$ basis $A$ admits an infinite $B\subset A$ such that $A\setminus B$ is an order-$2$ asymptotic basis (Lemma 881.2). - Any order-$k$ asymptotic basis satisfies the counting lower bound $A(x)\ge (x/2)^{1/k}$ for all large $x$ (Lemma 881.3).

(ii) First gap (crisp). For $k\ge 2$, given a strongly minimal order-$k$ basis $A$, prove or disprove: \[\exists\,\text{infinite }B\subset A\text{ such that }[N,\infty)\subset (k+1)(A\setminus B)\text{ for some }N.\]

(iii) Top 3 next moves. 1. Try to prove a “robustness” lemma: from any order-$k$ basis $A$ extract a co-infinite subset $A'\subset A$ that is still an order-$(k+1)$ basis. 2. Attempt a probabilistic thinning: delete each element independently with small probability and prove (or disprove) that $(k+1)$-fold sums still cover all large integers. 3. Search for a counterexample construction via block/scale separation where each block contains elements essential even for $(k+1)$-term representations.

(iv) Minimal counterexample structure. A counterexample (for some fixed $k\ge 2$) would be a strongly minimal order-$k$ basis $A$ such that every co-infinite subset $A'\subset A$ fails to be an order-$(k+1)$ basis; equivalently, for every infinite $B\subset A$ there are infinitely many integers not in $(k+1)(A\setminus B)$. One expects such an $A$ (if it exists) to have highly constrained representation structure, likely via widely separated “blocks” forcing near-unique use of certain elements.