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
Best Answer
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$.