Power-Saving Lower Bounds for Additive Bases of Polynomial Sequences

Let \(h\geq 2\) be fixed, let \(f\) be a natural-valued polynomial of degree \(d\geq 2\) , and suppose that \(A\subseteq\N\) satisfies \(f(\N)\subseteq hA\) . We prove \[ \card{A\cap[0,X]}\geq \begin{cases} X^{4/(3hd)-o(1)},& h\text{ even},\\ X^{4/((3h+1)d)-o(1)},& h\text{ odd}. \end{cases} \] Both exponents are strictly larger than the elementary exponent \(1/(hd)\) . This gives an affirmative qualitative answer, for every fixed \(h\geq2\) , to Problem 2.8 from the 2004 AIM problem list on recent trends in additive combinatorics. The argument combines a self-contained graph-path form of an Erdős–Newman two-basis estimate with a divisor bound for repeated differences of polynomial values. For odd \(h\) , one summand is first frozen on a large fibre and the remaining summands are then split into two equal blocks. No optimality of the displayed exponents is asserted.