Return to Answer

Following marshall's comment below, I (sadly) had to completely re-write my original answer.

A famous open conjecture of Paul Erdos, first stated about 80 years ago, is that if all subset sums of an integer set $S\subset[1,n]$ are pairwise distinct, then $|S|<\log_2n+O(1)$ as $n\to\infty$. (Here $\log_2$ denotes the base-$2$ logarithm.) In modern terms, a subset of an abelian group, all of whose subset sums are pairwise distinct, is called dissociated. Similarly to Erdos' original problem, one can ask how large can dissociated subsets of other "natural" sets in abelian groups be. Say, you are asking what is the largest possible size of a dissociated subset of the set $\{0,1\}^n\subset{\mathbb R}^n$, and this particular problem has been studied by a number of authors. It is known that the largest size of its dissociated subset is $$ \frac12(1+o(1))\,n\log_2 n; $$ see, for instance, this paper by Bshouty for details and a historical account.

Added 19.02.24

Here is an argument showing that for $n=10$, at most $28$ vectors can be found. Quite likely, it can be pushed further to yield an even smaller bound.

Assuming that $S=\{s_1,\ldots,s_m\}$ is a dissociated subset of $\{0,1\}^n$, for each $i\in[m]$ and $k\in[n]$ write $s_i=(s_{i1},\ldots,s_{in})$ and  $w_k:=s_{1k}+\dotsb+s_{mk}$. Choose $\epsilon_1,\ldots,\epsilon_m\in\{0,1\}$ independently of each other and randomly with ${\mathsf P}(\epsilon_I=0)={\mathsf P}(\epsilon_i=1)=1/2$, and let  $X_k:=\epsilon_1s_{1k}+\dotsb+\epsilon_ms_{mk}$ $(k\in[n])$; thus,  $X_1,\ldots,X_n$ are random variables with $X_k\sim B(w_k,1/2)$ and  $\epsilon_1s_1+\dotsb+\epsilon_ms_m=(X_1,\ldots,X_n)$.

For each $k\in[n]$, let $I_k:=\left[\frac12w_k-3,\frac12w_k+3\right]$ if $w_k$ is even, and $I_k:=\left[\frac12w_k-\frac52,\frac12w_k+\frac72\right]$ if $w_k$ is odd; notice, that $I_k$ contains exactly seven integers in any case. An easy computation shows that for any $w_k\le n$ (recall that $n=10$), one has $X_k\notin I_k$ with probability not exceeding $\frac{11}{512}$; hence, $X_k\in I_k$ holds for all $k\in[n]$ with probability at least $1-n\cdot\frac{11}{512}=\frac{201}{256}$. We now observe that $X_1\in I_1,\ldots,X_n\in I_n$ means that  $\epsilon_1s_1+\dotsb+\epsilon_ms_m\in I_1\times\dotsb\times I_n$, the probability of which is $2^{-m}T$, where $T$ is the number of subsets sums of  $S$ (that is, the number of choices of $\epsilon_1,\ldots,\epsilon_m$) that fall into the box $I_1\times\dotsb\times I_n$. However, since $S$ is dissociated, the number of such subset sums does not exceed the total number of integer points inside $I_1\times\dotsb\times I_n$, which is $7^{10}$. As a result, we get $$ \frac{201}{256} \le 2^{-m}\cdot7^{10}, $$ and $m\le 28$ follows readily.

Following marshall's comment below, I (sadly) had to completely re-write my original answer.

A famous open conjecture of Paul Erdos, first stated about 80 years ago, is that if all subset sums of an integer set $S\subset[1,n]$ are pairwise distinct, then $|S|<\log_2n+O(1)$ as $n\to\infty$. (Here $\log_2$ denotes the base-$2$ logarithm.) In modern terms, a subset of an abelian group, all of whose subset sums are pairwise distinct, is called dissociated. Similarly to Erdos' original problem, one can ask how large can dissociated subsets of other "natural" sets in abelian groups be. Say, you are asking what is the largest possible size of a dissociated subset of the set $\{0,1\}^n\subset{\mathbb R}^n$, and this particular problem has been studied by a number of authors. It is known that the largest size of its dissociated subset is $$ \frac12(1+o(1))\,n\log_2 n; $$ see, for instance, this paper by Bshouty for details and a historical account.

Added 19.02.14 / Edited 24.02.14###

A bug in my original post fixed, what I can show is that for $n=10$, at most $36$ vectors can be found. Perhaps, with some effort this can be pushed a little further to yield an even smaller bound. Here is the argument.

Assuming that $S=\{s_1,\ldots,s_m\}$ is a dissociated subset of $\{0,1\}^n$, for each $i\in[m]$ and $k\in[n]$ write $s_i=(s_{i1},\ldots,s_{in})$ and  $w_k:=s_{1k}+\dotsb+s_{mk}$. Choose $\epsilon_1,\ldots,\epsilon_m\in\{0,1\}$ independently of each other and randomly with ${\mathsf P}(\epsilon_i=0)={\mathsf P}(\epsilon_i=1)=1/2$, and let  $X_k:=\epsilon_1s_{1k}+\dotsb+\epsilon_ms_{mk}$ $(k\in[n])$; thus,  $X_1,\ldots,X_n$ are random variables with $X_k\sim B(w_k,1/2)$ and  $\epsilon_1s_1+\dotsb+\epsilon_ms_m=(X_1,\ldots,X_n)$.

Fix an integer $b\ge 0$ and for each $k\in[n]$, let $I_k$ denote the block of $b$ consecutive integers, centered around $w_k/2$. (If $w_k$ and $b$ are of the same parity, there is a unique such block, otherwise there are two blocks.) Write $p_w(b)$ for the length $w+1-b$ tail of the binomial distribution $B(w,1/2)$; that is, $p_w(b)$ is the probability that a random variable with this distribution will not take one of its $b$ most probable values. We then have ${\mathsf P}(X_k\notin I_k)=p_{w_k}(b)\le p_m(b)$ for each $k\in[n]$; hence, by the union bound, $X_k\in I_k$ holds for all $k\in[n]$ with probability at least $1-n\cdot p_m(b)$. 

We now observe that $X_1\in I_1,\ldots,X_n\in I_n$ means that  $\epsilon_1s_1+\dotsb+\epsilon_ms_m\in I_1\times\dotsb\times I_n$, the probability of which is $2^{-m}T$, where $T$ is the number of subsets sums of  $S$ (that is, the number of choices of $\epsilon_1,\ldots,\epsilon_m$) that fall into the box $I_1\times\dotsb\times I_n$. However, since $S$ is dissociated, the number of such subset sums does not exceed the total number of integer points inside $I_1\times\dotsb\times I_n$, which is $b^n$. As a result, we get $$ 2^{-m}b^n \ge 1-n\cdot p_m(b), \tag{$\ast$} $$ and to show that $m\le 36$ it remains to notice that ($\ast$) is invalid for $n=10,\ m=37$, and $b=11$.

Following marshall's comment below, I (sadly) had to completely re-write my original answer.

A famous open conjecture of Paul Erdos, first stated about 80 years ago, is that if all subset sums of an integer set $S\subset[1,n]$ are pairwise distinct, then $|S|<\log_2n+O(1)$ as $n\to\infty$. (Here $\log_2$ denotes the base-$2$ logarithm.) In modern terms, a subset of an abelian group, all of whose subset sums are pairwise distinct, is called dissociated. Similarly to Erdos' original problem, one can ask how large can dissociated subsets of other "natural" sets in abelian groups be. Say, you are asking what is the largest possible size of a dissociated subset of the set $\{0,1\}^n\subset{\mathbb R}^n$, and this particular problem has been studied by a number of authors. It is known that the largest size of its dissociated subset is $$ \frac12(1+o(1))\,n\log_2 n; $$ see, for instance, this paper by Bshouty for details and a historical account.

Added 19.02.24

Here is an argument showing that for $n=10$, at most $30$ vectors can be found. No doubt, it can be pushed further to yield an even smaller bound.

Assuming that $S=\{s_1,\ldots,s_m\}$ is a dissociated subset of $\{0,1\}^n$, for each $i\in[m]$ and $k\in[n]$ write $s_i=(s_{i1},\ldots,s_{in})$ and $w_k:=s_{1k}+\dotsb+s_{mk}$. Choose $\epsilon_1,\ldots,\epsilon_m\in\{0,1\}$ independently of each other and randomly with ${\mathsf P}(\epsilon=0)={\mathsf P}(\epsilon=1)=1/2$, and let $X_k:=\epsilon_1s_{1k}+\dotsb+\epsilon_ms_{mk}$ $(k\in[n])$; thus, $X_1,\ldots,X_n$ are random variables with $X_k\sim B(w_k,1/2)$ and $\epsilon_1s_1+\dotsb+\epsilon_ms_m=(X_1,\ldots,X_n)$.

Fix an integer $b$ and for each $k\in[n]$, let $I_k:=(w_k-b,w_k+b)$. By a standard large deviation bound, $X_k\notin I_i$ holds with probability less than $2e^{-2b^2/w_k}\le 2e^{-2b^2/n}$; hence, $X_k\in I_k$ holds for all $k\in[n]$ with probability more than $1-2ne^{-2b^2/n}$. We now observe that $X_1\in I_1,\ldots,X_n\in I_n$ means that $\epsilon_1s_1+\dotsb+\epsilon_ms_m\in I_1\times\dotsb\times I_n$, the probability of which is $2^{-m}T$, where $T$ is the number of subsets sums of $S$ (that is, the number of choices of $\epsilon_1,\ldots,\epsilon_m$) that fall into the box $I_1\times\dotsb\times I_n$. However, since $S$ is dissociated, the number of these subset sums does not exceed the total number of integer points inside $I_1\times\dotsb\times I_n$, which is $(2b-1)^n$. As a result, we get $$ 1-2ne^{-2b^2/n} < 2^{-m}(2b-1)^n. $$

For $n=10$, we optimize by choosing $b=4$. This results in $7^{10}\cdot 2^{-m}>1-20e^{-3.2}$, and $m\le 30$ follows readily.

Following marshall's comment below, I (sadly) had to completely re-write my original answer.

A famous open conjecture of Paul Erdos, first stated about 80 years ago, is that if all subset sums of an integer set $S\subset[1,n]$ are pairwise distinct, then $|S|<\log_2n+O(1)$ as $n\to\infty$. (Here $\log_2$ denotes the base-$2$ logarithm.) In modern terms, a subset of an abelian group, all of whose subset sums are pairwise distinct, is called dissociated. Similarly to Erdos' original problem, one can ask how large can dissociated subsets of other "natural" sets in abelian groups be. Say, you are asking what is the largest possible size of a dissociated subset of the set $\{0,1\}^n\subset{\mathbb R}^n$, and this particular problem has been studied by a number of authors. It is known that the largest size of its dissociated subset is $$ \frac12(1+o(1))\,n\log_2 n; $$ see, for instance, this paper by Bshouty for details and a historical account.

Added 19.02.24

Here is an argument showing that for $n=10$, at most $28$ vectors can be found. Quite likely, it can be pushed further to yield an even smaller bound.

Assuming that $S=\{s_1,\ldots,s_m\}$ is a dissociated subset of $\{0,1\}^n$, for each $i\in[m]$ and $k\in[n]$ write $s_i=(s_{i1},\ldots,s_{in})$ and $w_k:=s_{1k}+\dotsb+s_{mk}$. Choose $\epsilon_1,\ldots,\epsilon_m\in\{0,1\}$ independently of each other and randomly with ${\mathsf P}(\epsilon_I=0)={\mathsf P}(\epsilon_i=1)=1/2$, and let $X_k:=\epsilon_1s_{1k}+\dotsb+\epsilon_ms_{mk}$ $(k\in[n])$; thus, $X_1,\ldots,X_n$ are random variables with $X_k\sim B(w_k,1/2)$ and $\epsilon_1s_1+\dotsb+\epsilon_ms_m=(X_1,\ldots,X_n)$.

For each $k\in[n]$, let $I_k:=\left[\frac12w_k-3,\frac12w_k+3\right]$ if $w_k$ is even, and $I_k:=\left[\frac12w_k-\frac52,\frac12w_k+\frac72\right]$ if $w_k$ is odd; notice, that $I_k$ contains exactly seven integers in any case. An easy computation shows that for any $w_k\le n$ (recall that $n=10$), one has $X_k\notin I_k$ with probability not exceeding $\frac{11}{512}$; hence, $X_k\in I_k$ holds for all $k\in[n]$ with probability at least $1-n\cdot\frac{11}{512}=\frac{201}{256}$. We now observe that $X_1\in I_1,\ldots,X_n\in I_n$ means that $\epsilon_1s_1+\dotsb+\epsilon_ms_m\in I_1\times\dotsb\times I_n$, the probability of which is $2^{-m}T$, where $T$ is the number of subsets sums of $S$ (that is, the number of choices of $\epsilon_1,\ldots,\epsilon_m$) that fall into the box $I_1\times\dotsb\times I_n$. However, since $S$ is dissociated, the number of such subset sums does not exceed the total number of integer points inside $I_1\times\dotsb\times I_n$, which is $7^{10}$. As a result, we get $$ \frac{201}{256} \le 2^{-m}\cdot7^{10}, $$ and $m\le 28$ follows readily.

Following marshall's comment below, I (sadly) had to completely re-write my original answer.

A famous open conjecture of Paul Erdos, first stated about 80 years ago, is that if all subset sums of an integer set $S\subset[1,n]$ are pairwise distinct, then $|S|<\log_2n+O(1)$ as $n\to\infty$. (Here $\log_2$ denotes the base-$2$ logarithm.) In modern terms, a subset of an abelian group, all of whose subset sums are pairwise distinct, is called dissociated. Similarly to Erdos' original problem, one can ask how large can dissociated subsets of other "natural" sets in abelian groups be. Say, you are asking what is the largest possible size of a dissociated subset of the set $\{0,1\}^n\subset{\mathbb R}^n$, and this particular problem has been studied by a number of authors. It is known that the largest size of its dissociated subset is $$ \frac12(1+o(1))\,n\log_2 n; $$ see, for instance, this paper by Bshouty for details and a historical account.

Here is an argument showing that for $n=10$, at most $30$ vectors can be found. No doubt, it can be pushed further to yield an even smaller bound.

Assuming that $S=\{s_1,\ldots,s_m\}$ is a dissociated subset of $\{0,1\}^n$, for each $i\in[m]$ and $k\in[n]$ write $s_i=(s_{i1},\ldots,s_{in})$ and $w_k:=s_{1k}+\dotsb+s_{mk}$. Choose $\epsilon_1,\ldots,\epsilon_m\in\{0,1\}$ independently of each other and randomly with ${\mathsf P}(\epsilon=0)={\mathsf P}(\epsilon=1)=1/2$, and let $X_k:=\epsilon_1s_{1k}+\dotsb+\epsilon_ms_{mk}$ $(k\in[n])$; thus, $X_1,\ldots,X_n$ are random variables with $X_k\sim B(w_k,1/2)$ and $\epsilon_1s_1+\dotsb+\epsilon_ms_m=(X_1,\ldots,X_n)$.

Fix an integer $b$ and for each $k\in[n]$, let $I_k:=(w_k-b,w_k+b)$. By a standard large deviation bound, $X_k\notin I_i$ holds with probability less than $2e^{-2b^2/w_k}\le 2e^{-2b^2/n}$; hence, $X_k\in I_k$ holds for all $k\in[n]$ with probability more than $1-2ne^{-2b^2/n}$. We now observe that $X_1\in I_1,\ldots,X_n\in I_n$ means that $\epsilon_1s_1+\dotsb+\epsilon_ms_m\in I_1\times\dotsb\times I_n$, the probability of which is $2^{-m}T$, where $T$ is the number of subsets sums of $S$ (that is, the number of choices of $\epsilon_1,\ldots,\epsilon_m$) that fall into the box $I_1\times\dotsb\times I_n$. However, since $S$ is dissociated, the number of these subset sums does not exceed the total number of integer points inside $I_1\times\dotsb\times I_n$, which is $(2b-1)^n$. As a result, we get $$ 1-2ne^{-2b^2/n} < 2^{-m}(2b-1)^n. $$

For $n=10$, we optimize by choosing $b=4$. This results in $7^{10}\cdot 2^{-m}>1-20e^{-3.2}$, and $m\le 30$ follows readily.

Following marshall's comment below, I (sadly) had to completely re-write my original answer.

A famous open conjecture of Paul Erdos, first stated about 80 years ago, is that if all subset sums of an integer set $S\subset[1,n]$ are pairwise distinct, then $|S|<\log_2n+O(1)$ as $n\to\infty$. (Here $\log_2$ denotes the base-$2$ logarithm.) In modern terms, a subset of an abelian group, all of whose subset sums are pairwise distinct, is called dissociated. Similarly to Erdos' original problem, one can ask how large can dissociated subsets of other "natural" sets in abelian groups be. Say, you are asking what is the largest possible size of a dissociated subset of the set $\{0,1\}^n\subset{\mathbb R}^n$, and this particular problem has been studied by a number of authors. It is known that the largest size of its dissociated subset is $$ \frac12(1+o(1))\,n\log_2 n; $$ see, for instance, this paper by Bshouty for details and a historical account.

Added 19.02.24

Here is an argument showing that for $n=10$, at most $30$ vectors can be found. No doubt, it can be pushed further to yield an even smaller bound.

Assuming that $S=\{s_1,\ldots,s_m\}$ is a dissociated subset of $\{0,1\}^n$, for each $i\in[m]$ and $k\in[n]$ write $s_i=(s_{i1},\ldots,s_{in})$ and $w_k:=s_{1k}+\dotsb+s_{mk}$. Choose $\epsilon_1,\ldots,\epsilon_m\in\{0,1\}$ independently of each other and randomly with ${\mathsf P}(\epsilon=0)={\mathsf P}(\epsilon=1)=1/2$, and let $X_k:=\epsilon_1s_{1k}+\dotsb+\epsilon_ms_{mk}$ $(k\in[n])$; thus, $X_1,\ldots,X_n$ are random variables with $X_k\sim B(w_k,1/2)$ and $\epsilon_1s_1+\dotsb+\epsilon_ms_m=(X_1,\ldots,X_n)$.

Fix an integer $b$ and for each $k\in[n]$, let $I_k:=(w_k-b,w_k+b)$. By a standard large deviation bound, $X_k\notin I_i$ holds with probability less than $2e^{-2b^2/w_k}\le 2e^{-2b^2/n}$; hence, $X_k\in I_k$ holds for all $k\in[n]$ with probability more than $1-2ne^{-2b^2/n}$. We now observe that $X_1\in I_1,\ldots,X_n\in I_n$ means that $\epsilon_1s_1+\dotsb+\epsilon_ms_m\in I_1\times\dotsb\times I_n$, the probability of which is $2^{-m}T$, where $T$ is the number of subsets sums of $S$ (that is, the number of choices of $\epsilon_1,\ldots,\epsilon_m$) that fall into the box $I_1\times\dotsb\times I_n$. However, since $S$ is dissociated, the number of these subset sums does not exceed the total number of integer points inside $I_1\times\dotsb\times I_n$, which is $(2b-1)^n$. As a result, we get $$ 1-2ne^{-2b^2/n} < 2^{-m}(2b-1)^n. $$

For $n=10$, we optimize by choosing $b=4$. This results in $7^{10}\cdot 2^{-m}>1-20e^{-3.2}$, and $m\le 30$ follows readily.