Consider an array of positive integers $A$ of length $n$. Now consider the set of sums of all the contiguously indexed subarrays of $A$. For example if $A = (1,3,5,6)$ then the set would be $S_A = \{1,3,5,6,4,8,11,9,14,15\}$.

If the sums of all contiguously indexed subarrays are distinct (as they are in the example above), does the set of these sums uniquely specify the set of integers in the array the sums were calculated from?

We can certainly compute the smallest element in the original array as it is the smallest element in $S_A$. Similarly there must be a value in the original array which is the largest value in $S_A$ minus the second largest.

To show one of the subtleties of this problem, consider $A = (1, 6, 2, 3)$ and $S_A = \{1, 6, 2, 3, 7, 8, 5, 9, 11, 12\}$. We can immediately tell from $S_A$ that $1$ occurs somewhere in $A$. Similarly we can tell that $2$ occurs somewhere in $A$. But what can we tell about $3$? If $1$ and $2$ were next to each then as $1+2=3$ we would know that $3$ can't be in $A$. But if $1$ and $2$ are not next to each in $A$ then we know $3$ must be in $A$. How do we tell which case we are in?

The answer turns out to be NO. Take $A = (4, 6, 5, 2, 1)$ and $B = (3, 8, 2, 4, 1)$. We have that $S_A = S_B$ but the set of elements in $A$ and $B$ are distinct.

  • 3
    yeah, there have been a few questions recently (in the last few months) dealing with subsequence sums of an array. so i was just wondering where all the common interest comes from. :) OK, lets clarify a few things: (1) $S_A$ is a SET, so you should use curly braces like $S_A = \{1,3,5,...\}$. (2) your highlighted question asks does $S_A$ uniquely specify the SET of integers, e.g. $\{1, 3, 5, 6\}$, but is that what you mean? Or do you mean to ask if $S_A$ uniquely specify the SEQUENCE (ARRAY) of integers e.g. $(1,3,5,6)$ -- which may still be true, modulo sequence reversal $(6,5,3,1)$? – antkam Nov 9 at 20:26
  • 1
    @antkam I asked about the set only because it’s a weaker claim. That is it is more likely to be true. Of course if it’s also true for the array, modulo reversal, that’s even better. (Fixed bracket error now) – felipa Nov 9 at 20:51
  • 1
    If $S_A$ is a set, shouldn't it be $\{1,3,4,\cdots\}$, i.e. an ordered list without repetitions ? – G Cab Nov 10 at 19:48
  • 3
    This is a version of the “turnpike” problem, or equivalently the “partial digest” problem. It is known that there can be very many distinct arrays with the same set of substring sums for large $n$, however I am not aware of any results with the restriction that all the sums are distinct. Nice question. – Erick Wong Nov 10 at 21:13
  • 3
    @mathlove No sorry that isn't right. The question is if for all arrays A (which are ordered) does $S_A$ (unordered) uniquely determine the set (unordered) of integers in A under the constraint that the subarray sums of A are all distinct. In your example the set $\{1,2,3\}$ does indeed tell us that A contains exactly the integers 1 and 2 (but not their order). – Anush Nov 14 at 10:47
up vote 6 down vote accepted

The answer turns out to be NO. Take $A = (4, 6, 5, 2, 1)$ and $B = (3, 8, 2, 4, 1)$. We have that $S_A = S_B$ but the set of elements in $A$ and $B$ are distinct.

  • how did you find the counterexample? search by a program? hand-crafted? – antkam Nov 15 at 15:08
  • 2
    @antkam I wrote some code. There are no counter examples with arrays of length shorter than 5. – felipa Nov 15 at 16:13
  • To clarify, there are no counter examples at all for length < 5 since it is known that every array of length $\le 4$ is uniquely determined (up to reversal) by its multi set of substring sums. – Erick Wong Nov 15 at 21:07
  • @ErickWong Yes. I still have no good feeling at all about this problem area. Which arrays of length > 4 are uniquely determined (up to reversal) by the set of substring sums? Are any necessary conditions known? – felipa Nov 15 at 21:52
  • 1
    There is a decent amount known about this actually. I recommend reading “Reconstructing Sets from Interpoint Distances” by Skiena, Smith, Lemke, which you should be able to find a PDF for. They give a nice argument that the set of solutions for a given set of sums has a hypercube structure, in particular it is always a power of $2$ (if non-zero). – Erick Wong Nov 15 at 22:18

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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