Skip to main content
5 of 10
Expanded answer and included more explanatory comments.
Geoff Robinson
  • 44.4k
  • 5
  • 123
  • 169

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.

Note that as we decrease $k$, the numerator of the fraction appearing decreases, and the denominator increases.

Hence when $n$ is even, the number of involutions is less than $2^{\frac{n^{2}}{2}} \prod_{j=\frac{n}{2}+1}^{n}( 1- \frac{1}{2^{j}}) \left( \sum_{k=1}^{\frac{n}{2}} 2^{- 2\left(\frac{n}{2}-k\right)^{2}}\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 product appearing approaches $1$ from below. In any case, we see that when $n$ is even and positive , the number of involutions is always between $\frac{3}{4} 2^{\frac{n^{2}}{2}}$ and $2^{\frac{n^{2}}{2}}\sum_{j= 0}^{\infty} \left(\frac{1}{4} \right)^{j^{2}}$, where the latter term is the limiting value.

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

Geoff Robinson
  • 44.4k
  • 5
  • 123
  • 169