Abstract
John Holte (Am. Math. Mon. 104:138–149, 1997) 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 (Brenti and Welker, Adv. Appl. Math. 42:545–556, 2009; Diaconis and Fulman, Am. Math. Mon. 116:788–803, 2009; Adv. Appl. Math. 43:176–196, 2009) and in the analysis of riffle shuffling (Diaconis and Fulman, Am. Math. Mon. 116:788–803, 2009; Adv. Appl. Math. 43:176–196, 2009). 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 (Cyclic Homology, 1992) 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.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
When n numbers are added in the usual way, “carries” accrue along the way. For example, working base b=10, the display shows the carries along the top when n=3 ten-digit numbers are added:
Here the carries (reading right to left in italic print) are κ 0=0, κ 1=2, κ 2=1, κ 3=2,…. When n numbers are added, the carries can be 0,1,2,…,n−1. If the digits are chosen uniformly at random in {0,1,…,b−1}, it is easy to see that the carries form a Markov chain: the chance that the next carry is j given the past carries only depends on the last carry. Thus the distribution of carries is determined by the transition matrix
The carries process was studied by Holte [17] who showed
For example, when n=3, the matrix is
Holte found the eigenvalues, eigenvectors, and many amazing properties of these matrices.
Work of [4, 7, 8] shows that the same matrix arises in the analysis of the Gilbert–Shannon–Reeds method of shuffling cards and in the Hilbert series of the Veronese embedding of projective varieties.
The main results of the present paper identify a different area where the matrix appears. The left eigenvectors of the matrix are the Foulkes characters of the symmetric group. The right eigenvectors are the Eulerian idempotents that occur in the study of free Lie algebras and Hochschild homology. We obtain new closed-form expressions for these characters.
Section 2 gives background on Foulkes characters and presents some new results for left eigenvectors. Section 3 does the same for the right eigenvectors and applies some of the new formulae to the original carries process, giving the variance and covariance of the number of carries. Section 4 gives another connection between representation theory of the symmetric group (the RSK correspondence) and carries.
In follow-up work to the current paper, Novelli and Thibon [23] prove many of our results using the theory of noncommutative symmetric functions.
2 Foulkes characters
This section introduces the Foulkes characters of the symmetric group and some of their properties (Sect. 2.1). It shows that the Foulkes characters are the left eigenvectors of the transition matrix M of (1.1) (Sect. 2.2). This connection is used to prove a branching rule (from S n to S n−1) and a closed-form formula for Foulkes characters (Sect. 2.3).
2.1 Background on Foulkes characters
Foulkes characters were discovered by Foulkes [11] as part of the study of the descent patterns in the permutation group. They are developed in [19] and [18] gives a readable textbook treatment. Gessel and Reutenauer [15] use them to enumerate permutations by descents and conjugacy classes; see [9] for a probabilistic interpretation of these results. Stanley [28] uses Foulkes characters to develop enumerative results for alternating permutations by cycle type.
Recall that a permutation σ∈S n has a descent at i if σ(i+1)<σ(i). The set of places where descents occur is D(σ)⊆[n−1]. For example, if σ=4512376, D(σ)={2,6}. If U⊆[n−1] is any set, Foulkes suggested constructing a ribbon shape (also called a rim hook) R(U) beginning with a single box and sequentially adding the next box below the last box if i∈U, and to the left of the last box if i∉U, 1≤i≤n−1. Thus, if U={2,6}, boxes are built up as follows:
The final skew shape will have n boxes and be the lower rim of a partition α; in this example, α is 5,4,1, and the ribbon shape is 5,4,1\3:
Labeling the boxes in the ribbon shape by all ways they can be sequentially removed from α and reading this from right to left and top to bottom gives all permutations with the original U as descent set. For example, removing boxes in the order shown as
gives 1435672. The skew shape R(U) corresponding to U⊆[n−1] gives a skew character χ R(U): if R(U)=α\β and χ λ is an irreducible character of the symmetric group S n , the coefficient of χ λ in χ R(U) is 〈χ β⋅χ λ|χ α〉 (see [22, Sect. 1.7]). From the development above, the dimension of χ R(U) is the number of permutations with descent set U. Solomon [25, Sect. 6] describes a related construction of MacMahon in his work on Simon Newcomb’s problem.
For fixed k, 0≤k≤n−1, the Foulkes character χ n,k is defined as the sum of χ R(U) over all U with n−k−1 descents. It follows that the dimension of χ n,k is the Eulerian number A(n,k), the number of permutations with k descents. Foulkes showed that χ n,k(σ) only depends on σ through the number of cycles in σ. In particular,
Most importantly, letting \(\chi_{j}^{n,k}\) denote the value of the Foulkes character on permutations with j cycles (so the dimension \(\chi_{n}^{n,k}=A(n,k)\)), one has from p. 306 of [18] that
This, with the starting value \(\chi_{1}^{1,0}=1\), gives an efficient way to build a Foulkes character table. Let k=0,1,…,n−1 index the rows and j=n,n−1,…,1 index the columns. Table 1 gives the example when n=5.
Further properties of Foulkes characters appear in Kerber and Thürlings [19]:
Thus the χ n,k form a ℚ basis for the characters that only depends on the number of cycles. Hidden in the proof of (2.7): the hook character \(\chi^{i+1,1^{n-i-1}}\) is the only hook occurring in χ n,i and it occurs with multiplicity its degree \(\binom{n-1}{i}\). A related fact appears in Solomon [25, Theorem 4]. Kerber and Thürlings [19] further determine the permutation character for S n acting on {1,2,…,N}n:
has the decomposition
The χ n,k are usually not irreducible, and gives an interesting combinatorial rule for decomposing χ R(U) (and thus χ n,k).
Marty Isaacs conjectured that n! divides the determinant of the Foulkes character table. In fact, the following is true:
Proof
Construct an n×n matrix A from the (n−1)×(n−1) Foulkes character table by adding a left column consisting of the partial sums of the Eulerian numbers A(n,0),A(n,0)+A(n,1),…,n! and filling out the rest of the top row with zeros. Thus, when n=5,
The 4×4 matrix in the lower right corner is the Foulkes character table for n=4. The first column entries are the partial sums of the Eulerian numbers 1, 26, 66, 26, 1. In particular, the (1,1) entry is n!, so by induction the determinant of A is n!(n−1)!⋯2!.
The n×n Foulkes character table is constructed from A as follows: in A, subtract row 2 from row 1, then row 3 from row 2, and so on. The recurrence (2.3) shows this gives the n×n Foulkes character table. □
Marty Isaacs observes that while the {χ n,k} are not disjoint, they sum up to the regular character of S n ; see [25, Th. 2] for a proof. Alas, this does not seem to be enough to have the nice theory of supercharacters [1] carry over, but the parallels are intriguing. Further properties of Foulkes characters are given in Sect. 2.3 after the connection with the carries transition matrix is developed.
Rim hook characters are a basic construction of representation theory of S n ; see [3, 20] and the references there. They are also available for other Coxeter groups [25]. Foulkes’ innovation, showing that sums of these characters have interesting properties, has not been explored for general type.
2.2 The connection with carries
We noticed from Holte’s paper [17] that the matrix of left (row) eigenvectors for the carries Markov chain on {0,1,2,3,4} (e.g., adding 5 numbers) is
Comparing this with Table 1, the Foulkes character table, leads to the following result.
Theorem 2.1
Let \(v^{n}_{i,j}\) denote the jth entry of the ith left eigenvector of the carries matrix for addition of n numbers base b (here 0≤i,j≤n−1, and the eigenvalues are 1/b i). Then
Proof
The first case is that i=0. From [17], \(v^{n}_{0,j}=A(n,j)\). From the dimension formula, \(\chi^{n,n-j-1}_{n}=A(n,n-1-j)\). By symmetry of the Eulerian numbers, A(n,j)=A(n,n−1−j), so the theorem follows in the first case.
The second case is that j=n−1. By (2.2), \(\chi^{n,0}_{j}=(-1)^{n-j}\). Thus we need to show that \(v^{n}_{n-j,n-1}=(-1)^{n-j}\). By Holte’s formula for the left eigenvectors of the carries chain [17, p. 143], it follows that
The result now follows by induction, since
For the remaining cases, i>0 and j<n−1. By the recursive formula (2.3), it is enough to show that
for i>0, j<n−1. From p. 144 of [17],
Clearly,
which implies the result. □
2.3 Some consequences
In [17], Holte gave a closed formula for the left eigenfunctions,
Thus we get an apparently new formula for the Foulkes characters.
Corollary 2.2
In rereading Foulkes [11, Sect. 4], we found the formula (Theorem 4.1),
This seems a little less direct than Corollary 2.2. Corollary 2.2 gives a direct proof of the following restriction formula of Foulkes characters from S n to S n−1.
Corollary 2.3
[11, Corollary 4.6]
Remarks
We first learned Corollary 2.3 from Marty Isaacs, who both observed it and showed that it follows from Corollary 2.2. The well-known recursion formula for the Eulerian numbers A(n,k)=(k+1)A(n−1,k)+(n−k)A(n−1,k−1) is the special case of evaluation at the identity. Thus Corollary 2.3 represents a “categorification” of this recurrence.
Proof
The required formula translates to
From Corollary 2.2,
Combining the third and fifth terms using \(\binom{n}{r} + \binom{n}{r-1} = \binom{n+1}{r}\), one obtains
Adding and subtracting
yields
The penultimate equality used Corollary 2.2 and the final equality used the identity
□
3 Riffle shuffle idempotents and right eigenvectors of the carries matrix
This section simplifies Holte’s formula for the right eigenvectors of the carries matrix, and relates these eigenvectors to representation theory of the symmetric group (Sect. 3.1). The eigenfunctions are used to compute basic things about carries in Sect. 3.2.
3.1 Right eigenfunctions
To begin, let \(u^{n}_{j}(i)\) denote the value of the jth right eigenvector of the carries chain (0≤j≤n−1, eigenvalues 1/b j) evaluated at i (0≤i≤n−1). We also let s(n,k) be the Stirling number of the first kind, defined as (−1)n−k multiplied by the number of permutations on n symbols with k cycles. It can also be defined by the equation
Theorem 4 of Holte [17] shows that
where 00 is taken to be 1. Note that \(u_{j}^{n}(i)\) is a polynomial in i of degree j. For example, \(u_{0}^{n}(i)=1,\ u_{1}^{n}(i)=n(n-1-i)-\binom{n}{2}\).
The next theorem gives a simpler formula for \(u^{n}_{j}(i)\).
Theorem 3.1
Proof
By Theorem 4 of Holte [17], \(u^{n}_{j}(i)\) is n! multiplied by the i,j entry of the inverse of the matrix of left row eigenvectors. From this and (2.10), proving the first equality of the theorem is equivalent to proving that
Now
The third equality used (3.1), the fifth used the basic identity \(\sum_{i}\binom{a}{i}\binom{b}{n-i}=\binom{a+b}{n}\) [26, p. 12], and the final equality is from p. 147 of [17].
To prove the second equality of the theorem, write
and use (3.1). □
Remark
Let E n,k be elements of the symmetric group algebra defined by the equation
where d(w) denotes the number of descents of w. By work of Garsia and Reutenauer [13], these are orthogonal idempotents of the symmetric group algebra whose sum is the identity. They also arise in the theory of riffle shuffling [2] and in Hochschild homology [16]. Their images under the sign map are known as Eulerian idempotents. In this version, they were discovered by Gerstenhaber–Schack [14] to give Hodge decompositions of Hochschild homology. They have been developed by Loday [21] for cyclic homology. Patras [24] gives an unusual treatment involving decompositions of the n-cube into simplices. For a textbook treatment, see Weibel [29, Sect. 9.4.3].
The eigenvectors of the carries and descent matrix lift to eigenvectors of the full riffle shuffle matrix. These in turn are identified in Denham [6] and Diaconis–Pang–Ram [10].
Clearly, the value of E n,k on a permutation depends only on its number of descents. Letting E n,k (d) denote the value of E n,k on a permutation with d descents, we have the following corollary of Theorem 3.1.
Corollary 3.2
It would be nice to have a more conceptual proof of Corollary 3.2. The paper [23] is a development along these lines.
3.2 Applications
This section gives some applications of the explicit form of the right eigenvectors of the carries chain for the addition of n numbers base b. We note that another application (to lower bounding the convergence rate of the carries chain) appears in [8].
The transition matrix of the carries chain is viewed as a linear operator on functions in the usual way: Kf(x)=∑ y K(x,y)f(y). We let κ r denote the value of the carry from column r−1 to column r. We also recall that the covariance Cov(Z 1,Z 2) between two random variables Z 1,Z 2 is E(Z 1 Z 2)−E(Z 1)E(Z 2).
Proposition 3.3
Suppose that the carries chain is started from its stationary distribution π. Then for n≥2,
Proof
Since P(κ 0=i)=π(i),
By Theorem 3.1, \(u^{n}_{1}\) is a right eigenvector of the carries chain with eigenvalue 1/b. Dividing by −1/n, we have the eigenvector \(f(i)=i-\frac{n-1}{2}\),
It follows that
From [17] or [8], the stationary distribution of the carries chain is π(i)=A(n,i)/n! (here A(n,i) is the number of permutations on n symbols with i descents). It is known [5] that for n≥2 the mean and variance of the Eulerian numbers are \(\frac{n-1}{2}\) and \(\frac{n+1}{12}\). This, together with (3.2), gives
and the result follows since \(E(\kappa_{0})E(\kappa_{r})= (\frac{n-1}{2} )^{2}\), which is true since the chain started from its stationary distribution π. □
A similar calculation allows us to compute the covariance started from the state 0, as in the usual carries process.
Proposition 3.4
Suppose that the carries chain is started from 0, and that n≥2. Then
-
1.
\(E(\kappa_{s})= (1-\frac{1}{b^{s}} )\frac{n-1}{2}\).
-
2.
\(\textup{Var}(\kappa_{s})= (1-\frac{1}{b^{2s}} )\frac{n+1}{12}\).
-
3.
\(\textup{Cov}(\kappa_{s},\kappa_{s+r})=\frac{1}{b^{r}}\frac{n+1}{12} (1-\frac{1}{b^{2s}} )>0\).
Proof
Parts 1 and 2 are proved in Theorem 4.1 of [7]. For part 3, arguing as in the proof of Proposition 3.3,
By parts 1 and 2, this is equal to
□
The eigenvectors of the carries matrix can be used to give a simple proof that the sum of χ n,k gives the regular character. Holte [17] shows that if V is the matrix whose rows are left eigenvectors and U is the matrix whose columns are right eigenvectors, then VU=n!×I. Just looking at products involving the first column of U (which is identically one) we get that the χ n,k sum up to the regular character.
It is instructive to see the problems encountered in trying to use the available eigenstructure to bound the rate of convergence of the carries chain to its stationary distribution A(n,j)/n!. Let M b (i,j) be the transition matrix (1.1) corresponding to adding n numbers base b. Let \(M_{b}^{k}(i,j)\) be the kth power of this matrix. From elementary linear algebra,
where l a ,r a are the left and right eigenvectors of M b normed so that \(l_{0}(j)=\frac{A(n,j)}{n!}\) (and r 0(j)=1) for 0≤j≤n−1. Here
The total variation distance to stationarity, starting at i=0, after k steps is
From the formulae above,
While bounding this is feasible, it is a bit of a mess. In [8, Sect. 3], a different representation is used to prove that the carries chain is close to stationarity after order \(\frac{1}{2}\log_{b}(n)\) steps.
4 Carries and the RSK correspondence
In this section, we use the RSK correspondence to derive a generating function for descents after a b r-riffle shuffle on a deck of n cards. Recall that an a-riffle shuffle is given by first cutting the n cards into packet sizes k 1,…,k a with multinomial probability \(\frac{n!}{a^{n} \prod_{i} k_{i}!}\). The cards are then dropped one at a time with probability proportional to packet size. So if the packet sizes are X 1,…,X a at a given time, the next card drops from packet i with probability X i /(X 1+⋯+X a ). For further background on riffle shuffles, the reader can see [2].
By a main result of [7], the generating function for descents after a b r-riffle shuffle on a deck of n cards is equal to the generating function for the rth carry κ r when n numbers are added base b (and one can give another proof of Theorem 4.1 using Holte’s formula for P(κ r =i)).
Theorem 4.1
Let P(w) be the probability of w following a b r-riffle shuffle on a deck of n cards started at the identity, and let d(w) denote the number of descents of w. Then
Proof
Let w be a permutation produced by a b r riffle shuffle. The RSK correspondence associates to w a pair of standard Young tableaux (P(w),Q(w)) of the same shape. Moreover, there is a notion of descent set for standard Young tableaux, and by Lemma 7.23.1 of [27], the descent set of w is equal to the descent set of Q(w). It is known from [12] that if w is produced by a b r shuffle, then the chance that Q(w) is equal to any particular standard Young tableau of shape λ is \(s_{\lambda}(\frac{1}{b^{r}},\ldots,\frac{1}{b^{r}} )\), where there are b r variables. Letting f λ (a) denote the number of standard Young tableaux of shape λ with a descents, it follows that
By (7.96) of [27],
where in the kth summand, s λ (1,…,1) denotes the Schur function with k variables specialized to 1. Thus
where [u n]g(u) denotes the coefficient of u n in a power series g(u). Applying the Cauchy identity for Schur functions [27, p. 322], this becomes
as desired. □
References
Aguiar, M., Andre, C., Benedetti, C., Bergeron, N., Chen, Z., Diaconis, P., Hendrickson, A., Hsiao, S., Isaacs, I.M., Jedwab, A., Johnson, K., Karaali, G., Lauve, A., Le, T., Lewis, S., Li, H., Magaard, K., Marberg, E., Novelli, J., Pang, A., Saliola, F., Tevlin, L., Thibon, J., Thiem, N., Venkateswaran, V., Vinroot, C.R., Yan, N., Zabrocki, M.: Supercharacters, symmetric functions in noncommuting variables, and related Hopf algebras. Adv. Math. (2010, to appear). ArXiv e-prints 1009.4134
Bayer, D., Diaconis, P.: Trailing the dovetail shuffle to its lair. Ann. Appl. Probab. 2, 294–313 (1992)
Billera, L.J., Thomas, H., van Willigenburg, S.: Decomposable compositions, symmetric quasisymmetric functions and equality of ribbon Schur functions. Adv. Math. 204, 204–240 (2006). doi:10.1016/j.aim.2005.05.014
Brenti, F., Welker, V.: The Veronese construction for formal power series and graded algebras. Adv. Appl. Math. 42, 545–556 (2009). doi:10.1016/j.aam.2009.01.001
Carlitz, L., Kurtz, D., Scoville, R., Stackelberg, O.: Asymptotic properties of Eulerian numbers. Z. Wahrscheinlichkeitstheor. Verw. Geb. 23, 47–54 (1972)
Denham, G.: Eigenvectors for a random walk on a hyperplane arrangement. Adv. Appl. Math. (2010, to appear). ArXiv e-prints 1010.0232
Diaconis, P., Fulman, J.: Carries, shuffling, and an amazing matrix. Am. Math. Mon. 116, 788–803 (2009a). doi:10.4169/000298909X474864
Diaconis, P., Fulman, J.: Carries, shuffling, and symmetric functions. Adv. Appl. Math. 43, 176–196 (2009b). doi:10.1016/j.aam.2009.02.002
Diaconis, P., McGrath, M., Pitman, J.: Riffle shuffles, cycles, and descents. Combinatorica 15, 11–29 (1995)
Diaconis, P., Pang, A., Ram, A.: Hopf algebras and Markov chains: two examples and a theory. Preprint, Department of Mathematics, Stanford University (2011)
Foulkes, H.O.: Eulerian numbers, Newcomb’s problem and representations of symmetric groups. Discrete Math. 30, 3–49 (1980). doi:10.1016/0012-365X(80)90061-8
Fulman, J.: Applications of symmetric functions to cycle and increasing subsequence structure after shuffles. J. Algebr. Comb. 16, 165–194 (2002)
Garsia, A.M., Reutenauer, C.: A decomposition of Solomon’s descent algebra. Adv. Math. 77, 189–262 (1989). doi:10.1016/0001-8708(89)90020-0
Gerstenhaber, M., Schack, S.D.: A Hodge-type decomposition for commutative algebra cohomology. J. Pure Appl. Algebra 48, 229–247 (1987). doi:10.1016/0022-4049(87)90112-5
Gessel, I.M., Reutenauer, C.: Counting permutations with given cycle structure and descent set. J. Comb. Theory, Ser. A 64, 189–215 (1993). doi:10.1016/0097-3165(93)90095-P
Hanlon, P.: The action of Sn on the components of the Hodge decomposition of Hochschild homology. Mich. Math. J. 37, 105–124 (1990)
Holte, J.M.: Carries, combinatorics, and an amazing matrix. Am. Math. Mon. 104, 138–149 (1997)
Kerber, A.: Applied Finite Group Actions. Algorithms and Combinatorics, vol. 19, 2nd edn. Springer, Berlin (1999)
Kerber, A., Thürlings, K.-J.: Eulerian numbers, Foulkes characters and Lefschetz characters of S n . Sémin. Lothar. 8, 31–36 (1984)
Lascoux, A., Pragacz, P.: Ribbon Schur functions. Eur. J. Comb. 9, 561–574 (1988)
Loday, J.-L.: Cyclic Homology. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 301. Springer, Berlin (1992). Appendix E by María O. Ronco
Macdonald, I.G.: Symmetric Functions and Hall Polynomials, 2nd edn. Oxford Mathematical Monographs. The Clarendon Press, Oxford University Press, New York (1995). With contributions by A. Zelevinsky, Oxford Science Publications
Novelli, J.-C., Thibon, J.-Y.: Noncommutative symmetric functions and an amazing matrix. ArXiv e-prints 1110.3209 (2011)
Patras, F.: Construction géométrique des idempotents Eulériens. Filtration des groupes de polytopes et des groupes d’homologie de Hochschild. Bull. Soc. Math. Fr. 119, 173–198 (1991)
Solomon, L.: A decomposition of the group algebra of a finite Coxeter group. J. Algebra 9, 220–239 (1968)
Stanley, R.P.: Enumerative Combinatorics, vol. 1. Cambridge Studies in Advanced Mathematics, vol. 49. Cambridge University Press, Cambridge (1997). With a foreword by Gian-Carlo Rota, Corrected reprint of the 1986 original
Stanley, R.P.: Enumerative Combinatorics, vol. 2. Cambridge Studies in Advanced Mathematics, vol. 62. Cambridge University Press, Cambridge (1999). With a foreword by Gian-Carlo Rota and Appendix 1 by Sergey Fomin
Stanley, R.P.: Alternating permutations and symmetric functions. J. Comb. Theory, Ser. A 114, 436–460 (2007). doi:10.1016/j.jcta.2006.06.008
Weibel, C.A.: An Introduction to Homological Algebra. Cambridge Studies in Advanced Mathematics, vol. 38. Cambridge University Press, Cambridge (1994)
Acknowledgements
We thank Danny Goldstein, Bob Guralnick, Marty Isaacs, Eric Rains, Arun Ram, and a referee for their insights, hard work, and suggestions. P. Diaconis is supported in part by NSF grant 0804324. J. Fulman is supported in part by NSF grant 0802082 and NSA grant H98230-08-1-0133.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Diaconis, P., Fulman, J. Foulkes characters, Eulerian idempotents, and an amazing matrix. J Algebr Comb 36, 425–440 (2012). https://doi.org/10.1007/s10801-012-0343-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10801-012-0343-7