From Recursions to Asymptotics: On Szekeres’ Formula for the Number of Partitions

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

                           erc@cs.uga.edu

For Herb Wilf on his 65-th Birthday

Submitted: August 1, 1996; Accepted: November 21, 1996

Abstract.

We give a new proof of Szekeres’ formula for P (n, k), the number of partitions of the integer n having k or fewer positive parts. Our proof is based on the recursion satisfied by P (n, k) and Taylor’s formula. We make no use of the Cauchy integral formula or any complex variables. The derivation is presented as a step-by-step procedure, to facilitate its application in other situations. As corollaries we obtain the main term of the Hardy-Ramanujan formulas for p(n) = the number of unrestricted partitions of n, and for q(n) = the number of partitions of n into distinct parts.

AMS-MOS Subject Classification (1990). Primary: 05A17 Secondary: 05A20, 05A16, 11P81

1 Introduction.

A partition of an integer n into k parts is a solution to the system

n = x_{1} + x_{2} + ⋯ x_{k}, x_{1} ≥ x_{2} ≥ ⋯ ≥ x_{k} > 0.

Let P (n, k) be the number of partitions of n into k or fewer parts. We will prove the following.

Theorem. (Szekeres) Let ϵ > 0 be given. Then, uniformly for k ≥ n^{1/6},

P (n, k) = \frac{f(u)}{n} exp\{n^{1/2}g(u) + O(n^{−1/6+ϵ})\}.

Here, u = k/n^{1/2}, and the functions f(u), g(u) are:

f(u) = \frac{v}{2^{3/2}πu}(1 − e^{−v} − \frac{1}{2}u^{2}e^{−v})^{−1/2}  (1.1)
g(u) = \frac{2v}{u} − u log(1 − e^{−v}),  (1.2)

where v (= v(u)) is determined implicitly by

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

Remarks. The estimate can be made uniform for the entire range k ≥ 1 by adding 1/k to the big-oh term. The last equation uniquely determines v because the right hand side is an increasing function of v.

Szekeres presents his results in two papers [12, 13], using substantially different approaches for two distinct though slightly overlapping ranges of k. The papers are remarkable both for the depth of the analysis contained in them, and for the precision of their results. Indeed, Szekeres’ is the only known proof that p (n, k) is unimodal in k for fixed n. (p (n, k) = P (n, k) − P (n, k − 1) is the number of partitions of n with exactly k parts. No combinatorial proof of this unimodality result is known, and Szekeres’ proof itself holds only for n sufficiently large.)

As a partial justification for publishing the reproof of an old theorem, I offer the following quotation from the famous paper [7, p. 78]: (recall that Hardy and Ramanujan used the theory of linear transformations of elliptic functions to prove their asymptotic formula for p (n), the total number of partitions of n.)

“It is very important, in dealing with such a problem as this, to distinguish clearly the various stages to which we can progress by arguments of a progressively ‘deeper’ and less elementary character. … the more elementary methods are likely to be applicable to other problems in which the more subtle analysis is impracticable.”

Erdös [6] has given an elementary (meaning complex-variable-free) derivation of the main term in the Hardy-Ramanujan formula using the recursion:

np (n) = ∑_{ν,μ} νp (n − μν).

Our proof also uses a recursion, and differs from Szekeres’ in the absence of complex variables. It is perhaps noteworthy that we can recover all of Szekeres’ result, including the leading constant, and can consolidate his two formulas into the one given in the Theorem above. Moreover, our method can be used to estimate other two-dimensional arrays of combinatorial significance.

For this last reason, we present in the next section a derivation of our result in the form of a step-by-step procedure intended to be generally applicable. In the procedure section we give only the key formulas while the next section of the paper contains more details and justification. In the procedure section we do not give the specific definitions of the functions a(u), A_{1}(u), A_{2}(u); these are found in the later section.

The origin of the method presented here is [2], and a later example is [3]. Both of these deal with graphical enumeration problems. The present paper differs in the area of application (partitions), the n^{1/2} term exponentiated in the approximation formula, and in the procedural style of presentation. This style was chosen both to facilitate future applications and also as a first step toward possible software implementation.

Knessl and Keller [8, 9] demonstrate a method with similarities to the one presented here. As they point out, their method is formal. Formulas found via their formal method are observed to be asymptotically correct over a certain range by comparison to known results. However, proof of asymptotic correctness is not a part of their method. The reader will see that the first four steps in the following procedure section constitute a formal procedure for arriving at a putative formula; the remaining eighteen steps provide a general approach to proving a big-oh bound on the error.

For a comprehensive overview of asymptotic methods in enumeration, the reader may consult [11].

2 Procedure.

Step 1. Start with a recursion for the doubly-indexed sequence to be estimated.

P (n, k) = P (n − k, k) + P (n, k − 1).

Step 2. Guess the form of the estimate.

P (n, k) ≈ n^{−1} exp{n^{1/2}g(u) + a(u)}, u = k/n^{1/2}.

Step 3. Express the right side of the recursion in terms of u, g(u), a(u), using Taylor series.

\begin{aligned}P (n − k, k) & ≈ n^{−1} exp\{n^{1/2}g(u) + a(u) − ug(u)/2 + u^{2}g′(u)/2 + \frac{A_{1}(u)}{n^{1/2}} + ⋯\} \\ P (n, k − 1) & ≈ n^{−1} exp\{n^{1/2}g(u) + a(u) − g′(u) + \frac{A_{2}(u)}{n^{1/2}} + ⋯\}. \end{aligned}

Remarks. Because of its frequent appearance, we define v to be the following function:

v(u) = ug(u)/2 − u^{2}g′(u)/2.

It emerges after solving for g(u) in Step 4 that this function v(u) is given by (1.3). For typographical brevity we often omit the argument u from functions such as v, g, a, g′, A_{1}, and A_{2}.

Step 4. Substitute the guessed form into the recursion; equate coefficients of like powers of n on both sides, and solve the resulting differential equations for g(u), a(u). Dividing through by n^{−1} exp{n^{1/2}g + a}, and expanding the exponential function,

1 = e^{−v}(1 + \frac{A_{1}}{n^{1/2}} + ⋯) + e^{−g′}(1 + \frac{A_{2}}{n^{1/2}} + ⋯);

this gives one differential equation determining g(u):

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

and another determining a(u):

0 = e^{−v}A_{1} + e^{−g′}A_{2}.  (2.2)

Step 5. Solve for P (n, k) when k is sufficiently small, by other means.

P (n, k) = \frac{1}{k!}\binom{n − 1}{k − 1} exp\{O(k^{3}/n)\}, for k = O(n^{1/3}),

= \frac{1/2π}{n} exp\{k log(\frac{ne^{2}}{k^{2}} ) + O(k^{3}/n + 1/k)\}.

Remark. The first equality above is due to Erdös and Lehner [5].

Step 6. Define b(n, k) to be the relative error of the approximation.

P (n, k) = n^{−1} exp{n^{1/2}g(u) + a(u)}(1 + b(n, k)).

Step 7. Expand the functions g(u), a(u) for small u to see how the approximator behaves for k small.

g(u) = −2u log(u) + 2u + O(u^{3})
a(u) = − log(2π) + O(u^{4})
n^{−1} exp\{n^{1/2}g(u) + a(u)\} = \frac{1/2π}{n} exp\{k log(\frac{ne^{2}}{k^{2}} ) + O(k^{3}/n)\}.

Step 8. Compare Steps 5 and 7 to bound b(n, k) for k sufficiently small.

b(n, k) = O(k^{3}/n + 1/k), for k = O(n^{1/3}).

Step 9. Hypothesize a bound of the form k^{α}/n^{β} for b(n, k), and a range for which it is true.

|b(n, k)| ≤^{?} Ck^{α}/n^{β}, for k ≥ n^{δ_{1}}.

Step 10. Determine conditions on α, β such that hypothesis ≤^{?} holds for sufficiently large C in some initial infinite segment of k. To achieve

max(k^{3}/n, 1/k) ≤ Ck^{α}/n^{β}, n^{δ_{1}} ≤ k ≤ n^{δ_{2}},

it suffices to have

β ≤ (1 + α)δ_{1}, (3 − α)δ_{2} ≤ 1 − β, δ_{1} < δ_{2} < 1/3

Step 11. In preparation for a proof by induction of the hypothesized bound on |b(n, k)|, give a recursion for the latter. Using the definition of Step 6,

1 + b(n,k)

= \frac{(n − k)^{−1} exp\{(n − k)^{1/2}g(k(n − k)^{−1/2}) + a(k(n − k)^{−1/2})\}}{n^{−1} exp\{n^{1/2}g(u) + a(u)\}}(1 + b(n − k, k))

+ \frac{n^{−1} exp\{n^{1/2}g((k − 1)n^{−1/2}) + a((k − 1)n^{−1/2})\}}{n^{−1} exp\{n^{1/2}g(u) + a(u)\}}(1 + b(n, k − 1))

= T_{1}(n, k)(1 + b(n − k, k)) + T_{2}(n, k)(1 + b(n, k − 1)),

say. Step 12. When using the above b(n, k) recursion in the inductive step, take advantage of k − 1 in place of k:

\frac{(k − 1)^{α}}{n^{β}} = \frac{k^{α}}{n^{β}} (1 − α/k + O(k^{−2}));

and compensate fairly for n − k in place of n:

\frac{k^{α}}{(n − k)^{β}} = \frac{k^{α}}{n^{β}} (1 + βk/n + O(k^{2}n^{−2})).

Small u

Steps 13 through 16 involve small u: u ≤ ϵ_{0}. The correct choice of ϵ_{0} appears in Step 15. All big-oh assertions in Steps 13 through 16 are uniform for u ≤ ϵ_{0}.

Step 13. Using Taylor series with remainder for g(u), a(u), find estimates beyond the A_{1} and A_{2} terms for T_{1}(n, k) and T_{2}(n, k) that hold uniformly for u ≤ ϵ_{0}.

\begin{aligned}T_{1} & = e^{−v}(1 + \frac{A_{1}}{n^{1/2}} + O(u^{2}n^{−1})) \\ T_{2} & = e^{−g′}(1 + \frac{A_{2}}{n^{1/2}} + O(u^{−2}n^{−1})). \end{aligned}

Step 14. Rewrite the recursion of Step 11 using the known form of T_{1} + T_{2}. Since e^{−g′} = O(u^{2}), the two differential equations (2.1,2.2) imply that T_{1} + T_{2} = 1 + O(n^{−1}). Hence,

b(n, k) = O(n^{−1}) + T_{1} · b(n − k, k) + T_{2} · b(n, k − 1).

In view of the final two terms in the latter and the admonition of Step 12, we make the following calculation:

e^{−v}(1 + \frac{A_{1}}{n^{1/2}} + O(u^{2}n^{−1}))(1 + βk/n + O(k^{2}n^{−2}))

+ e^{−g′}(1 + \frac{A_{2}}{n^{1/2}} + O(u^{−2}n^{−1}))(1 − α/k + O(k^{−2}))

= 1 + \frac{βe^{−v}k}{n} − \frac{αe^{−g′}}{k} + O(n^{−1}).

Step 15. The difference αe^{−g′}/k − βe^{−v}k/n turns out to be crucial; determine a lower bound for small u by taking the first terms of the Taylor series:

αe^{−g′}/k − βe^{−v}k/n > \frac{α − β}{2} \frac{u}{n^{1/2}} for u ≤ ϵ_{0}.

This inequality is the defining property of ϵ_{0}.

Step 16. Determine conditions on α and β so that the inductive step in a proof

of hypothesis ≤^{?} goes through for sufficiently large C and k in the range n^{δ_{2}} ≤ k ≤ ϵ_{0}n^{1/2}:

\begin{aligned}|b(n, k)| & ≤ O(n^{−1}) + Ck^{α}/n^{β}(1 + \frac{βe^{−v}k}{n} − \frac{αe^{−g′}}{k} + O(n^{−1})) \\ & ≤^{?} Ck^{α}/n^{β}. \end{aligned}

Since 1/n = o(u), the induction goes through provided

\frac{1}{n} ≤ C \frac{k^{α}}{n^{β}} \frac{α − β}{3} \frac{u}{n^{1/2}} ,

for which it suffices

β ≤ (1 + α)δ_{2}, α > β

Large u

Steps 17 through 20 involve large u: ϵ_{0} ≤ u ≤ 25 log n. The value of ϵ_{0} is inherited from Step 15. The upper bound 25 log n is small enough that u = o(n^{1/2}), thus making approximations like the first in (3.1) still valid; and it is large enough to make Steps 21 and 22 easy. All big-oh assertions in Steps 17 through 20 are uniform for ϵ_{0} ≤ u ≤ 25 log n.

Step 17. Repeat Step 13 for large u:

\begin{aligned}T_{1} & = e^{−v}(1 + \frac{A_{1}}{n^{1/2}} + O(u^{4}n^{−1})) \\ T_{2} & = e^{−g′}(1 + \frac{A_{2}}{n^{1/2}} + O(u^{2}e^{−v}n^{−1})). \end{aligned}

Step 18. Repeat Step 14 for large u.

e^{−v}(1 + \frac{A_{1}}{n^{1/2}} + O(u^{4}n^{−1}))(1 + βk/n + O(k^{2}n^{−2}))

+ e^{−g′}(1 + \frac{A_{2}}{n^{1/2}} + O(u^{2}e^{−v}n^{−1}))(1 − α/k + O(k^{−2}))

= 1 + \frac{βe^{−v}k}{n} − \frac{αe^{−g′}}{k} + O(ue^{−v}n^{−1}).

Step 19. Find a positive lower bound for the crucial difference discussed in Step 15 holding when u ≥ ϵ_{0}.

αe^{−g′}/k − βe^{−v}k/n > c_{1}(α − β)/k,

where c_{1} is the minimum of 1 − e^{−v} for u ≥ ϵ_{0}.

Step 20. Find a condition on α, β, and C so that the induction step goes through for large u. We need to know for the range ϵ_{0}n^{1/2} ≤ k ≤ 25n^{1/2} log n that

\frac{ue^{−v}}{n} ≤ C \frac{k^{α}}{n^{β}} \frac{c_{1}(α − β)}{k};

for this it suffices to have

(1 − α)/2 < 1 − β, α > β

Step 21. Make a special argument for the range of extraordinarily large k; that is, k > 25n^{1/2} log n.

Step 22. Choose α and β subject to the accumulated restrictions so as to prove the best possible bound on b(n, k) of the form n^{−c}. Taking α slightly larger than 1/3, and β = 1/3, and again making a special argument for k > 25n^{1/2} log n, we obtain the result stated in the Theorem.

3 Details.

Within this part of the paper we’ll label our remarks as Comment 1, Comment 2, etc. to parallel the labeling of the Steps in the previous section.

Comment 1. This is a well known recursion, and here is a proof: (see [4, p. 96], for example) if a partition has fewer than k parts, then it is counted by P (n, k − 1); on the other hand, if it has exactly k strictly positive parts, then each part can be reduced by 1 and there results a partition counted by P (n − k, k).

Comment 2. This step requires creativity. In the problem under consideration, the number of partitions P (n, k), one can glean the correct form from Szekeres’ papers. In attacking a previously unsolved recursion, one might carry out Step 5 first, making an educated guess based on that. Presumably any incorrect assumptions will be exposed as frauds in later steps. Note that the function f(u) in the theorem appears at this point in logarithmic form: f = exp{a}.

Comment 3. This step involves calculating a number of Taylor expansions. For now we ignore error bounds and carry each expansion out to enough terms to find the differential equations in the next step. Later, in Comments 13 and 17, the quantity indicated by the ellipsis ⋯ in each equation must be filled in. (In Comment 13 we find suitable big-oh terms for the ⋯’s when u is restricted to be smaller than ϵ_{0}; in Comment 17 we do the same for large u.) First, for the term P (n − k, k),

k(n − k)^{−1/2} = u + (u^{2}/2n^{1/2} + 3u^{3}/8n + ⋯)
g(k(n − k)^{−1/2}) = g(u) + u^{2}g′(u)/2n^{1/2} + (3u^{3}g′(u) + u^{4}g′′(u))/8n + ⋯
a(k(n − k)^{−1/2}) = a(u) + u^{2}a′(u)/2n^{1/2} + ⋯
(n − k)^{1/2} = n^{1/2} − u/2 − u^{2}/8n^{1/2} + ⋯  (3.1)
n(n − k)^{−1} = 1 + k(n − k)^{−1} = exp{u/n^{1/2} + ⋯}
P (n − k, k) ≈ (n − k)^{−1} exp{(n − k)^{1/2}g(k(n − k)^{−1/2}) + a(k(n − k)^{−1/2})}
= n^{−1} exp{n^{1/2}g(u) + a(u)}

× e^{−v}(1 + \frac{−uv/4 + u^{4}g′′(u)/8 + u^{2}a′(u)/2 + u}{n^{1/2}} + ⋯).

Second, for the term P (n, k − 1), which is computationally simpler,

(k − 1)n^{−1/2} = u − n^{−1/2}
g((k − 1)n^{−1/2}) = g(u) − g′(u)/n^{1/2} + g′′(u)/2n + ⋯
a((k − 1)n^{−1/2}) = a(u) − a′(u)/n^{1/2} + ⋯  (3.2)
P (n, k − 1) ≈ n^{−1} exp{n^{1/2}g((k − 1)n^{−1/2}) + a((k − 1)n^{−1/2})}
= n^{−1} exp{n^{1/2}g(u) + a(u)}

× e^{−g′}(1 + \frac{g′′(u)/2 − a′(u)}{n^{1/2}} + ⋯).

¿From these we read off the formulas

A_{1} = −uv/4 + u^{4}g′′(u)/8 + u^{2}a′(u)/2 + u
A_{2} = g′′(u)/2 − a′(u).  (3.3)

Comment 4. Let us begin by computing all the derivatives we will need from here on. Assume that g,v, and a are given by (1.2), (1.3) and the logarithm of (1.1); then

v′ = v/u + \frac{uv/2}{e^{v} − 1 − u^{2}/2}
g′ = − log(1 − e^{−v})
g′′ = \frac{−v/u}{e^{v} − 1 − u^{2}/2}
g′′′ = \frac{(v/u)^{2}e^{v}(e^{v} − 1)}{(e^{v} − 1 − u^{2}/2)^{3}} − \frac{3v/2}{(e^{v} − 1 − u^{2}/2)^{2}}  (3.4)
a(u) = − log(2^{3/2}π) + log \frac{v}{u} − \frac{1}{2} log(1 − e^{−v}(1 + u^{2}/2))
a′(u) = \frac{u − v/2u − uv/4}{e^{v} − 1 − u^{2}/2} − \frac{u^{3}v/8 + uv/4}{(e^{v} − 1 − u^{2}/2)^{2}}

a′′(u) = ∑_{j=1}^{4} \frac{p_{j}}{(e^{v} − 1 − u^{2}/2)^{j}} , p_{j} = polynomial in u, v, u^{−1}.

In the last expression only p_{1} = 1 + v^{2}/4 − 3v/2 + v^{2}/2u^{2} will be needed explicitly. The calculation of g′ verifies relation (2.1). With A_{1} and A_{2} defined by (3.3), we want to check relation (2.2). Since only a′(u), and not a(u), enters into the latter relation, the function a(u) is determined by this relation only up to an additive constant. The value − log(2^{3/2}π) chosen above gives the right hand limit

a(0^{+}) = − log 2π,  (3.5)

which is needed later in Comment 7. Since each of A_{1}, A_{2}, e^{v}, and e^{−g′} = 1 − e^{−v} is a rational function of u, v, and e^{v}, verification of the relation (2.2) is reduced to some (albeit tedious) rational algebra in three variables.

Comment 5.We follow Erdös and Lehner [5] for this step. It is well known [4, p. 123] that the binomial coefficient \binom{n−1}{k−1} counts the number of integer k-tuples satisfying

n = x_{1} + ⋯ + x_{k}; x_{i} > 0,

because each such solution corresponds to choosing k − 1 out of the n − 1 gaps available when n dots are placed in a row. Such k-tuples differ from partitions in that the order of the summands counts; they are called compositions.

How many (n, k)-compositions contain a repeated part ? This was answered first in [5], and has been readdressed in later literature. The number in question is certainly bounded above by

\binom{k}{2} ∑_{h≥1} \binom{n − 2h − 1}{k − 3} ≤ \binom{k}{2} ∑_{h≥1} \binom{n − 2 − h}{k − 3}

= \binom{k}{2}\binom{n − 2}{k − 2}

= O(k^{3}/n)\binom{n − 1}{k − 1}.

The number of (n, k)-compositions with no repeated part is equal to k! times the number of partitions of n into k positive distinct parts. Reducing the smallest part by 1, the next smallest part by 2, etc., the latter number of partitions is seen to be P (n − \binom{k+1}{2}, k), and so

P (n − \binom{k + 1}{2}, k) = \frac{1}{k!}\binom{n − 1}{k − 1} exp\{O(k^{3}/n)\}.

The first equation in Step 5 follows, and the second is obtained by using

\binom{n − 1}{k − 1} = \frac{k}{n} \frac{n^{k}}{k!} exp\{O(k^{2}/n)\}

and Stirling’s formula.

Comment 6. No comment necessary.

Comment 7. We want estimates of g and a for small u. In Comment 13 we need similar estimates for the higher derivatives of these functions, so we record them all here. The big-oh terms are uniform for bounded u. The right side of the equation (1.3) is readily seen to be v + v^{2}/4 + O(v^{3}); this can be inverted to obtain

v = u^{2} − u^{4}/4 + O(u^{6}).

This and (3.4) lead to the formulas stated below for g and its derivatives. For a′′(u) a different argument is needed since our explicit formula is incomplete. By the Reversion Theorem and other standard results on real power series [10, Chapter 5, esp. Section 21] it follows that first v(u), then a(u) due to fortuitous cancelling among logarithmic terms, are represented by convergent power series in some interval (−η, +η) about u = 0. Given this, the assertions about a′ and a′′ follow from that about a.

g(u) = −2u log u + 2u + O(u^{3})
g′(u) = −2 log u + O(u^{2})
g′′(u) = −2/u + O(u)
g′′′(u) = 2/u^{2} + O(1)  (3.6)
a(u) = − log 2π + O(u^{4})
a′(u) = O(u^{3})
a′′(u) = O(u^{2}).

Again, these estimates are uniform for bounded u.

Comments 8 through 12. No comment necessary.

Recall that throughout Comments 13 through 16 we have u ≤ ϵ_{0}, and all big-oh assertions are uniform for that range.

Comment 13. Reexamining the definition in Step 11 of T_{1} and T_{2}, we see that what’s needed is to make modifications in the formal expansions of Step 3 so that the imprecise ≈ signs can be replaced with exact equalities =. This is accomplished by determining rigorous big-oh terms for the ellipses ⋯ in those expansions. Refer to the series of calculations (3.1). If we find suitable big-oh terms for the six ⋯’s appearing in that series of calculations, the final one is in fact the desired T_{1} formula. Likewise the three ⋯’s in (3.2) for T_{2}. All that’s needed is Taylor’s formula with remainder, which we state here in generic form:

G(u + Δu) = G(u) + ΔuG′(u) + \frac{1}{2}(Δu)^{2}G′′(u) + \frac{1}{6}(Δu)^{3}G′′(ξ),

with ξ between u and u + Δu. The latter is appropriate for the expression (n − k)^{1/2}g(k(n − k)^{−1/2}); for a(k(n − k)^{−1/2}) one less term suffices. Replacing Δu by u^{2}/2n^{1/2} + 3u^{3}/8n + O(u^{4}n^{−3/2}), using the bounds (3.6), and noting Δu = o(u) so that g′′′(ξ) = O(u^{−2}), we find that the first five ⋯’s in (3.1) can be filled in with, respectively: O(u^{4}n^{−3/2}), O(u^{4} log(u) n^{−3/2}), O(u^{3}n^{−1}), O(u^{3}n^{−1}), and O(u^{2}n^{−1}). These five combine algebraically to determine the sixth as the desired O(u^{2}n^{−1}). In like manner the three ellipses ⋯ in (3.2) may be filled in with O(u^{−2}n^{−3/2}), O(u^{2}n^{−1}), and O(u^{−2}n^{−1}).

Comment 14. The first assertion, about b(n, k), is immediate from the previous step. The second follows by straightforward algebra, using A_{1} = O(u) and A_{2} = O(u^{−1}) for the two products, and then the relations (2.1,2.2) to simplify the sum. The fact that e^{−g′} = O(u^{2}) is needed.

Comment 15. By (3.6) we have e^{−g′} = u^{2} + O(u^{4}), and by (2.1) e^{−v} = 1 + O(u^{2}); hence,

\begin{aligned}αe^{−g′}/k − βe^{−v}k/n & = (αe^{−g′}/u − βe^{−v}u)/n^{1/2} \\ & = (αu − βu + O(u^{3}))/n^{1/2}, \end{aligned}

which gives the desired lower bound if ϵ_{0} is set sufficiently small.

Comment 16. No comment necessary.

Recall that throughout Comments 17 through 20 we assume that u ≤ ϵ_{0}; further, all big-oh assertions are uniform for that range.

Comment 17. This step is completed in much the same manner as was Step 13. First we need the large u analog of the small u approximations appearing in (3.6). Observe that

∫_{0}^{∞} \frac{t}{e^{t} − 1}dt = \frac{π^{2}}{6} ,

as can be seen by expanding (e^{t} − 1)^{−1} as ∑_{m=1}^{∞} e^{−mt} and using the well known ∑_{m=1}^{∞} m^{−2} = π^{2}/6. By this we conclude from (1.3) that

\frac{v}{u} → π/6^{1/2} as u → ∞.  (3.7)

Thus for u ≥ ϵ_{0} the ratio v/u is confined to a closed interval [η, M], 0 < η < M < ∞. This plus formulas (1.2) and (3.4) suffice to prove

g = O(1), g′, g′′, g′′′ = O(e^{−v}), a′, a′′ = O(u^{2}e^{−v}).  (3.8)

Consider again the series of equations (3.1). Because Δu = O(u^{2}n^{−1/2}), it follows that v(ξ), the v-value corresponding to ξ, equals v(u)+o(1); hence, g′′′(ξ_{1}) = O(e^{−v}) and a′′(ξ_{2}) = O(u^{2}e^{−v}). We may then calculate that the proper substitutions for the six ellipses ⋯ appearing in (3.1), when u ≥ ϵ_{0}, are O(u^{4}n^{−3/2}), O(u^{6}e^{−v}n^{−3/2}), O(u^{6}e^{−v}n^{−1}), O(u^{3}n^{−1}), O(u^{2}n^{−1}), and O(u^{4}n^{−1}). In like manner the three ellipses appearing in (3.2) are filled in with O(u^{2}e^{−v}n^{−3/2}), O(u^{2}e^{−v}n^{−1}), and O(u^{2}e^{−v}n^{−1}).

Comment 18. This is similar to Step 14, and is straightforward using A_{1} = O(u^{2}), A_{2} = O(u^{2}e^{−v}).

Comment 19. Because t(e^{t} − 1)^{−1} is a decreasing function of t, we have

\frac{v^{2}}{u^{2}} = ∫_{0}^{v} \frac{t}{e^{t} − 1}dt ≥ v \frac{v}{e^{v} − 1} = \frac{v^{2}}{e^{v} − 1},

and so

e^{v} − 1 ≥ u^{2}.

Hence,

αe^{−g′}/k − βe^{−v}k/n = (αe^{−g′} − βe^{−v}u^{2})/k
≥ (α(1 − e^{−v}) − βe^{−v}(e^{v} − 1))/k
= (α − β)(1 − e^{−v})/k,

as needed.

Comment 20. No comment necessary.

Comments 21 and 22. Define k_{1}, u_{1} by

k_{1} = ⌊25n^{1/2} log n⌋, u_{1} = k_{1}/n^{1/2}.

The following lemma is the key to Steps 21 and 22.

Lemma. Assume 4 ≥ α − β > 0, and

|b(ν, k)| ≤ Ck^{α}/ν^{β} for ν < n or (ν = n and k ≤ k_{1}).

Then, uniformly for C ≥ 1 and k ≥ k_{1}

1 + b(n, k) = (1 + b(n, k_{1}))(1 + O(Cn^{−24}))

Proof. The desired result follows from

g(u) − g(u_{1}) = O(n^{−25}) for u > u_{1}  (i)
a(u) − a(u_{1}) = O(n^{−24}) for u > u_{1}  (ii)
P (n, k)/P (n, k_{1}) = 1 + O(Cn^{−24}) for n ≥ k > k_{1}.  (iii)

To see (i), recall (3.8) that g′(u) = O(e^{−v}), and (3.7) that v/u → π/6^{1/2} > 1. For the range of u under discussion e^{−v} = o(e^{−u}), and so

g(u) = g(u_{1}) + ∫_{u_{1}}^{u} g′(t)dt < g(u_{1}) + e^{−u_{1}} = g(u_{1}) + O(n^{−25}).

Relation (ii) is handled similarly. Since 1 + Cν^{α−β} ≤ 2Cν^{α−β} and g is increasing, we have

p(ν) = P (ν, ν) < c_{2}Cν^{α−β−1}e^{c_{3}\sqrt{ν}} for ν < n,

where

c_{2} = 2 max_{u} e^{a(u)}, c_{3} = lim_{u→∞} g(u) = π(2/3)^{1/2} > 5/2.

The above limit is determined by (3.7) and (1.2). Since P (n, k) increases with k, it suffices to prove (iii) for k = n. Using (n − k_{1})^{1/2} < n^{1/2} − 12 log n and c_{3} = g(u_{1}) + O(n^{−24}), we have for large n

P (n, n) − P (n, k_{1}) = ∑_{n≥k>k_{1}} P (n − k, k)
< (n − k_{1})p(n − k_{1})
< c_{2}C(n − k_{1})^{α−β}e^{c_{3}\sqrt{n−k_{1}}}
< Cn^{α−β−30}e^{c_{3}\sqrt{n}}
< Cn^{α−β−29} exp{n^{1/2}g(u_{1})}.

Dividing through by P (n, k_{1}) = n^{−1} exp{n^{1/2}g(u_{1}) + O(1)}, we obtain (iii). The proof of the lemma is complete.

To complete Step 21, use the Lemma and the known result on b(n, k_{1}) to find, for n ≥ k > k_{1},

|b(n, k)| ≤ |b(n, k_{1})| + O(Cn^{−24}) ≤ C(\frac{k_{1}^{α}}{n^{β}} + O(n^{−24})).

Collecting the conditions needed to prove the Lemma with conditions sufficient to prove the rightmost term above is ≤ C(k_{1} + 1)^{α}/n^{β}, we impose

C ≥ 1, 4 ≥ α − β > 0, β < 24 + min{0, (α − 1)/2}

We now turn to Step 22. Choosing α = 1/3 + ϵ, β = 1/3, δ_{2} = 1/4, and δ_{1} sufficiently close to δ_{2} satisfies the four accumulated constraints on α and β. Hence, |b(n, k)| ≤ Cn^{−1/6+ϵ/3} for n large and k ≤ k_{1} by the Ck^{α}/n^{β} bound. By the Lemma, we see that |b(n, k)| ≤ Cn^{−1/6+ϵ/4} for large n and all k. Since ϵ is arbitrary, the Theorem has been proved.

4 Conclusion. Hardy and Ramanujan gave a complete asymptotic expansion for p(n), and

Szekeres did the same for P (n, k). Later Rademacher extended earlier work to find a convergent sum for p(n). I do not know any of the later terms in Szekeres’ expansion explicitly, or any results concerning convergence of his expansion. It seems possible that the method described in this paper could produce at least one additional asymptotic term, but I have not done it.

As for the size of the overall relative error, O(n^{−1/6+ϵ}), improving on this requires starting the induction in the Erdös-Lehner range with something more accurate. For instance, if we show by a combinatorial argument more involved than the one in Comment 5 that

P (n, k) = \binom{n − 1}{k − 1} exp\{c_{4}k^{3}/n + O(k^{5}/n^{2})\}, k = O(n^{2/5}),  (4.1)

then our conclusion in Step 8 becomes

b(n, k) = O(k^{5}/n^{2} + 1/k), k = O(n^{2/5}),

and the first constraint on α and β in Step 10 improves to

β ≤ (1 + α)δ_{1}, (5 − α)δ_{2} ≤ 2 − β, δ_{1} < δ_{2} < 2/5.

The correct value of c_{4} in (4.1), by [13], is −1/4, but I do not have a combinatorial proof of this. Such a revised start to the induction improves the O(n^{−1/6+ϵ}) error to O(n^{−1/4+ϵ}). For any ϵ > 0, an overall error of O(n^{−1/2+ϵ}) can be achieved by a sufficiently accurate (hence increasingly complex) combinatorial argument at the start of the induction. To break the O(n^{−1/2}) barrior, however, requires introducing an additional term in the exponent of the guessed form, making it n^{1/2}g(u)+a(u)+ a_{1}(u)n^{−1/2}, as alluded to in the previous paragraph.

As shown by Szekeres [13], classical asymptotic formulas for p(n) and q(n) follow from the Theorem.

Corollary 1. (Hardy and Ramanujan [7]) Let p(n) be the number of partitions of n; for any ϵ > 0,

p(n) = \frac{1}{4 · 3^{1/2}n}e^{π\sqrt{2n/3}}(1 + O(n^{−1/6+ϵ})).

Proof. Using (3.7), (1.1), and (1.2)

g(u) → π(2/3)^{1/2}, f(u) → 1/4 · 3^{1/2}, as u → ∞.

This yields Corollary 1.

Corollary 2. (Hardy and Ramanujan [7]) Let q(n) be the number of partitions of n into distinct parts; for any ϵ > 0,

q(n) = \frac{1}{4 · 3^{1/4}n^{3/4}} e^{π\sqrt{n/3}}(1 + O(n^{−1/6+ϵ})).

Proof. Let q(n, k) be the number of partitions of n into k distinct parts. Since q(n, k) = P (n − \binom{k+1}{2}, k), we have uniformly for ϵ_{1}n^{1/2} ≤ k ≤ (2^{1/2} − ϵ_{1})n^{1/2}, (ϵ_{1} fixed)

q(n, k) = \frac{F (u)}{n} exp\{n^{1/2}G(u) + O(n^{−1/6+ϵ})\},

where

\begin{aligned}F (u) & = (1 − u^{2}/2)^{−1}f(u(1 − u^{2}/2)^{−1/2}) exp\{−\frac{1}{2}v_{∗}(u)\} \\ G(u) & = (1 − u^{2}/2)^{1/2}g(u(1 − u^{2}/2)^{−1/2}) \\ v_{∗}(u) & = v(u(1 − u^{2}/2)^{−1/2}). \end{aligned}

Let u_{0} satisfy the equation G′(u_{0}) = 0; then uniformly for t = O(n^{1/3})

q(n, u_{0}n^{1/2} + t) = \frac{F (u_{0})}{n} exp\{n^{1/2}G(u_{0}) + \frac{1}{2}t^{2}G′′(u_{0})n^{−1/2} + O(n^{−1/6+ϵ})\}.

By a standard argument in asymptotic methods ([11], 5.1), a key step of which is

∑_{|t|≤n^{1/3}} exp(\frac{1}{2}t^{2}G′′n^{−1/2}) = n^{1/4}(1+o(1)) ∫_{−∞}^{+∞} e^{G′′x^{2}/2}dx = n^{1/4}(−2π/G′′)^{1/2}(1+o(1)),

with a relative error o(1) much smaller than the O(n^{−1/6+ϵ}) precision which we are maintaining, one may show that terms q(n, k) with |k − u_{0}n^{1/2}| > n^{1/3} contribute insignificantly to ∑_{k} q(n, k) and conclude

q(n) = \frac{F (u_{0})}{n^{3/4}} \sqrt{\frac{2π}{−G′′(u_{0})}} exp\{n^{1/2}G(u_{0}) + O(n^{−1/6+ϵ})\}.

To obtain the corollary, one must evaluate u_{0}, G(u_{0}), F (u_{0}), and G′′(u_{0}), an intriguing exercise for aficionados of algebra and analysis. In the interest of bringing the paper to a close, we will just mention two highlights of the calculation. First, G′(u) has a nice form:

G′(u) = −v_{∗}(u) − log(1 − e^{−v_{∗}(u)}).

Hence, to make G′ vanish we need

v_{∗}(u_{0}) = log 2.

Determining u_{0} requires (see [1], 27.7.7 and 27.7.3)

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

Cited Publications

1. M. Abramowitz and I. Stegun, Handbook of Mathematical Functions, Dover, 1973.

2. E. A. Bender, E. R. Canfield, and B. D. McKay, The asymptotic number of labeled connected graphs with a given number of vertices and edges, Random Structues and Algorithms 1 (1990) 127–169.

3. E. A. Bender, E. R. Canfield, and B. D. McKay, The asymptotic number of labeled graphs with n vertices, q edges, and no isolated vertices, preprint.

4. L. Comtet, Advanced Combinatorics, D. Reidel, 1974.

5. P. Erdös and J. Lehner, The distribution of the number of summands in the partitions of a positive integer, Duke Math. J. 8 (1941) 335–345.

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

7. G. G. Hardy and S. Ramanujan, Asymptotic formulae in combinatory analysis, J. London Math. Society 17 (1918) 75–115.

8. C. Knessl and J. B. Keller, Partition asymptotics for recursion equations, SIAM J. Appl. Math. 50 (1990) 323–338.

9. C. Knessl and J. B. Keller, Stirling number asymptotics from recursion equations using the ray method, Studia Appl. Math. 84 (1991) 43–56.

10. K. Knopp, Theory and Application of Infinite Series, Dover, 1990.

11. A. M. Odlyzko, Asymptotic enumeration methods, in Handbook of Combinatorics, volume II (R. L. Graham, M. Grötschel, and L. Lovász, eds.), Elsevier, 1995, pages 1063–1229.

12. G. Szekeres, An asymptotic formula in the theory of partitions, Quart. J. of Math. (Oxford) (2) 2 (1951) 85–108.

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