Existence of family of binary vectors with certain spanning properties.

65 Views Asked by At

Given dimension $d$, can you construct a full-rank family of vectors $V \subseteq \mathbb F_2^d$, satisfying the following property?

  • If $U \subseteq V$ is an independent family of $\Omega(d)$ vectors, then $U$ spans $\omega\left(\frac{1}{\log d}\right)$ fraction of $V \setminus U$. Formally, $$ |span(U) \cap (V\setminus U)| \geq \omega\left(\frac{1}{\log d}\right)\cdot |V\setminus U|.$$

Note that $\Omega(.)$ and $\omega(.)$ are as used in "Big O notation". Specifically, if $f$ and $g$ are nonnegative-real-valued functions defined on the natural numbers, then we say $f(n)$ is in $\Omega(g(n))$ if $\liminf_{n \to \infty} \frac{f(n)}{g(n)} > 0$. Similarly, we say $f(n)$ is in $\omega (g(n))$ if $\lim_{n\to\infty} \frac{f(n)}{g(n)} =\infty.$