most recent 30 from http://mathoverflow.net 2013-05-20T16:48:06Z http://mathoverflow.net/feeds/question/107210 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 Vidit Nanda 2012-09-14T20:31:05Z 2012-09-15T15:07:36Z

<p>The question is simple:</p> <blockquote> <p>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$)? </p> </blockquote> <p>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)|}$$ </p> <p>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.</p> <h2>Motivation</h2> <p>I write <a href="http://www.math.rutgers.edu/~vidit/perseus.html" rel="nofollow">software</a> that pre-processes large (filtered) cell complexes via <a href="http://en.wikipedia.org/wiki/Discrete_Morse_theory" rel="nofollow">discrete Morse theory</a> 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. </p> <p>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 <em>how often should one expect an invertible integer matrix to have exploitable units?</em> in order to judge the performance of discrete Morse theoretic reductions on these spheres.</p>

http://mathoverflow.net/questions/107210/what-fraction-of-n-x-n-invertible-integer-matrices-contain-at-least-one-unit/107225#107225 Will Jagy 2012-09-15T02:16:58Z 2012-09-15T04:19:32Z

<p>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.$ </p> <p>Edit, 9:17 pm. I did 3 by, i killed it after it finished $m=8.$</p> <pre><code>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:~$ </code></pre> <p>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.</p> <pre><code>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:~$ </code></pre>

http://mathoverflow.net/questions/107210/what-fraction-of-n-x-n-invertible-integer-matrices-contain-at-least-one-unit/107226#107226 Greg Martin 2012-09-15T02:22:14Z 2012-09-15T02:22:14Z

<p>I imagine the answer is that the limiting probability equals 0.</p> <p>Even the asymptotics for $|G_n(M)|$ are nontrivial. See example 1.6 in <a href="http://www.ams.org/mathscinet-getitem?mr=1230289" rel="nofollow">Duke/Rudnick/Sarnak</a>. I would suggest looking at <a href="http://www.ams.org/mathscinet-getitem?mr=2566466" rel="nofollow">one of Shparlinski's papers</a> and the references cited therein; maybe what you need has already been done.</p> <p>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.</p>

http://mathoverflow.net/questions/107210/what-fraction-of-n-x-n-invertible-integer-matrices-contain-at-least-one-unit/107227#107227 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>

http://mathoverflow.net/questions/107210/what-fraction-of-n-x-n-invertible-integer-matrices-contain-at-least-one-unit/107241#107241 Denis Chaperon de Lauzières 2012-09-15T08:21:42Z 2012-09-15T09:23:40Z

<p>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). </p> <p>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$.</p> <p>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.</p>

http://mathoverflow.net/questions/107210/what-fraction-of-n-x-n-invertible-integer-matrices-contain-at-least-one-unit/107262#107262 Igor Rivin 2012-09-15T15:07:36Z 2012-09-15T15:07:36Z

<p>Really a couple of comments on @smokedsalmonsandwich's answer:</p> <p>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.</p> <p>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</p> <p>Thirdly, one can get sharp error bounds on the asymptotics restricted to congruence subsets using Nevo/Sarnak and Gorodnik/Nevo.</p> <p>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.</p>