Skip to main content
5 of 7
added 24 characters in body
Seva
  • 23k
  • 2
  • 59
  • 141

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.

Seva
  • 23k
  • 2
  • 59
  • 141