# 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)$?

-

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.

-
+1! a masterstroke. –  Pietro Majer Oct 4 '10 at 6:53

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

-
@qiaochu: is your statement a theorem or part of the folklore? –  ronaf Oct 3 '10 at 22:39
It's neither, really, but it's true. A product of some of the $x_i$ becomes a sum of some of the $\log{|x_i|}$, and from here it is basic linear algebra to show that $k \ge n$. –  drvitek Oct 3 '10 at 22:49
So, the missing last step of the answer is the following observation. The $k$ equations define a $(n-k)$-dimensional hyperplane in log-space. But the surface $\sum e^{\log|x_i|}=C$ does not include any hyperplanes (of dimension at least $1$) in the $\log|x_i|$s. So the hyperplane of solutions to the known equations does not pick out a given $C$. –  Theo Johnson-Freyd Oct 4 '10 at 2:21

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

-