# Deducing a list of natural numbers from the list of sums

Let $S$ be a list of k natural numbers (including 0). Let $S'$ be another such list. Each such list gives way to a list of $2^k$ sums of its members. Can $S$ be recovered if I'm given the list of its $2^k$ sums? Progress so far: you can read a minimum element of $S$ by reading a minimum element of its list of sums. You can read a maximum element of $S$ by taking the top two of its sums and subtracting. You can read off the sum of every element by looking at the maximum element in the list of sums. Thus, you can also recover the sum of every element in S without one copy of the min and one copy of the max.

• Does "including $0$" refer to the natural numbers (i.e. the list can include $0$) or to the list (i.e. the list includes $0$)? Sep 24, 2012 at 8:55
• The list could include 0 but it doesn't have to.
– Jeff
Sep 24, 2012 at 8:55
• Then I'd call them "non-negative integers". Sep 24, 2012 at 8:59
• I suspect that here the natural numbers could be replaced by the integers, rationals, reals, or complex numbers. Perhaps it could even be replaced by any commutative monoid with a cancellation law. Please answer in as much generality as possible, although anything that works even for the stated case in the original problem above will suffice for what I need.
– Jeff
Sep 24, 2012 at 8:59
• The first sentence of the question is still ambiguous. Sep 24, 2012 at 9:53

At each stage of the algorithm, add a least element of the list of sums to the list of numbers and then remove all sums of this element with all combinations of elements that were already in the list of numbers from the list of sums. That is, if $S$ is the multiset of sums and $L$ is the multiset of numbers, start with $L_0=\emptyset$ and $S_0=S$ and apply
\begin{align} L_{n+1}&=L_n\cup\{\min S_n\}\;,\\ S_{n+1}&=S_n\setminus\left\{\min S_n+\sum_{t\in T}t\mid T\subseteq L_n\right\} \end{align}
to obtain $L=L_k$.