3
$\begingroup$

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).

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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