# Lagrange four squares theorem

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?

• Sieve theory will give that one can take $X$ to be the set of numbers with at most $r$ prime factors for some enormous $r$, probably Oct 21, 2018 at 11:23

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.

• @Ofir Gorodetsky Thanks for the answer and the references. Oct 22, 2018 at 4:36

I know this question has already been sufficiently answered, but I would like to mention an explicit construction of Choi-Erdős-Nathanson, as opposed to the probabilistic proofs that are common in this field. Even though the result is a bit weaker than the results that can be proven probabilistically, it is, in my opinion, still worth sharing.

Theorem (Choi-Erdős-Nathanson). There exists a set of squares $$S$$ with $$|S| < cn^{\frac{1}{3}}\log(n)$$ such that every positive integer smaller than or equal $$n$$ can be written as a sum of at most $$4$$ elements of $$S$$.

Proof. Let $$x = n^{\frac{1}{3}}$$ and define the sequences $$a_i = i$$, $$b_i = \left \lfloor x\sqrt{i} \right \rfloor$$ and $$c_i = \left \lfloor x\sqrt{i} \right \rfloor -1$$. Now let $$A = \displaystyle \bigcup_{i=1}^{\left \lfloor 2x \right \rfloor} a_i^2$$, $$B = \displaystyle \bigcup_{i = 4}^{\left \lfloor x \right \rfloor} b_i^2$$, $$C = \displaystyle \bigcup_{i = 4}^{\left \lfloor x \right \rfloor} c_i^2$$. Then we first aim to prove that every positive integer $$m$$ with $$m \le n$$ and $$m \not \equiv 0 \pmod{4}$$ can be written as a sum of at most $$4$$ elements of $$D = A \cup B \cup C$$, and note that $$|D| < 4x = 4n^{\frac{1}{3}}$$.

From Lagrange's theorem it follows that if $$m \le 4x^2$$, then $$m$$ is the sum of at most $$4$$ elements of $$A$$, so we may assume $$4x^2 < m \le n$$. With $$k$$ defined as $$k = \left \lfloor \frac{m}{x^2} \right \rfloor$$, it is clear that $$4 \le k \le x$$. If we let $$d$$ be equal to $$\left \lfloor x\sqrt{k} \right \rfloor$$, then $$d^2 \in B \subset D$$ and $$(d-1)^2 \in C \subset D$$. By Gauss' Theorem on sums of three squares, either $$m - d^2$$ or $$m - (d-1)^2$$ can be written as the sum of three squares, since $$m \not \equiv 0 \pmod{4}$$. Moreover, $$m - (d-1)^2 < (k+1)x^2 - (x\sqrt{k}-2)^2 < 4x^2$$ for $$x$$ large enough (and the small values can easily be checked by hand). So we conclude that either $$m - d^2$$ of $$m - (d-1)^2$$ can be written as the sum of three elements of $$A$$.

Now all we need to deal with are the integers $$m \le n$$ such that $$m \equiv 0 \pmod{4}$$. But then we can write $$m = 4^jm'$$ with $$j \le \frac{\log(n)}{\log(4)}$$ and where $$m'$$ can be written as the sum of at most $$4$$ elements of $$D$$. So define $$S_i = \{4^i d | d \in D\}$$ and $$S = \displaystyle \bigcup_{i=0}^{\left \lfloor \frac{\log(n)}{\log(4)}\right \rfloor} S_i$$. Then $$|S| < 4n^{\frac{1}{3}}\left(\frac{\log(n)}{\log(4)} + 1\right)$$ and every positive integer smaller than or equal to $$n$$ is the sum of at most $$4$$ elements of $$S$$.

Back to my original suggestion, it appears that taking $$X$$ to be numbers with at most four prime factors is (basically) enough. Indeed, the following paper due to Tsang and Zhao show the following: every sufficiently large integer $$N \equiv 4 \pmod{24}$$ can be written as $$x_1^2 + x_2^2 + x_3^2 + x_4^2 = N$$, with $$x_i \in P_4$$ for $$i = 1,2,3,4$$. Here $$P_r$$ is the set of numbers with at most $$r$$ prime factors. I am guessing one only needs to take $$r$$ slightly larger, and allowing for possibly non-primitive representations, to cover the remaining congruence classes.