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
    Commented Oct 22, 2014 at 12:45
  • 1
    $\begingroup$ OK. If you disallow intersection, it is NP-complete over the naturals. $\endgroup$
    – joro
    Commented Oct 22, 2014 at 13:04
  • 2
    $\begingroup$ There may be no better name than distinct subset sums. $\endgroup$
    – Ben Barber
    Commented 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
    Commented Oct 22, 2014 at 13:08
  • 2
    $\begingroup$ In the additive combinatorics literature such sets are called ``dissociated". $\endgroup$
    – Lucia
    Commented 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .