, ,

Version of 3/9/05

y Jason Fulman (fulman@math.pitt.edu)

niversity of Pittsburgh Math Department, 414 Thackeray Hall Pittsburgh, PA 15260

<ph f="cmr"> </ph><ph f="cmbx">An Inductive Proof of the Berry-Esseen Theorem for Character Ratios</ph>

B

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

2000 Mathematics Subject Classification: 05E10, 60C05.

Key words and phrases: character ratio, Berry-Esseen theorem, Stein's method, Plancherel measure, Jack polynomial.

1 Introduction

The Plancherel measure of a finite group

G

is a probability measure on the set of irreducible representations of

G

which chooses a representation

ρ

with probability

\frac{d i m (ρ)^{2}}{| G |}

, where

d i m (ρ)

denotes the dimension of

ρ

. For instance if

G

is the symmetric group, the irreducible representations are parameterized by partitions

λ

n

, and the Plancherel measure chooses a partition

λ

with probability

\frac{n!}{\prod_{x \in λ} h (x)^{2}}

where the product is over boxes in the partition and

h (x)

is the hooklength of a box. The hooklength of a box

x

is defined as 1 + number of boxes in same row as x and to the right of x + number of boxes in same column of x and below x. For example we have filled in each box in the partition of 7 below with its hooklength

\begin{matrix} 6 & 4 & 2 & 1 \end{matrix}

\begin{matrix} 3 & 1 \end{matrix}

\begin{matrix} 1 \end{matrix}

and the Plancherel measure would choose this partition with probability

\frac{7!}{(6 * 4 * 3 * 2)^{2}}

. Recently there has been interest in the statistical properties of partitions chosen from Plancherel measure and we refer the reader to the surveys [AlD] , [De] and the seminal papers [J] , [O1] , [BOO] for a glimpse of the remarkable recent work on Plancherel measure. We recommend [Sa] as an introduction to representation theory of the symmetric group.

Let

λ

be a partition of

n

chosen from the Plancherel measure of the symmetric group

S_{n}

and let

χ^{λ} (12)

be the irreducible character parameterized by

λ

evaluated on the transposition

(12)

. The quantity

\frac{χ^{λ} (12)}{d i m (λ)}

is called a character ratio and is crucial for analyzing the convergence rate of the random walk on the symmetric group generated by transpositions [DSh] . In fact Diaconis and Shahshahani prove that the eigenvalues for this random walk are the character ratios

\frac{χ^{λ} (12)}{d i m (λ)}

each occurring with multiplicity

d i m (λ)^{2}

Character ratios on transpositions also play an essential role in work on the moduli space of curves [EO] , [OP] .

Given these motivations, it is natural to study the distribution of the character ratio

\frac{χ^{λ} (12)}{d i m (λ)}

and there has been a substantial amount of work in this direction, which we now summarize. Kerov [K1] proved that if

λ

is chosen from the Plancherel measure of the symmetric group, then for all real

x_{0}

l i m_{n \to \infty} P (\frac{n - 1}{\sqrt{2}} \frac{χ^{λ} (12)}{d i m (λ)} \leq x_{0}) = \frac{1}{\sqrt{2 π}} \int_{- \infty}^{x_{0}} e^{- \frac{t^{2}}{2}} d t .

The details of Kerov's argument appeared in [IO] , which gave a beautiful development of Kerov's work. Hora [Ho] gave another proof of Kerov's result, exploiting the fact that the kth moment of a Plancherel distributed character ratio is equal to the chance that the random walk generated by random transpositions is at the identity after k steps. Both of these proofs were essentially combinatorial in nature and used the method of moments (and so information about all moments of the character ratio). Recent work of Sniady [Sn1] , [Sn2] understands these moments in terms of the genus expansion from random matrix theory.

A more probabilistic approach to Kerov's result appeared in [F1] , which proved that for all

n \geq 2

and real

x_{0}

| P (\frac{n - 1}{\sqrt{2}} \frac{χ^{λ} (12)}{d i m (λ)} \leq x_{0}) - \frac{1}{\sqrt{2 π}} \int_{- \infty}^{x_{0}} e^{- \frac{t^{2}}{2}} d t | \leq 40.1 n^{- 1 / 4} .

The proof used Stein's method (which is fundamentally different from the method of moments as it only uses information about a few lower order moments) and random walk on the set of irreducible representations of the symmetric group. Note that unlike Kerov's original result, this result includes an error term. The paper [F3] used martingale theory to sharpen the error term to

C_{s} n^{- s}

for any

s < \frac{1}{2}

where

C_{s}

is a constant depending on

s

. The paper [ShSu] developed a refinement of Stein's method which led to a proof of the conjecture of [F1] that an error term of

C n^{- \frac{1}{2}}

holds where

C

is a universal constant. A second proof of this conjecture appears in [CF] , using a different refinement of Stein's method. Both of these proofs used the “exchangeable pairs” approach to Stein's method.

The purpose of the present paper is to use a completely different technique to prove a bound of

40 n^{- \frac{1}{2}}

. The method is based on Bolthausen's [Bol] ingenious inductive proof of the Berry-Esseen theorem for sums of independent identically distributed random variables. As in [F3] , we write the character ratio as a sum of martingale differences, but these are neither independent nor identically distributed so some subtle combinatorics is required to adapt Bolthausen's method. This is not the first example of adapting Bolthausen's method to the non i.i.d. case; Bolthausen [Bol] used the approach to study the distribution of

\sum_{1 \leq i \leq n} A_{i π (i)}

where

A

is a fixed

n \times n

matrix and

π

is a random permutation on

n

symbols. But the case of character ratios is of considerable interest and quite unlike any other example to which his technique has been applied.

Note that a central limit theorem is known for some other conjugacy classes of the symmetric group [K1] , [IO] , [Ho] , but with no information about the error term (see the end of Section 2 for a conjecture). The technique of this paper does not obviously extend, however, since in Section 2 when we write

\frac{(\binom{n}{2}) χ^{λ} (12)}{d i m (λ)}

as a sum of martingale differences, we require the fact that the expected value of the square of a summand given the previous summands is constant. This is false for general conjugacy classes. Also it is a nontrivial combinatorial problem to give upper bounds on the expected absolute value of the cubes of the summands. Fortunately for the case of transpositions this can be done without much difficulty. And the case of transpositions does seem to have unique practical importance [EO] , [OP] .

The contents of this paper are as follows. Section 2 develops the combinatorics needed to adapt Bolthausen's method to the case of character ratios, and then proves an upper bound of

40 n^{- 1 / 2}

. Section 3 then recalls the Jack

_{α}

measure on partitions (here

α > 0

is a parameter) and why it is interesting.

It then briefly indicates the modifications to the Plancherel case needed to prove a central limit theorem with an error term of

C_{α} n^{- 1 / 2}

, where

C_{α}

is a constant depending on

α

. This organization is natural since many algebraically inclined readers will want to understand the result for character ratios without needing combinatorics of Jack polynomials; thus a key lemma is given an algebraic proof in Section 2 and a combinatorial proof in Section 3 .

2 Central limit theorem for Plancherel measure

The random variable we wish to study is

T_{n} (λ) = \frac{\sqrt{(\binom{n}{2})} χ^{λ} (12)}{d i m (λ)}

where

λ

is chosen from the Plancherel measure of the symmetric group

S_{n}

. To begin we write

T_{n}

as a sum of other random variables. For this we need Kerov's growth process on partitions [K2] ; this has a natural generalization to arbitrary finite groups [F3] , but we only recall it in the case of interest. Given a partition

λ (j)

of size

j

, one obtains a partition

λ (j + 1)

of size

j + 1

by choosing

λ (j + 1)

with probability

\frac{d i m (λ (j + 1))}{(j + 1) d i m (λ (j))}

λ (j + 1)

can be obtained from

λ (j)

by adding a single box, and with probability 0 otherwise. Thus starting from

λ (1)

, the unique partition of size

1

, one obtains a random sequence

(λ (1), \dots, λ (n))

of partitions. Kerov [K2] proves that each

λ (j)

is distributed according to the Plancherel measure of

S_{j}

Given Kerov's growth process, one can write

T_{n} = \frac{1}{\sqrt{(\binom{n}{2})}} (X_{1} + \dots + X_{n})

where

X_{1} = 0

χ^{λ (1)} (12)

is defined as 0, and

X_{j} = \frac{(\binom{j}{2}) χ^{λ (j)} (12)}{d i m (λ (j))} - \frac{(\binom{j - 1}{2}) χ^{λ (j - 1)} (12)}{d i m (λ (j - 1))}

for

j \geq 2

Lemma 2.1 states that the

X_{j}

are martingale differences satisfying special properties. We remark that [F3] extends this lemma to more general conjugacy classes and groups. The notation

E (A | \cdot)

means the expected value of

A

given

\cdot

Lemma 2.1. ([F3] )

(1) $E (X_{j} | λ (j - 1)) = 0$ for $2 \leq j \leq n$ and all partitions $λ (j - 1)$ .
(2) $E (X_{j} | T_{n}) = \frac{j - 1}{\sqrt{(\binom{n}{2})}} T_{n}$ for all $1 \leq j \leq n$ .
(3) $E (X_{j}^{2}) = j - 1$ .
(4) $E (T_{n}^{2}) = 1$ .

Frobenius [Fr] found the following explicit formula for the character ratio of the symmetric group on transpositions:

\frac{χ^{λ} (12)}{d i m (λ)} = \frac{1}{(\binom{n}{2})} \sum_{i} ((\binom{λ_{i}}{2}) - (\binom{λ_{i}^{'}}{2}))

where

λ_{i}

is the length of row

i

λ

and

λ_{i}^{'}

is the length of column

i

λ

. From his formula it follows that

X_{j} = c (x)

where

x

is the box added to

λ (j - 1)

to obtain

λ (j)

and the “content”

c (x)

of a box is defined as column number of box row number of box.

Lemma 2.2 gives the conditional second and fourth moments of the

X_{j}

's.

We emphasize that these were not derived or even stated in terms of character ratios, but rather were proved in a completely combinatorial way by studying the behavior of the moments of

c (x)

where

x

is the box added during Kerov's growth process. We remark that for other conjugacy classes, there is not an analog of the fact that

E (X_{j}^{2} | λ (j - 1))

is independent of

λ (j - 1)

Lemma 2.2. Let

λ (j - 1)

be a partition of size

j - 1 \geq 1

(1) ([K3] ) $E (X_{j}^{2} | λ (j - 1)) = j - 1$ .
(2) ([La] ) $E (X_{j}^{4} | λ (j - 1)) = (\binom{j}{2}) + 3 \sum_{x \in λ (j - 1)} c (x)^{2}$ .

Lemma 2.3 is a useful identity. Although a combinatorial proof can be given using properties of Schur functions, we defer combinatorial arguments to the more general setting of Jack polynomials in Section 3 and give an algebraic proof.

Lemma 2.3. Let

e_{r} (z_{1}, \dots, z_{n}) = \sum_{1 \leq i_{1} < \dots < i_{r} \leq n} z_{i_{1}} \dots z_{i_{r}}

be the rth elementary symmetric function of

z_{1}, \dots, z_{n}

. For

λ

a partition of

n

, let

e_{r} (λ)

denote the rth elementary symmetric function of the contents of the boxes of

λ

. Then

E (e_{r} (λ)) = 0

for

1 \leq r \leq n

Proof. If $r = n$ the result is clear since the box in the first row and column of $λ$ has content 0, so that $e_{n} (λ) = 0$ for all $λ$ .
For $1 \leq r < n$ , we use the theory of Murphy elements [Mu] ; a friendly reference giving background on these elements is [DG] . For $2 \leq i \leq n$ , the ith Murphy element is defined as the sum of transpositions $R_{i} = \sum_{1 \leq j < i} (j, i)$ .
Let $z$ be the element of the group algebra of $S_{n}$ which is the sum of all permutations with $n - r$ cycles. By Proposition 2.1 of [DG] , $z$ is the rth elementary symmetric function of the elements $R_{2}, \dots, R_{n}$ .
Since the elements $R_{2}, \dots, R_{n}$ are simultaneously diagonalizable in every irreducible representation of the symmetric group, it follows from Murphy's determination of their eigenvalues that in the representation of $S_{n}$ parameterized by $λ$ , $z$ is a scalar multiple of the $d i m (λ) \times d i m (λ)$ identity matrix with scalar equal to $e_{r} (λ)$ . In the regular representation of $S_{n}$ the irreducible representation parameterized by $λ$ occurs with multiplicity $d i m (λ)$ . Hence the trace of $z$ in the regular representation is $n! E (e_{r} (λ))$ . But the coefficient of the identity in $z$ is 0, so the trace of $z$ in the regular representation is 0, implying the result. □

Lemma 2.4 gives upper bounds for

E (| X_{n} |^{3})

and for

E (| T_{n - 1} | | X_{n} |^{3})

Lemma 2.4. Suppose that

n \geq 3

(1) $E (| X_{n} |^{3}) \leq (n - 1) \sqrt{2 n - 3}$ .
(2) $E (| T_{n - 1} | | X_{n} |^{3}) \leq (n - 1) \sqrt{2 n - 3}$ .

Proof. By the Cauchy-Schwarz inequality,

E (| X_{n} |^{3}) \leq \sqrt{E (X_{n}^{2}) E (X_{n}^{4})}

. By Lemma 2.2 ,

E (X_{n}^{2}) = n - 1

and

E (X_{n}^{4}) = E (E (X_{n}^{4} | λ (n - 1))) = (\binom{n}{2}) + 3 E (\sum_{x \in λ (n - 1)} c (x)^{2}) .

By Lemma 2.3 with

r = 2

and then part 4 of Lemma 2.1 ,

\begin{matrix} E (\sum_{x \in λ (n - 1)} c (x)^{2}) & = & E [{(\sum_{x \in λ (n - 1)} c (x))}^{2} - 2 e_{2} (λ (n - 1))] \end{matrix}

\begin{matrix} = & (\binom{n - 1}{2}) E (T_{n - 1}^{2}) \end{matrix}

\begin{matrix} = & (\binom{n - 1}{2}) . \end{matrix}

This proves the first assertion.

For the second assertion, note (using part 4 of Lemma 2.1 in the final equality) that

\begin{matrix} E (| T_{n - 1} | | X_{n} |^{3}) & = & E (E (| T_{n - 1} | | X_{n} |^{3} | λ (n - 1))) \end{matrix}

\begin{matrix} = & E (| T_{n - 1} | E (| X_{n} |^{3} | λ (n - 1))) \end{matrix}

\begin{matrix} \leq & \sqrt{E (T_{n - 1}^{2}) E (E (| X_{n} |^{3} | λ (n - 1))^{2})} \end{matrix}

\begin{matrix} = & \sqrt{E (E (| X_{n} |^{3} | λ (n - 1))^{2})} . \end{matrix}

The conditional version of the Cauchy-Schwarz inequality and part 1 of Lemma 2.2 give that

E (| X_{n} |^{3} | λ (n - 1))^{2}

is at most

E (X_{n}^{2} | λ (n - 1)) E (X_{n}^{4} | λ (n - 1)) = (n - 1) E (X_{n}^{4} | λ (n - 1)) .

Thus

\sqrt{E (E (| X_{n} |^{3} | λ (n - 1))^{2})} \leq \sqrt{(n - 1) E (X_{n}^{4})},

and the proof of the first assertion showed this to equal

(n - 1) \sqrt{2 n - 3}

, as desired. □

Now we adapt Bolthausen's [Bol] inductive proof of the Berry-Esseen theorem for i.i.d. random variables to the setting of character ratios. We remark that the unpublished notes of Mann [Man] are a useful exposition of Bolthausen's proof and we refer to them in the proof of Theorem 2.5 .

Theorem 2.5. Let

λ

be chosen from the Plancherel measure on partitions of size

n

. Then for all

n \geq 2

and real

x_{0}

| P (T_{n} (λ) \leq x_{0}) - \frac{1}{\sqrt{2 π}} \int_{- \infty}^{x_{0}} e^{- \frac{t^{2}}{2}} d t | \leq 40 n^{- 1 / 2} .

Proof. The theorem is visibly true for

n = 2

, so throughout we suppose that

n \geq 3

For

z

real, let

h_{z, 0} = I_{(- \infty, z]}

be the indicator function of the set

(- \infty, z]

For

z

real and

b > 0

, let

h_{z, b}

be the function which is 1 for

x \leq z

and then drops linearly to the value 0 at

z + b

and is 0 for

x \geq z + b

. Let

δ (b, n) = {sup}_{z} {| E (h_{z, b} (T_{n})) - Φ h_{z, b} |}

where

Φ f

is the expected value of a function f under the normal distribution.

Note that our ultimate goal is to upper bound

δ (0, n)

As in Stein's method [Stn] , let

f (x) = f_{z, b} (x) = e^{x^{2} / 2} \int_{- \infty}^{x} (h_{z, b} (w) - Φ h_{z, b}) e^{- w^{2} / 2} d w .

Then

f^{'} (x) - x f (x) = h_{z, b} (x) - Φ h_{z, b}

, so that

E (h_{z, b} (T_{n})) - Φ h_{z, b} = E [f^{'} (T_{n}) - T_{n} f (T_{n})] .

Part 2 of Lemma 2.1 with

j = n

implies that

E (X_{n} f (T_{n})) = E [f (T_{n}) E (X_{n} | T_{n})] = \frac{n - 1}{\sqrt{(\binom{n}{2})}} E (T_{n} f (T_{n})),

so that

E [f^{'} (T_{n}) - T_{n} f (T_{n})] = E [f^{'} (T_{n}) - \frac{\sqrt{(\binom{n}{2})}}{n - 1} X_{n} f (T_{n})] .

By part 1 of Lemma 2.1 and part 1 of Lemma 2.2 , this is equal to

\begin{matrix} E [f^{'} (T_{n})] + E [\frac{X_{n}^{2}}{n - 1} f^{'} (\sqrt{\frac{n - 2}{n}} T_{n - 1}) - f^{'} (\sqrt{\frac{n - 2}{n}} T_{n - 1})] \end{matrix}

\begin{matrix} - E [\frac{\sqrt{(\binom{n}{2})}}{n - 1} X_{n} f (T_{n}) - \frac{\sqrt{(\binom{n}{2})}}{n - 1} X_{n} f (\sqrt{\frac{n - 2}{n}} T_{n - 1})] \end{matrix}

\begin{matrix} = & E [f^{'} (T_{n}) - f^{'} (\sqrt{\frac{n - 2}{n}} T_{n - 1})] \end{matrix}

\begin{matrix} - E [\frac{X_{n}^{2}}{n - 1} \int_{0}^{1} f^{'} (\sqrt{\frac{n - 2}{n}} T_{n - 1} + t \frac{X_{n}}{\sqrt{(\binom{n}{2})}}) - f^{'} (\sqrt{\frac{n - 2}{n}} T_{n - 1}) d t] . \end{matrix}

Next we upper bound

E [f^{'} (T_{n}) - f^{'} (\sqrt{\frac{n - 2}{n}} T_{n - 1})]

. Recall from [Bol] or [Man] that for any

x

and

Δ

| f^{'} (x + Δ) - f^{'} (x) | \leq | Δ | (3 + 2 | x | + \frac{1}{b} \int_{0}^{1} I_{[z, z + b]} (x + s Δ) d s) .

Thus

E [f^{'} (T_{n}) - f^{'} (\sqrt{\frac{n - 2}{n}} T_{n - 1})] \leq A_{1} + A_{2} + A_{3}

where

$∙$ $A_{1} = \frac{3 E (| X_{n} |)}{\sqrt{(\binom{n}{2})}}$ .
$∙$ $A_{2} = \frac{2 \sqrt{\frac{n - 2}{n}}}{\sqrt{(\binom{n}{2})}} E (| X_{n} | | T_{n - 1} |)$ .
$∙$ $A_{3} = \frac{1}{b \sqrt{(\binom{n}{2})}} \int_{0}^{1} E (| X_{n} | E (I_{[z, z + b]} (\sqrt{\frac{n - 2}{n}} T_{n - 1} + \frac{s X_{n}}{\sqrt{(\binom{n}{2})}}) | X_{n})) d s$ .

By part 3 of Lemma 2.1 ,

E | X_{n} | \leq \sqrt{E (X_{n}^{2})} = \sqrt{n - 1}

; thus

A_{1} \leq \frac{3 \sqrt{2}}{\sqrt{n}}

. By parts 3 and 4 of Lemma 2.1 ,

E (| X_{n} | | T_{n - 1} |) \leq \sqrt{E (X_{n}^{2}) E (T_{n - 1}^{2})} = \sqrt{n - 1} .

Thus

A_{2} \leq \frac{2 \sqrt{2}}{\sqrt{n}}

. To bound

A_{3}

, we use the fact (explained in [Man] ) that

0 \leq E (I_{B} (c_{1} T_{n} + c_{2})) \leq \frac{| B |}{c_{1} \sqrt{2 π}} + 2 δ (0, n)

for any interval

B

and constants

c_{1}, c_{2}

with

c_{1} \neq 0

. This, together with the fact (used in bounding

A_{1}

) that

E | X_{n} | \leq \sqrt{n - 1}

, implies that

A_{3} \leq \sqrt{\frac{2}{n}} (\sqrt{\frac{n}{n - 2}} \frac{1}{\sqrt{2 π}} + \frac{2 δ (0, n - 1)}{b}) \leq \frac{\sqrt{2}}{\sqrt{n}} (1 + \frac{2 δ (0, n - 1)}{b}) .

Summarizing, we conclude that

E [f^{'} (T_{n}) - f^{'} (\sqrt{\frac{n - 2}{2}} T_{n - 1})] \leq \frac{\sqrt{2}}{\sqrt{n}} (6 + \frac{2 δ (0, n - 1)}{b}) .

Next, we upper bound

E | \frac{X_{n}^{2}}{n - 1} \int_{0}^{1} [f^{'} (\sqrt{\frac{n - 2}{n}} T_{n - 1} + t \frac{X_{n}}{\sqrt{(\binom{n}{2})}}) - f^{'} (\sqrt{\frac{n - 2}{n}} T_{n - 1})] d t | .

Arguing as in the previous paragraph this is at most

B_{1} + B_{2} + B_{3}

where

$∙$ $B_{1} = \frac{1}{n - 1} \int_{0}^{1} \frac{3 t E | X_{n} |^{3}}{\sqrt{(\binom{n}{2})}} d t = \frac{3 E | X_{n} |^{3}}{2 (n - 1) \sqrt{(\binom{n}{2})}}$ .
$∙$ $B_{2} = \frac{1}{n - 1} \int_{0}^{1} \frac{2 t \sqrt{\frac{n - 2}{n}}}{\sqrt{(\binom{n}{2})}} E (| T_{n - 1} | | X_{n} |^{3}) d t = \frac{\sqrt{\frac{n - 2}{n}}}{(n - 1) \sqrt{(\binom{n}{2})}} E (| T_{n - 1} | | X_{n} |^{3})$ .
$∙$ $B_{3} = \frac{1}{n - 1} E [\int_{0}^{1} \frac{t | X_{n} |^{3}}{b \sqrt{(\binom{n}{2})}} \int_{0}^{1} E (I_{[z, z + b]} (\sqrt{\frac{n - 2}{n}} T_{n - 1} + s t \frac{X_{n}}{\sqrt{(\binom{n}{2})}}) | X_{n}) d s d t]$ .

To bound

B_{1}

, use part 1 of Lemma 2.4 to conclude that

B_{1} \leq \frac{3}{\sqrt{n}}

. To bound

B_{2}

, use part 2 of Lemma 2.4 to conclude that

B_{2} \leq \frac{2}{\sqrt{n}}

. To bound

B_{3}

, note that by the reasoning used in bounding

A_{3}

E (I_{[z, z + b]} (\sqrt{\frac{n - 2}{n}} T_{n - 1} + s t \frac{X_{n}}{\sqrt{(\binom{n}{2})}}) | X_{n}) \leq \frac{b}{\sqrt{2 π}} \sqrt{\frac{n}{n - 2}} + 2 δ (0, n - 1) .

Thus

B_{3} \leq \frac{E | X_{n} |^{3}}{2 (n - 1) \sqrt{(\binom{n}{2})}} [\frac{1}{\sqrt{2 π}} \sqrt{\frac{n}{n - 2}} + \frac{2 δ (0, n - 1)}{b}]

. By part 1 of Lemma 2.4 and since

n \geq 3

, this implies that

B_{3} \leq \frac{1}{\sqrt{n}} + \frac{2 δ (0, n - 1)}{b \sqrt{n}}

. To summarize,

B_{1} + B_{2} + B_{3} \leq \frac{6}{\sqrt{n}} + \frac{2 δ (0, n - 1)}{b \sqrt{n}}

The previous two paragraphs imply that

δ (b, n) \leq \frac{(\sqrt{2} + 1)}{\sqrt{n}} (6 + \frac{2 δ (0, n - 1)}{b}) \leq \frac{15}{\sqrt{n}} + \frac{5 δ (0, n - 1)}{b \sqrt{n}} .

From [Bol] or [Man] ,

δ (0, n) \leq δ (b, n) + \frac{b}{\sqrt{2 π}}

for all

b

, which implies that

δ (0, n) \leq \frac{15}{\sqrt{n}} + \frac{5 δ (0, n - 1)}{b \sqrt{n}} + \frac{b}{\sqrt{2 π}} .

Choosing

b = \frac{10 \sqrt{3}}{\sqrt{2} \sqrt{n}}

gives that

δ (0, n) \leq \frac{20}{\sqrt{n}} + \frac{δ (0, n - 1) \sqrt{2}}{2 \sqrt{3}}

. The result now follows by induction since

\frac{20}{\sqrt{n}} + \frac{δ (0, n - 1) \sqrt{2}}{2 \sqrt{3}} \leq \frac{20}{\sqrt{n}} + \frac{20 \sqrt{2}}{\sqrt{3} \sqrt{n - 1}} \leq \frac{40}{\sqrt{n}}

for

n \geq 3

. □

To conclude this section, we note that it would be of interest to prove the following (more general) conjecture.

Conjecture: Let

i \geq 2

be fixed. Then for all

n \geq i

and real

x_{0}

| P (\sqrt{\frac{n!}{(n - i)! i}} \frac{χ^{λ} (12 \dots i)}{d i m (λ)} \leq x_{0}) - \frac{1}{\sqrt{2 π}} \int_{- \infty}^{x_{0}} e^{- \frac{t^{2}}{2}} d t | \leq C_{i} n^{- 1 / 2}

where

C_{i}

is a constant depending on

i

3 Central limit theorem for Jack measure

For

α > 0

the Jack

_{α}

measure on partitions of size

n

chooses a partition

λ

with probability

\frac{α^{n} n!}{\prod_{x \in λ} (α a (x) + l (x) + 1) (α a (x) + l (x) + α)},

where the product is over all boxes in the partition. Here

a (x)

denotes the number of boxes in the same row of

x

and to the right of

x

(the “arm” of x) and

l (x)

denotes the number of boxes in the same column of

x

and below

x

(the “leg” of x). For example the partition of 5 below

\begin{matrix}  \end{matrix}

\begin{matrix}  \end{matrix}

would have Jack

_{α}

measure

\frac{30 α^{2}}{(3 α + 1) (α + 2) (2 α + 1) (α + 1)^{2}} .

Note that when

α = 1

, Jack measure reduces to Plancherel measure of the symmetric group. The papers [O2] , [BO] emphasize that for

α

fixed the study of Jack

_{α}

measure is an important open problem, about which relatively little is known for general values of

α

. It is a discrete analog of eigenvalue ensembles from random matrix theory and like Jack polynomials [GHJ] , should also be relevant to the moduli space of curves.

Given

α > 0

, the quantity to be studied is

T_{n, α} (λ) = \frac{\sum_{i} (α (\binom{λ_{i}}{2}) - (\binom{λ_{i}^{'}}{2}))}{\sqrt{α (\binom{n}{2})}},

where as usual

λ_{i}

is the length of the ith row of

λ

and

λ_{i}^{'}

is the length of the ith column of

λ

. It is of interest to study the quantity

T_{n} (α)

under Jack measure for several reasons. When

α = 1

it reduces to the study of the character ratio of transpositions under Plancherel measure. When

α = 2

it is a spherical function of the Gelfand pair

(S_{2 n}, H_{2 n})

where

H_{2 n}

is the hyperoctahedral group of size

2^{n} n!

. Also by Corollary 1 of [DHol] , there is a natural random walk on perfect matchings of the complete graph on

n

vertices, whose eigenvalues are precisely

\frac{T_{n, 2} (λ)}{\sqrt{n (n - 1)}}

, occurring with multiplicity proportional to the Jack

_{2}

measure of

λ

The paper [F2] used the “exchangeable pairs” version of Stein's method to prove a central limit theorem for

T_{n, α}

with error term

C_{α} n^{- 1 / 4}

where

C_{α}

is a constant depending on

α

. This was sharpened in [F3] using martingales to

C_{α, s} n^{- s}

for any

s < \frac{1}{2}

, and the paper [CF] gives a bound

C_{α} n^{- 1 / 2}

using a refinement of the “exchangeable pairs” version of Stein's method.

The main result of this section is Theorem 3.1 .

Theorem 3.1. Suppose that

α \geq 1

and let

λ

be chosen from the Jack

_{α}

measure on partitions of size

n

. Then there is a constant

C_{α}

depending on

α

so that for all

n \geq 2

and real

x_{0}

| P (T_{n, α} (λ) \leq x_{0}) - \frac{1}{\sqrt{2 π}} \int_{- \infty}^{x_{0}} e^{- \frac{t^{2}}{2}} d t | \leq C_{α} n^{- 1 / 2} .

Note that in Theorem 3.1 we suppose that

α \geq 1

since the Jack

_{α}

probability of

λ

is equal to the Jack

_{\frac{1}{α}}

probability of the transpose of

λ

, implying that for any

x

, the Jack

_{α}

probability that

T_{n, α} = x

is equal to the Jack

_{\frac{1}{α}}

probability that

T_{n, \frac{1}{α}} = - x

. Also note that

C_{α}

must depend on

α

, since by Corollary 5.3 of [F2] , the random variable

T_{n, α}

has mean 0, variance 1, and third moment

\frac{α - 1}{\sqrt{α (\binom{n}{2})}}

There is no need to write out a proof of Theorem 3.1 , which uses exactly the same logic as that of Theorem 2.5 . But it is necessary to give analogs of Lemmas 2.1 , 2.2 , 2.3 , and 2.4 , and we do that.

There is an

α

-analog of Kerov's growth process (due to Kerov [K4] ) giving a sequence of partitions

(λ (1), \dots, λ (n))

with

λ (j)

distributed according to the Jack

_{α}

measure on partitions of size

j

; see [F3] for details. Moreover from the definition of

T_{n, α}

, it follows that

T_{n, α} = \frac{1}{\sqrt{α (\binom{n}{2})}} (X_{1, α} + \dots + X_{n, α}) .

Here

X_{1, α} = 0

and if

j \geq 2

then

X_{j, α} = c_{α} (x)

where

x

is the box added to

λ (j - 1)

to obtain

λ (j)

and the “

α

-content”

c_{α} (x)

of a box

x

is defined to be

α

(column number of x-1) (row number of x-1).

Lemma 3.2 is an analog of Lemma 2.1 and is generalized in [F3] to arbitrary spherical functions of the Gelfand pair

(S_{2 n}, H_{2 n})

Lemma 3.2. ([F3] )

(1) $E (X_{j, α} | λ (j - 1)) = 0$ for $2 \leq j \leq n$ and all partitions $λ (j - 1)$ .
(2) $E (X_{j, α} | T_{n, α}) = \frac{(j - 1) \sqrt{α}}{\sqrt{(\binom{n}{2})}} T_{n, α}$ for all $1 \leq j \leq n$ .
(3) $E (X_{j, α}^{2}) = α (j - 1)$ .
(4) $E (T_{n, α}^{2}) = 1$ .

Lemma 3.3 is the

α

version of Lemma 2.2 .

Lemma 3.3. Let

λ (j - 1)

be a partition of size

j - 1 \geq 1

(1) ([K4] ) $E (X_{j, α}^{2} | λ (j - 1)) = α (j - 1)$ .

(2) ([La] )

\begin{matrix} E (X_{j, α}^{4} | λ (j - 1)) & = & α^{2} (\binom{j}{2}) + α (α - 1)^{2} (j - 1) + 3 α \sum_{x \in λ (j - 1)} c_{α} (x)^{2} \end{matrix}

\begin{matrix} + 3 α (α - 1) \sum_{x \in λ (j - 1)} c_{α} (x) . \end{matrix}

Lemma 3.4 is the

α

version of Lemma 2.3 . The proof is combinatorial, as opposed to the algebraic argument given for Lemma 2.3 .

Lemma 3.4. Consider the Jack

_{α}

measure on partitions of size

n

(1) If $m \geq 1$ is an integer then $E (\prod_{x \in λ} (m + c_{α} (x))) = m^{n} .$
(2) Let $e_{r, α} (λ)$ denote the $r$ th elementary symmetric function of the $α$ -contents of the boxes of $λ$ . Then $E (e_{r, α} (λ)) = 0$ for $1 \leq r \leq n$ .

Proof. It suffices to prove the first assertion since the second assertion follows from the first by taking the coefficient of $m^{n - r}$ on both sides. Page 324 of [Mac] proves the identity $\sum_{λ} b_{λ} (q, t) P_{λ} (y; q, t) P_{λ} (z; q, t) = e^{\sum_{n \geq 1} (\frac{1 - t^{n}}{1 - q^{n}} \frac{p_{n} (y) p_{n} (z)}{n})}$ where the sum is over all $λ$ of all sizes, $P_{λ} (y; q, t)$ denotes a Macdonald symmetric function, $p_{n} (y) = \sum_{i} y_{i}^{n}$ denotes the nth power sum symmetric function, and $b_{λ} (q, t)$ is a number to be discussed more below. We apply the homomorphism of the ring of symmetric functions determined by $p_{r} (y) \mapsto m u^{r}$ , $p_{r} (z) \mapsto l^{1 - r}$ for all $r \geq 1$ where $m, l$ are positive integers; this is possible since the $p_{r}$ 's are algebraically independent. Then we take the limit $q = t^{α}, t \mapsto 1$ in which Macdonald polynomials become Jack polynomials.
With these substitutions, consider the left hand side of the identity. By pages 380 and 381 of [Mac] , $b_{λ} (q, t) \mapsto \prod_{x \in λ} \frac{α a (x) + l (x) + 1}{α a (x) + l (x) + α}$ $P_{λ} (y; q, t) \mapsto u^{| λ |} \prod_{x \in λ} \frac{m + c_{α} (x)}{α a (x) + l (x) + 1}$ $P_{λ} (z; q, t) \mapsto \frac{1}{l^{| λ |}} \prod_{x \in λ} \frac{l + c_{α} (x)}{α a (x) + l (x) + 1} .$ Letting $l \to \infty$ , one sees that the coefficient of $u^{n}$ in the left-hand side of the identity is $\frac{1}{α^{n} n!} E (\prod_{x \in λ} (m + c_{α} (x)))$ .
Consider the right hand side of the identity with these substitutions. One obtains $e^{\sum_{n \geq 1} (\frac{m u^{n}}{n α l^{n - 1}})}$ . Letting $l \to \infty$ , one obtains $e^{\frac{m u}{α}}$ , and taking the coefficient of $u^{n}$ gives $\frac{m^{n}}{α^{n} n!}$ . Comparing with the previous paragraph proves the first assertion of the lemma. □

Finally, we give the analog of Lemma 2.4 .

Lemma 3.5. Suppose that

n \geq 3

. There is a constant

D_{α}

such that

(1) $E (| X_{n, α} |^{3}) \leq D_{α} n^{3 / 2}$ .
(2) $E (| T_{n - 1, α} | | X_{n, α} |^{3}) \leq D_{α} n^{3 / 2}$ .

Proof. The proof method is the same as that of Lemma 2.4 , using the Cauchy-Schwarz inequality in the first part and the conditional Cauchy-Schwarz inequality in the second part. One uses that

E (X_{n, α}^{2} | λ (n - 1)) = α (n - 1)

for all

λ (n - 1)

(part 1 of Lemma 3.3 ). Also one needs that

\begin{matrix} E (X_{n, α}^{4}) & = & α^{2} (\binom{n}{2}) + α (α - 1)^{2} (n - 1) + 3 α E (\sum_{x \in λ (n - 1)} c_{α} (x)^{2}) \end{matrix}

\begin{matrix} = & α^{2} (\binom{n}{2}) + 3 α^{2} (\binom{n - 1}{2}) + α (α - 1)^{2} (n - 1) . \end{matrix}

The first equality used part 2 of Lemma 3.3 and the fact that

E (T_{n, α}) = 0

The second equality used part 4 of Lemma 3.2 and Lemma 3.4 with

r = 2

. □

4 Acknowledgements

The author was partially supported by NSA grant number H98230-05-1-0031. References

Aldous, D. and Diaconis, P., Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem, Bull. AMS (N.S.) 36 (1999), 413-432.
Bolthausen, E., An estimate of the remainder term in a combinatorial central limit theorem, Z. Wahrsch. Verw. Gebiete 66 (1984), 379-386.
Borodin, A., Okounkov, A., and Olshanski, G., Asymptotics of Plancherel measures for symmetric groups, J. Amer. Math. Soc. 13 (2000), 481-515.
Borodin, A. and Olshanski, G., Z-measures on partitions and their scaling limits, preprint math-ph/0210048 at http://xxx.lanl.gov.
Chatterjee, S. and Fulman, J., Stein's method for chi-squared approximation and spectral measure of Gelfand pairs, in preparation.
Deift, P., Integrable systems and combinatorial theory, Notices Amer. Math. Soc. 47 (2000), 631-640.
Diaconis, P. and Greene, C., Applications of Murphy's elements, Stanford University technical report no. 335 (1989).
Diaconis, P. and Holmes, S., Random walk on trees and matchings, Elec. J. Probab. 7 (2002), 17 pages (electronic).
Diaconis, P. and Shahshahani, M., Generating a random permutation with random transpositions, Z. Wahr. Verw. Gebiete 57 (1981), 159-179.
Eskin, A. and Okounkov, A., Asymptotics of branched coverings of a torus and volumes of moduli spaces of holomorphic differentials, Invent. Math. 145 (2001), 59-103.
Frobenuis, F., Uber die charaktere der symmetrischen gruppe, Sitz. Konig. Preuss. Akad. Wissen. (1900), 516-534; Gesammelte abhandlungen III, Springer-Verlag, Heidelberg, 1968, 148-166.
Fulman, J., Stein's method and Plancherel measure of the symmetric group, Transac. Amer. Math. Soc. 357 (2005), 555-570.
Fulman, J., Stein's method, Jack measure, and the Metropolis algorithm, J. Combin. Theory Ser. A 108 (2004), 275-296.
Fulman, J., Martingales and character ratios, to appear in Transac. Amer. Math. Soc., available at http://www.math.pitt.edu/ $\sim$ fulman.
Goulden, I., Harer, J., and Jackson, D., A geometric parametrization for the virtual Euler characteristic of the moduli spaces of real and complex algebraic curves, Trans. Amer. Math. Soc. 353 (2001), 4405-4427.
Hora, A., Central limit theorem for the adjacency operators on the infinite symmetric group, Comm. Math. Phys. 195 (1998), 405-416.
Ivanov, V. and Olshanski, G., Kerov's central limit theorem for the Plancherel measure on Young diagrams, in Symmetric Functions 2001: Surveys of developments and perspectives, Kluwer Academic Publishers, Dodrecht, 2002.
Johansson, K., Discrete orthogonal polynomial ensembles and the Plancherel measure, Ann. of Math. (2) 153 (2001), 259-296.
Kerov. S.V., Gaussian limit for the Plancherel measure of the symmetric group, Compt. Rend. Acad. Sci. Paris, Serie I, 316 (1993), 303-308.
Kerov, S.V., The boundary of Young lattice and random Young tableaux, in Formal power series and algebraic combinatorics, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 24, Amer. Math. Soc., Providence, RI, (1996), 133-158.
Kerov, S.V., Transition probabilities of continual Young diagrams and the Markov moment problem, Funct. Anal. Appl. 27 (1993), 104-117.
Kerov, S.V., Anisotropic Young diagrams and Jack symmetric functions, Funct. Anal. Appl. 34 (2000), 41-51.
Lassalle, M., Jack polynomials and some identities for partitions, Trans. Amer. Math. Soc. 356 (2004), 3455-3476.
Macdonald, I., Symmetric functions and Hall polynomials, Second edition, Oxford University Press, New York, 1995.
Mann, B., Bolthausen's proof of Berry-Esseen, unpublished manuscript (1994).
Murphy, G.E., A new construction of Young's seminormal representation of the symmetric group, J. Algebra 69 (1981), 287-291.
Okounkov, A., Random matrices and random permutations, Internat. Math. Res. Notices 20 (2000), 1043-1095.
Okounkov, A., The uses of random partitions, preprint math-ph/0309015 at http://xxx.lanl.gov.
Okounkov, A. and Pandaripandhe, R., Gromov-Witten theory, Hurwitz numbers, and Matrix models, I, preprint math.AG/0101147 at http://xxx.lanl.gov.
Sagan, B., The symmetric group. Representations, combinatorial algorithms, and symmetric functions, Springer-Verlag, New York, 1991.
Shao, Q., and Su, Z., The Berry-Esseen bound for character ratios, preprint (2004).
Sniady, P., Asymptotics of characters of symmetric groups, Gaussian fluctuations of Young diagrams and genus expansion, preprint math.CO/0411647 at xxx.lanl.gov.
Sniady, P., Gaussian fluctuations of characters of symmetric groups and of Young diagrams, preprint math.CO/0501112 at xxx.lanl.gov.
Stein, C., Approximate computation of expectations, Institute of Mathematical Statistics Lecture Notes, Volume 7, 1986.