Search

We obtain sharp bounds on the convergence rate of Markov chains on irreducible representations of finite general linear, unitary, and symplectic groups (in both odd and even characteristic) given by tensoring with Weil representations., Comment: 28 pages

We use representation theory of the symmetric group S_n to prove Poisson limit theorems for the distribution of fixed points for three types of non-uniform permutations. First, we give results for the commutator of g and x where g and x are uniform in S_n. Second, we give results for the commutator of g and x where g in uniform in S_n and x is fixed. Third, we give results for permutations obtained by multiplying n*log(n)/i + cn many random i-cycles. Some of our results are known by other, quite different, methods., Comment: 16 pages.This is a major rewriting. Thanks to Jimmy He a conjecture from the previous draft is proved. We also incorporate feedback from Alex Miller

We prove that if G is a sufficiently large finite almost simple group of Lie type, then given a fixed nontrivial element x in G and a coset of G modulo its socle, the probability that x and a random element of the coset generate a subgroup containing the socle is uniformly bounded away from 0 (and goes to 1 if the field size goes to infinity). This is new even if G is simple. Together with results of Lucchini and Burness--Guralnick--Harper, this proves a conjecture of Lucchini and has an application to profinite groups. A key step in the proof is the determination of the limits for the proportion of elements in a classical group which fix no subspace of any bounded dimension., Comment: 26 pages

In work on the two alleles Moran model, Ewens showed that the stationary distribution for the number of genes of one type can be approximated by a Beta distribution. In this short note, we provide a sharp error term for this approximation. We show that this example fits perfectly into Doebler's framework for Beta approximation by Stein's method of exchangeable pairs., Comment: 7 pages

A paper by Boros, Little, Moll, Mosteig, and Stanley relates properties of a map defined on the space of rational functions to Eulerian polynomials. We link their work to the carries Markov chain, giving a new proof and slight generalization of one of their results., Comment: 6 pages

We study the conjugacy classes of the classical affine groups. We derive generating functions for the number of classes analogous to formulas of Wall and the authors for the classical groups. We use these to get good upper bounds for the number of classes. These naturally come up as difficult cases in the study of the non-coprime k(GV) problem of Brauer., Comment: 35 pages

Motivated by questions in algebraic geometry, Yifeng Huang recently derived generating functions for counting mutually annihilating matrices and mutually annihilating nilpotent matrices over a finite field. We give a different derivation of his results using statistical properties of random partitions chosen from the Cohen-Lenstra measure., Comment: 6 pages

In this expository article, we highlight the direct connection between card shuffling and the functions known as $P$-partitions that come from algebraic combinatorics. While many (but not all) of the results we discuss are known, we give a unified treatment. The key idea is this: the probability of obtaining a permutation $\pi$ from shelf shuffling is the probability that a random $P$-partition is sorted by $\pi$, and the probability of obtaining $\pi$ from riffle shuffling is the probability that a random $P$-partition is sorted by $\pi^{-1}$., Comment: 22 pages, 4 tables

We study the joint distribution of descents and sign for elements of the symmetric group and the hyperoctahedral group (Coxeter groups of types $A$ and $B$). For both groups, this has an application to riffle shuffling: for large decks of cards the sign is close to random after a single shuffle. In both groups, we derive generating functions for the Eulerian distribution refined according to sign, and use them to give two proofs of central limit theorems for positive and negative Eulerian numbers., Comment: 25 pages

The number of peaks of a random permutation is known to be asymptotically normal. We give a new proof of this and prove a central limit theorem for the distribution of peaks in a fixed conjugacy class of the symmetric group. Our technique is to apply ``analytic combinatorics'' to study a complicated but exact generating function for peaks in a given conjugacy class., Comment: 21 pages, 1 figure

Narayana numbers appear in many places in combinatorics and probability, and it is known that they are asymptotically normal. Using Stein's method of exchangeable pairs, we provide an error of approximation in total variation to a symmetric binomial distribution of order~$n^{-1}$, which also implies a Kolmogorov bound of order~$n^{-1/2}$ for the normal approximation. Our exchangeable pair is based on a birth-death chain and has remarkable properties, which allow us to perform some otherwise tricky moment computations. Although our main interest is in Narayana numbers, we show that our main abstract result can also give improved convergence rates for the Poisson-binomial and the hypergeometric distributions., Comment: 13 pages

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., Comment: 21 pages, minor revisions to Section 5

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., Comment: 23 pages

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., Comment: 27 pages

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., Comment: 28 pages, to appear in Journal of Group Theory. We simplified the treatment of the unitary groups, shortening the paper by 3 pages

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., Comment: 24 pages

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., Comment: 17 pages

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., Comment: 13 pages

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.

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., Comment: 10 pages

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., Comment: 18 pages

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.

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., Comment: 29 pages

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., Comment: 59 pages, final version, to appear in Transactions of AMS

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., Comment: Published at http://dx.doi.org/10.1214/13-AOP889 in the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

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., Comment: 19 pages

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)., Comment: 14 pages

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., Comment: 12 pages

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., Comment: Published in at http://dx.doi.org/10.1214/12-AAP884 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

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., Comment: 15 pages

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., Comment: 21 pages. Error in one term of the bound of the main theorem has been corrected, resulting in some changes to the bound for urn process

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., Comment: 17 pages

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., Comment: 30 pages

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., Comment: 13 pages

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., Comment: 34 pages

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)., Comment: 53 pages

The "carries" when n random numbers are added base b form a Markov chain with an "amazing" transition matrix determined by Holte. This same Markov chain occurs in following the number of descents or rising sequences when n cards are repeatedly riffle shuffled. We give generating and symmetric function proofs and determine the rate of convergence of this Markov chain to stationarity. Similar results are given for type B shuffles. We also develop connections with Gaussian autoregressive processes and the Veronese mapping of commutative algebra., Comment: 23 pages

The number of ``carries'' when $n$ random integers are added forms a Markov chain [23]. We show that this Markov chain has the same transition matrix as the descent process when a deck of $n$ cards is repeatedly riffle shuffled. This gives new results for the statistics of carries and shuffling., Comment: 16 pages

Stein's method is used to study the trace of a random element from a compact Lie group or symmetric space. Central limit theorems are proved using very little information: character values on a single element and the decomposition of the square of the trace into irreducible components. This is illustrated for Lie groups of classical type and Dyson's circular ensembles. The approach in this paper will be useful for the study of higher dimensional characters, where normal approximations need not hold., Comment: 22 pages; same results, but more efficient exposition in Section 3.1

It is shown that the combinatorics of commutation relations is well suited for analyzing the convergence rate of certain Markov chains. Examples studied include random walk on irreducible representations, a local random walk on partitions whose stationary distribution is the Ewens distribution, and some birth-death chains., Comment: 37 pages; referee suggestions implemented, discuss up-down chains as well, slightly better bounds in Props. 5.6, 7.6

The number of fixed points of a random permutation of 1,2,...,n has a limiting Poisson distribution. We seek a generalization, looking at other actions of the symmetric group. Restricting attention to primitive actions, a complete classification of the limiting distributions is given. For most examples, they are trivial -- almost every permutation has no fixed points. For the usual action of the symmetric group on k-sets of 1,2,...,n, the limit is a polynomial in independent Poisson variables. This exhausts all cases. We obtain asymptotic estimates in some examples, and give a survey of related results., Comment: 30 pages

Random walk on the irreducible representations of the symmetric and general linear groups is studied. A separation distance cutoff is proved and the exact separation distance asymptotics are determined. A key tool is a method for writing the multiplicities in the Kronecker tensor powers of a fixed representation as a sum of non-negative terms. Connections are made with the Lagrange-Sylvester interpolation approach to Markov chains., Comment: 20 pages