# variant of Lagrange's four square theorem using a restricted set of squares

The well-known four square theorem states that any positive integer is the sum of at most four squares. Suppose that, instead of allowing all squares, I only consider the following set of squares: $$S=\{n^2:n\not\equiv 0~(\text{mod}~6)\}.$$ Are there universal constants $N$ and $k$ such that any integer $n\geq N$ can be expressed as a sum of at most $k$ elements of $S$?

If not, then fix constants $N$ and $k$ and define $A(N,k)$ to be the set of integers $n\geq N$ that can be expressed as a sum of at most $k$ elements of $S$. Are there any values of $N$ and $k$ for which $A(N,k)$ contains an infinite arithmetic progression (e.g. all positive even integers)? Via a result of Erdos, Nathanson, and Sarkozy, a positive answer to the previous question would follow from the existence of $N$ and $k$ such that $A(N,k)$ has positive lower asymptotic density.

The number $6$ in the set above is somewhat arbitrary, so I would be interested if similar questions could be addressed with a different fixed positive integer in place of $6$. The $0$ is important on the other hand (I think).

• do some computer experiments and get back to me – Will Jagy Apr 17 '16 at 16:15

I don't know the answer to the first question (if there are $N$ and $k$ such that any integer greater than $N$ can be expressed as a sum of $k$ elements of $S$). (updated below)

There are $N$ and $k$ such that $A(N,k)$ contains an infinite arithmetic progression. In particular, there is a characterization, due to Gauss, of positive integers which can be expressed as the sum of three squares. Part of this theorem goes by showing that any number congruent to $1$, $3$, or $5$ modulo $8$ is the sum of three squares (see, e.g., Lemma 1.9 of Additive number theory by Melvyn B. Nathanson). Since any square is congruent to $0$, $1$, or $4$ modulo $8$, it follows that if $n$ is congruent to $3$ modulo $8$, then $n$ is the sum of three odd squares.

In conclusion, since $S$ contains all odd squares, the arithmetic progression $8\mathbb{N}+3$ is contained in $A(3,3)$.

UPDATE #1: It looks like one can use the above remarks, together with a theorem on Shnirel'man density, to prove that, for some $k>0$, every positive integer is a sum of at most $k$ elements of $S$.

See Theorem 7.7 of Additive number theory by Melvyn B. Nathanson

Suppose $A$ is a set of integers such that $0\in A$ and $$\sigma(A):=\inf_{n>0}\frac{A(n)}{n}>0,$$ where $A(n)=|A\cap[1,n]|$. Then there is some $h>0$ such that any nonnegative integer is the sum of $h$ elements of $A$ (possibly repeated).

Corollary: There is some $k>0$ such that any positive integer is the sum of at most $k$ elements of $S$.

Proof: Let $S_0=S\cup\{0\}$ and let $A=S_0+S_0+S_0$. It suffices by Shnirel'man's theorem to show that $\sigma(A)>0$. We argued above that $A$ contains $8\mathbb{N}+3$. From this it is easy to calculate a positive lower bound for $\sigma(A)$. For instance, $8\mathbb{N}+3\subseteq A$ implies $$\frac{A(n)}{n}\geq\frac{\lfloor\frac{n+5}{8}\rfloor}{n}> \frac{1}{8}-\frac{3}{8n}$$ Note also that $1,2,3\in A$, so $A(1)=1$, $A(2)=2$, and $A(3)=3$. So, altogether, $\sigma(A)\geq \frac{1}{32}$.

UPDATE #2: Looking through the proof of Theorem 7.7 quoted above, one can get a fairly reasonable upper bound $k$ such that every positive integer is the sum of at most $k$ odd squares (I couldn't find this after a quick Google, but surely it is somewhere). From the proof of Theorem 7.7, the following is evident.

Suppose $A$ is a set of integers such that $0\in S$ and $\sigma(A)=\alpha>0$. Let $l>0$ be such that $(1-\alpha)^l\leq\frac{1}{2}$. Then any nonnegative integer is the sum of $2l$ elements of $A$ (possibly repeated).

Now let $A$ be the nonnegative integers which can be written as a sum of at most $3$ odd squares. Then the inequality above still holds: $$\frac{A(n)}{n}>\frac{1}{8}-\frac{3}{8n}.$$ Since $1,2,3\in A$, we have $\frac{A(n)}{n}\geq \frac{1}{8}$ for all $n\leq 24$. From the above inequality $\frac{A(n)}{n}\geq \frac{7}{64}$ for $n\geq 24$. Therefore $\sigma(A)\geq \frac{7}{64}$, and so $(1-\sigma(A))^6\leq\frac{1}{2}$. By the fact above, any nonnegative integer is the sum of $12$ elements of $A$, and so every positive integer is the sum of at most $36$ odd squares.

Doing any better would require improving the inequality above since, even if we knew $\sigma(A)\geq\frac{1}{8}$, we would still need $l=6$ in the above fact.