Maximal set of $n$-bit strings that does not span $\mathbb{R}^n$

Question

I am trying to find out the maximum-sized subset $S\subseteq \{0,1\}^n$ of $n$-bit strings that does not span $\mathbb{R}^n$.

It is easy to show that $S$ has size at least $2^{n-1}$ when $S$ exactly consists of $0\cdot \{0,1\}^{n-1}$, the strings that start with a 0. Adding any one more string to this set will include a basis.

My question is whether this is the best what we can do or a larger-sized subset is possible. My guess will be that we can go up to $2^{n-1}+\mathrm{poly}(n)$ but I am unable to prove it as of now. Any pointers or ideas will be appreciated.

Answer 1

If $S$ contains more than $2^{n-1}$ strings, then by pigeonhole principle for every $j=1,2,\ldots, n$ it contains two strings which differ only at $j$-th coordinate. The difference of these two strings is the $j$-th standard basic vector. They do span $\mathbb{R}^n$.

Answer 2

Assume that $S$ does not span $\mathbb{R}^n$. As $S$ is a subset of $\mathbb{Q}^n$, it does not span $\mathbb{Q}^n$ over $\mathbb{Q}$, hence there is a primitive vector $\mathbb{v}\in\mathbb{Z}^n$ orthogonal to $S$. Reducing $S$ modulo $2$ yields a subset $T$ of $\mathbb{F}_2^n$ which is orthogonal to the nonzero vector $\mathbb{v}\bmod 2$ in $\mathbb{F}_2^n$. Hence $T$ spans a proper subspace of $\mathbb{F}_2^n$. In particular, $|S|=|T|\leq 2^{n-1}$.

Answer 3

We can prove this by induction. Suppose that $A\subseteq\{0,1\}^n$ and $|A|>2^{n-1}$. Let $\pi:\mathbb{R}^n\rightarrow\mathbb{R}^{n-1}$ be the projection where we drop the final coordinate. Then $|\pi[A]|>2^{n-2}$. Therefore, $\pi[A]$ spans all of $\mathbb{R}^{n-1}$. Suppose now that $A$ spans the subspace $V$ of $\mathbb{R}^n$. If $A$ has dimension $n$, then the proof is complete. If $A$ has dimension $n-1$, then there is some $\phi:\mathbb{R}^{n-1}\rightarrow\mathbb{R}$ with $V=\{(\mathbf{x},\phi(\mathbf{x})):\mathbf{x}\in\mathbb{R}^{n-1}\}$. However, if $a\in A$, then $\phi\circ\pi(a)=a$ which means that the restriction $\pi|_A$ is injective. This means that $|A|\leq 2^{n-1}$ which is a contradiction.