4

Let $x_1,\dots,x_n$ be not necessarily distinct real numbers. Form a multiset $A$ by taking the $2^n-1$ sums of nonempty subsets of the numbers. For example, if we have $(x_1,x_2,x_3)=(1,2,-3)$, then by taking the seven sums, $A=\{-3,-2,-1,0,1,2,3\}$. The set $(x_1,x_2,x_3)=(-1,-2,3)$ generates the same $A$.

If we are given a multiset $A$ of size $2^n-1$, can we tell whether it is generated in this way by some $n$ numbers? Obviously the $n$ numbers are present in $A$, so one way is to try all $\binom{2^n-1}{n}$ combinations of $n$ numbers, but this is large even for modest values of $n$. Is there a more efficient way?

pi66
  • 7,164
  • 1
    Well, I'd start by ordering them...$s_0≤s_1≤\cdots≤ s_{2^n-2}$ $s_0$ is the sum of the (strictly) negative terms. If it occurs multiply, that lets you count the $0's$. Ignoring multiples, $s_1-s_0$ is either the least positive term or the largest negative (meaning the one nearest $0$). Seems like you can attack it that way. – lulu Oct 23 '16 at 20:07
  • Should say: it isn't even obvious to me that the original set is uniquely determined by your sum set. It's true for small $n$ and I'd bet it's generally true...but it would be worth proving. – lulu Oct 23 '16 at 20:12
  • It's not necessarily unique. $(1,2,-3)$ and $(-1,-2,3)$ generate the same multiset. – pi66 Oct 23 '16 at 20:14
  • Thanks! Saves me wasting time on trying to prove it is unique... – lulu Oct 23 '16 at 20:15
  • … and a necessary condition to be a sum-multiset is that for every sum $s$, at least one of $s+d$ and $s-d$ is in the multiset, where $d$ is the difference between the two smallest distinct sums. And every sum occurs at least as often as the smallest. – Daniel Fischer Oct 23 '16 at 20:21

1 Answers1

1

Let $A=\{a_1,a_2\dotsb a_{2^n-1}\}$. WLOG $a_1 = x_1$, $a_2 = x_2,\dotsb a_n = x_n$, $a_{n+1}=x_1+x_2$, ...

Define the elementary symmetric polynomials $$\sigma_1= a_1 + a_2 \dotsb a_{2^n-1}$$ $$\sigma_2= \sum_i\sum_{j>i} a_ia_j = a_1 a_2 + a_1 a_3 \dotsb$$ etc

These polynomials can be expressed as polynomials in $x_1,x_2\dotsb x_n$ instead, and laboriously obtained by substituting. For n = 2: $$\sigma_1 = 2(x_1+x_2)$$ $$\sigma_2 = x_1 x_2(x_1+x_2)$$

For n=3:

$$\sigma_1 = 4(x_1 + x_2 + x_3)$$

$$\sigma_2 = 6(x_1 + x_2 + x_3)^2+2(x_1x_2+x_1x_3+x_2x_3)$$

$$\sigma_3 = 4(x_1+x_2+x_3)^3+6(x_1+x_2+x_3)(x_1x_2+x_1x_3+x_2x_3)$$

$$\sigma_7 = x_1x_2x_3 (x_1+x_2+x_3)((x_1+x_2+x_3)(x_1x_2+x_1x_3+x_2x_3)-x_1x_2x_3)$$

I'm not going to actually use $\sigma_3$ but it might come in handy for some other calculations. These are tiresome to find, so I didn't compute the other ones.

Since $\sigma_i$ is expressed as a function of the numbers we have, we can compute those and use them to find the elementary symmetric polynomials of $(x_1,x_2\dotsb x_n)$, so let $x_1 + x_2 + x_3 = a$, $x_1x_2+x_1x_3+x_2x_3 = b$ and $x_1x_2x_3 = c$, then solving this system is equivalent to finding the roots of $t^3-at^2+bt-c=0$, which can hopefully be found with the rational root test.

In your example, $\sigma_1=0$, $\sigma_2=-14$, $\sigma_7=0$, then $$x_1+x_2+x_3=0$$ $$x_1x_2+x_1x_3+x_2x_3=-7$$ $$x_1x_2x_3= ?$$ This is a degenerate case because $\sigma_1 = 0$, but the two valid solutions can be found by examining the subsets with sum 0. Also this leads to insight on the uniqueness of the solutions, if $\sigma_1\not=0$ then all of $x_1 + x_2 + x_3$, $x_1x_2+x_1x_3+x_2x_3$, $x_1x_2x_3$ are uniquely determined which wields a single solution up to permutation.

For larger n expressing $\sigma_1,\sigma_2\dotsb\sigma_n$ as a function of $x_1,x_2\dotsb x_n$ gets much more complex, but disregarding that the problem can be probably solved the same way.

Sophie
  • 3,378