Asymptotics for the enumeration of commuting matrices over finite fields

Kathrin Bringmann, Shane Chern, Johann Franke, Bernhard Heim · 2025

Read Asymptotics for the enumeration of commuting matrices over finite fields by Kathrin Bringmann, Shane Chern, Johann Franke, Bernhard Heim (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-16178.txt.

Introduction

Kathrin Bringmann, Shane Chern, Johann Franke, and Bernhard Heim count pairs of matrices over finite fields that commute, meaning the order of their product does not matter. They derive formulas that describe how this count grows as the field and matrix size change. Their method uses product expansions of generating functions, which package the counts into a single power series. The short note gives a clean asymptotic picture for a classic counting problem in algebra.

Catalog record

CREATORKathrin Bringmann, Shane Chern, Johann Franke, Bernhard Heim
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE18 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-16178

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Asymptotics for the enumeration of commuting matrices over finite fields Kathrin Bringmann, Shane Chern, Johann Franke, Bernhard Heim Abstract . We give asymptotic expressions for the number of commuting matrices over finite fields. For this we use product expansions for the corresponding generating functions. In honor of James Lepowsky’s 80-th birthday. 1. Introduction and statement of results Let \mathbb{F}_{p^{r}} be the finite field with p^{r} elements, where p is a prime and r\in\mathbb{N} . The study of the enumeration of commuting square matrix pairs over \mathbb{F}_{p^{r}} was first launched by Feit and Fine [ 5 ] . Let Q_{p^{r}}(n) denote the number of ordered pairs of (not necessarily distinct) commuting n\times n matrices with coefficients in \mathbb{F}_{p^{r}} . Feit and Fine proved that Q_{p^{r}}(n) (re-normalized) admits the following product-like generating function. Theorem 1.1 (Feit–Fine, [ 5 , p. 91] ) . We have (1.1) \displaystyle\sum_{n\geq 0}\frac{Q_{p^{r}}(n)}{p^{rn^{2}}f_{p^{r}}(n)}w^{n}=\prod_{\begin{subarray}{c}\ell\geq 1\\ j\geq 0\end{subarray}}\frac{1}{1-p^{r(1-j)}w^{\ell}}, where (1.2) \displaystyle f_{p^{r}}(n):=\prod_{j=1}^{n}\left(1-p^{-rj}\right). Remarks . (1) The product in ( 1.1 ) converges for w\in\mathbb{C} with |w|<1 not being a pole and continues to a meromorphic function for |w|<1 . This is due to the absolute and uniform convergence on compact subsets of the double series \sum_{\begin{subarray}{c}\ell\geq 1\\ j\geq 0\end{subarray}}p^{r(1-j)}w^{\ell} away from a pole. (2) Recall that (see [ 8 , (2.1)] ) (1.3) \left|\mathrm{GL}_{n}(\mathbb{F}_{p^{r}})\right|=p^{rn^{2}}f_{p^{r}}(n). Therefore, ( 1.1 ) can be written as \displaystyle\sum_{n\geq 0}\frac{Q_{p^{r}}(n)}{\left|\mathrm{GL}_{n}(\mathbb{F}_{p^{r}})\right|}w^{n}=\prod_{\begin{subarray}{c}\ell\geq 1\\ j\geq 0\end{subarray}}\frac{1}{1-p^{r(1-j)}w^{\ell}}. (3) By [ 5 , (1)] and ( 1.3 ), we have (1.4) Q_{p^{r}}(n)=|\mathrm{GL}_{n}(\mathbb{F}_{p^{r}})|\sum_{\lambda\vdash n}\frac{p^{r\sum_{k=1}^{n}b_{k}}}{\prod_{k=1}^{n}{f_{p^{r}}(b_{k})}}, where the sum runs over all partitions of n and \lambda has the frequencies b_{k} given by n=\sum_{k=1}^{n}b_{k}k . A natural question is to approximate Q_{p^{r}}(n) , as n\to\infty . It was shown by Motzkin–Taussky [ 12 ] (see also [ 9 , p. 71, Theorem 2] ) that the space of n\times n commuting matrices over an algebraically closed field has dimension n^{2}+n . Hence, heuristically, Q_{p^{r}}(n) should be proportional to p^{r(n^{2}+n)} for n sufficiently large. This observation was rigorously proved by Fulman and Guralnick [ 7 , Theorem 2.6] as a byproduct of their new proof of the result of Feit and Fine. More precisely, Fulman and Guralnick established that (1.5) \lim_{n\to\infty}\frac{Q_{p^{r}}(n)}{p^{r(n^{2}+n)}}=\prod_{j\geq 1}\left(1-p^{-rj}\right)^{-j}. In this paper, we prove more precise asymptotics for Q_{p^{r}}(n) . To start with, we write, for w\in{\mathbb{C}} with |w|<1 , (1.6) \displaystyle\prod_{\begin{subarray}{c}\ell\geq 1\\ j\geq 0\end{subarray}}\frac{1}{1-p^{r(1-j)}w^{\ell}}=P_{0,p^{r}}(w)F_{p^{r}}(w), where for x>0 (1.7) \displaystyle P_{m,x}(w):=\prod_{\begin{subarray}{c}\ell\geq 1\\ \ell\not=m\end{subarray}}\frac{1}{1-xw^{\ell}},\qquad F_{p^{r}}(w):=\prod_{\ell,j\geq 1}\frac{1}{1-p^{r(1-j)}w^{\ell}}. We show the following asymptotic behavior of Q_{p^{r}}(n) , as n\to\infty . Throughout, we use the notation \zeta_{m}:=e^{\frac{2\pi i}{m}} . Theorem 1.2 . We have, as n\to\infty , (1.8) \displaystyle Q_{p^{r}}(n)\sim p^{rn^{2}}f_{p^{r}}(n)\sum_{m\geq 1}C_{m,p^{r}}(n)p^{\frac{rn}{m}}, where \displaystyle C_{m,p^{r}}(n):=\frac{1}{m}\sum_{j=0}^{m-1}P_{m,p^{r}}\left(\zeta_{m}^{-j}p^{-\frac{r}{m}}\right)F_{p^{r}}\left(\zeta_{m}^{-j}p^{-\frac{r}{m}}\right)\zeta_{m}^{nj}. In particular, we have, as n\to\infty , \displaystyle{Q_{p^{r}}(n)=p^{r\left(n^{2}+n\right)}\prod_{j\geq 1}\left(1-p^{-rj}\right)^{-j}}+O\left(p^{rn^{2}+\frac{rn}{2}}\right). Remark . The series in ( 1.8 ) does not converge, but should be viewed as an asymptotic expansion. Also note that C_{m,p^{r}}(n) only depends on n\pmod{m} . In particular, C_{1,p^{r}}(n) does not depend on n . Furthermore, we have \displaystyle|C_{m,p^{r}}(n)|\leq\max_{0\leq j\leq m-1}\left|P_{m,p^{r}}\!\left(\zeta_{m}^{-j}p^{-\frac{r}{m}}\right)\!F_{p^{r}}\!\left(\zeta_{m}^{-j}p^{-\frac{r}{m}}\right)\right|=\left|P_{m,p^{r}}\!\left(p^{-\frac{r}{m}}\right)\!F_{p^{r}}\!\left(p^{-\frac{r}{m}}\right)\right|. As a result, when truncated at m=N , the error in ( 1.8 ) is O(p^{\frac{rn}{N+1}}) . Example. Let p=2 and r=1 . By ( 1.1 ), we have (1.9) \displaystyle(1-2w)\sum_{n\geq 0}\frac{Q_{2}(n)}{2^{n^{2}}f_{2}(n)}w^{n}=\prod_{\begin{subarray}{c}\ell\geq 1\\ j\geq 0\\ (\ell,j)\not=(1,0)\end{subarray}}\frac{1}{1-2^{1-j}w^{\ell}}. While ( 1.1 ) has radius of convergence \tfrac{1}{2} , the right-hand side of ( 1.9 ) has radius of convergence \frac{1}{\sqrt{2}} . Hence, we obtain \displaystyle C_{1,2}(1)=\lim_{n\to\infty}\frac{Q_{2}(n)}{2^{n^{2}+n}f_{2}(n)}=\prod_{j\geq 1}\frac{1}{\left(1-2^{-j}\right)^{j+1}}=34.738723457\ldots. Further values are given by \displaystyle C_{2,2}(1) \displaystyle=-11716.7651425569\ldots \displaystyle\quad C_{2,2}(2) \displaystyle=-11716.3960075313\ldots \displaystyle C_{3,2}(1) \displaystyle=7970793.64416118\ldots \displaystyle\quad C_{3,2}(2) \displaystyle=7970793.59033743\ldots \displaystyle C_{3,2}(3) \displaystyle=7970793.67801128\ldots. Looking at these first values one notes that they are very close to each other for m fixed. A further investigation of their behavior would be interesting. The paper is organized as follows. First we recall some basic definitions. Then we give a proof of Theorem 1.2 , and generalize these ideas to another Cohen–Lenstra series in Theorem 4.1 . In the final section, we propose problems for further research. 2. Preliminaries In the following, we recall some required results from complex analysis. We start with a well-known and simple observation that is still very useful for many aspects in the theory of q -series, recurrences, and combinatorics. For \varrho\in{\mathbb{R}}^{+} let B_{\varrho}(a):=\{z\in\mathbb{C}:|z-a|<\varrho\} . Proposition 2.1 . Let a\in{\mathbb{C}} , \varrho\in{\mathbb{R}}^{+} , and f be a holomorphic function defined in a neighborhood of a . Then the following are equivalent: (1) The function f extends to an analytic function on B_{\varrho}(a) , but not on B_{\varrho+\varepsilon}(a) for any \varepsilon>0 . (2) The power series \sum_{n\geq 0}\frac{f^{(n)}(a)}{n!}(z-a)^{n} has radius of convergence \varrho . For a sequence a_{m} of non-zero complex numbers (2.1) \displaystyle F(w):=\prod_{m\geq 1}\left(1-\frac{w}{a_{m}}\right). Proposition 2.2 (Wang, [ 13 , Theorem 1] ) . Let a_{m} be a sequence of non-zero complex numbers such that a_{m}\not=a_{n} for m\not=n and such that \sum_{m\geq 1}|a_{m}|^{-1} converges. Then the function \frac{1}{F} is holomorphic in a neighborhood of w=0 and we have there \displaystyle\frac{1}{F(w)}=-\sum_{k\geq 0}\sum_{m\geq 1}\frac{1}{F^{\prime}(a_{m})a_{m}^{k+1}}w^{k}. 3. Proof of Theorem 1.2 To prove Theorem 1.2 , we require the following lemma. Lemma 3.1 . Let x>1 , n\in\mathbb{N} , 0<\varepsilon<x^{-\frac{1}{n}} , and f be a holomorphic function in some region \mathcal{R}_{x,n,\varepsilon}:=\{w\in{\mathbb{C}}\colon x^{-\frac{1}{n}}-\varepsilon<|w|<x^{-\frac{1}{n}}+\varepsilon\} . Define \displaystyle g(w):=\frac{f(w)}{1-xw^{n}}. Then \displaystyle g(w)-\frac{1}{n}\sum_{j=0}^{n-1}\frac{f\left(\zeta_{n}^{-j}x^{-\frac{1}{n}}\right)}{1-\zeta_{n}^{j}x^{\frac{1}{n}}w} continues holomorphically to \mathcal{R}_{x,n,\varepsilon} . Proof. The only poles of g in \mathcal{R}_{x,n,\varepsilon} lie in \{\zeta_{n}^{-j}x^{-\frac{1}{n}}\colon 0\leq j\leq n-1\} . These are simple. We compute, using l’Hospital, \displaystyle\lim_{w\to\zeta_{n}^{-j}\!x^{-\frac{1}{n}}}\frac{\left(1-\zeta_{n}^{j}x^{\frac{1}{n}}w\right)\!f(w)}{1-xw^{n}}=\frac{1}{n}f\!\left(\zeta_{n}^{-j}x^{-\frac{1}{n}}\right)\!. The claim follows. ∎ We have the following corollary to Lemma 3.1 . Corollary 3.2 . Let f be a function holomorphic inside the unit disk and N\in\mathbb{N} . Then \displaystyle P_{0,p^{r}}(w)f(w)-\sum_{m=1}^{N}\frac{1}{m}\sum_{j=0}^{m-1}\frac{P_{m,p^{r}}\left(\zeta_{m}^{-j}p^{-\frac{r}{m}}\right)f\left(\zeta_{n}^{-j}p^{-\frac{r}{m}}\right)}{1-\zeta_{m}^{j}p^{\frac{r}{m}}w} continues holomorphically to the region \{w\in{\mathbb{C}}:|w|<p^{-\frac{r}{N+1}}\} . Proof. By ( 1.7 ), we have, for m\in{\mathbb{N}} , \displaystyle P_{0,p^{r}}(w)f(w)=\frac{P_{m,p^{r}}(w)f(w)}{1-p^{r}w^{m}}. Note that the numerator is holomorphic in the region \left\{w\in{\mathbb{C}}\colon p^{-\frac{r}{m-1}}<|w|<p^{-\frac{r}{m+1}}\right\} (where p^{-\frac{r}{0}}:=0 ). By applying Lemma 3.1 iteratively, the claim follows. ∎ We are now ready to prove Theorem 1.2 . Proof of Theorem 1.2 . Let N\in{\mathbb{N}} be arbitrary. We abbreviate c_{m,j}:=P_{m,p^{r}}\left(\zeta_{m}^{-j}p^{-\frac{r}{m}}\right)F_{p^{r}}\left(\zeta_{m}^{-j}p^{-\frac{r}{m}}\right). By ( 1.1 ), ( 1.6 ), and Corollary 3.2 we conclude that \displaystyle\sum_{n\geq 0}\frac{Q_{p^{r}}(n)}{p^{rn^{2}}f_{p^{r}}(n)}w^{n}-\sum_{m=1}^{N}\frac{1}{m}\sum_{j=0}^{m-1}\frac{c_{m,j}}{1-\zeta_{m}^{j}p^{\frac{r}{m}}w} continues holomorphically to \{w\in{\mathbb{C}}:|w|<p^{-\frac{r}{N+1}}\} . We can then write \displaystyle\sum_{m=1}^{N}\frac{1}{m}\sum_{j=0}^{m-1}\frac{c_{m,j}}{1-\zeta_{m}^{j}p^{\frac{r}{m}}w}=\sum_{n\geq 0}\sum_{m=1}^{N}\frac{p^{\frac{rn}{m}}w^{n}}{m}\sum_{j=0}^{m-1}c_{m,j}\zeta_{m}^{jn}. Hence we have, for \varepsilon>0 , \displaystyle\frac{Q_{p^{r}}(n)}{p^{rn^{2}}f_{p^{r}}(n)}-\sum_{m=1}^{N}\frac{1}{m}\sum_{j=0}^{m-1}c_{m,j}\zeta_{m}^{jn}p^{\frac{rn}{m}}=O_{\varepsilon}\left(p^{\left(\frac{r}{N+1}+\varepsilon\right)n}\right)\quad(n\to\infty). Equivalently, we have, as n\to\infty , Q_{p^{r}}(n)=p^{rn^{2}}f_{p^{r}}(n)\sum_{m=1}^{N}\frac{1}{m}\sum_{j=0}^{m-1}c_{m,j}\zeta_{m}^{jn}p^{\frac{rn}{m}}+O_{\varepsilon}\left(p^{rn^{2}+\left(\frac{r}{N+1}+\varepsilon\right)n}\right). The result follows after a straightforward calculation. ∎ Finally, we give an upper bound for the coefficients in the asymptotic expansion in Theorem 1.2 . Proposition 3.3 . We have, for \varepsilon>0 , uniformly in m , p^{r} , and n \displaystyle C_{m,p^{r}}(n)\ll_{\varepsilon}\exp\left(\frac{\zeta(3)+\varepsilon}{\left(1-p^{-\frac{r}{m}}\right)^{2}}\right), where \zeta denotes the Riemann zeta function. Proof. By ( 1.7 ) we have \displaystyle\left|P_{m,p^{r}}\!\left({{p}^{-\frac{r}{m}}}\right)\!F_{p^{r}}\!\left({{p}^{-\frac{r}{m}}}\right)\right|=\prod_{\begin{subarray}{c}\ell\geq 1\\ \ell\not=m\end{subarray}}\left|\frac{1}{1-p^{r-\frac{r\ell}{m}}}\right|\prod_{\ell,j\geq 1}\left|\frac{1}{1-p^{r(1-j)}p^{-\frac{r\ell}{m}}}\right|. We estimate both products separately. First, we have \displaystyle\prod_{\begin{subarray}{c}\ell\geq 1\\ \ell\not=m\end{subarray}}\frac{1}{1-p^{r-\frac{r\ell}{m}}} \displaystyle=(-1)^{m+1}p^{-\frac{rm(m+1)}{2m}}P_{0,1}\!\left(p^{-\frac{r}{m}}\right)\prod_{\ell=1}^{m-1}\frac{1}{1-p^{-\frac{r\ell}{m}}} \displaystyle\ll p^{-\frac{r(m-1)}{2}}P_{0,1}^{2}\!\left(p^{-\frac{r}{m}}\right). For the second product, we find \prod_{\ell,j\geq 1}\frac{1}{1\!-\!p^{r(1-j)}p^{-\frac{r\ell}{m}}}=\prod_{\begin{subarray}{c}j\geq 0\\ \ell\geq 1\end{subarray}}\frac{1}{1\!-\!p^{-\frac{r}{m}(mj+\ell)}}\ll\prod_{\begin{subarray}{c}j\geq 0\\ \ell\geq 1\end{subarray}}\frac{1}{1\!-\!p^{-\frac{r}{m}(j+\ell)}}\\ =\prod_{j\geq 1}\!\left(1\!-\!p^{-\frac{rj}{m}}\right)^{\!-j}. Applying [ 2 , Lemma 3.2] , we have, as w\to 1^{-} , \displaystyle P_{0,1}^{2}\left(w\right)\ll_{\varepsilon}e^{\frac{\zeta(2)+\varepsilon}{|w-1|}},\qquad\prod_{j\geq 1}\frac{1}{(1-w^{j})^{j}}\ll_{\varepsilon}e^{\frac{\zeta(3)+\varepsilon}{|w-1|^{2}}} for all \varepsilon>0 . As a result, for all \varepsilon>0 , we find the claimed bound. ∎ 4. Cohen–Lenstra Series and the Nilpotent Classes Since its discovery, Feit and Fine’s generating function ( 1.1 ) has been reproved by other means such as the motivic Donaldson–Thomas theory [ 3 ] . More recently, Huang [ 10 ] placed such counting problems into the framework of Cohen–Lenstra series [ 4 ] . Simply speaking, Huang considered (generalized) Cohen–Lenstra series , which are defined as \displaystyle Z_{R}(w)=Z_{R/\mathbb{F}_{p^{r}}}(w):=\sum_{M}\frac{1}{|\operatorname{Aut}(M)|}w^{\dim_{\mathbb{F}_{p^{r}}}(M)}, where M runs over

Read the complete text