30 Pages
Downloading requires you to have access to the YouScribe library
Learn all about the services we offer


Downloading requires you to have access to the YouScribe library
Learn all about the services we offer
30 Pages


DD-‡D~-pDD-Differences of the partition functionA. M. OdlyzkoAT&T Bell LaboratoriesMurray Hill, New Jersey 07974ABSTRACTLet p(n) denote the number of unrestricted partitions of n, and letk k 1p(n) = p(n) p(n 1 ), p(n) = D ( p ) (n). This note answers severalkquestions about the behavior of the k-difference p(n) by proving that if k is largekenough, there is an integer n (k) such that p(n) alternates in sign for n < n (k)0 06 2 2_ __and is nonnegative for n n (k). It is also shown that n (k) k ( log k) as0 0 2k fi ¥ .D-DD-DDp--D-D‡D‡DD‡DDDDifferences of the partition functionA. M. OdlyzkoAT&T Bell LaboratoriesMurray Hill, New Jersey 07974. .Dedicated to Paul Erdos on the occasionof his 75th Birthday.1. IntroductionIf f (n) is any function on the nonnegative integers, define its first difference f bykf (n) = f (n) f (n 1 ) for n 1, f ( 0 ) = f ( 0 ). The k-th difference f of f isk k 1then defined recursively by f = D ( f). A few years ago, I. J. Good [5a] askedkabout the behavior of p(n), where p(n) denotes the number of unrestricted partitionskof n. He initially conjectured [5a] that if k > 3, then the sequence p(n),n = 0 , 1 , . . . , alternates in sign. However, computations by R. Razen andindependently by I. J. Good and his associates [5b] found counterexamples to thiskconjecture, and led to a new conjecture, namely that for each fixed k, p(n) > 0 for nsufficiently large. I. J. Good [5b] even made the stronger ...



Published by
Reads 8
Language English


Differences of the partition function
A. M. Odlyzko AT&T Bell Laboratories Murray Hill, New Jersey 07974
Letp(n) denote the number of unrestricted partitions ofn, and let
Dp(n)1p(n)%p(n%1 ),Dkp(n)1 D(Dk%1p) (n note answers several). This
questions about the behavior of thek-differenceDkp(n) by proving that ifkis large
enough, there is an integern0(k) such thatDkp(n) alternates in sign forn0n0(k) and is nonnegative forn³n0(k). It is also shown thatn0(k)ς_ϑ_62_k2( logk)2as
k| υ.
1. Introduction
Differences of the partition function A. M. Odlyzko AT&T Bell Laboratories Murray Hill, New Jersey 07974 Dedicated to Paul Erd.o. s on the occasion of his 75th Birthday.
Iff(nnonnegative integers, de®ne its ®rst difference) is any function on the Dfby Df(n)1f(n)%f(n%1 ) forn³1,Df( 0 )1f( 0 ). Thek-th differenceDkfoffis then de®ned recursively byDkf1 D(Dk%1f few years ago, I. J. Good [5a] asked). A about the behavior ofDkp(n), wherep(n) denotes the number of unrestricted partitions ofn. He initially conjectured [5a] that ifk23, then the sequenceDkp(n), n10 , 1 , . . . , alternates in sign. However, computations by R. Razen and independently by I. J. Good and his associates [5b] found counterexamples to this conjecture, and led to a new conjecture, namely that for each ®xedk,Dkp(n)20 forn suf®ciently large. I. J. Good [5b] even made the stronger conjecture that for eachk, there is ann0(k) such thatDkp(n) alternates in sign forn0n0(k), andDkp(n)³0 for n³n0(k also suggested that 6). He (k%1 ) (k%2 )#k3/2 might be a good approximation ton0(k further computations by R. A. Gaskins led I. J. Good to). Some revise his conjecture about the size ofn0(k), and suggest thatϑk5/2might be a good approximation to it [5c].
At about the same time as the ®rst publication of I. J. Good's problem, the same question about the sign ofDkp(n) was also raised independently by G. E. Andrews, and was answered by H. Gupta [6]. Gupta noted thatDp(n)20 for alln, and gave a simple
- 2 -
proof of the result thatD2p(n)³0 forn³2, whileD2p( 0 )11,D2p( 1 )1 %1. Gupta also noted that it can be shown easily using the Hardy-Ramanujan-Rademacher series [1,2,3,7,8] forp(n) that for eachk,Dkp(n)20 ifnis suf®ciently large. In fact, this result can be obtained from some of the earliest of the Hardy-Ramanujan approximations [7] top(n):
p(n)1 _1____Ö2_` _ _d_nd_(ln%1exp (Cln) )#O( exp ( (C /2# Α)n1/2 ,) ) (1.1) 2ϑ for everyΑ 20, whereC1 ϑ( 2/3 )1/2andln1(n%1/24 )1/2. Thek-th difference of the second term on the right side of (1.1) is of the same order of magnitude as that term (fork®xed,n| υ), while thek-th  itsdifference of the ®rst term is very close tok-th derivative. Thus we obtain the estimate
Dkp(n)1Ckn%k/2p(n 1) (#O(n%1/2) ) asn| υ, (1.2)
whereCk1(ϑ/Ö6 )k estimate of. (Gupta's asymptoticDkp(n) in [6] is incorrect.) ` Gupta's computations led him to the same conjecture as Good's aboutDkp(n) alternating up to somen0(k) and then immediately becoming positive, but Gupta conjectured thatn0(k)ςk3ask| υ.
Another easy proof thatDkp(n) is positive for largencan be obtained by applying the theorem of Bateman and Erd.o. s [4]. They showed that ifpA(n) denotes the number of partitions ofninto summands taken from some setAof positive integers (repetitions allowed), thenDkpA(n)³0 for all largenif and only if the greatest common divisor of each subsetBÍAwithïA \ Bï 1k T1. Bhealquo  tE dn.odrmetaa nasie slt iresu .s far too general, though, to provide information about initial segments ofDkpA(n).
- 3 -
This paper carries the investigation ofDkp(n) further, and largely settles the Good-Gupta conjectures. The main result is the following.
Theorem. There is a k0so that if k³k0, then there is an integer n0(k)such that (%1 )nDkp(n)20for0σn0n0(k)andDkp(n)³0for n³n0(k). Furthermore,
n0(k)ς__62_k2( logk)2as k| υ.(1.3) ϑ
With more work it would probably be possible to establish the above result for allk. Such an extension would require replacing various O-estimates by explicit numerical bounds. We should note that the above result does not exclude the possibility that Dkp(n)10 might occur. In fact, the proof shows that for each largek,Dkp(n)10 can hold for at most one value ofnbe shown with more effort that values of, and it can k for whichDkp(n)10 occurs for somenare very rare. is probably true that It Dkp(n)10 has only ®nitely many solutions among all pairsk,n, but this conjecture seems to be hard to prove.
The asymptotic approximation (1.3) is not very accurate for smallk. For example, from the computational results quoted in [5c], it appears thatn0( 30 )115416. Now fork130,ϑk5/21 while 615486. 49... ,ϑ%2k2( logk)216329. 32... . proof The of (1.3) can be used to obtain more accurate estimates ofn0(k), however.
2. Intuitive explanation of result
IfF(z) denotes the generating function ofp(n),
- 4 -
υ F(z)1Sp(n)zn, n10 then it is well known (and easy to see) that υ F(z)1P( 1%zm)%1. m11 If we de®neFk(z) to be the generating function ofDkp(n), υ n Fk(z)1SDkp(n)z, n10
then υ Fk(z)1( 1%z)kF(z)1( 1%z)kP( 1%zm)%1.(2.4) m11 The theorem could be proved by investigating the analytic behavior ofFk(z), but we will only useFk(z) to explain why the Good-Gupta conjectures are true. The basic philosophy in the use of generating functions for asymptotic analysis is that the singularities of the function determine the behavior of the coef®cients. Generally speaking, a dominant singularity (i.e., one near which the function grows faster than near other points) at 1 corresponds to a monotone increasing sequence, while a dominant singularity at -1 corresponds to an alternating sequence. The functionF(z) has the unit circle as its natural boundary. However, as was shown by Hardy and Ramanujan [7], F(z) is most singular (i.e., grows fastest) near 1, is next most singular at -1, and is much better behaved away from those two points. This led them to the following re®nementof (1.1):
- 5 -
(%1 )nd ______ _   p(n)1_ __2ϑ1__Ö_2`_ _d_d n(_ln%1/2exp (Cln) )#2ϑd_n(_l%n1exp (Cln/2 ) ) #O( exp (n1/2(C /3# Α (2.5)) ) )
for anyΑ 20. (Taking other points onïzï 11 into account led Hardy-Ramanujan to their famous asymptotic series [7].) The ®rst term on the right in (2.5) comes fromz11, the second fromz1 %1, and the remainder is the contribution of the rest of the circle.
The importance of the fact thatz11 is the dominant singularity ofF(z) andz1 %1 is next most dominant is that when we studyDkp(n), we deal with the generating functionFk(z)1( 1%z)kF(z effect of multiplying). TheF(z) by ( 1%z)kis that the singularity atz1 %1 increases in inthe function is increased by about 2 uence, as knear ¯ ¯ z1 % the other hand, the singularity at1. Onz11 diminishes in in Since uence.F(z) grows much faster than any polynomial in ( 1%z)%1asz|1, this diminution is fairly small very close toz11, and therefore for largen, the size ofDkp(n) largely re¯ects the in uence of the singularity atz1 for small1. However,n, this diminution is nontrivial, ¯ and allowsz1 % All the other points on1 to dominate.ïzï 11 make contributions that are still smaller than that ofz1 % reason that the transition from alternation of1. The signs to positivity is very sharp is that in the transition zone, the singularity atz11 begins to dominate very rapidly. Let us write
Dkp(n)1a(n)#(%1 )nb(n)#c(n) ,
wherea(n) is the positive contribution fromz11,b(n) is the absolute value of the contribution fromz1 %1, andc(n in the transition region) is the remainder. Then a(n#1 )%a(n) is about 2 (b(n#1 )%b(n) ), and is much larger thanc(n), so that onceDkp(n) becomes nonnegative, it stays nonnegative.
- 6 -
The above presents an intuitive explanation of the mechanism that causes the Good-Gupta phenomenon of alternation followed by abrupt transition to positivity. This explanation could be developed into a rigorous proof, using relatively simple analytic methods. The estimates in the transitional region between alternation of signs and positivity would in fact be fairly simple, using the rough estimates of [7]. However, the need to cover the range of small values ofnrequires more delicate analysis, and so the proof presented below uses the Rademacher convergent series expansion forp(n) [1,2,3,8]. The explanation above presents an intuitive picture of what's happening which is not obvious from the proof below, in which the analytic behavior of the generating function shows up only indirectly in the form of the Rademacher expansion (3.3).
3. Detailed proof We ®rst use a very simple argument to show that forklarge,Dkp(n) alternates in sign fornup to aboutk /2.
Proposition 3.1. For anyΑ Π10( 0 ,%10)there is a k1(Α)such that if k³k1(Α)and 0σnσ( 1/2% Α)k, then
(%1 )nDkp(n)20.
Proof that in the range 0. Noteσnσ( 1/2% Α)k, (%1 )nDkp(n)1j1Sn0(%1 )jîìnk%jp(j).
Now if 0σj0n,
- 7 -  
k%_k__%__n__#_j_#1__³_k_%__n__#1__³1# Α. ìînk%jîìn%j%111n%j n By the Hardy-Ramanujan approximation (1.1), we see thatp(j#1 )/ p(j)01# Αfor j³2m0(Α). Hence for everym1³m0we have
(3.1) n)jìînk%jp(j)³mën1S /m21ìíîìîn%k2mp( 2m)î%ìn%2mk%1p( 2m#1 )20 S(%1 j12m1
since each term is positive.
To deal with the remaining sum, we note that 2m1%1 2jm1S10%1(%1 )jìînk%jp(j)1îìknj1S0(%1 )jîìkn%jîìkn%1p(j). Now for 0σjσ2m1%1 andnσ( 1/2% Α)k, ìînk%jìînk%11i1jP1_kn __%%__nj_##_ii_1îìï_nk_ïj( 1#O(k%1 ,) )
(the constant in theO-notation depending onm1andΑ), so 2jm11S0%1(%1 )jìînk%jìîkn%1p(j)12jm1S10%1(%1 )jì ♠j1) îï_nk_ïp(j)#O(k%.(3.2)
The in®nite sum (2.1) forF(z) does not vanish on the segment [%( 1/2% Α 0 ]) , because it has the convergent in®nite product (2.2) in which all the terms are nonzero, and therefore for some≅ 1 ≅(Α)20, we must haveF(z)³ ≅for zÎ[%( 1/2% Α the partial sums of  Since ]. 0) ,the in®nite sum in (2.1) converge to F(z) uniformly on compact subsets of the unit disk, there is somem2such that for all
- 8 -
m³2m2%1, and allzÎ[%( 1/2% Α) , ], 0 m Sp(j)zj³ ≅/2. j10 We now selectm11max (m0,m2), so thatm1depends onΑalone, and discover from (3.2) that fork³k1(Α), 2m1S%1(%1 )jïìnj#O(k%1)³ ≅/4 , j10î_k_ïp(j) which proves the proposition.
We next consider slightly larger values ofn we recall the Rademacher. First convergent series expansion forp(n before, we let As) [1,2,3,8]. C1 ϑ( 2/3 )1/2,ln1(n%1/24 )1/2. Then, for anyn³1, 1υn)m1/2_d_dn_(ln%1sinh (Cm%1ln) p(n)1_ϑ2___ 1/_2_mS11Am( ) , where theAm(n) satisfy A1(n)11 andA2(n)1(%1 )nforn³1 , ïAm(n)ï σmfor allm,n³1. (TheAm(n) are known explicitly in terms of Dedekind sums [1,2,3,7,8].) We de®ne, form,n³1,
(3.4) (3.5)
ïRnï σ10f3(n).(3.10) Proof of Lemma. The estimates (3.9) and (3.10) can be veri®ed numerically for 1σnσ50 by computingp(n) ,f1(n), andf2(n). (Tables of values ofp(n) are contained in [1,7], for example, or they can be computed using the recurrences in [1,3,7].) Forn250, we use the estimate [3; pp. 191-192] ïmS1υ5Am(n)fm(n)ï σ2C2l%n1îíìCln/12#25%1sinh (Cln/4 )together with the explicit formulas forf3(n) andf4(n) to prove (3.9) and (3.10).
p(n)1 ϑ%12%1/2ìíîf1(n)#(%1 )nf2(n)#Rn.
Lemma 3.2. For all n³1,
 ïRnï σ_53_f2(n)
so that
υ Rn1SAm(n)fm(n) , m13
/2d __  fm(n)1m1dn(_ln%1sinh (Cm%1ln ,) ) andfm( 0 )10, and we let
- 9 -
- 10 - 
The estimate (3.9) is tight only for very smalln, while the constant 10 in (3.10) could easily be decreased with slightly more careful work. We next investigateDkp(n) for ranges ofnnot covered by Proposition 3.1.
Proposition 3.3. There are constants c1,k2, andΑ 20such that if k³k2, then the following estimates hold:
(a) For2k /5σnσk%2,
ïDkf1(n)ï σc1k1/2îìkn.
(b) For k%1σnσk#1, ïDkf1(n)ï σc1k5exp (c1k1/2). (c) For k#2σn, ïDkf1(n)ï σc1n%k/10exp (c1n1/2). (d) For( 1/2% Α)kσnσk /2, 23ì ïDkf1(n)ï σ___ 10îkn.
Proof the proof of Rademacher's convergent series (3.3) (see [2; p. 109], for. From example) we ®nd that f1(n)1 ___2a_i_(b)t%5/2exp (t# Χ l2t%1)dt, (3.15) n ϑ where