# Characters of symmetric groups in terms of free cumulants and Frobenius coordinates.

1 Introduction

This contribution is an extended abstract of a full version [DFS08] which will be published elsewhere.

1.1 Dilations of Young diagrams and normalized characters

For a Young diagram [lambda] and an integer s [greater than or equal to] 1 we denote by s[lambda] the dilation of [lambda] by factor s. This operation can be easily described on a graphical representation of a Young diagram: we just dilate the picture of [lambda] or, alternatively, we replace each box of [lambda] by a grid of s x s boxes.

[FIGURE 1 OMITTED]

Any permutation [pi] [member of] [??](k) can be also regarded as an element of [??](n) if k [less than or equal to] n (we just declare that [pi] [member of] [??](n) has additional n - k fixpoints). For any [pi] [member of] [??](k) and an irreducible representation [[rho].sup.[lambda]] of the symmetric group [??](n) corresponding to the Young diagram [lambda] we define the normalized character

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

We shall concentrate our attention on the characters on cycles, therefore we will use the special notation

[[summation].sup.[lambda].sub.k] = [[summation].sup.[lambda].sub.(1, 2, ..., k)],

where we treat the cycle (1, 2, ..., k) as an element of [??](k) for any integer k [greater than or equal to] 1.

The notion of dilation of a Young diagram is very useful from the viewpoint of the asymptotic representation theory because it allows us to ask the following question:

Problem 1 What can we say about the characters of the symmetric groups in the limit when the Young diagram [lambda] tends in some sense to infinity in a way that [lambda] preserves its shape?

This informal problem can be formalized as follows: for fixed [lambda] and k we ask about (asymptotic) properties of the normalized characters [[summation].sup.s[lambda].sub.k] in the limit s [right arrow] [infinity]. The reason why we decided to study this particular normalization of characters is the following well-known yet surprising result.

Fact 2 For any Young diagram [lambda] and integer k [greater than or equal to] 2 the normalized character on a dilated diagram

N [contains as members] s [??] [[summation].sup.s[lambda].sub.k-1] (1)

is a polynomial function of degree (at most) k.

1.2 Generalized Young diagrams

Any Young diagram drawn in the French convention can be identified with its graph which is equal to the set {(x, y) : 0 [less than or equal to] x, 0 [less than or equal to] y [less than or equal to] f(x)} for a suitably chosen function f : [R.sub.+] [right arrow] [R.sub.+], where [R.sub.+] = [0, [infinity]), cf. Figure 1. It is therefore natural to define the set of generalized Young diagrams Y (in the French convention) as the set of bounded, non-increasing functions f : [R.sub.+] [right arrow] [R.sub.+] with a compact support; in this way any Young diagram can be regarded as a generalized Young diagram. Notice that with the notion of generalized Young diagrams we may consider dilations s[lambda] for any real s [greater than or equal to] 0.

1.3 How to describe the shape of a Young diagram?

Our ultimate goal is to explicitly express the polynomials (1) in terms of the shape of [lambda]. However, before we start this task we must ask ourselves: how to describe the shape of [lambda] in the best way? In the folowing we shall present two approaches to this problem.

We define the fundamental functionals of shape of a Young diagram [lambda] by an integral over the area of [lambda]

[S.sup.[lambda].sub.k] = (k - 1) [integral][[integral].sub.(x,y)[member of][lambda]] [[(contents.sub.(x,y)]).sup.k-2] dx dy

for integer k [greater than or equal to] 2, and where [contents.sub.(x,y)] = x - y is the contents of a point of a Young diagram. When it does not lead to confusions we will skip the explicit dependence of the fundamental functionals on Young diagrams and instead of [S.sup.[lambda].sub.k] we shall simply write [S.sub.k]. Clearly, each functional [S.sub.k] is a homogeneous function of the Young diagram with degree k, i.e. [S.sup.s[lambda].sub.k] = [s.sup.k][S.sup.[lambda].sub.k].

For a Young diagram with Frobenius coordinates [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] we define its shifted Frobenius coordinates with [A.sub.i] = [a.sub.i] + 1/2 and [B.sub.i] = [b.sub.i] + 1/2. Shifted Frobenius coordinates have a simple interpretation as positions (up to the sign) of the particles and holes in the Dirac sea corresponding to a Young diagram [Oko01]. Functionals [S.sup.[lambda].sub.k] can be nicely expressed in terms of (shifted) Frobenius coordinates as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (2)

Another way of describing the shape of a Young diagram [lambda] is to use its free cumulants [R.sup.[lambda].sub.2], [R.sup.[lambda].sub.3], ... which are defined as the coefficients of the leading terms of the polynomials (1):

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Later on we shall show how to calculate free cumulants directly from the shape of a Young diagram. [R.sub.k] is a homogeneous function of the Young diagram with degree k, i.e. [R.sup.s[lambda].sub.k] = [s.sup.k][R.sup.[lambda].sub.k].

The importance of homogeneity of [S.sup.[lambda].sub.k] and [R.sup.[lambda].sub.k] becomes clear when one wants to solve asymptotic problems, such as understanding coefficients of the polynomial (1).

1.4 Character polynomials and their applications

It is not very difficult to show [DFS08] that for each integer k [greater than or equal to] 1 there exists a polynomial with rational coefficients [J.sub.k] ([S.sub.2], [S.sub.3], ...) with a property that

[[summation].sup.[lambda].sub.k] = [J.sub.k]([S.sup.[lambda].sub.2], [S.sup.[lambda].sub.3], ...)

holds true for any Young diagram A. For example, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The polynomials [J.sub.n] are very useful, when one studies the asymptotics of characters in the limit when the parameters [[alpha].sub.1], [[alpha].sub.2], ..., [[beta].sub.1], [[beta].sub.2], ... converge to some limits and the number of boxes of [lambda] tends to infinity. Equation (2) shows that for such scaling it is convenient to consider a different gradation, in which the degree of [S.sub.k] is equal to k - 1. We leave it as an exercise to the Reader to use the results of this paper to show that with respect to this gradation polynomial [J.sub.k] has the form

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The dominant part of the right-hand side (the first summand) coincides with the estimate of Wassermann [Was81] and with Thoma character on [??]([infinity]) [VK81]. In a similar way it is possible to obtain next terms in the expansion.

One can also show that for each integer k [greater than or equal to] 1 there exists a polynomial with integer coefficients [K.sub.k] ([R.sub.2], [R.sub.3], ...), called Kerov character polynomial [Ker00, Bia03] with a property that

[[summation].sup.[lambda].sub.k] = [K.sub.k]([R.sup.[lambda].sub.2], [R.sup.[lambda].sub.3], ...)

holds true for any Young diagram [lambda]. For example,

[[summation].sub.1] = [R.sub.2], [[summation].sub.2] = [R.sub.3], [[summation].sub.3] = [R.sub.4] + [R.sub.2], [[summation].sub.4] = [R.sub.5] + 5[R.sub.3], [[summation].sub.5] = [R.sub.6] + 15[R.sub.4] + 5[R.sup.2.sub.2] + 8[R.sub.2], [[summation].sub.6] = [R.sub.7] + 35[R.sub.5] + 35[R.sub.3][R.sub.2] + 84[R.sub.3].

The advantage of Kerov polynomials [K.sub.k] over polynomials [J.sub.k] comes from the fact that they usually have a much simpler form, involve smaller number of summands and are more suitable for studying asymptotics of characters in the case of balanced Young diagrams, i.e. for example in the case of characters [[summation].sup.s[lambda].sub.k] of dilated Young diagrams [Bia03].

1.5 The main result: explicit form of character polynomials

For a permutation [pi] we denote by C([pi]) the set of the cycles of [pi].

Theorem 3 (Dolega, Feray, Sniady [DFS08]) The coefficients of polynomials [J.sub.k] are explicitly described as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

is equal to [(-1).sup.l-1] times the number of the number of the triples ([[sigma].sub.1], [[sigma].sub.2], l) where

* [[sigma].sub.1], [[sigma].sub.2] [contains as members] [??](k) are such that [[sigma].sub.1] [omicron] [[sigma].sub.2] = (1, 2, ..., k),

* l : C([[sigma].sub.2]) [right arrow] {1, ..., 1} is a bijective labeling,

* for each 1 [less than or equal to] i [less than or equal to] 1 there are exactly [j.sub.i] - 1 cycles of or which intersect cycle [l.sup.-1](i) and which do not intersect any of the cycles [l.sup.-1](i + 1), [l.sup.-1](i + 2),....

Theorem 4 (Dolega, Feray, Sniady [DFS08]) The coefficient of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] ... in the Kerov polynomial [K.sub.k] is equal to the number of triples ([[sigma].sub.1], [[sigma].sub.2], q) with the following properties:

(a) [[sigma].sub.1], [[sigma].sub.2] [member of] [??](k) are such that [[sigma].sub.1] [omicron] [[sigma].sub.2] = (1, 2, ..., k);

(b) the number of cycles of [[sigma].sub.2] is equal to the number of factors in the product [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] ...; in other words [absolute value of C([[sigma].sub.2])] = [s.sub.2] + [s.sub.3] + ...;

(c) the total number of cycles of [[sigma].sub.1] and [[sigma].sub.2] is equal to the degree of the product [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] ...; in other words [absolute value of C([[sigma].sub.1])] + [absolute value of C([[sigma].sub.1])] = 2[s.sub.2] + 3[s.sub.3] + 4[s.sub.4] + ...;

(d) q : C([[sigma].sub.2] ) [right arrow] {2, 3, ...} is a coloring of the cycles of [[sigma].sub.2] with a property that each color i [member of] {2, 3, ...} is used exactly [s.sub.i] times (informally, we can think that q is a map which to cycles of C ([[sigma].sub.2]) associates the factors in the product [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] ...);

(e) for every set A [subset] C([[sigma].sub.2]) which is nontrivial (i.e., A [not equal to] 0 and A [not equal to] C( [[sigma].sub.2])) there are more than [[summation].sub.i[member of]A] (q(i) - 1) cycles of or which intersect [union] A.

Only condition (e) is rather complicated, therefore we will provide two equivalent combinatorial conditions below.

1.6 Marriage and transportation interpretations of condition (e)

Let ([[sigma].sub.1], [[sigma].sub.2], q) be a triple which fulfills conditions (a)-(d) of Theorem 4. We consider the following polyandrous interpretation of Hall marriage theorem. Each cycle of [[sigma].sub.1] will be called a boy and each cycle of [[sigma].sub.2] will be called a girl. For each girl j [member of] C ([[sigma].sub.2]) let q(j) - 1 be the desired number of husbands of j. We say that a boy i [member of] C ([[sigma].sub.1]) is a possible candidate for a husband for a girl j [member of] C ( [[sigma].sub.2]) if cycles i and j intersect. Hall marriage theorem applied to our setup says that there exists an arrangement of marriages M : C([[sigma].sub.1]) [right arrow] C([[sigma].sub.2]) which assigns to each boy his wife (so that each girl j has exactly q(j) - 1 husbands) if and only if for every set A [subset equal to] C([[sigma].sub.2]) there are at least [[summation].sub.i[member of]A] (q(i) - 1) cycles of [[sigma].sub.1] which intersect [union] A. As one easily see, the above condition is similar but not identical to (e). The following Proposition shows the connection between these two problems.

Proposition 5 Condition (e) is equivalent to each of the following two conditions:

([e.sup.2]) for every nontrivial set of girls A [subset equal to] C([[sigma].sub.2]) (i.e., A [not equal to] 0 and A [not equal to] C([[sigma].sub.2])) there exist two ways of arranging marriages [M.sub.p] : C ([[sigma].sub.1]) [right arrow] C ([[sigma].sub.2]), p [member of] {1, 2} for which the corresponding sets of husbands of wives from A are different:

[M.sup.-1.sub.1](A) [not equal to] [M.sup.-1.sub.2](A),

([e.sup.3]) there exists a strictly positive solution to the following system of equations:

Set of variables

{[x.sub.i,j] : i [member of] C ([[sigma].sub.1]) and j [member of] C ([[sigma].sub.2]) are intersecting cycles}

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Note that the possibility of arranging marriages can be rephrased as existence of a solution to the above system of equations with a requirement that [x.sub.i.j] [member of] {0, 1}.

The system of equations in condition ([e.sup.3]) can be interpreted as a transportation problem where each cycle of [[sigma].sub.1] or is interpreted as a factory which produces a unit of some ware and each cycle j of [[sigma].sub.2] is interpreted as a consumer with a demand equal to q(j) - 1. The value of [x.sub.i,j] is interpreted as amount of ware transported from factory i to the consumer j.

1.7 General conjugacy classes

An analogue of Theorem 3 holds true with some minor modifications also for the analogues of polynomials J giving the values of characters on general permutations, not just cycles.

In case of the analogues of the Kerov polynomials giving the values of characters on more complex permutations [pi] than cycles the situation is slightly more diffcult. Namely, an analogue of Theorem 4 holds true if the character [[summation].sub.[pi]] is replaced by some quantities which behave like classical cumulants of cycles constituting n and the sum on the right-hand side is taken only over transitive factorizations. Since the expression of characters in terms of classical cumulants of cycles is straightforward, we obtain an expression of characters in terms of free cumulants.

1.8 Applications of the main result

The results of this article (Theorem 4 in particular) can be used to obtain new asymptotic inequalities for characters of the symmetric groups. This vast topic is outside of the scope of this article and will be studied in a subsequent paper.

1.9 Contents of this article

In this article we shall prove Theorem 3. Also, since the proof of Theorem 4 is rather long and technical [DFS08], in this overview article we shall highlight just the main ideas and concentrate on the first nontrivial case of quadratic terms of Kerov polynomials.

Due to lack of space we were not able to show the full history of the presented results and to give to everybody the proper credits. For more history and bibliographical references we refer to the full version of this article [DFS08].

2 Ingredients of the proof of the main result

2.1 Polynomial functions on the set of Young diagrams

Surprisingly, the normalized characters [[summation].sup.[lambda].sub.[pi]] can be extended in a natural way for any generalized Young diagram [lambda] [member of] Y. The algebra they generate will be called algebra of polynomial functions on (generalized) Young diagrams. It is well-known that many natural families of functions on Young diagrams generate the same algebra, for example the family of free cumulants ([R.sup.[lambda].sub.k]) or the family of fundamental functionals ([S.sup.[lambda].sub.k]).

[FIGURE 2 OMITTED]

2.2 Stanley polynomials

For two finite sequences of positive real numbers p = ([p.sub.1], ..., [p.sub.m]) and q = ([q.sub.1], ..., [q.sub.m]) with [q.sub.1] [greater than or equal to] ... [greater than or equal to] [q.sub.m] we consider a multirectangular generalized Young diagram pxq, cf Figure 2. In the case when [p.sub.1], ..., [p.sub.m], [q.sub.1], ..., [q.sub.m] are natural numbers p x q is a partition

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proposition 6 Let F : Y [right arrow] R be a polynomial function on the set of generalized Young diagrams. Then (p, q) [??] F(p x q) is a polynomial in in determinates [p.sub.1], ..., [p.sub.m], [q.sub.1], ..., [q.sub.m], called Stanley polynomial.

Proof: It is enough to prove this proposition for some family of generators of the algebra of polynomial functions on Y. In the case of functionals [S.sub.2], [S.sub.3], ... it is a simple exercise.

Lemma 7 If we treat p as variables and q as constants then for every k [greater than or equal to] 2 and all [i.sub.1] < ... < [i.sub.s]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (3)

Proof: The integral over the Young diagram p x q can be split into several integrals over rectangles constituting p x q therefore

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

For any [i.sub.1] < ... < [i.sub.s]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

which finishes the proof.

Theorem 8 Let F : Y [right arrow] R be a polynomial function on the set of generalized Young diagrams, we shall view it as a polynomial in [S.sub.2], [S.sub.3], ... Then for any [j.sub.1], ..., [j.sub.l] [greater than or equal to] 2

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

Proof: By linearity is enough to consider the case when [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Clearly, the left hand side is equal to the number of permutations of the sequence ([m.sub.1], ..., [m.sub.r]) which are equal to the sequence ([j.sub.1], ..., [j.sub.l]). Lemma 7 shows that the same holds true for the right-hand side.

Corollary 9 If [j.sub.1], ..., [j.sub.l] [greater than or equal to] 2 then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

does not depend on the order of the elements of the sequence ([j.sub.1], ..., [j.sub.l]).

2.3 Stanley polynomials for characters

The following theorem gives explicitly the Stanley polynomial for normalized characters of symmetric groups. It was conjectured by Stanley [Sta06] and proved by F6ray [F6r06] and therefore we refer to it as Stanley-F6ray character formula. For a more elementary proof we refer to [FS07].

Theorem 10 The value of the normalized character on [pi] [member of] [??](k) for a multirectangular Young diagram p x q for p = ([p.sub.1], ..., [p.sub.r]), q = ([q.sub.1], ..., [q.sub.r]) is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (4)

where [[phi].sub.1] : C([[sigma].sub.1]) [right arrow] {1, ..., r} is defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Notice that Theorem 8 and the above Theorem 10 give immediately the proof of Theorem 3.

2.4 Relation between free cumulants and fundamental functionals

Corollary 11 The value of the k-th free cumulant for a multirectangular Young diagram p x q for p = ([p.sub.1], ..., [p.sub.r]), q = ([q.sub.1], ..., [q.sub.r]) is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (5)

where [[phi].sub.1] : C([[sigma].sub.1]) [right arrow] {1, ..., r} is defined as in Theorem 10.

Proof: It is enough to consider the homogeneous part with degree k of both sides of (4) for [pi] = (1, ..., k - 1) [member of] [??](k - 1).

Proposition 12 For any integer n [greater than or equal to] 2

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Before the proof notice that the above formula shows that free cumulants can be explicitly and directly calculated from the shape of a Young diagram.

Proof: For simplicity, we shall proof a weaker form of this result, namely

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (6)

Theorem 8 shows that the expansion of [R.sub.k] in terms of ([S.sub.j]) involves coefficients of Stanley polynomials and the latter are given by Corollary 11. We shall use this idea in the following.

Notice that the condition [absolute value of C ([[sigma].sub.1])] + [absolute value of C ([[sigma].sub.2])] = k appearing in (5) is equivalent to [absolute value of [[sigma].sub.1]] + [absolute value of [[sigma].sub.2]] = [absolute value of [[sigma].sub.1]] [omicron] [absolute value of [[sigma].sub.2]] where [absolute value of [pi]] denotes the length of the permutation, i.e. the minimal number of factors necessary to write [pi] as a product of transpositions. In other words, [[pi].sub.1] [omicron] [[pi].sub.2] = (1, ..., k - 1) is a minimal factorization of a cycle. Such factorizations are in a bijective correspondence with non-crossing partitions of k - 1-element set [Bia96]. It is therefore enough to enumerate appropriate non-crossing partitions. We present the details of this reasoning below.

The linear term [[S.sub.k]][R.sub.k] = [[p.sub.1][q.sup.k-1.sub.1]][R.sup.pxq.sub.k] is equal to the number of minimal factorizations such that [[sigma].sub.2] consists of one cycle and [[sigma].sub.1] consists of k - 1 cycles. Such factorizations corresponds to non-crossing partitions of k - 1 element set which have exactly one block and clearly there is only one such partition.

Since both free cumulants ([R.sub.j]) and fundamental functionals of shape are homogeneous, by comparing the degrees we see that [[S.sub.j]][R.sub.k] =0 if j [not equal to] k. The same argument shows that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] if [j.sub.1] + [j.sub.2] [not equal to] k.

Instead of finding the quadratic terms [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is better to find the derivative [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] since it better takes care of the symmetric case [j.sub.1] = [j.sub.2]. The latter derivative is equal (up to the sign) to the number of minimal factorizations such that [[sigma].sub.2] consists of two labeled cycles [c.sub.1], [c.sub.2] and [[sigma].sub.1] consists of k - 2 cycles. Furthermore, we require that there are [j.sub.2] - 1 cycles of [[sigma].sub.1] which intersect cycle [c.sub.2]. This is equivalent to counting non-crossing partitions of k - 1-element set which consist of two labeled blocks [b.sub.1], [b.sub.2] and we require that the block [b.sub.2] consists of [j.sub.2] - 1 elements. It is easy to see that all such non-crossing partitions can be transformed into each other by a cyclic rotation hence there are k - 1 of them which finishes the proof.

The general case can be proved by analogous but more technically involved combinatorial considerations.

2.5 Identities fulfilled by coefficients of Stanley polynomials

The coefficients of Stanley polynomials [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII][F.sup.pxq] for a polynomial function F are not linearly independent; in fact they fulfill many identities. In the following we shall show just one of them.

Lemma 13 For any polynomial function F : Y [right arrow] R

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (7)

Proof: It is enough to prove the Lemma if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a monomial in fundamental functionals. Lemma 7 shows that the left-hand side of (7) is non-zero only if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (it is also a consequence of Theorem 8); otherwise every monomial in p and q with a nonzero coefficient would be at least quadratic with respect to the variables p. The same argument shows that if the right-hand side is non-zero then either F = [S.sub.k] is linear (in this case k = [j.sub.1] + [j.sub.2] by comparing the degrees) or [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is quadratic. In the latter case, an inspection of the coefficient

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

thanks to (3) leads to a contradiction.

It remains to show that for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] the Lemma holds true, but this is an immediate consequence of Lemma 7.

3 Toy example: Quadratic terms of Kerov polynomials

We shall prove Theorem 4 in the simplest non-trivial case of the quadratic coefficients [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. In this case Theorem 4 takes the following equivalent form.

Theorem 14 For all integers [j.sub.1], [j.sub.2] [greater than or equal to] 2 and k [greater than or equal to] 1 the derivative

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

is equal to the number of triples ([[sigma].sub.1], [[sigma].sub.2], q) with the following properties:

(a) [[sigma].sub.1], [[sigma].sub.2] is a factorization of the cycle; in other words [[sigma].sub.1], [[sigma].sub.2] [member of] [??](k) are such that [[sigma].sub.1] [omicron] [[sigma].sub.2] = (1, 2, ..., k);

(b) [[sigma].sub.2] consists of two cycles;

(c) [[sigma].sub.1] consists of [j.sub.1] + [j.sub.2] - 2 cycles;

(d) l : C([[sigma].sub.2]) [right arrow] {1, 2} is a bijective labeling of the two cycles of [[sigma].sub.2];

(e) for each cycle c [member of] C([[sigma].sub.2]) there are at least [j.sub.l(c)] cycles of [[sigma].sub.1] which intersect nontrivially c.

Proof: Equation (6) shows that for any polynomial function F on the set of generalized Young diagrams

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where all derivatives are taken at [R.sub.2] = [R.sub.3] = ... = [S.sub.2] = [S.sub.3] = ... = 0. Theorem 8 shows that the right-hand side is equal to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Lemma 13 applied to the second summand shows therefore that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (8)

On the other hand, let us compute the number of the triples ([[sigma].sub.1], [[sigma].sub.2], l) which contribute to the quantity presented in Theorem 14. By inclusion-exclusion principle it is equal to

(number of triples which fulfill conditions (a)-(d)) + (-1)(number of triples for which the cycle [l.sup.-1] (1) intersects at most [j.sub.1] - 1 cycles of [[sigma].sub.1]) + (-1) (number of triples for which the cycle [l.sup.-1] (2) intersects at most [j.sub.2] - 1 cycles of [[sigma].sub.1]). (9)

At first sight it might seem that the above formula is not complete since we should also add the number of triples for which the cycle [l.sup.-1](1) intersects at most [j.sub.1] - 1 cycles of o1 and the cycle [l.sup.-1](2) intersects at most [j.sub.2] - 1 cycles of [[sigma].sub.1], however this situation is not possible since [[sigma].sub.1] consists of [j.sub.1] + [j.sub.2] - 2 cycles and ([[sigma].sub.1], [[sigma].sub.2]) acts transitively.

By Stanley-Feray character formula (4) the first summand of (9) is equal to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (10)

the second summand of (9) is equal to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (11)

and the third summand of (9) is equal to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We can apply Corollary 9 to the summands of (11); it follows that (11) is equal to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (12)

It remains now to count how many times a pair (a, b) contributes to the sum of (10), (11), (12). It is not difficult to see that the only pairs which contribute are (0, [j.sub.1] + [j.sub.2] - 2) and ([j.sub.1] - 1, [j.sub.2] - 1), therefore the number of triples described in the formulation of the Theorem is equal to the right-hand of (8) which finishes the proof.

References

[Bia96] Philippe Biane. Minimal factorizations of a cycle and central multiplicative functions on the infinite symmetric group. J. Combin. Theory Ser. A, 76(2):197-212, 1996.

[Bia03] Philippe Biane. Characters of symmetric groups and free cumulants. In Asymptotic combinatorics with applications to mathematical physics (St. Petersburg, 2001), volume 1815 of Lecture Notes in Math., pages 185-200. Springer, Berlin, 2003.

[DFS08] Maciej Dolega, Valentin F6ray, and Piotr Sniady. Explicit combinatorial interpretation of Kerov character polynomials as numbers of permutation factorizations. Preprint arXiv:0810.3209, 2008.

[F6r06] Valentin F6ray. Proof of Stanley's conjecture about irreducible character values of the symmetric group. Preprint arXiv:math.CO/0612090, 2006.

[FS07] Valentin F6ray and Piotr Sniady. Asymptotics of characters of symmetric groups related to Stanley-Feray character formula. Preprint arXiv:math/0701051, 2007.

[Ker00] S. Kerov. Talk in Institute Henri Poincare, Paris, January 2000.

[Oko01] Andrei Okounkov. Infinite wedge and random partitions. Selecta Math. (N.S.), 7(1):57-81, 2001.

[Sta06] Richard P. Stanley. A conjectured combinatorial interpretation of the normalized irreducible character values of the symmetric group. Preprint arXiv:math.CO/0606467, 2006.

[VK81] A. M. Vershik and S. V. Kerov. Asymptotic theory of the characters of a symmetric group. Funktsional. Anal. i Prilozhen., 15(4):15-27, 96, 1981.

[Was81] Anthony John Wassermann. Automorphic actions of compact groups on operator algebras. PhD thesis, University of Pennsylvania, 1981.

Maciej Dolega (1), Valentin Feray (2) and Piotr Sniady (1)([dagger])

(1) Institute of Mathematics, University of Wroclaw, pl. Grunwaldzki 2/4, 50-384 Wroclaw, Poland

(2) The Gaspard-Monge Institute of Electronics and Computer Science, University of Marne-La-Vallee Paris-Est, 77454 Marne-la-Vallee Cedex 2, France

([dagger]) Supported by the MNiSW research grant P03A 013 30, by the EU Research Training Network "QP-Applications", contract HPRN-CT-2002-00279 and by the EC Marie Curie Host Fellowship for the Transfer of Knowledge "Harmonic Analysis, Nonlinear Analysis and Probability", contract MTKD-CT-2004-013389. PS thanks Marek Bozejko, Philippe Biane, Akihito Hora, Jonathan Novak, Swiatoslaw Gal and Jan Dymara for several stimulating discussions during various stages of this research project.

This contribution is an extended abstract of a full version [DFS08] which will be published elsewhere.

1.1 Dilations of Young diagrams and normalized characters

For a Young diagram [lambda] and an integer s [greater than or equal to] 1 we denote by s[lambda] the dilation of [lambda] by factor s. This operation can be easily described on a graphical representation of a Young diagram: we just dilate the picture of [lambda] or, alternatively, we replace each box of [lambda] by a grid of s x s boxes.

[FIGURE 1 OMITTED]

Any permutation [pi] [member of] [??](k) can be also regarded as an element of [??](n) if k [less than or equal to] n (we just declare that [pi] [member of] [??](n) has additional n - k fixpoints). For any [pi] [member of] [??](k) and an irreducible representation [[rho].sup.[lambda]] of the symmetric group [??](n) corresponding to the Young diagram [lambda] we define the normalized character

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

We shall concentrate our attention on the characters on cycles, therefore we will use the special notation

[[summation].sup.[lambda].sub.k] = [[summation].sup.[lambda].sub.(1, 2, ..., k)],

where we treat the cycle (1, 2, ..., k) as an element of [??](k) for any integer k [greater than or equal to] 1.

The notion of dilation of a Young diagram is very useful from the viewpoint of the asymptotic representation theory because it allows us to ask the following question:

Problem 1 What can we say about the characters of the symmetric groups in the limit when the Young diagram [lambda] tends in some sense to infinity in a way that [lambda] preserves its shape?

This informal problem can be formalized as follows: for fixed [lambda] and k we ask about (asymptotic) properties of the normalized characters [[summation].sup.s[lambda].sub.k] in the limit s [right arrow] [infinity]. The reason why we decided to study this particular normalization of characters is the following well-known yet surprising result.

Fact 2 For any Young diagram [lambda] and integer k [greater than or equal to] 2 the normalized character on a dilated diagram

N [contains as members] s [??] [[summation].sup.s[lambda].sub.k-1] (1)

is a polynomial function of degree (at most) k.

1.2 Generalized Young diagrams

Any Young diagram drawn in the French convention can be identified with its graph which is equal to the set {(x, y) : 0 [less than or equal to] x, 0 [less than or equal to] y [less than or equal to] f(x)} for a suitably chosen function f : [R.sub.+] [right arrow] [R.sub.+], where [R.sub.+] = [0, [infinity]), cf. Figure 1. It is therefore natural to define the set of generalized Young diagrams Y (in the French convention) as the set of bounded, non-increasing functions f : [R.sub.+] [right arrow] [R.sub.+] with a compact support; in this way any Young diagram can be regarded as a generalized Young diagram. Notice that with the notion of generalized Young diagrams we may consider dilations s[lambda] for any real s [greater than or equal to] 0.

1.3 How to describe the shape of a Young diagram?

Our ultimate goal is to explicitly express the polynomials (1) in terms of the shape of [lambda]. However, before we start this task we must ask ourselves: how to describe the shape of [lambda] in the best way? In the folowing we shall present two approaches to this problem.

We define the fundamental functionals of shape of a Young diagram [lambda] by an integral over the area of [lambda]

[S.sup.[lambda].sub.k] = (k - 1) [integral][[integral].sub.(x,y)[member of][lambda]] [[(contents.sub.(x,y)]).sup.k-2] dx dy

for integer k [greater than or equal to] 2, and where [contents.sub.(x,y)] = x - y is the contents of a point of a Young diagram. When it does not lead to confusions we will skip the explicit dependence of the fundamental functionals on Young diagrams and instead of [S.sup.[lambda].sub.k] we shall simply write [S.sub.k]. Clearly, each functional [S.sub.k] is a homogeneous function of the Young diagram with degree k, i.e. [S.sup.s[lambda].sub.k] = [s.sup.k][S.sup.[lambda].sub.k].

For a Young diagram with Frobenius coordinates [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] we define its shifted Frobenius coordinates with [A.sub.i] = [a.sub.i] + 1/2 and [B.sub.i] = [b.sub.i] + 1/2. Shifted Frobenius coordinates have a simple interpretation as positions (up to the sign) of the particles and holes in the Dirac sea corresponding to a Young diagram [Oko01]. Functionals [S.sup.[lambda].sub.k] can be nicely expressed in terms of (shifted) Frobenius coordinates as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (2)

Another way of describing the shape of a Young diagram [lambda] is to use its free cumulants [R.sup.[lambda].sub.2], [R.sup.[lambda].sub.3], ... which are defined as the coefficients of the leading terms of the polynomials (1):

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Later on we shall show how to calculate free cumulants directly from the shape of a Young diagram. [R.sub.k] is a homogeneous function of the Young diagram with degree k, i.e. [R.sup.s[lambda].sub.k] = [s.sup.k][R.sup.[lambda].sub.k].

The importance of homogeneity of [S.sup.[lambda].sub.k] and [R.sup.[lambda].sub.k] becomes clear when one wants to solve asymptotic problems, such as understanding coefficients of the polynomial (1).

1.4 Character polynomials and their applications

It is not very difficult to show [DFS08] that for each integer k [greater than or equal to] 1 there exists a polynomial with rational coefficients [J.sub.k] ([S.sub.2], [S.sub.3], ...) with a property that

[[summation].sup.[lambda].sub.k] = [J.sub.k]([S.sup.[lambda].sub.2], [S.sup.[lambda].sub.3], ...)

holds true for any Young diagram A. For example, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The polynomials [J.sub.n] are very useful, when one studies the asymptotics of characters in the limit when the parameters [[alpha].sub.1], [[alpha].sub.2], ..., [[beta].sub.1], [[beta].sub.2], ... converge to some limits and the number of boxes of [lambda] tends to infinity. Equation (2) shows that for such scaling it is convenient to consider a different gradation, in which the degree of [S.sub.k] is equal to k - 1. We leave it as an exercise to the Reader to use the results of this paper to show that with respect to this gradation polynomial [J.sub.k] has the form

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The dominant part of the right-hand side (the first summand) coincides with the estimate of Wassermann [Was81] and with Thoma character on [??]([infinity]) [VK81]. In a similar way it is possible to obtain next terms in the expansion.

One can also show that for each integer k [greater than or equal to] 1 there exists a polynomial with integer coefficients [K.sub.k] ([R.sub.2], [R.sub.3], ...), called Kerov character polynomial [Ker00, Bia03] with a property that

[[summation].sup.[lambda].sub.k] = [K.sub.k]([R.sup.[lambda].sub.2], [R.sup.[lambda].sub.3], ...)

holds true for any Young diagram [lambda]. For example,

[[summation].sub.1] = [R.sub.2], [[summation].sub.2] = [R.sub.3], [[summation].sub.3] = [R.sub.4] + [R.sub.2], [[summation].sub.4] = [R.sub.5] + 5[R.sub.3], [[summation].sub.5] = [R.sub.6] + 15[R.sub.4] + 5[R.sup.2.sub.2] + 8[R.sub.2], [[summation].sub.6] = [R.sub.7] + 35[R.sub.5] + 35[R.sub.3][R.sub.2] + 84[R.sub.3].

The advantage of Kerov polynomials [K.sub.k] over polynomials [J.sub.k] comes from the fact that they usually have a much simpler form, involve smaller number of summands and are more suitable for studying asymptotics of characters in the case of balanced Young diagrams, i.e. for example in the case of characters [[summation].sup.s[lambda].sub.k] of dilated Young diagrams [Bia03].

1.5 The main result: explicit form of character polynomials

For a permutation [pi] we denote by C([pi]) the set of the cycles of [pi].

Theorem 3 (Dolega, Feray, Sniady [DFS08]) The coefficients of polynomials [J.sub.k] are explicitly described as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

is equal to [(-1).sup.l-1] times the number of the number of the triples ([[sigma].sub.1], [[sigma].sub.2], l) where

* [[sigma].sub.1], [[sigma].sub.2] [contains as members] [??](k) are such that [[sigma].sub.1] [omicron] [[sigma].sub.2] = (1, 2, ..., k),

* l : C([[sigma].sub.2]) [right arrow] {1, ..., 1} is a bijective labeling,

* for each 1 [less than or equal to] i [less than or equal to] 1 there are exactly [j.sub.i] - 1 cycles of or which intersect cycle [l.sup.-1](i) and which do not intersect any of the cycles [l.sup.-1](i + 1), [l.sup.-1](i + 2),....

Theorem 4 (Dolega, Feray, Sniady [DFS08]) The coefficient of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] ... in the Kerov polynomial [K.sub.k] is equal to the number of triples ([[sigma].sub.1], [[sigma].sub.2], q) with the following properties:

(a) [[sigma].sub.1], [[sigma].sub.2] [member of] [??](k) are such that [[sigma].sub.1] [omicron] [[sigma].sub.2] = (1, 2, ..., k);

(b) the number of cycles of [[sigma].sub.2] is equal to the number of factors in the product [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] ...; in other words [absolute value of C([[sigma].sub.2])] = [s.sub.2] + [s.sub.3] + ...;

(c) the total number of cycles of [[sigma].sub.1] and [[sigma].sub.2] is equal to the degree of the product [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] ...; in other words [absolute value of C([[sigma].sub.1])] + [absolute value of C([[sigma].sub.1])] = 2[s.sub.2] + 3[s.sub.3] + 4[s.sub.4] + ...;

(d) q : C([[sigma].sub.2] ) [right arrow] {2, 3, ...} is a coloring of the cycles of [[sigma].sub.2] with a property that each color i [member of] {2, 3, ...} is used exactly [s.sub.i] times (informally, we can think that q is a map which to cycles of C ([[sigma].sub.2]) associates the factors in the product [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] ...);

(e) for every set A [subset] C([[sigma].sub.2]) which is nontrivial (i.e., A [not equal to] 0 and A [not equal to] C( [[sigma].sub.2])) there are more than [[summation].sub.i[member of]A] (q(i) - 1) cycles of or which intersect [union] A.

Only condition (e) is rather complicated, therefore we will provide two equivalent combinatorial conditions below.

1.6 Marriage and transportation interpretations of condition (e)

Let ([[sigma].sub.1], [[sigma].sub.2], q) be a triple which fulfills conditions (a)-(d) of Theorem 4. We consider the following polyandrous interpretation of Hall marriage theorem. Each cycle of [[sigma].sub.1] will be called a boy and each cycle of [[sigma].sub.2] will be called a girl. For each girl j [member of] C ([[sigma].sub.2]) let q(j) - 1 be the desired number of husbands of j. We say that a boy i [member of] C ([[sigma].sub.1]) is a possible candidate for a husband for a girl j [member of] C ( [[sigma].sub.2]) if cycles i and j intersect. Hall marriage theorem applied to our setup says that there exists an arrangement of marriages M : C([[sigma].sub.1]) [right arrow] C([[sigma].sub.2]) which assigns to each boy his wife (so that each girl j has exactly q(j) - 1 husbands) if and only if for every set A [subset equal to] C([[sigma].sub.2]) there are at least [[summation].sub.i[member of]A] (q(i) - 1) cycles of [[sigma].sub.1] which intersect [union] A. As one easily see, the above condition is similar but not identical to (e). The following Proposition shows the connection between these two problems.

Proposition 5 Condition (e) is equivalent to each of the following two conditions:

([e.sup.2]) for every nontrivial set of girls A [subset equal to] C([[sigma].sub.2]) (i.e., A [not equal to] 0 and A [not equal to] C([[sigma].sub.2])) there exist two ways of arranging marriages [M.sub.p] : C ([[sigma].sub.1]) [right arrow] C ([[sigma].sub.2]), p [member of] {1, 2} for which the corresponding sets of husbands of wives from A are different:

[M.sup.-1.sub.1](A) [not equal to] [M.sup.-1.sub.2](A),

([e.sup.3]) there exists a strictly positive solution to the following system of equations:

Set of variables

{[x.sub.i,j] : i [member of] C ([[sigma].sub.1]) and j [member of] C ([[sigma].sub.2]) are intersecting cycles}

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Note that the possibility of arranging marriages can be rephrased as existence of a solution to the above system of equations with a requirement that [x.sub.i.j] [member of] {0, 1}.

The system of equations in condition ([e.sup.3]) can be interpreted as a transportation problem where each cycle of [[sigma].sub.1] or is interpreted as a factory which produces a unit of some ware and each cycle j of [[sigma].sub.2] is interpreted as a consumer with a demand equal to q(j) - 1. The value of [x.sub.i,j] is interpreted as amount of ware transported from factory i to the consumer j.

1.7 General conjugacy classes

An analogue of Theorem 3 holds true with some minor modifications also for the analogues of polynomials J giving the values of characters on general permutations, not just cycles.

In case of the analogues of the Kerov polynomials giving the values of characters on more complex permutations [pi] than cycles the situation is slightly more diffcult. Namely, an analogue of Theorem 4 holds true if the character [[summation].sub.[pi]] is replaced by some quantities which behave like classical cumulants of cycles constituting n and the sum on the right-hand side is taken only over transitive factorizations. Since the expression of characters in terms of classical cumulants of cycles is straightforward, we obtain an expression of characters in terms of free cumulants.

1.8 Applications of the main result

The results of this article (Theorem 4 in particular) can be used to obtain new asymptotic inequalities for characters of the symmetric groups. This vast topic is outside of the scope of this article and will be studied in a subsequent paper.

1.9 Contents of this article

In this article we shall prove Theorem 3. Also, since the proof of Theorem 4 is rather long and technical [DFS08], in this overview article we shall highlight just the main ideas and concentrate on the first nontrivial case of quadratic terms of Kerov polynomials.

Due to lack of space we were not able to show the full history of the presented results and to give to everybody the proper credits. For more history and bibliographical references we refer to the full version of this article [DFS08].

2 Ingredients of the proof of the main result

2.1 Polynomial functions on the set of Young diagrams

Surprisingly, the normalized characters [[summation].sup.[lambda].sub.[pi]] can be extended in a natural way for any generalized Young diagram [lambda] [member of] Y. The algebra they generate will be called algebra of polynomial functions on (generalized) Young diagrams. It is well-known that many natural families of functions on Young diagrams generate the same algebra, for example the family of free cumulants ([R.sup.[lambda].sub.k]) or the family of fundamental functionals ([S.sup.[lambda].sub.k]).

[FIGURE 2 OMITTED]

2.2 Stanley polynomials

For two finite sequences of positive real numbers p = ([p.sub.1], ..., [p.sub.m]) and q = ([q.sub.1], ..., [q.sub.m]) with [q.sub.1] [greater than or equal to] ... [greater than or equal to] [q.sub.m] we consider a multirectangular generalized Young diagram pxq, cf Figure 2. In the case when [p.sub.1], ..., [p.sub.m], [q.sub.1], ..., [q.sub.m] are natural numbers p x q is a partition

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proposition 6 Let F : Y [right arrow] R be a polynomial function on the set of generalized Young diagrams. Then (p, q) [??] F(p x q) is a polynomial in in determinates [p.sub.1], ..., [p.sub.m], [q.sub.1], ..., [q.sub.m], called Stanley polynomial.

Proof: It is enough to prove this proposition for some family of generators of the algebra of polynomial functions on Y. In the case of functionals [S.sub.2], [S.sub.3], ... it is a simple exercise.

Lemma 7 If we treat p as variables and q as constants then for every k [greater than or equal to] 2 and all [i.sub.1] < ... < [i.sub.s]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (3)

Proof: The integral over the Young diagram p x q can be split into several integrals over rectangles constituting p x q therefore

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

For any [i.sub.1] < ... < [i.sub.s]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

which finishes the proof.

Theorem 8 Let F : Y [right arrow] R be a polynomial function on the set of generalized Young diagrams, we shall view it as a polynomial in [S.sub.2], [S.sub.3], ... Then for any [j.sub.1], ..., [j.sub.l] [greater than or equal to] 2

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

Proof: By linearity is enough to consider the case when [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Clearly, the left hand side is equal to the number of permutations of the sequence ([m.sub.1], ..., [m.sub.r]) which are equal to the sequence ([j.sub.1], ..., [j.sub.l]). Lemma 7 shows that the same holds true for the right-hand side.

Corollary 9 If [j.sub.1], ..., [j.sub.l] [greater than or equal to] 2 then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

does not depend on the order of the elements of the sequence ([j.sub.1], ..., [j.sub.l]).

2.3 Stanley polynomials for characters

The following theorem gives explicitly the Stanley polynomial for normalized characters of symmetric groups. It was conjectured by Stanley [Sta06] and proved by F6ray [F6r06] and therefore we refer to it as Stanley-F6ray character formula. For a more elementary proof we refer to [FS07].

Theorem 10 The value of the normalized character on [pi] [member of] [??](k) for a multirectangular Young diagram p x q for p = ([p.sub.1], ..., [p.sub.r]), q = ([q.sub.1], ..., [q.sub.r]) is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (4)

where [[phi].sub.1] : C([[sigma].sub.1]) [right arrow] {1, ..., r} is defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Notice that Theorem 8 and the above Theorem 10 give immediately the proof of Theorem 3.

2.4 Relation between free cumulants and fundamental functionals

Corollary 11 The value of the k-th free cumulant for a multirectangular Young diagram p x q for p = ([p.sub.1], ..., [p.sub.r]), q = ([q.sub.1], ..., [q.sub.r]) is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (5)

where [[phi].sub.1] : C([[sigma].sub.1]) [right arrow] {1, ..., r} is defined as in Theorem 10.

Proof: It is enough to consider the homogeneous part with degree k of both sides of (4) for [pi] = (1, ..., k - 1) [member of] [??](k - 1).

Proposition 12 For any integer n [greater than or equal to] 2

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Before the proof notice that the above formula shows that free cumulants can be explicitly and directly calculated from the shape of a Young diagram.

Proof: For simplicity, we shall proof a weaker form of this result, namely

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (6)

Theorem 8 shows that the expansion of [R.sub.k] in terms of ([S.sub.j]) involves coefficients of Stanley polynomials and the latter are given by Corollary 11. We shall use this idea in the following.

Notice that the condition [absolute value of C ([[sigma].sub.1])] + [absolute value of C ([[sigma].sub.2])] = k appearing in (5) is equivalent to [absolute value of [[sigma].sub.1]] + [absolute value of [[sigma].sub.2]] = [absolute value of [[sigma].sub.1]] [omicron] [absolute value of [[sigma].sub.2]] where [absolute value of [pi]] denotes the length of the permutation, i.e. the minimal number of factors necessary to write [pi] as a product of transpositions. In other words, [[pi].sub.1] [omicron] [[pi].sub.2] = (1, ..., k - 1) is a minimal factorization of a cycle. Such factorizations are in a bijective correspondence with non-crossing partitions of k - 1-element set [Bia96]. It is therefore enough to enumerate appropriate non-crossing partitions. We present the details of this reasoning below.

The linear term [[S.sub.k]][R.sub.k] = [[p.sub.1][q.sup.k-1.sub.1]][R.sup.pxq.sub.k] is equal to the number of minimal factorizations such that [[sigma].sub.2] consists of one cycle and [[sigma].sub.1] consists of k - 1 cycles. Such factorizations corresponds to non-crossing partitions of k - 1 element set which have exactly one block and clearly there is only one such partition.

Since both free cumulants ([R.sub.j]) and fundamental functionals of shape are homogeneous, by comparing the degrees we see that [[S.sub.j]][R.sub.k] =0 if j [not equal to] k. The same argument shows that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] if [j.sub.1] + [j.sub.2] [not equal to] k.

Instead of finding the quadratic terms [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is better to find the derivative [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] since it better takes care of the symmetric case [j.sub.1] = [j.sub.2]. The latter derivative is equal (up to the sign) to the number of minimal factorizations such that [[sigma].sub.2] consists of two labeled cycles [c.sub.1], [c.sub.2] and [[sigma].sub.1] consists of k - 2 cycles. Furthermore, we require that there are [j.sub.2] - 1 cycles of [[sigma].sub.1] which intersect cycle [c.sub.2]. This is equivalent to counting non-crossing partitions of k - 1-element set which consist of two labeled blocks [b.sub.1], [b.sub.2] and we require that the block [b.sub.2] consists of [j.sub.2] - 1 elements. It is easy to see that all such non-crossing partitions can be transformed into each other by a cyclic rotation hence there are k - 1 of them which finishes the proof.

The general case can be proved by analogous but more technically involved combinatorial considerations.

2.5 Identities fulfilled by coefficients of Stanley polynomials

The coefficients of Stanley polynomials [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII][F.sup.pxq] for a polynomial function F are not linearly independent; in fact they fulfill many identities. In the following we shall show just one of them.

Lemma 13 For any polynomial function F : Y [right arrow] R

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (7)

Proof: It is enough to prove the Lemma if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a monomial in fundamental functionals. Lemma 7 shows that the left-hand side of (7) is non-zero only if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (it is also a consequence of Theorem 8); otherwise every monomial in p and q with a nonzero coefficient would be at least quadratic with respect to the variables p. The same argument shows that if the right-hand side is non-zero then either F = [S.sub.k] is linear (in this case k = [j.sub.1] + [j.sub.2] by comparing the degrees) or [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is quadratic. In the latter case, an inspection of the coefficient

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

thanks to (3) leads to a contradiction.

It remains to show that for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] the Lemma holds true, but this is an immediate consequence of Lemma 7.

3 Toy example: Quadratic terms of Kerov polynomials

We shall prove Theorem 4 in the simplest non-trivial case of the quadratic coefficients [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. In this case Theorem 4 takes the following equivalent form.

Theorem 14 For all integers [j.sub.1], [j.sub.2] [greater than or equal to] 2 and k [greater than or equal to] 1 the derivative

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

is equal to the number of triples ([[sigma].sub.1], [[sigma].sub.2], q) with the following properties:

(a) [[sigma].sub.1], [[sigma].sub.2] is a factorization of the cycle; in other words [[sigma].sub.1], [[sigma].sub.2] [member of] [??](k) are such that [[sigma].sub.1] [omicron] [[sigma].sub.2] = (1, 2, ..., k);

(b) [[sigma].sub.2] consists of two cycles;

(c) [[sigma].sub.1] consists of [j.sub.1] + [j.sub.2] - 2 cycles;

(d) l : C([[sigma].sub.2]) [right arrow] {1, 2} is a bijective labeling of the two cycles of [[sigma].sub.2];

(e) for each cycle c [member of] C([[sigma].sub.2]) there are at least [j.sub.l(c)] cycles of [[sigma].sub.1] which intersect nontrivially c.

Proof: Equation (6) shows that for any polynomial function F on the set of generalized Young diagrams

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where all derivatives are taken at [R.sub.2] = [R.sub.3] = ... = [S.sub.2] = [S.sub.3] = ... = 0. Theorem 8 shows that the right-hand side is equal to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Lemma 13 applied to the second summand shows therefore that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (8)

On the other hand, let us compute the number of the triples ([[sigma].sub.1], [[sigma].sub.2], l) which contribute to the quantity presented in Theorem 14. By inclusion-exclusion principle it is equal to

(number of triples which fulfill conditions (a)-(d)) + (-1)(number of triples for which the cycle [l.sup.-1] (1) intersects at most [j.sub.1] - 1 cycles of [[sigma].sub.1]) + (-1) (number of triples for which the cycle [l.sup.-1] (2) intersects at most [j.sub.2] - 1 cycles of [[sigma].sub.1]). (9)

At first sight it might seem that the above formula is not complete since we should also add the number of triples for which the cycle [l.sup.-1](1) intersects at most [j.sub.1] - 1 cycles of o1 and the cycle [l.sup.-1](2) intersects at most [j.sub.2] - 1 cycles of [[sigma].sub.1], however this situation is not possible since [[sigma].sub.1] consists of [j.sub.1] + [j.sub.2] - 2 cycles and ([[sigma].sub.1], [[sigma].sub.2]) acts transitively.

By Stanley-Feray character formula (4) the first summand of (9) is equal to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (10)

the second summand of (9) is equal to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (11)

and the third summand of (9) is equal to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We can apply Corollary 9 to the summands of (11); it follows that (11) is equal to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (12)

It remains now to count how many times a pair (a, b) contributes to the sum of (10), (11), (12). It is not difficult to see that the only pairs which contribute are (0, [j.sub.1] + [j.sub.2] - 2) and ([j.sub.1] - 1, [j.sub.2] - 1), therefore the number of triples described in the formulation of the Theorem is equal to the right-hand of (8) which finishes the proof.

References

[Bia96] Philippe Biane. Minimal factorizations of a cycle and central multiplicative functions on the infinite symmetric group. J. Combin. Theory Ser. A, 76(2):197-212, 1996.

[Bia03] Philippe Biane. Characters of symmetric groups and free cumulants. In Asymptotic combinatorics with applications to mathematical physics (St. Petersburg, 2001), volume 1815 of Lecture Notes in Math., pages 185-200. Springer, Berlin, 2003.

[DFS08] Maciej Dolega, Valentin F6ray, and Piotr Sniady. Explicit combinatorial interpretation of Kerov character polynomials as numbers of permutation factorizations. Preprint arXiv:0810.3209, 2008.

[F6r06] Valentin F6ray. Proof of Stanley's conjecture about irreducible character values of the symmetric group. Preprint arXiv:math.CO/0612090, 2006.

[FS07] Valentin F6ray and Piotr Sniady. Asymptotics of characters of symmetric groups related to Stanley-Feray character formula. Preprint arXiv:math/0701051, 2007.

[Ker00] S. Kerov. Talk in Institute Henri Poincare, Paris, January 2000.

[Oko01] Andrei Okounkov. Infinite wedge and random partitions. Selecta Math. (N.S.), 7(1):57-81, 2001.

[Sta06] Richard P. Stanley. A conjectured combinatorial interpretation of the normalized irreducible character values of the symmetric group. Preprint arXiv:math.CO/0606467, 2006.

[VK81] A. M. Vershik and S. V. Kerov. Asymptotic theory of the characters of a symmetric group. Funktsional. Anal. i Prilozhen., 15(4):15-27, 96, 1981.

[Was81] Anthony John Wassermann. Automorphic actions of compact groups on operator algebras. PhD thesis, University of Pennsylvania, 1981.

Maciej Dolega (1), Valentin Feray (2) and Piotr Sniady (1)([dagger])

(1) Institute of Mathematics, University of Wroclaw, pl. Grunwaldzki 2/4, 50-384 Wroclaw, Poland

(2) The Gaspard-Monge Institute of Electronics and Computer Science, University of Marne-La-Vallee Paris-Est, 77454 Marne-la-Vallee Cedex 2, France

([dagger]) Supported by the MNiSW research grant P03A 013 30, by the EU Research Training Network "QP-Applications", contract HPRN-CT-2002-00279 and by the EC Marie Curie Host Fellowship for the Transfer of Knowledge "Harmonic Analysis, Nonlinear Analysis and Probability", contract MTKD-CT-2004-013389. PS thanks Marek Bozejko, Philippe Biane, Akihito Hora, Jonathan Novak, Swiatoslaw Gal and Jan Dymara for several stimulating discussions during various stages of this research project.

Printer friendly Cite/link Email Feedback | |

Author: | Dolega, Maciej; Feray, Valentin; Sniady, Piotr |
---|---|

Publication: | DMTCS Proceedings |

Article Type: | Report |

Geographic Code: | 4EXPO |

Date: | Jan 1, 2009 |

Words: | 5010 |

Previous Article: | On wiring and tiling diagrams related to bases of tropical Plucker functions. |

Next Article: | K-distant crossings and nestings of matchings and partitions. |

Topics: |