
We investigate combinatorial properties of a family of probability
distributions on finite abelian pgroups. This family includes several
wellknown distributions as specializations. These specializations have been
studied in the context of CohenLenstra heuristics and cokernels of families of
random padic matrices.

In this paper we use generating function methods to obtain new asymptotic
results about spaces of $F$stable maximal tori in $GL_n(\overline{F_q})$,
$Sp_{2n}(\overline{F_q})$, and $SO_{2n+1}(\overline{F_q})$. We recover
stability results of ChurchEllenbergFarb and Jim\'enez RollandWilson for
"polynomial" statistics on these spaces, and we compute explicit formulas for
their stable values. We derive a double generating function for the characters
of the cohomology of flag varieties in type B/C, which we use to obtain analogs
in type B/C of results of Chen: we recover "twisted homological stability" for
the spaces of maximal tori in $Sp_{2n}(\mathbb{C})$ and
$SO_{2n+1}(\mathbb{C})$, and we compute a generating function for their "stable
twisted Betti numbers". We also give a new proof of a result of Lehrer using
symmetric function theory.

Answering a question of Geoff Robinson, we compute the large n limiting
proportion of i(n,q)/q^[n^2/2], where i(n,q) denotes the number of involutions
in GL(n,q). We give similar results for the finite unitary, symplectic, and
orthogonal groups, in both odd and even characteristic. At the heart of this
work are certain new "sum=product" identities. Our selfcontained treatment of
the enumeration of involutions in even characteristic symplectic and orthogonal
groups may also be of interest.

Feit and Fine derived a generating function for the number of ordered pairs
of commuting n by n matrices over the finite field F_q. This has been reproved
and studied by Bryan and Morrison from the viewpoint of motivic
DonaldsonThomas theory. In this note we give a new proof of the FeitFine
result, and generalize it to the Lie algebra of finite unitary groups and to
the Lie algebra of odd characteristic finite symplectic groups. We extract some
asymptotic information from these generating functions. Finally, we derive
generating functions for the number of commuting nilpotent elements for the Lie
algebras of the finite general linear and unitary groups, and of odd
characteristic symplectic groups.

This is the fourth paper in a series. We prove a conjecture made
independently by Boston et al and Shalev. The conjecture asserts that there is
an absolute positive constant delta such that if G is a finite simple group
acting transitively on a set of size n > 1, then the proportion of derangements
in G is greater than delta. We show that with possibly finitely many
exceptions, one can take delta = .016. Indeed, we prove much stronger results
showing that for many actions, the proportion of derangements goes to 1 as n
increases and prove similar results for families of permutation
representations.

Motivated by analogous results for the symmetric group and compact Lie
groups, we study the distribution of the number of fixed vectors of a random
element of a finite classical group. We determine the limiting moments of these
distributions, and find exactly how large the rank of the group has to be in
order for the moment to stabilize to its limiting value. The proofs require a
subtle use of some qseries identities. We also point out connections with
orthogonal polynomials.

With ${\mathcal{Q}}_{q,n}$ the distribution of $n$ minus the rank of a matrix
chosen uniformly from the collection of all $n\times(n+m)$ matrices over the
finite field $\mathbb{F}_q$ of size $q\ge2$, and ${\mathcal{Q}}_q$ the
distributional limit of ${\mathcal{Q}}_{q,n}$ as $n\rightarrow\infty$, we apply
Stein's method to prove the total variation bound
$\frac{1}{8q^{n+m+1}}\leq\{\mathcal{Q}}_{q,n}{\mathcal{Q}}_q\_{\mathrm{TV}}\leq\frac{3}{q^{n+m+1}}$.
In addition, we obtain similar sharp results for the rank distributions of
symmetric, symmetric with zero diagonal, skew symmetric, skew centrosymmetric
and Hermitian matrices.

This is the third in a series of papers in which we prove a conjecture of
Boston and Shalev that the proportion of derangements (fixed point free
elements) is bounded away from zero for transitive actions of finite simple
groups on a set of size greater than one. This paper treats the case of
primitive subspace actions. It is also shown that if the dimension and
codimension of the subspace go to infinity, then the proportion of derangements
goes to one. Similar results are proved for elements in finite classical groups
in cosets of the simple group. The results in this paper have applications to
probabilistic generation of finite simple groups and maps between varieties
over finite fields.

A recent paper of Church, Ellenberg, and Farb uses topology and
representation theory of the symmetric group to prove enumerative results about
squarefree polynomials and Fstable maximal tori of the general linear group
over the algebraic closure of F_q. In this note, we use generating functions to
give elementary proofs of some of their results, and some extensions.

Consider a uniformly chosen random reduced decomposition of the longest
element in the symmetric group. It is known that the location of the first
transposition in this decomposition converges to the semicircle distribution.
In this note we provide a sharp error term for this result, using the
"comparison of generators" approach to Stein's method.

CohenLenstra heuristics for Jacobians of random graphs give rise to random
partitions. We connect these random partitions to the HallLittlewood
polynomials of symmetric function theory, and use this connection to give
combinatorial proofs of properties of these random partitions. In addition, we
use Markov chains to give an algorithm for generating these partitions.

We study the combinatorics of addition using balanced digits, deriving an
analog of Holte's "amazing matrix" for carries in usual addition. The
eigenvalues of this matrix for base b balanced addition of n numbers are found
to be 1,1/b,...,1/b^n, and formulas are given for its left and right
eigenvectors. It is shown that the left eigenvectors can be identified with
hyperoctahedral Foulkes characters, and that the right eigenvectors can be
identified with hyperoctahedral Eulerian idempotents. We also examine the
carries that occur when a column of balanced digits is added, showing this
process to be determinantal. The transfer matrix method and a serendipitous
diagonalization are used to study this determinantal process.

Many casinos routinely use mechanical card shuffling machines. We were asked
to evaluate a new product, a shelf shuffler. This leads to new probability, new
combinatorics and to some practical advice which was adopted by the
manufacturer. The interplay between theory, computing, and realworld
application is developed.

Let g be a random element of a finite classical group G, and let
\lambda_{z1}(g) denote the partition corresponding to the polynomial z1 in
the rational canonical form of g. As the rank of G tends to infinity,
\lambda_{z1}(g) tends to a partition distributed according to a CohenLenstra
type measure on partitions. We give sharp upper and lower bounds on the total
variation distance between the random partition \lambda_{z1}(g) and the
CohenLenstra type measure.

We compute generating functions for the sum of the realvalued character
degrees of the finite general linear and unitary groups, through symmetric
function computations. For the finite general linear group, we get a new
combinatorial proof that every realvalued character has FrobeniusSchur
indicator 1, and we obtain some qseries identities. For the finite unitary
group, we expand the generating function in terms of values of HallLittlewood
functions, and we obtain combinatorial expressions for the character degree
sums of realvalued characters with FrobeniusSchur indicator 1 or 1.

Using generating functions, we enumerate regular semisimple conjugacy classes
in the finite classical groups. For the general linear, unitary, and symplectic
groups this gives a different approach to known results; for the special
orthogonal groups the results are new.

We derive a new result for exponential approximation using Stein's method of
exchangeable pairs. As an application, an exponential limit theorem with error
term is derived for Tr(U)^2, where Tr(U) denotes the trace of a matrix chosen
from the Haar measure of the unitary group U(n,C).

Combining Stein's method with heat kernel techniques, we study the function
Tr(AO), where A is a fixed n by n real matrix over such that Tr(AA^t)=n, and O
is from the Haar measure of the orthogonal group O(n,R). It is shown that the
total variation distance of the random variable Tr(AO) to a standard normal
random variable is bounded by 2 * squareroot(2) /(n1), slightly improving the
constant in a bound of Meckes, which was obtained by completely different
methods.

The tools of zero biasing are adapted to yield a general result suitable for
analyzing the behavior of certain growth processes. The main theorem is applied
to prove central limit theorems, with explicit error terms in the L^1 metric,
for certain statistics of the Jack measure on partitions and for the number of
balls drawn in a PolyaEggenberger urn process.

John Holte [16] introduced a family of "amazing matrices" which give the
transition probabilities of "carries" when adding a list of numbers. It was
subsequently shown that these same matrices arise in the combinatorics of the
Veronese embedding of commutative algebra [4,6,7] and in the analysis of riffle
shuffling [6,7]. We find that the left eigenvectors of these matrices form the
Foulkes character table of the symmetric group and the right eigenvectors are
the Eulerian idempotents introduced by Loday [20] in work on Hochschild
homology. The connections give new closed formulae for Foulkes characters and
allow explicit computation of natural correlation functions in the original
carries problem.

Combining Stein's method with heat kernel techniques, we show that the trace
of the jth power of an element of U(n,C), USp(n,C) or SO(n,R) has a normal
limit with error term of order j/n. In contrast to previous works, here j may
be growing with n. The technique should prove useful in the study of the value
distribution of approximate eigenfunctions of Laplacians.

We develop cycle index generating functions for orthogonal groups in even
characteristic, and give some enumerative applications. A key step is the
determination of the values of the complex linearWeil characters of the finite
symplectic group, and their inductions to the general linear group, at
unipotent elements. We also define and study several natural probability
measures on integer partitions.

We define an analog of Plancherel measure for the set of rooted unlabeled
trees on n vertices, and a Markov chain which has this measure as its
stationary distribution. Using the combinatorics of commutation relations, we
show that order n^2 steps are necessary and suffice for convergence to the
stationary distribution.

Adding a column of numbers produces "carries" along the way. We show that
random digits produce a pattern of carries with a neat probabilistic
description: the carries form a onedependent determinantal point process. This
makes it easy to answer natural questions: How many carries are typical? Where
are they located? We show that many further examples, from combinatorics,
algebra and group theory, have essentially the same neat formulae, and that any
onedependent point process on the integers is determinantal. The examples give
a gentle introduction to the emerging fields of onedependent and determinantal
point processes.

We present explicit upper bounds for the number and size of conjugacy classes
in finite Chevalley groups and their variations. These results have been used
by many authors to study zeta functions associated to representations of finite
simple groups, random walks on Chevalley groups, the final solution to the Ore
conjecture about commutators in finite simple groups and other similar
problems. In this paper, we solve a strong version of the BostonShalev
conjecture on derangements in simple groups for most of the families of
primitive permutation group representations of finite simple groups (the
remaining cases are settled in two other papers of the authors and applications
are given in a third).