<s>[INST] Sets of squares representing all squares up to $n^2$ 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.
 [/INST] Here is a little example following Jeremy Rouse's construction. Let $A$ be the $a_i$ terms
and $B$ the $b_i$ terms.
$$A=\{1,2,3,4,5,6,8,11,16\}$$
$$B=\{0,0,0,0,42,78,142,263,519\}$$
For example 
$$a_9 = \lfloor \sqrt{b_8} \rfloor = \lfloor \sqrt{263} \rfloor = 16 \;,$$
and
$$b_9=b_8+a^2_9 = 263+16^2 = 519 \;.$$
The missing squares can be achieved as follows:
$$7^2 = 2^2 + 3^2 + 6^2$$
$$9^2 = 1^2 + 4^2 + 8^2$$
$$10^2 = 6^2 + 8^2$$
$$12^2 = 3^2 - 11^2 + 16^2$$
$$13^2 = -4^2+ 8^2+ 11^2$$
$$14^2 = 2^2 -8^2 + 16^2$$
$$15^2 = 1^2 + 2^2 - 6^2 + 16^2$$
</s>