On subspaces spanned by random selections of +-1 vectors.

Let vectors v sub 1,..., v sub p be chosen at random from the +-1 vectors of length n. The probability that there is at least one +-1 vector in the subspace (over the reals) spanned by v sub 1,..., v sub p that is different from the +- v sub j is shown to be 4(p above 3) (3 over 4) sup n + O((7 over 10) sup n) as n -> inf, for p = n - 10n/(log n), where the constant implied by the O-notation is independent of p. The main term in this estimate is the probability that some three of the v sub j contain another +-1 vector in their linear span. This result answers a question that arose in the work of Kanter and Sompolinsky on associative memories.