6
$\begingroup$

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

$\endgroup$

3 Answers 3

30
$\begingroup$

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.

$\endgroup$
1
  • 3
    $\begingroup$ +1! a masterstroke. $\endgroup$ Oct 4, 2010 at 6:53
8
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ @qiaochu: is your statement a theorem or part of the folklore? $\endgroup$
    – ronaf
    Oct 3, 2010 at 22:39
  • $\begingroup$ 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$. $\endgroup$
    – dvitek
    Oct 3, 2010 at 22:49
  • 4
    $\begingroup$ 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$. $\endgroup$ Oct 4, 2010 at 2:21
2
$\begingroup$

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

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