MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

2 $m/4$ instead of $m/2$ in one place

I believe (but haven't fully checked) that you can get an upper bound of $m=cn \log^2 n$ using the second moment method. I'm including a sketched argument below.

I will assume WLOG that $m$ is even. I will also (for now) make a parity assumption: I will assume that, modulo $2$, the sum of all $m$ vectors is equal to $(1,0,\dots,0)$.

Consider the $\binom{m}{m/2}$ vectors $$v_A := \sum_{j \in A} v_j - \sum_{j \notin A} v_j,$$ where $A$ is any subset of size $m/2$. For any given $A$, the probability $v_A$ equals $(1,0,\dots 0)$ is $$\frac{\binom{m}{m/2-1}}{2^{m-1}} \left(\frac{\binom{m}{m/2}}{2^{m-1}}\right)^{n-1} = \left(\frac{4}{\pi n}+o(1)\right)^{n/2}$$ by Stirling's approximation (note that I'm dividing by $2^{m-1}$ here due to the parity assumption).

So the expected number of $v_A$ equal to $(1,0,\dots,0)$ is (again using Stirling's approximation) $$\frac{2^m}{\sqrt{\pi m/2}} \left(\frac{2}{\pi n}+o(1)\right)^{n/2},$$ which tends to infinity for $m=c n \log n$ and sufficiently large $c$. We now look at the second moment.

If $|A \cap B|=k$, then for each coordinate (except the first, which is pretty much the same), the event $v_A(t)=v_B(t)=0$ corresponds (after a bit of rearrangement) to the pair of events $$\sum_{j \in A \cap B} v_j (t) = \sum_{j \in A^C \cap B^C} v_j(t)$$ $$\sum_{j \in A \cap B^C} v_j (t) = \sum_{j \in A^C \cap B} v_j(t).$$ So the probability that both occur equals $$\frac{\binom{2k}{k} \binom{m-2k}{m/2-k}}{2^{m-1}}.$$ We therefore have $$\frac{P(v_A=v_B=0)}{P(v_A=0)^2}=\left( 2^{m-1} \frac{\binom{2k}{k} \binom{m-2k}{m/2-k}}{\left(\binom{m}{m/2}\right)^2} \right)^n$$ Applying Stirling/central binomial asmyptotics again, I get that after some more algebra this becomes $$\left(\frac{m/4}{\sqrt{k(m/2-k)}} \left(1+O(\frac{1}{\min(k,m/2-k)})\right)\right)^n.$$

For $|k-m/2|=t\sqrt{m}$, |k-m/4|=t\sqrt{m}$, the first fraction is$1+O\left(\frac{t^2}{m}\right)$so for$t=o(\sqrt{\log n})$we have $$\frac{P(v_A=v_B=0)}{P(v_A=0)^2}= \left(1+O(\frac{t^2}{m})\right)^n = 1+o(1).$$ [The parity assumption is necessary to make this work -- otherwise the fact that$v_A=v_B$modulo$2$increases the probability by a factor of$2$for each coordinate]. I believe (but haven't gone through the full details) that it's similarly possible to bound the tails, so by Chebyshev we will almost surely have$(1,0,0,\dots,0)$by the time we get to$m=c n \log n$, under our parity conditioning. By another second moment calculation, we know that any subset of size$2m$vectors almost surely has a subset of size$m$having the desired sum modulo$2$(the second moment calculation's actually a lot simpler here -- for any$A \neq B$the sums of$A$and$B$are independent!). So by increasing$m$to$2cn \log n$, we can remove the parity conditioning and almost surely have a sum equal to$(1,0,\dots,0)$. Taking$\log n$collections of this size$m$, we can almost surely hit every coordinate vector. Effectively I lost a$\log$in this argument when I only considered the$v_A$instead of more general sums, and another$\log$in the end when I considered$\log n$disjoint collections of vectors instead of allowing the collections to interact with each other. Both may be unncessary. 1 I believe (but haven't fully checked) that you can get an upper bound of$m=cn \log^2 n$using the second moment method. I'm including a sketched argument below. I will assume WLOG that$m$is even. I will also (for now) make a parity assumption: I will assume that, modulo$2$, the sum of all$m$vectors is equal to$(1,0,\dots,0)$. Consider the$\binom{m}{m/2}$vectors $$v_A := \sum_{j \in A} v_j - \sum_{j \notin A} v_j,$$ where$A$is any subset of size$m/2$. For any given$A$, the probability$v_A$equals$(1,0,\dots 0)$is $$\frac{\binom{m}{m/2-1}}{2^{m-1}} \left(\frac{\binom{m}{m/2}}{2^{m-1}}\right)^{n-1} = \left(\frac{4}{\pi n}+o(1)\right)^{n/2}$$ by Stirling's approximation (note that I'm dividing by$2^{m-1}$here due to the parity assumption). So the expected number of$v_A$equal to$(1,0,\dots,0)$is (again using Stirling's approximation) $$\frac{2^m}{\sqrt{\pi m/2}} \left(\frac{2}{\pi n}+o(1)\right)^{n/2},$$ which tends to infinity for$m=c n \log n$and sufficiently large$c$. We now look at the second moment. If$|A \cap B|=k$, then for each coordinate (except the first, which is pretty much the same), the event$v_A(t)=v_B(t)=0$corresponds (after a bit of rearrangement) to the pair of events $$\sum_{j \in A \cap B} v_j (t) = \sum_{j \in A^C \cap B^C} v_j(t)$$ $$\sum_{j \in A \cap B^C} v_j (t) = \sum_{j \in A^C \cap B} v_j(t).$$ So the probability that both occur equals $$\frac{\binom{2k}{k} \binom{m-2k}{m/2-k}}{2^{m-1}}.$$ We therefore have $$\frac{P(v_A=v_B=0)}{P(v_A=0)^2}=\left( 2^{m-1} \frac{\binom{2k}{k} \binom{m-2k}{m/2-k}}{\left(\binom{m}{m/2}\right)^2} \right)^n$$ Applying Stirling/central binomial asmyptotics again, I get that after some more algebra this becomes $$\left(\frac{m/4}{\sqrt{k(m/2-k)}} \left(1+O(\frac{1}{\min(k,m/2-k)})\right)\right)^n.$$ For$|k-m/2|=t\sqrt{m}$, the first fraction is$1+O\left(\frac{t^2}{m}\right)$so for$t=o(\sqrt{\log n})$we have $$\frac{P(v_A=v_B=0)}{P(v_A=0)^2}= \left(1+O(\frac{t^2}{m})\right)^n = 1+o(1).$$ [The parity assumption is necessary to make this work -- otherwise the fact that$v_A=v_B$modulo$2$increases the probability by a factor of$2$for each coordinate]. I believe (but haven't gone through the full details) that it's similarly possible to bound the tails, so by Chebyshev we will almost surely have$(1,0,0,\dots,0)$by the time we get to$m=c n \log n$, under our parity conditioning. By another second moment calculation, we know that any subset of size$2m$vectors almost surely has a subset of size$m$having the desired sum modulo$2$(the second moment calculation's actually a lot simpler here -- for any$A \neq B$the sums of$A$and$B$are independent!). So by increasing$m$to$2cn \log n$, we can remove the parity conditioning and almost surely have a sum equal to$(1,0,\dots,0)$. Taking$\log n$collections of this size$m$, we can almost surely hit every coordinate vector. Effectively I lost a$\log$in this argument when I only considered the$v_A$instead of more general sums, and another$\log$in the end when I considered$\log n\$ disjoint collections of vectors instead of allowing the collections to interact with each other. Both may be unncessary.