Modulo-n study of Mahonian statistics

Jacques Désarménien

[This is a translation of the paper “Étude modulo n des statistiques mahoniennes” from French. The paper was originally published in Séminaire Lotharingien de Combinatoire, B22a (1989). The translation was done by Darij Grinberg. The translation occasionally veers away from the original wording and corrects a few typos and minor oversights.

The author thanks Darij Grinberg for his careful reading of the original French version, for his accurate and precise translation as well as for his most valuable remarks.]

Introduction

Under the general notion of Mahonian statistics, one subsumes a certain number of statistics defined on some sets of words of length n. Examples of such statistics are the number of inversions of permutations, their major index or their imajor index, and the same statistics on the words over the alphabet {0, 1}. One can furthermore impose constraints on the form (“up-down sequence”, for example) of permutations. A celebrated result by Foata and Schützenberger [F–S] establishes in this case the equidistribution of the number of inversions and the imajor index. Thus one needs only study the major index of a Young tableau, which allows one to use the whole arsenal of classical algebra. Such an approach has been used, in particular, in [D2, D–F1, D–F2, D–F3, D–F4].

The purpose of this paper is to establish an equidistribution property of Young tableaux of a given form with respect to the modulo-n value of their major index. From this, we will then deduce the same property for all the statistics on permutations, and many analogous results.

We will also obtain the explicit decomposition of the representation of the symmetric group on the free Lie algebra associated to a partition n. This result, due to Kraskiewicz and Weyman [K–W], is cited by Reutenauer [R].

The tools we will use are, first, the relationship between certain characters of the symmetric group and the major index of Young tableaux, and second, a lemma of arithmetical nature.

With the support of P.R.C. Math.-Info.

J. Désarménien

1. The arithmetical lemma

We shall use the notation (a, b) for the greatest common divisor of two integers a and b.

Let n be a positive integer. Denote by Φ_{n}(q) the n-th cyclotomic polynomial (so that Φ_{1}(q) = 1 − q, Φ_{2}(q) = 1 + q, …). We will need the Ramanujan sums c_{n}(m) = ∑_{(i,n)=1} ζ^{im}, where ζ denotes a primitive nth root of unity (cf. [H–W]). One can easily find the explicit value of Ramanujan sums in terms of the Möbius function μ(n) and Euler’s totient function φ(n). More precisely, the following result, due to Hölder, holds :

Lemma 1.1 [H–W, p. 238]. — Set (m, n) = δ and n = δN ; then

c_{n}(m) = \frac{μ(N)φ(n)}{φ(N)}.

In particular, if (n_{1}, m) = (n_{2}, m), then c_{n}(m_{1}) = c_{n}(m_{2}).

Let now P (q) = ∑_{0≤k≤n−1} a_{k}q^{k} be a polynomial with integer coefficients. Following the terminology of Cohen [C], we say that the coefficients of P (q), and, by abuse of notation, the polynomial P (q) itself, are even modulo n if, for every k and l from 0 to n − 1, the equality (k, n) = (l, n) implies the equality of coefficients a_{k} = a_{l}.

The functions even modulo n have been studied by Cohen, who has shown that they coincide with the linear combinations of Ramanujan sums. The latter have been utilized, in particular, by Nicol and Vandiver [N–V], in enumerating certain combinatorial configurations.

Proposition 1.2. — Let P (q) be a polynomial with integer coefficients and degree less than n. Then, the following two properties are equivalent :

(i) For every divisor d of n, the residue r_{d} of P (q) modulo Φ_{d}(q) is an integer. (ii) The polynomial P (q) is even modulo n. Moreover, if these two equivalent properties (i) and (ii) are satisfied,

one has

a_{k} = \frac{1}{n} ∑_{d|n} r_{d}c_{d}(k)  and  r_{δ} = ∑_{d|n} a_{n/d}c_{d}(n/δ).

Proof of Proposition 1.2. — The polynomials satisfying (i) and those satisfying (ii) clearly form Z-modules of the same rank, and this rank is equal to the number of divisors of n.

Assume that property (ii) holds ; in other words, whenever (k, n) = n/d, we have a_{k} = a_{n/d}. In order to prove the property (i), it suffices to see that whenever q is set to any primitive δ-th root of unity, with δ|n, the value attained by P (q) is a number r_{δ} depending only on δ (but not on the choice of the primitive δ-th root of unity). The primitive δ-th roots of unity are the ζ^{i} with (i, n) = n/δ, and for these we have

\begin{aligned}P (ζ^{i}) & = ∑_{0≤k≤n−1} a_{k}ζ^{ik}, \\ & = ∑_{d|n} a_{n/d} ∑_{(k,n)=n/d} ζ^{ik}. \end{aligned}

One can write k = k′ \frac{n}{d} where (k′, d) = 1 ; moreover, if ζ is a primitive n-th root of unity, then ζ^{n/d} is a primitive d-th root of unity. Thus,

P (ζ^{i}) = ∑_{d|n} a_{n/d} ∑_{(k′,d)=1} ζ^{ik′n/d},

= ∑_{d|n} a_{n/d}c_{d}(i),

= ∑_{d|n} a_{n/d}c_{d}(n/δ).

Hence, one obtains property (i) and the value for r_{δ} announced.

Conversely, let us show that (i) implies (ii), and prove the formulas for the a_{k} and r_{δ} in terms of each other. In order to verify that the a_{k} can be expressed in terms of the r_{d} as indicated, one can use an inversion formula due to Cohen [C, Theorem 2]. In order for this paper to remain self-contained, we are going to actually establish this inversion formula directly in our particular case.

Assume that property (i) holds. Let ζ^{0}, ζ^{1}, …, ζ^{n−1} be the n distinct n-th roots of unity. The primitive d-th roots of unity thus are the ζ^{k} for (k, n) = n/d. Since P (q) ≡ r_{d} (mod Φ_{d}(q)), we have, for every k that satisfies (k, n) = n/d, the equality P (ζ^{k}) = r_{d}. Since we now know the value of P (q) at n distinct points, we can apply the Lagrange interpolation formula :

P (q) = ∑_{0≤i≤n−1} P (ζ^{i}) ∏_{j≠i} \frac{(q − ζ^{j})}{(ζ^{i} − ζ^{j})},

= ∑_{0≤i≤n−1} P (ζ^{i}) ∏_{j≠i} \frac{(ζ^{n−i}q − ζ^{n−i+j})}{(1 − ζ^{n−i+j})},

= ∑_{0≤i≤n−1} P (ζ^{i}) ∏_{j≠0} \frac{(ζ^{n−i}q − ζ^{j})}{(1 − ζ^{j})}.

Since the polynomial whose roots are ζ^{j} for j ≠ 0 (each only once) is ∑_{0≤k≤n−1} q^{k}, we thus have

P (q) = \frac{1}{n} ∑_{0≤i≤n−1} P (ζ^{i}) ∑_{0≤k≤n−1} ζ^{(n−i)k}q^{k}.

Now, regrouping the indices i according to the value n/d of (i, n), and replacing P (ζ^{i}) by r_{d}, we can rewrite this as

P (q) = \frac{1}{n} ∑_{d|n} r_{d} ∑_{(i,n)=n/d} ∑_{0≤k≤n−1} ζ^{(n−i)k}q^{k},

= \frac{1}{n} ∑_{0≤k≤n−1} q^{k} ∑_{d|n} r_{d} ∑_{(i,n)=n/d} ζ^{ik},

= \frac{1}{n} ∑_{0≤k≤n−1} q^{k} ∑_{d|n} r_{d}c_{d}(k).

Thus one obtains the value announced for the coefficient a_{k}.

Now, property (ii) readily follows. Indeed, whenever (k, n) = (l, n), we have (k, d) = (l, d) for every divisor d of n, and thus a_{k} = a_{l} according to the formula we have shown for the coefficients a_{k}.

This completes the proof of Proposition 1.2.

2. Characters and congruences

Regarding the definitions and general properties of symmetric functions, the reader is referred to [M]. The word “shape” shall in the following refer to an arbitrary skew partition. We know that the power-sum symmetric functions p_{λ}, where λ ranges over the partitions, form a Q-basis of the vector space of symmetric functions. Moreover, to each representation of a symmetric group, a symmetric function is associated. In this way, the Schur functions S_{λ} for partitions (or straight shapes) λ are associated to the irreducible representations. The Schur functions form a Z-basis of the Z-module of symmetric functions. More precisely, if we denote by χ_{λ}(μ) the value at μ of the irreducible character of the symmetric group associated to λ, then one has the decompositions

S_{λ} = ∑_{μ} \frac{1}{z_{μ}} χ_{λ}(μ)p_{μ},

p_{μ} = ∑_{λ} χ_{λ}(μ)S_{λ},

where z_{μ} is the integer 1^{μ_{1}}2^{μ_{2}} … μ_{1}! μ_{2}! …, when μ is a partition consisting of μ_{1} parts equal to 1, of μ_{2} parts equal to 2, …

Given a standard Young tableau T of shape λ and size n, let us denote by rec T the set of all integers i with 1 ≤ i ≤ n − 1 such that i + 1 lies farther to the left (in the wider sense, i. e., i + 1 lies in the same column as i or in a column to the left of i) than i in T (these integers i are called the recoils of T), and let us denote by imaj T the sum of the integers i ∈ rec T (this is called the imajor index of T). In particular, if the shape λ is a ribbon (cf. [D2]), then the tableau T can be considered as a permutation whose shape is given by λ, and the statistic thus defined on T coincides with the imajor index of this permutation. [Here, the “shape” of a permutation is defined as the shape of a standard Young tableau of ribbon shape whose reading word is the permutation. This is just another way to encode the descent set of the permutation.] Denote by (q, q)_{n} = (1 − q)(1 − q^{2}) ⋯ (1 − q^{n}) the q-factorial.

The connection between Schur functions and Mahonian statistics is essentially contained in the following lemma (cf. [D–F1]) :

Lemma 2.1. — The generating function of the statistic imaj on the standard tableaux of shape λ is given by

∑_{T} q^{imaj T} = (q, q)_{n}S_{λ}(1, q, q^{2}, …),

where the sum ranges over all standard tableaux of shape λ.

Let P_{λ}(q) = ∑_{0≤k≤n−1} a_{k}(λ)q^{λ} be the polynomial whose coefficient a_{k}(λ) is the number of tableaux T of shape λ such that imaj T ≡ k (mod n). We can now state the main result of this article.

Theorem 2.2. — For any given shape λ of size n, the value of a_{k}(λ) depends only on the greatest common divisor (k, n) (but not on k). More precisely,

a_{k}(λ) = \frac{1}{n} ∑_{d|n} χ_{λ}(d^{n/d})c_{d}(k).

Proof of Theorem 2.2. — Let d|n. Since 1 − q^{n} is divisible by Φ_{d}(q), the remainder modulo Φ_{d}(q) of P_{λ}(q) and that of the generating series of imaj on the tableaux of shape λ are equal. By virtue of Lemma 2.1, it equals the remainder of (q, q)_{n}S_{λ}(1, q, q^{2}, …) modulo Φ_{d}(q).

We can thus use the expression of S_{λ} as a linear combination of powersum symmetric functions. We thus obtain

(q, q)_{n}S_{λ}(1, q, q^{2}, …) = ∑_{μ} \frac{1}{z_{μ}} χ_{λ}(μ)T_{μ}(q),

where

T_{μ}(q) = (q, q)_{n}p_{μ}(1, q, q^{2}, …).

One easily sees that

T_{μ}(q) = \frac{(1 − q)(1 − q^{2}) ⋯ (1 − q^{n})}{(1 − q)^{μ_{1}}(1 − q^{2})^{μ_{2}} ⋯ (1 − q^{n})^{μ_{n}}} .

The only factors appearing in the preceding expression are cyclotomic polynomials. It is not hard to find the remainder modulo any cyclotomic polynomial (cf. [D1, D2, D–F4]). Here, we are only interested in the remainder modulo Φ_{d}(q), for which we will rederive the result. The multiplicity of the factor Φ_{d}(q) in T_{μ}(q) is

\frac{n}{d} − (μ_{d} + μ_{2d} + ⋯ + μ_{n}).

Since

n = μ_{1} + 2μ_{2} + ⋯ + nμ_{n} ≥ d(μ_{d} + μ_{2d} + ⋯ + μ_{n}),

it follows that T_{μ}(q) is divisible by Φ_{d}(q) unless μ = d^{n/d}. In the latter case,

T_{d^{n/d}}(q) = \frac{(1 − q) ⋯ (1 − q^{d})(1 − q^{d+1}) ⋯ (1 − q^{2d}) ⋯ (1 − q^{n})}{(1 − q^{d})^{n/d}},

and substituting for q any primitive d-th root of unity in the preceding expression gives

T_{d^{n/d}}(q) ≡ d^{n/d}(n/d)! = z_{d^{n/d}} (mod Φ_{d}(q)).

Consequently, one has the congruence

(q, q)_{n}S_{λ}(1, q, q^{2}, …) ≡ χ_{λ}(d^{n/d}) (mod Φ_{d}(q)).

The condition (i) of Proposition 1.2 is thus satisfied for the polynomial P_{λ}(q), and Theorem 2.2 is demonstrated.

3. Combinatorial consequences

Theorem 2.2 can be applied to all shapes λ, which includes ribbons, as mentioned above. The standard Young tableaux of a ribbon shape are exactly the permutations whose shape is given by the ribbon. By taking linear combinations of Schur functions of ribbon shape, one obtains permutations whose shape is subject to certain conditions. It is precisely on these sets of permutations that Foata and Schützenberger [F–S] have proven the equidistribution of the number of inversion and the imajor index. One can thus deduce from Theorem 2.2 the following result.

Proposition 3.1. — The number of permutations of [1, n] subject to given conditions on their shape and whose number of inversions is congruent to k modulo n depends only on the greatest common divisor (k, n) and on the conditions (but not on k).

One can deduce analogous results for all the sequences analogous to the classical number sequences studied in [D2] : alternating permutations, Eulerian permutations, desarrangements, …

We have studied, following Gessel [D–W], the symmetric functions associated to Lyndon words of a given type. In a fashion completely analogous to our proof of Lemma 2.1, one can deduce the existence of symmetric functions L_{λ} of degree n such that the generating function of the statistic imaj ranging over the permutations whose cycle type is λ equals (q, q)_{n}L_{λ}(1, q, q^{2}, …). By decomposing these functions L_{λ} as sums of Schur functions, and applying Theorem 2.2 to each of the Schur functions, one obtains the following result.

Proposition 3.2. — The number of permutations of [1, n] whose cycle type is λ and whose imajor index is congruent to k modulo n depends only on the greatest common divisor of k and n and on λ (but not on k).

A case particularly worthy of interest is that where λ is a partition with only one part ; this part must of course be n. The permutations with this cycle type are thus the cyclic permutations. In this case, the function L_{n}, a weighted sum of Lyndon words of length n, can be evaluated by Pólya’s theorem :

L_{n} = \frac{1}{n} ∑_{d|n} μ(d)p_{d}^{n/d}.

Now, let us write this weighted-sum decomposition as a sum of Schur functions :

L_{n} = \frac{1}{n} ∑_{d|n} ∑_{λ} μ(d)χ_{λ}(d^{n/d})S_{λ},

= ∑_{λ}(\frac{1}{n} ∑_{d|n} μ(d)χ_{λ}(d^{n/d}))S_{λ},

= ∑_{λ} a_{1}(λ)S_{λ}.

The latter expression of L_{n} results from Theorem 2.2 and from the corollary to Lemma 1.1 stating that c_{d}(1) = μ(d). We can thus deduce the following decomposition, obtained by other means by Kraskiewicz and Weyman [K–W].

Proposition 3.3. — The multiplicity of S_{λ} in L_{n} equals the number of standard Young tableaux of shape λ whose imajor index is congruent to 1 modulo n.

This result, as Reutenauer [R] indicates, has further consequences. Indeed, let us start at the identity of the preceding proposition :

L_{n} = ∑_{λ} a_{1}(λ)S_{λ}.

Using the techniques and the notations of [D–W], we can write

L_{n} = ∑_{λ} a_{1}(λ) ∑_{T} ∑_{s⊥rec T} w(s),

where the second sum ranges over the standard tableaux T of shape λ. One can rewrite

L_{n} = ∑_{E⊂[1,n−1]} ∑_{s⊥E} w(s)A^{E},

where A^{E} is the number of pairs of standard tableaux (U, V) of order n, of same shape, satisfying imaj U ≡ 1 (mod n) and rec T = E.

The Robinson-Schensted-Schützenberger construction establishes precisely a bijection between the pairs (U, V) of standard Young tableaux of equal shape and the permutations σ. Moreover, the set of recoils of U equals the set of recoils of σ and the set of recoils of V equals the set of descents of σ. Consequently, A^{E} is also the number of permutations σ of [1, n] whose set of descents is E and for which imaj σ is congruent to 1 modulo n.

On the other hand,

L_{n} = ∑_{E⊂[1,n−1]} ∑_{s⊥E} w(s)C^{E},

where C^{E} is the number of cyclic permutations of [1, n] whose set of descents is E (cf. [D–W]). By comparing the two equalities for L_{n} (and by solving a triangular system of equations), we thus conclude the equality A^{E} = C^{E}. Using also the result of Foata and Schützenberger, we thus have established the following proposition, due to Reutenauer [R].

Proposition 3.4. — Let E ⊂ [1, n − 1]. The following sets have the same cardinality :

(i) The cyclic permutations whose set of descents is E; (ii) The permutations whose set of descents is E and whose imajor index is congruent to 1 modulo n; (iii) The permutations whose set of descents is E and whose number of inversions is congruent to 1 modulo n.

In another vein, let us mention that Proposition 1.2 can also be applied to Gaussian, or q-binomial, polynomials. We have established in [D1] the following congruence : If n = ka + r and m = kb + s are the divisions with rest of two integers n and m by k, then

\left[{n \atop m}\right] ≡ \binom{a}{b}\left[{r \atop s}\right] (mod Φ_{k}).

When k divides n, the polynomial \left[{r \atop s}\right] is 0 or 1 according to whether k does not divide or divides m. In either case, the right-hand side of the congruence is an integer. Now, using the combinatorial interpretations of Gaussian polynomials, due to MacMahon, we obtain the following result analogous to Theorem 2.2 for Mahonian statistics on words.

Proposition 3.5. — The number of n-letter words containing m times the letter 0 and n − m times the letter 1 and whose number of inversions (or, equivalently, whose major index) is congruent to k modulo n depends only on the greatest common divisor (k, n) and m (but not on k).

REFERENCES

[C] COHEN (E.). — A class of arithmetical functions, Proc. Natl. Acad. Sci. U.S.A., vol. 41, 1955, p. 939–944.

[D1] D^{}ÉSARM^{}ÉNIEN (J.). — Un analogue des congruences de Kummer pour les qnombres d’Euler, Europ. J. Combin., vol. 3, 1982, p. 19–28.

[D2] D^{}ÉSARM^{}ÉNIEN (J.). — Fonctions symétriques associées à des suites classiques de

nombres, Ann. Scient. école Normale Supérieure, vol. 16, 1983, p. 271–304.

[D–F1] D^{}ÉSARM^{}ÉNIEN (J.) and FOATA (D.). — Fonctions symétriques et séries hypergéométriques basiques multivariées, Bull. Soc. Math. France, vol. 113, 1985, p. 3–22.

[D–F2] D^{}ÉSARM^{}ÉNIEN (J.) and FOATA (D.). — Fonctions symétriques et séries hypergéométriques basiques multivariées II, Combinatoire énumérative, [Labelle (G.) and Leroux (P.), eds. ; Montréal, 28 mai–1 juin 1985], p. 68–90. — Heidelberg, Springer-Verlag (Lecture Notes in Mathematics, vol. 1234), 1987.

[D–F3] D^{}ÉSARM^{}ÉNIEN (J.) and FOATA (D.). — Statistiques d’ordre sur les permutations

colorées, Discrete Mathematics, vol. 87, 1991, p. 133-148.

[D–F4] D^{}ÉSARM^{}ÉNIEN (J.) and FOATA (D.). — The signed Eulerian numbers, Discrete

Mathematics, vol. 99, 1992, p. 49-58.

[D–W] D^{}ÉSARM^{}ÉNIEN (J.) and WACHS (M.). — Descentes sur les dérangements et mots circulaires, Séminaire lotharingien de combinatoire, 19^{e} session, [Strehl (V.), ed. ; Schloß Schwanberg/Ufr. 22–25 mars 1988], p. 13–21. — Strasbourg, Publ. I.R.M.A. 361/S–19, 1988.

[F–S] FOATA (D.) and SCH^{}ÜTZENBERGER (M.). — Major index and inversion number

of permutations, Math. Nachr., vol. 83, 1978, p. 143–159.

[H–W] HARDY (G.M.) and WRIGHT (E.M.). — An introduction to the theory of numbers

(5^{e} ed.). — Oxford, Clarendon Press, 1979.

[K–W] KRASKIEWICZ (W.) and WEYMAN (J.). — Algebra of invariants and the action of a Coxeter element, preprint, Institute of Mathematics of the University of Copernic, Toruń, Poland.

[M] MACDONALD (I.G.). — Symmetric functions and Hall polynomials. — Oxford,

Clarendon Press, 1979. [N–V] NICOL (C.A.) and VANDIVER (H.S.). — A Von Sterneck arithmetical function

and restricted partitions with respect to a modulus, Proc. Natl. Acad. Sci. U.S.A., vol. 40, 1954, p. 825–835.

[R] REUTENAUER (C.). — Number of permutations with given descent set and cycle stucture, Séminaire lotharingien de combinatoire, Actes 21^{e} session, Strasbourg, Publ. I.R.M.A. 413/S–21, 1990.

Département d’informatique,

Institut universitaire de technologie de l’Université Robert-Schuman, 72, route du Rhin, 67400 Illkirch-Graffenstaden.