A generalization of Waring's problem Let $f(x)$ be a polynomial with integer coefficients such that $$\lim_{x\to +\infty}f(x)=+\infty.$$
Is it true that there always exist two integers $K$ and $R$ (depend on $f(x)$), such that every positive integer $n$ can be expressed as $$n=r+\sum_{i=1}^kf(x_i),$$
where $|r|\leq R,k\leq K,x_i(i\leq k)\in \mathbb N.$
This is a generalization of Waring's problem. If $f(x)=x^2$ then $K=4,R=0.$
 A: Not sure anyone knows. Hilbert's proof of finiteness of $g(k)$ in Waring's problem depended on the particular shape of the polynomials, namely $f(x) = x^k.$ See CONJECTURE. If you have access to a university mathematics library, look up Additive Number Theory and then Additive Bases on MathSciNet and see what happens. Meanwhile, the book you should be reading is The Hardy-Littlewood Method by Robert C. Vaughan. Your  trick of adding or subtracting bounded $r$ does not change things all that much. 
Meanwhile, you should have little trouble settling the case of $$ f(x) = a x^2 + b x + c $$ for positive integer $a,$ by multiplying through by $4a,$ completing the square, and using the Four Square Theorem you quote. After that try $$ f(x) = a x^3 + b x^2 + c x + d $$ and see if you get anywhere at all, and decide what restrictions you might want on $a,b,c,d$ to make an approachable problem.
Continuing on the theme of nobody knowing in this generality, see SCHNIRELMANN. Although your sets are strongly related to the sets for the Waring problem, they still have density zero. 
Note that there is a probabilistic argument that suggests your scheme ought to work. Your polynomial starts $a x^k + b x^{k-1} + \cdots.$ As a result, the count of nonnegative $x$ values with $f(x) \leq N$ for some positive $N$ is asymptotically $N^{1/k},$ since $a^{1/k}$ goes to 1. As  a result, the sum of $k+1$ different copies gives you an excess of lattice points. So, if you can rule out $p$-adic restrictions, you can sort of expect that not many numbers will be missed, and these can be covered by your finite $r.$ Just remember that the $p$-adic restrictions are by far the major component in $g(4)$ being as large as it is. Furthermore, there are other types of obstruction. For integer $x,y,z$ and (positive) prime $p \equiv 1 \pmod 4,$ we have $$ x^2 + y^2 + z^9 \neq 216 p^3.  $$ Note that the exponent 9 is not a typo. 
