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, \ldots , v_p,$ $p\leq n-1,$ be chosen at random uniformly and independently from $\{ \pm 1\}^n \subset { \bf R}^n.$ 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{ p \choose 3}\left(\frac{ 3}{ 4}\right)^n + O\left(\left(\frac{ 5}{ 8} + o_n(1)\right)^n\right) \quad \mbox{ as} \quad n\to \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, \ldots , 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}. $
Categories: math.CO cs.DM math.AT math.PR