Skip to main content
4 of 10
indicated D >0
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$.

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.

This makes it clear that the contributions from the terms in the inner sum die away rather quickly as $k$ gets further from $\frac{n}{2}$, and makes it clear that the number of involutions is bounded above by $C2^{\frac{n^{2}}{2}}$ for some constant $C$, as well as bounded below by $D2^{\frac{n^{2}}{2}}$ for some positive constant $D$. It might be tedious, but it should be relatively easy to get good bounds for $C$ and $D$.

Geoff Robinson
  • 44.4k
  • 5
  • 123
  • 169