Séminaire Lotharingien de Combinatoire 70 (2014), Article B70i

A NOTE ON THE NUMBER OF k-ROOTS IN S_{n}

YUVAL ROICHMAN

Abstract. The number of k-roots of an arbitrary permutation is expressed as an alternating sum of μ-unimodal k-roots of the identity permutation.

1. A Combinatorial Identity

1.1. Outline. μ-unimodality, which was introduced in computations of Iwahori–Hecke algebra characters [9, 13, 14], was applied most recently to prove conjectures of Regev regarding induced characters [6] and of Shareshian and Wachs regarding Stanley’s chromatic symmetric function [5]. In this note it will be shown that the number of k-roots of a permutation of cycle type μ is equal to an alternating sum of μ-unimodal k-roots of the identity permutation.

1.2. μ-unimodal permutations. Let μ = (μ_{1}, …, μ_{t}) be a partition of n with t nonzero parts. Write

μ_{(0)} := 0

μ_{(i)} := ∑_{j=1}^{i} μ_{i} (1 ≤ i ≤ t)

and

(1)  S(μ) := (μ_{(1)}, …, μ_{(t)}).

A permutation π ∈ S_{n} is μ-unimodal if for every i with 0 ≤ i < t there exists ı with 0 ≤ ı ≤ μ_{i+1} such that

π(μ_{(i)} + 1) > π(μ_{(i)} + 2) > ⋯ > π(μ_{(i)} + ı) < π(μ_{(i)} + ı + 1) < ⋯ < π(μ_{(i+1)}).

Denote the set of μ-unimodal permutations in S_{n} by U_{μ}.

For example, let μ = (μ_{1}, μ_{2}, μ_{3}) = (4, 3, 1) then S(μ) = (μ_{(1)}, μ_{(2)}, μ_{(3)}) = (4, 7, 8). The permutations 53687142 and 35687412 are μ-unimodal, but 53867142 and 53681742 are not.

Note that U_{(1,...,1)} = S_{n}.

1.3. k-roots in S_{n}. For n ≥ 1 and k ≥ 0, we write

I_{n}^{k} := {π ∈ S_{n} : π^{k} = 1}

for the set of k-roots of the identity permutation in S_{n}.

Theorem 1.1. For every n ≥ 1, k ≥ 0, partition μ ⊢ n, and π ∈ S_{n} of cycle type μ, we have

(2)  #{σ ∈ S_{n} : σ^{k} = π} = ∑_{σ∈I_{n}^{k}∩U_{μ}}(−1)^{|Des(σ)\S(μ)|}.

It follows that the set of k-roots of the identity permutation is a fine set in the sense of [3]. The case k = 2 follows from [2, Prop.1.5]. Note that the proof there does not apply to a general k.

2. Proof of Theorem 1.1

2.1. Induced representations. For every n ≥ 1 and k ≥ 0, let θ^{k,n} : S_{n} ⟶ ℕ ∪ {0} be the enumerator of k-roots of a permutation π in S_{n},

θ^{(k,n)}(π) := #{σ ∈ S_{n} : σ^{k} = π}.

Clearly, θ^{(k,n)} is a class function. By a classical result of Frobenius and Schur, θ^{(2,n)} is not virtual, see e.g. [11, §4]. It was conjectured by Kerber and proved by Scharf [16] that, for every k ≥ 0, θ^{(k,n)} is a non-virtual character.

Let Z_{λ} be the centralizer of a permutation of cycle type λ in S_{n}. Z_{λ} is isomorphic to the direct product ×_{i=1}^{n}C_{i} ≀ S_{m_{i}}, where m_{i} is the multiplicity of the part i in λ. Denote by ρ_{i} the one-dimensional representation of C_{i} ≀ S_{m_{i}} indexed by the i-tuple of partitions (∅, (m_{i}), ∅, …, ∅). Let

ρ^{λ} := ⨂_{i=1}^{n} ρ_{i}

be a one-dimensional representation of Z_{λ}, and

ψ^{λ} = ρ^{λ} ↑_{Z_{λ}}^{S_{n}}

the corresponding induced S_{n}-representation.

Denote by ϕ^{k,n} the representation whose character is θ^{(k,n)}. The following theorem implies that ϕ^{k,n} is not virtual.

Theorem 2.1 ([16]). For every n ≥ 1 and k ≥ 0, we have

ϕ^{k,n} = _{⨁_{λ⊢n} all parts divide k}ψ^{λ}.

See also [18, Cor. 5.2] and [17, Ex. 7.69(c)]. Note that by letting k = 2 one obtains the well known construction of Inglis, Richardson, and Saxl of a Gelfand model for S_{n} [10].

2.2. Descents over conjugacy classes. Let C_{λ} be the conjugacy class of cycle type λ in S_{n} and SYT(ν) be the set of all standard Young tableaux of shape ν. Denote the multiplicity of the Specht module S^{ν} in ψ^{λ} by m(ν, λ). The following is a reformulation of [8, Thm. 2.1], see also [12].

Theorem 2.2. For every λ ⊢ n, we have

(3)  ∑_{π∈C_{λ}} x^{Des(π)} = ∑_{ν⊢n} m(ν, λ) ∑_{T ∈SYT(ν)} x^{Des(T)}.

A NOTE ON THE NUMBER OF k-ROOTS IN S_{n} 3

Proof. Denote by L_{λ} the image of ψ^{λ} under the Frobenius characteristic map. For an explicit description of this symmetric function, see e.g. [17, Ex. 7.89]. For J ⊆ [n − 1], let z_{J} be the skew Schur function which corresponds to the zigzag skew shape with down steps on positions which belong to J. For example, in French notation, J = {1, 4, 5} ⊆ [7] corresponds to the shape

1 2 3 4 5 6 7 8 .

By [8, Thm. 2.1], the coefficient of x^{J} in the left-hand side of Equation (3), which is the number of permutations of cycle type λ and descent set J, is equal to ⟨L_{λ}, z_{J}⟩.

Now,

⟨L_{λ}, z_{J}⟩ = ⟨L_{λ}, ∑_{ν⊢n}⟨s_{ν}, z_{J}⟩s_{ν}⟩ = ∑_{ν⊢n}⟨L_{λ}, s_{ν}⟩⟨s_{ν}, z_{J}⟩ = ∑_{ν⊢n} m(ν, λ)⟨s_{ν}, z_{J}⟩.

Since ⟨s_{ν}, z_{J}⟩ is equal to the number of standard Young tableaux of shape ν and descent set J [7, Thm. 7] (see also [1, Thm. 4.1]), this is equal to the coefficient of x^{J} in the right-hand side of Equation (3). □

Corollary 2.3. For every partition μ ⊢ n, the value of ψ^{λ} at a permutation of cycle type μ is

(4)  ψ_{μ}^{λ} = ∑_{σ∈C_{λ}∩U_{μ}}(−1)^{|Des(σ)\S(μ)|}.

Proof. For partitions μ and ν of n, let χ_{μ}^{ν} be the character value of the Specht module S^{ν} on a conjugacy class of cycle type μ. A standard Young tableau T of size n is μ-unimodal if Des(T) \ S(μ) is a disjoint union of intervals of the form [μ_{(i)} + 1, μ_{(i)} + ı] for some 0 ≤ ı < μ_{i+1}. For example, the standard Young tableau

T = 5 2 4 1 3 6

has Des(T) = {1, 3, 4}, and is therefore (3, 3)-unimodal but not (4, 2)-unimodal. By [14, Theorem 4] [13], we have

χ_{μ}^{ν} = ∑_{T ∈SYT(ν)∩SYT_{μ}}(−1)^{|Des(T)\S(μ)|},

where SYT(ν) is the set of all standard Young tableaux of shape ν and SYT_{μ} is the set of μ-unimodal standard Young tableaux of size n.

Combining this with Theorem 2.2 gives

ψ_{μ}^{λ} = ∑_{ν⊢n} m(ν, λ)χ_{μ}^{ν} = ∑_{ν⊢n} m(ν, λ) ∑_{T ∈SYT(ν)∩SYT_{μ}}(−1)^{|Des(T)\S(μ)|}

= ∑_{σ∈C_{λ}∩U_{μ}}(−1)^{|Des(σ)\S(μ)|}.

□

2.3. Conclusion. By Theorem 2.1 together with Corollary 2.3, for every π ∈ S_{n} of cycle type μ, we have

#{σ ∈ S_{n} : σ^{k} = π} = θ^{(k,n)}(π) = _{∑_{λ⊢n} all parts divide k}ψ_{μ}^{λ}

= _{∑_{λ⊢n} all parts divide k} ∑_{σ∈C_{λ}∩U_{μ}}(−1)^{|Des(σ)\S(μ)|} = ∑_{σ∈I_{n}^{k}∩U_{μ}}(−1)^{|Des(σ)\S(μ)|},

completing the proof of Theorem 1.1. □

3. Remarks and questions

It is desirable to prove Theorem 1.1 via generalizations of the explicit combinatorial construction of Gelfand models described in [2].

Question 3.1. Find a “simple” S_{n}-linear action on a basis of ϕ^{k,n} indexed by I_{n}^{k}, which implies the character formula given on the right-hand side of Equation (2).

Another desirable approach to prove Theorem 1.1 is purely combinatorial.

Question 3.2. Define, for any given partition μ of n, an involution on the set of kroots of the identity permutation, which changes the parity of Des(·)\S(μ) on non-fixed points, such that the cardinality of the fixed point set is equal to the left-hand side of Equation (2).

The case μ = (n) was recently solved by Archer [4].

Question 3.3. Prove Theorem 2.2 by constructing a map from C_{λ} to standard Young tableaux of size n, under which for every ν ⊢ n and T ∈ SYT(ν) the cardinality of the preimage of T is exactly m(ν, λ).

Note that for λ = (2^{k}, 1^{n−2k}), 0 ≤ k ≤ n/2, the Robinson–Schensted–Knuth map satisfies this property.

Finally, a natural objective is to extend the setting of the current note to other finite groups. Complex reflection groups are of special interest.

Question 3.4. Generalize Theorem 1.1 to other Coxeter and complex reflection groups.

This question is intimately related to the problem of characterizing the finite groups for which the character θ^{(k,n)} is non-virtual. For wreath products, see [15].

Acknowledgements

Thanks to Ron Adin for useful discussions and to Michael Schein and the anonymous referees for helpful comments and references.

References

[1] R. M. Adin, F. Brenti and Y. Roichman, Descent representations and multivariate statistics, Trans. Amer. Math. Soc. 357 (2005), 3051–3082.

[2] R. M. Adin, A. Postnikov and Y. Roichman, Combinatorial Gelfand models, J. Algebra 320 (2008), 1311–1325.

[3] R. M. Adin and Y. Roichman, Matrices, characters and descents, preprint; arχiv:1301.1675.

[4] K. Archer, Descents of λ-unimodal cycles in a character formula, preprint; arχiv:1401.2433.

[5] C. A. Athanasiadis, Power sum expansion of chromatic quasisymmetric functions, preprint 2014.

[6] S. Elizalde and Y. Roichman, Arc permutations, J. Algebraic Combin. 39 (2014), 301–334.

[7] I. M. Gessel, Multipartite P -partitions and inner products of skew Schur functions, Combinatorics and Algebra (Boulder, Colo., 1983), Contemp. Math. 34, Amer. Math. Soc., Providence, R.I., 1984, pp. 289–317.

[8] I. M. Gessel and C. Reutenauer, Counting permutations with given cycle structure and descent set, J. Combin. Theory Ser. A 64 (1993), 189–215.

[9] T. Halverson, R. Leduc and A. Ram, Iwahori–Hecke algebras of type A, bitraces and symmetric functions, Internat. Math. Res. Notices (1997), 401–416.

[10] N. F. J. Inglis, R. W. Richardson and J. Saxl, An explicit model for the complex representations of S_{n}, Arch. Math. (Basel) 54 (1990), 258–259.

[11] I. M. Isaacs, Character Theory of Finite Groups. Dover, New York, 1994.

[12] A. Jöllenbeck and C. Reutenauer, Eine Symmetrieeigenschaft von Solomons Algebra und der höheren Lie-Charaktere, (German) [A symmetry property of Solomon’s algebra and the higher Lie characters] Abh. Math. Sem. Univ. Hamburg 71 (2001), 105–111.

[13] A. Ram, An elementary proof of Roichman’s rule for irreducible characters of Iwahori–Hecke algebras of type A, in: Mathematical essays in honor of Gian-Carlo Rota, Progr. Math., vol. 161, Birkhäuser, Boston, 1998, pp. 335–342.

[14] Y. Roichman, A recursive rule for Kazhdan–Lusztig characters, Adv. in Math. 129 (1997), 24–45.

[15] T. Scharf, Über Wurzelanzahlfunktionen voller monomialer Gruppen, (German) [On root number functions of full monomial groups] Dissertation, Universität Bayreuth, Bayreuth, 1991. Bayreuth. Math. Schr. 38 (1991), 99–207.

[16] T. Scharf, Die Wurzelanzahlfunktion in symmetrischen Gruppen, (German) [The root number function in symmetric groups] J. Algebra 139 (1991), 446–457.

[17] R. P. Stanley, Enumerative combinatorics, vol. 2, Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press, Cambridge, 1999.

[18] J.-Y. Thibon, The inner plethysm of symmetric functions and some of its applications, Bayreuth. Math. Schr. 40 (1992), 177–201.

Department of Mathematics, Bar-Ilan University, 52900 Ramat-Gan, Israel

  E-mail address: yuvalr@math.biu.ac.il