# Can we determine summands from their partial sums?

Assume there are non-negative numbers $$\lambda_1\le \ldots\le \lambda_n\in[0,\infty)$$. You are given the (ordered) list $$s_1\le\ldots\le s_{2^n}\in[0,\infty)$$ of all partial sums, i.e. every $$s_i$$ is of the form $$s_i=\sum_{k\in K_i}\lambda_k$$ for some unique but unknown $$K_i\subseteq\{1,\ldots,n\}$$.

Question: Can we determine the $$\lambda_1,\ldots,\lambda_n$$ from knowing the $$s_1,\ldots,s_{2^n}$$?

Some obvious facts are

1. Since there is some $$s_i$$ corresponding to $$K_i=\emptyset$$, $$s_1=\cdots=s_i=0$$.
2. $$\lambda_1=s_2$$, since no non-trivial partial sum can be smaller as the smallest possible summand.
3. $$s_{2^n}=\sum_{k=1}^n\lambda_k$$, since no partial sum can be bigger.
4. For $$n=2$$ the answer is yes, since $$\lambda_1=s_2$$ and $$\lambda_2=s_4-s_2$$.

Note: For my use case it would be sufficient to know if for any given $$s_1\le\cdots\le s_{2^n}$$ there is at most one possibility for $$\lambda_1\le\cdots\le\lambda_n$$.

1. By calculating how many $$s_i$$ are zero, you can determine how many $$\lambda_i$$ are zero. If there are any, they will be creating repeated entries $$s_i$$ throughout, but in a systematic manner where one can eliminate their effect; indeed, if there are $$k$$ zeroes, then there will be $$k$$ extra duplicates of every entry. For simplicity, suppose $$\lambda_1 > 0$$.

2. Now, indeed, $$\lambda_1 = s_2$$.

3. We proceed by induction. Suppose we have identified $$\lambda_1,\ldots,\lambda_j$$ and calculated the partial sums consisting of only $$\lambda_1,\ldots,\lambda_j$$, such as $$\lambda_1+\lambda_3$$. Then the smallest remaining partial sum must be $$\lambda_{j+1}$$. Proof: Otherwise the smallest remaining partial sum would have to be a sum with at least one unknown $$\lambda_m$$ that is (by definition) not yet in the list of known partial sums, which would imply that $$\lambda_m$$ is smaller than the smallest remaining partial sum; a contradiction.

4. Now that $$\lambda_{j+1}$$ is also known, consider the known list of partial sums to include all sums of $$\lambda_1,\ldots,\lambda_{j+1}$$.

Actually, separate treatment of steps 1 and 2 is not necessary; one only has to initialize the list of known partial sums with the empty sum $$s_1=0$$.

This method probably works even if you are missing entires from the list of partial sums, as long as all the missing entries are strictly greater than $$\lambda_n$$.

• One has to be careful: Assume we have $\lambda_1=1,\lambda_2=2,\lambda_3=3,\lambda_4=4,...$ and already computed $\lambda_1,\lambda_2$. The set of known partial sums is $K=\{0,1,2,3\}$, so the smallest partial sum not in $K$ would be $4\ne\lambda_3$. The problem here is that $\lambda_3=\lambda_1+\lambda_2$ is itself a partial sum. I believe that this can be fixed by using multisets of partial sums: In the above situation the multiset of all partial sums would be $\{0,1,2,3,3,4,...\}$, so after removing the multiset $K$ the smallest remaining element would be $3=\lambda_3$ as required. – Robert Rauch Apr 25 at 7:47
• @RobertRauch Indeed, but since you are using an ordered list of partial sums with $2^{n}$ elements, it already contains the information about multiplicity. – Tommi Brander Apr 25 at 7:55

Here is a streamlined version of Tommi Brander's solution: $$\newcommand{\IN}{\mathbb{N}}$$

Lemma: Let $$0\le\lambda_1\le\cdots\le\lambda_n$$ and $$\mathcal{P}\doteq\left\{\lambda_K\doteq\sum_{k\in K}\lambda_k\left|K\subseteq\mathbb{N}_n\right.\right\}$$ the set of their partial sums, where $$\IN_n\doteq\{1,2,\ldots,n\}$$. For $$0\le l\le n$$ consider the function $$m_l:\mathcal{P}\to\IN_0$$ with $$m_l(\lambda)=\#\{K\subseteq\IN_l\mid\lambda_K=\lambda\}$$. Then for all $$1\le l\le n$$, $$$$\lambda_l=\min\left\{\lambda\in\mathcal{P}\mid m_{l-1}(\lambda) In particular, noting that $$m_0(\lambda)=\mathbf{1}(\lambda=0)$$, the $$\lambda_1,\ldots,\lambda_n$$ can be recovered iteratively only from $$\mathcal{P}$$ and $$m_n$$.

Proof: Let $$\mathcal{P}_l\doteq\left\{\lambda\in\mathcal{P}\mid m_{l-1}(\lambda). By construction, $$\lambda_l\in\mathcal{P}_l$$ and therefore $$\lambda_*=\min\mathcal{P}_l$$ exists and satisfies $$\lambda_*\le\lambda_l$$. Since $$m_{l-1}(\lambda_*), there is some $$K\subseteq\IN_n$$ with $$K\not\subseteq\IN_{l-1}$$ such that $$\lambda_*=\lambda_K$$. In particular there is $$r\in K$$ with $$r\ge l$$ and, hence, $$\lambda_r\in\mathcal{P}_l$$. By positivity of the $$\lambda_i$$ we find that $$\lambda_r\le\lambda_K=\lambda_*$$ and therefore $$\lambda_*=\lambda_r$$ by minimality of $$\lambda_*$$. Since $$r\ge l$$ we conclude $$\lambda_l\le \lambda_r=\lambda_*\le\lambda_l$$, thus $$\lambda_*=\lambda_l$$.