What fraction of n x n invertible integer matrices contain at least one unit?

Question

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 that pre-processes large (filtered) cell complexes via 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.

Answer 1

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

Answer 2

I imagine the answer is that the limiting probability equals 0.

Even the asymptotics for $|G_n(M)|$ are nontrivial. See example 1.6 in Duke/Rudnick/Sarnak. I would suggest looking at one of Shparlinski's papers and the references cited therein; maybe what you need has already been done.

My hope would be that you could count the number of matrices in $|G_n(M)|$ with a prescribed fixed first row, say. If so, you could solve this problem just by considering the 1s in the first row.

Answer 3

I did the 2 by 2 case for $m$ up to $100.$ For very small entry bound $m,$ a $\pm 1$ is always required in order to get determinant $\pm 1.$ I think the limit of $r_2(m)$ is $0$ as $m$ goes to $\infty.$

Edit, 9:17 pm. I did 3 by, i killed it after it finished $m=8.$

jagy@phobeusjunior:~$ ./units_3
               m      H_3(m)      G_3(m)           r_3(m)
               1        6960        6960            1
               2      135408      135408            1
               3     1279344     1281648            0.9982023145200555
               4     5094192     5194416            0.9807054344511491
               5    19593840    20852976            0.939618402668281
               6    43474800    47054640            0.9239216366334967
               7   113376432   131283120            0.8636025103608141
               8   214735152   256950192            0.8357073031492422
    ^C
    jagy@phobeusjunior:~$ 
jagy@phobeusjunior:~$ 

I think for $r_3(m)$ you also get limit $0.$ And so on. It should not be difficult switching to $3$ by $3,$ it will just execute even more slowly. 7:16 pm.

jagy@phobeusjunior:~$ ./units
               m        H_2(m)     G_2(m)  r_2(m)
               1          40          40   1
               2         104         104   1
               3         232         232   1
               4         328         360   0.9111111111111111
               5         520         616   0.8441558441558441
               6         616         744   0.8279569892473119
               7         840        1128   0.7446808510638298
               8         968        1384   0.6994219653179191
               9        1192        1768   0.6742081447963801
              10        1320        2024   0.6521739130434783
              11        1608        2664   0.6036036036036037
              12        1704        2920   0.5835616438356165
              13        1992        3688   0.5401301518438177
              14        2152        4072   0.5284872298624754
              15        2408        4584   0.525305410122164
              16        2568        5096   0.5039246467817896
              17        2888        6120   0.4718954248366013
              18        2984        6504   0.4587945879458795
              19        3336        7656   0.4357366771159875
              20        3496        8168   0.4280117531831538
              21        3784        8936   0.423455684870188
              22        3944        9576   0.4118629908103592
              23        4296       10984   0.3911143481427531
              24        4424       11496   0.3848295059151009
              25        4776       12776   0.3738259236067627
              26        4968       13544   0.3668044890726521
              27        5256       14696   0.3576483396842678
              28        5416       15464   0.3502327987584066
              29        5832       17256   0.3379694019471488
              30        5928       17768   0.3336334984241333
              31        6344       19688   0.3222267370987403
              32        6504       20712   0.3140208574739282
              33        6792       21992   0.308839578028374
              34        7016       23016   0.3048314216197428
              35        7400       24552   0.3014011078527207
              36        7560       25320   0.2985781990521327
              37        7944       27624   0.2875760208514335
              38        8104       28776   0.2816235752015568
              39        8456       30312   0.2789654262338348
              40        8616       31336   0.2749553229512382
              41        9096       33896   0.2683502478168516
              42        9192       34664   0.2651742441726286
              43        9608       37352   0.2572285285928465
              44        9832       38632   0.2545040381031269
              45       10120       40168   0.2519418442541326
              46       10344       41576   0.2487973831056379
              47       10760       44520   0.2416891284815813
              48       10888       45544   0.2390655190584929
              49       11368       48232   0.2356941449659977
              50       11560       49512   0.2334787526256261
              51       11912       51560   0.2310318076027928
              52       12072       53096   0.2273617598312491
              53       12488       56424   0.2213242591804906
              54       12648       57576   0.2196748645268862
              55       13128       60136   0.2183051749368099
              56       13352       61672   0.2165001945777663
              57       13704       63976   0.2142053269976241
              58       13864       65768   0.2108016056440822
              59       14344       69480   0.206447898675878
              60       14440       70504   0.2048110745489618
              61       14920       74344   0.2006886904121382
              62       15144       76264   0.1985733766914927
              63       15464       78568   0.1968231341003971
              64       15752       80616   0.1953954549965267
              65       16200       83688   0.1935761399483797
              66       16360       84968   0.1925430750400151
              67       16776       89192   0.1880886178132568
              68       16936       91240   0.1856203419552828
              69       17352       94056   0.1844858382240367
              70       17512       95592   0.1831952464641393
              71       18120      100072   0.1810696298664961
              72       18216      101608   0.1792772222659633
              73       18696      106216   0.1760186789184304
              74       18920      108520   0.1743457427202359
              75       19208      111080   0.1729204177169608
              76       19496      113384   0.1719466591406195
              77       19912      117224   0.1698628267249027
              78       20072      118760   0.169013135735938
              79       20616      123752   0.1665912470101493
              80       20808      125800   0.1654054054054054
              81       21224      129256   0.1642012749891688
              82       21416      131816   0.1624688960368999
              83       21896      137064   0.1597501896924065
              84       22056      138600   0.1591341991341991
              85       22536      142696   0.1579301452037899
              86       22760      145384   0.1565509271996919
              87       23112      148968   0.1551474142097632
              88       23272      151528   0.1535821762314556
              89       23880      157160   0.1519470603206923
              90       24040      158696   0.1514845994858093
              91       24584      163304   0.1505413217067555
              92       24808      166120   0.1493378280760896
              93       25096      169960   0.1476582725347141
              94       25320      172904   0.1464396428075695
              95       25800      177512   0.1453422867186444
              96       25960      179560   0.144575629316106
              97       26504      185704   0.1427217507431181
              98       26728      188392   0.1418743895706824
              99       27176      192232   0.1413708435640268
             100       27400      194792   0.1406628608977781
    jagy@phobeusjunior:~$ 

Answer 4

Using arguments like those indicated by smoked-salmon-sandwiches, it will follow that the "probability" $|H_n(m)|/|G_n(m)|$ tends to zero exponentially fast with the height $m$. This should be a special case of the general results of Gorodnik and Nevo (see their book in Annals of Math. Studies).

Another way of measuring things with the same conclusion is to take a generating set $S$ of $\mathrm{GL}_n(\mathbf{Z})$ and consider a random walk using $S$ (and the inverses of elements of $S$). After $k$ steps, it will transpire that the probability of being in the subset $H_n$ will be $\leq c_1c_2^{-k}$ for some $c_1>0$, $c_2>1$. Here the argument is a bit more transparent maybe: basically, the equidistribution modulo a prime follows from elementary Markov chain methods, and the uniformity over primes that implies exponential decay (by choosing a suitable prime) is a direct consequence of Kazhdan's Property (T) (for $n\geq 3$) or Property ($\tau$) for $n=2$.

Arguments like this are known as "escape from subvariaties" in the recent literature concerning sieve in discrete groups (though the focus there is on more complicated counting problems.) There is some discussion in the paper "Affine linear sieve" of Bourgain, Gamburd and Sarnak and in recent surveys of this topic which can be found by googling around.

Answer 5

Really a couple of comments on @smokedsalmonsandwich's answer:

for the result $\mod p$ the sledgehammer way of dealing with this is the Lang-Weil bound: restricting some specific entry to 1 defines a proper sub variety of algebraic group $SL(n)$ and so for large $p$ the number of restricted matrices is like $c/p$ times the number of unrestricted matrices. You are in the union of $n^2$ such subvarieties, so you get something very similar to @smokedsalmonsandwich's bound.

Secondly, if the matrices have different restrictions on coefficients, there is relevant work of Ahmadi-Shparlinsky: Distribution of matrices with restricted entries over finite fields O Ahmadi, IE Shparlinski - Indagationes Mathematicae, 2007

Thirdly, one can get sharp error bounds on the asymptotics restricted to congruence subsets using Nevo/Sarnak and Gorodnik/Nevo.

Fourthly, using all of the above together with sieve machinery (see, e.g., Emmanuel Kowalski's book) should give decent bounds on what the odds are of finding a matrix with a $\pm1$ entry.