format: text

text:
# Contents

## 1 Introduction

A natural problem is to understand what a typical element of the finite general linear group $`GL(n,q)`$ “looks like”. Many of the interesting properties of a random matrix depend only on its conjugacy class. The following list of questions one could ask are of this type:

1. How many Jordan blocks are there in the rational canonical form of a random matrix?
2. What is the distribution of the order of a random matrix?
3. What is the probability that the characteristic polynomial of a random matrix has no repeated factors?
4. What is the probability that the characteristic polynomial of a random matrix is equal to its minimal polynomial?
5. What is the probability that a random matrix is semisimple (i.e. diagonalizable over the algebraic closure $`\overline{F_q}`$ of the field of $`q`$ elements)?

As Section 2 will indicate, answers to these questions have applications to the study of random number generators, to the analysis of algorithms in computational group theory, and to other parts of group theory. Section 2 describes a unified approach to answering such probability questions using cycle index generating functions. As an example of its power, it is proved independently in \[F1\] and \[W2\] that the $`n\mathrm{}`$ limit of answer to Question 3 is $`(1\frac{1}{q^5})/(1+\frac{1}{q^3})`$. There is (at present) no other method for deriving this result and generating functions give effective bounds on the convergence rate to the limit. Extensions of the cycle index method to the set of all matrices and to other finite classical groups are sketched.

Section 3 gives a purely probabilistic picture of what the conjugacy class of a random element of $`GL(n,q)`$ looks like. The main object of study is a probability measure $`M_{GL,u,q}`$ on the set of all partitions of all natural numbers. This measure is connected with the Hall-Littlewood symmetric functions. Exploiting this connection leads to several methods for growing random partitions distributed as $`M_{GL,u,q}`$ and gives insightful probabilistic proofs of group theoretic results. We hope to convince the reader that the interplay between probability and symmetric functions is beautiful and useful. A method is given for sampling from $`M_{GL,u,q}`$ conditioned to live on partitions of a fixed size (which amounts to studying Jordan form of unipotent elements) and for sampling from a $`q`$-analog of Plancherel measure (which is related to the longest increasing subsequence problem of random permutations).

Section 3 goes on to describe a probabilistic approach to $`M_{GL,u,q}`$ using Markov chains. This connection is quite surprising, and we indicate how it leads to a simple and motivated proof of the Rogers-Ramanujan identities. The measure $`M_{GL,u,q}`$ has analogs for the finite unitary, symplectic, and orthogonal groups. As this is somewhat technical these results are omitted and pointers to the literature are given. However we remark now that while the analogs of the symmetric function theory viewpoint are unclear for the finite symplectic and orthogonal groups, the connections with Markov chains carry over. Thus there is a coherent probabilistic picture of the conjugacy classes of the finite classical groups.

Section 4 surveys probabilistic aspects of conjugacy classes in $`T(n,q)`$, the group of $`n\times n`$ upper triangular matrices over the field $`F_q`$ with $`1`$’s along the main diagonal. Actually a simpler object is studied, namely the Jordan form of randomly chosen elements of $`T(n,q)`$. From work of Borodin and Kirillov, one can sample from the corresponding measures on partitions. We link their results with symmetric function theory and potential theory on Bratteli diagrams.

The field surveyed in this article is young and evolving. The applications to computational group theory call for extensions of probability estimates discussed in Section 2 to maximal subgroups of finite classical groups. It would be marvellous if the program surveyed here carries over; this happens for the finite affine groups \[F9\]. The first step is understanding conjugacy classes and partial results can be found in the thesis \[Mu\].

We close with a final motivation for the study of conjugacy classes of random matrices over finite fields. The past few years have seen an explosion of interest in eigenvalues of random matrices from compact Lie groups. For the unitary group $`U(n,C)`$ over the complex numbers, two matrices are in the same conjugacy class if and only if they have the same set of eigenvalues. Hence, at least in this case, which is related to the zeroes of the Riemann zeta function \[KeaSn\], the study of eigenvalues is the same as the study of conjugacy classes.

As complements to this article, the reader may enjoy the surveys \[Sh2\],\[Py1\],\[Py2\]. These articles discuss probabilistic and enumerative questions in group theory and have essentially no overlap with the program surveyed here.

## 2 Cycle Index Techniques

Before describing cycle index techniques for the finite classical groups, we mention that the cycle index techniques here are modelled on similar techniques for the study of conjugacy class functions on the symmetric groups. For a permutation $`\pi `$, let $`n_i(\pi )`$ be the number of length $`i`$ cycles of $`\pi `$. The cycle index of a subgroup $`G`$ of $`S_n`$ is defined as

$$\frac{1}{|G|}\underset{\pi G}{}\underset{i1}{}x_i^{n_i(\pi )}$$

and is called a cycle index because it stores information about the cycle structure of elements of $`G`$. Applications of the cycle index to graph theory and chemical compounds are exposited in \[PoRe\]. It is standard to refer to the generating function

$$1+\underset{n1}{}\frac{u^n}{n!}\underset{\pi S_n}{}\underset{i1}{}x_i^{n_i(\pi )}$$

as the cycle index or cycle index generating function of the symmetric groups. From the fact that there are $`\frac{n!}{_in_i!i^{n_i}}`$ elements in $`S_n`$ with $`n_i`$ cycles of length $`i`$, one deduces Polya’s result that this generating function is equal to $`_{m1}e^{\frac{x_mu^m}{m}}`$. This allows one to study conjugacy class functions of random permutations (e.g. number of fixed points, number of cycles, the order of a permutation, length of the longest cycle) by generating functions. We refer the reader to \[Ko\] for results in this direction using analysis and to \[ShLl\] for results about cycle structure proved by a probabilistic interpretation of the cycle index generating function.

Subsection 2.1 reviews the conjugacy classes of $`GL(n,q)`$ and then discusses cycles indices for $`GL(n,q)`$ and $`Mat(n,q)`$, the set of all $`n\times n`$ matrices with entries in the field of $`q`$ elements. Subsection 2.2 describes applications of cycle index techniques. Subsection 2.3 discusses generalizations of cycle indices to the finite classical groups.

It is necessary to recall some standard notation. Let $`\lambda `$ be a partition of some non-negative integer $`|\lambda |`$ into integer parts $`\lambda _1\lambda _2\mathrm{}0`$. We will also write $`\lambda n`$ if $`\lambda `$ is a partition of $`n`$. Let $`m_i(\lambda )`$ be the number of parts of $`\lambda `$ of size $`i`$, and let $`\lambda ^{}`$ be the partition dual to $`\lambda `$ in the sense that $`\lambda _i^{}=m_i(\lambda )+m_{i+1}(\lambda )+\mathrm{}`$. Let $`n(\lambda )`$ be the quantity $`_{i1}(i1)\lambda _i`$ and let $`(\frac{u}{q})_i`$ denote $`(1\frac{u}{q})\mathrm{}(1\frac{u}{q^i})`$.

### 2.1 The General Linear Groups

To begin we follow Kung \[Kun\] in defining a cycle index for $`GL(n,q)`$. First it is necessary to understand the conjugacy classes of $`GL(n,q)`$. As is explained in Chapter 6 of the textbook \[Her\], an element $`\alpha GL(n,q)`$ has its conjugacy class determined by its rational canonical form. This form corresponds to the following combinatorial data. To each monic non-constant irreducible polynomial $`\varphi `$ over $`F_q`$, associate a partition (perhaps the trivial partition) $`\lambda _\varphi `$ of some non-negative integer $`|\lambda _\varphi |`$. Let $`deg(\varphi )`$ denote the degree of $`\varphi `$. The only restrictions necessary for this data to represent a conjugacy class are that $`|\lambda _z|=0`$ and $`_\varphi |\lambda _\varphi |deg(\varphi )=n.`$

An explicit representative of this conjugacy class may be given as follows. Define the companion matrix $`C(\varphi )`$ of a polynomial $`\varphi (z)=z^{deg(\varphi )}+\alpha _{deg(\varphi )1}z^{deg(\varphi )1}+\mathrm{}+\alpha _1z+\alpha _0`$ to be:

$$\left(\begin{array}{ccccc}0& 1& 0& \mathrm{}& 0\\ 0& 0& 1& \mathrm{}& 0\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}\\ 0& 0& 0& \mathrm{}& 1\\ \alpha _0& \alpha _1& \mathrm{}& \mathrm{}& \alpha _{deg(\varphi )1}\end{array}\right)$$

Let $`\varphi _1,\mathrm{},\varphi _k`$ be the polynomials such that $`|\lambda _{\varphi _i}|>0`$. Denote the parts of $`\lambda _{\varphi _i}`$ by $`\lambda _{\varphi _i,1}\lambda _{\varphi _i,2}\mathrm{}`$. Then a matrix corresponding to the above conjugacy class data is

$$\left(\begin{array}{cccc}R_1& 0& 0& 0\\ 0& R_2& 0& 0\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}\\ 0& 0& 0& R_k\end{array}\right)$$

where $`R_i`$ is the matrix

$$\left(\begin{array}{ccc}C(\varphi _i^{\lambda _{\varphi _i,1}})& 0& 0\\ 0& C(\varphi _i^{\lambda _{\varphi _i,2}})& 0\\ 0& 0& \mathrm{}\end{array}\right)$$

For example, the identity matrix has $`\lambda _{z1}`$ equal to $`(1^n)`$ and all other $`\lambda _\varphi `$ equal to the emptyset. An elementary transvection with $`a0`$ in the $`(1,2)`$ position, ones on the diagonal and zeros elsewhere has $`\lambda _{z1}`$ equal to $`(2,1^{n2})`$ and all other $`\lambda _\varphi `$ equal to the emptyset. For a given matrix only finitely many $`\lambda _\varphi `$ are non-empty. Many algebraic properties of a matrix can be stated in terms of the data parameterizing its conjugacy class. For instance the characteristic polynomial of $`\alpha GL(n,q)`$ is equal to $`_\varphi \varphi ^{|\lambda _\varphi (\alpha )|}`$ and the minimal polynomial of $`\alpha `$ is equal to $`_\varphi \varphi ^{|\lambda _{\varphi ,1}(\alpha )|}`$. Furthermore $`\alpha `$ is semisimple (diagonalizable over the algebraic closure $`\overline{F_q}`$) precisely when all $`\lambda _\varphi (\alpha )`$ have largest part at most 1.

To define the cycle index for $`Z_{GL(n,q)}`$, let $`x_{\varphi ,\lambda }`$ be variables corresponding to pairs of polynomials and partitions. Define

$$Z_{GL(n,q)}=\frac{1}{|GL(n,q)|}\underset{\alpha GL(n,q)}{}\underset{\varphi :|\lambda _\varphi (\alpha )|>0}{}x_{\varphi ,\lambda _\varphi (\alpha )}.$$

Note that the coefficient of a monomial is the probability of belonging to the corresponding conjugacy class, and is therefore equal to one over the order of the centralizer of a representative. It is well known (e.g. easily deduced from page 181 of \[Mac\]) that one over the order of the centralizer of conjugacy class of $`GL(n,q)`$ corresponding to the data $`\{\lambda _\varphi \}`$ is

$$\frac{1}{_\varphi q^{deg(\varphi )_i(\lambda _{\varphi ,i}^{})^2}_{i1}(\frac{1}{q^{deg(\varphi )}})_{m_i(\lambda _\varphi )}}.$$

The formulas given for conjugacy class size in \[Kun\] and \[St1\] are written in different form; for the reader’s benefit they have been expressed here in the form most useful to us. It follows that

$$1+\underset{n=1}{\overset{\mathrm{}}{}}Z_{GL(n,q)}u^n=\underset{\varphi z}{}\left[1+\underset{n1}{}\underset{\lambda n}{}x_{\varphi ,\lambda }\frac{u^{ndeg(\varphi )}}{q^{deg(\varphi )_i(\lambda _i^{})^2}_{i1}\left(\frac{1}{q^{deg(\varphi )}}\right)_{m_i(\lambda _\varphi )}}\right].$$

This is called the cycle index generating function.

Let $`Mat(n,q)`$ be the set of all $`n\times n`$ matrices over the field $`F_q`$. Define

$$Z_{Mat(n,q)}=\frac{1}{|GL(n,q)|}\underset{\alpha Mat(n,q)}{}\underset{\varphi :|\lambda _\varphi (\alpha )|>0}{}x_{\varphi ,\lambda _\varphi (\alpha )}.$$

Analogous arguments \[St1\] show that

$$1+\underset{n=1}{\overset{\mathrm{}}{}}Z_{Mat(n,q)}u^n=\underset{\varphi }{}\left[1+\underset{n1}{}\underset{\lambda n}{}x_{\varphi ,\lambda }\frac{u^{ndeg(\varphi )}}{q^{deg(\varphi )_i(\lambda _i^{})^2}_{i1}\left(\frac{1}{q^{deg(\varphi )}}\right)_{m_i(\lambda _\varphi )}}\right].$$

This will be used in Subsection 2.2. Note that the denominator in $`Z_{Mat(n,q)}`$ is $`|GL(n,q)|`$, not $`|Mat(n,q)|`$, since the formula follows from a formula for the size of the orbits of $`GL(n,q)`$ acting on $`Mat(n,q)`$ by conjugation. This makes no essential difference for applications.

### 2.2 Applications

This subsection describes applications of cycle indices. The first example is treated in detail and results for the other examples are sketched.

Example 1: Cyclic and Separable Matrices

Recall that a matrix $`\alpha Mat(n,q)`$ operating on a vector space $`V`$ is called cyclic if there is a vector $`v_0V`$ such that $`v_0,v_0\alpha ,v_0\alpha ^2,\mathrm{}`$ span $`V`$. As is explained in \[NP2\], this is equivalent to the condition that the characteristic and minimal polynomials of $`\alpha `$ are equal.

The need to estimate the proportion of cyclic matrices arose from \[NP1\] in connection with analyzing the running time of an algorithm for deciding whether or not the group generated by a given set of matrices in $`GL(n,q)`$ contains the special linear group $`SL(n,q)`$. Cyclic matrices also arise in recent efforts to improve upon the MeatAxe algorithm for computing modular characters \[NP4\] and in Example 8 below. John Thompson has asked if every matrix is the product of a cyclic matrix and a permutation matrix, suggesting that the answer could have applications to finite projective planes.

Letting $`c_M(n,q)`$ be the proportion of cyclic elements of $`Mat(n,q)`$, the paper \[NP2\] proves that

$$\frac{1}{q^2(q+1)}<1c_M(n,q)<\frac{1}{(q^21)(q1)}.$$

The cycle index approach is also informative, yielding a formula for the $`n\mathrm{}`$ limit of $`C_M(n,q)`$, denoted by $`c_M(\mathrm{},q)`$, together with convergence rates. For the argument two lemmas are useful, as is some notation. Let $`N_d(q)`$ be the number of degree $`d`$ irreducible polynomials over the field $`F_q`$. In all that follows $`\varphi `$ will denote a monic irreducible polynomial over $`F_q`$. Given a power series $`f(u)`$, let $`[u^n]f(u)`$ denote the coefficient of $`u^n`$ in $`f(u)`$.

###### Lemma 1

$$\underset{\varphi }{}(1\frac{u^{deg(\varphi )}}{q^{deg(\varphi )}})=1u$$

Proof: Expanding $`\frac{1}{1\frac{u^{deg(\varphi )}}{q^{deg(\varphi )}}}`$ as a geometric series and using unique factorization in $`F_q[x]`$, one sees that the coefficient of $`u^d`$ in the reciprocal of the left hand side is $`\frac{1}{q^d}`$ times the number of monic polynomials of degree $`d`$, hence 1. Comparing with the reciprocal of the right hand side completes the proof. $`\mathrm{}`$

###### Lemma 2

If the Taylor series of $`f`$ around 0 converges at $`u=1`$, then

$$lim_n\mathrm{}[u^n]\frac{f(u)}{1u}=f(1).$$

Proof: Write the Taylor expansion $`f(u)=_{n=0}^{\mathrm{}}a_nu^n`$. Then observe that $`[u^n]\frac{f(u)}{1u}=_{i=0}^na_i`$. $`\mathrm{}`$

Theorem 1 calculates $`c_M(\mathrm{},q)`$.

###### Theorem 1

(\[F1\],\[W2\])

$$c_M(\mathrm{},q)=(1\frac{1}{q^5})\underset{r=3}{\overset{\mathrm{}}{}}(1\frac{1}{q^r})$$

Proof: Recall that $`\alpha `$ is cyclic precisely when its characteristic polynomial and minimal polynomials are equal. From Subsection 2.1, these polynomials are equal when all $`\lambda _\varphi `$ have at most one part. In the cycle index for $`Mat(n,q)`$ set $`x_{\varphi ,\lambda }=1`$ if $`\lambda `$ has at most 1 part and $`x_{\varphi ,\lambda }=0`$ otherwise. It follows that

$$c_M(n,q)=\frac{|GL(n,q)|}{q^{n^2}}[u^n]\underset{\varphi }{}(1+\underset{j=1}{\overset{\mathrm{}}{}}\frac{u^{jdeg(\varphi )}}{q^{(j1)deg(\varphi )}(q^{deg(\varphi )}1)}).$$

By Lemma 1 this equation can be rewritten as

$`c_M(n,q)`$ $`=`$ $`{\displaystyle \frac{|GL(n,q)|}{q^{n^2}}}[u^n]{\displaystyle \frac{_\varphi (1\frac{u^{deg(\varphi )}}{q^{deg(\varphi )}})(1+_{j=1}^{\mathrm{}}\frac{u^{jdeg(\varphi )}}{q^{(j1)deg(\varphi )}(q^{deg(\varphi )}1)})}{1u}}`$
$`=`$ $`{\displaystyle \frac{|GL(n,q)|}{q^{n^2}}}[u^n]{\displaystyle \frac{_\varphi (1+\frac{u^{deg(\varphi )}}{q^{deg(\varphi )}(q^{deg(\varphi )}1)})}{1u}}`$
$`=`$ $`{\displaystyle \frac{|GL(n,q)|}{q^{n^2}}}[u^n]{\displaystyle \frac{_{d1}(1+\frac{u^d}{q^d(q^d1)})^{N_d(q)}}{1u}}.`$
Recall that a product $`_{n=1}^{\mathrm{}}(1+a_n)`$ converges absolutely if the series $`_{n1}|a_n|`$ converges. Thus using the crude bound $`N_d(q)q^d`$

$$\underset{d1}{}(1+\frac{u^d}{q^d(q^d1)})^{N_d(q)}$$

is analytic in a disc of radius greater than $`1`$. Lemma 2 implies that

$`c_M(\mathrm{},q)`$ $`=`$ $`lim_n\mathrm{}{\displaystyle \frac{|GL(n,q)|}{q^{n^2}}}[u^n]{\displaystyle \frac{_{d1}(1+\frac{u^d}{q^d(q^d1)})^{N_d(q)}}{1u}}`$
$`=`$ $`{\displaystyle \underset{r=1}{\overset{\mathrm{}}{}}}(1{\displaystyle \frac{1}{q^r}}){\displaystyle \underset{d1}{}}(1+{\displaystyle \frac{1}{q^d(q^d1)}})^{N_d(q)}.`$
Applying Lemma 1 (with $`u=\frac{1}{q}`$, $`u=\frac{1}{q^2}`$ and then $`u=\frac{1}{q^5}`$) gives that

$`c_M(\mathrm{},q)`$ $`=`$ $`{\displaystyle \underset{r=3}{\overset{\mathrm{}}{}}}(1{\displaystyle \frac{1}{q^r}}){\displaystyle \underset{d1}{}}((1+{\displaystyle \frac{1}{q^d(q^d1)}})(1{\displaystyle \frac{1}{q^{2d}}})(1{\displaystyle \frac{1}{q^{3d}}}))^{N_d(q)}`$
$`=`$ $`{\displaystyle \underset{r=3}{\overset{\mathrm{}}{}}}(1{\displaystyle \frac{1}{q^r}}){\displaystyle \underset{d1}{}}(1{\displaystyle \frac{1}{q^{6d}}})^{N_d(q)}`$
$`=`$ $`(1{\displaystyle \frac{1}{q^5}}){\displaystyle \underset{r=3}{\overset{\mathrm{}}{}}}(1{\displaystyle \frac{1}{q^r}}).`$
$`\mathrm{}`$

The next challenge is to bound the convergence rate of $`c_M(n,q)`$ to $`c_{\mathrm{}}(n,q)`$. Wall \[W2\] found a strikingly simple way of doing this by relating the cycle index of cyclic matrices to the cycle index of the set of matrices whose characteristic polynomial is squarefree (these matrices are termed separable in \[NP2\]). To state the result, let $`s_M(n,q)`$ be the probability that an $`n\times n`$ matrix is separable. Next let $`C_M(u,q)`$ and $`S_M(u,q)`$ be the generating functions defined as

$$C_M(u,q)=1+\underset{n1}{}\frac{u^nq^{n^2}}{|GL(n,q)|}c_M(n,q)$$

$$S_M(u,q)=1+\underset{n1}{}\frac{u^nq^{n^2}}{|GL(n,q)|}s_M(n,q).$$

###### Lemma 3

(\[W2\])

$$(1u)C_M(u,q)=S_M(u/q,q).$$

Proof: The proof of Theorem 1 shows that

$$(1u)C_M(u,q)=\underset{d1}{}(1+\frac{u^d}{q^d(q^d1)})^{N_d(q)}.$$

A matrix is separable if and only if all $`\lambda _\varphi `$ have size $`0`$ or $`1`$. Hence

$$S_M(u,q)=\underset{d1}{}(1+\frac{u^d}{q^d1})^{N_d(q)}.$$

The result follows. $`\mathrm{}`$

###### Corollary 1

(\[W2\])

$$0<|c_M(n,q)c_M(\mathrm{},q)|<\frac{1}{q^{n+1}(11/q)}$$

Proof: Taking coefficients of $`u^{n+1}`$ on both sides of Lemma 3 gives the relation

$$c_M(n+1,q)c_M(n,q)=\frac{s_M(n+1,q)c_M(n,q)}{q^{n+1}}.$$

Since $`0|s_M(n+1,q)c_M(n,q)|1`$ for all $`n`$, it follows that

$$|c_M(n,q)c_M(\mathrm{},q)|\underset{i=n}{\overset{\mathrm{}}{}}|c_M(i+1,q)c_M(i,q)|\underset{i=n}{\overset{\mathrm{}}{}}\frac{1}{q^{i+1}},$$

as desired. $`\mathrm{}`$

Remarks:

1. As mentioned in the introduction, an argument similar to that of Theorem 1 shows that the $`n\mathrm{}`$ probability that an element of $`GL(n,q)`$ is cyclic is $`(1\frac{1}{q^5})/(1+\frac{1}{q^3})`$. For large $`q`$ this goes like $`11/q^3`$. The reason for this is a result of Steinberg \[Stei\] stating that the set of non-regular elements in an algebraic group has co-dimension 3. In type $`A`$, regular (i.e. centralizer of minimum dimension) and cyclic elements coincide, but not always. For more discussion on this point, see \[NP2\], \[FNP\].
2. The generating functions $`S_M(u,q)`$ and $`C_M(u,q)`$ have intriguing analytical properties. It is proved in \[W2\] that

$$S_M(u,q)=\frac{_{d=1}^{\mathrm{}}(1\frac{u^d(u^d1)}{q^d(q^d1)})^{N_d(q)}}{1u}.$$

Thus $`S_M(u,q)`$ has a pole at 1 and $`S_M(u,q)\frac{1}{1u}`$ can be analytically extended to the circle of radius $`q`$. Analogous properties hold for $`C_M(u,q)`$ by means of Lemma 3.
3. The limits $`s_M(\mathrm{},q)`$ and $`s_{GL}(\mathrm{},q)`$ are in \[F1\],\[W2\]. Bounding the rate of convergence of $`s_M(n,q)`$ to $`s_M(\mathrm{},q)`$ leads to interesting number theory. Let $`p(d)`$ be the number of partitions of $`d`$ and let $`p_2(d)=_{i=0}^dp(d)`$. It is proved in \[W2\] that

$$|\frac{s_M(n,q)q^{n^2}}{|GL(n,q)|}1|\underset{d=n+1}{\overset{\mathrm{}}{}}(p_2(d)+qp(d2))q^d\frac{1}{3}(\frac{4q+27}{2q3})(\frac{2}{3}q)^n.$$
4. Lehrer \[Leh\] expresses $`s_M(n,q)`$ and $`s_{GL}(n,q)`$ as inner products of characters in the symmetric group and proves a stability result about their expansions in power of $`q^1`$. See also \[W2\] and \[LehSe\].
5. The results of \[F2\] and \[W2\] surveyed above are extended to the finite classical groups in \[FNP\]. The paper \[FlJ\] gives (intractable) formulas for the chance of being separable in groups such as $`SL(n,q)`$ (i.e. semisimple and simply connected).

Example 2: Eigenvalue free matrices

The paper \[NP3\] studies eigenvalues free matrices (i.e. matrices without fixed lines) over finite fields as a step in obtaining estimates of cyclic probabilities in orthogonal groups \[NP5\]. It is interesting that the study of eigenvalue free matrices was one of the motivations for the original papers \[Kun\],\[St1\], the latter of which proves that the $`n,q\mathrm{}`$ limit of the chance that an element of $`GL(n,q)`$ has no eigenvalues is $`\frac{1}{e}`$.

The $`n\mathrm{}`$ probability that a random element of $`S_n`$ has no fixed points is also $`\frac{1}{e}`$. This is not coincidence; in general the $`q\mathrm{}`$ limit of the chance that the characteristic polynomial of a random element of $`Mat(n,q)`$ factors into $`n_i`$ degree $`i`$ irreducible factors is the same as the probability that an element of $`S_n`$ factors into $`n_i`$ cycles of degree $`i`$. This is proved at the end of \[St1\] and is extended to finite Lie groups in \[F1\] using the combinatorics of maximal tori. There is another interesting line of argument which should be mentioned. It is easy to see from the cycle index that the factorization type of the characteristic polynomial of a random element of $`Mat(n,q)`$ and the factorization type of a random degree $`n`$ polynomial over $`F_q`$ have the same distribution as $`q\mathrm{}`$. Now the factorization type of a random degree $`n`$ polynomial over $`F_q`$ has same distribution as the cycle type of a random permutation distributed as a $`q`$-shuffle on $`n`$ cards \[DiaMcPi\], and as $`q\mathrm{}`$ a $`q`$-shuffle converges to a random permutation. The connection of Lie theory with card shuffling may seem adhoc, but is really the tip of a deep iceberg \[F10\].

Example 3: Characteristic polynomials

The previous example is a special case of the problem of studying the degrees of the factors of the characteristic polynomial of a random matrix. Many results in this direction (all proved used cycle indices) can be found in Stong’s paper \[St1\]. Hansen and Schmutz \[HSchm\] use cycle index manipulations to prove that if one ignores factors of small degree, then the factorization type of the characteristic polynomial of a random element of $`GL(n,q)`$ is close to the factorization type of a random degree $`n`$ polynomial over $`F_q`$. More precisely, let $`A_{n,l}`$ be the set of sequences $`(\alpha _{l+1},\mathrm{},\alpha _n)`$ where $`\alpha _i`$ is the number of degree $`i`$ factors of a random polynomial chosen from some measure. Let $`Q_n^{(1)}`$ be the measure on polynomials arising from characteristic polynomials of random elements of $`GL(n,q)`$ and let $`Q_n^{(2)}`$ be the measure arising from choosing a degree $`n`$ polynomial over $`F_q`$ uniformly at random. They prove

###### Theorem 2

(\[HSchm\]) There exists constants $`c_1,c_2`$ such that for all $`l`$ with $`c_1log(n)ln`$ and $`BN^{nl}`$,

$$|Q_n^{(1)}(A_n(B))Q_n^{(2)}(A_n(B))|<c_2/l.$$

The final section of their paper uses this principle to prove results about characteristic polynomials of random matrices using known results about random polynomials. A useful reference on the distribution of degrees of random polynomials over finite fields is \[ArBarT\].

Example 4: Generating transvections

Recall that the motivation behind Example 1 was a group recognition problem, i.e. trying to determine whether or not the group generated by a given set $`X`$ of matrices in $`GL(n,q)`$ contains the special general linear group $`SL(n,q)`$. However the problem still remains of making the recognition algorithm constructive. For instance if the group generated by $`X`$ is $`GL(n,q)`$ it would be desirable to write any element of $`GL(n,q)`$ as a word in $`X`$.

The paper \[CeLg\] proposes such a constructive recognition algorithm. An essential step involves constructing a transvection, that is a non-identity element of $`SL(n,q)`$ which has an $`n1`$ dimensional fixed space. This in turn is done in two steps. First, find an element $`\alpha `$ of $`GL(n,q)`$ conjugate to diag$`(C((z\tau )^2),R)`$ where $`C`$ is the companion matrix as in Subsection 2.1 and $`R`$ is semisimple without $`\tau `$ as an eigenvalue. Second, one checks that raising $`\alpha `$ to the least common multiple of the orders of $`\tau `$ and $`R`$ gives a transvection.

Thus it necessary to bound the number of feasible $`\alpha `$ in the first step. Such $`\alpha `$ have conjugacy class data $`\lambda _{z\tau }=(2)`$ and all other $`\lambda _\varphi `$ have largest part at most 1. The cycle index approach gives bounds improving on those in \[CeLg\]; see \[FNP\] for the details.

Example 5: Semisimple matrices

A fundamental problem in computational group theory is to construct an element of order $`p`$. Given a group element $`g`$ with order a multiple of $`p`$, this can be done by raising $`g`$ to an appropriate power. It is proved in \[IsKanSp\] that if $`G`$ is a permutation group of degree $`n`$ with order divisible by $`p`$, then the probability that a random element of $`G`$ has order divisible by $`p`$ is at least $`\frac{1}{n}`$.

Their proof reduces the assertion to simple groups and then uses the classification of simple groups. Let us consider the group $`GL(n,q)`$, which is close enough to simple to be useful for the applications at hand. When $`p`$ is the characteristic of the field of definition of $`GL(n,q)`$, an element has order prime to $`p`$ precisely when it is semisimple. Thus the problem is to study the probability that an element of $`GL(n,q)`$ is semisimple. The paper \[GuLub\] shows that if $`G`$ is a simple Chevalley group, then the probability of not being semisimple is at most $`3/(q1)+2/(q1)^2`$ and thus at most $`c/q`$ for some constant $`c`$ as conjectured by Kantor.

As mentioned earlier, a matrix $`\alpha `$ is semisimple if and only if all $`\lambda _\varphi (\alpha )`$ have largest part size at most 1. Stong \[St1\] used cycle indices to obtain crude asymptotic bounds for the probability that an element of $`GL(n,q)`$ is semisimple. The thesis \[F1\] used the Rogers-Ramanujan identities to prove that the $`n\mathrm{}`$ probability that an element of $`GL(n,q)`$ is semisimple is

$$\underset{\genfrac{}{}{0pt}{}{r=1}{r=0,\pm 2(mod5)}}{\overset{\mathrm{}}{}}\frac{(1\frac{1}{q^{r1}})}{(1\frac{1}{q^r})}.$$

The paper \[FNP\] gives effective bounds for finite $`n`$.

Example 6: Order of a matrix

A natural problem is to study the order of a random matrix. This has been done in \[St2\] and \[Schm\]; see also the remarks in Subsection 3.3 and the very preliminary calculations for other classical groups in \[F1\]. Shalev \[Sh1\] uses facts about the distribution of the order of a random matrix together with Aschbacher’s study of maximal subgroups of classical groups \[As\] as key tools in studying the probability that a random element of $`GL(n,q)`$ belongs to an irreducible subgroup of $`GL(n,q)`$ that does not contain $`SL(n,q)`$. As explained in \[Sh1\] this has a number of appications; for instance it leads to a proof that if $`x`$ is any non-trivial element of $`PSL(n,q)`$ then the probability that $`x`$ and a randomly chosen element $`y`$ generate $`PSL(n,q)`$ tends to $`1`$ as $`q\mathrm{}`$. Shalev \[Sh1\] asks for extensions of these results to other finite classical groups.

It is also useful to count elements of given orders (e.g. $`2`$ or $`3`$) in classical groups and their maximal subgroups. The recent paper \[CTY\] uses cycle indices to perform such enumerations. One motivation for such enumerations is the study of finite simple quotients of $`PSL(2,Z)`$; a group $`G`$ is a quotient of $`PSL(2,Z)`$ if and only if $`G=<x,y>`$ with $`x^2=y^3=1`$. For further discussion, see \[Sh2\].

Example 7: Random number generators

We follow \[Mar\],\[MarTs\] in indicating the relevance of random matrix theory to the study of random number generators. Suppose one wants to test a mechanism for generating a random integer between $`0`$ and $`2^{33}1`$. In base $`2`$ these are length $`33`$ binary vectors. Generating say $`n`$ of these and listing them gives an $`n\times 33`$ matrix. If the random generator were perfect, the arising matrix would be random. One could choose a statistic such as the rank of a matrix and compare the generation method with theory. They report that shift-register generators will fail such tests but that congruential generators usually pass. It would be interesting to see how various random number generators perform when tested using other conjugacy class functions of random matrices.

Diaconis and Graham \[DiaGr\] analyze random walks of the form $`X_n=AX_{n1}+ϵ_n`$ where $`X_i`$ is a length $`d`$ $`01`$ vector, $`A`$ is an element of $`GL(n,2)`$, and $`ϵ_n`$ is a random vector of disturbance terms. For more general $`A`$ (in $`GL(n,q)`$) this includes the problem of running a psuedo-random number generator with recurrence $`Y_n=a_1Y_{n1}+\mathrm{}+a_dY_{nd}+ϵ_n`$ with $`Y_iF_q`$. They show that the rational canonical form of $`A`$ is related in a subtle way to the convergence rate of the walk. It would be interesting to understand what happens when $`A`$ is a random matrix.

Example 8: Product replacement algorithm

In recent years finite group theory has become much more computational. Given a generating set $`S`$ of a finite group $`G`$, it is natural to seek random elements of $`G`$. One approach, implemented in the computer systems GAP and MAGMA, is the product replacement algorithm \[CeLgMuNiOb\]. Fixing $`G`$ and some $`k`$, one performs a random walk on $`k`$-tuples $`(g_1,\mathrm{},g_k)`$ of elements of $`G`$ which generate the group. The walk proceeds by picking an ordered pair $`(i,j)`$ with $`1ijn`$ uniformly at random and applying one of the following four operations with equal probability:

$$R_{i,j}^\pm :(g_1,\mathrm{},g_i,\mathrm{},g_k)(g_1,\mathrm{},g_ig_j^\pm ,\mathrm{},g_k)$$

$$L_{i,j}^\pm :(g_1,\mathrm{},g_i,\mathrm{},g_k)(g_1,\mathrm{},g_j^\pm g_i,\mathrm{},g_k).$$

These moves map generating $`k`$-tuples to generating $`k`$-tuples. One starts from any generating $`k`$-tuple, applies the algorithm for $`r`$ steps, and then outputs a random entry of the resulting $`k`$-tuple (i.e. a group element).

The product replacement algorithm has superb practical performance (often converging more rapidly than random walk on the Cayley graph), in spite of the theoretical defects that a random entry of a random generating $`k`$-tuple does not have the same distribution as a random element of $`G`$, and that the convergence rate of the chain on $`k`$-tuples to its stationary distribution is unknown. The paper \[CeLgMuNiOb\], aware of these issues, tests the algorithm against theory, using conjugacy class statistics such as the order of an element, the number of factors of the characteristic polynomial of a random matrix, the degree of the largest irreducible factor of the characteristic polynomial of a random matrix, and the proportion of cyclic matrices in the finite classical groups. In short, understanding properties of random matrices is crucial to their analysis.

A recent effort to understand the performance of the product replacement algorithm uses Kazhdan’s property (T) from the representation theory of Lie groups \[LubPa\]; the paper \[Pa\] is a useful survey. Much remains to be done.

Example 9: Running times of algorithms

One of the main approaches to computing determinants and permanents of integer matrices involves doing the computations for reductions mod prime powers. Section 4.6.4 of \[Kn\] gives a detailed discussion with references to literature on upper bounds of running times. If one believes that typical matrices one encounters in the real world are like random matrices, this motivates studying random matrices over finite fields. In fact von Neumann’s interest in eigenvalues of random matrices with independent normal entries arose from the same heuristic applied to questions in numerical analysis (the introduction of \[E\] gives further discussion of this point).

Examples of algorithms in which properties of random matrices were really needed to bound running times include recognizing when a group generated by a set of matrices contains $`SL(n,q)`$ \[NP1\] and the MeatAxe algorithm for computing modular characters \[NP4\].

Example 10: Isometry classes of linear codes

Fripertinger \[Frip1\], \[Frip2\] considers cycle indices (in the permutation sense) of matrix groups acting on lines. His interest was in understanding properties of random isometry classes of linear codes–a harder problem than understanding random linear codes. The cycle indices he obtains seem quite intractable for theorem proving, but are useful in conjunction with computers. He also gives references to the switching function literature.

Curiously, understanding the permutation action of random matrices of lines comes up in another context. Wieand \[Wi\] has shown that the eigenvalues of random permutation matrices possess a structure similar to the eigenvalues of matrices from compact Lie groups. Persi Diaconis has suggested that the eigenvalues of high dimensional representations of finite groups of Lie type (such as the permutation action on lines) may possess similar structure; see \[F5\] for more in this direction.

### 2.3 Generalization to the Classical Groups

This subsection will focus on the finite unitary groups, with remarks about symplectic and orthogonal groups at the end. These cycle indices were derived in \[F1\],\[F2\] and were applied to the problem of estimating proportions of cyclic, separable, and semisimple matrices (these terms were defined in Subsection 2.2) in \[FNP\].

The unitary group $`U(n,q)`$ can be defined as the subgroup of $`GL(n,q^2)`$ preserving a non-degenerate skew-linear form. Recall that a skew-linear form on an $`n`$ dimensional vector space $`V`$ over $`F_{q^2}`$ is a bilinear map $`<,>:V\times VF_{q^2}`$ such that $`<\stackrel{}{x},\stackrel{}{y}>=<\stackrel{}{y},\stackrel{}{x}>^q`$ (raising to the $`q`$th power is an involution in a field of order $`q^2`$). One such form is given by $`<\stackrel{}{x},\stackrel{}{y}>=_{i=1}^nx_iy_i^q`$. Any two non-degenerate skew-linear forms are equivalent, so that $`U(n,q)`$ is unique up to isomorphism.

Wall \[W1\] parametrized the conjugacy classes of the finite unitary groups and computed their sizes. To describe his result, an involution on polynomials with non-zero constant term is needed. Given a polynomial $`\varphi `$ with coefficients in $`F_{q^2}`$ and non vanishing constant term, define a polynomial $`\stackrel{~}{\varphi }`$ by:

$$\stackrel{~}{\varphi }=\frac{z^{deg(\varphi )}\varphi ^q(\frac{1}{z})}{[\varphi (0)]^q}$$

where $`\varphi ^q`$ raises each coefficient of $`\varphi `$ to the $`q`$th power. Writing this out, a polynomial $`\varphi (z)=z^{deg(\varphi )}+\alpha _{deg(\varphi )1}z^{deg(\varphi )1}+\mathrm{}+\alpha _1z+\alpha _0`$ with $`\alpha _00`$ is sent to $`\stackrel{~}{\varphi }(z)=z^{deg(\varphi )}+(\frac{\alpha _1}{\alpha _0})^qz^{deg(\varphi )1}+\mathrm{}+(\frac{\alpha _{deg(\varphi )1}}{\alpha _0})^qz+(\frac{1}{\alpha _0})^q`$. An element $`\alpha U(n,q)`$ associates to each monic, non-constant, irreducible polynomial $`\varphi `$ over $`F_{q^2}`$ a partition $`\lambda _\varphi `$ of some non-negative integer $`|\lambda _\varphi |`$ by means of rational canonical form. The restrictions necessary for the data $`\lambda _\varphi `$ to represent a conjugacy class are that $`|\lambda _z|=0`$, $`\lambda _\varphi =\lambda _{\stackrel{~}{\varphi }}`$, and that $`_\varphi |\lambda _\varphi |deg(\varphi )=n.`$

Using formulas for conjugacy class sizes from \[W1\] together with some combinatorial manipulations, the following unitary group cycle index generating function was derived in \[F1\]. The products in the theorem are as always over monic irreducible polynomials.

###### Theorem 3

$`1+{\displaystyle \underset{n=1}{\overset{\mathrm{}}{}}}{\displaystyle \frac{u^n}{|U(n,q)|}}{\displaystyle \underset{\alpha U(n,q)}{}}{\displaystyle \underset{\varphi :|\lambda _\varphi (\alpha )|>0}{}}x_{\varphi ,\lambda _\varphi (\alpha )}`$
$`=`$ $`{\displaystyle \underset{\varphi z,\varphi =\stackrel{~}{\varphi }}{}}\left[1+{\displaystyle \underset{n1}{}}{\displaystyle \underset{\lambda n}{}}x_{\varphi ,\lambda }{\displaystyle \frac{(u)^{ndeg(\varphi )}}{(q)^{deg(\varphi )_i(\lambda _i^{})^2}_{i1}\left(\frac{1}{(q)^{deg(\varphi )}}\right)_{m_i(\lambda )}}}\right]`$
$`{\displaystyle \underset{\{\varphi ,\stackrel{~}{\varphi }\},\varphi \stackrel{~}{\varphi }}{}}[1+{\displaystyle \underset{n1}{}}{\displaystyle \underset{\lambda n}{}}x_{\varphi ,\lambda }x_{\stackrel{~}{\varphi },\lambda }{\displaystyle \frac{u^{2ndeg(\varphi )}}{q^{2deg(\varphi )_i(\lambda _i^{})^2}_{i1}\left(\frac{1}{q^{2deg(\varphi )}}\right)_{m_i(\lambda )}}}]`$
One interesting theoretical result concerning the cycle index of $`U(n,q)`$ is the following functional equation. Letting $`C_{GL}(u,q)`$ and $`C_U(u,q)`$ be the cycle index generating functions for cyclic matrices in the general linear and unitary groups respectively, the functional equation states that

$$C_{GL}(u,q)C_U(u,q)=C_{GL}(u^2,q^2).$$

The paper \[FNP\] proves that this relation holds whenever the condition on the partitions $`\lambda _\varphi `$ is independent of the polynomial $`\varphi `$. In the current example, a matrix is cyclic if and only if all $`\lambda _\varphi `$ have at most one row. This condition is independent of $`\varphi `$.

Cycle indices for the symplectic and orthogonal groups are a bit trickier to establish from Wall’s formulas. To the treatment in \[F1\],\[F2\] we add a remark which should be very helpful to anyone trying to use those cycle indices. The paper \[F2\] only wrote out an explicit formula for the cycle index for the sum of $`+`$,$``$ type orthogonal groups. To solve for an individual orthogonal group, it is necessary to average that formula with a formula for the difference of $`+`$,$``$ type orthogonal groups (this procedure is carried out in a special case in \[FNP\]). In general, the formula for the difference of orthogonal groups is obtained from the formula for the sum of orthogonal groups as follows. First, for the polynomials $`z\pm 1`$, replace terms corresponding to partitions with an odd number of odd parts by their negatives. Second, for polynomials invariant under $`\stackrel{~}{}`$, replace terms corresponding to partitions of odd size by their negatives.

### 2.4 Limitations and Other Methods

Cycle index techniques, while very useful, also have their limitations and are not always the best way to proceed, as the following examples demonstrate.

Example 1: Primitive prime divisor elements

For integers $`b,e>1`$ a primitive prime divisor of $`b^e1`$ is a prime dividing $`b^e1`$ but not dividing $`b^i1`$ for any $`i`$ with $`1i<e`$. An element of $`GL(n,q)`$ is called a primitive prime divisor (ppd) element if its order is divisible by a primitive prime divisor of $`q^e1`$ with $`n/2<en`$. The analysis in \[NiP\] derives elegant bounds on the proportions of ppd elements in the finite classical groups and applies them to the group recognition problem for classical groups over finite fields (determining when a group generated by a set of matrices contains $`SL(n,q)`$). We do not see how to get comparable bounds using generating function techniques.

Example 2: Proportions of semisimple elements in exceptional groups

Although Example 5 of Section 2.2 was estimating proportions of semisimple matrices, this was only for the finite classical groups, where the index $`n`$ can take an infinite number of values. Cycle indices don’t seem useful unless there is a tower of groups of varying rank available.

Fortunately the computer package CHEVIE permits calculations precisely in finite rank cases such as the exceptional groups. Indeed this is how \[GuLub\] obtained estimates of the proportions of semisimple elements in the exceptional groups.

Example 3: Non-uniform distributions on matrices

The cycle indices give useful information about conjugacy class functions when the matrix is chosen uniformly at random. However there are other distributions on matrices which one could study and for which cycle index methods (at present) can not be applied.

One example is random $`n\times n`$ matrices where the matrix entries are chosen independently according to a given probability distribution on $`F_q`$. Charlap, Rees, and Robbins \[ChReRo\] show that if the probability distribution is not concentrated on any proper affine subspace of $`F_q`$, then as $`n\mathrm{}`$ the probability that the matrix is invertible is the same as for a uniform matrix. They use Moebius inversion on the lattice of subspaces of an $`n`$ dimensional vector space and the Poisson summation formula. Is the same true for other natural conjugacy class functions? We expect that the answer is yes, which can be regarded as a type of “universality” result for the asymptotic description of random elements of $`GL(n,q)`$ to be given in Subsection 3.1. Analogous universality results are known for matrices with complex entries \[So\]. For further information on the rank of random $`01`$ matrices, see \[BKW\] for sparse matrices, \[Bo\] for a survey of results on the rank over the real numbers, and also the discussion of work of Rudvalis and Shinoda in Subsection 3.2.

It is conceivable that cycle index techniques will be able to handle certain natural non-uniform distributions on $`GL(n,q)`$. This happens for the symmetric groups, where natural non-uniform measures such as performing a $`q`$-riffle shuffle on a deck of cards has a useful cycle index \[DiaMcPi\],\[F10\].

## 3 Running Example: General Linear Groups

The purpose of this section is to give different ways of understanding the conjugacy class of a random element of $`GL(n,q)`$. The analogous theory for other finite classical groups is mentioned in passing but is not treated in detail as many of the main ideas can be communicated using $`GL(n,q)`$. Subsection 3.1 will show how this leads naturally to the study of certain probability measures $`M_{GL,u,q}`$ on the set of all partitions of all natural numbers. Connections with symmetric function theory lead to several ways of growing random partitions distributed according to $`M_{GL,u,q}`$. One consequence is a motivated proof of the Rogers-Ramanujan identities.

### 3.1 Measures on Partitions

The goal is to obtain a probabilistic description of the conjugacy class of a random element of $`GL(n,q)`$. The ideas are based on \[F1\]. For this the following definition will be fundamental.

Definition: The measure $`M_{GL,u,q}`$ on the set of all partitions of all natural numbers is defined by

$$M_{GL,u,q}(\lambda )=\underset{r=1}{\overset{\mathrm{}}{}}(1\frac{u}{q^r})\frac{u^{|\lambda |}}{q^{_i(\lambda _i^{})^2}_i(\frac{1}{q})_{m_i(\lambda )}}.$$

The motivation for this definition will be clear from Theorem 4. The measure $`M_{GL,u,q}`$, while seemingly complicated, does have some nice combinatorial properties. For instance for partitions of a fixed size, this measure respects the dominance order on partitions (in this partial order $`\lambda \mu `$ if and only if $`\lambda _1+\mathrm{}\lambda _i\mu _1+\mathrm{}+\mu _i`$ for all $`i1`$). In work with Bob Guralnick we actually needed this property.

Lemma 4 proves that for $`q>1`$ and $`0<u<1`$, the measure $`M_{GL,u,q}`$ is in fact a probability measure. There are at least three other proofs of this fact: an argument using $`q`$ series, specializing an identity about Hall-Littlewood polynomials, or a slick argument using Markov chains and an identity of Cauchy. This third argument will be given in Subsection 3.4.

###### Lemma 4

If $`q>1`$ and $`0<u<1`$, then $`M_{GL,u,q}`$ defines a probability measure.

Proof: $`M_{GL,u,q}`$ is clearly non-negative when $`q>1`$ and $`0<u<1`$. Stong \[St1\] established an equation which is equivalent to the sought identity

$$\underset{\lambda }{}\frac{u^{|\lambda |}}{q^{_i(\lambda _i^{})^2}_i(\frac{1}{q})_{m_i(\lambda )}}=\underset{r=1}{\overset{\mathrm{}}{}}(\frac{1}{1\frac{u}{q^r}}).$$

As some effort is required to see this equivalence, we derive the identity directly using Stong’s line of reasoning.

First observe that unipotent elements of $`GL(n,q)`$ corresponding to nilpotent $`n\times n`$ matrices (subtract the identity matrix), and that the number of nilpotent $`n\times n`$ matrices is $`q^{n(n1)}`$ by the Fine-Herstein theorem \[FeinHer\]. The number of unipotent elements in $`GL(n,q)`$ can be evaluated in another way using the cycle index of the general linear groups. Namely set $`x_{\varphi ,\lambda }=1`$ if $`\varphi =z1`$ and set $`x_{\varphi ,\lambda }=0`$ otherwise. One concludes that

$$\underset{\lambda n}{}\frac{1}{q^{_i(\lambda _i^{})^2}_i(\frac{1}{q})_{m_i(\lambda )}}=\frac{q^{n(n1)}}{|GL(n,q)|}.$$

Now multiply both sides by $`u^n`$, sum in $`n`$, and apply Euler’s identity

$$\underset{n=0}{\overset{\mathrm{}}{}}\frac{u^nq^{\left(\genfrac{}{}{0pt}{}{n}{2}\right)}}{(q^n1)\mathrm{}(q1)}=\underset{r=1}{\overset{\mathrm{}}{}}(\frac{1}{1\frac{u}{q^r}}).$$

$`\mathrm{}`$

The measure $`M_{GL,u,q}`$ is a fundamental object for understanding the probability theory of conjugacy classes of $`GL(n,q)`$. This emerges from Theorem 4.

###### Theorem 4

1. Fix $`u`$ with $`0<u<1`$. Then choose a random natural number $`N`$ with probability of getting $`n`$ equal to $`(1u)u^n`$. Choose $`\alpha `$ uniformly in $`GL(N,q)`$. Then as $`\varphi `$ varies, the random partitions $`\lambda _\varphi (\alpha )`$ are independent random variables, with $`\lambda _\varphi `$ distributed according to the measure $`M_{GL,u^{deg(\varphi )},q^{deg(\varphi )}}`$.
2. Choose $`\alpha `$ uniformly in $`GL(n,q)`$. Then as $`n\mathrm{}`$, the random partitions $`\lambda _\varphi (\alpha )`$ converge in finite dimensional distribution to independent random variables, with $`\lambda _\varphi `$ distributed according to the measure $`M_{GL,1,q^{deg(\varphi )}}`$.

Proof: Recall the cycle index factorization

$$1+\underset{n=1}{\overset{\mathrm{}}{}}Z_{GL(n,q)}u^n=\underset{\varphi z}{}\left[1+\underset{n1}{}\underset{\lambda n}{}x_{\varphi ,\lambda }\frac{u^{ndeg(\varphi )}}{_\varphi q^{deg(\varphi )_i(\lambda _i^{})^2}_{i1}(\frac{1}{q^{deg(\varphi )}})_{m_i}}\right].$$

Setting all $`x_{\varphi ,\lambda }`$ equal to $`1`$ and using Lemma 4 shows that

$$\frac{1}{1u}=\underset{\varphi z}{}\underset{r=1}{\overset{\mathrm{}}{}}(\frac{1}{1\frac{u^{deg(\varphi )}}{q^{rdeg(\varphi )}}}).$$

Taking reciprocals and multiplying by the cycle index factorization shows that

$$(1u)+\underset{n=1}{\overset{\mathrm{}}{}}Z_{GL(n,q)}(1u)u^n=\underset{\varphi z}{}\left(M_{GL,u^{deg(\varphi )},q^{deg(\varphi )}}(\mathrm{})+\underset{\lambda :|\lambda |>0}{}M_{GL,u^{deg(\varphi )},q^{deg(\varphi )}}(\lambda )x_{\varphi ,\lambda }\right).$$

This proves the first assertion of the theorem. For the second assertion, use Lemma 2 from Subsection 2.2. $`\mathrm{}`$

Remarks:

1. Theorem 4 has an analog for the symmetric groups \[ShLl\]. The statement is as follows. Fix $`u`$ with $`0<u<1`$. Then choose a random natural number $`N`$ with probability of getting $`n`$ equal to $`(1u)u^n`$. Choose $`\pi `$ uniformly in $`S_N`$. Letting $`n_i`$ be the number of $`i`$-cycles of $`\pi `$, the random variables $`n_i`$ are independent, with $`n_i`$ distributed as a Poisson with mean $`\frac{u^i}{i}`$. Furthermore if one chooses $`\pi `$ uniformly in $`S_n`$ and lets $`n\mathrm{}`$, then the random variables $`n_i`$ are independent random variables, with $`n_i`$ distributed as a Poisson$`(\frac{1}{i})`$.
2. The idea of performing an auxiliary randomization of $`n`$ is a mainstay of statistical mechanics, known as the grand canonical ensemble. For a clear discussion see Sections 1.7, 1.9, and 4.3 of \[Fey\].

### 3.2 Symmetric Function Theory and Sampling Algorithms

The aim of this subsection is two-fold. First, the measures $`M_{GL,u,q}`$ are connected with the Hall-Littlewood symmetric functions. Then we indicate how this connection can be exploited to give probabilistic methods for growing random partitions distributed as $`M_{GL,u,q}`$. The purpose is not to drown the reader in formulas, but rather to show that the connection between symmetric functions and probability is deep, beautiful, and useful in both directions. The results on this section are based on \[F1\] and \[F3\], except for the remark on how to make the algorithms terminate in finite time, which is joint with Mark Huber.

To begin, we recall the Hall-Littlewood symmetric functions, which arise in many parts of mathematics: enumeration of $`p`$ groups, representation theory of $`GL(n,q)`$, and counting automorphisms of modules. The basic references for Hall-Littlewood polynomials $`P_\lambda `$ is Chapter 3 of \[Mac\], which offers the following definition

$$P_\lambda (x_1,\mathrm{},x_n;t)=\left[\frac{1}{_{i0}_{r=1}^{m_i(\lambda )}\frac{1t^r}{1t}}\right]\underset{wS_n}{}w\left(x_1^{\lambda _1}\mathrm{}x_n^{\lambda _n}\underset{i<j}{}\frac{x_itx_j}{x_ix_j}\right).$$

Here $`w`$ is a permutation acting on the $`x`$-variables by sending $`x_i`$ to $`x_{w(i)}`$. Recall that $`m_i(\lambda )`$ is the number of parts of $`\lambda `$ of size $`i`$. At first glance it is not obvious that these are polynomials, but the denominators cancel out after the symmetrization. The Hall-Littlewood polynomials interpolate between the Schur functions ($`t=0`$) and the monomial symmetric functions ($`t=1`$).

Theorem 5 relates the measures $`M_{GL,u,q}`$ to the Hall-Littlewood polynomials. Recall that $`n(\lambda )=_i(i1)\lambda _i=_i\left(\genfrac{}{}{0pt}{}{\lambda _i^{}}{2}\right)`$.

###### Theorem 5

$$M_{GL,u,q}(\lambda )=\underset{i=1}{\overset{\mathrm{}}{}}(1\frac{u}{q^i})\frac{P_\lambda (\frac{u}{q},\frac{u}{q^2},\mathrm{};\frac{1}{q})}{q^{n(\lambda )}}$$

Proof: From the above formula for Hall-Littlewood polynomials, it is clear that the only surviving term in the specialization $`P_\lambda (\frac{u}{q},\frac{u}{q^2},\mathrm{};\frac{1}{q})`$ is the term when $`w`$ is the identity. The rest is a simple combinatorial verification. (Alternatively, one could use “principal specialization” formulas for Macdonald polynomials on page 337 of \[Mac\]). $`\mathrm{}`$

Remark: The paper \[F3\] gives symmetric function theoretic generalizations of the measure $`M_{GL,u,q}`$ on partitions. In the case of Schur functions $`s_\lambda `$, this measure depends on two infinite sets of variables $`x_i,y_i`$ and assigns a partition $`\lambda `$ mass equal to $`s_\lambda (x_i)s_\lambda (y_i)_{i,j}(1x_iy_j)`$. It is remarkable that precisely this measure arose in work of the random matrix community relating the distribution of the lengths of increasing subsequences of random permutations to the distribution of eigenvalues of random GUE matrices (these matrices have complex entries). To elaborate, the Robinson-Schensted-Knuth correspondence associates a random partition of size $`n`$ to a random permutation of size $`n`$ and the shape of the partition encodes information about the longest increasing subsequence of the permutation. Choosing the size of the symmetric group randomly (according to a Poisson distribution) gives a probability measure on the set of all partitions of all natural numbers which is a special case of the above Schur function measure. Then the coordinate change $`h_j=\lambda _1^{}+\lambda _jj`$ maps the set of row lengths $`\{\lambda _j\}`$ of the partition to a set of distinct integers $`\{h_j\}`$. These $`h_j`$ can be viewed as positions of electrostatic charges repelling each other, and from this viewpoint the measure on subsets of the integers bears a striking resemblance to the eigenvalue density of a random GUE matrix. This fantastic heuristic can be made precise and led to a solution of the long-standing conjecture relating lengths of increasing subsequences of permutations to eigenvalues of random matrices. For these developments see \[BOOl\],\[Jo\] and the many references therein.

Now we return to the measure $`M_{GL,u,q}`$ and describe an algorithm for growing random partitions according to this measure.

The Young Tableau Algorithm

Start with $`N=1`$ and $`\lambda `$ the empty partition. Also start with a collection of coins indexed by the natural numbers, such that coin $`i`$ has probability $`\frac{u}{q^i}`$ of heads and probability $`1\frac{u}{q^i}`$ of tails.

Flip coin $`N`$.

If coin $`N`$ comes up tails, leave $`\lambda `$ unchanged, set $`N=N+1`$ and go to Step 1.

If coin $`N`$ comes up heads, choose an integer $`S>0`$ according to the following rule. Set $`S=1`$ with probability $`\frac{q^{N\lambda _1^{}}1}{q^N1}`$. Set $`S=s>1`$ with probability $`\frac{q^{N\lambda _s^{}}q^{N\lambda _{s1}^{}}}{q^N1}`$. Then increase the size of column $`s`$ of $`\lambda `$ by 1 and go to Step 1.

As an example of the Young Tableau Algorithm, suppose we are at Step 1 with $`\lambda `$ equal to the following partition:

$$\begin{array}{cccc}& & & \\ & & & \\ & & & \end{array}$$

Suppose also that $`N=4`$ and that coin 4 had already come up heads once, at which time we added to column 1, giving $`\lambda `$. We flip coin 4 again and get heads, going to Step 2b. We add a box to column $`1`$ with probability $`\frac{q1}{q^41}`$, to column $`2`$ with probability $`\frac{q^2q}{q^41}`$, to column $`3`$ with probability $`\frac{q^3q^2}{q^41}`$, to column $`4`$ with probability $`0`$, and to column $`5`$ with probability $`\frac{q^4q^3}{q^41}`$. We then return to Step 1.

###### Theorem 6

For $`0<u<1`$ and $`q>1`$, the Young Tableau Algorithm generates partitions which are distributed according to the measure $`M_{GL,u,q}`$.

To give insight into the proof of Theorem 6, we remark that it was deduced by proving a stronger result (Theorem 7) inductively and then taking the $`N\mathrm{}`$ limit. As is clear from the statement of Theorem 7, the connection with Hall-Littlewood polynomials (in particular the ability to truncate them) was crucial. It is unlikely that the Young Tableau Algorithm would have been discovered without this connection.

###### Theorem 7

Let $`P^N(\lambda )`$ be the probability that the algorithm outputs $`\lambda `$ when coin $`N`$ comes up tails. Then

$$P^N(\lambda )=\{\begin{array}{cc}\frac{u^{|\lambda |}(\frac{u}{q})_N(\frac{1}{q})_N}{(\frac{1}{q})_{N\lambda _1^{}}}\frac{P_\lambda (\frac{1}{q},\mathrm{},\frac{1}{q^N},0,\mathrm{};0,\frac{1}{q})}{q^{n(\lambda )}}\hfill & \text{if }\lambda _1^{}N\hfill \\ 0\hfill & \text{if }\lambda _1^{}>N.\hfill \end{array}$$

Next we explain why the Young Tableau Algorithm is called that. A standard Young tableau $`T`$ of size $`n`$ is a partition of $`n`$ with each box filled by one of $`\{1,\mathrm{},n\}`$ such that each of $`\{1,\mathrm{},n\}`$ appears exactly once and the numbers increase in each row and column of $`T`$. For instance,

$$\begin{array}{ccccc}\text{1}& \text{3}& \text{5}& \text{6}& \\ \text{2}& \text{4}& \text{7}& & \\ \text{8}& \text{9}& & & \end{array}$$

is a standard Young tableau. Standard Young tableaux are important in combinatorics and representation theory. The Young Tableau Algorithm is so named because numbering the boxes in the order in which they are created gives a standard Young tableau. Thus although our initial interest was in the measure $`M_{GL,u,q}`$ on partitions, the Young Tableau Algorithm yields more: a probability measure on standard Young tableaux. One consequence of this is a (new) representation of prinicipally specialized Hall-Littlewood polynomials as a sum of certain weights over standard Young tableaux.

Let us indicate an application of this probability measure on standard Young tableaux. Rudvalis and Shinoda \[RuShi\] studied the distribution of fixed vectors for the classical groups over finite fields. Let $`G=G(n)`$ be a classical group (i.e. one of $`GL`$,$`U`$,$`Sp`$, or $`O`$) acting on an $`n`$ dimensional vector space $`V`$ over a finite field $`F_q`$ (in the unitary case $`F_{q^2}`$) in its natural way. Let $`P_{G,n}(k,q)`$ be the chance that an element of $`G`$ fixes a $`k`$ dimensional subspace and let $`P_{G,\mathrm{}}(k,q)`$ be the $`n\mathrm{}`$ limit of $`P_{G,n}(k,q)`$. They found (in a 76 page unpublished work) beautiful formulas for $`P_{G,\mathrm{}}(k,q)`$. Their formulas are (setting $`x=\frac{1}{q}`$):

1. $`P_{GL,\mathrm{}}(k,q)=\left[_{r=1}^{\mathrm{}}(1x^r)\right]\frac{x^{k^2}}{(1x)^2\mathrm{}(1x^k)^2}`$
2. $`P_{U,\mathrm{}}(k,q)=\left[_{r=1}^{\mathrm{}}\frac{1}{1+x^{2r1}}\right]\frac{x^{k^2}}{(1x^2)\mathrm{}(1x^{2k})}`$
3. $`P_{Sp,\mathrm{}}(k,q)=\left[_{r=1}^{\mathrm{}}\frac{1}{1+x^r}\right]\frac{x^{\frac{k^2+k}{2}}}{(1x)\mathrm{}(1x^k)}`$
4. $`P_{O,\mathrm{}}(k,q)=\left[_{r=0}^{\mathrm{}}\frac{1}{1+x^r}\right]\frac{x^{\frac{k^2k}{2}}}{(1x)\mathrm{}(1x^k)}`$.

From a probabilistic perspective, it is very natural to try to interpret the factorizations in these formulas as certain random variables being independent (the paper \[RuShi\] gives no insight as to why these formulas have a product form). The Young tableau algorithm leads to such an understanding for the finite general linear and unitary groups; see \[F3\] for details.

Remarks

1. A skew diagram is the set theoretic difference between paritions $`\mu ,\lambda `$ with $`\mu \lambda `$ and a horizontal strip is a skew diagram with at most one square in each column. There is another algorithm for growing random partitions distributed according to $`M_{GL,u,q}`$ in which one tosses coins and adds horizontal strips (as opposed to a box at a time). Details are in \[F3\].
2. (Joint with Mark Huber) We indicate how to make the Young Tableau Algorithm run on a computer, so as to terminate in finite time (clearly one can’t flip infinitely many coins). Let $`a_N`$ be the number of times that coin $`N`$ comes up heads; the idea is to first determine the random vector $`(a_1,a_2,\mathrm{})`$ and then grow the partitions as in Step 2b of the Young Tableau Algorithm. So let us explain how to determine $`(a_1,a_2,\mathrm{})`$. For $`N1`$ let $`t^{(N)}`$ be the probability that all tosses of all coins numbered $`N`$ or greater are tails. For $`N1`$ and $`j0`$ let $`t_j^{(N)}`$ be the probability that some toss of a coin numbered $`N`$ or greater is a head and that coin $`N`$ comes up heads $`j`$ times. It is simple to write down expressions for $`t^{(N)},t_0^{(N)},t_1^{(N)},\mathrm{}`$ and clearly $`t^{(N)}+_{j0}t_j^{(N)}=1`$.

The basic operation a computer can perform is to produce a random variable $`U`$ distributed uniformly in the interval $`[0,1]`$. By dividing $`[0,1]`$ into intervals of length $`t^{(1)},t_0^{(1)},t_1^{(1)},\mathrm{}`$ and seeing where $`U`$ is located, one arrives at the value of $`a_1`$. Furthermore, if $`U`$ landed in the interval of length $`t^{(1)}`$ then all coins come up tails and the algorithm is over. Otherwise, move on to coin 2, dividing $`[0,1]`$ into intervals of length $`t^{(2)},t_0^{(2)},t_1^{(2)},\mathrm{}`$ and so on.

For $`0<u<1`$ and $`q`$ the size of a finite field, this algorithm terminates quickly. The probability of the algorithm stopping after the generation of the first uniform in $`[0,1]`$ is $`_{i=1}^{\mathrm{}}(1u/q^i)_{i=1}^{\mathrm{}}(11/q^i)>(11/q)^21/4`$ where the second inequality is Corollary 3.6 of \[NP2\]. Should it be necessary to generate future uniforms, the same argument shows that the algorithm stops after each one with probalility at least $`1/2`$.

### 3.3 Sampling for a Given Size: Unipotent Elements

An element of $`GL(n,q)`$ is called unipotent if all of its eigenvalues are $`1`$; a theorem of Steinberg asserts that the number of unipotent elements in $`GL(n,q)`$ is $`q^{n(n1)}`$ (this is the square of the order of a $`q`$-Sylow subgroup if $`q`$ is prime). Unipotent elements are interesting because any element $`\alpha `$ in $`GL(n,q)`$ can be written uniquely as the product $`\alpha _s\alpha _u`$ where $`\alpha _s`$ is semisimple and $`\alpha _u`$ is unipotent.

Thus it is natural to study the random partition $`\lambda _{z1}`$ for unipotent elements in $`GL(n,q)`$. This is the same as conditioning the measure $`M_{GL,u,q}`$ to live on partitions of size $`n`$. This subsection explains how to modify the sampling method of Subsection 3.2 to sample from this conditioned version of $`M_{GL,u,q}`$ and also from a $`q`$-analog of Plancharel measure (related to the longest increasing subsequence problem). These results are joint with Mark Huber.

Algorithm for Sampling from $`M_{GL,u,q}`$ given that $`|\lambda |=n`$

Start with $`N=1`$ and $`\lambda `$ the empty partition.

If $`n=0`$ then stop. Otherwise set $`h=1\frac{1}{q^n}`$.

Flip a coin with probability of heads $`h`$.

If the toss of Step 2 came up tails, increase the value of $`N`$ by $`1`$ and go to Step 2.

If the toss of Step 2 comes up heads, decrease the value of $`n`$ by $`1`$, increase $`\lambda `$ according to the rule of Step 2b of the Young Tableau Algorithm (which depends on $`N`$), and then go to Step 1.

Theorem 8 will show that the above algorithm samples from $`M_{GL,u,q}`$ conditioned to live on partitions of size $`n`$. It is perhaps surprising that unlike the Young Tableau Algorithm, the probability of a coin coming up heads is independent of the coin number; it depends only on the number of future boxes needed to get a partition of size $`n`$.

###### Lemma 5

Let $`N_i`$ be the number of times that coin $`i`$ comes up heads in the Young Tableau Algorithm with $`u=1`$ and let $`\stackrel{}{N_i}`$ be the infinite vector with $`i`$th component $`N_i`$.

1. The probability that $`\stackrel{}{N_i}=\stackrel{}{n_i}`$ is $`\frac{_{r=1}^{\mathrm{}}(1\frac{1}{q^i})}{q^{_iin_i}}`$.
2. $$\underset{\stackrel{}{n_i}:{\scriptscriptstyle n_i}=a}{}\frac{1}{q^{_iin_i}}=\frac{1}{q^a(\frac{1}{q})_a}.$$

Proof: The first assertion is clear. The second assertion is well known in the theory of partitions, but we argue probabilistically. Multiply both sides by $`_{r=1}^{\mathrm{}}(1\frac{1}{q^i})`$. Then note from the first assertion that the left hand side is the $`M_{GL,1,q}`$ chance of having a partition of size $`a`$. Now use the second equation in the proof of Lemma 4 in Subsection 3.1. $`\mathrm{}`$

For Theorem 8 the notation Prob. is shorthand for the probability of an event.

###### Theorem 8

The algorithm for sampling from $`M_{GL,u,q}`$ conditioned to live on partitions on size $`n`$ is valid.

Proof: From the formula for $`M_{GL,u,q}`$, the conditioned measure for $`M_{GL,u,q}`$ is the same as for $`M_{GL,1,q}`$. Now let $`n_i`$ be the number of times that coin $`i`$ comes up heads in the Young Tableau Algorithm. Letting $`|`$ denote conditioning, it suffices to show that

$$Prob.(n_i1|\underset{ji}{}n_j=s)=1\frac{1}{q^s}.$$

In fact (for reasons to be explained later) we compute a bit more, namely the conditional probability that $`n_i=a`$ given that $`_{ji}n_j=s`$. By definition this conditional probability is the ratio

$$\frac{Prob.(n_i=a,_{ji}n_j=s)}{Prob.(_{ji}n_j=s)}.$$

The numerator and denominator are computed using Lemma 6 as follows:

$`Prob.(n_i=a,{\displaystyle \underset{ji}{}}n_j=s)`$ $`=`$ $`{\displaystyle \underset{a_{i+1}+\mathrm{}=sa}{}}{\displaystyle \frac{_{r=i}^{\mathrm{}}(11/q^r)}{q^{ia}q^{_{ji+1}ja_j}}}`$
$`=`$ $`{\displaystyle \underset{a_{i+1}+\mathrm{}=sa}{}}{\displaystyle \frac{_{r=i}^{\mathrm{}}(11/q^r)}{q^{is}q^{_{ji+1}(ji)a_j}}}`$
$`=`$ $`{\displaystyle \underset{a_1+\mathrm{}=sa}{}}{\displaystyle \frac{_{r=i}^{\mathrm{}}(11/q^r)}{q^{is}q^{_{j1}a_j}}}`$
$`=`$ $`{\displaystyle \frac{_{r=i}^{\mathrm{}}(11/q^r)}{q^{is}q^{sa}(\frac{1}{q})_{sa}}}.`$
$`Prob.({\displaystyle \underset{ji}{}}n_j=s)`$ $`=`$ $`{\displaystyle \underset{a_i+\mathrm{}=s}{}}{\displaystyle \frac{_{r=i}^{\mathrm{}}(11/q^r)}{q^{_{ji}ja_j}}}`$
$`=`$ $`{\displaystyle \underset{a_i+\mathrm{}=s}{}}{\displaystyle \frac{_{r=i}^{\mathrm{}}(11/q^r)}{q^{(i1)s+_{ji}(j(i1))a_j}}}`$
$`=`$ $`{\displaystyle \underset{a_1+\mathrm{}=s}{}}{\displaystyle \frac{_{r=i}^{\mathrm{}}(11/q^r)}{q^{(i1)s+_{j1}ja_j}}}`$
$`=`$ $`{\displaystyle \frac{_{r=i}^{\mathrm{}}(11/q^r)}{q^{is}(\frac{1}{q})_s}}.`$
Thus $`Prob.(n_i=0|_{ji}n_j=s)=\frac{1}{q^s}`$ and the result follows. $`\mathrm{}`$

As mentioned in Subsection 3.2 there is a natural measure $`M_{Pl,q}`$ on the set of all partitions of all integers which when conditioned to live on partitions of a given size gives a $`q`$-analog of Plancherel measure, which is related to longest increasing subsequence in non-uniform random permutations \[F3\]. In what follows $`J_a(q)`$ is the polynomial discussed on pages 52-54 of \[F1\], $`h(s)`$ denotes the hook-length of a dot in $`\lambda `$ \[Mac\] and $`[n]=\frac{q^n1}{q1}`$ is the $`q`$-analog of the number $`n`$. Recall that a skew diagram is the set theoretic difference between paritions $`\mu ,\lambda `$ with $`\mu \lambda `$ and that a horizontal strip is a skew diagram with at most one square in each column.

Algorithm for Sampling from $`M_{Pl,q}`$ for $`q>1`$ given that $`|\lambda |=n`$

Start with $`\lambda `$ the empty partition.

If $`n=0`$ then stop. Otherwise choose $`a`$ with $`0an`$ with probability

$$\frac{q^{n^2}(1\frac{1}{q^{na+1}})^2\mathrm{}(1\frac{1}{q^n})^2}{q^{(na)^2+n}(\frac{1}{q})_a}\frac{J_{na}(q)}{J_n(q)}.$$

Then increase $`\lambda `$ to $`\mathrm{\Lambda }`$ with probability

$$(1\frac{1}{q})\mathrm{}(1\frac{1}{q^a})\frac{q^{n(\lambda )}_{s\lambda }(1\frac{1}{q^{h(s)}})}{q^{n(\mathrm{\Lambda })}_{s\mathrm{\Lambda }}(1\frac{1}{q^{h(s)}})}$$

if $`\mathrm{\Lambda }\lambda `$ is a horizontal strip of size $`a`$ and with probability $`0`$ otherwise. Finally replace $`n`$ by $`na`$ and repeat Step 1.

Using Lemma 6, Theorem 9 proves that the algorithm for sampling from $`M_{Pl,q}`$ conditioned to live on $`|\lambda |=n`$ works. We omit the details, which (given the background material in \[F1\]) are analogous to the case of $`M_{GL,u,q}`$.

###### Lemma 6

Let $`N_i`$ be the number of times that coin $`i`$ comes up heads in the algorithm from \[F3\] for sampling from the measure $`M_{Pl,q}`$ and let $`\stackrel{}{N_i}`$ be the infinite vector with $`i`$th component $`N_i`$.

1. The probability that $`\stackrel{}{N_i}=\stackrel{}{n_i}`$ is $`\frac{_{r=1}^{\mathrm{}}_{j=r}^{\mathrm{}}(1\frac{1}{q^j})}{q^{_iin_i}_i(\frac{1}{q})_{n_i}}`$.
2. $$\underset{\stackrel{}{n_i}:_{n_i}=a}{}\frac{1}{q^{_iin_i}_i(\frac{1}{q})_{n_i}}=\frac{J_a(q)}{q^{a^2}(1\frac{1}{q})^2\mathrm{}(1\frac{1}{q^a})^2}.$$

###### Theorem 9

The algorithm given for sampling from $`M_{Pl,q}`$ with $`q>1`$ conditioned to live on $`|\lambda |=n`$ is valid.

### 3.4 Markov Chain Approach

The main result in this subsection is a third method for understanding the measure $`M_{GL,u,q}`$ probabilistically (\[F7\]). The idea is to build up the random partition a column at a time; if the current column has size $`a`$, then the next column will have size $`b`$ (with $`ba`$) with probability $`K(a,b)`$. The surprise is that this transition rule turns out to be independent of the columns, yielding a Markov on the natural numbers. This Markov chain is diagonalizable with eigenvalues $`1,\frac{u}{q},\frac{u^2}{q^4},\mathrm{}`$. It will be used to give a probabilistic proof of the Rogers-Ramanujan identities in Subsection 3.5.

It is convenient to set $`\lambda _0^{}`$ (the height of an imaginary zeroth column) equal to $`\mathrm{}`$. For the entirety of this subsection, let $`P(a)`$ be the $`M_{GL,u,q}`$ probability that $`\lambda _1^{}=a`$. Theorem 10, which makes the connection with Markov chains, is proved in a completely elementary way. The argument reproves that $`M_{GL,u,q}`$ is a probability measure (Lemma 4 of Subsection 3.1), shows that the asserted Markov transition probabilities add to one, and gives a formula for $`P(a)`$.

###### Theorem 10

Starting with $`\lambda _0^{}=\mathrm{}`$, define in succession $`\lambda _1^{},\lambda _2^{},\mathrm{}`$ according to the rule that if $`\lambda _i^{}=a`$, then $`\lambda _{i+1}^{}=b`$ with probability

$$K(a,b)=\frac{u^b(\frac{1}{q})_a(\frac{u}{q})_a}{q^{b^2}(\frac{1}{q})_{ab}(\frac{1}{q})_b(\frac{u}{q})_b}.$$

Then the resulting partition is distributed according to $`M_{GL,u,q}`$.

Proof: Suppose we know that $`M_{GL,u,q}`$ is a probability measure and that

$$P(a)=\frac{u^a(\frac{u}{q})_{\mathrm{}}}{q^{a^2}(\frac{1}{q})_a(\frac{u}{q})_a}.$$

Then the $`M_{GL,u,q}`$ probability of choosing a partition with $`\lambda _i^{}=r_i^{}`$ for all $`i`$ is

$$Prob.(\lambda _0^{}=\mathrm{})\frac{Prob.(\lambda _0^{}=\mathrm{},\lambda _1^{}=r_1)}{Prob.(\lambda _0^{}=\mathrm{})}\underset{i=1}{\overset{\mathrm{}}{}}\frac{Prob.(\lambda _0^{}=\mathrm{},\lambda _1^{}=r_1,\mathrm{},\lambda _{i+1}^{}=r_{i+1})}{Prob.(\lambda _0^{}=\mathrm{},\lambda _1^{}=r_1,\mathrm{},\lambda _i^{}=r_i)}.$$

Thus it is enough to prove the (surprising) assertion that

$$\frac{Prob.(\lambda _0^{}=\mathrm{},\lambda _1^{}=r_1,\mathrm{},\lambda _{i1}^{}=r_{i1},\lambda _i^{}=a,\lambda _{i+1}^{}=b)}{Prob.(\lambda _0^{}=\mathrm{},\lambda _1^{}=r_1,\mathrm{},\lambda _{i1}^{}=r_{i1},\lambda _i^{}=a)}=\frac{u^b(\frac{1}{q})_a(\frac{u}{q})_a}{q^{b^2}(\frac{1}{q})_{ab}(\frac{1}{q})_b(\frac{u}{q})_b},$$

for all $`i,a,b,r_1,\mathrm{},r_{i1}`$. One calculates that

$$\underset{\genfrac{}{}{0pt}{}{\lambda :\lambda _1^{}=r_1,\mathrm{},\lambda _{i1}^{}=r_{i1}}{\lambda _i^{}=a}}{}M_{GL,u,q}(\lambda )=\frac{u^{r_1+\mathrm{}+r_{i1}}}{q^{r_1^2+\mathrm{}+r_{i1}^2}(\frac{1}{q})_{r_1r_2}\mathrm{}(\frac{1}{q})_{r_{i2}r_{i1}}(\frac{1}{q})_{r_{i1}a}}P(a).$$

Similarly, observe that

$$\underset{\genfrac{}{}{0pt}{}{\lambda :\lambda _1^{}=r_1,\mathrm{},\lambda _{i1}^{}=r_{i1}}{\lambda _i^{}=a,\lambda _{i+1}^{}=b}}{}M_{GL,u,q}(\lambda )=\frac{u^{r_1+\mathrm{}+r_{i1}+a}}{q^{r_1^2+\mathrm{}+r_{i1}^2+a^2}(\frac{1}{q})_{r_1r_2}\mathrm{}(\frac{1}{q})_{r_{i2}r_{i1}}(\frac{1}{q})_{r_{i1}a}(\frac{1}{q})_{ab}}P(b).$$

Thus the ratio of these two expressions is

$$\frac{u^b(\frac{1}{q})_a(\frac{u}{q})_a}{q^{b^2}(\frac{1}{q})_{ab}(\frac{1}{q})_b(\frac{u}{q})_b},$$

as desired. Note that the transition probabilities must sum to 1 because

$$\underset{ba}{}\frac{_{\genfrac{}{}{0pt}{}{\lambda :\lambda _1^{}=r_1,\mathrm{},\lambda _{i1}^{}=r_{i1}}{\lambda _i^{}=a,\lambda _{i+1}^{}=b}}M_{GL,u,q}(\lambda )}{_{\genfrac{}{}{0pt}{}{\lambda :\lambda _1^{}=r_1,\mathrm{},\lambda _{i1}^{}=r_{i1}}{\lambda _i^{}=a}}M_{GL,u,q}(\lambda )}=1$$

for any measure $`M_{GL,u,q}`$ on partitions.

Thus to complete the proof, it must be shown that $`M_{GL,u,q}`$ is a probability measure and that

$$P(a)=\frac{u^a(\frac{u}{q})_{\mathrm{}}}{q^{a^2}(\frac{1}{q})_a(\frac{u}{q})_a}.$$

Since

$$\frac{_{\genfrac{}{}{0pt}{}{\lambda :\lambda _1^{}=r_1,\mathrm{},\lambda _{i1}^{}=r_{i1}}{\lambda _i^{}=a,\lambda _{i+1}^{}=b}}M_{GL,u,q}(\lambda )}{_{\genfrac{}{}{0pt}{}{\lambda :\lambda _1^{}=r_1,\mathrm{},\lambda _{i1}^{}=r_{i1}}{\lambda _i^{}=a}}M_{GL,u,q}(\lambda )}=\frac{P(b)u^a}{P(a)q^{a^2}(\frac{1}{q})_{ab}}$$

it follows that

$$\underset{ba}{}\frac{P(b)u^a}{P(a)q^{a^2}(\frac{1}{q})_{ab}}=1.$$

From this recursion and the fact that $`P(0)=(\frac{u}{q})_{\mathrm{}}`$, one solves for $`P(a)`$ inductively, finding that

$$P(a)=\frac{u^a(\frac{u}{q})_{\mathrm{}}}{q^{a^2}(\frac{1}{q})_a(\frac{u}{q})_a}.$$

Cauchy’s identity (page 20 of \[A1\]) gives that $`_aP(a)=1`$, so that $`M_{GL,u,q}`$ is a probability measure. $`\mathrm{}`$

Theorem 11 diagonalizes the transition matrix $`K`$, finding a basis of eigenvectors, which is fundamental for understanding the Markov chain (part 3 is stated as a Lemma in \[A2\]). Since the matrix $`K`$ is upper triangular with distinct eigenvalues, this is straightforward.

###### Theorem 11

1. Let $`C`$ be the diagonal matrix with $`(i,i)`$ entry $`(\frac{1}{q})_i(\frac{u}{q})_i`$. Let $`M`$ be the matrix $`\left(\frac{u^j}{q^{j^2}(\frac{1}{q})_{ij}}\right)`$. Then $`K=CMC^1`$, which reduces the problem of diagonalizing $`K`$ to that of diagonalizing $`M`$.
2. Let $`A`$ be the matrix $`\left(\frac{1}{(\frac{1}{q})_{ij}(\frac{u}{q})_{i+j}}\right)`$. Then the columns of $`A`$ are eigenvectors of $`M`$ for right multiplication, the $`j`$th column having eigenvalue $`\frac{u^j}{q^{j^2}}`$.
3. The inverse matrix $`A^1`$ is $`\left(\frac{(1u/q^{2i})(1)^{ij}(\frac{u}{q})_{i+j1}}{q^{\left(\genfrac{}{}{0pt}{}{ij}{2}\right)}(\frac{1}{q})_{ij}}\right)`$.

Corollary 2 (immediate from Theorem 11) will be useful for the proof of the Rogers-Ramanujan identities in Section 3.5. In the case $`L\mathrm{}`$ and $`j=0`$, it is the so called Rogers-Selberg identity.

###### Corollary 2

Let $`E`$ be the diagonal matrix with $`(i,i)`$ entry $`\frac{u^i}{q^{i^2}}`$. Then $`K^r=CAE^rA^1C^1`$. More explicitly,

$$K^r(L,j)=\frac{(\frac{1}{q})_L(\frac{u}{q})_L}{(\frac{1}{q})_j(\frac{u}{q})_j}\underset{n=0}{\overset{\mathrm{}}{}}\frac{u^{rn}(1u/q^{2n})(1)^{nj}(\frac{u}{q})_{n+j1}}{q^{rn^2}(\frac{1}{q})_{Ln}(\frac{u}{q})_{L+n}q^{\left(\genfrac{}{}{0pt}{}{nj}{2}\right)}(\frac{1}{q})_{nj}}.$$

Proof: This is immediate from Theorem 11. $`\mathrm{}`$

Remarks

1. One of our motivations for seeking a Markov chain description of $`M_{GL,u,q}`$ is work of Fristedt \[Fris\], who had a Markov chain approach for the measure $`P_q`$ on the set of all partitions of all natural numbers defined by $`P_q(\lambda )=_{i=1}^{\mathrm{}}(1q^i)q^{|\lambda |}`$ where $`q<1`$. Fristedt’s interest was in studying what a uniformly chosen partition of an integer looks like, and conditioning $`P_q`$ to live on partitions of size $`n`$ gives a uniform partition. The measure $`P_q`$ is related to to vertex operators \[O1\] and to the enumeration of ramified coverings of the torus \[Dij\]. In this regard the papers \[O1\] and \[BlO\] prove that the $`k`$ point correlation function

$$F(t_1,\mathrm{},t_k)=\underset{\lambda }{}q^{|\lambda |}\underset{k=1}{\overset{n}{}}\underset{i=1}{\overset{\mathrm{}}{}}t_k^{\lambda _ii+\frac{1}{2}}$$

is a sum of determinants involving genus 1 theta functions and their derivatives and give connections with quasi-modular forms. It would be marvellous if the measure $`M_{GL,u,q}`$ (being related to modular forms via the Rogers-Ramanujan identities) is also related to enumerative questions in algebraic geometry.
2. As mentioned in the introduction, the Markov chain approach gives a unified description of conjugacy classes of the finite classical groups. For the symplectic and orthogonal groups it is necessary to use two Markov chains $`K_1`$ and $`K_2`$. For the symplectic case, steps with column number $`i`$ odd use $`K_1`$ and steps with column number $`i`$ even use $`K_2`$. For the orthogonal case, steps with column number $`i`$ odd use $`K_2`$ and steps with column number $`i`$ even use $`K_1`$. The Markov chains $`K_1,K_2`$ are the same for both cases! Details are in \[F6\]. The Markov chain approach is also related to quivers \[F7\].

### 3.5 Rogers-Ramanujan Identities

The Rogers-Ramanujan identities \[Ro\]

$$1+\underset{n=1}{\overset{\mathrm{}}{}}\frac{q^{n^2}}{(1q)(1q^2)\mathrm{}(1q^n)}=\underset{n=1}{\overset{\mathrm{}}{}}\frac{1}{(1q^{5n1})(1q^{5n4})}$$

$$1+\underset{n=1}{\overset{\mathrm{}}{}}\frac{q^{n(n+1)}}{(1q)(1q^2)\mathrm{}(1q^n)}=\underset{n=1}{\overset{\mathrm{}}{}}\frac{1}{(1q^{5n2})(1q^{5n3})}$$

are among the most interesting partition identities in number theory and combinatorics, with connections to Lie theory and statistical mechanics (see the discussions in \[A2\] and \[F7\] for many references). One ongoing challenge in the subject (posed by Hardy) has been to find a proof of the Rogers-Ramanujan identities which is both motivated and simple. The purpose of this subsection is to describe such a proof (\[F7\]), which is also the first probabilistic proof of the Rogers-Ramanujan identities.

To illustrate the idea we give the proof of the following generalization of the first Rogers-Ramanujan identity (called the Andrews-Gordon identity \[A3\],\[Gor\]):

$$\underset{n_1,\mathrm{},n_{k1}0}{}\frac{1}{q^{N_1^2+\mathrm{}+N_{k1}^2}(1/q)_{n_1}\mathrm{}(1/q)_{n_{k1}}}=\underset{\genfrac{}{}{0pt}{}{r=1}{r0,\pm k(mod2k+1)}}{\overset{\mathrm{}}{}}\frac{1}{1(1/q)^r}$$

where $`N_i=n_i+\mathrm{}+n_{k1}`$.

The idea is simple. We study the distribution of the length of the first row of a random partition distributed as $`M_{GL,1,q}`$. From the definition of $`M_{GL,1,q}`$ the probability that the first row has length less than $`k`$ is equal to

$$\underset{r=1}{\overset{\mathrm{}}{}}(1\frac{1}{q^r})\underset{\lambda :\lambda _k^{}=0}{}\frac{1}{q^{(\lambda _1^{})^2+\mathrm{}+(\lambda _{k1}^{})^2}(1/q)_{\lambda _1^{}\lambda _2^{}}\mathrm{}(1/q)_{\lambda _{k1}^{}\lambda _k^{}}}.$$

Letting $`n_i`$ denote $`\lambda _i^{}\lambda _{i+1}^{}`$ and $`N_i`$ denote $`\lambda _i^{}`$, this becomes

$$\underset{r=1}{\overset{\mathrm{}}{}}(1\frac{1}{q^r})\underset{n_1,\mathrm{},n_{k1}0}{}\frac{1}{q^{N_1^2+\mathrm{}+N_{k1}^2}(1/q)_{n_1}\mathrm{}(1/q)_{n_{k1}}}$$

which is a essentially the left hand side of the Andrews-Gordon identity. On the other hand the probability that the first row has length less than $`k`$ is equal to the probability that the Markov chain of Section 3.4 is absorbed at $`0`$ at time $`k`$. Since we diagonalized the matrix associated to this Markov chain, it is straightforward to compute this probability. To get it into product form it is necessary to apply Jacobi’s triple product identity which has a simple combinatorial proof \[A1\]. Further details are in \[F7\].

Next we argue that this proof is motivated. Certainly the measure $`M_{GL,1,q}`$ is a natural object to study, given that it is the $`n\mathrm{}`$ limit law of $`\lambda _{z1}`$ for a random element of $`GL(n,q)`$. It was natural to try to build up the random partitions $`\lambda `$ column by column as in Section 3.4. Observing that the resulting Markov chain is absorbing at $`0`$ with probability one, the time to absorption (equivalent to the distribution of the length of the first row) is the most natural quantity one could examine. The final step is applying Jacobi’s triple product identity, and thus going from a “sum = sum” identity to a “sum = product” identity. As mentioned above Jacobi’s triple product identity is easy to verify, but one still wants a motivation for trying to write the left hand side of the Andrews-Gordon identity in product form. One motivation is Baxter’s work on statistical mechanics (surveyed in \[A2\],\[Bax1\],\[Bax2\]) in which he really needed “sum = product” identities and was led to conjecture analogs of Rogers-Ramanujan type identities. Although a proof of the Rogers-Ramanujan identities doesn’t emerge from his work, it is clearly one of the truly great accomplishments in mathematics and his book \[Bax1\] has been very influential. A second motivation is our work on the $`n\mathrm{}`$ asymptotic probability that an element of $`GL(n,q)`$ is semisimple. The argument, recorded in \[F1\] or the more readily available \[F4\] needed a “sum = product” identity. The corresponding computation in \[F9\] for the finite affine groups needed both Rogers-Ramanujan identities.

Andrews’ paper \[A4\] notes that many proofs of the Rogers-Ramanujan identities make use of the following result called Bailey’s Lemma, alluded to in \[Bai\] and stated explicity in \[A3\]. A pair of sequences $`\{\alpha _L\}`$ and $`\{\beta _L\}`$ are called a Bailey pair if

$$\beta _L=\underset{r=0}{\overset{L}{}}\frac{\alpha _r}{(1/q)_{Lr}(u/q)_{L+r}}.$$

Bailey’s Lemma states that if $`\alpha _L^{}=\frac{u^L}{q^{L^2}}\alpha _L`$ and $`\beta _L^{}=_{r=0}^L\frac{u^r}{q^{r^2}(1/q)_{Lr}}\beta _r`$, then $`\{\alpha _L^{}\}`$ and $`\{\beta _L^{}\}`$ are a Bailey pair. From the viewpoint of Markov chains, this case of Bailey’s Lemma is clear. To explain, let $`A,D,M`$ be as in Theorem 11 (recall that $`M=ADA^1`$). Viewing $`\alpha =\stackrel{}{\alpha _L}`$ and $`\beta =\stackrel{}{\beta _L}`$ as column vectors, the notion of a Bailey pair means that $`\beta =A\alpha `$. This case of Bailey’s Lemma follows because

$$\beta ^{}=M\beta =ADA^1\beta =AD\alpha =A\alpha ^{}.$$

As Andrews explains in \[A2\], the power of Bailey’s lemma lies in its ability to be iterated and gives a short proof of the Rogers-Selberg identity (Corollary 2 in Section 3.4). From the remarks in this paragraph it is clear that iterating Bailey’s lemma corresponds to taking several according to the Markov chain $`K`$. This demystifies the Bailey’s Lemma proofs of the Rogers-Ramanujan identities, which strike this author as unmotivated. The fact that the Markov chain approach has analogs for other finite classical groups and for quivers is further evidence of its naturality.

## 4 Upper Triangular Matrices

This section surveys probabilistic aspects of conjugacy classes in the group $`T(n,q)`$ of upper triangular matrices over finite fields with $`1`$’s along the main diagonal. At present little is known about conjugacy in $`T(n,q)`$. The papers \[VAr\], \[VArV\] study the number of conjugacy classes. Kirillov \[Kir\] calls for an extension of his method of coadjoint orbits for groups over real, complex, or $`p`$-adic fields to the group $`T(n,q)`$ and gives premilinary connections with statistical physics; the paper \[IsKar\] gives a counterexample to one of his conjectures. As we do not see how to further develop those results or improve on their exposition, we instead focus on a simpler problem: the probabilistic study of Jordan form of elements of $`T(n,q)`$.

Subsection 4.1 describes a probabilistic growth algorithm for the Jordan form of upper triangular matrices over a finite field. This is linked with symmetric function theory and potential theory on Bratteli diagrams in Subsection 4.2.

### 4.1 Growth Algorithm for Jordan Form

Theorem 12 gives a probabilistic growth algorithm for the Jordan form of random elements of $`T(n,q)`$. Its proof uses elementary reasoning from linear algebra.

###### Theorem 12

(\[Kir\],\[B\]) The Jordan form of a uniformly chosen element of $`T(n,q)`$ can be sampled from by stopping the following procedure after $`n`$ steps:

Starting with the empty partition, at each step transition from a partition $`\lambda `$ to a partition $`\mathrm{\Lambda }`$ by adding a box to column $`i`$ chosen according to the rules

* $`i=1`$ with probability $`\frac{1}{q^{\lambda _1^{}}}`$
* $`i=j>1`$ with probability $`\frac{1}{q^{\lambda _j^{}}}\frac{1}{q^{\lambda _{j1}^{}}}`$

Theorem 12 leads to the following central limit theorem about the asymptotic Jordan form of an element of $`T(n,q)`$.

###### Theorem 13

(\[B\]) Let $`\lambda `$ be the partition corresponding to the Jordan form of a random element of $`T(n,q)`$. Let $`Prob^n`$ denote probability under the uniform measure on $`T(n,q)`$ and let $`p_i=\frac{1}{q^{i1}}\frac{1}{q^i}`$. Then

$$lim_n\mathrm{}Prob^n(\frac{\lambda _ip_in}{\sqrt{n}}x_i,i=1,\mathrm{},k)=(2\pi )^{\frac{k}{2}}_{\mathrm{}}^{x_1}\mathrm{}_{\mathrm{}}^{x_k}e^{\frac{1}{2}<Qt,t>}𝑑t$$

for any $`(x_1,\mathrm{},x_k)R^k`$, where the covariance matrix equals

$$Q=diag(p_1,\mathrm{},p_k)(p_ip_j)_{i,j=1}^k.$$

### 4.2 Symmetric Functions and Potential Theory

Given the usefulness of symmetric functions in the probabilistic study of the measure $`M_{GL,u,q}`$, it is natural to seek an analogous understanding of Theorem 12. That is the topic of the present subsection. The ideas here are from the report \[F8\].

The first step is to link the probability that an element of $`T(n,q)`$ has Jordan form of type $`\mathrm{\Lambda }`$ with symmetric function theory. For the rest of this section, $`P_\mathrm{\Lambda }(q,t)`$ denotes a Macdonald polynomial, $`K_{\mu \mathrm{\Lambda }}(q,t)`$ denotes a Kostka-Foulkes polynomial, and $`f^\mu `$ is the dimension of the irreducible representation of $`S_n`$ corresponding to the partition $`\mu `$ (see \[Mac\] for background). Note that when $`q=0`$ the Macdonald polynomial is our friend, a Hall-Littlewood polynomial.

###### Theorem 14

(\[F5\]) The probability that a random element of $`T(n,q)`$ has Jordan form of type $`\mathrm{\Lambda }`$ is

$$P_\mathrm{\Lambda }(1\frac{1}{q},\frac{1}{q}\frac{1}{q^2},\mathrm{};0,\frac{1}{q})\underset{\mu n}{}f^\mu K_{\mu \mathrm{\Lambda }}(0,q).$$

Next we give some background on potential theory on Bratteli diagrams. This is a beautiful subject, with connections to probability and representation theory. We recommend \[Ke1\] for background on potential theory with many examples and \[BOl\] for a survey of recent developments. The basic set-up is as follows. One starts with a Bratteli diagram; that is an oriented graded graph $`\mathrm{\Gamma }=_{n0}\mathrm{\Gamma }_n`$ such that

1. $`\mathrm{\Gamma }_0`$ is a single vertex $`\mathrm{}`$.
2. If the starting vertex of an edge is in $`\mathrm{\Gamma }_i`$, then its end vertex is in $`\mathrm{\Gamma }_{i+1}`$.
3. Every vertex has at least one outgoing edge.
4. All $`\mathrm{\Gamma }_i`$ are finite.

For two vertices $`\lambda ,\mathrm{\Lambda }\mathrm{\Gamma }`$, one writes $`\lambda \mathrm{\Lambda }`$ if there is an edge from $`\lambda `$ to $`\mathrm{\Lambda }`$. Part of the underlying data is a multiplicity function $`\kappa (\lambda ,\mathrm{\Lambda })`$. Letting the weight of a path in $`\mathrm{\Gamma }`$ be the product of the multiplicities of its edges, one defines the dimension $`dim(\mathrm{\Lambda })`$ of a vertex $`\mathrm{\Lambda }`$ to be the sum of the weights over all maximal length paths from $`\mathrm{}`$ to $`\mathrm{\Lambda }`$ (this definition clearly extend to intervals). Given a Bratteli diagram with a multiplicity function, one calls a function $`\varphi `$ harmonic if $`\varphi (0)=1`$, $`\varphi (\lambda )0`$ for all $`\lambda \mathrm{\Gamma }`$, and

$$\varphi (\lambda )=\underset{\mathrm{\Lambda }:\lambda \mathrm{\Lambda }}{}\kappa (\lambda ,\mathrm{\Lambda })\varphi (\mathrm{\Lambda }).$$

An equivalent concept is that of coherent probability distributions. Namely a set $`\{M_n\}`$ of probability distributions $`M_n`$ on $`\mathrm{\Gamma }_n`$ is called coherent if

$$M_{n1}(\lambda )=\underset{\mathrm{\Lambda }:\lambda \mathrm{\Lambda }}{}\frac{dim(\lambda )\kappa (\lambda ,\mathrm{\Lambda })}{dim(\mathrm{\Lambda })}M_n(\mathrm{\Lambda }).$$

The formula allowing one to move between the definitions is $`\varphi (\lambda )=\frac{M_n(\lambda )}{dim(\lambda )}`$.

One reason the set-up is interesting from the viewpoint of probability theory is the fact that every harmonic function can be written as a Poisson integral over the set of extreme harmonic functions (which is often the Martin boundary). For the Pascal lattice (vertices of $`\mathrm{\Gamma }_n`$ are pairs $`(k,n)`$ with $`k=0,1,\mathrm{},n`$ and $`(k,n)`$ is connected to $`(k,n+1)`$ and $`(k+1,n+1)`$), this fact is the simplest instance of de Finetti’s theorem. When the multiplicity function $`\kappa `$ is integer valued, one can define a sequence of algebras $`A_n`$ associated to the Bratteli diagram, and harmonic functions correspond to certain characters of the inductive limit of the algebras $`A_n`$.

Next we define a branching for which the probability that an element of $`T(n,q)`$ has Jordan type $`\mathrm{\Lambda }`$ is a harmonic function. First some notation is needed. For $`\lambda \mathrm{\Lambda }`$, let $`R_{\mathrm{\Lambda }/\lambda }`$ (resp. $`C_{\mathrm{\Lambda }/\lambda }`$) be the boxes of $`\lambda `$ in the same row (resp. column) as the boxes removed from $`\lambda `$ to get $`\mathrm{\Lambda }`$. This notation differs from that in \[Mac\]. Let $`a_\lambda (s)`$, $`l_\lambda (s)`$ be the number of dots in $`\lambda `$ strictly to the east and south of $`s`$, and let $`h_\lambda (s)=a_\lambda (s)+l_\lambda (s)+1`$.

Definition 1: For $`0q<1`$ and $`0<t<1`$, the underlying Bratteli diagram $`\mathrm{\Gamma }`$ has as level $`\mathrm{\Gamma }_n`$ all partitions $`\lambda `$ of $`n`$. Letting $`i`$ be the column number of the dot removed to go from $`\lambda `$ to $`\mathrm{\Lambda }`$, for $`\lambda \mathrm{\Lambda }`$, define the multiplicty function as

$$\kappa (\lambda ,\mathrm{\Lambda })=\frac{1}{t^{\mathrm{\Lambda }_i^{}1}}\underset{sR_{\mathrm{\Lambda }/\lambda }}{}\frac{1q^{a_\mathrm{\Lambda }(s)+1}t^{l_\mathrm{\Lambda }(s)}}{1q^{a_\lambda (s)+1}t^{l_\lambda (s)}}\underset{sC_{\mathrm{\Lambda }/\lambda }}{}\frac{1q^{a_\mathrm{\Lambda }(s)}t^{l_\mathrm{\Lambda }(s)+1}}{1q^{a_\lambda (s)}t^{l_\lambda (s)+1}}.$$

Equation I.10 of \[GarsH\] proves that

$$dim(\mathrm{\Lambda })=\frac{1}{t^{n(\mathrm{\Lambda })}}\underset{\mu n}{}f^\mu K_{\mu \mathrm{\Lambda }}(q,t).$$

Definition 2: For $`0q<1,0<t<1`$ and $`0x_1,x_2,\mathrm{}`$ such that $`x_i=1`$, define a family $`\{M_n\}`$ of probability measures on partitions of size $`n`$ by

$`M_n(\mathrm{\Lambda })`$ $`=`$ $`{\displaystyle \frac{(1q)^{|\mathrm{\Lambda }|}P_\mathrm{\Lambda }(x;q,t)_{\mu n}f^\mu K_{\mu \mathrm{\Lambda }}(q,t)}{_{s\mathrm{\Lambda }}(1q^{a_\mathrm{\Lambda }(s)+1}t^{l_\mathrm{\Lambda }(s)})}}`$
$`=`$ $`{\displaystyle \frac{(1q)^{|\mathrm{\Lambda }|}P_\mathrm{\Lambda }(x;q,t)t^{n(\mathrm{\Lambda })}dim(\mathrm{\Lambda })}{_{s\mathrm{\Lambda }}(1q^{a_\mathrm{\Lambda }(s)+1}t^{l_\mathrm{\Lambda }(s)})}}`$
Consider the specialization that $`q=0`$ and $`t=\frac{1}{q}`$, where this second $`q`$ is the size of a finite field. Further, set $`x_i=\frac{1}{q^{i1}}\frac{1}{q^i}`$. Then Theorem 14 implies that $`M_n(\mathrm{\Lambda })`$ is the probability that a uniformly chosen element of $`T(n,q)`$ has Jordan type $`\mathrm{\Lambda }`$. The multiplicities have a simple description; letting $`i`$ be the column to which one adds in order to go from $`\lambda `$ to $`\mathrm{\Lambda }`$, it follows that $`\kappa (\lambda ,\mathrm{\Lambda })=q^{\lambda _i^{}}+q^{\lambda _i^{}1}+\mathrm{}+q^{\lambda _{i+1}^{}}`$. Second, $`dim(\mathrm{\Lambda })`$ reduces to a Green’s polynomial $`Q^\mathrm{\Lambda }(q)=Q_{(1^n)}^\mathrm{\Lambda }(q)`$ as in Section 3.7 of \[Mac\]. These polynomials are important in the representation theory of the finite general linear groups. This specialization was the motivation for Definition 2.

The connection with potential theory is given by the following result.

###### Theorem 15

(\[F8\]) The measures of Definition 2 are harmonic with respect to the branching of Definition 1.

It is elementary and well-known that if one starts at the empty partition and transitions from $`\lambda `$ to $`\mathrm{\Lambda }`$ with probability $`\frac{\kappa (\lambda ,\mathrm{\Lambda })M_n(\mathrm{\Lambda })dim(\lambda )}{M_{n1}(\lambda )dim(\mathrm{\Lambda })}`$, one gets samples from any coherent family of measures $`\{M_n\}`$. Applying this principle to the above specialization in which $`M_n(\mathrm{\Lambda })`$ is $`T(n,q)`$ and using Macdonald’s principal specialization formula (page 337 of \[Mac\]) gives the advertised proof of Theorem 12 by means of symmetric functions and potential theory.

Remarks:

1. As indicated in \[F8\], the example of Schur functions ($`q=t<1`$) is also interesting. The measure $`M_n(\mathrm{\Lambda })`$ reduces to $`s_\mathrm{\Lambda }f^\mathrm{\Lambda }`$, where $`s_\mathrm{\Lambda }`$ is a Schur function. Setting $`x_1=\mathrm{}=x_n=\frac{1}{n}`$ and letting $`n\mathrm{}`$, one obtains Plancherel measure, which is important in representation theory and random matrix theory. Letting $`x_1=\mathrm{}=x_n`$ satisfy $`x_i=1`$ (all other $`x_j=0`$) gives a natural deformation of Plancherel measure, studied for instance by \[ItTWi\]. Stanley \[Sta\] shows that this measure on partitions also arises by applying the Robinson-Schensted-Knuth algorithm to a random permutation distributed after a biased riffle shuffle (in other words, this measure encodes information about the longest increasing subsequences of permutations distributed as shuffles).
2. It has been pointed out to the author that the branchings $`\kappa (\lambda ,\mathrm{\Lambda })`$ of Definition 1 are related to the branchings $`\tau (\lambda ,\mathrm{\Lambda })`$ of \[Ke2\] by the formula

$$\kappa (\lambda ,\mathrm{\Lambda })=f(\lambda )\tau (\lambda ,\mathrm{\Lambda })f(\mathrm{\Lambda })^1,$$

for a certain positive function $`f(\lambda )`$ on the set of vertices, which implies by \[Ke3\] that the boundaries of these two branchings are homeomorphic and that the branchings of Definition 1 are multiplicative. Kerov \[Ke2\] has a conjectural description of the boundary. It has been verified for Schur functions \[T\], Kingman branching \[Kin\], and Jack polynomials \[KeOOl\], but remains open for the general case of Macdonald polynomials. In particular, it is open for Hall-Littlewood polynomials, the case related to $`T(n,q)`$. It is interesting that the $`\kappa (\lambda ,\mathrm{\Lambda })`$ of Definition 1 are integers for Hall-Littlewood polynomials, whereas the $`\tau (\lambda ,\mathrm{\Lambda })`$ of \[Ke2\] are not.

## Acknowledgements

The author’s greatest thanks go to Persi Diaconis (his former thesis advisor) for years of friendship, encouragement, and inspiration. He was very helpful in the preparation of this article. We thank Peter M. Neumann and Cheryl E. Praeger for countless conversations about conjugacy classes and computational group theory, and Mark Huber for permission to survey some joint unpublished results. The author received the financial support of an NSF Postdoctoral Fellowship.