Suppose that I have $n$ unknown variables $x\_1,\ldots,x\_n$. I wish to compute their sum:
$$Sum(x) = \sum\_{i=1}^nx\_i$$
However, the only access to these variables is through products: that is, for any subset $S \subset [n]$ I may compute:
$$P(S) = \prod\_{i \in S}x\_i$$


That is, I wish to find some number of subsets $S\_1,\ldots,S\_k$, compute $P(S\_1),\ldots,P(S\_k)$, and then apply some postprocessing $f$ to find the sum of the variables:
$$f(P(S\_1),\ldots,P(S\_k)) = Sum(x)$$


My question is: How large must $k$ be? Clearly, $k = n$ suffices, since with $k$ subsets I may uniquely identify each $x\_i$ and then sum the values myself. Is it possible to do with $k < n$? With $k = O(1)$?



How many products specify a sum?
Here is an extreme case: I will tell you that either every variable is zero or possibly a single one of them is 1. So your task is to decide if the sum is 0 or it is 1. Any product of more than one term gives no information at all. To rule out all zero you need to check each variable.


