Some Central Limit Theorems for Doubly Restricted Partitions Citation Skarda, Ralph Vencil, Jr. (1966) Some Central Limit Theorems for Doubly Restricted Partitions. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/YH19-JH87. https://resolver.caltech.edu/CaltechTHESIS:10122015-160506112 Abstract Let P K, L (N) be the number of unordered partitions of a positive integer N into K or fewer positive integer parts, each part not exceeding L. A distribution of the form Ʃ/N≤x P K,L (N) is considered first. For any fixed K, this distribution approaches a piecewise polynomial function as L increases to infinity. As both K and L approach infinity, this distribution is asymptotically normal. These results are proved by studying the convergence of the characteristic function. The main result is the asymptotic behavior of P K,K (N) itself, for certain large K and N. This is obtained by studying a contour integral of the generating function taken along the unit circle. The bulk of the estimate comes from integrating along a small arc near the point 1. Diophantine approximation is used to show that the integral along the rest of the circle is much smaller. Item Type: Thesis (Dissertation (Ph.D.)) Subject Keywords: (Mathematics) Degree Grantor: California Institute of Technology Division: Physics, Mathematics and Astronomy Major Option: Mathematics Thesis Availability: Public (worldwide access) Research Advisor(s): Apostol, Tom M. Thesis Committee: Unknown, Unknown Defense Date: 3 May 1965 Record Number: CaltechTHESIS:10122015-160506112 Persistent URL: https://resolver.caltech.edu/CaltechTHESIS:10122015-160506112 DOI: 10.7907/YH19-JH87 Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 9215 Collection: CaltechTHESIS Deposited By: INVALID USER Deposited On: 13 Oct 2015 15:06 Last Modified: 08 Mar 2024 00:27 Thesis Files Preview PDF - Final Version See Usage Policy. 5MB Repository Staff Only: item control page

SOt'viE CEi'U'RAL L D.1IT THEORE!v!S FOR DOUBLY RESTRICTED PARTITIONS Dissertation by Ralph Vencil Skarda, Jr. In Partial Fulfillment of the Requirements For the Degree of Doctor of Philosophy California Institute of Technology Pasadena, California 1966 (Submitted May 3, 1965) ii ACKNOWLEDGEMENTS The author thanks the following for their attention and hel p : Profe:rnor Tom M. A:po::.tol , who in me.ny facet:;; of hi:. teaching provided an i mportant · example to the author, and wh o guided the preparation of this dissertation. Doct or Basil Gordon of the University of California at Los Angeles, whose helpful conunent s led t o the author's i nve s t igat ion of Diophantine approximation, whi ch is at the heart of the main result herein . The California Institute of Technology for scholarships and graduate teaching assist antships during the course of research, and for t he opportunity to be a teachi ng assistant under Professors H. F. Bohnenblust, Mil t on Lees and Tom Apostol. The Musical Activities Cor:unittee for sponsoring t he Caltech Glee Club, which has given me many of my most satisfying experiences at the California I nstitute. Mrs . Ruth Bowen of t he General Library staff, who s ecured a vital r-eference from the Int erlibrary Loan at the University of California at Berkel ey within f i fty hours . ~!a" . anc Mrs . Ralph V. Skarda , the author's parent s , for their patient encouragement . Mrs . David Corbett, who has skillfully typed this di sser tation. iii ABSTRACT Let P~ -(N) be tne number of unordered partitions of a positive f\.) 1 integer N into K or fewer positive integer parts, each part not ex ceeciing L. A distribution of the form \L P-K,L-(N) N~x is considered first. For any fixed K, tnis distribution approaches a piecewise polynomial function as L increases to infinity. As both K and L approach infinity, this distribution is asymptotically normal. These results are proved by studying the convergence of the characteristic function. The main result is the asymptotic behavior of PK,K(N) itself, for certain large K and N. This is obtained by studying a contour inte- gral of the generating funct ion taken along the unit circle. The bulk of the estimate comes from integrating along a small arc near the point 1. Diophantine approximation is used to show that the integral along the rest of the circle is much smaller. 1. INTRODUCTION We shall consider four pa:i;-tition enumerating functions. If K, L, and N are positive integers, the function PK,L(N) is define d to be the number of unordered partitions of N into K parts, the largest of For example, 22 has 11 partitions into 5 parts with 6 as which is L. a largest part. These are 6 + 6 + 6 + 3 + 1, 6 + 6 + 5 + 4 + 1, 6 + 6 + 4 + 4 + 2, 6 + 5 + 5 + 5 + 1, 6 + 5 + 5 + 3 + 3, 6 + 4 + 4 + 4 + 4. Therefore P~ .,/' 6 6 + 6 + 6 + 2 + 2, 6 + 6 + 5 + 3 + 2, 6 + 6 + 4+ 3 + 3, 6 + 5 + 5 + 4 + 2, 6 + 5 + 4 + 4 + 3, (22) = 11 • The function PK,L(N) is similar to PK,L(N) except that the number of parts of each enumerated partition is K or less. Thus, we have K PK,L(N) = I Pr,L(N). r=1 The function PK,L(N) differs from PK,L(N) in another way. Each enumerated partition has exactly K parts, but the largest part may be equal to L or any smaller integer . L PK,L(N) = Hence we have I PK,s(N) • S=l 2 The function PK,L(N) represents both of these modifications jointly, enumerating partitions with not more than K parts, each part not being greater than L. Vie may write K L l l Pr,s(N). P-K,L-(N) r=1 S=1 These functions are natural refinements of the more familiar functions PK(N) = P(N) lim PK,L(N) and L .... eo lim P- -(N) K .... oo K,L = L .... oo which enumerate simply restricted and unrestricted partitions respectively. Most of the classical lore of these functions can be found in accessible introductions to combinatorial analysis or number theory. In particular, a comprehensive treatment of nineteenth century algebraic methods can be found in MacMahon ( [ 5], Volume II, Section VII). Hardy and Wright ([4], pp. 273-96) give a more concise treatment, as does Riordan ([8], pp. 107-62). In the next section we shall cite the elementary properties we need. One of these, Lerruna 2-5, is a relationship connecting the functions PK,L(N), PK,L(N), PK,L(N) and PK,L(N). Consequently it will suffice to discuss PR,L(N) only. It will be convenient to define PK,L(N) = 0 for all negative 3 We set P- -(0) = 1. K,L Before stating Theorem 1, we introduce some more notation. integers N. Let g 1 (x) = 1 if 0 ~ x ~ 1 and let g 1 (x) = 0 elsewhere. For the integers K 2 2, gK(x) is defined recursively by the formula The function gK(x) is the K-fold convolution of g 1 (x), and it can be written in the form [x] gK(x) = 1 (K-1)! L (Ku)(-1 )u(x-u )K-1. \ We shall be interested in the following normalization of gK(x): \'le now state the Theorem 1. simplest result of this dissertation. Let K be a constant and Land B increase to infinity in such a way that B/L approaches a limit a, and let b = ./i27K(a - K/2). Then vie have ( K+L) K -1 B \' P- -(N) ~ L K,L N=O This result was suggested heuristically in 1928 by Tricomi [ 10], who noticed a correspondence between the partitions of an integer S into n unequal parts not exceeding N and the ways that a sum equal to S could 4 result when n balls are dravm from an urn containing a set of N balls numbered from 1 to N. He assumed that as S, n and N grew large the inequality r e striction for the parts viould become relatively insignificant, so that the probability density for S would approximate the convolution of identically distributed random processes. The actual number of such partitions is equal to P- ~(s - !ll!i.±1.l) ([8], p. 113), n,N-n 2 so Tricomi's result would be a special case of Theorem 1. The proof of Theorem 1 appears in Section 4 and uses a general theorem of Levy and Cramer on probability distributions. The next result is similarly proved: Theorem 2 . If K, L and B increase to infinity in such a way that KL 1 li2(B-2HKL(K+L+1 ))2" approaches a limit b, then 1 B K+L\ - ( K} 1 \ P- -(N) ~ , ~L K,L N=O 'i2rr I -x212dx. b e -00 Tricomi (11] and Castelnuovo (1] have proved similar r e sults for ordered partitions. Their methods deal with identically ·distributed independent random variables, and these appear to be applicable only to ordered partitions or to partitions with unequal parts. In 1941 Erd8s and Lehner [3] obtained a similar result for simply restricted partitions: If, for some fixed x, Kand N approach infinity in such a way that K = [/N(x+(log n)/C)], where C = ~' then 5 lim PK(N) P(N) = exp[-(2/C)exp(-Cx/2)]. Their proof uses an inclusion-exclusion process and the asymptotic formula P(N) = eCYN/(4N/3). The next theorem is the principal result in this dissertation: Theorem 3. If K and N approach infinity in such a way that Ji5(N - ~)K-3/2 approaches a limit b, then we have l K3/2(2K)-lP- -(N) ~ 6 K K,K The proof of this theorem is based on contour integration of the generating function FK,K(z) = l PK,K(N)zN along a path surrounding the N origin. In the usual treatments of the partition function P(N), which is the limiting case as K increases to infinity, it is necessary to confine the contour of integration to the interior of the unit circle. A case in point is the recent approach by Nevnnan [6] in which the con- tour is a circle of radius 1 - (n/./6r'i.). He isolates a short segment close to 1 which contributes the bulk of his estimate. He then shows that the generating function is of a smaller exponential order on the remainder of the circle . Since our function FK,K(z) is a polynomial, it is possible to use the unit circle itself. The major part of the estimate is done on an arc centered on the point z = 1. Diophantine approximation is used to obtain a bound on the polynomial elsewhere on the circle. 6 2. ELEMENTARY PROPERTIES OF P-K,L-(N) Unless stated otherwise, each of the following lerrunas is a direct consequence of the definitions. Lemma 2-1. If either N < 0 or N >KL holds, then we have P-K,L-(N) = O. Lemma 2-2. For all positive K and L we have P-K, -(N) = 1 if 0 ~ N ~ K, and P-1,L-(N) = if 0 ~ N ~ L. Lemma 2-3. For K ~ 2 , L ~ 2 and all N we have Lemma 2-4. P-K,L-(N) = P-L,K-(N). This is best proven with a Ferrer's graph, as in [4], pp. 273-74, or in [8], pp. 113-1 4. Lemma 2-5. P-K,L-(N) PK+l,L(N+L) = PK,L+l"(N+K) PK+l ,L+l (N+K+L+l ). This follows from Lerronas 2-3 and 2-4 and the formulas appearing with the definitions. We now introduce the generating function 7 KL \ P- -(N)zN. L K,L N=O FK,L(z) Lemma 2-6. Except wherever the denominator vanishes we have K+L 1-zr) n( K L 'Ti' / I ( 1 -zr ) ( 1 -zr ) n' r=l r=1 This can be deduced from Lemmas 2-1, 2-2 and 2-3. Other derivations of this formula appear in [5], p. 5, and in [8], p. 153, problem 5. This lenuna shows that the polynomial FK,L(z) has all its zeroes on the circle \z\ = 1. Lemma 2-7. KL \L P-K,L-(N) = N=O 8 3. THE DISTRIBUTION °'K,L (x) AND ITS CHARACTERISTIC FUNCTION qK,L ( t) The weak asymptotic behavior of PR,:L(N) is easily investigated in terms of the following function: where the sum is taken over all integers N :S (KL/2) + cK,Lx and where cK,L is defined to be fKL(K+L+l)/12. (Whenever there is no danger of ambiguity, the subscripts K and L are omitted.) Since we have Q(x) = 0 for x < -KL/(2C), and Q(x) = 1 for x > KL/(2C), and since Q is a nondecreasing step function for intermediate values of x, we can ·. It can be shown easily, using Lerrunas 3-3 treat Q as a distribution. and 3-4, that Q has mean 0 and variance 1. We now introduce its characteristic function 00 q(t) = qK L(t) = ' S-coe ixt d°'K L(x), which is defined for every real value oft. ' A simple calculation yields the following: Lerrana 3-1. q(t) = (K~L rI 1 KL PR,E(N)exp( ( (N-(KL/2) )/C)it) N=O This can be carried further with Lerruna 2-6 and the exponential formula for the sine. 9 Lerruna 3-2. Wherever the denominator does not vanish we have K+L nsiCr~J~&)C) q(t) r=1 = -------------- K L 71' sin (rt/2Ql 71' sin (rt/2C) 11 (rt/2C) 11 (rt/2C) r=1 r=l The following lenunas are needed only for the proofs of Theorems 2 and 3. Lerruna 3-3. Within the interval {It I < (2n:C/(K+L))}, q(t) has an analytic logaxithm with a power series expansion of the form 00 \' log q(t) = L a2nt 2n , n=1 where - {;(2n) n(2rcC) 2n For any complex z such that lzl < 1, the quotient sin n:z is n:z nonzero and analytic. It has a logarithm which can be found from Proof. the Weierstrass product for the sine: 10 (X) log si~zltZ (X) (X) =I1og(1-(z/s) ) =-I I (z/s)2n/n 2 S=l n=l S=l For \t\ < (21tC/(K+L)), Lemma 3-2 gives us L K \ 1 log sin (rt/2C) - L (rt/2C) L sin (rt/2C) sin (rt/2C) \ i og (rt/2C) - L og (rt/2C) r=l r=l r=l K+L log q(t) = \ Now, using the expansion of log sin :n:z ltZ , we have log q(t) and the lem~a is proved. Lemma 3-4. ?roof. Since we have K+L \ In the previous lerruna, a 2 is equal to -1/2. K 2 \ 2 Lr - Lr - r=l 11 = i { (K+L)(K+L+1 )(2K+2L+l )- K(K+l )(2K+l) - L(L+1 )(2L+1) } it is easy to show that 2 a 2 = -C(2)(2:1tC)- KL(K+L+1) = -1/2. Lemma 3-5! Within the interval {ltl = (2:1tC/(K+L))} we have 2 q(t) :S e-t /2 • Proof. Lemmas 3-3 and 3-4 imply that log e 2 -t /2 00 - log q(t) = which is nonnegative since all the a2n's are negative. ;Lema 3-6. Within the interval {\t\ :S (rrC/(K+L))} we have log e Proof. -t 2 /2 . As above, we have 2 4 1 1 - log q(t) :S (2t /15)(K- +L- ). log e-t /2 - log q(t) 12 where the integration is taken in the interval 2 2 [-((r+L)t/(2nC)) ,-(rt/2rtC) ]. Since l t I < ( nC/K+L), we have ( 1+u)- 1 < 1 - 4u/3 in the integrand. Using this estimate, integrating and summing we find 2 log e-t /2 - log q(t) :S (2/15)rt 4(t/(2rtC)) 4KL~K+L+l)(~+L2+KL+K+L) = (2t 4/15)(K- 1+L- 1-(K+L+1)- 1 ). and the lenuna is proved. Lerna 3-7. For all t satisfying ltl :S (nC/K+L) we have 13 Proof. The leftmost inequality comes from Lemma 3-5. gives us Hence we have since 1 - e -u ~ u if u ~ O. Lerrana 3-6 14 4. THE PROOF OF THEOREM 1 Since CK,L is defined to be IKL(K+L+l)/12, we see at once that if K is fixed as L increases to infinity then C also increases to infinity and that For any finite t and r, S r S K, it is possible to take L so large that sin (rt/2C) (rt/2c) is then nonzero and increasing to 1 as L increases to infinity. Lemma 3-2 we have immediately that From lim qK 1 (t) exists and equals L ... oo ' which is the Fourier transform of hK(x). , We now refer to the following theorem of Levy and Cramer: Given a sequence of distributions F 1 (x),F2 (x), ... and the characteristic £'unctions ~ (t),~ 2 (t), . . . . A necessary and 1 sufficient condition for the convergence of the sequence Fn (x) to a distribution function F*(x) is that, for every t, the sequence ~n (t) converges to a limit ~(t), which is continuous for the special value t = o. 15 When this condition is satisfied, the limit ~(t) is identical with the characteristic function of the limiting ([2), p. 96) distribution F*(x). We shall take the distribution functions to be FL{x) = °'K,L(x). Since the characteristic function is identical to the Fourier transform, we also have ~1 (t) = qK,L(t) and ~(t) = (sin -67Kt)K· -13/Kt This L"Il!1lediately yields °'K,L(c) ~ c J hK(x)dx for any real value -co Of c. Now for any € > 0 the hypothesis of Theorem 1 implies that there is an L € such that if L > L then we have - € I B-(KL/2)+(1/2) -. b CK,L ! < €. Since Q. is nondecreasing, we have Q(b-€) :S Q(B-(KL&2)+(1/2}\:S Q.(b+€) K,L ) for all L ~ L€. . As this L increases to infinity, we see that sb-\K(x)dx -oo ~ lim inf Q(B-(KL22)+(1/2)) L -+ oo . K,L :5,. lim sup Q (B-(KL&2 )+(l/2 L -+ oo . K,L l\:s. Jb+\K(x)dx. ) -co 16 The continuity of the integral implies that the extreille right and left b members of this inequality will approach J hK(x)dx as € ... O. Thus -oo lim Q (B-(KL&2)+( 1/2)) L .... oo J hK(x)dx. The definition of . Q shows that this is b exists and equals K,L -oo equivalent to Theorem 1. 5. THE PROOF OF THEOREM 2 As K and L both increase to infinity, it is apparent that CK L/(K+L) does also. ' 2 2 pointwise to e-t 1 Thus Lemma 3-7 implies that qK,L(t) converges The rest of the proof of Theorem 2 follows from this fact in the same way that the proof of Theorem 1 followed from the convergence of qK,L(t) in Section 4. 18 6. THE PROOF OF THEOREM 3 The Cauchy residue theorem gives us PK,K (N) = (2r.i )-1sz -(N+1) FK,K( z )dz, where the contour is the circle lzl = 1, traversed counterclockwise. F is the generating function introduced in Section 2. I f we write z =e 2ni9 1 -21 5, e 5, 2' this becomes , . '1 J·2(2K)cos(2n((K2/2)-N)9 )qK,K(2nCK,K9- )de,· < ( e 2rrie) = (2K) eK nie and since is an = 2 O 2 since FK, K K qK, K 2nCK, Ke), q even real function. Now we write r::::--1 .2 2 PK,K(N) - ( 2K) K (v2nC) exp(((Ir/2)-N) /2C 2 ) _1 ' 2Kcos(2n( (K-/2)-N)e _2 , = 2 ( 2K)J K )qK,K(2nCK,Ke )ae 0 19 1 + 2J ~e{e2niN9FK,K(e2ni9)}de 2K 2 - 2(2KK)J ~cos(2n((~/2)-N)9)e-( 2 nce) /2 ae. 2K Thus we have 1 2 S 2(~K)J 4Kcos(2n((~/2)-N)e)\q(2nC9)-e-( 2 nce) 12 \ae 0 20 _1 + 2(~K)J~Kcos(2n((~/2)-N)9lq(2nC9)-e-( 2 2 nce) 12 \ae 4K 1 + 2 J2jF(e2ni9)\d6 1 2K 00 + 2(2~)J cos(2n((~/2)-N)6)e-( 2 nCB) /2 ae 2 1 2K ( 6-1) . say. As a consequence of Theorem 3-7, we can write (6-2) 21 From Lerruna 3- 5 we deduce that _1 2 s 2 (2;)J~Ke-c2~ce) /209 . 4K Thus vie have I2 + I4 ~ 2(iK)J ~e-(2.ce)2/2aa 4K (6-3) The estimation of 1 3 is made possible by the following lemma, which i s proved in Section 7. Lemma 6-1. For 2~ S 9 S ~' we nave 22 This yields irrunediately that (6-4) The estimates expressed in inequalities (6-2), (6-3) and (6-4) are all of smaller order than ( 2K)/c K K,K as K increases to infinity. (6-1). Theorem 3 now follows from inequality 23 7. ESTTh1ATING F( z) ON AN ARC OF THE CilWLE I z l -1 The proof of Lemma 6-1 will be worked out in terms of the funct~on GK(e) = lFK,K(e 2niS)l. We shall derive an upper bound for 2 G on the interval ~ S, 9 S, ~· For large K, this bound will be much 2 smaller than the maximum for G, ( KK), attained at 9 = o. We begin with the following well-knovm lemma from the theory of Diophantine approximation. Lerruna 7-1. If K is a positive integer and if e is a real number on the interval [0,1], then there are relatively prime integers, p and q, which satisfy o s p s_ q s_ 2K, Vie have taken n and je - p/qj < q( 2 ~+l). 2K in Niven's statement and proof of this result ( [ 7] , pp. 3- 4) . 2 We shall choose any particular e1 in the interval [ ~,~J. For this e 1 each fraction p/q d_e termined by Lemma 7-1 must have q 2: 2. For any such choice of p/q we shall obtain an estimate for G(9) for all e in the interval Ie - p/q I < q ( 2~+ 1)" This_bound} which depends only on K, is given by the following lemma: Lemma 7-2. 1 If 2 K S, e S, 2 ~'and if D = (2n) 3123-9n exp(tg + 5), we have ~ 2 GK(e) < Di1(K+l ) 32K < 55K Lemma 7-2 directly implies Lerrana 6-1. (K+1 )32-K(~K). It is easily verified for the 24 case K = 1. We shall give the proof for K 2: 2 by mathematical in- ductiop on K. Given K, we assume that the lenuna is true for all small er integers. The proof splits naturally into two cases: ( 1 ) K < q $_2K, and (2) q ~ K. CASE 1 : 2 ~ K < q S 2K 2 i'/ithin the interval \6 - p/q \ < q( ~+l ) ' the only factor of 2K n l 1- e2rrir8 l G(8 ) = r=K+1 K rrr=l \ l-e2nir 6 \ which vanishes at al l is 2 l1-e niqel = 2lsin qn6 l = 2 sin qnl6 - p/qJ < n/K. ( 7-1) The following result will be convenient in estimating the rest of the quotient above . Lenuna 7-3 . For any 6 in the interval [o,~], and for any n > 1, we have n lT \sin sne \ < /2nn32-n/2 (7-2) S= l Equivalently, when x e 2ni6 is considered, we have n ff \1-xs j < -l2;n32-n/ 2 ( 7- 3) S=l P-£oof . If n = 1, the lemma may be verified by inspection. we have, if 0 < e < 1/n, I f n ~ 2, 25 n rr Sin sn9 S= 1 (nn6)n log n n = log TT sinsn9s118 S=l 00 \ ' = l l log(l-(s9/u) 2 ) +log nn~ S=l U=l n < - oo oo l l l {s9/u) 2t/t + log{&e-nnn+l/2 (1+(1 /4n ))/nn} S=l U=l t=l n co l (se) l (1 /u 2 ) 2 < log{../2nne-n(1+(1/4n))} S=l U=l n Thus log l sin srce is bounded above by S=l which attains its maximum, n(log 3-3/2) + log{l2rcn(l+(l/4n))}, when e is equal to 3/nn. Since log 3 - 3/2 < -(log 2)/2, the lemma follows for the case 0 < e < 1/n. For the remaining case, e ~ 1/n, it is sufficient to cite a lemma in a recent paper by Sudler, Lemma 7-3 is then complete. ([9], pp. 4-7). The proof of 26 Now we can bound q-1 2K n 2K n n q-1 rr f(rp/q). f(rp/q) f(rp/q) f(rp/q) r=K-..+"'-1_ __ r=l r=q+l r=g+l G*(p/q) = - - - - - - - - = q-1 K ,...,, f(rp/q)2 11 r(rp/q) r=1 r=1 2 n 2K-q q-1-K rr f(rp/ci) n f(rp/q)2 q-1 n ' f(rp/q) r-1 where f(v) = j 1-e 2 rdvl. The previous lemma implies that the numerator is less than (-r2';~)3(2K-q)3( q-l-K) 62( q/2 )-l, if K + 1 < q < 2K. Since we have (2K-q)(q-1-K) 2 < 4K3/27, this bound becomes ("t2°;)3(26;39)K92K- 1• If q = K + 1, the numerator is less than .f2;K32K/2 • the numerator is less than 2n(K-1) 62K-l. If q = 2K, Since the denominator of G* is equal to q, we can ·write G*(p/q) < ( 2 ~)3/2K8 2 K+5 3 -9 if K + 1 < q < 2K, G*(p/q) < /2;.~2K/2 if q = K + 1, _and G*(p/q) < (rt/2K)(K-1)62K if q = 2K. From these inequalities, along with the fact that we are con- 27 sidering K 2: 2, we obtain, for K < q :S 2K, ( 7-4) Now we estimate 2K . l1 . ,.,_ 2 :rciro n 1~:2nirp/q 1 r=K+1 ~ = r~g ll 2:rcir9 l JT r=l 1 for 0 < \G-p/qj < q( 2 K+l ). is close to 1. 1 =:2:rcirp/q A typical factor l l 2rrirG -e . / 1...:e 2 nrp q 1 Hence we consider sin nr9 sin(:rcrp/q) - 1 = cot(1TI'p/q)sin 1TI'U +cos :rcru - 1, where u = e - p/q. For the numerator of G*( e )/G*(p/q) we have 2K log \ sin 1Cre L sin( )'(rp/q) r=K+1 r_;i'q 2K < l Icos :rcru-1 \ + \cot (1TI'p/q) \ l sin :rcru \ r=K+1 r_;i'q ! sin nr9 sin(:rcrp/q) l 28 2K I ((Jrru ) 2/2+nrIu11 cot ( rrrp/q) j ) < r=K+l rJq 2K 2K \' 2 I rrr\ul \cot(rrrp/q)I 2 . f_, · r (rm) /2 + < r=K+1 rJq r=K+1 r/q 2K 2 2 < '.)n u K3/4 + 2nKI u l l l cot ( rcrp/q) l r=K+l r,fq 2K I' \cot(rcrp/q)I, 2 < 5rc /(16q) + (rc/q) r=K+1 r/q because \uj < 2~q· Since K < q, no more than one value of r, K + 1 ~ r ~ 2K, can fall in any residue class modulo q, and we have 2K TT [K/2] lcot(1trp/q)\ ~ 2 TT [K/2] cot(nrl/q) = 2 n q/(nr) r=K+l rJq < (2q/rr)(l+log (K/2)). We can then write 2K log J TT r=K+l r/q l sin 1're sin(rrrp/q) l 2 = 5n / (1 6q) + 2 + 2 log K - 2 log 2. (7-5) 29 We now show that each of the factors of the denominator i s bounded away from O. Since r :5 K here, we have r\u] < 2~, and l sin rtre _] > 1 - I 1-cos nru 1 - 1cot ( rcrp/q) 11 sin nru I sin( 1U'p/q) - = 1 - ( rrKu) 2/2 - nKlu]cot(n/q) 2 2 > 1/2 - J"( /(8q ) > 1/3. Since log v 2: (v-1 )/v for 0 < v :5 1, we have ~ ~ rrre j < · (lsin rrre j -log II \sin sin(nrp/q~ 3 L. sin(n:rp/ci) r=l · r=l K 2 2 < (3r. u )/2 K l r + 3 l nr\u\ \~ot(;crp/q) 2 r=l r=l K 2 2 l < n u J2 + <3n\u\K \cot(r.rp/q)j r=1 [K+1/2] < i/(liq) + 31t/q I cot(1U'1/q) r=l 2 < n /(liq) + 3 + 3 log(K+1) - 3 log 2 . Combining this inequality with inequality (7-5), we have 1 30 2 log G*(e)/G*(p/q) ~ 9~ /(16q) + 5 - 5 log 2 + 2 log K + 3 log(K+l). From inequalities ( 7-1) and ( 7-4) we obtain 9 2 GK(e) = l1-e niq j(G*(9)/G*(p/q))G*(p/q) < (n/K)exp{9n 2/(16q)+5-5 log 2}~CK+1) 3 (2n) 3 /2 253-9KS2K. And we obtain GK(e) ~ DK9 (K+1) 32K, ( 7-6) 2 2 where D =Jtexp{9n /48+5}(2n) 31 3-9 > 2. Stirling's formula for factorials yields 2 Since D(9/8) ./; < 55, both formulas in Lemma 7-2 hold for Case 1. CASE 2: q < K There are unique integers K1 and K which satisfy 2 In connection with this decompos ition, a very interesting relation hol ds: Lerruna 7-4. If l 9-p/q\ < q(~+l )' then we have 31 . if K2 O, and if 0 < ~ < q. Proof. · For any e ./. p/q vie can write 2K -1 2K n r=2K2+1 ~--"~~~~~ K n 1 \sin nre l Tf 1sin n( (pt/q)+( t+sq)u) \ q+2K2 rr = 2 sin rcre t=1+2~ _ S=_O~~~~~~~ K -1 1 11' JI (7-7) 2 sin rc((pt/q)+(t+sq)u) r=JS+ 1 where u = 9 - p/q. This product represents GK(6) if K2 = 0 and GK(e)/GK (9) if K2 > O. 2 The index t in this product assumes q consecutive integer values, exactly one of which, say t 0 , is divisible by q. If ~ < q/2, we have t 0 = q. The corresponding part of the pro- duct is 2K 1-1 TT 2K1 \sin ;r(p+( s+ 1 )qu) l TT l sin rcsqu 1 S=0 = S=1 K, - 1 K1 Tf sin27t(p+(s+1 )qu) Tf sin21(squ __,,;;..---"-~~~~~~~~- S=O ~"--~~~- 32 2K, :::: (2K 1) K, 1T sin nsqu nsqu In 2K, nsou)2 ' (sin :;rsqu S=1 S=l which is bounded away from both infinity and zero in the given interval. As in the proof of Lemma 3-3, we have I n 2Kl loo0 { 2K, S=l ) 2 1T (sinnsqu nsgu) sin :r.:sgu n:squ S=l co =-I :s .o. m=1 If ~ 2: q/2, we have t 0 = 2q. The corresponding part of the product has the sane bound as above, as can be shmm in the same way. Thus to complete the proof of Lemma 7-4 it is sufficient to show that the rest of (7-7), 2K -1 1 q+2~ f(u) = H l sin 1!((pt/q)+(t+sq)u I n n t=1+2~ qft S=O K -1 1 ' 2 sin n((pt/q)+(t+sq)u) S=O is not greater than 1 in absolute value. All factors of f(u) are non- 33 As u approaches o, f(u) approaches 1. vanishing in the given interval. Thus it suffices to show that the logarithmic derivative below is nonpositive for positive u. (It follows in the same way that this deriv- ative is nonnegative for negative u.) We have q+2K2 (2K 1-1 d~(log f(u)) = l l (t+sq)1( cot 1(((pt/q)+(t+sq)u) t=1+2~ . S=O q~t K -1 1 l (t+sq)1( cot •( (pt/q)+(t+sq)u~ - 2 S=O q+2K K -1 2 1 = l l ((t+(s+K )q)rtcot1(((pt/q)+(t+(s+Kl)q_)u) 1 t=l+21S s:O '· qft'· - (t+sq)it cot it((pt/q)+( t+sq)u)) = q+2K K -1 l l (t+sq)it(cot n((pt/q)+(t+(s+K )q)u) 2 1 1 - cot rr((pt/q)+(t+s q)u)) 1 K -1 + L, •K1q S=O ( q+2JS ) l cot •( (j,t /q)+( t+(s+K1) q )u) • t = l+2~ qft 34 In the first swnmat ion term of the last expansion, the "cotangent minus . cot angent" factors are nonpositive, because the cotangent is monotonically decreasing on each open interval between multiples of ~. Since both arguments are on the same such interval, and since u is nonnegative, the whole term is nonnegative . In the other surrunation term we have q+2~ l q.+2~ cot n((pt/q)+(t+(s+K1 )q)u) < l t=l+2~ t=1+2~ qtt q-!'t cot n(pt/q) o, and the proof of Lerruna 7-4 is complete. The proof of Lerruna 7-2 for Case 2 now subdivides into the following cases: (a) ~ = O;. (b) K2 > O and 1/(2~+1) < e :5 1/2; (c) K2 = 1 and e < 1/(2~+1); (d) 1 < ~ :5 q/2 and e :5 1/(2~+1); and q/2 < ~ < q and e < 1 /(2~+ 1). CASE 2a: K2 = 0 2 St i· r1.ing ' s approx:una · t ion · yie · ld s ( 2nn ) < 2 n. Lemma 7-4 now yields and the second formula in Lemma 7-2 follows from this in the same way it did from relation (7-6). CASE 2b : 0 < ~and 1/(2K2+1) < e :5 1/2 Recalling that Lemma 7-2 is assumed for i ntegers less than K, including ~ in particular, we have 35 CASE 2c: ~ = 1 and es 1/(2~+1) It is sufficient to write CASE 2d : 1 < K2 = q/2 and 9 < 1/(2K2+1) Since K1 2: 1 and ~ 2: 2, we have 2K 1 + 2K2 S 2K 1K + K • 2 2 estimate is then G ( e ) = ( 2Kl ) G ( e ) = ( 2K, 2~ < 2 K ~ K2 ~ )( ~ ) 2K +2K 1 2 Our s 2K. CASE 2e: q/2 < K2 < q and e < 1/(2~+1) Lemma 3-5 tells us that when jej < 1/(2~+1) we have since 4 < ~ /(3 log 2). 2 The hypothesis of Lemma 7-2 yields 8 < (p/q ) - 1/ (2K+l) 2:. 1/q - 1/(q(2K+l )) so that we now have = 2K/(q(2K+1 )), 36 . 3 2 _ ( 2K )(2K )' -4K2 (2K/( q(2K+ 1))) GK(e) - K 1 K 2 2 1 2 2K1 + 2~ - 4K2(2K) 2 (2K+1)- 2q- 2 ((q/2) + (1/2)) 2 < 2 Thus the discussion for Case 2 is completed, and--with it--the proof of Lemma 7-2 • 37 REFERENCES 1. G. Castelnuovo, Sur quelques problemes se rattachant au Calcul, des ,, ,, Probabilites, Annales de l'Institut Henri Poincare, Universite de Paris, vol. III, pp. 465-90, 1932-33· 2. H. Cramer, Mathematical Methods of Statistics, Princeton Univer- sity Press, 1946. 3. P. Erd8s and J. Lehner, The distribution of the nu.i~ber of sunmands in the partitions of a positive integer, Duke Mathematical Journal, vol. 8, pp. 335-45, 1941. 4. G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Fourth Edition, Clarendon Press (Oxford), 1960. 5, P. A. MacMahon, Combinatory Analysis, Cambridge University Press, 1916. 2 vols. 6. D. J. Newman, A simplified proof of the partition formula, Michigan Mathematical Journal, vol. 9, pp. 283-87, 1962. 7. I. Niven, Diophantine Approximations, New York: Interscience, 1963. 8. J. Riordan, An Introduction to Combinatorial Analysis, New York: Wiley, 1958. 9. C. Sudler, An estimate for a restricted partition function, Quarterly Journal of Mathematics, Oxford, Second Series, vol. 15, pp. 1-10, 1964. 10. F. Tricomi, Sul nurnero delle partizioni di un intero dato, Bollettino della Unione Maternatica Italiana, vol. VII, pp. 243-45, 1928. 11. F. Tricomi, Su di una variabile casuale connessa con un notevole tipo di partizioni di un nurnero intero, Giornale dell'Istituto Italiano degli Attuari, vol. II, pp. 455-68, 1931.