7
$\begingroup$

Is it known how the number of involutions in $GL_n(2)$, the group of $n\times n$ matrices over $\mathbb{Z}/2\mathbb{Z}$, behaves as $n\to\infty$ ?

Equivalently, one may ask this for the number of $n\times n$ matrices $A$ over $\mathbb{Z}/2\mathbb{Z}$ satisfying $A^2=0$, as $(A+I)^2=I \mod 2$.

Needless to say, there are $\lfloor n/2\rfloor$ conjugacy classes of involutions in $GL_n(2)$, and one can write down formula for the centraliser order for each class,

$$\frac{\left|GL_n(2)\right|}{2^{k^2+2k(n-2k)}\left|GL_k(2)\right|\left|GL_{n-2k}(2)\right|},\quad 1\leq k\leq \left\lfloor \frac{n}{2} \right\rfloor,$$

but it's quite a mess to just sum them up.

$\endgroup$
  • $\begingroup$ Have you tried calculating the first few terms, then consulting the Online Encyclopedia of Integer Sequences? $\endgroup$ – Gerry Myerson Sep 30 '15 at 3:01
  • $\begingroup$ yes I did. No such sequence is known, apparently. $\endgroup$ – Dima Pasechnik Sep 30 '15 at 3:31
  • 2
    $\begingroup$ Rod Gow informs me that A. A. Kirillov and A. Melnikov answered this question in a paper dating from 1995: www.emis.de/journals/SC/1997/2/pdf/smf_sem-cong_2_35-42.pdf $\endgroup$ – John Murray Sep 30 '15 at 14:05
  • 1
    $\begingroup$ John, this paper talks a lot about solutions of $X^2=0$ in upper triangular matrices over a finite field, but does not mention $GL$. $\endgroup$ – Dima Pasechnik Sep 30 '15 at 16:36
  • 1
    $\begingroup$ I guess this question led to this paper by Jason Fulman, Robert Guralnick, and Dennis Stanton arxiv.org/abs/1602.03611 $\endgroup$ – j.c. Sep 27 '17 at 15:51
5
$\begingroup$

As a matter of fact, OEIS has the corresponding integer sequence A053722, although shifted by 1, as it corresponds to the number of solutions to $X^2=1$ in $GL_n(2)$, i.e. it counts the identity along with the involutions. I thought OEIS does this kind of elementary transformations of sequences automatically, but in fact it does not.

Incidentally, this (shifted) number can be obtained as the sum of dimensions of real representations of $GL_n(2)$, see e.g. paper by Fulman and Vinroot.

This still does not answer the original question, though.

$\endgroup$
  • $\begingroup$ The summation given in OEIS seems routine for asymptotic estimation. $\endgroup$ – Brendan McKay Oct 3 '15 at 1:37
  • $\begingroup$ I added a formula for each of [n/2] terms (plus the term for k=0, which should be 1, assuming $|GL_0(k)|=1$) in the question, but it does not look routine... $\endgroup$ – Dima Pasechnik Oct 3 '15 at 4:09
  • $\begingroup$ The ratio of consecutive terms is easy to calculate and from that the dominant terms can be identified. It looks pretty messy, but not fundamentally difficult. $\endgroup$ – Brendan McKay Oct 3 '15 at 4:57
  • $\begingroup$ Well, I only did such things for ordinary hypergeometric functions, not for basic hypergeometric ones, like here. Any place to look for these things? $\endgroup$ – Dima Pasechnik Oct 3 '15 at 5:37
  • $\begingroup$ OK, I think I'm being lazy, I should just sit down and calculate :-) $\endgroup$ – Dima Pasechnik Oct 3 '15 at 15:56
3
$\begingroup$

We may write $|{\rm GL}(n,2)| = 2^{n^{2}} \prod_{j=1}^{n}( 1- \frac{1}{2^{j}}).$ As $n \to \infty$, the rightmost factor tends to $\left( \sum_{r=0 }^{\infty} \frac{p(r)}{2^{r}} \right)^{-1}$, where $p(r)$ is the number of partitions of $r$. Let us write $|{\rm GL}(n,2)| = 2^{n^{2}}f(n)$.

Then we see that the number of involutions of ${\rm GL}(n,2)$ is given by $\sum_{k = 1}^{\lfloor \frac{n}{2} \rfloor} 2^{2k(n-k)} \frac{f(n)}{f(k)f(n-2k)}$ using the formula given in the question ( if $k = \frac{n}{2}$, we should interpret $|{\rm GL}(n-2k,2)|$ as $1$).

Hence the number of involutions in ${\rm GL}(n,2)$ may be expressed as

$2^{\frac{n^{2}}{2}} \left(\sum_{k=1}^{\lfloor \frac{n}{2} \rfloor} 2^{- 2\left(\frac{n}{2}-k\right)^{2}}\left( \frac{\prod_{j=k+1}^{n}( 1- \frac{1}{2^{j}})}{ \prod_{m=1}^{n-2k}( 1- \frac{1}{2^{m}})}\right)\right)$ if $n$ is odd, and $2^{\frac{n^{2}}{2}} \left( \prod_{j=\frac{n}{2}+1}^{n}( 1- \frac{1}{2^{j}})+ \sum_{k=1}^{\lfloor \frac{n}{2} \rfloor-1} 2^{- 2\left(\frac{n}{2}-k\right)^{2}}\left( \frac{\prod_{j=k+1}^{n}( 1- \frac{1}{2^{j}})}{ \prod_{m=1}^{n-2k}( 1- \frac{1}{2^{m}})}\right)\right)$ if $n$ is even.

Hence when $n$ is even, the number of involutions is at most $2^{\frac{n^{2}}{2}} \prod_{j=\frac{n}{2}+1}^{n}( 1- \frac{1}{2^{j}}) \left( 1 + \frac{1}{\prod_{m=1}^{n-2}( 1- \frac{1}{2^{m}})} \left( \sum_{k=1}^{\frac{n}{2}} 2^{- 2(\frac{n}{2}-k)^{2}}\right)\right)$ and is at least $2^{\frac{n^{2}}{2}} \prod_{j=\frac{n}{2}+1}^{n}( 1- \frac{1}{2^{j}})$.

As (even) $n \to \infty$, the first product appearing approaches $1$ from below and (the reciprocal of) the second product appearing tends to $\sum_{r=0}^{\infty} \frac{p(r)}{2^{r}}$, while the inner sum is at most $\sum_{j=0}^{\infty} \left(\frac{1}{4} \right)^{j^{2}}$.

I omit the similar analysis when $n$ is odd.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.