On linear-combinatorial problems associated with subspaces spanned by $\{\pm 1\}$-vectors

A complete answer to the question about subspaces generated by $\{\pm 1\}$-vectors, which arose in the work of I.Kanter and H.Sompolinsky on associative memories, is given. More precisely, let vectors $v_1,\dots ,v_p,$ $p\le n-1,$ be chosen at random uniformly and independently from $\{\pm 1{\}}^n\subset {\mathbf{R}}^n\mathrm{.}$ Then the probability $\mathbb{P}(p,n)$ that span \ \langle v_1, \ldots , v_p \rangle \cap \left\{ \{\pm 1\}^n \setminus \{\pm v_1, \ldots , \pm v_p\}\right\} \ne \emptyset \ is shown to be $$4\left(\genfrac{}{}{0px}{}{p}{3}\right){\left(\frac{3}{4}\right)}^n+O\left({(\frac{5}{8}+o_n(1))}^n\right)asn\to \mathrm{\infty },$$ where the constant implied by the $O$-notation does not depend on $p$. The main term in this estimate is the probability that some 3 vectors $v_{j_1},v_{j_2},v_{j_3}$ of $v_j$, $j=1,\dots ,p,$ have a linear combination that is a $\{\pm 1\}$-vector different from $\pm v_{j_1},\pm v_{j_2},\pm v_{j_3}\mathrm{.}$