3
$\begingroup$

Consider a set $S = \{x_1, \dots, x_n\} \subset \mathbb{Q}\setminus\{0\}$ and assume that for any $I, J \subset [n]$ with $I \neq J$ we have that

\begin{equation} \sum_{i \in I} x_i \neq \sum_{j \in J} x_j \end{equation}

I would like to know if sets of this form have a name (possibly changing $\mathbb{Q}$ for $\mathbb{R}$ or $\mathbb{Z}$), or if there are any known conditions to ensure that $S$ satisfies this condition with some probability.

For example, this holds almost surely for $\mathbb{R}$ if the elements in $S$ are drawn from a continuous distribution, but I am interested in the other cases.

Thanks.

$\endgroup$
9
  • 1
    $\begingroup$ Related: oeis.org/A201052 $\endgroup$
    – joro
    Oct 22, 2014 at 12:45
  • 1
    $\begingroup$ OK. If you disallow intersection, it is NP-complete over the naturals. $\endgroup$
    – joro
    Oct 22, 2014 at 13:04
  • 2
    $\begingroup$ There may be no better name than distinct subset sums. $\endgroup$
    – Ben Barber
    Oct 22, 2014 at 13:07
  • 2
    $\begingroup$ It does not matter whether you allow $I$ and $J$ to intersect, as replacing $I$ by $I \setminus J$ and $J$ by $J \setminus I$ will preserve equality. $\endgroup$
    – Ben Barber
    Oct 22, 2014 at 13:08
  • 2
    $\begingroup$ In the additive combinatorics literature such sets are called ``dissociated". $\endgroup$
    – Lucia
    Oct 22, 2014 at 13:55

1 Answer 1

2
$\begingroup$

Regarding conditions to decide.

It is NP-complete over the positive integers.

As pointed by Ben Barber, "It does not matter whether you allow $I$ and $J$ to intersect, as replacing $I$ by $I \setminus J$ and $J$ by $J \setminus I$ will preserve equality."

ON THE COMPLEXITY OF VARIATIONS OF EQUAL SUM SUBSETS, p. 1

The Equal Sum Subsets problem, where we are given a set of positive integers and we ask for two nonempty disjoint subsets such that their elements add up to the same total, is known to be NP-hard.

Also related is OEIS A201052 a(n) is the maximal number c of integers that can be chosen from {1,2,...,n} so that all 2^c subsets have distinct sums.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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