THE MAHONIAN PROBABILITY DISTRIBUTION ON WORDS IS ASYMPTOTICALLY NORMAL

RODNEY CANFIELD, SVANTE JANSON, AND DORON ZEILBERGER

Abstract. We study XXX

[ Abstract!  Correct date!  No showkeys!  ]  XXX

1. Introduction

S:intro

The most important discrete probability distribution, by far, is the Binomial distribution, B(n, p) for which we know everything explicitly, ℙ(X = i) (\binom{n}{i}p^{i}(1 − p)^{n−i}), the probability generating function ((pt + (1 − p))^{n}), the moment generating function ((pe^{t} + 1 − p)^{n}), etc. etc. Most importantly, it is asymptotically normal, which means that the normalized random variable

Z_{n} = \frac{X_{n} − np}{\sqrt{np(1 − p)}}

tends to the standard Normal distribution N(0, 1), as n → ∞.

Another important discrete distribution function is the Mahonian distribution, defined on the set of permutations on n objects, and describing, inter-alia, the random variable “number of inversions”. (Recall that an inversion in a permutation π_{1}, …, π_{n} is a pair 1 ≤ i < j ≤ n such that π_{i} > π_{j}). Let us call this random variable M_{n}. The probability generating function, due to Netto, is given explicitly by:

F_{n}(q) = \frac{1}{n!} ∏_{i=1}^{n} \frac{1 − q^{i}}{1 − q} .  (1.1) netto

The formula (1.1) has a simple probabilistic interpretation (see Feller’s account in [3, Section X.6]): If Y_{j} is the number of i with 1 ≤ i < j and π_{i} > π_{j}, then

M_{n} = Y_{1} + ⋯ + Y_{n},  (1.2) nettoy

and Y_{1}, …, Y_{n} are independent random variables and Y_{j} is uniformly distributed on {0, …, j − 1}, as is easily seen by constructing π by inserting 1, …, n in this order at random positions; thus Y_{j} has probability generating function (1 − q^{j})/(j(1 − q)). It follows from (1.1) or (1.2) by simple calculations that the Mahonian distribution has mean and variance

Date: July 4, 2009 (typeset July 4, 2009 9.24).

Accompanied by Maple package MahonianStat available from http://www.math.rutgers.edu/∼zeilberg/mamarim/mamarimhtml/mahon.html.  The work of D. Zeilberger was supported in part by the United States of America National Science Foundation.

𝔼 M_{n} = \frac{n(n − 1)}{4},  (1.3) em
Var M_{n} = \frac{n(n − 1)(2n + 5)}{72} = \frac{2n^{3} + 3n^{2} − 5n}{72}.  (1.4) varm

Even though there is no explicit expression for the coefficients themselves (i.e. for the exact probabilitity that a permutation of n objects would have a certain number of inversions), it is a classical result (see [3, Section X.6]), that follows from an extended form of the Central Limit Theorem, that the normalized version

\frac{M_{n} − n(n − 1)/4}{\sqrt{(2n^{3} + 3n^{2} − 5n)/72}} ,

tends to N(0, 1), as n → ∞. So this sequence of probability distributions, too, is asymptotically normal.

But what about words, also known as multi-set permutations?. Permutations on n objects can be viewed as words in the alphabet {1, 2, …, n}, where each letter shows up exactly once. But what if we allow repetitions? I.e., we consider all words with a_{1} occurrences of 1, a_{2} occurrences of 2, …, a_{m} occurrences of m. (We assume throughout that m ≥ 2 and each a_{j} ≥ 1.) We all know that the number of such words is the multinomial coefficient

\binom{a_{1} + ⋯ + a_{m}}{a_{1}, …, a_{m}}

and many of us also know that the number of such words with exactly k inversions is the coefficient of q^{k} in the q-analog of the multinomial coefficient

\binom{a_{1} + ⋯ + a_{m}}{a_{1}, …, a_{m}}_{q} := \frac{[a_{1} + ⋯ + a_{m}]!}{[a_{1}]! ⋯ [a_{m}]!} ,  (1.5) qmulti

where [n]! := [1][2] ⋯ [n], and [n] := (1 − q^{n})/(1 − q). Assuming that all words are equally likely (the uniform distribution), the probability generating function is

F_{a_{1},...,a_{m}}(q) := \frac{(∏_{i=1}^{m} a_{i}!) · ∏_{i=1}^{a_{1}+···+a_{m}}(1 − q^{i})}{(a_{1} + ⋯ + a_{m})! ∏_{j=1}^{m} ∏_{i=1}^{a_{j}}(1 − q^{i})} = \frac{F_{a_{1}+···+a_{m}}(q)}{F_{a_{1}}(q) ⋯ F_{a_{m}}(q)}.

(1.6) F

Indeed, this can be seen as follows. Let M_{a_{1},...,a_{m}} denote the number of inversions in a random word. If we distinguish the a_{i} occurrences of i by adding different fractional parts, in random order, the number of inversions will increase by Z_{i}, say, with the same distribution as M_{a_{i}}; further M_{a_{1},...,a_{m}} and Z_{1}, …, Z_{m} are independent. On the other hand, M_{a_{1},...,a_{m}}+Z_{1}+⋯+Z_{m} has the same distribution as M_{a_{1}+···+a_{m}}. Hence,

F_{a_{1},...,a_{m}}(q)F_{a_{1}}(q) ⋯ F_{a_{m}}(q) = F_{a_{1}+···+a_{m}}(q),  (1.7) FF

which is (1.6).

By (1.6), we further have the factorization

F_{a_{1},...,a_{m}}(q) = ∏_{j=2}^{m} F_{A_{j−1},a_{j}}(q),  (1.8) F2

where A_{j} := a_{1} + ⋯ + a_{j}, which reduces the general case to the two-letter case.

Note that (1.6) shows that the distribution of M_{a_{1},...,a_{m}} is invariant if we permute a_{1}, …, a_{m}; a symmetry which is not obvious from the definition.

Rpart Remark 1.1. The two-letter case is particularly interesting, since the unnormalized generating function

\binom{a + b}{a}F_{a,b}(q) = \frac{(1 − q^{a+b})(1 − q^{a+b−1}) ⋯ (1 − q^{a+1})}{(1 − q^{b})(1 − q^{b−1}) ⋯ (1 − q^{1})} = \frac{[a + b]!}{[a]! [b]!} ,

(the q-binomial coefficient in (1.5)) is the same as the generating function for the set of integer-partitions with largest part ≤ a and ≤ b parts, in other words the set of integer-partitions whose Ferrers diagram lies inside an a by b rectangle, where the random variable is the “number of dots” (i.e. the integer being partitioned). In other words, the number of such partitions of an integer n equal the number of words of a 1’s and b 2’s with n inversions.

It is easy to see that the mean of M_{a_{1},...,a_{m}} is

μ(a_{1}, …, a_{m}) := 𝔼 M_{a_{1},...,a_{m}} = e_{2}(a_{1}, …, a_{m})/2

(here e_{k}(a_{1}, …, a_{m}) is the degree k elementary symmetric function), so considering the shifted random variable M_{a_{1},...,a_{m}} − μ(a_{1}, …, a_{m}), “number of inversions minus the mean”, we get that the probability generating function is

G_{a_{1},...,a_{m}}(q) := q^{−μ(a_{1},...,a_{m})}F_{a_{1},...,a_{m}}(q) = \frac{F_{a_{1},...,a_{m}}(q)}{q^{e_{2}(a_{1},...,a_{k})/2}}  (1.9) G

By computing (q(qG)′)′ and plugging-in q = 1, or from (1.7) and (1.3)–(1.4), it is easy to see that the variance σ^{2} := Var M_{a_{1},...,a_{m}} is

σ^{2} = \frac{(e_{1} + 1)e_{2} − e_{3}}{12} .  (1.10) sigma

(By σ we mean σ(a_{1}, …, a_{m}) and we omit the arguments (a_{1}, …, a_{m}) from the e_{i}’s.)

Let N := e_{1} = a_{1} + ⋯ + a_{m}, the length of the random word, and let a^{∗} := max_{j} a_{j} and N_{∗} := N − a^{∗}.

One main result of the present article is: T1 Theorem 1.2. Consider the random variable, M_{a_{1},...,a_{m}}, “number of inver-

sions”, on the (uniform) sample space of words with a_{1} 1’s, a_{2} 2’s, …, a_{m} m’s. For any sequence of sequences (a_{1}, …, a_{m}) = (a_{1}^{(ν)}, …, a_{m^{(ν)}}^{(ν)}) such that N_{∗} := N − a^{∗} → ∞, the sequence of normalized random variables

X_{a_{1},...,a_{m}} = \frac{M_{a_{1},...,a_{m}} − μ(a_{1}, …, a_{m})}{σ(a_{1}, …, a_{m})} ,

tends to the standard normal distribution N (0, 1), as ν → ∞.

Theorem 1.2 includes both the case when m ≥ 2 is fixed, and the case when m → ∞. If m is fixed and a_{1} ≥ a_{2} ≥ ⋯ ≥ a_{m}, as may be assumed by symmetry, then the condition N_{∗} → ∞ is equivalent to a_{2} → ∞. In the case m → ∞, the assumption N_{∗} → ∞ is redundant, because N_{∗} ≥ m − 1. Remark 1.3. The condition N_{∗} → ∞ is also necessary for asymptotic normality, see Section 6.

We give a short proof of this result using characteristic functions in Section 3. We give first in Section 2 another proof (at least of a special case) that is computer-assisted, using the Maple package MahonianStat available from the webpage of this article:

http://www.math.rutgers.edu/∼zeilberg/mamarim/mamarimhtml/mahon.html,

where one can also find sample input and output. This first proof uses the method of moments.

We conjecture that Theorem 1.2 can be refined to a local limit theorem as follows:

Conjlocal Conjecture 1.4. Uniformly for all a_{1}, …, a_{m} and all integers k,

ℙ(M_{a_{1},...,a_{m}} = k) = \frac{1}{\sqrt{2π}σ} (e^{−(k−μ)^{2}/(2σ^{2})} + O(\frac{1}{N_{∗}} )).  (1.11) local

We have not been able to prove this conjecture in full generality, but we prove it under additional hypotheses on a_{1}, …, a_{m} in Section 4.

2. A computer-inspired proof

Spf1

We assume for simplicity that m is fixed, and that (a_{1}, …, a_{m}) = (ta_{1}^{0}, …, ta_{m}^{0}) for some fixed a_{1}^{0}, …, a_{m}^{0} and t → ∞.

We discover and prove the leading term in the asymptotic expansion, in t, for an arbitrary 2r-th moment, for the normalized random variable X_{a_{1},...,a_{m}} = (M_{a_{1},...,a_{m}} − μ)/σ, and show that it converges to the moment μ_{2r} = (2r)!/(2^{r}r!) of N (0, 1), for every r.

For the sake of exposition, we will only treat in detail the two-letter case, where we can find explicit expressions for the asymptotics of the 2r-th moment, for symbolic a_{1}, a_{2}, t and r to any desired (specific) order s (i.e. the leading coefficient t^{3r} as well as the terms involving t^{3r−1}, …, t^{3r−s}). A modified argument works for the general case, but we can only find the leading term, i.e. that

α_{2r} := 𝔼(X_{a_{1},...,a_{m}})^{2r} = \frac{(2r)!}{2^{r}r!}t^{3r} + O(t^{3r−1}) .

Of course the odd moments are all zero, since the distribution of M_{a_{1},...,a_{m}} is symmetric about μ.

The mean in the two-letter case is simply ab/2, so the probability generating function for M_{a,b} − μ is

G_{a,b}(q) = \frac{F_{a,b}(q)}{q^{ab/2}(a + b)!/(a!b!)} = \frac{a!b!(1 − q^{a+b})(1 − q^{a+b−1}) ⋯ (1 − q^{a+1})}{q^{ab/2}(a + b)!(1 − q^{b})(1 − q^{b−1}) ⋯ (1 − q^{1})} ,

Taking ratios, we have:

\frac{G_{a,b}(q)}{G_{a−1,b}(q)} = \frac{a(1 − q^{a+b})}{q^{b/2}(a + b)(1 − q^{a})} .  (2.1) ratio

Recall that the binomial moments A_{r} := 𝔼[\binom{X}{r}] are the Taylor coefficients of the probability generating function (in our case G_{a,b}(q)) around q = 1. Writing q = 1 + z, we have

G_{a,b}(1 + z) = ∑_{r=0}^{∞} A_{r}(a, b)z^{r}

Note that A_{0}(a, b) = 1 and A_{1}(a, b) = 0. Let us call the expression on the right side of (2.1), with q replaced by 1 + z, P (a, b, z):

P (a, b, z) := \frac{a(1 − (1 + z)^{a+b})}{(1 + z)^{b/2}(a + b)(1 − (1 + z)^{a})}

Maple can easily expand P (a, b, z) to any desired power of z, It starts out with

P (a, b, z) = 1 + \frac{1}{24} (2 a + b) bz^{2} − \frac{1}{24} (2 a + b) bz^{3}

− \frac{1}{5760} (8 a^{3} − 8 a^{2}b − 12 ab^{2} − 3 b^{3} − 440 a − 220 b) bz^{4} + …

note that the coefficients of all the powers of z are polynomials in (a, b). So let us write

P (a, b, z) = ∑_{i=0}^{∞} p_{i}(a, b)z^{i} ,

where p_{i}(a, b) are certain polynomials that Maple can compute for any i, no matter how big.

Looking at the recurrence

G_{a,b}(1 + z) = P (a, b, z)G_{a−1,b}(1 + z) ,

and comparing coefficients of z^{r} on both sides, we get

A_{r}(a, b) − A_{r}(a − 1, b) = ∑_{s=1}^{r} A_{r−s}(a − 1, b)p_{s}(a, b) .  (2.2) recurrence

Assuming that we already know the polynomials A_{r−1}(a, b), A_{r−2}(a, b), …, A_{0}(a, b), the left side is a certain specific polynomial in a and b, that Maple can easily compute, and then A_{r}(a, b) is simply the indefinite sum of that polynomial, that Maple can do just as easily. So (2.2) enables us to get explicit expressions for the binomial moments A_{r}(a, b) for any (numeric) r.

But what about the general (symbolic) r? It is too much to hope for the full expression, but we can easily conjecture as many leading terms as we wish. We first conjecture, and then immediately prove by induction, that for r ≥ 1

A_{2r}(a, b) = \frac{1}{r!} (\frac{ab(a + b)}{24})^{r} + lower order terms
A_{2r+1}(a, b) = \frac{−1}{(r − 1)!} (\frac{ab(a + b)}{24})^{r} + lower order terms ,

where we can conjecture (by fitting polynomials in (a, b) to the data obtained from the numerical r’s) any (finite, specific) number of terms.

Once we have asymptotics, to any desired order, for the binomial moments, we can easily compute the moments μ_{r}(a, b) of M_{a,b} − μ themselves, for any desired specific r and asymptotically, to any desired order. We do that by using the expressions of the powers as linear combination of fallingfactorials (or equivalently binomials) in terms of Stirling numbers of the second kind, S(n, k). Note that for the asymptotic expressions to any desired order, we can still do it symbolically, since for any specific m, S(n, n − m) is a polynomial in n (that Maple can easily compute, symbolically, as a polynomial in n). In particular, the variance is:

σ^{2} = μ_{2}(a, b) = \frac{ab(a + b + 1)}{12} ,

in accordance with (1.10). In general we have μ_{2r+1}(a, b) = 0, of course, and the six leading terms of μ_{2r}(at, bt) can be found in the webpage of this article. From this, Maple finds that α_{2r}(at, bt) := μ_{2r}(at, bt)/μ_{2}(at, bt)^{r} are given asymptotically (for fixed a, b and t → ∞) by:

α_{2r}(at, bt) = \frac{(2r)!}{2^{r}r!} · (1 − \frac{r(r − 1) (b^{2} + ab + a^{2})}{5ab (a + b)} · \frac{1}{t}) + O(t^{−2}) .

In particular, as t → ∞, they converge to the famous moments of N (0, 1). QED.

2.1. The general case. To merely prove asymptotic normality, one does not need a computer, since we only need the leading terms. The above proof can be easily adapted to the general case (a_{1}, …, a_{m}) = (ta_{1}^{0}, …, ta_{m}^{0}). One simply uses induction on m, the number of different letters.

2.2. The Maple package MahonianStat. The Maple package MahonianStat, accompanying this article, has lots of features, that the readers can explore at their leisure. Once downloaded into a directory, one goes into a maple session, and types read MahonianStat. To get a list of the main procedures, type: ezra();. To get help with a specific procedure, type ezra(ProcedureName);. Let us just mention some of the more important procedures.

  AsyAlphaW2tS(r,a,b,t,s): inputs symbols r,a,b,t and a positive in-

teger s, and outputs the asymptotic expansion, to order s, for α_{2r} (=μ_{2r}/μ_{2}^{r})

ithMomWktE(r,e,t) the r-th moment about the mean of the number of inversions of a_{1}t 1’s, …, a_{m}t n’s in terms of the elementary symmetric functions, in a_{1}, …, a_{m}. Here r is a specific (numeric) positive integer, but e and t are symbolic.

AppxWk(L,x): Using the asymptotics implied by the asymptotic normality of the (normalized) random variable under consideration, finds an approximate value for the number of words with L[1] 1’s, L[2] 2’s, …, L[n] n’s with exactly x inversions. For example, try: AppxWk([100,100,100],15000);

For the two-lettered case, one can get better approximations, by procedure BetterAppxW2, that uses improved limit-distributions, using more terms in the probability density function.

The webpage of this article has some sample input and output.

3. A general proof of Theorem 1.2

Spf2

We have an exact formula (1.10) for the variance σ^{2} of M_{a_{1},...,a_{m}}. We first show that σ 2 is always of the order Θ(N^{2}N_{∗}).

Lsigma Lemma 3.1. For any a_{1}, …, a_{m},

\frac{N^{2}N_{∗}}{36} ≤ σ^{2} ≤ \frac{(N + 1)NN_{∗}}{12} ≤ \frac{N^{2}N_{∗}}{6} .

Proof. For the upper bounds we assume, by symmetry, that a_{1} ≥ ⋯ ≥ a_{m}. Then a^{∗} = a_{1} and

e_{2} = a_{1} ∑_{j=2}^{m} a_{j} + a_{2} ∑_{j=3}^{m} a_{j} + ⋯ ≤ N ∑_{j=2}^{m} a_{j} = NN_{∗}.

Since e_{1} = N, (1.10) yields the upper bounds.

For the lower bound, we first observe that 2e_{2}e_{1} − 6e_{3} ≥ 0 (since this difference can be written as a sum of certain a_{j}a_{k}a_{l}). Hence e_{3} ≤ e_{1}e_{2}/3 and (1.10) yields

12σ^{2} ≥ e_{1}e_{2} − e_{3} ≥ \frac{2}{3}e_{1}e_{2}.

Further,

2e_{2} = ∑_{j=1}^{m} a_{j}(N − a_{j}) ≥ ∑_{j=1}^{m} a_{j}(N − a^{∗}) = NN_{∗},

and the lower bound follows. □

Proof of Theorem 1.2. From (1.6) follows the identity

F_{n_{1},n_{2}}(e^{iθ}) = ∏_{j=1}^{n_{2}} \frac{(e^{i(n_{1}+j)θ} − 1)/(i(n_{1} + j)θ)}{(e^{ijθ} − 1)/(ijθ)}.  (3.1) f2q

By Taylor’s series

log \frac{e^{z} − 1}{z} = z/2 + z^{2}/24 + O(z^{4}), |z| ≤ 1,

and we substitute this expansion into the identity (3.1) to conclude:

F_{n_{1},n_{2}}(e^{iθ}) = exp (in_{1}n_{2}θ/2 − n_{1}n_{2}(n_{1} + n_{2} + 1)θ^{2}/24 + O(n_{2}n_{1}^{4}θ^{4})) ,_{(3.2) r3}

uniformly for n_{1} ≥ n_{2} ≥ 1 and |θ| ≤ (n_{1} + n_{2})^{−1}.

We use the factorization (1.8). By symmetry, we may assume a_{1} ≥ a_{2} ≥ ⋯ ≥ a_{m}, and then A_{j−1} ≥ a_{j−1} ≥ a_{j} for each j. Thus (3.2) yields, uniformly for q = e^{iθ} with |θ| ≤ N^{−1},

F_{a_{1},...,a_{m}}(q) = ∏_{j=2}^{m} F_{A_{j−1},a_{j}}(q)

= exp (∑_{j=2}^{m}(iA_{j−1}a_{j}θ/2 − A_{j−1}a_{j}(A_{j} + 1)θ^{2}/24 + O(a_{j}A_{j−1}^{4}θ^{4}))) .

Here, the sums of the coefficients of θ and θ^{2} are easily evaluated, but we do not have to do that since they have to equal iμ and −σ^{2}/2, respectively. Further,

∑_{j=2}^{m} A_{j−1}^{4}a_{j} ≤ N^{4} ∑_{j=2}^{m} a_{j} = N^{4}N_{∗}.  (3.3) pa1

Consequently, if |θ| ≤ N^{−1},

F_{a_{1},...,a_{m}}(e^{iθ}) = exp(iμθ − σ^{2}θ^{2}/2 + O(N^{4}N_{∗}θ^{4}))  (3.4) pa2

and, by (1.9),

G_{a_{1},...,a_{m}}(e^{iθ}) = exp(−σ^{2}θ^{2}/2 + O(N^{4}N_{∗}θ^{4})).  (3.5) pag

Let θ = t/σ. For any fixed t, by Lemma 3.1,

|Nt/σ| = O(N_{∗}^{−1/2}) = o(1),

so |θ| ≤ N^{−1} if ν is large enough. Hence, by (3.3)–(3.5) and Lemma 3.1,

G_{a_{1},...,a_{m}}(e^{it/σ}) == exp (−\frac{t^{2}}{2} + O(\frac{N^{4}N_{∗}t^{4}}{N^{4}N_{∗}^{2}} )) = exp(−t^{2}/2 + o(1)),

and Theorem 1.2 follows by the continuity theorem [4, Theorem XV.3.2]. □

4. The local limit theorem

Slocal

“If one can prove a central limit theorem for a sequence a_{n}(k) of numbers arising in enumeration, then one has a qualitative feel for their behavior. A local limit theorem is better because it provides asymptotic information about a_{n}(k) …,” [2]. In this section we prove that the relation (1.11) holds uniformly over certain very general, albeit not unrestricted, sets of tuples a = (a_{1}, …, a_{m}). The exact statement is given below in Theorem 4.5.

As explained in Bender [2], there are two standard conditions for passage from a central to a local limit theorem: (1) if the sequence in question is unimodal, then one has a local limit theorem for n in the set {|n − μ| ≥ ϵσ}, ϵ > 0; (2) if the sequence in question is log-concave, then one has a local limit theorem for all n. Our sequence, the coefficients of the q-mutinomial, is in fact unimodal, as first shown by Schur [6] using invariant theory, and later by O’Hara [5] using combinatorics. Unfortunately, the ensuing local limit theorem fails to cover the most interesting coefficients, the largest ones, near the mean μ. However, our polynomials are manifestly not log-concave as is seen by inspecting the first three coefficients (assuming n_{1}, n_{2} ≥ 2)

\binom{n_{1} + n_{2}}{n_{1}}_{q} = 1 + q + 2q^{2} + · · · .

The question arises might the coefficients be log-concave near the mean, and here is a small table of empirical values: (c[j] = [q^{j}]\binom{2n}{n}_{q})

\begin{matrix}n & (c[n^{2}/2 − 1])^{2} − c[n^{2}/2] × c[n^{2}/2 − 2] \\ 2 & -1 \\ 4 & -7 \\ 6 & -165 \\ 8 & -1529 \\ 10 & 44160 \\ 12 & 7715737 \\ 14 & 905559058 \\ 16 & 101507214165 \\ 18 & 11955335854893 \\ 20 & 1501943866215277 \end{matrix}

Based on this scant evidence, we speculate that some sort of log-concavity theorem is true, but that its proper statement is complicated by describing the appropriate range of a and j. Thus, we use neither of the two standard methods mentioned above for proving our local limit theorem. (Later, we shall see that our theorem has implications for log-concavity.) Instead, we use another standard method, direct integration (Fourier inversion) of the characteristic function, or equivalently of the probability generating function F (q) for q = e^{iθ} on the unit circle. This method uses the estimates for small θ derived in Section 3 together with estimates of |F (e^{iθ})| for larger θ. We begin with one such estimate for rather small θ.

LG1 Lemma 4.1. There exists a constant τ > 0 such that for any a_{1}, …, a_{m} and |θ| ≤ τ/N,

|F_{a_{1},...,a_{m}}(e^{iθ})| = |G_{a_{1},...,a_{m}}(e^{iθ})| ≤ e^{−σ^{2}θ^{2}/4}.

Proof. Suppose that 0 < |θ| ≤ τ/N. Then, using Lemma 3.1,

\frac{N^{4}N_{∗}θ^{4}}{σ^{2}θ^{2}} ≤ \frac{N^{2}N_{∗}τ^{2}}{σ^{2}} ≤ 36τ^{2},

so if τ is chosen small enough, the error term O(N^{4}N_{∗}θ^{4}) in (3.4) and (3.5) is ≤ σ^{2}θ^{2}/4, and thus the result follows from (3.5). □

We let in the sequel τ denote this constant. We may assume 0 < τ ≤ 1. Lemma 4.2. Uniformly, for all a_{1}, …, a_{m} and all integers k,

Lmagnus

ℙ(M_{a_{1},...,a_{m}} = k) = \frac{1}{\sqrt{2π}σ} e^{−(k−μ)^{2}/(2σ^{2})}+∫_{τ/N}^{π} |F_{a_{1},...,a_{m}}(e^{iθ})| dθ+O(\frac{1}{σN_{∗}} ).

Proof. For any integer k,

ℙ(M_{a_{1},...,a_{m}} = k) − \frac{1}{\sqrt{2π}σ} e^{−(k−μ)^{2}/(2σ^{2})}

= \frac{1}{2π} ∫_{−π}^{π} F_{a_{1},...,a_{m}}(e^{iθ})e^{−ikθ} dθ − \frac{1}{2π} ∫_{−∞}^{∞} e^{−σ^{2}θ^{2}/2}e^{−i(k−μ)θ} dθ

= \frac{1}{2π} ∫_{|θ|≤τ/N}(G_{a_{1},...,a_{m}}(e^{iθ}) − e^{σ^{2}θ^{2}/2})e^{−i(k−μ)θ} dθ

+ \frac{1}{2π} ∫_{τ/N≤|θ|≤π} F_{a_{1},...,a_{m}}(e^{iθ})e^{−ikθ} dθ

− \frac{1}{2π} ∫_{|θ|≥τ/N} e^{−σ^{2}θ^{2}/2}e^{−i(k−μ)θ} dθ

=: I_{1} + I_{2} + I_{3}.

For |θ| ≤ τ/N, |G_{a_{1},...,a_{m}}(e^{iθ})| ≤ e^{−σ^{2}θ^{2}/4} by Lemma 4.1, so (3.5) and the mean-value theorem applied to z ↦ e^{z} yield

\begin{aligned}|G_{a_{1},...,a_{m}}(e^{iθ}) − e^{−σ^{2}θ^{2}/2}| & ≤ O(N^{4}N_{∗}θ^{4}) max(|G_{a_{1},...,a_{m}}(e^{iθ})|, e^{−σ^{2}θ^{2}/2}) \\ & = O(N^{4}N_{∗}θ^{4}e^{−σ^{2}θ^{2}/4}). \end{aligned}

Integrating, we find, using Lemma 4.1,

\begin{aligned}|I_{1}| & ≤ ∫_{|θ|≤τ/N} |G_{a_{1},...,a_{m}}(e^{iθ}) − e^{−σ^{2}θ^{2}/2}| dθ \\ & ≤ O(N^{4}N_{∗}) ∫_{−∞}^{∞} θ^{4}e^{−σ^{2}θ^{2}/4} dθ = O(N^{4}N_{∗}σ^{−5}) = O(\frac{1}{σN_{∗}} ). \end{aligned}

Further, again using Lemma 4.1,

|I_{3}| ≤ ∫_{τ/N}^{∞} e^{−σ^{2}θ^{2}/2} dθ ≤ 3σ^{−1}e^{−(στ/N)^{2}/2} ≤ \frac{6}{σ(στ/N)^{2}} = O(\frac{1}{σN_{∗}} ).

Finally, |I_{2}| ≤ ∫_{τ/N}^{π} |F_{a_{1},...,a_{m}}(e^{iθ})| dθ. □

In order to verify Conjecture 1.4, it thus suffices to show that the integral ∫_{τ/N}^{π} |F_{a_{1},...,a_{m}}(e^{iθ})| dθ in Lemma 4.2 is O(\frac{1}{σN_{∗}} ). Remark 4.3. For example, an estimate

F_{a_{1},...,a_{m}}(e^{iθ}) = O(\frac{1}{σ^{3}θ^{3}} ),  0 < θ ≤ π,  (4.1) conj3

is sufficient for (1.11). We conjecture that this estimate (4.1) holds when N_{∗} ≥ 6, say. Note that it does not hold for very small N_{∗}: taking θ = π we have, for even n_{1}, F_{n_{1},1}(−1) = 1/(n_{1} + 1) = 1/N, and the same holds for F_{n_{1},2}(−1).

Note further that even the weaker estimate

F_{a_{1},...,a_{m}}(e^{iθ}) = O(\frac{1}{σ^{2}θ^{2}} ),  0 < θ ≤ π,  (4.2) conj2

would be enough to prove (1.11) with the weaker error term O(N_{∗}^{−1/2}).

We obtain a partial proof of Conjecture 1.4 using the following lemma. LC1 Lemma 4.4. For a given τ ∈ (0, 1] there exists c = c(τ) > 0 such that

|F_{n_{1},n_{2}}(e^{iθ})| ≤ e^{−cn_{2}}  (4.3) r2

for n_{1} ≥ n_{2} ≥ 1 and τ/(n_{1} + n_{2}) ≤ |θ| ≤ π.

More generally, for any a_{1}, …, a_{m} and τ/N ≤ |θ| ≤ π,

|F_{a_{1},...,a_{m}}(e^{iθ})| ≤ e^{−cN_{∗}}.  (4.4) r2m

Proof. We prove first (4.3). For positive integer n define

f_{n}(y, q) = ∏_{j=0}^{n}(1 − yq^{j})^{−1}.

For 0 ≤ R < 1, we have (e.g. by Taylor expansions) e^{2R} ≤ \frac{1+R}{1−R}, and thus

e^{4R} ≤ \frac{(1+R)^{2}}{(1−R)^{2}} = 1 + \frac{4R}{(1−R)^{2}} . Hence, by convexity, for any real ζ,

e^{2R(1−cos ζ)} ≤ 1 + \frac{2R(1 − cos ζ)}{(1 − R)^{2}} = \frac{1 + R^{2} − 2R cos ζ}{(1 − R)^{2}} = \frac{|1 − Re^{iζ}|^{2}}{(1 − R)^{2}} ,

and thus

|(1 − Re^{iζ})^{−1}| ≤ (1 − R)^{−1} exp (R(1 − cos ζ)) .

Consequently, by a simple trigonometric identity, for any real ϕ and θ,

|f_{n_{1}}(Re^{iϕ}, e^{iθ})| ≤ (1 − R)^{−n_{1}−1}

× exp (−R(n_{1} + 1 − cos(ϕ + \frac{n_{1}}{2} θ)\frac{sin(n_{1} + 1)θ/2}{sin θ/2}))

≤ (1 − R)^{−n_{1}−1} × exp (R(−n_{1} − 1 + \frac{sin(n_{1} + 1)θ/2}{sin θ/2})) .

The function g(θ) = g_{n}(θ) := \frac{sin n(θ/2)}{sin(θ/2)}, where n ≥ 1, is an even function of θ; is decreasing for 0 ≤ θ ≤ π/n, as can be verified by calculating g′; and satisfies |g(θ)| ≤ g(π/n) for π/n ≤ |θ| ≤ π. Further, for n ≥ 2 and 0 ≤ |θ| ≤ π/n,

g_{n}(θ) = 2\frac{sin(nθ/4)}{sin(θ/2)} cos(nθ/4) = 2g_{n/2}(θ) cos(nθ/4) ≤ n cos(nθ/4)

≤ n(1 − \frac{n^{2}θ^{2}}{40} ).

Let θ_{0} = τ(n_{1} + n_{2})^{−1} < π/(n_{1} + 1). For θ_{0} ≤ |θ| ≤ π we thus have

|g_{n_{1}+1}(θ)| ≤ g_{n_{1}+1}(θ_{0}) ≤ n_{1} + 1 − \frac{n_{1}^{3}θ_{0}^{2}}{40} ;

whence, for 0 ≤ R < 1, the estimate above yields

|f_{n_{1}}(Re^{iϕ}, e^{iθ})| ≤ (1 − R)^{−n_{1}−1} exp (−Rn_{1}^{3}θ_{0}^{2}/40) .  (4.5) tho

Combinatorially we know that [y^{ℓ}q^{n}]f_{n_{1}}(y, q) is the number of partitions of n having at most ℓ parts no one of which exceeds n_{1}. As said in Remark 1.1, this equals [q^{n}]\binom{n_{1}+ℓ}{n_{1}}F_{n_{1}+ℓ}(q). Hence, using Cauchy’s integral formula, for any R > 0,

\binom{n_{1} + n_{2}}{n_{1}}F_{n_{1},n_{2}}(q) = [y^{n_{2}}]f_{n_{1}}(y, q) = \frac{1}{2πi} ∫_{|y|=R} f_{n_{1}}(y, q)\frac{dy}{y^{n_{2}+1}} .

Consequently, (4.5) implies that for θ_{0} ≤ |θ| ≤ π and 0 < R < 1,

\binom{n_{1} + n_{2}}{n_{1}}|F_{n_{1},n_{2}}(q)| ≤ (1 − R)^{−n_{1}−1}R^{−n_{2}} exp (−Rn_{1}^{3}θ_{0}^{2}/40) .

Now choose R = ρ := n_{2}/(n_{1} + n_{2}) ≤ 1/2. By Stirling’s formula,

\binom{n_{1} + n_{2}}{n_{1}} = Ω(n_{2}^{−1/2}) (1 − ρ)^{−n_{1}−1} ρ^{−n_{2}}

and thus, for θ_{0} ≤ |θ| ≤ π,

|F_{n_{1},n_{2}}(q)| ≤ O(n_{2}^{1/2}) exp (−ρn_{1}^{3}θ_{0}^{2}/40) = O(n_{2}^{1/2}) exp (−Ω(n_{2})) .

This shows (4.3) for n_{2} large enough, say n_{2} ≥ n_{0}. The case n_{2} ≤ n_{0} can be

XXX XXX I hope this case is simple, and perhaps can be dismissed without giving details. If not, I think that we do not really need it.

To prove (4.4), we assume as we may that a_{1} ≥ ⋯ ≥ a_{m} and use the factorization (1.8). Let J be the first index such that a_{2} + ⋯ + a_{J} ≥ N_{∗}/2. For j ≥ J, then A_{j−1} + a_{j} = A_{j} ≥ A_{J} ≥ a_{1} + N_{∗}/2 ≥ N/2, and thus A_{k}|θ| ≥ N|θ|/2 ≥ τ/2; hence (4.3) yields

|F_{A_{j−1},a_{j}}(e^{iθ})| ≤ e^{−c(τ/2)a_{j}}.

We thus obtain from (1.8), since each F_{n_{1},n_{2}} is a probability generating function and thus is bounded by 1 on the unit circle,

|F_{a_{1},...,a_{m}}(e^{iθ})| = ∏_{j=2}^{m} |F_{A_{j−1},a_{j}}(e^{iθ})| ≤ ∏_{j=J}^{m} e^{−c(τ/2)a_{j}} ≤ e^{−c(τ/2)N_{∗}/2},

because ∑_{j=J}^{m} a_{j} ≥ N_{∗}/2. This proves (4.4) (redefining c(τ)). □

Tlocal Theorem 4.5. There exists a positive constant c such that for every C, the following is true. Uniformly for all a_{1}, …, a_{m} such that a^{∗} ≤ Ce^{cN_{∗}} and all integers k,

ℙ(M_{a_{1},...,a_{m}} = k) = \frac{1}{\sqrt{2π}σ} (e^{−(k−μ)^{2}/(2σ^{2})} + O(\frac{1}{N_{∗}} )).  (4.6) localxxx

Proof. Let c_{1} = c(τ) be the constant in Lemma 4.4. Then, Lemmas 4.2 and 4.4 yield

ℙ(M_{a_{1},...,a_{m}} = k) = \frac{1}{\sqrt{2π}σ} (e^{−(k−μ)^{2}/(2σ^{2})} + O(\frac{1}{N_{∗}} + σe^{−c_{1}N_{∗}})).

For any fixed c < c_{1} we have, using Lemma 3.1, σN_{∗}e^{−c_{1}N_{∗}} = O(Ne^{−cN_{∗}}) and thus

ℙ(M_{a_{1},...,a_{m}} = k) = \frac{1}{\sqrt{2π}σ} (e^{−(k−μ)^{2}/(2σ^{2})} + O(\frac{1 + Ne^{−cN_{∗}}}{N_{∗}} )).

The result follows, since Ne^{−cN_{∗}} = a^{∗}e^{−cN_{∗}}+N_{∗}e^{−cN_{∗}} = a^{∗}e^{−cN_{∗}}+O(1). □

[Old stuff to be edited:]  XXX

The combinatorics of the Macmahon q statistic appear not to have been greatly used, but in fact play an essential, easily overlooked, role. It seems that the Taylor estimate (3.2) is the key for a central limit theorem. As in Bender [2], some kind of smoothness condition is needed to proceed to a local limit theorem (1). Lemma 1, the large θ bound, imposes the required smoothness. The proof of Lemma 1 is made possible by the following combinatorial property:

[q^{n}]\binom{n_{1} + n_{2}}{n_{1}}_{q} = ∑_{ℓ=1}^{n_{2}}[y^{ℓ}] ∏_{j=1}^{n_{1}}(1 − yq^{j})^{−1}.

Thus, our Theorem 4.5 may be the h(x) = (1−x)^{−1} case of a more general theorem about

[q^{n}] ∑_{ℓ=1}^{n_{2}}[y^{ℓ}] ∏_{j=1}^{n_{1}} h(yq^{j}).

5. Log-concavity

[Old stuff to be edited:]  XXX

Let us review the proof of Theorem 4.5 with the intention of greater accuracy. The goal is to prove log-concavity in some range. For concreteness, let a = (n, n). Then σ^{2} is of order n^{3}, and for sufficient accuracy we take the Taylor series (3) out to O(θ^{10}). This improves (5) to:

\frac{1}{2π} ∫_{small θ} F (e^{iθ})e^{−ijθ}dθ = \frac{F (1)}{σ\sqrt{2π}} (e^{−x^{2}/2} (1 + \frac{p_{4}(x)}{σ^{4}} + \frac{p_{6}(x)}{σ^{6}} + \frac{p_{8}(x)}{σ^{8}} ) + O( \frac{1}{n^{4}} )) .

Here, p_{4}(x), … are certain polynomials and x is determined by j = μ + xσ. The sizes of the terms involving the polynomials are 1, 1/n, 1/n^{2}, 1/n^{3}. The large θ contribution is negligible by comparison. One may now use the formula to calculate the difference c_{j}^{2} − c_{j_{1}}c_{j+1} to accuracy O(1/n^{4}). Taking out the obvious common factors, it is found to equal 1/σ^{2}. This gives:

TC2 Theorem 5.1 (A log-concavity result). For each constant C we have n_{0} such that for

n ≥ n_{0}

c_{j}^{2} ≥ c_{j−1}c_{j+1},

for |j − μ| ≤ Cσ. Here,

c_{j} = [q^{j}]\binom{2n}{n}_{q}.

We note that the “mysterious” numbers appearing in our earlier table are asymptotically

\frac{1}{2πσ^{4}} \binom{2n}{n}^{2}.

6. Final comments

Sfine

Suppose that N_{∗} ↛ ∞. We may, as usual, assume that a_{1} ≥ ⋯ ≥ a_{m}. By considering a subsequence (if necessary), we may assume that N_{∗} := N − a^{∗} = a_{2} + ⋯ + a_{m} is a constant; this entails that m is bounded, so by again considering a subsequence, we may assume that m and a_{2}, …, a_{m} are constant. We thus study the case when a_{1} → ∞ with fixed a_{2}, …, a_{m}.

In this case, the number of inversions between indices 2, …, m is O(1), which is asymptotically negligible. Ignoring these, we can thus consider the random word as N_{∗} letters 2, …, m inserted in a_{1} 1’s, and the number of inversions is the sum of their positions, counted from the end. It follows easily, either probabilistically or by calculating the characteristic function from (1.6), that M_{a_{1},...,a_{m}}/N, or equivalently M_{a_{1},...,a_{m}}/a_{1}, converges in distribution to the sum ∑_{j=1}^{N_{∗}} U_{j} of N_{∗} independent random variables U_{j} with the uniform distribution on [0, 1]. Equivalently, since σ^{2} ∼ n_{1}^{2}N_{∗}/12 ∼ N^{2}N_{∗}/12,

\frac{M_{a_{1},...,a_{m}} − μ(a_{1}, …, a_{m})}{σ(a_{1}, …, a_{m})} ⟶^{d} \sqrt{\frac{12}{N_{∗}}} ∑_{j=1}^{N_{∗}}(U_{j} − \frac{1}{2}),

where ⟶^{d} denotes convergence in distribution. This limit is clearly not normal for any finite N_{∗}. (However, its distribution is close to standard normal for large N_{∗}. Note that it is normalized to mean 0 and variance 1.)

References

Andrews [1] G. E. Andrews, The Theory of Partitions, Addison-Wesley, 1976. Bender [2] E. A. Bender, Central and local limit theorems applied to asymptotic

enumeration, JCT 15 (1973) 91–111.

FellerI [3] William Feller, An Introduction to Probability Theory and Its Applica-

tion, volume I, third edition, John Wiley & Sons, New York, 1968.

FellerII [4] W. Feller, An Introduction to Probability Theory and its Applications,

volume II, 2nd ed., Wiley, New York, 1971.

Ohara [5] K. M. O’Hara, Unimodality of Gaussian coefficients: a constructive

proof, Journal of Combinatorial Theory, Series A 53 (1990) 29–52.

Schur [6] I. J. Schur, see the explicit reference given on page 48 of [1].

Computer Science Department, University of Georgia, Athens, GA 30602-7404, USA

E-mail address: erc [At] cs [Dot] uga [Dot] edu

Department of Mathematics, Uppsala University, PO Box 480, SE-751 06 Uppsala, Sweden

E-mail address: svante.janson [At] math [Dot] uu [Dot] se
URL: http://www.math.uu.se/∼svante/

Mathematics Department, Rutgers University (New Brunswick), Piscataway, NJ 08854, USA

E-mail address: zeilberg [At] math [Dot] rutgers [Dot] edu