12
$\begingroup$

This is a follow up to a question about determining the set of values from a set of sums.

We consider the following setup:

Consider a 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)$.

It turns out it is not always possible to uniquely determine the set of integers in $A$ from the pair $(f(A), n)$? For example:

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

both give the same set of sums $f(A) = f(B) = \{1,2,3,4,5\}$.

However in some cases it is possible. For example, if $n=3$ and $f(C) = \{1,2,3,5,6\}$ then we know that $\operatorname{set}(C) = \{1, 2, 3\}$.

This raises the following question:

Is it possible to characterise which pairs $(f(X), n)$ uniquely determine the set of values in the array $X$?

$\endgroup$
  • $\begingroup$ Maybe it suffices to know that in the sum, there exist a one or a zero??? $\endgroup$ – user7427029 Oct 15 '18 at 22:50
  • 3
    $\begingroup$ @user7427029 I don’t quite understand your comment. Zero isn’t allowed as all the values in the arrays are positive. Also there is a 1 in the set of sums for both A and B in my example so that idea doesn’t work. $\endgroup$ – felipa Oct 16 '18 at 6:45
  • 1
    $\begingroup$ Observations: $a := \min_{c\in f(X)} c \in set(X)$ and $S := \sum_{i=1}^{n} X_i = \max_{c\in f(X)} c$. Maybe one can conclude $a = X_1$ or $a = X_n$, if $S - a \in set(X)$. And then this can be applied recursively? $\endgroup$ – Frozn Oct 16 '18 at 8:48
  • $\begingroup$ I should not write comments nightly. I thought of something like what @Frozn proposes. Two conjectures / ideas (I'm in a hurry): The question asks for something like the fundamental theorem of arithmetic concerning addition. Zeckendorf's theorem may help. $\endgroup$ – user7427029 Oct 16 '18 at 17:01
  • $\begingroup$ You may find useful results in links from a search for finite radon transform : google.com/… $\endgroup$ – Ethan Bolker Oct 17 '18 at 19:50

Your Answer

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

Browse other questions tagged or ask your own question.