# Can you determine a set of values from a set of sums?

Consider the following problem:

There is an vector $$A$$ (which you will not see) of $$n$$ positive integers. You are given the set of sums of the (contiguously indexed) subvectors of $$A$$. For example, say

$$A = (3,2,1,2)$$

The subvectors are $$(3),(2),(1),(2), (3,2), (2,1), (1,2),(3,2,1), (2,1,2),(3,2,1,2)$$. We would be given the sums $$\{1, 2, 3, 5, 6, 8\}$$. Let us call this set of sums $$f(A)$$.

Is it always possible to uniquely determine the set of integers in $$A$$ from $$f(A)$$ and $$n$$?

The answer turns out to be no. I posted a followup to When does a set of sums uniquely determine a set of values? .

• I understand that the vector is ordered, while the set of sums is not. So B=(2,1,2,3) is different from A, but f(A)=f(B). In this case, the answer is no. – toliveira Oct 15 '18 at 15:42
• @toliveira While this is true, I do think the question is a bit more interesting if we assume the subvectors are not ordered. – Don Thousand Oct 15 '18 at 15:43
• I accidentally read the question wrong initially, and I am interested in the version where you get a multiset of sums instead of just a set. Did you consider that question @felipa? Edit: and possibly you also want to reconstruct the multiset $A$, rather than just its 'set version'. – Mees de Vries Oct 15 '18 at 15:44
• @toliveira The question is about determining the set of integers in $A$ which is $\{1,2,3\}$. Your $B$ has the same set of integers. So in your case I don't think we know the answer is no. – felipa Oct 15 '18 at 15:44
• What are "some linear operations"? This is not obvious to me at all. – Mees de Vries Oct 15 '18 at 15:46

## 2 Answers

No: both $$(1, 1, 2, 2)$$ and $$(1, 1, 1, 3)$$ give you the set $$\{1, 2, 3, 4, 5, 6\}$$.

• These perfect dice! – Parcly Taxel Oct 15 '18 at 15:42
• You can't? What about $(1, 3)$? – Mees de Vries Oct 15 '18 at 15:49
• Yes, you can make $4$ with the second vector, using the last two entries. – Ross Millikan Oct 15 '18 at 15:50
• @MeesdeVries You can take out 1 from both vectors and it still is a counterexample – Don Thousand Oct 15 '18 at 15:51
• How confusing... something got updated since my comment. Nice counterexample! Thank you. – felipa Oct 15 '18 at 15:52

The answer is no.

Take the following subvectors:

$$A = (1, 1, 3)$$$$B = (1,2,2)$$It's easy to see that both vectors have a sum vector of $$[1,2,3,4,5]$$.

• The reconstruction also gets $n$, the length of the original vector. – Mees de Vries Oct 15 '18 at 15:47
• @ypercubeᵀᴹ Nope, the vectors have to be the same length. If not, $(1,1,1)$ and $(1,2)$ would be a counter example. – Don Thousand Oct 15 '18 at 19:34