Number of vectors so that no two subset sums are equal

Question

Consider all $10$-tuple vectors each element of which is either $1$ or $0$. It is very easy to select a set $v_1,\dots,v_{10}= S$ of $10$ such vectors so that no two distinct subsets of vectors $S_1 \subset S$ and $S_2 \subset S$ have the same sum. Here $\sum_{v \in S_i} v$ assumes simple element-wise addition over $\mathbb{R}$. For example, if we take the vectors that are the columns of the identity matrix as $S$ this will do.

What is the maximum number of vectors one can choose that have this property? Is there a counting argument that solves this?

---

A small clarification. The sum of two vectors in this problem is another vector.

---

Current records:

• Lower bound: $19$. First given by Brendan McKay over at MO.
• Upper bound: $30$. First given by Brendan McKay over at MO.

---

Cross-posted to https://mathoverflow.net/questions/157634/number-of-vectors-so-that-no-two-subset-sums-are-equal

Answer 1

UPDATE:

My best result (for vectors with $10$ elements) is $18$.

(But Brendan McKay obtained set of 19 vectors: see cited above http://mathoverflow.net link).

Example of $18$ sum-free binary vectors:

$\qquad(0,0,0,0,1,1,0,0,1,1)$,
$\qquad(0,0,0,1,1,0,1,0,0,1)$,
$\qquad(0,0,1,1,0,1,0,0,1,1)$,
$\qquad(0,0,1,1,1,1,0,1,1,0)$,
$\qquad(0,1,0,0,1,1,1,0,1,0)$,
$\qquad(0,1,0,1,0,0,0,1,0,0)$,
$\qquad(0,1,0,1,0,0,1,1,1,0)$,
$\qquad(0,1,0,1,1,0,0,0,0,1)$,
$\qquad(0,1,1,0,1,0,0,1,0,1)$,
$\qquad(0,1,1,1,0,1,1,1,0,1)$,
$\qquad(1,0,0,0,1,0,1,1,0,1)$,
$\qquad(1,0,0,0,1,0,1,1,1,1)$,
$\qquad(1,0,0,1,0,0,0,1,0,1)$,
$\qquad(1,0,1,0,0,1,0,1,0,1)$,
$\qquad(1,1,0,0,0,1,1,0,0,1)$,
$\qquad(1,1,0,0,1,0,0,0,1,1)$,
$\qquad(1,1,0,1,1,1,0,0,0,0)$,
$\qquad(1,1,1,0,1,0,1,0,0,0)$.

Example of $17$ sum-free binary vectors:

$\qquad(0,0,0,0,0,0,1,1,1,1)$,
$\qquad(0,0,0,0,1,0,0,0,1,1)$,
$\qquad(0,0,0,1,1,1,1,0,1,0)$,
$\qquad(0,0,1,1,1,0,0,0,1,1)$,
$\qquad(0,1,0,1,1,1,0,1,0,1)$,
$\qquad(0,1,1,0,0,0,0,1,1,1)$,
$\qquad(0,1,1,1,0,0,0,1,1,0)$,
$\qquad(0,1,1,1,0,0,1,0,1,0)$,
$\qquad(1,0,1,1,0,0,0,1,0,0)$,
$\qquad(1,0,1,1,1,0,0,0,0,1)$,
$\qquad(1,0,1,1,1,0,0,1,1,0)$,
$\qquad(1,1,0,0,0,1,0,0,0,0)$,
$\qquad(1,1,0,0,1,0,0,0,1,1)$,
$\qquad(1,1,0,1,0,0,1,0,0,0)$,
$\qquad(1,1,0,1,0,0,1,1,0,0)$,
$\qquad(1,1,1,0,1,1,1,1,0,0)$,
$\qquad(1,1,1,1,1,1,1,1,0,1)$.

And example of $11$ sum-free binary vectors (just for curious):

$\qquad(1,0,0,0,0,0,0,0,0,0)$,
$\qquad(0,1,0,0,0,0,0,0,0,0)$,
$\qquad(0,0,1,0,0,0,0,0,0,0)$,
$\qquad(0,0,0,1,0,0,0,0,0,0)$,
$\qquad(0,0,0,0,1,0,0,0,0,0)$,
$\qquad(0,0,0,0,0,1,0,0,0,0)$,
$\qquad(0,0,0,0,0,0,1,0,0,0)$,
$\qquad(0,0,0,0,0,0,0,1,0,0)$,
$\qquad(0,0,0,0,0,0,0,1,1,0)$,
$\qquad(0,0,0,0,0,0,0,1,0,1)$,
$\qquad(0,0,0,0,0,0,0,0,1,1)$.

---

For $3,4,5,6,7,8,9,10$-dimensional vectors my best results are $4,5,7,9,12,14,16,18$ accordingly.

Answer 2

An SSD-sequence is a sequence of positive integer numbers in which distinct subsets have distinct sums. If we fill our vectors with the binary representations of the elements of such a sequence, we clearly end with a sum-disjoint set of vectors. For istance, taking the SSD-sequence $3,5,6,7$ we have that $011,101,110,111$ are four sum-disjoint vectors in $\{0,1\}^3$. Erdos conjectured that $$M_n = \min\{\max(S)\;|\; S \mbox{ is a SSD sequence of length } n\}$$ satisfies $M_n \geq c\cdot 2^n$ for some constant $c$, and the problem is still open. On the other hand, it is easy to see that $M_n\leq\frac{1}{2}2^n$ by simply taking powers of two (or the identity matrix in our initial problem). Bohman proved in 1996 that the $k$ elements $s_i=a_k-a_{k-i}$ are an SSD-set, where $1\leq i\leq k$ and $\{a_n\}_{n\in\mathbb{N}}$ is the Conway-Guy sequence $$ 0, 1, 2, 4, 7, 13, 24, 44, 84, 161, 309, 594, 1164, 2284, 4484, 8807, 17305, 34301, 68008, 134852, 267420, 530356, 1051905, 2095003, 4172701, 8311101, 16554194, 32973536, 65679652, 130828948, 261127540, 521203175, 1040311347, 2076449993, \ldots$$ defined by $a_0=0,a_1=1$ and $$ a_{n+1} = 2a_n - a_{n-\lfloor\frac{1}{2}+\sqrt{2n}\rfloor}. $$ This gave the bound $M_n\leq 2^{n-2}$ for $n\geq 20$, for istance. Taking $k=11$ we get the eleven-elements SSD set: $$\{594,593,592,590,587,581,570,550,510,433,285\}$$ and by taking binary representations we have eleven sum-disjoint vectors in $\{0,1\}^{10}$ - in general, $n+2$ sum-disjoint vectors in $\{0,1\}^n$ for any $n\geq 20$ - not so many, but still better than the trivial bound.

We are clearly wasting a lot of information, since, for istance, $\{3,4,5,6,8\}$ is not an SSD-set (due to $5+6=8+3$), but the binary representations of $\{3,4,5,6,8\}$ give a five-elements sum-disjoint set of vectors in $\{0,1\}^4$.

Since there are $4$ sum-disjoint vectors in $\{0,1\}^3$, a clever tensor-trick gives that there are at least $\left\lfloor\frac{4n}{3}\right\rfloor$ sum-disjoint vectors in $\{0,1\}^n$. In the case $n=10$, these thirteen vectors are: $$\begin{array}{*10{c}} 1,0,0,0,0,0,0,0,0,0\\ 0,1,1,0,0,0,0,0,0,0\\ 0,1,0,1,0,0,0,0,0,0\\ 0,1,0,0,0,0,0,0,0,0\\ 0,0,1,1,0,0,0,0,0,0\\ 0,0,0,0,1,1,0,0,0,0\\ 0,0,0,0,1,0,1,0,0,0\\ 0,0,0,0,1,0,0,0,0,0\\ 0,0,0,0,0,1,1,0,0,0\\ 0,0,0,0,0,0,0,1,1,0\\ 0,0,0,0,0,0,0,1,0,1\\ 0,0,0,0,0,0,0,1,0,0\\ 0,0,0,0,0,0,0,0,1,1 \end{array}.$$ For the same reason, since there are $7$ sum-disjoint vectors in $\{0,1\}^5$, there are at least $14$ sum-disjoint vectors in $\{0,1\}^{10}$ and at least $\left\lfloor\frac{7n}{5}\right\rfloor$ sum-disjoint vectors in $\{0,1\}^n$.

Monte-Carlo computations below seem to suggest that there are at least $2n-3$ sum-disjoint vectors in $\{0,1\}^n$ for any $n\geq 4$. In order to fix notation, let $I_n$ be the maximum number of sum-disjoint vectors in $\{0,1\}^n$. If we manage to prove $$I_{n+1}\geq I_n+2,\tag{1}$$ we prove the $2n-3$-bound.

A simple way to achieve $(1)$ would be to take the vectors giving $I_n$, augment them with a zero in the first coordinate, then take the two additional vectors $(1,0,0,\ldots)$ and $(1,1,1,\ldots)$. Unluckyly, this naive construction does not work since $(1,1,1,1)=(1,0,0,0)+(0,1,0,0)+(0,0,1,1)$, but may be we can fix it.

There is also a graph-theoretic interpretation that may be useful. Consider a bipartite undirected graph $G$ with $m$ red nodes and $n$ ($10$ in the original problem) blue nodes (emitters), where distinct blue nodes have distinct neighbourhoods and there are only edges between a blue node and a red node. Every emitter can give a $+1$,$0$ or $-1$ weight to the elements of the set of its outcoming edges; the weight of a blue vertex is the sum of the weigths of its incoming edges. Sum-free property: if for every non-trivial weigth-assignment there exists a blue vertex with non-zero weight, we get $m$ sum-disjoint elements in $\{0,1\}^n$. For istance, the following "sum-free" graph:

gives $I_3\geq 4$ through the set of sum-free vectors $110,101,110,001$ corresponding to the neighbourhoods of the red nodes. The graph corresponding to the SSD-set $011,101,110,111$ is even nicer:

In the this paper Lev shows, through the probabilistic method, $$ I_n \geq \frac{1}{\log_2 9}\cdot(1+o(1))\cdot n\log_2(n), $$ and I think it is worth to reproduce its arguments in the specific $n=10$ case. Let $S=\{-1,0,1\}^{17}$. For any $s\in S$, let $m^+$ be the number of positive coordinates of $s$ and $m^-$ the number of negative coordinates of $s$. For a random chosen vector $d\in\{0,1\}^{17}$ the probability of being orthogonal to $s$ is equal to:

$$ \frac{1}{2^{m^+ + m^-}}\sum_{j=0}^{\min(m^-,m^+)}\binom{m^+}{j}\binom{m^-}{j}=\frac{1}{2^{m^+ + m^-}}\binom{m^+ + m^-}{m^+},$$

hence the probability for $10$ randomly chosen vectors to be simultaneously orthogonal to $s$ is very small. Since the number of elements of $S$ of a given $(m^-,m^+)$-type is just $\binom{17}{m^+ + m^-}\binom{m^+ + m^-}{m^+}$, in order to prove $I_{10}\geq 17$ it is sufficient to show that:

$$\sum_{1\leq m^+ + m^- \leq 17}\binom{17}{m^+ + m^-}\binom{m^+ + m^-}{m^+}\left(\frac{1}{2^{m^+ + m^-}}\binom{m^+ + m^-}{m^+}\right)^{10} <1,$$

that is true by direct computation. Moreover, I am now noticing that through a probabilistic argument (the Hoeffding bound) Seva on MO pushed the upper bound down to $30$.

Answer 3

Given a particular subset $S'\subset S$, you can think of each position in the sum as a measurement: the $i$-th measurement tells you how many elements of $S'$ have a $1$ in the $i$-th position. Equivalently, the $i$-th measurement gives you the size of $S'\cap A_i$, where $A_i=\{x\in S \;|\; \pi_i(x)=1\}$. How large can $S$ be if you can identify an arbitrary subset using $n$ such measurements? Well, if $|S|=k$, then each measurement can have $k+1$ different outcomes, and so the most information it can give you is $\log_2(k+1)$ bits. Since you need to distinguish between $2^k$ subsets, you need to obtain $k$ bits of information in total, so $$ n \log_2(k+1) \ge k, $$ or $$ \frac{k}{\log_2(k+1)} \le n. $$ For $n=10$, for instance, this implies $|S| \le 59$.

Answer 4

A slight improvement to the upper bound showing that the answer is $\le 47$. Assume contrariwise that a set $S$ of $48$ such vectors would exist. The set $S$ has $$ \sum_{k=1}^{24}{48\choose k}=156\,861\,290\,196\,877 $$ subsets of at most $24$ elements. The sum vectors of those subsets belong to the set $\{0,1,\ldots,24\}^{10}$ that has $25^{10}=95\,367\,431\,640\,625$ elements. Therefore a collision is inevitable by the pigeonhole principle.