gpt pro 5.2 attempt on Math-5967

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.