Finding $\sum_{x∈X} x^2$ given $\sum_{y∈Y}y$ for each $Y⊆X$ such that $|Y|=\frac{|X|}{2}$?

Question

Suppose we have a finite set of real numbers $X$, and we want to compute the sum $\sum_{x \in X} x^2$, however we don't know what any of the $x \in X$ are. Instead, assume that $|X|$ is even, and suppose for any $Y \subset X$ such that $|Y| = \frac{|X|}{2}$, we know $\sum_{y \in Y}y$.

It is straightforward to compute $(\sum_{x \in X} x)^2$ with this method, because we can calculate $(\sum_{y \in Y}y + \sum_{z \in X \setminus Y}z)^2$. This isn't what I want to calculate because of the crossterms, so how can these crossterms be eliminated?

Answer 1

Note that since you know $\sum_{y \in Y}y$ for each $Y$ with $|Y|=\frac{|X|}{2}$, you know $x_i-x_j$ for each $i \neq j$. Just take $Y_i$ to be any set containing half as many elements as $X$ and containing $x_i$ but not $x_j$, and $Y_j=(Y_i\cup\{x_j\})\setminus\{x_i\}$. Then $\sum_{y \in Y_i}y-\sum_{y \in Y_j}y=x_i-x_j$.

I'll demonstrate with $|X|=4$, so $X=\{x_1,x_2,x_3,x_3\}$. Then as you note, you can calculate $$((x_1+x_2)+(x_3+x_4))^2=x_1^2+x_2^2+x_3^2+x_4^2+2(x_1x_2+x_1x_3+x_1x_4+x_2x_3+x_2x_4+x_3x_4).$$

Now using the result of the first paragraph, we can also calculate $$(x_1-x_2)^2+(x_3-x_4)^2=x_1^2+x_2^2+x_3^2+x_4^2-2(x_1x_2+x_3x_4)$$ $$(x_1-x_3)^2+(x_2-x_4)^2=x_1^2+x_2^2+x_3^2+x_4^2-2(x_1x_3+x_2x_4)$$ $$(x_1-x_4)^2+(x_2-x_3)^2=x_1^2+x_2^2+x_3^2+x_4^2-2(x_1x_4+x_2x_3)$$ So summing all 4 displayed equations gives $4(x_1^2+x_2^2+x_3^2+x_4^2)$. The left hand side of each equation can be calculated from the information given, and so $\sum_{x\in X} x^2$ can be calculated from that information as well.

In general, if $|X|=n$, you'll want to calculate $\sum_{i=1}^n(x_i-x_i')^2$ over all possible pairings of elements $\{x_i,x_{i+1}\}$, $i=1,2,...,n$. There are $\frac{(2n)!}{2^nn!}$ such pairings, and given a pair of elements $\{x_i,x_i'\}$ it will appear in $\frac{(2(n-1))!}{2^{n-1}(n-1)!}$ such pairings. So summing $\sum_{i=1}^n(x_i-x_i')$ over all possible pairings yields $$\frac{(2n)!}{2^nn!}\sum_{i=1}^{2n}x_i^2-2\frac{(2(n-1))!}{2^{n-1}(n-1)!}\sum_{i <j} x_ix_j.$$ As you noted, you can also calculate $\sum_{i=1}^{2n} x_i^2 + 2\sum_{i < j} x_ix_j$, so with some algebra you can isolate $\sum_{i=1}^{2n} x_i^2$.

Answer 2

Following up on Kenta's comment, it's not really that arduous to deduce all the elements of $X$. Say $|X|=2n$, then suppose you want to know the values of $x_1, \ldots, x_n, x_{n+1}$.

For each $1 \le k \le n+1$ you know the value of $S_k := \displaystyle\sum_{\substack{1 \le i \le n+1 \\ i \ne k}} x_i$.

It's easy to see that $\bar{S} := \frac1n \sum_{i=1}^{n+1} S_i = \sum_{i = 1}^{n+1} x_i$. So each $x_i$ is simply $\bar{S} - S_i$.

This gives us (slightly more than) half of the elements using only $n+1$ values of $Y$ and $O(n)$ arithmetic operations. We can easily get the other half by repeating the procedure on the back half, and thus obtain every element's value. Alternatively, it is easy to obtain any desired element once we know the sum of any $n-1$ others (this just shaves off 2 lookups, which is optimal for the problem of identifying all elements).