How many products specify a sum? 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)$?
 A: $k$ must be at least as large as $n$.  Otherwise you have a system of less than $n$ linear equations in the variables $\log |x_i|$ (assuming they are real or complex), which is underdetermined or which has no solution.
A: 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.
A: Here is essentially Qiachu's argument, but spelled out in detail.  Suppose that you tell me $P(S_j)$ for some subsets $S_1,\dots,S_k$ of $\{1,\dots,n\}$.  Each subset $S_j$ corresponds to some vertex of the cube $\{0,1\}^n$ in $n$-dimensional space.  If you pick out $k < n$ vertices, then they span a $k$-dimensional hyperplane, and there is necessarily a line orthogonal to this hyperplane.  In fact, we can pick this line to pass through a (non-zero) integer point: suppose that it passes through $(a_1,\dots,a_n)$ with all $a_j \in \mathbb Z$.
Now suppose that $(x_1,\dots,x_n)$ is a solution to the system of $k$ equations $P(S_j) = P_j$.  Pick a constant $\lambda \neq 0,1$.  Then $(\lambda^{a_1}x_1,\dots,\lambda^{a_n}x_n)$ is also a solution, because $(a_1,\dots,a_n)$ is orthogonal to each point $S_j$.
Since at least one $a_j$ is non-zero, $\sum \lambda^{a_j}x_j$ is non-constant in $\lambda$ (provided the corresponding $x_j$s are non-zero).  For example, if some $a_j$ is positive, then as $\lambda \to \infty$, $\sum \to \infty$, and if some $a_j$ is negative, as $\lambda \to 0$, $\sum \to \infty$.  The last step is to check that by knowing fewer than $n$ of the $P(S_j)$, you cannot determine that all $x_j = 0$, and indeed there is some $j$ such that $x_j$ is not forced to be zero and $a_j$ can be taken to be nonzero.
(Depending on exactly how you ask your question, you can probably skip the last step: if some collection of $S_j$s is guaranteed to determine the sum upon the knowledge of the $P(S_j)$s, then certainly you can do it for all $x_j$ nonzero.  But the above argument should prove that over $\mathbb Q$, for example, no matter what values the $P(S_j)$ have, they don't determine the sum.  The argument fails over $\mathbb F_2$, since there we can't pick a $\lambda$.  Indeed, if you tell me that we are working over $\mathbb F_2$ and that $P(\{1,\dots,n\}) = 1$, then I know that $\sum = n \pmod 2$.)
