On the largest part size and its multiplicity of a random integer partition Ljuben Mutafchiev American University in Bulgaria, Blagoevgrad, 2700 ljuben@aubg.edu Abstract Let λ be a partition of the positive integer n chosen uniformly at ran- dom among all such partitions. Let Ln = Ln (λ) and Mn = Mn (λ) be the largest part size and its multiplicity, respectively. For large n, we focus on a comparison between the partition statistics Ln and Ln Mn . In terms of convergence in distribution, we show that they behave in the same way. However, it turns out that the expectation of Ln Mn −Ln grows as fast as 12 log n. We obtain a precise asymptotic expansion for this expectation and conclude with an open problem arising from this study. 1 Introduction and Statement of the Results Partitioning integers into summands (parts) is a subject of intensive research in combinatorics, number theory and statistical physics. If n is a positive integer, then, by a partition λ of n, we mean the representation λ: n = λ1 + λ2 + . + λk , k ≥ 1, (1) where the positive integers λj satisfy λ1 ≥ λ2 ≥ ... ≥ λk . Let Λ(n) be the set of all partitions of n and let p(n) = |Λ(n)| (by definition p(0) = 1 regarding that the one partition of 0 is the empty partition). The number p(n) is determined asymptotically by the famous partition formula of Hardy and Ramanujan [HR18]: r ! 1 2n p(n) ∼ √ exp π , n → ∞. 4n 3 3 A precise asymptotic expansion for p(n) was found by Rademacher [Rad37] (see also [And76, Chapter 5]). Further on, we assume that, for fixed integer n ≥ 1, a partition λ ∈ Λ(n) is selected uniformly at random. In other words, we assign the probability 1/p(n) to each λ ∈ Λ(n). We denote this probability measure on Λ(n) by P. Let E be the expectation with respect to P. In this way, each numerical characteristic of λ ∈ Λ(n) can be regarded as a random variable, or, a statistic produced by the random generation of partitions of n. In this paper, we focus on two statistics of random integer partitions λ ∈ Λ(n): Ln = Ln (λ) = λ1 , which is the largest part size in representation (1) and Mn = Mn (λ), equal to the multiplicity of the largest part λ1 (i.e., Mn (λ) = m, 1 ≤ m ≤ k − 1, if λ1 = ... = λm > λm+1 ≥ ... ≥ λk in (1), and Mn (λ) = k, if λ1 = ... = λk ). Each partition λ ∈ Λ(n) has a unique graphical representation called Ferrers diagram [And76, Chapter 1]. It illustrates (1) by the two-dimensional array of dots, composed by λ1 dots in the first (most left) row, λ2 dots Copyright © by the paper’s authors. Copying permitted for private and academic purposes. In: L. Ferrari, M. Vamvakari (eds.): Proceedings of the GASCom 2018 Workshop, Athens, Greece, 18–20 June 2018, published at http://ceur-ws.org 187 in the second row,..., and so on, λk dots in the kth row. Therefore, a Ferrers diagram may be considered as a union of disjoint blocks (rectangles) of dots whose side lengths represent the part sizes and their multiplicities of the partition λ, respectively. For instance, Figure 1 illustrates the partition 7 + 5 + 5 + 5 + 4 + 2 + 1 + 1 + 1 of n = 31 in which L31 = 7 and M31 = 1. • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • Figure 1 The earliest asymptotic results on random integer partition statistics have been obtained long ago by Husimi [Hum38] and Erdös and Lehner [EL41]. Husimi has derived an asymptotic expansion for E(Ln ) in the context of a statistical physics model of a Bose gas. Erdös and Lehner were apparently the first who have studied random partition statistics in terms of probabilistic limit theorems. In fact, they showed that   Ln 1 lim P √ − log n ≤ u = H(u), (2) n→∞ n 2c where   1 H(u) = exp − e−cu , −∞ < u < ∞ (3) c and π c= √ . (4) 6 Later on, Szekeres has studied in detail the asymptotic behavior of the number of integer partitions of n whose largest part is ≤ k and = k in the whole range of values of k = k(n). In particular, he has obtained in [Sze53] Erdös and Lehner’s limiting distribution (2) using an entirely different method of proof. Husimi’s asymptotic result was subsequently reconfirmed by Kessler and Livingston [KL76]. Higher moments of Ln were studied in [Ric74]. A general method providing asymptotic expansions of expectations of integer partition statistics was recently proposed by Grabner et al. [GKW14]. Among the numerous examples, they derived a rather complete asymptotic expansion for E(Ln ), namely, √ n log n 1 E(Ln ) = (log n + 2γ − 2 log c) + + 2c   2c2 4 1 + 2γ − 2 log c log n + +O , n → ∞, (5) 4c2 n where c is given by (4) and γ = 0.5772... denotes the Euler’s constant (see [GKW14, Proposition 4.2]). Notice that by conjunction of the Ferrers diagram the largest part and the total number of parts in a random partition of n are identically distributed for any n. The sequence {p(n)E(Ln )}n≥1 is given in [Slo18] as A006128. There are serious reasons to believe that the multiplicity Mn of the largest part of a random partition of n behaves asymptotically in a much simpler way than many other partition statistics. Grabner and Knopfmacher [GK06] used the Erdös-Lehner limit theorem (2) to establish that lim E(Mn ) = 1. (6) n→∞ In addition, among many other important asymptotic results, Fristedt, in his remarkable paper [Fri93], showed that, with probability tending to 1 as n → ∞, the first mn largest parts in a random partition of n are distinct if mn = o(n1/4 ). Hence it may not be that Ln constitutes the main contribution to n by a single part size and 188 some smaller part sizes may occur with sufficient multiplicity so that the products of these part sizes with their multiplicities could be much larger than Ln . In terms of the Ferrers diagram, this means that its first block (the block on the highest position in the Ferrers diagram) has typically smaller area than the areas of several next blocks with larger heights (multiplicities of parts). Our aim in this paper is to study the asymptotic behavior of the area Ln Mn of the first block in the Ferrers diagram of a random partition of n. We show some similarities and differences between the single part size Ln and its corresponding block area Ln Mn . As a first step, we obtain a distributional result for Mn that confirms the limit in (6). Theorem 1.1. For any n ≥ 1, we have p(n − 1) P(Mn = 1) = . (7) p(n) In addition, if n → ∞, then c 1 + c2 /2 P(Mn = 1) = 1 − √ + + O(n−3/2 ), (8) n n where the constant c is given by (4). Combining the Erdös-Lehner limit theorem (2) with (8), one can easily observe that the limiting distributions of Ln and Ln Mn coincide under the same normalization. Corollary 1.2. For any real u, we have   Ln Mn 1 lim P √ − log n ≤ u = H(u), n→∞ n 2c where H(u) and c are given by (3) and (4), respectively. Although Ln and Ln Mn follow the same limiting distribution, the difference in means E(Ln Mn ) − E(Ln ) grows as fast as 21 log n. A complete estimate is given by the following Theorem 1.3. If n → ∞, then, as n → ∞,   1 1 E(Ln Mn ) = E(Ln ) + log n − C + O , 2 log n where C = log c + 1 − γ = 0.67165... and E(Ln ) and c are given by (5) and (4), respectively. Remark 1.4. The sequence {p(n)E(Ln Mn )}n≥1 is given as A092321 in [Slo18]. The proofs of Theorems 1.1 and 1.3 and are based on generating function identities established in [ABBKM16] that involve products of the form P (x)G(x), where P (x) is the Euler partition generating function ∞ X ∞ Y P (x) := p(n)xn = (1 − xj )−1 (9) n=0 j=1 and G(x) is a function which is analytic in the open unit disk and does not grow too fast as x → 1. Our asymptotic expansions in (8) and Theorem 1.3 are obtained using a general asymptotic result of Grabner et al. [GKW14] for the nth coefficient xn [P (x)G(x)]. In the proof of Theorem 1.3 we also apply a classical approach for estimating the growth of a power series around its main singularity. We organize the paper as follows. Section 2 contains some auxiliary facts related to generating functions and the asymptotic analysis of their coefficients. In Section 3 we sketch the proofs of Theorems 1.1 and 1.3. Finally, in Section 4 we conclude with an open problem on the position of Ln Mn in the sequence of ordered block areas of a random Ferrers diagram. 189 2 Preliminaries: Generating Functions and an Asymptotic Scheme We start with two generating function identities. In the next two lemmas P (x) is the generating function given Q0 by (9) and by definition 1 := 1. Lemma 2.1. (i) For any positive integer m, we have ∞ X Y m−1 Y p(n)P(Mn = m)xn = xm (1 − xj )−1 = P (x)xm (1 − xj ). n=1 j≥m j=1 (ii) We also have ∞ ∞ k X X kxk Y p(n)E(Ln Mn )xn = (1 − xj )−1 = P (x)F (x), n=1 1 − xk j=1 k=1 where ∞ ∞ X kxk Y F (x) = (1 − xj ). (10) 1 − xk k=1 j=k+1 Sketch of the proof. Part (i) is the last conclusion of Theorem 2.3 from [ABBKM16]. Part (ii) is given in A092321 of [Slo18]. It also follows from Proposition 4.1 in [ABBKM16]. We shall essentially use the main result from [GKW14, Theorem 2.3]. We present here only slight modifications of those parts of this theorem that we will need in our further asymptotic analysis. Furthermore, by log x we denote the main branch of the logarithmic function that satisfies the inequality log x < 0 if 0 < x < 1. Lemma 2.2. Suppose that, for some constants K > 0 and η < 1, the function G(x) satisfies η G(x) = O(eK/(1−|x|) ), |x| → 1. (11) (i) Let G(e−t ) = atb + O(|f (t)|) as t → 0, 0, where b ≥ 0 is an integer and a is real number. Then, we have  b b+1  j 1 n 2π s X (b + j + 1)! 1 x [P (x)G(x)] = a √ − p(n) 24n − 1 s − 1 j=0 j!(b + j − 1)! 2s  1/2−  √  +O(e−2s ) + O e−n + f c/ n + O(n−1/2− ) for any  ∈ (0, (1 − η)/2), where s r 2π 2   1 1 s= n− = 2c n − (12) 3 24 24 and c is given by (4). (ii) Suppose that G(x) satisfies condition (11) and, for t = u + iv, let G(e−t ) = a log 1t + O(f (| t |)) as t → 0, where u > 0, v = O(u1+ ) as u → 0+ and  and a are as in part (i). Then, we have √   √ 1 n 24n − 1   x [P (x)G(x)] = a log + O n−1/2 + f c/ n + O(n−1/2− ) p(n) 2π with c given by (4). As in [GKW14], we remark that parts (i) and (ii) can be combined so that Lemma 2.2 generalizes to mixed asymptotic expansions involving sums of powers of t and logarithms of 1/t. The proof of Lemma 2.2, based on the saddle point method, is presented in [GKW14, Section 3]. 190 3 On the Method of Proof and Some Technical Details Sketch of the Proof of Theorem 1.1. First, we set m = 1 in Lemma 2.1 (i). We have ∞ X P(Mn = 1)xn = xP (x). (13) n=1 This implies (7) at once. The asymptotic behavior of the quotient in (7) may be found using Rademacher’s ”exact-asymptotic” formula [Rad37] (see also [And76, Chapter 5]). It seems that a quicker way is to apply the result of Lemma 2.2 (i). Here we have G(x) = x, which obviously satisfies (11). Setting x = e−t in (13) and expanding e−t as a Taylor series, we can take into account as many powers of t as we wish. This will be transferred into powers of n−1/2 in the asymptotic expansion of P(Mn = 1). We decide to bound the error of estimation up to a term of order O(n−3/2 ) and write 1 e−t = 1 − t + t2 + f (t), (14) 2 with ∞ j X t f (t) = . (15) j=3 j! The representation (14) requires to apply Lemma 2.2(i) twice: for the term √ −t with a = −1 and b = 1 and for the term 12 t2 with a = 1/2 and b = 2. Furthermore, (15) implies that f (c/ n + O(n−1/2− )) = O(n−3/2 ). Thus, from (13) it follows that xn [xP (x)] P(Mn = 1) = = 1 − A1 (n) + A2 (n) + O(n−3/2 ). (16) p(n) The computation of A1 (n) and A2 (n) is based on Lemma 2.2(i) with s given by (12). We skip all technical details and present here the final evaluations: c 1 A1 (n) = − √ − + O(n−3/2 ), (17) n n c2 A2 (n) = + O(n−3/2 ). (18) 2n The proof is completed by substituting (17) and (18) into (16). Proof of the Corollary. The total probability formula and the asymptotic estimate given by Theorem 1.1 imply that     Ln Mn 1 Ln Mn 1 P √ − log n ≤ u = P √ − log n ≤ u | Mn = 1 P(Mn = 1) n 2c n 2c   L n Mn 1 +P √ − log n ≤ u | Mn 6= 1 P(Mn 6= 1) n 2c √ √   Ln 1 = P √ − log n ≤ u (1 + O(1/ n)) + O(1/ n). n 2 Hence the Corollary follows easily from Erdös and Lehner’s result (2). Sketch of the Proof of Theorem 1.3. First, we represent the function F (x) given by (10) as F (x) = F1 (x) + F2 (x), (19) where ∞ X ∞ Y F1 (x) = kxk (1 − xj ), (20) k=1 j=k+1 191 ∞ X X∞ ∞ Y F2 (x) = k( xkl ) (1 − xj ) k=1 l=2 j=k+1 ∞ 2k ∞ X kx Y = (1 − xj ). (21) 1 − xk k=1 j=k+1 Grabner and Knopfmacher [GK06, formula 6.2] found a simpler alternative representation for F1 (x). They showed that the right-hand side of (20) yields ∞ X xk F1 (x) = . 1 − xk k=1 It is also known that ∞ X p(n)E(Ln )xn = P (x)F1 (x) n=1 (see, e.g., [GKW14, p. 1059]). In addition, Grabner et al. [GKW14, p. 1084] used Mellin trasform technique to show that log (1/t) + γ 1 t F1 (e−t ) = + − + O(| t |3 ), t → 0. t 4 144 From this expansion and their main result (see also both parts of Lemma 2.2) they derived asymptotic formula (5) for E(Ln ). From (19) it follows that xn [F (x)] = xn [F1 (x)] + xn [F2 (x)], which in turn implies that xn [F2 (x)] E(Ln Mn ) = E(Ln ) + . (22) p(n) The asymptotic analysis of the second summand in the right-hand side of (22) is based on Lemma 2.2 (ii). It requires a suitable expansion for F2 (e−t ) given by the next lemma. Lemma 3.1. If t = u + iv and u and v satisfy the conditions of Lemma 2(ii), then   1 1 F2 (e−t ) = log + γ − 1 + O 1/ log , t → 0. t t The proof of Lemma 3.1 contains lengthy technical details. We will skip them including here only a brief description. First, we focus on an asymptotic estimate for F2 (e−u ) as u → 0+ . We set x = e−u in (21) and partition the range of summation in its right-hand side into four intervals.  It turns out that the maincontribution is given by the sum over all integers k ∈ u1 log u1 − log log u1 − log 3 , u1 log u1 + log log u1 + log 2 , while the other three sums are negligible (of maximum order O 1/ log u1 as u → 0+ ). Finally, we transfer the variable u into t = u+iv using Taylor’s formula. For the reminder term we apply the same approach and the relationship between u and v from Lemma 2.2 (ii). Hence, applying Lemma 2.2 (ii) with G(x) := F2 (x) and f (t) := 1/ log 1t , we obtain   1 n c 1 x [F2 (x)] = log √ + γ − 1 + O , n → ∞. (23) p(n) n log n The proof of Theorem 1.3 is completed combining (22) with (23). 4 Concluding Remarks The main goal of this study is the comparison between the typical growths of the first block area Ln Mn and its base length Ln in the Ferrers diagram of a random integer partition n. It turns out that the leading terms in the √asymptotic expansions of the expectations of these two statistics are the same for large n; both are equal to 2cn log n. Erdös and Lehner’s limit theorem (2) and Theorem 1 show that this leading terms control the 192 weak convergence of Ln and Ln Mn . Both statistcs, after one and the same normalization, tend to a Gumbel distributed random variable. The expectations of Ln and Ln Mn are, however, different for large n. In fact, by Theorem 1.3   1 lim E(Ln Mn ) − E(Ln ) − log n = −C = −0.67165.... n→∞ 2 This phenomenon suggests a question related to the typical shape of a random Ferrers diagram of n. To state (k) the problem in a more precise way, we denote by Xn the multiplicity of part k (k = 1, ..., n) in a random integer (r) (k) partition of n. Let Zn be the rth largest member of the sequence {kXn }nk=1 . Erdös and Szalay [ES84] showed that   c (1) 1 n −u lim P √ Zn − log 2 − log log log n ≤ u = e−e , −∞ < u < ∞. n→∞ n 2 c Fristedt [Fri93, Theorem 2.7] has also studied this kind of rearrangements of the Ferrers diagrams and generalized (r) Erdös and Szalay’s result to Zn , where r ≥ 1 is fixed. He showed that   c (r) 1 n lim P √ Zn − log 2 − log log log n ≤ u n→∞ n 2 c Z u −w exp (−e − rw) = dw, −∞ < u < ∞. (24) −∞ (r − 1)! (r) So, it might be interesting to determine the typical position of Ln Mn among all ordered areas Zn . If Rn denotes (r) the smallest value of r such that Zn = Ln Mn , then we conjecture that E(Rn )  log log n, n → ∞. (25) This claim is supported by the following non-rigorous argument. From the result of Theorem 1.3 it follows that √ n √ E(Ln Mn ) = log n + O( n), n → ∞. (26) 2c A calculation of the expectation of the distribution in the right-hand side of (24) demonstrated in [Fri93, p. 708] shows that if r = r(n) → ∞ as n → ∞, then √ n √ E(Zn(r) ) = (log n + 2 log log log n − 2 log r) + O( n). (27) 2c Combining (26) with (27), one may conclude that log r(n) is of order log log log n, which supports the claim in (25). We hope to return to this question in a future study. The full text of this work may be found in [Mut17]. References [And76] G. E. Andrews. The Theory of Partitions. Encyclopedia of Mathematics and Its Applications-Volume 2. Addison-Wesley, 1976. [ABBKM16] M. Archibald, A. Blecher, C. Brennan, A. Knopfmacher, T. Mansour. Partitions according to multiplicities and part sizes. Australasian Journal of Combinatorics, 66:104-119, 2016. [EL41] P. Erdös, J. Lehner. The distribution of the number of summands in the partitions of a positive integer. Duke Mathematics Journal, 8:335-345, 1941. [ES84] P. Erdös, M. Szalay. On the statistical theory of partitions. In: Topics in Classical Number Theory - Volume I (G. Halasz ed.). North-Holland, Amsterdam, pp. 397-450, 1984. [Fri93] B. Fristedt. The structure of random partitions of large integers. Transactions of the American Math- ematical Society, 337:703-735, 1993. [GK06] P. Grabner, A. Knopfmacher. Analysis of some new partition statistics. Ramanujan Journal, 12:439- 454, 2006. 193 [GKW14] P. Grabner, A. Knopfmacher, S. Wagner. A general asymptotic scheme for the analysis of partition statistics. Combinatorics, Probability and Computing, 23:1057-1086, 2014. [HR18] G. H. Hardy, S. D. Ramanujan. Asymptotic formulae in combinatory analysis. Proceedings of the London Mathematical Society, 17(2):75-115, 1918. [Hum38] K. Husimi. Partitio numerium as occurring in a problem of nuclear physics. Proc. Phys.-Math. Soc. Japan, 20:912-925, 1938. [KL76] I. Kessler, M. Livingston. The expected number of parts in a partition of n. Monatshefte für Mathematik, 81:203-212, 1976. [Mut17] L. Mutafchiev. On the largest part and its multiplicity of a random integer partition. arXiv:1712.03233. [Rad37] H. Rademacher. On the partition function p(n). Proceedings of the London Mathematical Society, 43:241-254, 1937. [Ric74] L. B. Richmond. The moments of partitions, I. Acta Arithmetica, 211:345-373, 1974/75. [Slo18] N. Sloane. 2018. On-line Encyclopedia of Integer Sequences. https://oeis.org/. [Sze53] G. Szekeres. Some asymptotic formulae in the theory of partitions, II. Quarterly Journal of Mathe- matics, Oxford Academic, 4:96-111, 1953. 194