Showing 1–50 of 82 results for author: Fulman, J

Tensor product Markov chains and Weil representations

Authors: Jason Fulman, Michael Larsen, Pham Huu Tiep

Abstract: 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. 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. △ Less

Submitted 17 July, 2024; originally announced July 2024.

Comments: 28 pages

Fixed points of non-uniform permutations and representation theory of the symmetric group

Authors: Jason Fulman

Abstract: 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 obtaine… ▽ More 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. △ Less

Submitted 27 June, 2024; v1 submitted 17 June, 2024; originally announced June 2024.

Comments: 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

Probabilistic Generation of Finite Almost Simple Groups

Authors: Jason Fulman, Daniele Garzoni, Robert M. Guralnick

Abstract: 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… ▽ More 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. △ Less

Submitted 25 March, 2024; originally announced March 2024.

Comments: 26 pages

Beta approximation for the two alleles Moran model by Stein's method

Authors: Jason Fulman

Abstract: 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. 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. △ Less

Submitted 25 July, 2023; originally announced July 2023.

Comments: 7 pages

Carries and a map on the space of rational functions

Authors: Jason Fulman

Abstract: 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. 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. △ Less

Submitted 8 June, 2023; originally announced June 2023.

Comments: 6 pages

Enumeration of conjugacy classes in affine groups

Authors: Jason Fulman, Robert Guralnick

Abstract: 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. 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. △ Less

Submitted 30 December, 2021; originally announced December 2021.

Comments: 35 pages

Journal ref: Alg. Number Th. 18 (2024) 1189-1219

Cohen Lenstra Partitions and Mutually Annihilating Matrices over a Finite Field

Authors: Jason Fulman, Robert Guralnick

Abstract: 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. 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. △ Less

Submitted 17 November, 2021; originally announced November 2021.

Comments: 6 pages

Card shuffling and $P$-partitions

Authors: Jason Fulman, T. Kyle Petersen

Abstract: 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 $π$ from shelf shuffling is the probability that a random $P$-partition is s… ▽ More 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 $π$ from shelf shuffling is the probability that a random $P$-partition is sorted by $π$, and the probability of obtaining $π$ from riffle shuffling is the probability that a random $P$-partition is sorted by $π^{-1}$. △ Less

Submitted 27 April, 2021; v1 submitted 3 April, 2020; originally announced April 2020.

Comments: 22 pages, 4 tables

MSC Class: 05A05; 60C05

On the joint distribution of descents and signs of permutations

Authors: Jason Fulman, Gene B. Kim, Sangchul Lee, T. Kyle Petersen

Abstract: 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,… ▽ More 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. △ Less

Submitted 3 February, 2021; v1 submitted 9 October, 2019; originally announced October 2019.

Comments: 25 pages

Central limit theorem for peaks of a random permutation in a fixed conjugacy class of $S_n$

Authors: Jason Fulman, Gene B. Kim, Sangchul Lee

Abstract: 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. 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. △ Less

Submitted 3 February, 2019; originally announced February 2019.

Comments: 21 pages, 1 figure

Stein's method and Narayana numbers

Authors: Jason Fulman, Adrian Röllin

Abstract: 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… ▽ More 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. △ Less

Submitted 11 May, 2020; v1 submitted 28 August, 2018; originally announced August 2018.

Comments: 13 pages

Random Partitions and Cohen-Lenstra Heuristics

Authors: Jason Fulman, Nathan Kaplan

Abstract: 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. 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. △ Less

Submitted 24 January, 2019; v1 submitted 9 March, 2018; originally announced March 2018.

Comments: 21 pages, minor revisions to Section 5

Journal ref: Ann. Comb. 23 (2019), no. 2, 295-315

Enumeration of Commuting Pairs in Lie Algebras over Finite Fields

Authors: Jason Fulman, Robert Guralnick

Abstract: 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 charac… ▽ More 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. △ Less

Submitted 16 November, 2016; originally announced November 2016.

Comments: 23 pages

Generating functions and statistics on spaces of maximal tori in classical Lie groups

Authors: Jason Fulman, Rita Jimenez Rolland, Jennifer C. H. Wilson

Abstract: 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énez Rolland--Wilson for "polynomial" statistics on these spaces, and we compute explicit formulas for their stable values. We d… ▽ More 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énez 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. △ Less

Submitted 18 March, 2017; v1 submitted 21 October, 2016; originally announced October 2016.

Comments: 27 pages

Journal ref: New York J. Math. 23 (2017) 165-191

Asymptotics of the number of involutions in finite classical groups

Authors: Jason Fulman, Robert Guralnick, Dennis Stanton

Abstract: 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 o… ▽ More 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. △ Less

Submitted 22 February, 2017; v1 submitted 10 February, 2016; originally announced February 2016.

Comments: 28 pages, to appear in Journal of Group Theory. We simplified the treatment of the unitary groups, shortening the paper by 3 pages

Derangements in finite classical groups for actions related to extension field and imprimitive subgroups and the solution of the Boston-Shalev conjecture

Authors: Jason Fulman, Robert Guralnick

Abstract: 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… ▽ More 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. △ Less

Submitted 31 July, 2015; originally announced August 2015.

Comments: 24 pages

On the distribution of the number of fixed vectors for the finite classical groups

Authors: Jason Fulman, Dennis Stanton

Abstract: 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 som… ▽ More 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. △ Less

Submitted 23 May, 2015; originally announced May 2015.

Comments: 17 pages

A generating function approach to counting theorems for square-free polynomials and maximal tori

Authors: Jason Fulman

Abstract: 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. 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. △ Less

Submitted 13 October, 2014; originally announced October 2014.

Comments: 13 pages

Stein's method, semicircle distribution, and reduced decompositions of the longest element in the symmetric group

Authors: Jason Fulman, Larry Goldstein

Abstract: 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. 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. △ Less

Submitted 5 May, 2014; originally announced May 2014.

Hall-Littlewood polynomials and Cohen-Lenstra heuristics for Jacobians of random graphs

Authors: Jason Fulman

Abstract: 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. 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. △ Less

Submitted 3 March, 2014; originally announced March 2014.

Comments: 10 pages

Combinatorics of balanced carries

Authors: Persi Diaconis, Jason Fulman

Abstract: 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 characte… ▽ More 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. △ Less

Submitted 19 September, 2013; originally announced September 2013.

Comments: 18 pages

Cohen-Lenstra heuristics and random matrix theory over finite fields

Authors: Jason Fulman

Abstract: Let g be a random element of a finite classical group G, and let λ_{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, λ_{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 parti… ▽ More Let g be a random element of a finite classical group G, and let λ_{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, λ_{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 λ_{z-1}(g) and the Cohen-Lenstra type measure. △ Less

Submitted 2 July, 2013; originally announced July 2013.

Generating functions for real character degree sums of finite general linear and unitary groups

Authors: Jason Fulman, C. Ryan Vinroot

Abstract: 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 generatin… ▽ More 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. △ Less

Submitted 31 May, 2013; originally announced June 2013.

Comments: 29 pages

Derangements in Subspace Actions of Finite Classical Groups

Authors: Jason Fulman, Robert Guralnick

Abstract: 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 i… ▽ More 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. △ Less

Submitted 14 April, 2015; v1 submitted 21 March, 2013; originally announced March 2013.

Comments: 59 pages, final version, to appear in Transactions of AMS

Stein's method and the rank distribution of random matrices over finite fields

Authors: Jason Fulman, Larry Goldstein

Abstract: 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… ▽ More 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. △ Less

Submitted 14 May, 2015; v1 submitted 2 November, 2012; originally announced November 2012.

Comments: 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)

Report number: IMS-AOP-AOP889

Journal ref: Annals of Probability 2015, Vol. 43, No. 3, 1274-1314

The number of regular semisimple conjugacy classes in the finite classical groups

Authors: Jason Fulman, Robert Guralnick

Abstract: 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. 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. △ Less

Submitted 14 September, 2012; originally announced September 2012.

Comments: 19 pages

Exponential approximation and Stein's method of exchangeable pairs

Authors: Jason Fulman, Nathan Ross

Abstract: 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). 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). △ Less

Submitted 20 July, 2012; originally announced July 2012.

Comments: 14 pages

Stein's method, heat kernel, and linear functions on the orthogonal groups

Authors: Jason Fulman, Adrian Röllin

Abstract: 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… ▽ More 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. △ Less

Submitted 13 September, 2011; originally announced September 2011.

Comments: 12 pages

Analysis of casino shelf shuffling machines

Authors: Persi Diaconis, Jason Fulman, Susan Holmes

Abstract: 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. 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. △ Less

Submitted 23 July, 2013; v1 submitted 14 July, 2011; originally announced July 2011.

Comments: 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)

Report number: IMS-AAP-AAP884

Journal ref: Annals of Applied Probability 2013, Vol. 23, No. 4, 1692-1720

Foulkes Characters, Eulerian Idempotents, and an Amazing Matrix

Authors: Persi Diaconis, Jason Fulman

Abstract: 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 charac… ▽ More 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. △ Less

Submitted 25 February, 2011; originally announced February 2011.

Comments: 15 pages

Zero biasing and growth processes

Authors: Jason Fulman, Larry Goldstein

Abstract: 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. 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. △ Less

Submitted 13 May, 2011; v1 submitted 22 October, 2010; originally announced October 2010.

Comments: 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

Stein's method, heat kernel, and traces of powers of elements of compact Lie groups

Authors: Jason Fulman

Abstract: 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. 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. △ Less

Submitted 7 May, 2010; originally announced May 2010.

Comments: 17 pages

Cycle indices for finite orthogonal groups of even characteristic

Authors: Jason Fulman, Jan Saxl, Pham Huu Tiep

Abstract: 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 partit… ▽ More 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. △ Less

Submitted 15 April, 2010; originally announced April 2010.

Comments: 30 pages

A sharp analysis of the mixing time for random walk on rooted trees

Authors: Jason Fulman

Abstract: 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. 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. △ Less

Submitted 7 August, 2009; originally announced August 2009.

Comments: 13 pages

On adding a list of numbers (and other one-dependent determinantal processes)

Authors: Alexei Borodin, Persi Diaconis, Jason Fulman

Abstract: 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 theo… ▽ More 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. △ Less

Submitted 23 April, 2009; originally announced April 2009.

Comments: 34 pages

Bounds on the number and sizes of conjugacy classes in finite Chevalley groups with Applications to Derangements

Authors: Jason Fulman, Robert Guralnick

Abstract: 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… ▽ More 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). △ Less

Submitted 12 February, 2009; originally announced February 2009.

Comments: 53 pages

MSC Class: 20G40; 20B15.

Carries, shuffling, and symmetric functions

Authors: Persi Diaconis, Jason Fulman

Abstract: 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 resu… ▽ More 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. △ Less

Submitted 1 February, 2009; originally announced February 2009.

Comments: 23 pages

MSC Class: 60C05; 60J10; 05E05

Carries, Shuffling and An Amazing Matrix

Authors: Persi Diaconis, Jason Fulman

Abstract: 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. 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. △ Less

Submitted 22 June, 2008; originally announced June 2008.

Comments: 16 pages

Stein's Method and Characters of Compact Lie Groups

Authors: Jason Fulman

Abstract: 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… ▽ More 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. △ Less

Submitted 23 June, 2008; v1 submitted 12 June, 2008; originally announced June 2008.

Comments: 22 pages; same results, but more efficient exposition in Section 3.1

Commutation relations and Markov chains

Authors: Jason Fulman

Abstract: 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. 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. △ Less

Submitted 20 January, 2008; v1 submitted 9 December, 2007; originally announced December 2007.

Comments: 37 pages; referee suggestions implemented, discuss up-down chains as well, slightly better bounds in Props. 5.6, 7.6

On fixed points of permutations

Authors: Persi Diaconis, Jason Fulman, Robert Guralnick

Abstract: 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… ▽ More 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. △ Less

Submitted 20 August, 2007; originally announced August 2007.

Comments: 30 pages

MSC Class: 20B30; 20B35; 05A16; 60C07

Separation cutoffs for random walk on irreducible representations

Authors: Jason Fulman

Abstract: 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 int… ▽ More 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. △ Less

Submitted 10 March, 2007; originally announced March 2007.

Comments: 20 pages

MSC Class: 60C05; 20P05

Convergence rates of random walk on irreducible representations of finite groups

Authors: Jason Fulman

Abstract: Random walk on the set of irreducible representations of a finite group is investigated. For the symmetric and general linear groups, a sharp convergence rate bound is obtained and a cutoff phenomenon is proved. As related results, an asymptotic description of Plancherel measure of the finite general linear groups is given, and a connection of these random walks with quantum computing is noted. Random walk on the set of irreducible representations of a finite group is investigated. For the symmetric and general linear groups, a sharp convergence rate bound is obtained and a cutoff phenomenon is proved. As related results, an asymptotic description of Plancherel measure of the finite general linear groups is given, and a connection of these random walks with quantum computing is noted. △ Less

Submitted 18 October, 2006; v1 submitted 17 July, 2006; originally announced July 2006.

Comments: The main change is an expanded discussion of motivation of these random walks (requested by a referee). A connection with quantum computing is also noted

Exponential Approximation by Stein's Method and Spectral Graph Theory

Authors: Sourav Chatterjee, Jason Fulman, Adrian Rollin

Abstract: General Berry-Esseen bounds are developed for the exponential distribution using Stein's method. As an application, a sharp error term is obtained for Hora's result that the spectrum of the Bernoulli-Laplace Markov chain has an exponential limit. This is the first use of Stein's method to study the spectrum of a graph with a non-normal limit. General Berry-Esseen bounds are developed for the exponential distribution using Stein's method. As an application, a sharp error term is obtained for Hora's result that the spectrum of the Bernoulli-Laplace Markov chain has an exponential limit. This is the first use of Stein's method to study the spectrum of a graph with a non-normal limit. △ Less

Submitted 4 October, 2008; v1 submitted 19 May, 2006; originally announced May 2006.

Comments: 26 pages; this is a major revision, with an additional co-author (A. Rollin) and sharp bounds

MSC Class: 60C05; 60F05

Power series coefficients for probabilities in finite classical groups

Authors: John R. Britnell, Jason Fulman

Abstract: It is shown that a wide range of probabilities and limiting probabilities in finite classical groups have integral coefficients when expanded as a power series in 1/q. Moreover it is proved that the coefficients of the limiting probabilities in the general linear and unitary cases are equal modulo 2. The rate of stabilization of the finite dimensional coefficients as the dimension increases is d… ▽ More It is shown that a wide range of probabilities and limiting probabilities in finite classical groups have integral coefficients when expanded as a power series in 1/q. Moreover it is proved that the coefficients of the limiting probabilities in the general linear and unitary cases are equal modulo 2. The rate of stabilization of the finite dimensional coefficients as the dimension increases is discussed. △ Less

Submitted 15 November, 2005; originally announced November 2005.

Comments: 34 pages

MSC Class: 05E15; 20G40

Stein's Method and Random Character Ratios

Authors: Jason Fulman

Abstract: Stein's method is used to prove limit theorems for random character ratios. Tools are developed for four types of structures: finite groups, Gelfand pairs, twisted Gelfand pairs, and association schemes. As one example an error term is obtained for a central limit theorem of Kerov on the spectrum of the Cayley graph of the symmetric group generated by i-cycles, or equivalently for the character… ▽ More Stein's method is used to prove limit theorems for random character ratios. Tools are developed for four types of structures: finite groups, Gelfand pairs, twisted Gelfand pairs, and association schemes. As one example an error term is obtained for a central limit theorem of Kerov on the spectrum of the Cayley graph of the symmetric group generated by i-cycles, or equivalently for the character ratio of a Plancherel distributed representation on an i-cycle. Other main examples include an error term for a central limit theorem of Ivanov on character ratios of random projective representations of the symmetric group, and a new central limit theorem for the spectrum of certain graphs whose vertices are the set of perfect matchings on 2n symbols. The error terms in the resulting limit theorems are typically O(n^{-1/4}) or better. The results are obtained with remarkably little information: a character formula for a single representation close to the trivial representation and estimates on two step transition probabilities of a random walk. Although the limit theorems stated in this paper are all for the case of normal approximation, many of the tools developed are quite general. Indeed, both the construction of an exchangeable pair used for Stein's method and lemmas computing certain moments are useful for arbitrary distributional approximation. △ Less

Submitted 16 August, 2005; originally announced August 2005.

Comments: 52 pages

An Inductive Proof of the Berry-Esseen Theorem for Character Ratios

Authors: Jason Fulman

Abstract: Bolthausen used a variation of Stein's method to give an inductive proof of the Berry-Esseen theorem for sums of independent, identically distributed random variables. We modify this technique to prove a Berry-Esseen theorem for character ratios of a random representation of the symmetric group on transpositions. An analogous result is proved for Jack measure on partitions. Bolthausen used a variation of Stein's method to give an inductive proof of the Berry-Esseen theorem for sums of independent, identically distributed random variables. We modify this technique to prove a Berry-Esseen theorem for character ratios of a random representation of the symmetric group on transpositions. An analogous result is proved for Jack measure on partitions. △ Less

Submitted 8 August, 2006; v1 submitted 11 March, 2005; originally announced March 2005.

Comments: revised version (main modification to the proof of Theorem 2.5)

Stein's Method and Minimum Parsimony Distance after Shuffles

Authors: Jason Fulman

Abstract: Motivated by Bourque and Pevzner's simulation study of the parsimony method for studying genome rearrangement, Berestycki and Durrett used techniques from random graph theory to prove that the minimum parsimony distance after iterating the random transposition shuffle undergoes a transition from Poisson to normal behavior. This paper establishes an analogous result for minimum parsimony distance… ▽ More Motivated by Bourque and Pevzner's simulation study of the parsimony method for studying genome rearrangement, Berestycki and Durrett used techniques from random graph theory to prove that the minimum parsimony distance after iterating the random transposition shuffle undergoes a transition from Poisson to normal behavior. This paper establishes an analogous result for minimum parsimony distance after iterates of riffle shuffles or iterates of riffle shuffles and cuts. The analysis is elegant and uses different tools: Stein's method and generating functions. A useful technique which emerges is that of making a problem more tractable by adding extra symmetry, then using Stein's method to exploit the symmetry in the modified problem, and from this deducing information about the original problem. △ Less

Submitted 29 October, 2004; originally announced October 2004.

Comments: 23 pages

Martingales and character ratios

Authors: Jason Fulman

Abstract: Some general connections between martingales and character ratios of finite groups are developed. As an application we sharpen the convergence rate in a central limit theorem for the character ratio of a random representation of the symmetric group on transpositions. A generalization of these results is given for Jack measure on partitions. We also give a probabilistic proof of a result of Burns… ▽ More Some general connections between martingales and character ratios of finite groups are developed. As an application we sharpen the convergence rate in a central limit theorem for the character ratio of a random representation of the symmetric group on transpositions. A generalization of these results is given for Jack measure on partitions. We also give a probabilistic proof of a result of Burnside and Brauer on the decomposition of tensor products. △ Less

Submitted 25 February, 2004; originally announced February 2004.

Comments: 22 pages

Stein's Method, Jack Measure, and the Metropolis Algorithm

Authors: Jason Fulman

Abstract: The one parameter family of Jack(alpha) measures on partitions is an important discrete analog of Dyson's beta ensembles of random matrix theory. Except for special values of alpha=1/2,1,2 which have group theoretic interpretations, the Jack(alpha) measure has been difficult if not intractable to analyze. This paper proves a central limit theorem (with an error term) for Jack(alpha) measure whic… ▽ More The one parameter family of Jack(alpha) measures on partitions is an important discrete analog of Dyson's beta ensembles of random matrix theory. Except for special values of alpha=1/2,1,2 which have group theoretic interpretations, the Jack(alpha) measure has been difficult if not intractable to analyze. This paper proves a central limit theorem (with an error term) for Jack(alpha) measure which works for arbitrary values of alpha. For alpha=1 we recover a known central limit theorem on the distribution of character ratios of random representations of the symmetric group on transpositions. The case alpha=2 gives a new central limit theorem for random spherical functions of a Gelfand pair. The proof uses Stein's method and has interesting ingredients: an intruiging construction of an exchangeable pair, properties of Jack polynomials, and work of Hanlon relating Jack polynomials to the Metropolis algorithm. △ Less

Submitted 2 July, 2004; v1 submitted 17 November, 2003; originally announced November 2003.

Comments: very minor revisions; fix a few misprints and update bibliography