2 added 2 characters in body

I believe it is possible to use some recent closely related work of Kenneth Maples to get a much better (but probably still not quite tight) bound. Let $C>0$ be a constant to be chosen later. Call an $n \times n$ matrix $A$ good if it satisfies each of the following properties

P1. $A$ is non-singular over $\mathbb{R}$.

P2. $|det(A)|$ has at most $C \log n$ prime factors.

P3. $A$ has rank at least $n-C \log n$ over ${\mathbb F}_p$ for every prime $p$.

Here are two claims which together would imply $n+O(\log n)$ vectors are enough.

Claim 1: A random $n \times n$ $(0,1)$ matrix is good with probability $O\left(C^{-1}\right)$.1-O\left(C^{-1}\right)$. Claim 2: If$A$is any fixed good matrix, augmenting$A$by$5C \log n$random rows with high probability leads to a matrix whose rows span${\mathbb Z}^n$. We first look at claim 1. The probability P1 fails is exponentially small in$n$(as originally shown by Kahn, Komlos, and Szemeredi). For P2 and P3, we use the following result of Maples (Corollary 1.3 here): For any prime$p$, the probability that a random$n \times n$matrix has rank$n-k$over${\mathbb F}_p$is $$p^{-k^2} \frac{\prod_{\ell=k+1}^{\infty} \left(1-p^{-\ell}\right)}{\prod_{\ell=1}^k \left(1-p^{-\ell}\right)}+O\left(e^{-cn/2}\right),$$ where both$c$and the constant implicit in$O()$are independent of$p$. We can actually bound the probability above by$O\left(p^{-k^2} +e^{-cn/2}\right)$, since the ratio of products is at most$\prod_{\ell=1}^{\infty} (1-2^{-\ell})^{-1}$. Summing over all$k$, the probability$A$is singular over${\mathbb F}_p$is$O\left(\frac{1}{p} + e^{-\frac{cn}{2}}\right)$. Summing over all$p$, the expected number of primes less than$e^{cn/4}$dividing$|det(A)|$is at most$\log n +O(1)$. There can be at most$2 \log n/c$prime factors of$|det(A)|$larger than$e^{cn/4}$, since otherwise$|det(A)|$would be larger than$n^{n/2}$and violate Hadamard's bound. So the total expected number of factors is$O(\log n)$, and the probability P2 fails is$O(1/C)$by Markov's inequality. For P3, we again split into small and large primes. Applying Maples' theorem again, the probability P3 fails for a given prime less than$e^{cn/4}$is at most$O\left(p^{-C^2 \log^2 n}+ e^{-cn/2}\right)$, and by the union bound the probability P3 fails for some small prime is small. For large primes, we use the observation that$A$can only have rank less than$n-k$over${\mathbb F}_p$if$p^k$divides the determinant of$A$(e.g. because in this case we can row reduce over the integers so$k$rows have all entries divisible by$p$, at which point we can pull a factor of$p$out for each row). In particular, if$C$is sufficiently large we know from Hadamard's bound it is impossible for P1 to succeed and P3 to fail for some prime larger than$e^{cn/4}$. This finishes Claim 1. We now turn to Claim 2. We first note that the for$m \geq n$the vectors$v_1, \dots, v_m$span${\mathbb Z}^n$if and only if the matrix with the$v_i$as rows has full rank over${\mathbb F}_p$for every prime$p$(if the volume of a cell is$V$, then$V$divides the determinant of every$n \times n$submatrix). Since$A$is good, we know that we already are full rank for all but at most$C \log n$primes. So it is enough to show the augmentation with high probability fixes each of those primes. Fix any one such prime$p$. We use the following observation (originally due to Odlyzko): Any proper subspace of${\mathbb F}_p^n$contains at most half of the$(0,1)$vectors (e.g. because if you fix a column basis, whichever column is not in the basis is determined by the remaining$n-1$columns). It follows that so long as$v_1, \dots ,v_j$do not already span the space, $$P\left(v_{j+1} \notin Span(v_1, \dots v_j) \right) \geq \frac{1}{2}.$$ By assumption P3,$A$already had rank at least$n-C \log n$before we added the rows. The only way$A$can fail to be full rank after the augmentation is if the above event occurred at least$4 C \log n$times, an event which occurs with probability at most $$\binom{5C \log n}{4 C \log n} 2^{-4C \log n} = 2^{(-0.39+o(1)) C \log n}.$$ Taking the union bound over all$p$which divide$|det(A)|$, the probability we fail to be of full rank modulo some prime is at most$C \log n 2^{-(0.39+o(1)) C \log n} = Cn^{-0.39C+o(1)}$, proving Claim 2. This bound is probably still not quite tight, especially in the handling of P3 for large$p$. One annoyance in trying to drop below$\log n$is that if the last row of$A$and all the rows added in the augmentation are zero (an event occurring with probability roughly$2^{-n(m-n)}$), the matrix fails to be of full rank modulo every prime. This means just taking the union bound over all the roughly$2^{c n \log n}$primes less than$n^{n/2}$won't be enough if$m-n$is much smaller than$\log n$, unless we could possibly get some handle on the event "$A$is of full rank over$\mathbb{R}$but not over${\mathbb F}_p$" for large$p$. 1 I believe it is possible to use some recent closely related work of Kenneth Maples to get a much better (but probably still not quite tight) bound. Let$C>0$be a constant to be chosen later. Call an$n \times n$matrix$A$good if it satisfies each of the following properties P1.$A$is non-singular over$\mathbb{R}$. P2.$|det(A)|$has at most$C \log n$prime factors. P3.$A$has rank at least$n-C \log n$over${\mathbb F}_p$for every prime$p$. Here are two claims which together would imply$n+O(\log n)$vectors are enough. Claim 1: A random$n \times n(0,1)$matrix is good with probability$O\left(C^{-1}\right)$. Claim 2: If$A$is any fixed good matrix, augmenting$A$by$5C \log n$random rows with high probability leads to a matrix whose rows span${\mathbb Z}^n$. We first look at claim 1. The probability P1 fails is exponentially small in$n$(as originally shown by Kahn, Komlos, and Szemeredi). For P2 and P3, we use the following result of Maples (Corollary 1.3 here): For any prime$p$, the probability that a random$n \times n$matrix has rank$n-k$over${\mathbb F}_p$is $$p^{-k^2} \frac{\prod_{\ell=k+1}^{\infty} \left(1-p^{-\ell}\right)}{\prod_{\ell=1}^k \left(1-p^{-\ell}\right)}+O\left(e^{-cn/2}\right),$$ where both$c$and the constant implicit in$O()$are independent of$p$. We can actually bound the probability above by$O\left(p^{-k^2} +e^{-cn/2}\right)$, since the ratio of products is at most$\prod_{\ell=1}^{\infty} (1-2^{-\ell})^{-1}$. Summing over all$k$, the probability$A$is singular over${\mathbb F}_p$is$O\left(\frac{1}{p} + e^{-\frac{cn}{2}}\right)$. Summing over all$p$, the expected number of primes less than$e^{cn/4}$dividing$|det(A)|$is at most$\log n +O(1)$. There can be at most$2 \log n/c$prime factors of$|det(A)|$larger than$e^{cn/4}$, since otherwise$|det(A)|$would be larger than$n^{n/2}$and violate Hadamard's bound. So the total expected number of factors is$O(\log n)$, and the probability P2 fails is$O(1/C)$by Markov's inequality. For P3, we again split into small and large primes. Applying Maples' theorem again, the probability P3 fails for a given prime less than$e^{cn/4}$is at most$O\left(p^{-C^2 \log^2 n}+ e^{-cn/2}\right)$, and by the union bound the probability P3 fails for some small prime is small. For large primes, we use the observation that$A$can only have rank less than$n-k$over${\mathbb F}_p$if$p^k$divides the determinant of$A$(e.g. because in this case we can row reduce over the integers so$k$rows have all entries divisible by$p$, at which point we can pull a factor of$p$out for each row). In particular, if$C$is sufficiently large we know from Hadamard's bound it is impossible for P1 to succeed and P3 to fail for some prime larger than$e^{cn/4}$. This finishes Claim 1. We now turn to Claim 2. We first note that the for$m \geq n$the vectors$v_1, \dots, v_m$span${\mathbb Z}^n$if and only if the matrix with the$v_i$as rows has full rank over${\mathbb F}_p$for every prime$p$(if the volume of a cell is$V$, then$V$divides the determinant of every$n \times n$submatrix). Since$A$is good, we know that we already are full rank for all but at most$C \log n$primes. So it is enough to show the augmentation with high probability fixes each of those primes. Fix any one such prime$p$. We use the following observation (originally due to Odlyzko): Any proper subspace of${\mathbb F}_p^n$contains at most half of the$(0,1)$vectors (e.g. because if you fix a column basis, whichever column is not in the basis is determined by the remaining$n-1$columns). It follows that so long as$v_1, \dots ,v_j$do not already span the space, $$P\left(v_{j+1} \notin Span(v_1, \dots v_j) \right) \geq \frac{1}{2}.$$ By assumption P3,$A$already had rank at least$n-C \log n$before we added the rows. The only way$A$can fail to be full rank after the augmentation is if the above event occurred at least$4 C \log n$times, an event which occurs with probability at most $$\binom{5C \log n}{4 C \log n} 2^{-4C \log n} = 2^{(-0.39+o(1)) C \log n}.$$ Taking the union bound over all$p$which divide$|det(A)|$, the probability we fail to be of full rank modulo some prime is at most$C \log n 2^{-(0.39+o(1)) C \log n} = Cn^{-0.39C+o(1)}$, proving Claim 2. This bound is probably still not quite tight, especially in the handling of P3 for large$p$. One annoyance in trying to drop below$\log n$is that if the last row of$A$and all the rows added in the augmentation are zero (an event occurring with probability roughly$2^{-n(m-n)}$), the matrix fails to be of full rank modulo every prime. This means just taking the union bound over all the roughly$2^{c n \log n}$primes less than$n^{n/2}$won't be enough if$m-n$is much smaller than$\log n$, unless we could possibly get some handle on the event "$A$is of full rank over$\mathbb{R}$but not over${\mathbb F}_p$" for large$p\$.