ON ELEMENTARY LOWER BOUNDS FOR THE PARTITION FUNCTION

Attila Maróti^{1}

School of Mathematics and Statistics, University of Birmingham, Birmingham B15 2TT, United

Kingdom

                        marotia@maths.bham.ac.uk

Received: 1/8/03, Revised: 7/22/03, Accepted: 7/30/03, Published: 7/31/03

Abstract

We present two analogues of two well-known elementary arguments for a lower bound for p(n), the number of partitions of the integer n. One of these is character-theoretic, and the other relies on partition combinatorics developed and used in the theory of representations of the symmetric group. We show that these arguments provide better lower estimates. We also give an application.

1. Introduction

Although the asymptotic

\frac{e^{2\sqrt{π^{2}/6}\sqrt{n}}}{4n\sqrt{3}} ,

or even an exact formula for p(n), the number of partitions of the integer n, is long known, good, explicit estimates for the partition function are not at all straightforward (for non-specialists) from the works of Hardy, Ramanujan, Uspensky and Rademacher. Elementary and analytic proofs for the asymptotic formula (see [2], ([7]), [10], [3], [1]) indicate that sharp universal upper bounds for p(n) (holding for all n) are more natural than lower ones. Indeed, the partition function is relatively small compared to its asymptotic formula (above) at small integer values.

There are two elementary arguments to estimate p(n) from below: counting partitions by parts, and counting partitions with parts of bounded lengths. In this note, we present two analogues of these arguments.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 3 (2003), #A10 2

In particular, motivated by a group-theoretic application, to prove that the number of conjugacy classes of a primitive permutation group of degree n is at most p(n) (see [6]), we state explicit lower bounds for p(n) (holding for all n) which - we believe - are sharper than any other lower estimate available in the literature (see Corollary 2.1 with Remark (ii), Corollary 3.1 and Theorem 4.2). We note here that though the papers of Erdős [2] and Newman [7] give an elementary proof of the aymptotic expression for p(n) starting from a simple, well-known recursion formula, their (accurate) lower bounds are quite implicit and valid only for sufficiently large n. On the other hand, in the case of our second method, it is not known whether the asymptotic formula for p(n) is a direct consequence - in the spirit of Erdős and Newman - of Osima’s recursion formula (see Theorem 4.1).

1Research partially supported by the Hungarian National Foundation for Scientific Research Grant T034878.

Finally, as an application of our second method, we give a lower bound for the number of certain partitions of n which are interesting in the modular representation theory of the symmetric group.

2. Counting involutions

Let G be any finite group of even order, and let I(G) denote the set of elements of order 2 (that is, involutions), of G. It is well known that we have

1 + |I(G)| = ∑_{χ∈Irr(G)} ν(χ)χ(1),

where Irr(G) denotes the set of complex irreducible characters of G, and for χ ∈ Irr(G), ν(χ) denotes the Frobenius-Schur indicator of χ, which is 0 if χ is not real-valued, 1 if χ may be afforded by a real representation, −1 if χ may not be afforded by a real representation.

Using the Cauchy-Schwarz inequality, we deduce that |I(G)| < \sqrt{r(G)}\sqrt{|G|}, where r(G) is the number of irreducible characters of G which may be afforded by real representations. In particular, \frac{|I(G)|^{2}}{|G|} < k(G), where k(G) is the number of conjugacy classes of G (and k(G) is also the number of complex irreducible characters of G).

We summarize this in the following.

Theorem 2.1. Let G be a finite group and t ∈ G be an arbitrary element of order 2. We have

\frac{|G|}{|C_{G}(t)|^{2}} < k(G),

where C_{G}(t) is the centralizer of t in G and k(G) is the number of conjugacy classes of G.

Note that the dihedral groups show that the above estimate for k(G) is sharp apart from a constant factor, and that the symmetric groups show that the involution, t in the Theorem may not be replaced in general by any other element of order different than 2.

So what kind of lower bound does this argument give us for k(S_{n}) = p(n) in the special case of the symmetric group?

Corollary 2.1. We have

\frac{e^{2\sqrt{n}}}{cn} < p(n)

for some constant c.

Proof. We have

p(n) = k(S_{n}) > \frac{|I(S_{n})|^{2}}{n!} = \frac{(∑_{t=1}^{[n/2]} f(n, t))^{2}}{n!} > ∑_{t=1}^{[n/2]} \frac{f(n, t)^{2}}{n!} ,

where f(n, t) = \frac{n!}{2^{t}t!(n−2t)!} is the number of involutions in S_{n} which are products of t disjoint transpositions. Now

\frac{f(n, t)}{f(n, t + 1)} = \frac{2(t + 1)}{(n − 2t)(n − 2t − 1)},

so we see easily that for a fixed n, we have f(n, t) ≤ f(n, t+1) precisely when (n−2t)^{2} ≥ n+2. Hence the largest value of f(n, t) for n fixed and t in the range of [1, [n/2]] is taken by t_{0} = ⌊\frac{(n+2)−\sqrt{n+2}}{2}⌋. Finally, by an elementary argument using Stirling’s formula it may be shown that \frac{f(n,t_{0})^{2}}{n!} is of the desired form. □

Remarks. (i) The fact that we concentrated on just a single contribution does not significantly affect the general nature of the lower bound (even if all the f(n, t) were roughly equal, we would multiply by a factor of around \frac{n^{2}}{4} , but the f(n, t)’s decrease quickly as t moves away from t_{0}).

(ii) A more careful argument shows that the constant, c in Corollary 2.1 may be taken to be e^{3}\sqrt{2π^{3}}.

(iii) There is a combinatorial interpretation of the idea of the proof of Corollary 2.1 by means of the Robinson - Schensted algorithm. Indeed, the algorithm (see Chapter 3 of [9]) provides a bijection between elements of S_{n} and pairs of standard tableaux of the same shape. In particular, it gives n! = ∑_{λ⊢n} a_{λ}^{2} where a_{λ} denotes the number of standard tableaux of shape λ ⊢ n. A closer look at the algorithm shows that elements of order dividing 2 are in correspondence with pairs of tableaux with identical entries. Hence we also have 1 + |I(S_{n})| = ∑_{λ⊢n} a_{λ}. Now apply the inequality between the arithmetic and the quadratic means for the a_{λ}’s.

(iv) One might wonder why this estimate is close to the general nature of p(n)? A possible answer is that “almost all” irreducible character degrees of the symmetric group are “roughly” equal.

The above argument is similar to that of counting partitions by parts, however the character theory provides an even better lower estimate for the partition function. This will be shown in the rest of this section.

There are at least g(n, k) = \frac{1}{k!} \binom{n−1}{k−1} partitions of n with exactly k parts, so we have ∑_{k=1}^{n} g(n, k) ≤ p(n). Notice that for fixed n, the g(n,k)’s increase in the interval [1, \sqrt{1 + n} − 1) and decrease in the interval [\sqrt{1 + n} − 1, n]. By Wallis’s formula we see that

\frac{f(n, t)^{2}}{n!} ∼ \frac{1}{\sqrt{(\frac{π}{2})(2t + 1)}} · \frac{1}{(n − 2t)!}\binom{n}{n − 2t}

as both t and (t <<)n tend to infinity. For k ≡ n mod (2) define the function

G(n, k) = \frac{n! · (g(k − 1) + g(k))}{f(n, (n − k)/2)^{2}}.

There exists an irrational number 0 < c < 1 and an integer N_{1} such that if n > N_{1}, then G(n, k) < \sqrt[3]{7/6}\sqrt{2π} for all k in the interval ((1 − c)\sqrt{n} − 1, (1 + c)\sqrt{n} + 1) and that [(1−c)\sqrt{n}] ≡ n mod (2). Now choose ϵ to be 0 or 1 such that [(1+c)\sqrt{n}+ϵ] ≡ n mod (2). Put c_{1} = [(1−c)\sqrt{n}+1] and c_{2} = [(1+c)\sqrt{n}+ϵ] for convenience. Now choose an integer, N_{2} such that if n > N_{2}, then

∑_{k=1}^{n} g(n, k) < \sqrt[3]{7/6} ∑_{k=c_{1}}^{c_{2}} g(n, k).

There are l = \frac{c_{2}−c_{1}+1}{2} number of integers k in the interval [c_{1}, c_{2}] congruent to n modulo 2. For each such k we have an integer t = \frac{n−k}{2}. Label these l number of t’s with subscripts 1 through l such that f(n, t_{1}) < … < f(n, t_{l}). (Note that the t_{i}’s implicitly depend on n. When we write f(n, t_{i}), we really mean f(n, t_{i}(n).) Choose an integer N_{3} such that whenever n > N_{3}, then l > 3 and f(n, t_{l}) < \sqrt[3]{7/6} · f(n, t_{l−3}) follow. Put N = max {N_{1}, N_{2}, N_{3}}. If n > N, we have

\sqrt[3]{7/6} ∑_{k=c_{1}}^{c_{2}} g(n, k) < (\sqrt[3]{7/6})^{2}\sqrt{2π} ∑_{i=1}^{l} \frac{f(n, t_{i})^{2}}{n!} <

< \frac{(7/6)\sqrt{2π}}{3} \frac{(∑_{i=1}^{l} f(n, t_{i}))^{2}}{n!} < \frac{(∑_{t=1}^{[n/2]} f(n, t))^{2}}{n!} .

So indeed, the above argument produces a better lower bound for p(n).

3. Counting characters in the principal block

It is well-known that the (complex) irreducible characters of the symmetric group, S_{n} are labelled canonically by partitions of n. So if λ is a partition of n, denote the corresponding (complex) irreducible character of S_{n} by χ_{λ}.

Now fix an integer d > 1. For each partition λ of n we may define a d-core, γ_{λ} and a d-quotient, β_{λ} as in section 2.7 of [5]. The d-core is obtained from λ by removing all d-hooks from λ. The number of d-hooks to be removed from λ to go to the core is called the d-weight of λ and is denoted by w_{λ}. The quotient β_{λ} is a d-tuple of partitions whose cardinalities add up to w_{λ}. It is known that β_{λ} and γ_{λ} determine λ uniquely. A combinatorial d-block is a non-empty subset, B of Irr(S_{n}) with the property that the set of all partitions labelling the characters in B is precisely the set of partitions having a fixed d-core. The principal combinatorial d-block is the block which contains the trivial character of S_{n}, the one labelled by the partition (1^{n}), that is the partition with all parts being 1.

Nakayama’s conjecture (which is already a theorem) states that for any prime p, the combinatorial p-blocks of S_{n} are precisely the usual p-blocks of modular representation theory. Recently, it was proved in [4] that for each integer d > 1 the combinatorial dblocks coincide with the block-theoretic C-blocks where C is a certain union of (naturally defined) conjugacy classes of S_{n}. Loosly speaking, Nakayama’s conjecture is generalized for arbitrary integers, d > 1. This allows us to talk about just d-blocks rather than combinatorial d-blocks.

In this present work we will only need (and use) the basic combinatorics associated with partitions described above. (This is why our method will be elementary.) However, it is important to note that everything may be set in a wider and more natural blocktheoretic context.

Let us continue with an observation.

Theorem 3.1. For all positive integers d ≤ n we have p([n/d^{2}])^{d} ≤ p(n).

Proof. This is obvious for d = 1. So suppose that d > 1. The principal d-block has

∑_{w_{1},w_{2},...,w_{d}} p(w_{1})p(w_{2})...p(w_{d})

number of irreducible characters with different d-quotients of partitions labelling them where the w_{i}’s are nonnegative integers satisfying w_{1} +w_{2} +...+w_{d} = [n/d]. This number is at least p([n/d^{2}])^{d}. □

If d = [\sqrt{n/2}], then Theorem 3.1 gives the estimate 2^{[\sqrt{n/2}]} ≤ p(n), which is similar to saying that there are at least 2^{[\sqrt{n/2}]} partitions of n with parts not exceeding [\sqrt{n/2}]. By counting partitions with parts of bounded lengths one can not easily do better than 2^{\sqrt{2n}}/c < p(n) where c is a constant. However Theorem 3.1 suggests more.

Corollary 3.1. For all integers n we have

\frac{e^{2\sqrt{n}}}{14} < p(n).

Proof. For integers n < 190 this may be checked by computer. Similarly, if 190 ≤ n < 760, then it is checked that e^{2(\sqrt{n}+0.25)} < p(n) holds. Finally, if n ≥ 760, then by Theorem 3.1 and by induction, we have

p(n) > p([[n/2]/2])^{2} > e^{4(\sqrt{[[n/2]/2]}+0.25)} > e^{2(\sqrt{n}+0.25)}.
□

Remark. The estimate of Corollary 3.1 is better than the one noted in remark (ii) of Corollary 2.1. However, in the previous proof we had to check all values of p(n) for n no greater than 760 to start the induction, while in our other method we only have to know the values of p(n) for integers less than 110.

Notice that this lower bound may considerably be sharpened provided that we have a good computer. Theoretically, Theorems 3.1 with the idea in the proof of Corollary 3.1 gives a method to set an \frac{e^{(c_{0}−ϵ)\sqrt{n}}}{A(ϵ)} < p(n)-type lower bound for any given ϵ where A(ϵ) is some constant depending on ϵ and where c_{0} = 2\sqrt{π^{2}/6} ∼ 2.56.... We demonstrate this in the following example.

Example. Since e^{2.5·10^{3}} < p(10^{6}), applying Theorem 3.1 for d = 10, we see that there exists a computable constant c, such that \frac{e^{2.5\sqrt{n}}}{c} < p(n) for all 10-powers, n.

4. A sharp lower bound

The example above shows that it is hard to set a universal \frac{e^{2.5·\sqrt{n}}}{cn} -type lower bound for p(n) by only relying on Theorem 3.1. In this section we present a recursion formula (see Theorem 3 of [8]) for p(n) with which we are able to give such a lower estimate.

Theorem 4.1. For all integers n we have

p(n) = ∑_{t=0}^{n}_{n ; ∑_{w=0} ; 4w+t(t+1)=2n} ∑_{l=0}^{w} p(l)p(w − l).

Note that all l and m − l appearing in the above Theorem are at most [n/2].

Proof. Recall that each 2-block of S_{n} is uniquely determined by a certain 2-core. Moreover, by section 2.7 of [5], a partition of n is uniquely determined by its 2-core and its 2-quotient, and each “possible” pair consisting of a 2-core and a 2-quotient determines a partition. So we may label each 2-block, B of the symmetric group, S_{n} by some integer, t congruent to n modulo 2 with t(t + 1)/2 ≤ n such that the 2-core corresponding to the block B is a partition of the integer t(t + 1)/2. It is easy to see that this correspondence is one to one between the set of 2-blocks of S_{n} and the set of integers t congruent to n modulo 2 with t(t + 1)/2 ≤ n. Finally, for a given t, the expression on the right hand side of the equality without the first sum is exactly the number of irreducible characters in the 2-block of S_{n} corresponding to the integer t. □

Before we state the main theorem of this section, observe that the function f(x) = \frac{e^{2.5·\sqrt{x}}}{\sqrt{x}} defined for all real numbers x > 1 is monotone increasing. Moreover define the function p′(x) on all real numbers x > 1 by putting p′(x) := p(x) whenever x is an integer and by p′(x) := f(x) otherwise.

Theorem 4.2. For all integers n we have

\frac{e^{2.5·\sqrt{n}}}{13n} < p(n).

Proof. This is true for integers n < 11000. One can also check by computer that if 11000 ≤ n < 45000, then f(x) < p(n). So let us suppose that n ≥ 45000. Count all ordered pairs of integers (l, w − l) in the recursion formula in Theorem 4.1 for which \frac{n}{2} − \frac{1}{4} \sqrt{n} ≤ w ≤ \frac{n}{2} and for which both l and w − l is not less than \frac{n−\sqrt{n}}{4}. There are less than

g(n) := 2 · (\frac{1}{8}\sqrt{n} − 2) · \frac{\sqrt{2}}{4} · n^{0.25}

such ordered pairs. So by Theorem 4.1, we have p(n) > g(n) · p′((n − \sqrt{n})/4)^{2}. To finish the proof, it is sufficient to show that g(n) · p′((n − \sqrt{n})/4)^{2} > f(n), that is, to show

\frac{n − 16\sqrt{n}}{n − \sqrt{n}} · \frac{\sqrt{2}}{4} · n^{0.25} > e^{2.5(\sqrt{n}−\sqrt{n−\sqrt{n}})}.

Since the right-hand side of the previous inequality is less than e^{1.25}, it is sufficient to see

\frac{n − 16\sqrt{n}}{n − \sqrt{n}} · \frac{\sqrt{2}}{4} · n^{0.25} > e^{1.25}.

But this is clearly true for n ≥ 45000. □

5. An application

Euler showed that the number of partitions of n with different parts is equal to the number of partitions of n with odd parts. This was generalized in 1883 by Glaisher.

Proposition 5.1. Fix any positive integer d. The number of partitions of n not containing d equal parts is equal to the number of partitions of n with no part divisible by d.

Denote this common number by p_{d}^{∗}(n). By Proposition 5.2 of [4] and by Theorem 4.2 we are able to give good lower bounds for the p_{d}^{∗}(n)’s.

Theorem 5.1. For all integers d > 1 and n ≥ d^{2}, we have

(\frac{d(d − 1)}{160n})^{\sqrt{d}} · e^{2.5·\sqrt{(1−1/d)n}} < p_{d}^{∗}(n).

Proof. By Theorem 6.2.2 of [5] and by the proof of Theorem 3.1, we see that p([[n/d]/(d− 1)])^{d−1} ≤ p_{d}^{∗}(n). Using Theorem 4.2 to estimate the left hand side of the previous inequality we get

p_{d}^{∗}(n) · (d(d − 1))^{−d} > \frac{e^{2.5·(d−1)\sqrt{(n−d)/(d(d−1))−1}}}{(13n)^{d}} = \frac{e^{2.5·\sqrt{(1−1/d)n−(d−1/2)^{2}}}}{(13n)^{d}} .

Since n ≥ d^{2}, we conclude that

\frac{e^{2.5·\sqrt{(1−1/d)n−(d−1/2)^{2}}}}{(13n)^{d}} > \frac{e^{2.5·\sqrt{(1−1/d)n}−(d−1/2)}}{(13n)^{d}} > \frac{e^{2.5·\sqrt{(1−1/d)n}}}{(160n)^{d}} .

□

By Theorem 6.2.2 of [5] and by Theorem 4.1, we find a recursion formula for p_{2}^{∗}(n).

Theorem 5.2. The number of partitions of n with different parts, and the number of partitions of n with odd parts is equal to

∑_{t=0}^{n}_{n ; ∑_{m=0} ; 4m+t(t+1)=2n}p(m).

The number of partitions of n with different odd parts is equal to the number of self-conjugated partitions of n. Denote this number by u(n). Theorem 4 of [8] is the following.

Theorem 5.3. For a given integer n, let s_{i} (i = 1, …, q) be all of the non-negative integer solutions of the equations n − 4s = \frac{1}{2}k(k + 1) (k = 0, 1, …). Then

u(n) = ∑_{i=1}^{q} p(s_{i}).

In particular, we have p(s_{j}) < u(n) where s_{j} is the largest number among the s_{i}’s. Bt the use of Theorem 4.2, this observation allows us to give an even sharper bound than the one in Theorem 5.1 in the special case of d = 2.

Theorem 5.4. If n > 10, then we have

\frac{e^{1.25\sqrt{n−6}}}{4(n − 6)} < u(n) < p_{2}^{∗}(n).

Acknowledgements

The use of character theory in Section 2 was suggested to me by G. R. Robinson, who I thank most heartily.

References

[1] Apostol, T. M. Introduction to analytic number theory. Undergraduate Texts in Mathematics. Springer-Verlag, New York-Heidelberg, (1976).

[2] Erdős, P. On an elementary proof of some asymptotic formulas in the theory of partitions. Ann. of Math. (2) 43 (1942), 437–450.

[3] Knopp, M. I. Modular functions in analytic number theory. Markham Publishing Co., Chicago, Ill. (1970).

[4] Külshammer, B; Olsson, J. B; Robinson, G. R. Generalized blocks for symmetric groups, Invent. Math. 151 (2003), no. 3, 513–552.

[5] James, G; Kerber, A. The representation theory of the symmetric group. Encyclopedia of Mathematics and its Applications 16 (1981).

[6] Maróti, A. Bounding the number of conjugacy classes of a permutation group, submitted.

[7] Newman, D. J. The evaluation of the constant in the formula for the number of partitions of n. Amer. J. Math. 73, (1951). 599-601.

[8] Osima, M. On the irreducible representations of the symmetric group. Canadian J. Math. 4 (1952). 381–384.

[9] Sagan, B. E. The symmetric group. Representations, combinatorial algorithms, and symmetric functions. Second edition. Graduate Texts in Mathematics, 203, Springer-Verlag, New York, 2001.

[10] van Lint, J. H. Combinatorial Theory Seminar, Lecture Notes in Mathematics, Vol. 382. Springer-Verlag, Berlin-New York, (1974).