.PH ""
.nr Pt 1
.EQ
delim $$
gsize 12
define aA % {bold v sub 1} %
define bB % {bold v sub p} %
define cC % {bold v sub j} %
define dD % {P sub m} %
define eE % {R sub m} %
define fF % {P sub 3} %
define roR % {size 7 bold up 6 | back 13 size 12 roman R} %
.EN
.am DE
.sp
..
.ds HP 12 12 12 12 12 12 12
.ds HF 3 3 3 3 3 3 3
.ls 1
.ce 99
.B
.S 12
On subspaces spanned by random
selections of $fat +-$1 vectors
.R
.sp
.I
A. M. Odlyzko
.R
.sp .2
AT&T Bell Laboratories
Murray Hill, NJ 07974
.sp
.B
ABSTRACT
.R
.ce 0
.sp
.ls 2
.P
Suppose that vectors $aA ^,...,^ bB$ are chosen at random from
the $+-$1 vectors of length $n$.
The probability that these at least are $+-$1 vector in the subspace
(over the ????) spanned by $aA ^,...,^ bB$ that is different from
the $+- ^cC$ is shown to be
.DS 3
.EQ
4 left ( {pile {P above 3}} right ) ~left ( 3 over 4 right ) sup n ~+~
O left ( left ( 7 over 10 right ) sup n right ) ~~roman as~~ n ~->~ inf ^,
.EN
.DE
uniformly for $p ~<=~ n ~-~ 10n / ( log ^n)$.
Moreover, the main term in this estimate is the probability
that some ???? of the $cC$ 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.
.bp
.ls 1
.ce 99
.B
On subspaces spanned by random
selections of $fat +-$1 vectors
.R
.sp
.I
A. M. Odlyzko
.R
.sp .2
AT&T Bell Laboratories
Murray Hill, NJ 07974
.ce 0
.H 1 "Introduction"
.ls 2
The work of Kantor and Sompolinsky [\0] on associative memories gives
rise to the following question.
Let the vectors $aA ^,...,^ bB$ be chosen randomly from among $"{" +- 1 "}" sup n$
(the $+-$1 vectors of length $n$).
What is the probability that the subspace spanned by $aA ^,...,^ bB$ ???
the reals contains a $+-$1 vector different from $+- ^aA ^,...,^ +- ^ bB$?
(The reals can be replaced by any field of characteristic zero,
since the answers are the same.)
Some of the results of [\0] seemed to suggest that if $p ^,^ n ~->~ inf$
while $p/n ~->~ alpha$ for some $alpha , ~0 ~<~ alpha ~<~ 1$, then
this probability might tend to 0 for $alpha ~<~ 1-2 / pi$ and might
tend to 1 for $alpha ~>~ 1-2 / pi$.
.pn 2
.PH "''- \\\\nP -''"
However, G. Kalai and N. Limial conjectured that this is not
the case, and that in fact this probability is dominated by
the probability that some 3 of the $cC$ have a linear combination
that is a $+-$1 vector different from the $cC$.
We will prove this conjecture here.
.sp
.I
Theorem.
If $aA ^,...,^ bB$ are chosen at random from $"{" +- 1 "}" sup n$,
then the probability $P$ that the linear subspace spanned by
$aA ^,...,^ bB$ over the reals contain a $+-$1 vector different
from the $+- ~ cC$ equals
.R
.DS 3
.EQ (1.1)
P ~=~ fF ~+~ O left ( left ( 7 over 10 right ) sup n right ) ~~roman as~~
n ~->~ inf ^,
.EN
.DE
.I
where
.R
.DS 3
.EQ (1.2)
fF ~=~ 4 left ( {pile {P above 3}} right ) ^ left ( 3 over 4 right ) sup n
~+~ O left ( left ( 7 over 10 right ) sup n right ) ~~roman as~~ n ~->~ inf
.EN
.DE
.I
is the probability that some subset of 3 of the $cC$ has a linear
combination in $"{" +- 1 "}" sup n$ that differs from the $+- ~ cC$,
and where the above estimates are uniform for
.R
.DS 3
.EQ (1.3)
p ~<=~ n ~-~ 10 ^n ~( log ^n ) sup -1 ~.
.EN
.DE
.P
In light of the above result, the Kanter-Sompolinsky results of [\0]
have now been taken to suggest a different result.
Let $Q$ be the probability that when $aA ^,...,^ bB$ are chosen
at random from $"{" +- 1 "}" sup n$, and $V$ is the linear space
spanned by the $cC$, then there is a vector $bold w ~epsilon~ "{" +- 1 "}" sup n$
more of whose neighbors (i.e., vectors $bold u ~epsilon~ "{" +- 1 "}" sup n$
that differ from $bold w$ in one coordinate) is in $V$, but such
that $bold w$ is closer to $V$ (in the sense of ordinary Euclidean
distance) than any of its neighbors.
The current conjecture, based on the results of [\0], is that
$Q ~->~ 0$ as $p ^,^ n ~->~ inf$ with $p/n ~->~ alpha$ for
$alpha ~<~ 1- 2/ pi$, and $Q ~->~ 1$ for $alpha ~>~ 1-2 / pi$.
Our method do not shed any light on this conjecture.
.P
The error term $O(( 7/10 ) sup n )$ in our Theorem can be substantially
improved with additional effort.
On the other hand, the limitation $p ~<=~ n ~-~ 10^ n ~( log ^n ) sup -1$
seems hard to improve (except for the value of the constant 10).
When $p ~=~ n$, a result of
Komlo\*'s [\0] implies that the vectors
$aA ^,...,^ bold v sub n$ are linearly independent with probability
$->~ 1$ as $n ~->~ inf$, so that $V ~=~ "{" +- 1 "}" sup n$.
It would be interesting to find out just how large $p$ has to be
so that $P ~->~ 1$, but this problem appears very hard.
.P
The present work is closely related to that of Komlo\*'s.
The distribution of determinants of matrices whose entries
are drawn from some common distribution is only known in a few
special cases [\0], such as when they are all normal.
The problem of determinants of random $+-$1 matrices (or of (0,1)-matrices,
since there is a well-known correspondence between the two problems)
has been of substantial interest for a long time [\0].
Komlo\*'s [\0] was the first one to show that the probability
of a random $n ~times~ n$ $+-$1 matrix being singular $-> ~0$ as
$n ~->~ inf$.
We later [\0] extended this result to the case where the entries
are drawn from any non-degenerate distribution.
Finally, in [\0], he developed a simplified method that enabled
him to show that the probability of a random $n ~times~ n$ $+-$1 matrix
being singular is $O( n sup {-^ 1/2} )$ as $n ~->~ inf$.
(It is conjectured that this probability is $O( n sup 2 ^2 sup -n )$,
so that such matrices are singular primarily when two rows or
columns are equal to each other or the negations of each other.)
Parts of our proof use techniques very similar to those of [\0].
.P
There are many other open problems about 0,1 or $+-$1 random variables.
For example, L. Babai has conjectured that the characteristic polynomials
of adjacency matrices of random undirected graphs (i.e., of random
symmetric (0,1)-matrices with 0's on the diagonal) are irreducible
as the dimension $->~ inf$.
(If true, this would say that testing for graph isomorphism is easy
most of the time.)
This author has also conjectured that polynomials of degree $n$
with coefficients 0,1 and constant term 1 are irreducible with probability
$->~ 1$ as $n ~->~ inf$.
.P
Some additional results on convex combinations of vertices of an $n$-cube
and linear subspaces can be found in [\0].
.H 1 "Proof of Theorem"
Let $dD$ denote the probability that there is a linear combination
of some $m$ out of the $p$ random vectors $aA ^,...,^ bB ~epsilon~ "{" +- 1 "}" sup n$
which is in $"{" +- 1 "}" sup n$, and such that all $m$ coefficients
in this combination are nonnegative.
We will estimate $fF$ and show that $P sub 2 , ~P sub 4 , ~P sub 5 ^,...,^ P sub P$ are negligible.
.P
We start with the bounds for $P sub 5 , ~P sub 6 ^,...^$.
Our basic tool will be the following lemma, which was proved
by Erdo\*:s [\0], but is usually referred to as the Littlewood-Offord
Lemma after the people who first raised the problem and proved
a weaker form of the result [\0].
(The most general result of this type is due to Kleitman [\0].)
.sp
.I
Lemma 2.1.
Suppose that $x sub 1 ^,...,^ x sub m ~epsilon~ roR ~\e~ "{" 0 "}"$,
$y ~epsilon~ roR$.
Then
.R
.DS 3
.EQ (2.1)
left | left { ( epsilon sub 1 ^,...,^ epsilon sub m ): ~epsilon sub i ~=~ +- 1
~{roman {f o r~a l l}}~ i , ~sum from i ~epsilon sub i ^x sub i ~=~ y right }
right | ~<=~ left ( {pile {m above left floor m/2 right floor}} right ) ~.
.EN
.DE
.P
We now use Lemma 2.1 to prove the following result.
.sp
.I
Proposition 2.2.
If
.R
.DS 3
.EQ
5 ~<=~ m ~<=~ p ~<=~ n ~-~ 10 ^n ~( log ^n ) sup -1 ^,
.EN
.DE
then
.DS 3
.EQ (2.2)
dD ~<=~ ( 0.69 ) sup n ~~roman as~~ n ~->~ inf
.EN
.DE
for $n$ sufficiently large.
.sp
\f2Proof of Proposition 2.2\f1.
We clearly have
.DS 3
.EQ (2.3)
dD ~<=~ left ( {pile {P above m}} right ) ~eE ^,
.EN
.DE
where $eE$ is the probability that a random $m ~times~ n ~+- 1$ matrix
$M$ will have some combination of its $m$ rows with all coefficients
$!=~ 0$ in $"{" +- 1 "}" sup n$.
Denote the rows of $M$ by $bold w sub 1 ^,...,^ bold w sub m$.
Suppose that $0 ~<~ q ~<~ n-m$, and assume that the first $m ^+^ q$ columns
of $M$ have ????? $m$.
If columns $j sub 1 ^<...<^ j sub m ~<=~ m ^+^ q$ of $M$ are
linearly independent, then for each choice of $alpha sub 1 ^,...,^ alpha sub m ~epsilon~ "{" +- 1 "}"$,
there will be a unique set of coefficients $x sub 1 ^,...,^ x sub m$ with
the $j sub g$-th coordinate of $x sub 1 ^ bold w sub 1 ^+...+^ x sub m ^bold w sub m$
equal to $alpha sub g$.
Thus there will be at most $2 sup m$ sets $x sub 1 ^,...,^ x sub m ~epsilon~ roR ~\e~ "{" 0 "}"$
with the property that the first $m ^+^ q$ coordinates of
$x sub 1 ^bold w sub 1 ^+...+^ x sub m ^bold w sub m$ are all $+-$1.
Consider now a fixed choice of $x sub 1 ^,...,^ x sub m$.
The probability that the $j$-th coordinate of
$x sub 1 ^bold w sub 1 ^+...+^ x sub m ^bold w sub m$ equals 1 for
$m ^+^ q ~<~ j ~<=~ n$, as the $j$-th column of $M$ varies, is
.DS 3
.EQ
2 sup -m ^ left ( {pile {m above left floor m/2 right floor}} right )
.EN
.DE
by the Littlewood-Offord lemma, and similarly for the probability that
this coordinate equals -1.
Since columns $j$, $m ^+^ q ~<~ j ~<=~ n$, are independent of each
other, we obtain
.DS 3
.EQ (2.4)
eE ~<=~ 2 sup m ^left ( {pile {m ^+^ q above q}} right ) ~left [ 2 sup -m
~left ( {pile {m above left floor m/2 right floor}} right ) right ] sup {n ^-^ m ^-^ q}
~+~ Q sub {m ^,^ q} ^,
.EN
.DE
where $Q sub {m ^,^ q}$ is the probability that a random
$m ~times~ ( m ^+^ q) ~+- 1$ matrix has rank $<~ m$.
.P
We next bound $Q sub {m ^,^ q}$.
We have
.DS 3
.EQ (2.5)
Q sub {m ^,^ q} ~<=~ sum from k=1 to m-1 ~( m-k ) ^left ( {pile {m above k}} right )
^ left ( {pile {m ^+^ q above k}} right ) ~Q sub {m,^q,^k} ^,
.EN
.DE
where $Q sub {m,^q,^k}$ is the probability that a random $m ~times~ (m ^+^ q) ~+- 1$
matrix will have the property that every $k$ of its rows are
linearly independent, the upper left $k ~times~ k$ submatrix has
rank $k$, and the $(k+1)$-st row is linearly dependent on the first
$k$ rows.
Given a matrix satisfying the above properties, the rows
$bold u sub 1 ^,...,^ bold u sub k+1$ of the upper left $(k+1) ~times~ k$
submatrix determine unique nonzero coefficients $x sub 1 ^,...,^ x sub k+1$
such that $sum from i=1 to k+1 ~x sub i ^bold u sub i ~=~ ( 0 ^,...,^ 0 )$.
Given $x sub 1 ^,...,^ x sub k+1$, the probability that this same
relation will also hold in columns $k+1 ^,...,^ m ^+^ q$ is
.DS 3
.EQ (2.6)
<= ~ left [ 2 sup {-^ k-1} ~left ( {pile {k+1 above left floor (k+1) /2 right floor}} right ) right ] sup {m ^+^ q ^-^ k} ^,
.EN
.DE
and so this is a bound for $Q sub {m,^q,^k}$.
Therefore, combining (2.5) and (2.6), we obtain
.DS 3
.EQ
Q sub {m ^,^ q} ~<=~ m ~sum from k=1 to m-1 ~left ( {pile {m above k}} right )
^left ( {pile {m ^+^ q above k}} right ) ~left [ 2 sup {-^ k-1} ~left (
{pile {k+1 above left floor (k+1)/2 right floor}} right ) right ] sup {m ^+^ q ^-^ k} ^,
.EN
.DE
and so, by (2.3) and (2.4),
.DS 3
.EQ
dD ~mark <=~ 2 sup m ^left ( {pile {P above m}} right ) ^left ( {pile {m ^+^ q above q}} right )
~left [ 2 sup -m ~left ( {pile {m above left floor m/2 right floor}} right )
right ] sup {n ^-^ m ^-^ q}
.EN
.sp
.EQ (2.7)
~~~~
.EN
.sp
.EQ
~lineup +~ m ^left ( {pile {P above m}} right ) ~sum from k=1 to m-1 ~left ( {pile {m above k}} right )
^left ( {pile {m ^+^ q above k}} right ) ~left [ 2 sup {-^ k-1} ^left (
{pile {k+1 above left floor (k+1)/2 right floor}} right ) right ] sup {m ^+^ q ^-^ k} ~.
.EN
.DE
For $5 ~<=~ m ~<=~ n/1000$, we select
.DS 3
.EQ
q ~=~ left floor 65n over 100 right floor ~.
.EN
.DE
We find that
.DS 3
.EQ
2 sup m ^left ( {pile {P above m}} right ) ^left ( {pile {m ^+^ q above q}} right )
~<=~ 2 sup m ^left ( {pile {n above m}} right ) sup 2 ~<=~ 2 sup 3n/1000 ^,
.EN
.sp
.EQ
left [ 2 sup -m ^left ( {pile {m above left floor m/2 right floor}} right )
right ] sup {n ^-^ m ^-^ q} ~<=~ left ( 5 over 16 right ) sup 0.348n ^,
.EN
.sp
.EQ
left ( {pile {P above m}} right ) ^left ( {pile {m above k}} right ) ^
left ( {pile {m ^+^ q above k}} right ) ~<=~ 2 sup m ^left ( {pile {P above m}} right )
^left ( {pile {m ^+^ q above m}} right ) ~<=~ 2 sup 3n/1000 ^,
.EN
.DE
and for $1 ~<=~ k ~<=~ m-1$,
.DS 3
.EQ
left [ 2 sup {-^ k-1} ^left ( {pile {k+1 above left floor (k+1)/2 right floor}} right )
right ] sup {m ^+^ q ^-^k} ~<=~ 2 sup -q ^,
.EN
.DE
so that in this range
.DS 3
.EQ (2.8)
dD ~<=~ O ( 0.67 sup n ) ~~roman as~~ n ~->~ inf ~.
.EN
.DE
.P
We next consider $n/1000 ~<~ m ~<=~ p ~<~ n$.
This time we use the inequality
.DS 3
.EQ (2.9)
dD ~<=~ left ( {pile {P above m}} right ) ~{eE} prime ~+~ Q sub {p ^,^ q} ^,
.EN
.DE
where ${eE} prime$ is the probability that a random $m ~times~ n$ $+-$1
matrix has some nonzero combination of its rows in $"{" +- 1 "}" sup n$,
and that its first $p ^+^ q$ columns have rank $m$.
Then, by the previous argument,
.DS 3
.EQ
{eE} prime ~mark <=~ 2 sup {p ^+^ q} ~left ( {pile {p ^+^ q above m}} right )
~left [ 2 sup -m ^left ( {pile {m above left floor m/2 right floor}} right )
right ] sup {n ^-^ p ^-^ q}
.EN
.sp
.EQ (2.10)
~lineup <=~ 2 sup 2n ~left [ 2 sup -m ^left ( {pile {m above left floor m/2 right floor}} right )
right ] sup {n ^-^ p ^-^ q} ~<=~ 2 sup 2n ^left [ 8 n sup {-^ 1/2} right ] sup {n ^-^ p ^-^ q}
.EN
.DE
for large enough $n$.
On the other hand,
.DS 3
.EQ
Q sub {p ^,^ q} ~<=~ n ~sum from k=1 to p-1 ~left ( {pile {P above k}} right )
^left ( {pile {p ^+^ q above k}} right ) ~left [ 2 sup {-^ k-1} ~
left ( {pile {k+1 above left floor (k+1)/2 right floor}} right ) right ] sup {p ^+^ q ^-^k} ~.
.EN
.DE
Now for large $n$,
.DS 3
.EQ
mark sum from {k ^=^ left floor n sup 1/2 right floor ^+^1} to p-1 ~
left ( {pile {P above k}} right ) ^left ( {pile {p ^+^ q above k}} right )
~left [ 2 sup {-^ k-1} ^left ( {pile {k+1 above left floor (k+1)/2 right floor}} right ) right ] sup {p ^+^ q ^-^k}
.EN
.sp
.EQ
lineup <= ~n ^2 sup 2n ~n sup {-^ (p ^+^ q ^-^ k)4} ~<=~ n^ 2 sup 2n ^n sup {-^ n/10000}
~<=~ 2 sup -n ~.
.EN
.DE
At the same time, for some positive constant $C$,
.DS 3
.EQ
mark sum from k=1 to {left floor n sup 1/2 right floor} ~left ( {pile {P above k}} right )
^left ( {pile {p ^+^ q above k}} right ) ~left [ 2 sup {-^ k-1} ~
left ( {pile {k+1 above left floor (k+1)/2 right floor}} right ) right ] sup {p ^+^ q ^-^k}
.EN
.sp
.EQ
lineup <= ~sum from k=1 to {left floor n sup 1/2 right floor} ~{n sup 2k}
over {(k!) sup 2} ~left [ 2 sup {-^ k-1} ^left ( {pile {k+1 above left floor (k+1)/2 right floor}} right )
right ] sup {p ^+^ q ^-^ n sup 1/2}
.EN
.sp
.EQ
lineup <= ~e sup {C ^n sup 1/2 ^ log ^n} ~sum from k=1 to {left floor n sup 1/2 right floor}
~left [ 2 sup {-^ k-1} ^left ( {pile {k+1 above left floor (k+1)/2 right floor}} right )
right ] sup {p ^+^ q}
.EN
.sp
.EQ
lineup <= ~n sup 1/2 ~e sup {C ^n sup 1/2 ^ log ^n} ~2 sup {-^ p-q} ~.
.EN
.DE
Combining all these estimates we obtain
.DS 3
.EQ
dD ~mark <=~ left ( {pile {P above m}} right ) ^2 sup 2n ^left [ 8 n sup {-^ 1/2}
right ] sup {n ^-^ p ^-^ q} ~+~ 2 sup -n ~+~ e sup {n sup 2/3} ~
2 sup {-^ p-q}
.EN
.sp
.EQ (2.11)
~lineup <=~ 2 sup 3n ^left [ 8 n sup {-^ 1/2} right ] sup {n ^-^ p ^-^ q}
~+~ e sup {n sup 2/3} ~2 sup {1 ^-^ p ^-^ q} ^,
.EN
.DE
valid for sufficiently large $n$ and $n/1000 ~<~ m ~<=~ p ~<~ n$.
We now select $q$ so that
.DS 3
.EQ
n ^-^ p ^-^ q ~=~ left floor {7n ^ log ^2} over {log ^n} right floor ^,
.EN
.DE
and obtain the claim of Proposition 2.2.\0\0$blot$
.P
We now proceed to consider $P sub 2 , ~P sub 3$, and $P sub 4$.
If $bold v , ^bold w ~epsilon~ "{" +- 1 "}" sup n$, then
the only way to have $alpha bold v ~+~ beta bold w ~epsilon~ "{" +- 1 "}" sup n$
for $alpha beta ~!=~ 0$ is if $bold v ~=~ +-^ bold w$, to an
even that has probability $2 sup 1-n$.
Therefore
.DS 3
.EQ (2.12)
P sub 2 ~=~ O left ( n sup 2 ^2 sup -n right ) ~~roman as~~ n ~->~ inf ~.
.EN
.DE
.I
Proposition 2.3.
We have, for $3 ~<=~ p ~<=~ n$,
.R
.DS 3
.EQ (2.13)
fF ~=~ 4 ^ left ( {pile {P above 3}} right ) ^left ( 3 over 4 right ) sup n
~+~ O left ( {pile {4 above P}} ^left ( 5 over 8 right ) sup n right )
~~roman as~~ n ~->~ inf ~.
.EN
.DE
\f2Proof\f1.
By (2.3), $fF ~<=~ left ( {pile {P above 3}} right ) ~R sub 3$.
Since multiplying any collection of rows or columns of a $+-$1 matrix
by $+-$1's does not change the property that some $+-$1 vector
is in the span of rows of the matrix, we have
.DS 3
.EQ (2.14)
R sub 3 ~=~ 2 sup {2 ^-^ 2n} ~N ^,
.EN
.DE
where $N$ is the number of $3 ~times~ n ~+- 1$ matrices
$M$ with rows $aA ^,...,^ bold v sub 3$ for which $aA ~=~ (1,1 ^,...,^ 1)$,
the first column equals $(1,1,1 ) sup T$, and such that for some
$alpha , ^ beta , ^gamma$ with $alpha beta gamma ~!=~ 0$, we have
$alpha aA ~+~ beta bold v sub 2 ~+~ gamma bold v sub 3 ~epsilon~ "{" +- 1 "}" sup n$.
We will estimate the number of such matrices $M$.
.P
Let $bold v sub m ~=~ ( v sub m1 ^,...,^ v sub mn )$, and suppose
that $alpha v sub 11 ~+~ beta v sub 21 ~+~ gamma v sub 31 ~=~ u$.
If $M$ contains a column of the form $(1, ^-1, ^-1 ) sup T$ or
$(1,^1,^-1 ) sup T$, say in the $r$-th position, and
$alpha v sub 1r ~+~ beta v sub 2r ~+~ gamma v sub 3r ~=~ X$,
then $x ~=~ -u$, since if $x ~=~ u$, subtracting this equation
from $alpha v sub 11 ~+~ beta v sub 21 ~+~ gamma v sub 31 ~=~ u$
would give $beta ~=~ 0$ or $gamma ~=~ 0$, which is impossible.
Similarly, if $M$ contains the column $(1, ^-1, ^-1 ) sup T$, say
in the $r$-th position, and another column, say the $g$-th one,
equals $(1,^-1,^1 ) sup T$ or $(1, ^1,^-1 ) sup T$, then
$alpha v sub 1r ~+~ beta v sub 2r ~+~ gamma v sub 3r ~=~ u$.
Therefore we cannot have all 4 possible columns appearing in $M$,
since then we would have the 4 equations
.DS 3
.EQ
alpha v sub 11 ~mark +~ beta v sub 21 ~+~ gamma v sub 31 ~=~ u ^,
.EN
.sp
.EQ
alpha v sub 1r ~lineup +~ beta v sub 2r ~-~ gamma v sub 3r ~=~ -u ^,
.EN
.sp
.EQ
alpha v sub 1s ~lineup -~ beta v sub 2s ~+~ gamma v sub 3s ~=~ -u ^,
.EN
.sp
.EQ
alpha v sub 1t ~lineup -~ beta v sub 2t ~-~ gamma v sub 3t ~=~ u ^,
.EN
.DE
and adding them shows that $alpha ~=~ 0$, which is a contradiction.
On the other hand, for any selection of 3 out of the 4 possible
columns of $M$ (always including the first column $(1,^1,^1 ) sup T$),
the matrices consisting of precisely those columns, will have
the required property, since we will obtain a nonsingular system of 3
equations in 3 unknowns.
For any particular choice of 3 columns to appear in $M$,
we will have $3 sup n-1$ choices of $M$.
There are 3 possible choices of 3 out of 4 columns (since $(1,^1,^1 ) sup T$
always has to be included).
If only 2 different columns appear in $M$, then some two of
$aA , ~bold v sub 2$, and $bold v sub 3$ an equal, and there are
$O( 2 sup n )$ such matrices $M$.
Hence we conclude that
.DS 3
.EQ (2.15)
N ~=~ 3 sup n ~+~ O( 2 sup n ) ^,
.EN
.DE
and so
.DS 3
.EQ (2.16)
R sub 3 ~=~ 4( 3/4 ) sup n ~+~ O ( 2 sup -n ) ~.
.EN
.DE
.P
By the analysis above,
.DS 3
.EQ (2.17)
fF ~<=~ 4 ^ left ( {pile {P above 3}} right ) ^left ( 3 over 4 right ) sup n
~+~ O left ( P sup 3 ^2 sup -n right ) ~.
.EN
.DE
To get a lower bound for $fF$, consider the probability that 2 sets
of 3 vectors each, $bold v sub {i sub 1} , ~bold v sub {i sub 2} , ~bold v sub {i sub 3}$
and $bold v sub {j sub 1} , ~bold v sub {j sub 2} , ~bold v sub {j sub 3}$
simultaneously have linear combinations with nonzero coefficients
that are in $"{" +- 1 "}" sup n$.
If $I ~=~ "{" i sub 1 , ~i sub 2 , ~i sub 3 "}" ~cap~ "{" j sub 1 , ~j sub 2 , ~j sub 3 "}"$
is empty or has exactly one element, this probability is $R sub 3 sup 2$.
If $I$ contains 2 elements, then this probability is $2 sup {3 ^-^ 3n}$
times $N sub 2$, the number of $4 ~times~ n ~+- 1$ matrices with the first
row and column 1 and with the property that the submatrices formed
by deleting the third or the fourth row have at most 3 distinct
columns.
If we let $k$ denote the number of 1's, in the second now, we obtain
.DS 3
.EQ
<=~ 2 sup {max (k,^n-k) ^+^ 1}
.EN
.DE
choices for each of the third and fourth rows, so
.DS 3
.EQ
N sub 2 ~mark <=~ 4 ~sum from k=1 to n ~left ( {pile {n above k}} right )
~4 sup {max (k,^n-k)}
.EN
.sp
.EQ (2.18)
~lineup <=~ 8~ sum from k=0 to n ~left ( {pile {n above k}} right ) ~4 sup k
~=~ 8 ~cdot~ 5 sup n ~.
.EN
.DE
Therefore the probability of finding 2 sets of 3 vectors, each of
which gives the desired combination, is $O ( P sup 4 ^( 5/8 ) sup n )$,
and therefore we obtain the estimate (2.13) of Proposition 2.3.\0\0$blot$
.sp
.I
Proposition 2.4.
If $4 ~<=~ p ~<=~ n$, then
.R
.DS 3
.EQ (2.19)
P sub 4 ~=~ O left ( P sup 4 ^left ( 5 over 8 right ) sup n right ) ~~roman as~~
n ~->~ inf ~.
.EN
.DE
\f2Sketch of proof\f1.
The proof of this result uses the same ideas as that of Proposition 2.3,
but is considerably easier, since only a weak upper bound is required.
We reduce the problem of bounding $P sub 4$ to that of counting
the number of $4 ~times~ n ~+- 1$ matrices $M$ with rows
$aA ^,...,^ bold v sub 4$ such that $aA ~=~ (1,1 ^,...,^ 1)$,
the first column of $mu$ is $(1,^1,^1,^1 ) sup T$, and for some
nonzero $alpha , ^beta , ^gamma ,^delta$,
$alpha aA ~+~ beta bold v sub 2 ~+~ gamma bold v sub 3 ~+~ delta bold v sub 4 ~epsilon~ "{" +- 1 "}" sup n$.
A short argument then shows that such a matrix cannot have
more than 5 distinct columns, which then immediately yields (2.19).
(A more careful argument shows that such a matrix cannot have more
than 4 distinct columns, which then gives $P sub 4 ~=~ O( P sup 4 ^2 sup -n )$.)\0\0$blot$
.P
The Theorem easily follows from all the estimates that have been
obtained.
.HU "Acknowledgements"
The author thanks H. Sompolinsky for informing him of the
problem and helpful conversations.
.bp
.ce
.B
References
.R
.sp
.AL
.LI
T. W. Anderson, \f2Introduction to Multivariate Statistical Analysis\f1,
Wiley, 1958.
.LI
P. Erdo\*:s, On a lemma of Littlewood and Offord, Bull. Am. Math. Soc. \f25\f1
(1945), 898-902.
.LI
G. E. Forsythe and J. W. Tukey, The extent of $n$ random unit
vectors, (Abstract),
\f2Bull. Am. Math. Soc.\f1 \f258\f1 (1952), 502.
.LI
Z. Fu\*:redi, Random polytopes in the $d$-dimensional
cube, \f2Discr. Comp. Geometry\f1, to appear.
.LI
I. Kanter and H. Sompolinsky, Associative recall of memory without
errors, to appear.
.LI
D. J. Kleitman, On a lemma of Littlewood and Offord on the distribution
of linear combinations of vectors, \f2Advances Math. 5\f1 (1970), 155-157.
.LI
J. Komlo\*'s, On the determinant of (0,1) matrices,
\f2Studia Sci. Math. Hungar. 2\f1 (1967), 7-21.
.LI
J. Komlo\*'s, On the determinant of random matrices,
\f2Studia Sci. Math. Hungar. 3\f1 (1968), 387-399.
.LI
J. Komlo\*'s, unpublished manuscript (1977).
.LI
J. E. Littlewood and C. Offord, On the number of real roots of a random
algebraic equation. III. \f2Mat. Sbornik 12\f1 (1943), 277-286.
.LI
N. Metropolis, Spectra of determinant values in (0,1) matrices,
pp. 271-276 in \f2Computers in Number Theory\f1, A. O. L. Atkin
and B. J. Birch, eds., Academic Press, 1971.
.LI
H. Nyquist, S. O. Rice, and J. Riordan, The distribution of
random determinants, \f2Quart. Appl. Math. 12\f1 (1954), 97-104.
.LI
A. M. Odlyzko, On the ranks of some (0,1)-matrices with constant
row sums, \f2J. Australian Math. Soc. A 31\f1 (1981), 193-201.
.LI
A. Pre\*'kopa, On random determinants I,
\f2Studia Sci. Math. Hungar. 2\f1 (1967), 125-132.
.LI
G. Szekeres and P. Turan, On an extremal problem in the theory of
determinants, \f2Math. Naturwiss. Anz. Ungar. Akad. Wiss. 56\f1
(1937), 796-806 (in Hungarian).
.LI
P. Turan, On a problem in the theory of determinants,
\f2Acta Math. Sinica 5\f1 (1955), 411-423 (in Chinese).
.LE