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?

  • 3
    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 – Stanley Yao Xiao Oct 21 at 11:23
up vote 42 down vote accepted

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. – M. Farrokhi D. G. Oct 22 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.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.