Order lifting for sparse additive bases of polynomial values

Definitions and mathematical statement

Let $f\in\mathbb Z[x]$ have degree $d\geq2$ and positive leading coefficient, and suppose $f(m)\geq0$ for every positive integer $m$. Fix an integer $h\geq1$. For $A\subseteq\mathbb Z_{\geq0}$, put \[ hA=\{a_1+\cdots+a_h:a_i\in A\},\qquad A(N)=|A\cap\{0,1,\ldots,N\}|. \] Summands may repeat, and exactly $h$ are used. Say that $A$ is an additive basis of order $h$ for the polynomial sequence if $f(m)\in hA$ for every integer $m\geq1$. It need not represent integers outside that sequence.

Determine the strongest universal lower growth bound for $A(N)$ under this hypothesis, with constants allowed to depend on $f$ and $h$. The elementary counting scale is $N^{1/(hd)}$: there are order $N^{1/d}$ distinct polynomial values at most $N$, while at most $A(N)^h$ ordered sums can use summands at most $N$. Nonnegativity ensures that any representation of such a value uses only summands at most $N$. The workshop asks whether the polynomial structure for $d\geq2$ forces a substantially stronger bound than this counting estimate. A sharp answer should quantify the improvement and exhibit bases approaching it, or explain when the counting scale is optimal. The polynomial and the order are fixed while $N\to\infty$; changing the polynomial with $N$ is outside the question. The use of nonnegative naturals is an explicit convention for the source's word "naturals".

Short English statement

Must an additive basis for all values of a nonlinear polynomial be denser than the elementary representation-counting bound predicts?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 20001108 (AIM-COMBINATORICS-0233), AIM Workshop Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 American Institute of Mathematics, Recent trends in additive combinatorics, item 2.8. Original workshop question underlying AIM-COMBINATORICS-0233. https://aimath.org/WWN/additivecomb/additivecomb.pdf.