The question is simple:



> 
> What fraction of matrices in $G\_n = \text{GL}\_n(\mathbb{Z})$ have at least one unit entry (i.e., either $\lbrace\pm 1 \rbrace$)?
> 
> 
> 


I'm not sure what the correct measure on $G\_n$ would be, so here is a suggestion: for each natural number $m \geq 1$, define $G\_n(m)$ to be the set of precisely those matrices in $G\_n$ whose entries are bounded in absolute value by $m$ and let $H\_n(m)$ be the subset of matrices which have at least one unit entry. These are finite and non-empty sets, so in particular for each $m$ the following ratio is defined: $$r\_n(m) = \frac{|H\_n(m)|}{|G\_n(m)|}$$


Now, one can take limits (or lim-sups?) as $m \to \infty$. Again, this is only a suggested measure and it should not constrain potential answers: all reasonable measures are welcome.


Motivation
----------


I write [software](http://www.math.rutgers.edu/%7Evidit/perseus.html) that pre-processes large (filtered) cell complexes via [discrete Morse theory](http://en.wikipedia.org/wiki/Discrete_Morse_theory) to produce smaller cell complexes with identical homology groups. Without getting into gory details, the basic idea is to greedily exploit unit incidence among cell-pairs in order to clear out the corresponding row and column from the matrix representation of a boundary operator via obvious row and column operations: once these have been cleared, these paired cells can be removed from the complex altogether.


Recently, I was handed a collection of triangulated homology $4$-spheres with tons of torsion in the fundamental groups. On these complexes, the naive greedy collapsing schemes do not produce a perfect reduced complex (i.e., with one zero-dimensional cell and four dimensional cell). In fact, the boundary matrices of the reduced complexes often contain no units at all, and this is precisely when no more collapses are possible. I would like a quantification of *how often should one expect an invertible integer matrix to have exploitable units?* in order to judge the performance of discrete Morse theoretic reductions on these spheres.



What fraction of n x n invertible integer matrices contain at least one unit?
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$.


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


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


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 *any* entry is $\pm 1$ is *at most* $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$).


Hence the "probability"
that any term is $\pm 1$ is asymptotically at most $2n^2/(p-1)$ for any $p$, and hence $0$.


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:


<http://www.math.tau.ac.il/~borovoi/papers/hardy.pdf>


