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

  • $\begingroup$ 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. $\endgroup$ – Robert Rauch Apr 25 at 7:47
  • $\begingroup$ @RobertRauch Indeed, but since you are using an ordered list of partial sums with $2^{n}$ elements, it already contains the information about multiplicity. $\endgroup$ – 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$, \begin{equation} \lambda_l=\min\left\{\lambda\in\mathcal{P}\mid m_{l-1}(\lambda)<m_n(\lambda)\right\}. \end{equation} 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)<m_n(\lambda)\right\}$. 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_*)<m_n(\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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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