Durfee Polynomials

E. Rodney Canfield Department of Computer Science University of Georgia Athens, GA 30602, USA

                  erc@cs.uga.edu

Sylvie Corteel ^{∗} Laboratoire de Recherche en Informatique Bât 490, Université Paris-Sud 91405 Orsay, FRANCE

              Sylvie.Corteel@lri.fr

Carla D. Savage^{†} Department of Computer Science North Carolina State University Raleigh, NC 27695-8206, USA

            savage@cayley.csc.ncsu.edu

Submitted: February 12, 1998; Accepted: June 10, 1998.

AMS Subject Classification: 05A17, 05A20, 05A16, 11P81

Abstract

Let F(n) be a family of partitions of n and let F(n, d) denote the set of partitions in F(n) with Durfee square of size d. We define the Durfee polynomial of F(n) to be the polynomial P_{F,n} = ∑ |F(n, d)|y^{d}, where 0 ≤ d ≤ ⌊\sqrt{n}⌋. The work in this paper is motivated by empirical evidence which suggests that for several families F, all roots of the Durfee polynomial are real. Such a result would imply that the corresponding sequence of coefficients {|F(n, d)|} is logconcave and unimodal and that, over all partitions in F(n) for fixed n, the average size of the Durfee square, a_{F}(n), and the most likely size of the Durfee square, m_{F}(n), differ by less than 1.

∗Research supported by National Science Foundation Grant DMS9302505 †Supported in part by National Science Foundation Grants No. DMS 9302505 and DMS 9622772

In this paper, we prove results in support of the conjecture that for the family of ordinary partitions, P(n), the Durfee polynomial has all roots real. Specifically, we find an asymptotic formula for |P(n, d)|, deriving in the process a simple upper bound on the number of partitions of n with at most k parts which generalizes the upper bound of Erdös for |P(n)|. We show that as n tends to infinity, the sequence \{|P(n, d)|\}, 1 ≤ d ≤ \sqrt{n}, is asymptotically normal, unimodal, and log concave; in addition, formulas are found for a_{P}(n) and m_{P}(n) which differ asymptotically by at most 1.

Experimental evidence also suggests that for several families F(n) which satisfy a recurrence of a certain form, m_{F}(n) grows as c\sqrt{n}, for an appropriate constant c = c_{F}. We prove this under an assumption about the asymptotic form of |F(n, d)| and show how to produce, from recurrences for the |F(n, d)|, analytical expressions for the constants c_{F} which agree numerically with the observed values.

1 Introduction

A partition λ of an integer n is a sequence λ = (λ_{1}, λ_{2}, … λ_{ℓ}) of positive integers satisfying λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{ℓ} and λ_{1} + λ_{2} + ⋯ + λ_{ℓ} = n. The Ferrers diagram of λ is a two-dimensional array of dots in which row i has λ_{i} dots and rows are left justified. The Durfee square of λ is the largest square array of dots contained in its Ferrers diagram and d(λ) denotes the length of a side of this square. We let P(n) be the set of all partitions of n and let P(n, d) be the set of all partitions of n with Durfee square of size d. To simplify notation, we use the same symbol to denote a set and its size when the meaning is clear from context.

For a finite sequence of positive integers s = {a_{d}}, 0 ≤ d ≤ N, the average index of s is the ratio ∑(da_{d})/ ∑ a_{d} and a most likely index of s is an index i such that a_{i} = max{a_{d}}, i.e., a mode of s. It is well-known that if all roots of the polynomial ∑ a_{d}x^{d}, 0 ≤ d ≤ N are real (and hence negative), then {a_{d}} is strictly log-concave in d and therefore unimodal with a peak or a plateau of two points. (See [5, 17], for example). What is perhaps less well-known is that this condition on the roots guarantees that the average index and a most likely index of {a_{d}} differ by at most one [2, 7].

These properties have been studied for many combinatorial sequences [3, 19] and in particular for the sequences {f(n, k)} for fixed n, where f(n, k) is the number of partitions of n in F(n) and k is the size of a chosen parameter. For example, if p_{=}(n, k) is the number of partitions of n with exactly k parts, the polynomial ∑ p_{=}(n, k)y^{k}, 0 ≤ k ≤ ⌊n⌋, does not, in general, have all roots real and the sequences {p_{=}(n, k)} are not log-concave, but are unimodal for large n. Also, the difference between the average number of parts and the most likely number of parts is unbounded [15]. If d(n, k) is the number of partitions of n with exactly k distinct parts, the polynomial ∑ d(n, k)y^{k}, 0 ≤ k ≤ ⌊n⌋, does not, in general, have all roots real but the sequences {d(n, k)} seem to be log-concave and are known to be unimodal for large n. Also, for large n, the difference between the average number and most likely number of parts is less than one [15]. However for these sequences derived from partitions, combinatorial techniques seem difficult to apply. In fact, Szekeres’ analytic proof [20] is the only proof that {p_{=}(n, k)} and {d(n, k)} are unimodal for n sufficiently large. No combinatorial proof of this unimodality exists. For p_{=}(n, k) and d(n, k), the most likely number of parts was computed by Szekeres in [20]. The average number of parts was computed by Luthra in 1957 and was recomputed by Kessler and Livingston in 1976 [13], since the reviewer of Luthra’s paper questioned the rigor of the calculations. The most likely number of parts in a partition of n was also computed in a 1938 paper of Husimi [12].

For a family of partitions F, let F(n, d) be the set of partitions in F(n) with Durfee square of size d. We investigate the sequences {F(n, d)} for fixed n. The Durfee polynomial is their generating function P_{F,n}(y) = ∑_{d} F(n, d)y^{d}, 0 ≤ d ≤ ⌊\sqrt{n}⌋. The most likely and the average index of {F(n, d)} are, respectively, the most likely and the average size of the Durfee square of a partition in F(n) and we denote these by m_{F}(n) and a_{F}(n), respectively.

The context of our work is presented in Sections 2 and 3. In Section 2, we describe several families F to be considered and give the recurrences for F(n, d). In Section 3 we summarize the experiments which suggest that for each of these families F, (1) there is a constant c_{F} for which m_{F}(n) ∼ c_{F}\sqrt{n} and (2) the Durfee polynomial has all roots real.

Our main results are presented in Sections 4 and 5. In Section 4, for the family of ordinary partitions, P, we find an asymptotic formula for P(n, d). In the process, we derive a simple upper bound on the number of partitions of n with at most k parts which generalizes the upper bound of Erdös for P(n). From the asymptotic formula for P(n, d) we determine the average and most likely Durfee square size and show that the numbers {P(n, d)} are asymptotically normal. The results show that for n sufficiently large, |m_{P}(n) − a_{P}(n)| ≤ 1/2 + o(1) and that {P(n, d)}, ϵn^{1/2} ≤ d ≤ (1 − ϵ)n^{1/2}, is log-concave, but leave open the question as to whether the Durfee polynomial has all roots real.

In Section 5 we prove that if F(n, d) satisfies a recurrence of the type in Section 2 and has a particular asymptotic form, then for fixed n, the most likely value of the Durfee square of a partition in F(n) grows as c_{F}\sqrt{n} for some constant c_{F} which depends only on the recurrence for F(n, d). We use this to produce, for several families of partitions F, an analytical expression for the constant c_{F} which agrees with the experimental value given in Table 2 of Section 3. The expressions are valid under the assumption about the asymptotic form of F(n, d), which by the results of Section 4 is valid at least for P(n, d).

Further directions are discussed in Section 6.

2 The Families of Partitions

We consider the Durfee polynomial for several families of partitions F.

(1) P : unrestricted partitions

(2) B : basis partitions [10, 16]

(3) D : partitions into distinct parts

(4) D̄ : partitions λ into distinct parts with λ_{d(λ)} > d(λ)

(5) D̃ : partitions λ into distinct parts with λ_{d(λ)+1} < d(λ)

(6) SC : self conjugate partitions

(7) O : partitions into odd parts

(8) E : partitions into even parts

(9) Z : partitions λ in which the number of parts is d(λ)

The families D̄ and D̃ were included because of the form of their generating functions. Z was included because its defining recurrence and generating function are similar to the other families and a_{Z}(n) and m_{Z}(n) differ by less than 1 (for n ≤ 5000), but the Durfee polynomial fails to have all roots real. Note that Z(n, d) is equal to the number of partitions into d distinct parts that differ at least by 2 (counted by one side of the first Rogers-Ramanujan identity).

Observe that for self-conjugate partitions (6), SC(n, d) = 0 if n and d have opposite parity, so the sequence {SC(n, d)} cannot be unimodal and consequently the Durfee polynomial cannot have all roots real. We consider instead the subsequence consisting of nonzero entries. For similar reasons, the sequences {E(n, d)} (for even n) and {O(n, d)} are not log-concave, but we can consider the subsequences corresponding to even d or odd d. The Durfee polynomial is then ∑_{d} F(n, 2d)y^{d} or

Family F F(n, d) = 0 when d < 0 or F(n, d) = 1 when:
(d = 0 and n > 0) or:
P, B, Z n < d^{2}  n = d^{2}
D, D̃  n < 3d^{2}/2 − d/2  n = 3d^{2}/2 − d/2
D̄  n < 3d^{2}/2 + d/2  n = 3d^{2}/2 + d/2
SC  n < d^{2} or d ≢ n mod 2  n = d^{2}
O  n < d(2⌊d/2⌋ + 1)  n = d(2⌊d/2⌋ + 1)
E  n < 2d⌊(d + 1)/2⌋ or n odd n = 2d⌊(d + 1)/2⌋

Table 1: Boundary conditions for recurrences

∑_{d} F(n, 2d + 1)y^{d}.

In the remainder of this section, we present the recurrences and boundary conditions which we used both to compute F(n, d) in Section 3 and to calculate the constants c_{F} in Section 5. The recurrence for (1) is straightforward; (2) is from [16]; (3)–(9) are explained in detail in [6]. The boundary conditions of the recurrences are given in Table 1.

• P(n, d) = 2P(n − d, d) + P(n − 2d + 1, d − 1) − P(n − 2d, d)

• B(n, d) = B(n − d, d) + B(n − 2d + 1, d − 1) + B(n − 3d + 1, d − 1)

• D(n, d) = D(n−d, d)−D(n−2d+2, d)+D(n−3d+2, d)+D(n−3d+2, d−1) +D(n − 4d + 3, d − 1) + D(n − 5d + 2, d − 1) + D(n − 6d + 3, d − 1)

• D̄(n, d) = D̄(n − d, d) + D̄(n − 3d + 1, d − 1) + D̄(n − 4d + 1, d − 1)

• D̃(n, d) = D̃(n − d, d) + D̃(n − 3d + 2, d − 1) + D̃(n − 4d + 3, d − 1)

• SC(n, d) = SC(n − 2d, d) + SC(n − 2d + 1, d − 1)

• O(n, d) = \{ \begin{matrix}O(n − d, d − 1) + O(n − 2d, d) + O(n − d, d) − O(n − 3d, d) & d odd \\ O(n − 2d, d) + O(n − 3d + 1, d − 1) & d even \end{matrix}

• E(n, d) = \{ \begin{matrix}E(n − d, d − 1) + E(n − 2d, d) + E(n − d, d) − E(n − 3d, d) & d even \\ E(n − 2d, d) + E(n − 3d + 1, d − 1) & d odd \end{matrix}

• Z(n, d) = Z(n − d, d) + Z(n − 2d + 1, d − 1)

The generating functions F_{d}(x) = ∑_{n} F(n, d)x^{n} all have a common form, roughly

F_{d}(x) = x^{d^{2}} · (∑_{n} g(n, d)x^{n}) · (∑_{n} h(n, d)x^{n}).  (2.1)

m_{F}(n) ∼ c_{F}\sqrt{n}
Family F  Experimental Value of c_{F} Theoretical Value of c_{F}
(1) P  0.54  \sqrt{6} log 2/π ≈ 0.54044
(2) B  0.62  ^{(∗)} 0.6192194165...
(3) D  0.53  2\sqrt{3} log((1 + \sqrt{5})/2)/π ≈ 0.530611
(4) D̄  0.53  2\sqrt{3} log((1 + \sqrt{5})/2)/π
(5) D̃  0.53  2\sqrt{3} log((1 + \sqrt{5})/2)/π
(6) SC, odd d, n  0.54  \sqrt{6} log 2/π
(6) SC, even d, n  0.54  \sqrt{6} log 2/π
(7) O, odd d  0.53  2\sqrt{3} log((1 + \sqrt{5})/2)/π
(7) O, even d  0.53  2\sqrt{3} log((1 + \sqrt{5})/2)/π
(8) E, odd d, even n  0.53  2\sqrt{3} log((1 + \sqrt{5})/2)/π
(8) E, even d, n  0.53  2\sqrt{3} log((1 + \sqrt{5})/2)/π
(9) Z  0.60  \sqrt{15} log((1 + \sqrt{5})/2)/π ≈ 0.59324

(∗) See Section 5 in text.

Table 2: Most likely size Durfee square: tested for 0 ≤ n ≤ 5000; logs are to the base e.

Since a partition in F(n, d) can be viewed as comprising a Durfee square of size d plus some partition with largest part at most d below it and some partition with at most d parts to its right, we get identities of the form F(n, d) = ∑_{n_{1}} g(n_{1}, d)·h(n−d^{2}−n_{1}, d), for some families of partitions G and H and (2.1) follows. Details can be found in [6]. Note that the family Z is the only one for which one of g, h is constant, since the partitions in that family have nothing below the Durfee square.

3 Statistics of the Durfee Polynomial (Experimental Results)

In Section 3.1, we describe the experiments which suggest, for the families F in Section 2, the existence of a constant c_{F} such that m_{F}(n) ∼ c_{F}\sqrt{n} and estimate its value. In Section 3.2, we present the results of our experiments to test whether all roots of the Durfee polynomial are real, to check the difference between a_{F}(n) and m_{F}(n) and to test for log-concavity.

3.1 Mode of {F(n, d)}

For a family F of partitions and an integer n, let α(i) = min{n |m_{F}(n) = i}. From our experiments, it appears that for all of the families (1) – (9), the second difference of α(i), △^{2}α(i), is essentially constant. If the second difference is, say, b, then α(i) ∼ bi^{2}/2 and thus i ∼ \sqrt{(2α(i)/b)}. This means that m_{F}(n) ∼ \sqrt{2n/b}. A slight modification of this calculation is required for the families in which we consider the sequence {F(n, d)} only for odd d or even d.

The results of our experiments are displayed in Table 2. Each of the families of partitions F(n) in column 1 was checked for n = 0, …, 5000. Column 2 gives the numerical value of c_{F} based on the data, and column 3 gives the conjectured analytical expression for c_{F}, computed as to be described in Section 5. For the family P(n, d), the analytical expression for c_{P}(n) is proven correct in Corollary 3 of Section 4.

3.2 Roots of the Durfee Polynomial

We tested the Durfee polynomials of all the families (1) – (9) and, except for the family Z (first complex root when n = 75), found that all roots are real and negative for n ≤ 1000. It was also confirmed by our experiments for n ≤ 5000 that for all of the families (1) – (9), the average and most likely Durfee square size of a partition in F(n) differ by less than 1 and that the sequences {F(n, d)} are strictly log-concave. These results help to support the conjecture that the Durfee polynomials have all roots real since, as described in Section 1, they are necessary conditions.

Because of the form of the dependencies in the recurrences for F(n, d) presented in Section 2.1, we have not found a way to use the often successful technique of [11] to prove the Durfee polynomials have all their roots negative.

4 The Asymptotics of P(n, d)

In this section, we study P(n, d), the number of partitions of the integer n having Durfee square size d. We find an asymptotic formula for P(n, d); determine the average, most likely, and asymptotic distribution of the Durfee square size; and prove some unimodality results. We denote by p(n) the number of partitions of n and by p(n, k) the number of partitions of n with at most k parts. As is well known, p(n, k) also counts partitions of n into parts all less than or equal to k. We have found the following asymptotic formula for P(n, d).

Theorem 1 Fix ϵ > 0. Uniformly for ϵ ≤ x ≤ 1 − ϵ we have

P(n, xn^{1/2}) = \frac{F (x)}{n^{5/4}} exp\{n^{1/2}G(x) + O(n^{−1/2})\}.

Here, the functions F (x) and G(x) are given by:

F (x) = 2π^{1/2}f(u)^{2}(2 + u^{2})^{5/4}(g(u) − ug′(u) − u^{2}g′′(u))^{−1/2}

and

G(x) = 2g(u)(2 + u^{2})^{−1/2},

where u = (2x^{2}/(1 − x^{2}))^{1/2} and the functions f(u), g(u), and v = v(u) are:

f(u) = \frac{1}{2π\sqrt{2}} \frac{v}{u}(1 − e^{−v} − \frac{u^{2}e^{−v}}{2} )^{−1/2}

g(u) = \frac{2v}{u} − u log(1 − e^{−v}),  (4.1)

and, an implicit definition for v,

u^{2} = v^{2}/ ∫_{0}^{v} \frac{t}{e^{t} − 1}dt.  (4.2)

There are a few preliminaries before proving the theorem. Recall the well known recursion

p(n, k) = p(n − k, k) + p(n, k − 1),  (4.3)

which says that a partition of n into k or fewer positive parts either has exactly k parts, (in which case each part may be reduced by 1 to produce a partition of n − k into k or fewer positive parts); or it has strictly fewer than k positive parts.

We need the three derivatives

g′(u) = − log(1 − e^{−v})  (4.4)
g′′(u) = − \frac{dv/du}{e^{v} − 1}  (4.5)

and

\frac{d}{dv} \frac{1}{v^{2}} ∫_{0}^{v} \frac{t}{e^{t} − 1}dt = − \frac{2}{v^{3}} ∫_{0}^{v} \frac{t}{e^{t} − 1}dt + \frac{1}{v^{2}} \frac{v}{e^{v} − 1}.

The inequality

∫_{0}^{v} \frac{t}{e^{t} − 1}dt ≥ \frac{1}{e^{v} − 1} ∫_{0}^{v} tdt = \frac{\frac{1}{2}v^{2}}{e^{v} − 1}  (4.6)

shows that \frac{1}{v^{2}} ∫_{0}^{v} \frac{t}{e^{t}−1}dt is a decreasing function of v, whence the right side of (4.2) is an increasing function of v. Thus (4.2) uniquely determines v as a function of u, and, moreover, \frac{dv}{du} ≥ 0. From (4.4) and (4.5) we see that g′ ≥ 0 and g′′ ≤ 0.

Let K > 0 be a constant, and consider the function ϕ(Z) = Zg(K/Z). By (4.1) and (4.4) we note that

2v(u) = ug(u) − u^{2}g′(u);  (4.7)

hence,

ϕ′(Z) = g(K/Z) − (K/Z)g′(K/Z) = 2v(K/Z)(K/Z)^{−1},

and

ϕ′′(Z) = (K^{2}/Z^{3})g′′(K/Z).

This shows that ϕ′′ ≤ 0. Using the inequality

(n − K)^{1/2} − n^{1/2} ≤ − \frac{1}{2}Kn^{−1/2},

and the fact that ϕ′ ≥ 0, we have

((n − K)^{1/2} − n^{1/2})ϕ′(n^{1/2}) ≤ − \frac{1}{2}Kn^{−1/2} × 2v(Kn^{−1/2})(Kn^{−1/2})^{−1}
= − v(Kn^{−1/2}).

Expanding ϕ((n − K)^{1/2}) about n^{1/2}, we find by the negativity of ϕ′′ that

(n − K)^{1/2}g(K(n − K)^{−1/2}) ≤ n^{1/2}g(u) − v(u), u = Kn^{−1/2}.  (4.8)

In a similar manner, since g′′ ≤ 0, we have

n^{1/2}g((K − 1)n^{−1/2}) ≤ n^{1/2}g(u) − g′(u), u = Kn^{−1/2}.  (4.9)

We next prove a lemma which may be useful in a broader context than this paper: a simply stated absolute upper bound for p(n, k). The proof uses the recursion satisfied by p(n, k), induction, and the above analytic facts about g(u). The reader may be interested to know that Erdös [9] used a recursion, induction, and the analytic fact ∑ n^{−2} = π^{2}/6 to prove the following simply stated upper bound for the total number of partitions p(n):

p(n) < exp{(2/3)^{1/2}πn^{1/2}}, n ≥ 1.

Lemma 1 For all integers n, k ≥ 1 we have

p(n, k) ≤ exp{n^{1/2}g(kn^{−1/2})}.  (4.10)

Remark. Because g(u) increases to (2/3)^{1/2}π, Erdös’ inequality is implied by the Lemma.

Proof. We use double induction on n and k. We start the induction by noting that if either n or k is 1, then p(n, k) = 1, and the asserted inequality (4.10) holds because g ≥ 0. Now let N, K be two integers that are both greater than or equal to 2, and take as the induction hypothesis that inequality (4.10) is true for n = N, 1 ≤ k < K, as well as for n < N, 1 ≤ k. We now distinguish two cases. Case 1: K < N. In this case, we may use the recursion (4.3), the induction hypothesis, equation (4.4) in the form

e^{−v} + e^{−g′} = 1,

inequality (4.8), and inequality (4.9) to conclude, with u = KN^{−1/2},

p(N, K) = p(N − K, K) + p(N, K − 1)
≤ exp{(N − K)^{1/2}g(K(N − K)^{−1/2})} + exp{N^{1/2}g((K − 1)N^{−1/2})}
≤ exp{N^{1/2}g(u)} · (exp{−v} + exp{−g′})
= exp{N^{1/2}g(u)}.

Case 2: K ≥ N. In this case, because g(u) is an increasing function, and p(N, K) = p(N, N) for K ≥ N, we may assume that K = N. From (4.7) and g′ ≥ 0 we have

ug(u) ≥ v(u),

and so, using (4.9) again and letting u = N^{1/2},

p(N, N) = 1 + p(N, N − 1)
≤ 1 + exp{N^{1/2}g(u) − g′(u)}
= exp{N^{1/2}g(u)} · (exp{−N^{1/2}g(u)} + exp{−g′})
≤ exp{N^{1/2}g(u)} · (exp{−v} + exp{−g′})
= exp{N^{1/2}g(u)},

and the proof of the Lemma is complete. □ Proof of Theorem. The Ferrers diagram of a partition counted by P(n, d) consists of a d × d square with two independent partitions of n_{1} and n_{2}, n_{1} + n_{2} = n − d^{2}, attached to the east and south; the one to the east has at most d parts, and the one to the south has no parts exceeding d. Thus

P(n, xn^{1/2}) = ∑_{n_{1}+n_{2}=(1−x^{2})n} p(n_{1}, xn^{1/2})p(n_{2}, xn^{1/2}).  (4.11)

Szekeres [20] gives a complete asymptotic expansion for p(n, k) that uses the quantities (V, β) defined implicitly by the pair of equations V β = k and

β^{2} ∫_{0}^{V} \frac{t}{e^{t} − 1}dt + \frac{1}{2}β(\frac{V}{e^{V} − 1} − 1) + \frac{1}{12}(\frac{1}{2} + \frac{1}{e^{V} − 1} + \frac{V e^{V}}{(e^{V} − 1)^{2}} ) = n.

Clearly, β can be eliminated from the second equation by substituting β = k/V from the first. Uniformly for k restricted to the range ϵn^{1/2} ≤ k ≤ ϵ^{−1}n^{1/2}, where ϵ is an arbitrary prescribed positive constant, we find:

V = v − \frac{1}{2v} (\frac{v}{e^{v} − 1} − 1)(\frac{d}{dv} \frac{1}{v^{2}} ∫_{0}^{v} \frac{t}{e^{t} − 1}dt)^{−1}k^{−1} + O(n^{−1}).

By substituting this into Szekeres’ Theorem we obtain

p(n, un^{1/2}) = \frac{f(u)}{n} exp\{n^{1/2}g(u) + O(n^{−1/2})\}, uniformly for ϵ ≤ u ≤ ϵ^{−1}. (4.12)

An alternate proof of the latter formula which uses no complex variables appears in [4]; however, the error bound in the latter is weaker than the above.

Introduce the variable t by

n_{1}, n_{2} = \frac{1 − x^{2}}{2} n ± tn^{1/2},

the plus sign being used for n_{1}, the minus for n_{2}. View the summation in (4.11) as extending over a discrete set of real t, with stepsize n^{−1/2}:

P(n, xn^{1/2}) = ∑_{t} term(t);

we find using (4.12), uniformly for |t| ≤ n^{1/3}:

term(t) = \frac{4f(u)^{2}}{(1 − x^{2})^{2}n^{2}} exp\{\frac{2g(u)}{\sqrt{2 + u^{2}}} n^{1/2} + \frac{βt^{2}}{n^{1/2}} + O(\frac{t^{4}}{n^{3/2}} + \frac{t^{2}}{n} + \frac{1}{n^{1/2}} )\},

where

β = (2 + u^{2})^{3/2}(−g(u) + ug′(u) + u^{2}g′′(u))/4.

We sum over t by approximation with an integral; bounding the error committed, and justifying the replacement of a finite integral with an infinite one, are standard arguments in asymptotic analysis (see, for example, [8]). Algebraic simplification leads to the functions F (x) and G(x) given in the statement of the theorem; it remains for us only to bound the tails by showing:

∑_{|t|>n^{1/3}} term(t) = \frac{O(n^{−1/2})}{n^{5/4}} exp\{\frac{2g(u)}{\sqrt{2 + u^{2}}} n^{1/2}\}.  (4.13)

To see this, we use the upper bound proven in the Lemma. Letting u_{i} = xn^{1/2}/n_{i}^{1/2}, we have

term(t) = p(n_{1}, xn^{1/2})p(n_{2}, xn^{1/2})
≤ exp{n_{1}^{1/2}g(u_{1}) + n_{2}^{1/2}g(u_{2})}.  (4.14)

Since g′′ ≤ 0, we have α_{1}g(u_{1}) + α_{2}g(u_{2}) ≤ g(α_{1}u_{1} + α_{2}u_{2}) whenever α_{1} + α_{2} = 1, and so

n_{1}^{1/2}g(u_{1}) + n_{2}^{1/2}g(u_{2}) ≤ (n_{1}^{1/2} + n_{2}^{1/2})g(\frac{2xn^{1/2}}{n_{1}^{1/2} + n_{2}^{1/2}} ).  (4.15)

Define ϕ(Z) = Zg(2xn^{1/2}/Z). As noted in the discussion following equation (4.7),

ϕ′(Z) = 2v(2xn^{1/2}/Z) × (2xn^{1/2}/Z)^{−1},

and ϕ′′(Z) ≤ 0. The negativity of ϕ′′ implies

ϕ(Z_{1}) ≤ ϕ(Z_{0}) + (Z_{1} − Z_{0})ϕ′(Z_{0}).  (4.16)

We apply the latter with Z_{0} = 2^{1/2}(n_{1} + n_{2})^{1/2} and Z_{1} = n_{1}^{1/2} + n_{2}^{1/2}. Recalling u^{2} = 2x^{2}/(1 − x^{2}), we note that

ϕ(Z_{0}) = 2(2 + u^{2})^{−1/2}g(u)n^{1/2} and ϕ′(Z_{0}) = 2v/u.

Using

(n_{1} + n_{2})^{1/2} ≤ n_{1}^{1/2} + n_{2}^{1/2} ≤ 2^{1/2}(n_{1} + n_{2})^{1/2},

we find

Z_{0} − Z_{1} = 2^{1/2}(n_{1} + n_{2})^{1/2} − (n_{1}^{1/2} + n_{2}^{1/2})
= \frac{(n_{1}^{1/2} − n_{2}^{1/2})^{2}}{2^{1/2}(n_{1} + n_{2})^{1/2} + (n_{1}^{1/2} + n_{2}^{1/2})}
≥ \frac{(n_{1}^{1/2} − n_{2}^{1/2})^{2}}{(1 + 2^{1/2})(n_{1}^{1/2} + n_{2}^{1/2})}
= \frac{(n_{1} − n_{2})^{2}}{(1 + 2^{1/2})(n_{1}^{1/2} + n_{2}^{1/2})^{3}}
≥ \frac{(n_{1} − n_{2})^{2}}{(1 + 2^{1/2})2^{3/2}(n_{1} + n_{2})^{3/2}}
= \frac{4t^{2}}{(1 + 2^{1/2})2^{3/2}(1 − x^{2})^{3/2}n^{1/2}} .

Substituting for ϕ(Z_{1}), ϕ(Z_{0}), ϕ′(Z_{0}), and Z_{1} − Z_{0} in (4.16), we have shown

(n_{1}^{1/2} +n_{2}^{1/2})g(\frac{2xn^{1/2}}{n_{1}^{1/2} + n_{2}^{1/2}} ) ≤ 2(2+u^{2})^{−1/2}g(u)n^{1/2} − \frac{(4 − \sqrt{8})v}{u} (1−x^{2})^{−3/2}t^{2}n^{−1/2}.

Together with (4.14) and (4.15) we obtain

term(t) ≤ exp{2(2 + u^{2})^{−1/2}g(u)n^{1/2} − c_{4}t^{2}n^{−1/2}},  (4.17)

where the positive constant c_{4} is a minimum over the compact set ϵ ≤ x ≤ 1 − ϵ:

c_{4} = (4 − \sqrt{8}) min_{x} \frac{v}{u}(1 − x^{2})^{−3/2} > 0, u = (\frac{2x^{2}}{1 − x^{2}} )^{1/2}.

Of course, for |t| > n^{1/3}, t^{2}n^{−1/2} > n^{1/6}, which is more than enough to prove (4.13). The proof of Theorem 1 is complete. For future reference, we remark that the inequality (4.17) is valid for all t, even when one of n_{1} or n_{2} is zero. □

To locate the mode of P(n, d), the above suggests that we find x_{0} such that G′(x_{0}) = 0. It is rather fortunate that there is a closed form for x_{0}, and it depends on the fact (see [1], formula 27.7.3) that

∫_{0}^{log 2} \frac{t}{e^{t} − 1}dt = \frac{π^{2}}{12} − \frac{1}{2}(log 2)^{2}.

To see how this plays a role in the evaluation of x_{0}, we use the chain rule to find

G′(x) = (2g′(u)(2 + u^{2})^{−1/2} − 2u(2 + u^{2})^{−3/2}g(u)) \frac{du}{dx}.

The vanishing of G′(x) implies

(2 + u^{2})g′(u) = ug(u),

which in conjunction with 2v = ug − u^{2}g′ leads to the equation g′ = v. On the other hand, we know that identically e^{−v} + e^{−g′} = 1, and so we conclude that both g′ and v are log 2 when G′(x) = 0. Using the above evaluation of the definite integral, we find x_{0} = \sqrt{6} log 2/π, and we have the first corollary.

Corollary 1 Let x_{0} = \sqrt{6} log 2/π, d = x_{0}n^{1/2} + tn^{1/4}, c_{1} = \frac{π}{2(6)^{5/4}} (\frac{π^{2}}{6} − 2(log 2)^{2})^{−1/2}, c_{2} = π(2/3)^{1/2}, and c_{3} = \frac{−32π^{3}}{(24)^{3/2}} (\frac{π^{2}}{6} − 2(log 2)^{2})^{−1}. Then, uniformly for t = o(n^{1/12}),

P(n, d) = \frac{c_{1}}{n^{5/4}} exp\{c_{2}n^{1/2} + \frac{1}{2}c_{3}t^{2} + o(1)\}.

Thus the numbers P(n, d) are asymptotically normal as n → ∞.

Remark. The constants c_{i} are, respectively, the values of F, G, and G′′ at x_{0} = \frac{log 2×\sqrt{6}}{π}. (The function G(x) is maximized at x = x_{0}).

Corollary 2 For any positive ϵ there is an integer n_{0} (= n_{0}(ϵ)) such that for all n ≥ n_{0} and d satisfying ϵn^{1/2} ≤ d ≤ (1 − ϵ)n^{1/2} we have

P(n, d)^{2} > P(n, d − 1)P(n, d + 1).

Proof. Using an additional term in Szekeres’ expansion [20], we may refine equation (4.12) by replacing the error bound O(n^{−1/2}) with h(u)n^{−1/2}+O(n^{−1}), for appropriate h(u). This implies that there is a differentiable function H(x) such that

P(n, xn^{1/2}) = \frac{F (x)}{n^{5/4}} exp\{n^{1/2}G(x) + H(x)/n^{1/2} + O(n^{−1})\}.

It is not necessary to know, and we have not computed, the explicit form of H(x). Letting x = d/n^{1/2}, we evaluate the functions F, G, H at the arguments x, x ± n^{−1/2} and obtain

\frac{P(n, d)^{2}}{P(n, d − 1) · P(n, d + 1)} = exp\{−G′′(x)/n^{1/2} + O(n^{−1})\}.

The proof is completed by the calculation

G′′(x) = (2 + u^{2})^{3/2} \frac{−ve^{v}}{u(e^{v} − 1 − \frac{1}{2}u^{2})}.

G′′(x) is indeed negative, as it is implied by (4.6) that e^{v} − 1 − \frac{1}{2}u^{2} is positive. This proves Corollary 2. □

Corollary 3 Let a(n) be the mean of d(λ), λ varying uniformly over all partitions of n. We have:

a(n) = x_{0}n^{1/2} + \frac{F′/F}{−G′′} + O(n^{−1/2}).

Moreover, if m(n) is any sequence such that P(n, m(n)) = max_{d} P(n, d), then, as n → ∞,

|a(n) − m(n)| ≤ 1/2 + o(1).

Proof. We begin by showing m(n)n^{−1/2} → x_{0}. Otherwise, for some η > 0 and infinitely many n, |m(n)n^{−1/2} − x_{0}| ≥ η. Since G′(x_{0}) = 0 and G′′(x_{0}) < 0, for some δ > 0 and the same infinite set of n, G(m(n)n^{−1/2}) < G(x_{0}) − δ. Hence, for infinitely many n, (using (4.17) for the first inequality and Theorem 1 for the last),

P(n, m(n)) ≤ n exp{n^{1/2}G(m(n)n^{−1/2})}
= o(1) × exp{n^{1/2}(G(x_{0}) − δ/2)}
= o(1) × P(n, ⌊x_{0}n^{1/2}⌋),

contradicting the assumption that m(n) is a mode.

Next we obtain a closer estimate of m(n). The existence of H(x), as discussed in the proof of Corollary 2, gives us

P(n, x_{0}n^{1/2} + t) = \frac{F e^{G\sqrt{n}+H/\sqrt{n}}}{n^{5/4}} exp\{ \frac{\frac{1}{2}t^{2}G′′ + tF′/F}{n^{1/2}} + O((1 + t^{3})n^{−1})\}, t = o(n^{1/3}).

(4.18)

Here we follow the convention that F, F′, G, G′′, H denote the latter functions evaluated at the special value x_{0}. Let t_{0} be such that the expression \frac{1}{2}t^{2}G′′ + tF′/F is the same at both t_{0} and t_{0} + 1:

t_{0} = \frac{F′/F}{−G′′} − \frac{1}{2}.

It need not be the case that x_{0}n^{1/2} + t_{0} is an integer. Because m(n)n^{−1/2} → x_{0} we certainly know that m(n) lies for large n in the range ϵn^{1/2} ≤ d ≤ (1 − ϵ)n^{1/2}, where (by Corollary 2) P(n, d) is unimodal. If d is the largest integer which is strictly less than x_{0}n^{1/2} +t_{0}, say, d = x_{0}n^{1/2} +t_{0} −θ, 0 < θ ≤ 1, then, by (4.18) and the definition of t_{0}, for n sufficiently large,

P(n, d + 1)/P(n, d) = exp{−θG′′n^{−1/2} + O(n^{−1})} > 1.

Similarly, if d is the smallest integer which is strictly larger than x_{0}n^{1/2} + t_{0} + 1, we can show that P(n, d) < P(n, d − 1). It follows from these estimates and Corollary 2, then, that

x_{0}n^{1/2} + t_{0} ≤ m(n) ≤ x_{0}n^{1/2} + t_{0} + 1.

This locates m(n) to within 1, for n large. We can locate a(n) even more exactly: multiplying both sides of (4.18) by x_{0}n^{1/2} + t, summing over t, and dividing by p(n) gives

a(n) = x_{0}n^{1/2} − \frac{F′}{F G′′} + O(n^{−1/2}).

The Corollary now follows. □

Note that the assertions of the three corollaries are consequences of the conjecture that the Durfee polynomial P_{P,n}(y) has only real roots; as such, they may be taken as evidence of this conjecture.

5 The Most Likely Size of the Durfee Square

Note that for all of the families F considered in Section 2, F(n, d) satisfies a recurrence of the form:

F(n, d) = ∑_{i=1}^{m_{0}} C_{i}F(n − e_{i}d + f_{i}, d) + ∑_{i=1}^{m_{1}} D_{i}F(n − g_{i}d + h_{i}, d − 1),  (5.1)

where e_{i}, f_{i}, g_{i}, h_{i}, m_{0}, and m_{1} are nonnegative integers. Associate with the recursion (5.1) the two polynomials

Q(w) = ∑_{i=1}^{m_{0}} C_{i}w^{e_{i}}, R(w) = ∑_{i=1}^{m_{1}} D_{i}w^{g_{i}}.  (5.2)

Theorem 2 Assume that F(n, d) satisfies a recurrence of the form (5.1) and furthermore that F(n, d) is given, uniformly in d, by an asymptotic formula

F(n, d) = \frac{f(u)}{n^{b}} exp\{n^{1/2}g(u) + o(1)\}, u = d/n^{1/2}  (5.3)

for differentiable functions f(u), g(u) and exponent b. Then m_{F}(n), the mode of d(λ) over all partitions λ ∈ F(n), is given by

m_{F}(n) ∼ c_{F}\sqrt{n}.

where c_{F} is a constant which can be computed from the polynomials Q(w) and R(w) in (5.2).

Proof. Let the function v = v(u) be defined by

v = \frac{1}{2}ug(u) − \frac{1}{2}u^{2}g′(u).  (5.4)

Using the Taylor series

(n − e_{i}d + f_{i})^{1/2} = n^{1/2} − \frac{1}{2}e_{i}u + ⋯
d(n − e_{i}d + f_{i})^{−1/2} = u + \frac{\frac{1}{2}e_{i}u^{2}}{n^{1/2}} + ⋯
(n − e_{i}d + f_{i})^{1/2}g(d(n − e_{i}d + f_{i})^{−1/2}) = n^{1/2}g(u) − e_{i}v + ⋯,

we find from (5.3)

F(n − e_{i}d + f_{i}, d) = \frac{f(u)}{n^{b}} exp\{n^{1/2}g(u) − e_{i}v + o(1)\},

uniformly for d = O(n^{1/2}). The other terms on the right side of (5.1) can be expanded similarly. When these are substituted into the recursion (5.1), we find that g(u) must satisfy a certain differential equation. (In the above Taylor series, the ellipsis “⋯” denotes terms of lower order. Further terms are needed to determine the differential equation satisfied by the function f(u), but for our purposes here we need only g(u). See [4] for a detailed example of this method.) The differential equation found for g(u) is, after division by common factors,

1 = Q(e^{−v}) + e^{−g′}R(e^{−v}),  (5.5)

with Q(w), R(w) given in (5.2). Differentiating with respect to u and multiplying by −1:

0 = (Q′(e^{−v}) + e^{−g′}R′(e^{−v}))e^{−v} \frac{dv}{du} + e^{−g′}g′′R(e^{−v}).

We can eliminate g′′ and e^{−g′} from the previous by, first, differentiating the definition (5.4) of v with respect to u, and rearranging:

g′′ = \frac{−1}{v} · (\frac{v^{2}}{u^{2}} )′,

and, second, solving (5.5) for e^{−g′}. Isolating the term (v^{2}/u^{2})′ in the result, we obtain v implicitly as a function of u (and u explicitly as a function of v):

\frac{v^{2}}{u^{2}} = ∫_{0}^{v} H(t) dt,

the function H(t) being the integrand which appears below in equation (5.6). As in the beginning of the proof of Corollary 3, any mode d(n) for F(n, d) must satisfy d(n)n^{−1/2} → u_{0}, where g′(u_{0}) = 0. The value of u_{0} satisfying the latter condition is obtained by first solving the following polynomial in e^{−v_{0}}

1 = Q(e^{−v_{0}}) + R(e^{−v_{0}}),

(thus v_{0} is the logarithm of a certain algebraic number), and then using

u_{0} = v_{0} × [∫_{0}^{v_{0}} t(\frac{Q′(e^{−t})e^{−t}}{1 − Q(e^{−t})} + \frac{R′(e^{−t})e^{−t}}{R(e^{−t})} )dt]^{−1/2}  (5.6)

for u_{0}. □

For all the families of partitions which we have considered, the preceding integral can be evaluated in closed form using the dilogarithm function Li(X), where

Li(X) = ∑_{m=1}^{∞} X^{m}/m^{2}.

That the dilogarithm plays a role in the evaluation of integrals such as (5.6) is suggested by the formula

∫_{0}^{v} \frac{t}{e^{t} − 1}dt = \frac{π^{2}}{6} + v log(1 − e^{−v}) − Li(e^{−v}),  (5.7)

which can be verified through differentiation.

For instance, in the case of the basis partitions B(n, d), we find that e^{−v_{0}} is the positive root of the cubic

X^{3} + X^{2} + X = 1,

and u_{0} = 0.6192194165 ⋯ is given by

u_{0}^{2} = \frac{v_{0}^{2}}{−v_{0}^{2} + π^{2}/4 − 2 Li(e^{−v_{0}}) + \frac{1}{2} Li(e^{−2v_{0}})}.

The possibility of evaluating a dilogarithm by asymptotic partition counting was suggested by Andrews and carried out by Richmond and Szekeres [18]. See also [14].

Analytic expressions for the constants for all of the families (1) – (9) were computed in this way and are displayed in Table 2. Although in every case they agree with the experimental values obtained, their validity relies on the assumption (5.3). However, so far (5.3) has been verified only for the family P(n, d) (Theorem 1).

We add a few comments intended to assist the reader who would like to check the computation of the values for c_{F} for families (1), (3) – (9) appearing in Table 2. The polynomials Q(w) and R(w) can be read off directly from the recursion in Section 2 for the family. In each case, the equation Q(w) + R(w) = 1 has a unique positive real root, which is one of 1/2, (1/2)^{1/2}, ρ, or ρ^{1/2}, where ρ is the golden ratio: the positive solution to ρ^{2} + ρ = 1. Each integrand appearing in (5.6) can be expressed by partial fractions in the form

At + \frac{Bt}{1 − e^{−t}} + \frac{Ct}{1 + e^{−t}} + \frac{Dt}{1 − e^{−2t}} ,

with rational A, B, C, D. Each integral can be evaluated by a change of variable in (5.7) giving

∫_{0}^{v} \frac{t}{1 − e^{−t}} dt = \frac{1}{2}v^{2} + ψ(e^{−v}),

∫_{0}^{v} \frac{t}{1 + e^{−t}} dt = \frac{1}{2}v^{2} − ψ(e^{−v}) + \frac{1}{2}ψ(e^{−2v}),

and

∫_{0}^{v} \frac{t}{1 − e^{−2t}} dt = \frac{1}{2}v^{2} + \frac{1}{4}ψ(e^{−2v}),

where

ψ(e^{−v}) = ∫_{0}^{v} \frac{t}{e^{t} − 1}dt = v log(1 − e^{−v}) − Li(e^{−v}) + \frac{π^{2}}{6} .

A few special values of the dilogarithm are needed, which can be found in Table 13.1 of [14]:

Li(1/2) = \frac{π^{2}}{12} − \frac{1}{2}(log 2)^{2};

Li(ρ) = \frac{π^{2}}{10} − (log ρ)^{2};

Li(ρ^{2}) = \frac{π^{2}}{15} − (log ρ)^{2}.

There is a check on one’s algebra in that all of the integrals (except Family (2), of course) evaluate to a rational number times π^{2}, that is, the logarithms cancel out. One final note is needed: to treat O(n, odd), one must manipulate the recursion so that the right side contains terms O(n′, d) only with odd d. Similarly for O(n, even), E(n, odd), and E(n, even).

6 Directions for Further Research

Although it has been verified for n ≤ 1000, it remains open, for all of the families of partitions (1) – (8) of Section 2, whether the Durfee polynomial P_{F,n} has all roots real. The key may lie in the common form of the generating functions for the F(n, d). Although it has been verified for n ≤ 5000, it is open for the families (2) – (9) whether the sequences {F(n, d)} are at least log-concave and whether the average and the most likely Durfee square size differ by less than 1. For the family (1) of ordinary partitions, we have established, at least for sufficiently large n, that {P(n, d)} is log-concave and that the average and most likely Durfee square size differ by less than 1.

In Theorem 1 of Section 4, we found an asymptotic formula for P(n, d) which allowed us to show that the most likely Durfee square size for a partition in P(n) is

m_{P}(n) ∼ (\sqrt{6} log 2/π)(\sqrt{n}).

If we could show that the families (2) – (9) have an asymptotic form similar to P(n, d) (as described in Theorem 2), then Theorem 2 of Section 5 shows that for each of these families F, m_{F}(n) ∼ c_{F}\sqrt{n} for a constant c_{F} depending only on the recurrence for F(n, d) in Section 2. Furthermore, we have computed the analytic expression c_{F} would have and noted that it agrees with the empirical data.

It should be possible to apply the techniques of Section 4 to compute the asymptotics of F(n, d) for all the families (2) – (9). Note that one of the key tools in the proof of Theorem 1 was the derivation of a simple upper bound on p(n, k) (Lemma 1), so one approach is to come up with a version of Lemma 1 for each family F. Even better, our hope is that there will be some general approach to finding the asymptotic form of F(n, d) for any family F of partitions given by a recursion of the form in Section 2. Acknowledgment. We thank Herbert Wilf for helpful discussions and for suggesting the family of self-conjugate partitions, and an anonymous referee for detecting several errors in the originally submitted version of the paper.

References

[1] M. Abramowitz and I. A. Stegun, Handbook of Mathematical Functions, National Bureau of Standards, 1972.

[2] M. Benoumhani, Sur une proprieté des polynômes a racines réelles négatives, J. de Math. Pures et Appliquées 75 (1996) 85-105.

[3] F. Brenti, Log-concave and unimodal sequences in algebra, combinatorics, and geometry: an update, Jerusalem combinatorics ’93, Contemp. Math., 178, Amer. Math. Soc., Providence, RI (1994) 71-89.

[4] E. R. Canfield, From recursions to asymptotics: on Szekeres’ formula for the number of partitions, Electron. J. Combin., 4(2) (1997) R6.

[5] L. Comtet, Advanced Combinatorics, D. Reidel, 1974.

[6] S. Corteel, Computer methods applied to two problems about integer partitions, M. S. Thesis, Department of Computer Science, North Carolina State University, 1997.

[7] J. Darroch, On the distribution of the number of successes in independent trials, Ann. Math. Statist., 35 (1964) 1317-1321.

[8] N. G. de Bruijn, Asymptotic Methods in Analysis, North-Holland, Amsterdam 1958; also published by Dover, 1981.

[9] P. Erdös, On an elementary proof of some asymptotic formulas in the theory of partitions, Annals of Math.(2) 43 (1942) 437-450.

[10] H. Gupta, The rank-vector of a partition, Fibonacci Quarterly 16, no. 6 (1978) 548-552.

[11] L. H. Harper, Stirling behavior is asymptotically normal, Ann. Math. Stat. 38 (1967) 410-414.

[12] Husimi, K., Partitio numerorum as occurring in a problem of nuclear physics, Proceedings of the Physico-Mathematical Society of Japan 20 (1938), 912-925.

[13] Kessler, I. and Livingston, M., The expected number of parts in a partition of n, Monatshefte für Mathematik 81 (1976), 203-212.

[14] J. H. Loxton, Partition identities and the dilogarithm, in Structural Properties of Polylogarithms (L. Lewin ed.), American Mathematical Society, 1991 pages 287-299.

[15] S. M. Luthra, On the average number of summands in a partition of n. Proceedings of the National Institute of Sciences of India, part A: physical sciences, 23 (1957) 483-498.

[16] J. M. Nolan, C. D. Savage, and H. S. Wilf, Basis partitions, Discrete Math., to appear.

[17] J. Pitman, Probabilistic bounds on the coefficients of polynomials with only real zeros, J. Combin. Theory Ser. A 77 (1997), no. 2, 279-303.

[18] B. Richmond and G. Szekeres, Some formulas related to dilogarithms, the zeta function, and the Andrews-Gordon identities, J. Austr. Math. Soc. 31 (1981) 362–373.

[19] R. Stanley, Log-concave and unimodal sequences in algebra, combinatorics, and geometry, Graph theory and its applications: East and West (Jinan, 1986), Ann. New York Acad. Sci., 576 (1989) 500-535.

[20] G. Szekeres, Some asymptotic formulae in the theory of partitions (II), Quart. J. of Math. (Oxford) (2) 4 (1953) 96-111.