On subspaces spanned by random selections of \(\pm 1\) vectors (Q1115445)

How many sets of r vectors in n-dimensional space, all components of which are \(\pm 1\), have a \(\pm\) component vector, not \(\pm\) one of the original r, in the subspace they span? This is easy to compute for \(r=3\). One can then find a lower bound in general allowing 3 vectors at a time to have such a 4th vector. It is here shown that this bound is asymptotic to the entire number. Is is thus relatively rare for \(3+j\) vectors to have a \((4+j)th\) such vector in their span for \(j>0\) if no 3 have a 4th in their span. This result is obtained by using the `Littlewood-Offord lemma' and careful argument. It verifies a conjecture of Kalai and Linial and relates to work of \textit{Kanter} and \textit{Sompolinsky} [Phys. Rev. A(3) 35, 380-392 (1987)].