User smoked salmon sandwiches - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T10:52:28Z http://mathoverflow.net/feeds/user/26524 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/107210/what-fraction-of-n-x-n-invertible-integer-matrices-contain-at-least-one-unit/107227#107227 Answer by smoked salmon sandwiches for What fraction of n x n invertible integer matrices contain at least one unit? smoked salmon sandwiches 2012-09-15T02:53:42Z 2012-09-15T03:53:40Z <p>Let $G_p$ denote the subgroup $\mathrm{GL}_n(\mathbf{F}_p)$ consisting of matrices with determinant $\pm 1$. Then $G_p$ is exactly the image of $\mathrm{GL}_n(\mathbf{Z})$ under reduction mod $p$.</p> <p>Any natural method of counting matrices of "height at most $T$" should have the following property: if one restricts to matrices satisfying some congruence condition corresponding to some subset $S_p \subset G_p$, then the asymptotics should be modified by the factor $|S_p|/|G_p|$.</p> <p>On the other hand, as $p \rightarrow \infty$, the number of elements in $G_p$ with an entry in $\pm 1$ goes to zero. Here is an easy proof, which shows that the probability is at most $2 n^2/(p-1)$, if $n \ge 2$. </p> <p>Permuting the rows and columns preserves $G_p$. Hence the probability that any particular fixed entry is $\pm 1$ is equal to the probability that the first entry is $\pm 1$. Hence the probability that <em>any</em> entry is $\pm 1$ is <em>at most</em> $n^2$ times the probability that any fixed entry is $\pm 1$. Since $n \ge 2$, $G_p$ contains the diagonal matrix with terms $\{\epsilon, \epsilon^{-1}, 1, 1, \ldots, 1\}$, where $\epsilon$ is a primitive root. Multiplication by the $k$th power of element gives a bijection between terms whose first entry is one with terms whose first entry is $\epsilon^k$. Hence the probability that the first term is $\pm 1$ is $2/(p-1)$ times the probability it is non-zero (which is obviously at most $1$).</p> <p>Hence the "probability" that any term is $\pm 1$ is asymptotically at most $2n^2/(p-1)$ for any $p$, and hence $0$.</p> <p>It remains to show that the "natural" forms of counting do satisfy this hypothesis. If one counts columns by their Euclidean norm, then, in this case, the result follows from work of Borovoi and Rudnick:</p> <p><a href="http://www.math.tau.ac.il/~borovoi/papers/hardy.pdf" rel="nofollow">http://www.math.tau.ac.il/~borovoi/papers/hardy.pdf</a></p>