12
$\begingroup$

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.

$\endgroup$
16
  • 3
    $\begingroup$ 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)$? $\endgroup$
    – antkam
    Nov 9, 2018 at 20:26
  • 1
    $\begingroup$ @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) $\endgroup$
    – graffe
    Nov 9, 2018 at 20:51
  • 1
    $\begingroup$ If $S_A$ is a set, shouldn't it be $\{1,3,4,\cdots\}$, i.e. an ordered list without repetitions ? $\endgroup$
    – G Cab
    Nov 10, 2018 at 19:48
  • 3
    $\begingroup$ 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. $\endgroup$
    – Erick Wong
    Nov 10, 2018 at 21:13
  • 3
    $\begingroup$ @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). $\endgroup$
    – graffe
    Nov 14, 2018 at 10:47

1 Answer 1

9
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ how did you find the counterexample? search by a program? hand-crafted? $\endgroup$
    – antkam
    Nov 15, 2018 at 15:08
  • 3
    $\begingroup$ @antkam I wrote some code. There are no counter examples with arrays of length shorter than 5. $\endgroup$
    – graffe
    Nov 15, 2018 at 16:13
  • 1
    $\begingroup$ 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. $\endgroup$
    – Erick Wong
    Nov 15, 2018 at 21:07
  • 1
    $\begingroup$ @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? $\endgroup$
    – graffe
    Nov 15, 2018 at 21:52
  • 2
    $\begingroup$ 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). $\endgroup$
    – Erick Wong
    Nov 15, 2018 at 22:18

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.