Lagrange's four square theorem states that every non-negative integer is a sum of squares of four non-negative integers. Suppose $X$ is a subset of non-negative integers with the same property, that is, every non-negative integer is a sum of squares of four elements of $X$.
$\bullet$ Is $X=\{0,1,2,\ldots\}$?
$\bullet$ If not what is a minimal set $X$ with the given property?
Best Answer
The set $X$ doesn't have to be the set of non-negative integers. This was known already to Härtter and Zöllner in 1977, who constructed an $X$ of the form $\{ 0, 1, 2, \ldots \} \setminus S $ for an infinite $S$.
For any $\varepsilon>0$, Erdös and Nathanson proved the existence of a set $X$ with $|X \cap [0,n]| = O(n^{\frac{3}{4} +\varepsilon})$, so that already provides an upper bound for your second question.
The problem was essentially settled by Wirsing in 1986, who proved that one has $X$ with $|X \cap [0,n]| = O(n^{1/2}\log^{1/2} n)$. As the lower bound $|X \cap [0,n]| =\Omega(n^{1/2})$ is obvious, this leaves a very small gap for improvement.
Spencer has found a different proof of Wirsing's result.
Other relevant references may be found in the second page of a paper of Vu. Note that most of these proofs are probabilistic.