gpt pro 5.2 attempt on Math-5957

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.