Erdős Problem #870

Erdős Problem 870 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/870

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/870.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/870.tex.

FORMAL RESTATEMENT. Fix an integer $k\ge 3$.

• An additive basis of order $k$ is a set $A\subseteq\mathbb N$ (here $\mathbb N=\{1,2,3,\dots\}$) such that there exists $N_0$ with the property that every integer $n\ge N_0$ can be written as a sum of at most $k$ elements of $A$.
• A minimal additive basis of order $k$ is a basis $B$ of order $k$ such that for every $b\in B$ the set $B\setminus\{b\}$ is not a basis of order $k$.
• For $t\in\{0,1,\dots,k\}$ and $n\in\mathbb Z$, let $r_{A,\le t}(n)$ be the number of representations of $n$ as a sum of at most $t$ elements of $A$, where:
  • repetition of summands is allowed;
  • order of summands is ignored (so we count nondecreasing $t'$-tuples for some $0\le t'\le t$);
  • we include the empty sum as the unique representation of $0$ (so $r_{A,\le t}(0)\ge 1$).
  Define $r_A(n):=r_{A,\le k}(n)$.

(Counting ordered representations instead changes $r_A(n)$ by at most a factor $k!$ for fixed $k$, so the qualitative question "$\ge c\log n$" is insensitive to this convention.)

Problem. Does there exist a constant $c=c(k)>0$ such that for every additive basis $A$ of order $k$, if \[ r_A(n)\ge c\log n\qquad\text{for all sufficiently large }n, \] then $A$ contains a minimal additive basis of order $k$?

QUICK LITERATURE/CONTEXT CHECK. The problem text itself states:

• Erdős--Nathanson proved a $k=2$ positive result under the hypothesis $1_A\ast 1_A(n)>(\log(4/3))^{-1}\log n$ for all large $n$.
• Härtter and Nathanson proved there exist additive bases containing no minimal additive basis.

I do not use any additional literature beyond what is explicitly stated above.

ATTACK PLAN. Two natural tracks.

1. Proof track: try to delete elements of $A$ while preserving the basis property, and prove that the representation-count lower bound prevents an infinite deletion process without reaching a minimal basis.
2. Disproof track: try to modify known "no minimal subbasis" constructions by adding redundancy so that $r_A(n)\gg\log n$ still holds.

I can formalize how representation counts change under deletion (Lemma 1) and how minimality is witnessed (Lemma 2), but I do not close the global deletion argument.

WORK.

Lemma 1 (exact change in $r_{A,\le k}$ when deleting one element). Let $A\subset\mathbb N$, fix $k\ge 1$, and fix $a\in A$. For every integer $n$, \[ r_{A,\le k}(n) = r_{A\setminus\{a\},\le k}(n) + \sum_{j=1}^{k} r_{A\setminus\{a\},\le k-j}(n-ja). \] (We use the convention that $r_{B,\le t}(0)$ counts the empty sum as one representation for every $t\ge 0$ and $r_{B,\le t}(m)=0$ for $m<0$.)

Proof. Count representations of $n$ by the multiplicity $j\in\{0,1,\dots,k\}$ of the summand $a$.

If $j=0$, then the representation uses only elements of $A\setminus\{a\}$ and contributes $r_{A\setminus\{a\},\le k}(n)$.

If $j\ge 1$, remove the $j$ copies of $a$ from the multiset. The remaining multiset is a representation of $n-ja$ using at most $k-j$ elements from $A\setminus\{a\}$, hence is counted by $r_{A\setminus\{a\},\le k-j}(n-ja)$. Conversely, from any representation of $n-ja$ using at most $k-j$ elements of $A\setminus\{a\}$, adjoining $j$ copies of $a$ yields a unique representation of $n$ using at most $k$ elements of $A$ in which $a$ appears exactly $j$ times.

This gives a bijection for each fixed $j$ and summing over $j=0,1,\dots,k$ yields the identity. $\square$

Lemma 2 (minimality $\Leftrightarrow$ infinitely many witnesses for each element). Let $B\subset\mathbb N$ be an asymptotic basis of order $k$. Then $B$ is minimal of order $k$ if and only if for every $b\in B$ and every integer $N$ there exists $n\ge N$ such that $r_{B\setminus\{b\}}(n)=0$.

Proof. ($\Rightarrow$) If $B$ is minimal then for each $b\in B$, the set $B\setminus\{b\}$ is not a basis of order $k$. Therefore, for every threshold $N$ there exists $n\ge N$ not representable as a sum of at most $k$ elements of $B\setminus\{b\}$, i.e. $r_{B\setminus\{b\}}(n)=0$.

($\Leftarrow$) If for each $b\in B$ and each $N$ there is an $n\ge N$ with $r_{B\setminus\{b\}}(n)=0$, then $B\setminus\{b\}$ fails to represent arbitrarily large integers, hence is not a basis. Thus removing any $b$ destroys the basis property, so $B$ is minimal. $\square$

Where the argument stalls. Lemma 1 makes the effect of deleting one element completely explicit, but converting the hypothesis $r_A(n)\ge c\log n$ into a deletion scheme that guarantees $r(n)\ge 1$ for all large $n$ after infinitely many deletions is the main missing step. The natural obstruction is that even if each deletion decreases $r(n)$ only by a bounded amount depending on $n$, an infinite sequence of deletions can drive $r(n)$ to $0$ on an infinite subsequence of $n$.

VERIFICATION (FAST REALITY CHECK).

• Numerical check of the constant appearing in the $k=2$ statement: \[ (\log(4/3))^{-1}\approx 3.47605949678. \]
• Sanity check of Lemma 1 by brute force on small sets. I tested $200$ random instances with $k=3$, random $A\subset\{1,\dots,15\}$ of size $6$, random $a\in A$, and checked the identity for all $n\le 60$ (with the convention that $0$ has one empty representation). All $200/200$ tests passed.

FINAL. UNRESOLVED.

(i) Strongest proved partial result here. Lemma 1 (exact multiplicity decomposition under deletion) and Lemma 2 (minimality equivalent to infinitely many witness integers for each element).

(ii) First gap (crisp). Given a basis $A$ with $r_A(n)\ge c\log n$ for all large $n$, prove existence of a subset $B\subseteq A$ that is still a basis of order $k$ and satisfies the witness property of Lemma 2 for every $b\in B$.

(iii) Top 3 next moves (concrete).

1. Prove a quantitative "many deletions force failure" bound: if $D\subset A$ is deleted, lower bound $r_{A\setminus D}(n)$ in terms of $r_A(n)$ and an explicit statistic of $D$ (derived from Lemma 1) that can be controlled when $r_A(n)\gg\log n$.
2. Try a probabilistic thinning of $A$ to a random $B$ with $r_B(n)\ge 1$ for all $n$ in long ranges, then diagonalize; afterward attempt to enforce minimality by a controlled deletion using Lemma 2.
3. Attempt a counterexample construction by augmenting a known "no minimal subbasis" basis (as mentioned in the problem text) with structured redundancy that boosts $r_A(n)$ to $\gg\log n$.

(iv) Minimal counterexample structure. A counterexample would be a basis $A$ of order $k\ge 3$ with $r_A(n)\ge c\log n$ for all large $n$ but such that every subbasis $B\subseteq A$ contains an element $b\in B$ with $B\setminus\{b\}$ still a basis (so no minimal basis exists). Equivalently, there is an infinite strictly descending chain of subbases with no minimal element under inclusion.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

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

FORMAL RESTATEMENT. Fix an integer $k\ge 3$.

• An additive basis of order $k$ is a set $A\subseteq\mathbb N$ (here $\mathbb N=\{1,2,3,\dots\}$) such that there exists $N_0$ with the property that every integer $n\ge N_0$ can be written as a sum of at most $k$ elements of $A$.
• A minimal additive basis of order $k$ is a basis $B$ of order $k$ such that for every $b\in B$ the set $B\setminus\{b\}$ is not a basis of order $k$.
• For $t\in\{0,1,\dots,k\}$ and $n\in\mathbb Z$, let $r_{A,\le t}(n)$ be the number of representations of $n$ as a sum of at most $t$ elements of $A$, where:
  • repetition of summands is allowed;
  • order of summands is ignored (so we count nondecreasing $t'$-tuples for some $0\le t'\le t$);
  • we include the empty sum as the unique representation of $0$ (so $r_{A,\le t}(0)\ge 1$).
  Define $r_A(n):=r_{A,\le k}(n)$.

(Counting ordered representations instead changes $r_A(n)$ by at most a factor $k!$ for fixed $k$, so the qualitative question "$\ge c\log n$" is insensitive to this convention.)

Problem. Does there exist a constant $c=c(k)>0$ such that for every additive basis $A$ of order $k$, if \[ r_A(n)\ge c\log n\qquad\text{for all sufficiently large }n, \] then $A$ contains a minimal additive basis of order $k$?

QUICK LITERATURE/CONTEXT CHECK. The problem text itself states:

• Erdős--Nathanson proved a $k=2$ positive result under the hypothesis $1_A\ast 1_A(n)>(\log(4/3))^{-1}\log n$ for all large $n$.
• Härtter and Nathanson proved there exist additive bases containing no minimal additive basis.

I do not use any additional literature beyond what is explicitly stated above.

ATTACK PLAN. Two natural tracks.

1. Proof track: try to delete elements of $A$ while preserving the basis property, and prove that the representation-count lower bound prevents an infinite deletion process without reaching a minimal basis.
2. Disproof track: try to modify known "no minimal subbasis" constructions by adding redundancy so that $r_A(n)\gg\log n$ still holds.

I can formalize how representation counts change under deletion (Lemma 1) and how minimality is witnessed (Lemma 2), but I do not close the global deletion argument.

WORK.

Lemma 1 (exact change in $r_{A,\le k}$ when deleting one element). Let $A\subset\mathbb N$, fix $k\ge 1$, and fix $a\in A$. For every integer $n$, \[ r_{A,\le k}(n) = r_{A\setminus\{a\},\le k}(n) + \sum_{j=1}^{k} r_{A\setminus\{a\},\le k-j}(n-ja). \] (We use the convention that $r_{B,\le t}(0)$ counts the empty sum as one representation for every $t\ge 0$ and $r_{B,\le t}(m)=0$ for $m<0$.)

Proof. Count representations of $n$ by the multiplicity $j\in\{0,1,\dots,k\}$ of the summand $a$.

If $j=0$, then the representation uses only elements of $A\setminus\{a\}$ and contributes $r_{A\setminus\{a\},\le k}(n)$.

If $j\ge 1$, remove the $j$ copies of $a$ from the multiset. The remaining multiset is a representation of $n-ja$ using at most $k-j$ elements from $A\setminus\{a\}$, hence is counted by $r_{A\setminus\{a\},\le k-j}(n-ja)$. Conversely, from any representation of $n-ja$ using at most $k-j$ elements of $A\setminus\{a\}$, adjoining $j$ copies of $a$ yields a unique representation of $n$ using at most $k$ elements of $A$ in which $a$ appears exactly $j$ times.

This gives a bijection for each fixed $j$ and summing over $j=0,1,\dots,k$ yields the identity. $\square$

Lemma 2 (minimality $\Leftrightarrow$ infinitely many witnesses for each element). Let $B\subset\mathbb N$ be an asymptotic basis of order $k$. Then $B$ is minimal of order $k$ if and only if for every $b\in B$ and every integer $N$ there exists $n\ge N$ such that $r_{B\setminus\{b\}}(n)=0$.

Proof. ($\Rightarrow$) If $B$ is minimal then for each $b\in B$, the set $B\setminus\{b\}$ is not a basis of order $k$. Therefore, for every threshold $N$ there exists $n\ge N$ not representable as a sum of at most $k$ elements of $B\setminus\{b\}$, i.e. $r_{B\setminus\{b\}}(n)=0$.

($\Leftarrow$) If for each $b\in B$ and each $N$ there is an $n\ge N$ with $r_{B\setminus\{b\}}(n)=0$, then $B\setminus\{b\}$ fails to represent arbitrarily large integers, hence is not a basis. Thus removing any $b$ destroys the basis property, so $B$ is minimal. $\square$

Where the argument stalls. Lemma 1 makes the effect of deleting one element completely explicit, but converting the hypothesis $r_A(n)\ge c\log n$ into a deletion scheme that guarantees $r(n)\ge 1$ for all large $n$ after infinitely many deletions is the main missing step. The natural obstruction is that even if each deletion decreases $r(n)$ only by a bounded amount depending on $n$, an infinite sequence of deletions can drive $r(n)$ to $0$ on an infinite subsequence of $n$.

VERIFICATION (FAST REALITY CHECK).

• Numerical check of the constant appearing in the $k=2$ statement: \[ (\log(4/3))^{-1}\approx 3.47605949678. \]
• Sanity check of Lemma 1 by brute force on small sets. I tested $200$ random instances with $k=3$, random $A\subset\{1,\dots,15\}$ of size $6$, random $a\in A$, and checked the identity for all $n\le 60$ (with the convention that $0$ has one empty representation). All $200/200$ tests passed.

FINAL. UNRESOLVED.

(i) Strongest proved partial result here. Lemma 1 (exact multiplicity decomposition under deletion) and Lemma 2 (minimality equivalent to infinitely many witness integers for each element).

(ii) First gap (crisp). Given a basis $A$ with $r_A(n)\ge c\log n$ for all large $n$, prove existence of a subset $B\subseteq A$ that is still a basis of order $k$ and satisfies the witness property of Lemma 2 for every $b\in B$.

(iii) Top 3 next moves (concrete).

1. Prove a quantitative "many deletions force failure" bound: if $D\subset A$ is deleted, lower bound $r_{A\setminus D}(n)$ in terms of $r_A(n)$ and an explicit statistic of $D$ (derived from Lemma 1) that can be controlled when $r_A(n)\gg\log n$.
2. Try a probabilistic thinning of $A$ to a random $B$ with $r_B(n)\ge 1$ for all $n$ in long ranges, then diagonalize; afterward attempt to enforce minimality by a controlled deletion using Lemma 2.
3. Attempt a counterexample construction by augmenting a known "no minimal subbasis" basis (as mentioned in the problem text) with structured redundancy that boosts $r_A(n)$ to $\gg\log n$.

(iv) Minimal counterexample structure. A counterexample would be a basis $A$ of order $k\ge 3$ with $r_A(n)\ge c\log n$ for all large $n$ but such that every subbasis $B\subseteq A$ contains an element $b\in B$ with $B\setminus\{b\}$ still a basis (so no minimal basis exists). Equivalently, there is an infinite strictly descending chain of subbases with no minimal element under inclusion.