Integer Partitions and Convexity

Sadek Bouroubi USTHB Faculty of Mathematics Department of Operational Research Laboratory LAID3 P. O. Box 32 16111 El-Alia Bab-Ezzouar, Algiers Algeria

                      sbouroubi@usthb.dz
                      bouroubis@yahoo.fr

Abstract Let n be an integer ≥ 1, and let p(n, k) and P (n, k) count the number of partitions of n into k parts, and the number of partitions of n into parts less than or equal to k, respectively. In this paper, we show that these functions are convex. The result includes the actual value of the constant of Bateman and Erdős.

1 Introduction

The k^{th} difference Δ^{k}f of any function f of the nonnegative integers is defined recursively by Δ^{k}f = Δ(Δ^{k−1}f), with Δf(n) = f(n) − f(n − 1) for n ≥ 1 and Δf(0) = f(0). Good [5] studied the behavior of Δ^{k}p(n), where p(n) denotes the total number of partitions of n. He initially conjectured [5] that if k > 3, then the sequence Δ^{k}p(n), n ≥ 0 alternates in sign. However, computations by Razen, and, independently, by Good [5], found counterexamples to this conjecture, and led to a new conjecture, namely that Δ^{k}p(n) > 0 for each fixed k. Good [5] even made a stronger conjecture that for each k, there is an n_{0}(k) such that Δ^{k}p(n) alternates in sign for n < n_{0}(k), and Δ^{k}p(n) ≥ 0 for n ≥ n_{0}(k). He also suggested that 6(k − 1)(k − 2) + k^{3}/2 might be a good approximation to n_{0}(k). Some further computations by Gaskin led Good to revise his conjecture about the size of n_{0}(k), and suggest that πk^{5/2} might be a good approximation to it [6].

At about the same time as the first publication of Good’s problem, the same question about the sign of Δ^{k}p(n) was also raised independently by Andrews, and was answered by Gupta [7]. Gupta noted that Δp(n) > 0 for all n, and gave a simple proof of the result that Δ^{2}p(n) ≥ 0 for n ≥ 2, while Δ^{2}p(0) = 1, Δ^{2}p(1) = −1; in other words, he showed that the function p(n) is convex for n ≥ 2.

Another easy proof that Δ^{k}p(n) is positive for large n can be obtained by applying the result of the theorem of Beteman and Erdős [2]. They showed that if p(A, n) is the number of partitions of n into parts taken from A ⊂ {1, 2, 3, …}, then Δ^{k}p(A, n) ≥ 0 for all n large enough iff the greatest common divisor of each subset B ⊆ A with | A \ B |= k is equal to 1. In particular, the theorem of Beteman and Erdős asserts that there is n_{0} = n_{0}(A) such that the function p(A, n) is convex for n ≥ n_{0} iff for all pairs {a, b} of A, gcd(A \ {a, b}) = 1.

For more historical details see [8]. The aim of this paper is to give the actual form of this result when A = {1, 2, …, k}.

2 Definitions and notation

A partition of an integer n into k parts (1 ≤ k ≤ n) is an integer solution of the system:

\{ \begin{matrix}n = a_{1} + 2a_{2} + ⋯ + na_{n}, \\ k = a_{1} + a_{2} + ⋯ + a_{n}, \\ a_{i} ≥ 0, i = 1, …, n, \end{matrix}  (1)

where a_{i} counts the number of parts i.

Thus, a partition of n into parts less than or equal to k is an integer solution of the following system:

{ n = a_{1} + 2a_{2} + ⋯ + ka_{k}, a_{i} ≥ 0, i = 1, …, k.  (2)

Let p(n), p(n, k) and P (n, k) be respectively the total number of partitions of n, the number of partitions of n into exactly k parts and the number of partitions of n into parts less than or equal to k. According to Bouroubi [3] and Comtet [4], we have

p(n) = P (n, n),  (3)

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

p(n, k) = P (n − k, k),  (5)

and

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

3 Convexity of the functions (P (n, k))_{n} and (p(n, k))_{n}

Theorem 1. The function P (n, k) is convex for n ≥ 2 and k ≥ 7.

Proof. Setting,

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

First we note that if n ≤ k then

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

From (3), we get γ(n, k) = p(n) + p(n − 2) − 2p(n − 1) > 0. Suppose now n > k, since γ(7, 6) = γ(13, 6) = −1, let us show by mathematical induction on k that γ(n, k) is positive for every n, n > k ≥ 7. For that we consider g_{k} the generating function of P (n, k) [4], i.e.,

g_{k}(z) = \frac{1}{(1 − z) ⋯ (1 − z^{k})}, | z |< 1.

Thus, the generating function of γ(n, k) equals

h_{k}(z) = \frac{(1 − z)^{2}}{∏_{i=1}^{k}(1 − z^{i})}·

Hence

h_{k}(z) = \frac{1}{1 − z^{k}} h_{k−1}(z).

Consequently

γ(n, k) = ∑_{j=0}^{n} α(j, k) γ(n − j, k − 1),

where α(j, k) = 1 if k divides j and α(j, k) = 0 otherwise.

Now let us show that γ(n, 7) ≥ 0 for every n ≥ 8. By the decomposition of the rational function of h_{7}(z) into partial fractions, we get

h_{7}(z) = \frac{1}{5040} \frac{1}{(1−z)^{5}} + \frac{1}{480} \frac{1}{(1−z)^{4}} + \frac{47}{4320} \frac{1}{(1−z)^{3}} + \frac{161}{4320} \frac{1}{(1−z)^{2}} + \frac{16051}{172800} \frac{1}{1−z}+
+\frac{1}{192} \frac{1}{(1+z)^{3}} + \frac{23}{384} \frac{1}{(1+z)^{2}} + \frac{713}{2304} \frac{1}{1+z} + \frac{1}{7} \frac{(1−z)^{2}}{1−z^{7}} + \frac{1}{108} \frac{(21−2z)(1−z)}{1−z^{3}}+
+\frac{1}{54} \frac{(2+z)(1−z)^{2}}{(1−z^{3})^{2}} + \frac{1}{36} \frac{(1−2z)(1+z)}{1+z^{3}} + \frac{1}{25} \frac{(2−z+z^{2}−2z^{3})(1−z)}{1−z^{5}} − \frac{1}{16} \frac{z}{1+z^{2}} ·

By taking lower bounds of each of the coefficients of z^{n} for the power series expansions of the above functions we find:

γ(n, 7) ≥ \frac{1}{5040} (\frac{1}{24}n^{4} + \frac{5}{12}n^{3} + \frac{35}{24}n^{2} + \frac{25}{12}n + 1) + \frac{1}{480} (\frac{1}{6}n^{3} + n^{2} + \frac{11}{6}n + 1) +
+\frac{47}{4320} (\frac{1}{2}n^{2} + \frac{3}{2}n + 1) + \frac{161}{4320}(n + 1) + \frac{16051}{172800} − \frac{1}{192}(\frac{1}{2}n^{2} + \frac{3}{2}n + 1)−
−\frac{23}{384}(n + 1) − \frac{713}{2304} − \frac{2}{7} − \frac{23}{108} − \frac{1}{54}(n + 2) − \frac{1}{18} + \frac{2}{25} + \frac{1}{16}·

i.e.,

γ(n, 7) ≥ \frac{1}{120960}n^{4} + \frac{13}{30240}n^{3} + \frac{1}{192}n^{2} − \frac{859}{30240}n − \frac{16451}{24192}
= 0.8267195767 10^{−5} × (n + 30.63520805) × (n − 9.699836835)
× (n^{2} + 31.064628784 n + 276.8069841)·

Hence

γ(n, 7) ≥ 0, ∀n ≥ 10.

For n ∈ {8, 9}, we have

γ(8, 7) = 2 ; γ(9, 7) = 1.

Suppose now that γ(n, j) ≥ 0, for 7 ≤ j ≤ k − 1 and show that γ(n, k) ≥ 0.

On the one hand, we have

\begin{aligned}γ(n, k) & = & α(n, k) − α(n − 1, k) + α(n − k − 1, k) γ(k + 1, k − 1) + \\ & + & ∑_{j=0:j≠n−k−1}^{n−2} α(j, k) γ(n − j, k − 1). \end{aligned}

Hence by the induction assumption, we get

γ(n, k) ≥ α(n, k) − α(n − 1, k) + α(n − k − 1, k) γ(k + 1, k − 1).

On the other hand from (6), we have

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

Therefore

γ(k + 1, k − 1) = γ(k + 1, k − 2) + γ(2, k − 1) = 1 + γ(k + 1, k − 2).

- if k − 2 ≥ 7 then γ(k + 1, k − 2) ≥ 0, by the induction assumption.

- if k − 2 = 6 then γ(k + 1, k − 2) = γ(9, 6) = 0.

Consequently

γ(n, k) ≥ α(n, k) − α(n − 1, k) + α(n − k − 1, k) ≥ 0.

Indeed - if k divides n then α(n, k) − α(n − 1, k) + α(n − k − 1, k) = 1,

- if k divides n − 1 then α(n, k) − α(n − 1, k) + α(n − k − 1, k) = 0,

- if k divides neither n nor n − 1 then α(n, k) − α(n − 1, k) + α(n − k − 1, k) = 0.

Corollary 2. The function p(n, k) is convex for n ≥ k + 2 and k ≥ 7.

Proof. Using (5), we have

p(n, k) + p(n − 2, k) − 2p(n − 1, k) = P (n − k, k) + P (n − k − 2, k) − 2P (n − k − 1, k),

and the result follows immediately, using Theorem 1.

Remark 3. Using the same method we can show that the function P (n, 5) and P (n, 6) are convex for n ≥ 2 and n ≥ 14 respectively. We give below the value of γ(n, 5) and γ(n, 6), for 0 ≤ n ≤ 20.

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\ γ(n, 5) & 1 & -1 & 1 & 0 & 1 & 0 & 1 & 0 & 2 & 0 & 2 & 0 & 3 & 2 & 3 & 1 & 3 & 1 & 4 & 1 & 5 \\ γ(n, 6) & 1 & -1 & 1 & 0 & 1 & 0 & 2 & -1 & 3 & 0 & 3 & 0 & 5 & -1 & 6 & 1 & 6 & 1 & 9 & 0 & 11 \end{matrix}

Table 1: The value of γ(n, 5) and γ(n, 6), for 0 ≤ n ≤ 20.

4 Conclusion

Let A = {1, 2, …, k}, k ≥ 2. In this paper we showed that the partition function P (A, n) is convex for k ≥ 5 and the constant of Bateman and Erdős, n_{0}(A) equals 2 if k = 5 or k ≥ 7, however for A = {1, 2, 3, 4, 5, 6}, n_{0}(A) = 14.

5 Acknowledgments

The author would like to thank the referee for the detailed instructive comments and suggestions which helped to improve the quality of the paper.

References

[1] G. E. Andrews, The Theory of Partitions, Encyclopedia of Mathematics and its Applications, Vol. 2, Addison-Wesley, 1976.

[2] P. T. Bateman and P. Erdős, Monotonicity of partition functions, Mathematika, 3 (1956), 1–14.

[3] S. Bouroubi, Optimisation dans les Posets, Thése de Doctorat d’Etat en Mathématiques, USTHB, Alger, 2004.

[4] L. Comtet, Advanced Combinatorics, D. Reided, Dordrecht, 1974.

[5] I. J. Good and R. Razen, Solution to Advanced Problem 6137. Amer. Math. Monthly, 85 (1978), 830–831.

[6] I. J. Good, Solution to Advanced Problem 6137. Amer. Math. Monthly, 88 (1981), 215.

[7] H. Gupta, Finite differences of the partition function. Math. Comp., 32 (1978), 1241– 1243.

[8] A. M. Odlyzko, Differences of the partition function, Acta Arithmetica, 49 (1988), 237– 254.

2000 Mathematics Subject Classification: Primary 11P81. Keywords: integer partition, convexity.

(Concerned with sequence \underline{A026812}.)

Received March 6 2007; revised version received June 9 2007. Published in Journal of Integer Sequences, June 10 2007.

Return to Journal of Integer Sequences home page.