Let $S\_n=\{1,2,\ldots,n\}$ be natural numbers up to $n$.
Say that a subset $S \subseteq S\_n$
*square-represents* $S\_n^2$ if every
square $1^2,2^2,\ldots,n^2$ can be represented by adding or subtracting
at most one copy of squares of elements of $S$.


*Example*. For $n=7$, the set $S$ of $|S|=5$ numbers
$\{1, 2, 3, 5, 7\}$
square-represents $S\_7^2$
because
$4^2 = 5^2 - 3^2$
and $6^2 = 7^2 - 2^2 - 3^2$.


The "at most one copy" condition means that one could represent each
square missing from $S$ by a two-pan balance.
My question is:



> 
> **Q**. What is the minimum size $|S|$ to square-represent $S\_n^2$ as $n$ gets large?
>  In particular, is this size sublinear, $o(n)$?
> 
> 
> 


In some sense this asks for the frequency of occurrences of Pythagorean triples,
quadruples, and other analogous solutions of equations of the
form $a^2 = b^2 \pm c^2 \pm d^2 \pm \cdots$ with $a,b,c,d,\ldots$ distinct.
This may be well-known to the experts, in which case I apologize for asking a naive question.



Sets of squares representing all squares up to $n^2$
We can have the size of $S$ as small as $c \ln(n)$ for some constant $c$, and we can do this in such a way that every element of $\{1, 2, \ldots, n^2 \}$ can be represented by adding or subtracting at most copy of a square of something in $S$. I will construct a sequence of sets $T\_{k}$ so that $T\_{k}$ has size $k$, and every number $\leq (3/2)^{k}$ can be represented in the desired way.


Define a sequence by $a\_{1} = 1$, $a\_{2} = 2$, $a\_{3} = 3$, $a\_{4} = 4$, $a\_{5} = 5$.
Every integer $1 \leq m \leq 42$ can be represented in the desired way using elements of $\{ 1, 2, 3, 4, 5 \}$. Let $b\_{5} = 42$. For $k \geq 5$, let $a\_{k+1} = \lfloor \sqrt{b\_{k}} \rfloor$ and $b\_{k+1} = b\_{k} + a\_{k+1}^{2}$. Define $T\_{k+1} = \{ a\_{1}, a\_{2}, \ldots, a\_{k}, a\_{k+1} \}$. Then, by construction, every number between $1$ and $b\_{k}$ can be represented using the elements of $T\_{k}$ and every number between $b\_{k}+1$ an $b\_{k+1}$ can be represented in the form $a\_{k+1}^{2} + r$, where $1 \leq r \leq b\_{k}$.
In particular, every square between $1$ and $b\_{k+1}$ can be represented in the desired way using elements of $T\_{k}$. Moreover, it is easy to see that $a\_{k+1} > a\_{k}$ and $b\_{k+1} \geq (3/2) b\_{k}$ (and in fact, $b\_{k+1} \approx 2b\_{k}$). For an $S$ constructed in this way, we have $|S| = k$ and $n = \lfloor \sqrt{b\_{k}} \rfloor \geq (\sqrt{3/2})^{k}$. 


A trivial lower bound on $|S|$ is $\ln(n)/\ln(3)$, just because there are $3^{|S|}$ possible sums $\sum\_{s \in S} \epsilon\_{s} s$, where $\epsilon\_{s} \in \{ -1, 0, 1 \}$.


