Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
add comment

3 Answers

up vote 26 down vote accepted

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.

share|improve this answer
2  
+1! a masterstroke. –  Pietro Majer Oct 4 '10 at 6:53
add comment

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

share|improve this answer
    
@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
3  
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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.