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

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.

-
seems tractable for $n=2.$ Demand $a_{11} a_{22} = k, \; a_{12} a_{21} = k-1,$ all positive, why not? Then something about numbers of divisors of $k,k-1$ no larger than $m.$ If $k \geq m+2$ no $1$'s. I do see that you want $n$ large, but if the answer for $n=2$ is $0,$ while the answer for $n=1$ is $1,$ that is persuasive. –  Will Jagy Sep 14 '12 at 20:52
Are the inverses also supposed to be integer matrices? Gerhard "Ask Me About System Design" Paseman, 2012.09.14 –  Gerhard Paseman Sep 14 '12 at 21:00
@Gerhard, must be, the determinant needs to be $\pm 1$ for $GL_n.$ Also the limit is clearly $0$ if not. –  Will Jagy Sep 14 '12 at 21:06
I meant that I am demanding that the product of the two diagonal elements be my $k,$ but if both $m, m-1 < k$ and $m$ is the bound on element absolute values, $1 \cdot m < k$ and both diagonal elements must be larger than $1.$ So it should probably read $k \geq m+1.$ For $n=2$ we can simply switch the diagonal and the off-diagonal. Meanwhile, we must have $k \leq m^2$ here. The numerator and denominator in your $r_2(m)$ can thus be separately estimated pretty well, I think, with sums over my $1 \leq k \leq m^2,$ where $k \leq m$ and $m < k \leq m^2$ behave differently. Number theory. –  Will Jagy Sep 14 '12 at 21:53
Will: thank you, that makes sense at least for $n = 2$. –  Vidit Nanda Sep 14 '12 at 22:05

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

-

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.

-
Greg, thank you for the references. I was aware that counting in GL_n(Z) was not trivial, but hoped that the fraction could be estimated even though both numerator and denominator could not. It seems that the consensus is that unit entry matrices have measure zero as you indicate. –  Vidit Nanda Sep 15 '12 at 5:43

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:~$ - Wow, thank you for putting in the time to code. It seems like the ratio really does decline substantially as m is increased. – Vidit Nanda Sep 15 '12 at 5:37 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. - 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.

-