3
$\begingroup$

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.

$\endgroup$

2 Answers 2

9
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Yes, that is what I meant and I have edited my answer accordingly. $\endgroup$ Dec 20, 2014 at 23:25
  • $\begingroup$ So, if I understand your recipe, $S=\{1,2,3,4,5,6,8,10,12,16\}$ is a small example. $\endgroup$ Dec 20, 2014 at 23:29
  • 1
    $\begingroup$ Another simple way to see it is to note that $2^{2n}=(2^{n})^2$ and $2^{2n+1}=(3\cdot 2^{n-1})^2-(2^{n-1})^2$. Since every number has a binary decomposition, $1+(-1)=0$, and no square contains a single $2$ in it, we are almost done with the only problem that we may have some nasty effect near the endpoint (we cannot use numbers greater than $N$ to represent the squares near $N^2$). However, if we have $m^2>N^2/2$, then we can use the binary representation of $N^2-m^2$ or $(N-1)^2-m^2$ (whichever is even to avoid $2$ in the decomposition) instead because $\frac 98\cdot \frac 12<1$. $\endgroup$
    – fedja
    Dec 20, 2014 at 23:46
  • 1
    $\begingroup$ @JosephO'Rourke - The example you gave works for $n = 25$ and every integer less than $643$ can be expressed in terms of the squares of those numbers. This isn't quite what my recipe gives though. It gives $S = \{ 1, 2, 3, 4, 5, 6, 8, 11, 16 \}$. $\endgroup$ Dec 21, 2014 at 12:35
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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