A large set of low dimensional vectors in $\mathbb{F}_2^L$, which sums of any small subset do not cancel.

27 Views Asked by At

Fix a number $n$ and $L=O(\log n)$. Let $S=\{v_1,\dots,v_n\}$ be a set of vectors where $v_i\in \mathbb{F}_2^L$.

We say that $S$ is "$\alpha$-good" iff for any nonempty subset $T \subset S$ where $|T|\le \alpha$, $$\sum_{s\in T }s\neq0.$$

It is easy to show the existence of a $\alpha$-good set $S$, for any $\alpha<L$, by choosing $s_i$ uniformly randomly, and then use the union bound.

My question is

  • does it exist an $\alpha$-good set $S$, where $\alpha\ge L$ ?
  • does the definition of "$\alpha$-good" have any other name ? or similar concept ?