Sets of squares representing all squares up to $n^2$

Question

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.

Answer 1

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 \}$.

Answer 2

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$$