Skip to main content
2 of 2
$m/4$ instead of $m/2$ in one place
Kevin P. Costello
  • 5.8k
  • 2
  • 30
  • 37

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/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.

Kevin P. Costello
  • 5.8k
  • 2
  • 30
  • 37