• ### Random Partitions and Cohen-Lenstra Heuristics(1803.03722)

March 9, 2018 math.CO, math.PR, math.NT
We investigate combinatorial properties of a family of probability distributions on finite abelian p-groups. This family includes several well-known distributions as specializations. These specializations have been studied in the context of Cohen-Lenstra heuristics and cokernels of families of random p-adic matrices.
• ### Generating functions and statistics on spaces of maximal tori in classical Lie groups(1610.06816)

March 18, 2017 math.AT, math.CO, math.RT
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 Church--Ellenberg--Farb and Jim\'enez Rolland--Wilson 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.
• ### Asymptotics of the number of involutions in finite classical groups(1602.03611)

Feb. 22, 2017 math.CO, math.GR
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 self-contained treatment of the enumeration of involutions in even characteristic symplectic and orthogonal groups may also be of interest.
• ### Enumeration of Commuting Pairs in Lie Algebras over Finite Fields(1611.05499)

Nov. 16, 2016 math.CO, math.GR
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 Donaldson-Thomas theory. In this note we give a new proof of the Feit-Fine 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.
• ### Derangements in finite classical groups for actions related to extension field and imprimitive subgroups and the solution of the Boston-Shalev conjecture(1508.00039)

July 31, 2015 math.CO, math.GR
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.
• ### On the distribution of the number of fixed vectors for the finite classical groups(1505.06383)

May 23, 2015 math.CO, math.GR
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 q-series identities. We also point out connections with orthogonal polynomials.
• ### Stein's method and the rank distribution of random matrices over finite fields(1211.0504)

May 14, 2015 math.CO, math.PR
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.
• ### Derangements in Subspace Actions of Finite Classical Groups(1303.5480)

April 14, 2015 math.CO, math.GR
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 generating function approach to counting theorems for square-free polynomials and maximal tori(1410.3540)

Oct. 14, 2014 math.AT, math.CO, math.RT
A recent paper of Church, Ellenberg, and Farb uses topology and representation theory of the symmetric group to prove enumerative results about square-free polynomials and F-stable 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.
• ### Stein's method, semicircle distribution, and reduced decompositions of the longest element in the symmetric group(1405.1088)

May 5, 2014 math.CO, math.PR
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.
• ### Hall-Littlewood polynomials and Cohen-Lenstra heuristics for Jacobians of random graphs(1403.0473)

March 3, 2014 math.CO, math.NT
Cohen-Lenstra heuristics for Jacobians of random graphs give rise to random partitions. We connect these random partitions to the Hall-Littlewood 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.
• ### Combinatorics of balanced carries(1309.5116)

Sept. 19, 2013 math.CO, math.PR
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.
• ### Analysis of casino shelf shuffling machines(1107.2961)

July 23, 2013 math.CO, math.PR
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 real-world application is developed.
• ### Cohen-Lenstra heuristics and random matrix theory over finite fields(1307.0879)

July 2, 2013 math.CO, math.NT
Let g be a random element of a finite classical group G, and let \lambda_{z-1}(g) denote the partition corresponding to the polynomial z-1 in the rational canonical form of g. As the rank of G tends to infinity, \lambda_{z-1}(g) tends to a partition distributed according to a Cohen-Lenstra type measure on partitions. We give sharp upper and lower bounds on the total variation distance between the random partition \lambda_{z-1}(g) and the Cohen-Lenstra type measure.
• ### Generating functions for real character degree sums of finite general linear and unitary groups(1306.0031)

May 31, 2013 math.CO, math.RT, math.GR
We compute generating functions for the sum of the real-valued 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 real-valued character has Frobenius-Schur indicator 1, and we obtain some q-series identities. For the finite unitary group, we expand the generating function in terms of values of Hall-Littlewood functions, and we obtain combinatorial expressions for the character degree sums of real-valued characters with Frobenius-Schur indicator 1 or -1.
• ### The number of regular semisimple conjugacy classes in the finite classical groups(1209.3345)

Sept. 15, 2012 math.CO, math.GR
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.
• ### Exponential approximation and Stein's method of exchangeable pairs(1207.5073)

July 20, 2012 math.CO, math.PR
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).
• ### Stein's method, heat kernel, and linear functions on the orthogonal groups(1109.2975)

Sept. 14, 2011 math.CO, math.PR
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) /(n-1), slightly improving the constant in a bound of Meckes, which was obtained by completely different methods.
• ### Zero biasing and growth processes(1010.4759)

May 13, 2011 math.CO, math.PR
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 Polya-Eggenberger urn process.
• ### Foulkes Characters, Eulerian Idempotents, and an Amazing Matrix(1102.5159)

Feb. 25, 2011 math.CO, math.RT
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.
• ### Stein's method, heat kernel, and traces of powers of elements of compact Lie groups(1005.1306)

May 7, 2010 math-ph, math.MP, math.CO, math.PR
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.
• ### Cycle indices for finite orthogonal groups of even characteristic(1004.2678)

April 15, 2010 math.CO, math.RT, math.GR
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 linear-Weil 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.
• ### A sharp analysis of the mixing time for random walk on rooted trees(0908.1141)

Aug. 8, 2009 math.CO, math.PR
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.
• ### On adding a list of numbers (and other one-dependent determinantal processes)(0904.3740)

April 23, 2009 math.CO, math.PR
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 one-dependent 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 one-dependent point process on the integers is determinantal. The examples give a gentle introduction to the emerging fields of one-dependent and determinantal point processes.
• ### Bounds on the number and sizes of conjugacy classes in finite Chevalley groups with Applications to Derangements(0902.2238)

Feb. 13, 2009 math.CO, math.GR
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 Boston-Shalev 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).