partition.fn.diff

Description

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 ...

Informations

• Publié par: Vofeg
• Nombre de lectures: 9
• Langue: English

Extrait

Differences of the partition function

A. M. Odlyzko AT&T Bell Laboratories Murray Hill, New Jersey 07974

ABSTRACT

Letp(n) denote the number of unrestricted partitions ofn, and let

Dp(n)1p(n)%p(n%1 ),D k p(n)1 D(D k%1 p) (n note answers several). This

questions about the behavior of thek-differenceD k p(n) by proving that ifkis large

enough, there is an integern 0 (k) such thatD k p(n) alternates in sign forn0n 0 (k) and is nonnegative forn³n 0 (k). It is also shown thatn 0 (k)ς _ ϑ _6 2 _ k 2 ( logk) 2 as

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 differenceD k foffis then de®ned recursively byD k f1 D(D k%1 f few years ago, I. J. Good [5a] asked). A about the behavior ofD k p(n), wherep(n) denotes the number of unrestricted partitions ofn. He initially conjectured [5a] that ifk23, then the sequenceD k p(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,D k p(n)20 forn suf®ciently large. I. J. Good [5b] even made the stronger conjecture that for eachk, there is ann 0 (k) such thatD k p(n) alternates in sign forn0n 0 (k), andD k p(n)³0 for n³n 0 (k also suggested that 6). He (k%1 ) (k%2 )#k 3 /2 might be a good approximation ton 0 (k further computations by R. A. Gaskins led I. J. Good to). Some revise his conjecture about the size ofn 0 (k), and suggest thatϑk 5/2 might 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 ofD k p(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 thatD 2 p(n)³0 forn³2, whileD 2 p( 0 )11,D 2 p( 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,D k p(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 _ n d _ (l n %1 exp (Cl n ) )#O( exp ( (C /2# Α)n 1/2  ,) ) (1.1) 2ϑ for everyΑ 20, whereC1 ϑ( 2/3 ) 1/2 andl n 1(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

D k p(n)1C k n %k/2 p(n 1) (#O(n %1/2 ) ) asn| υ, (1.2)

whereC k 1(ϑ/ Ö 6   ) k  estimate of. (Gupta's asymptoticD k p(n) in [6] is incorrect.) ` Gupta's computations led him to the same conjecture as Good's aboutD k p(n) alternating up to somen 0 (k) and then immediately becoming positive, but Gupta conjectured thatn 0 (k)ςk 3 ask| υ.

Another easy proof thatD k p(n) is positive for largencan be obtained by applying the theorem of Bateman and Erd . o .  s [4]. They showed that ifp A (n) denotes the number of partitions ofninto summands taken from some setAof positive integers (repetitions allowed), thenD k p A (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 ofD k p A (n).

- 3 -

This paper carries the investigation ofD k p(n) further, and largely settles the Good- Gupta conjectures. The main result is the following.

Theorem. There is a k 0 so that if k³k 0 , then there is an integer n 0 (k)such that (%1 ) n D k p(n)20for0σn0n 0 (k)andD k p(n)³0for n³n 0 (k). Furthermore,

n 0 (k)ς __6 2 _ k 2 ( logk) 2 as 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 D k p(n)10 might occur. In fact, the proof shows that for each largek,D k p(n)10 can hold for at most one value ofnbe shown with more effort that values of, and it can k for whichD k p(n)10 occurs for somenare very rare. is probably true that It D k p(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 thatn 0 ( 30 )115416. Now fork130,ϑk 5/2 1 while 615486. 49... ,ϑ %2 k 2 ( logk) 2 16329. 32... . proof The of (1.3) can be used to obtain more accurate estimates ofn 0 (k), however.

2. Intuitive explanation of result

IfF(z) denotes the generating function ofp(n),

- 4 -

υ F(z)1 S p(n)z n , n10 then it is well known (and easy to see) that υ F(z)1 P ( 1%z m ) %1 . m11 If we de®neF k (z) to be the generating function ofD k p(n), υ n F k (z)1 S D k p(n)z, n10

(2.1)

(2.2)

(2.3)

then υ F k (z)1( 1%z) k F(z)1( 1%z) k P ( 1%z m ) %1 .(2.4) m11 The theorem could be proved by investigating the analytic behavior ofF k (z), but we will only useF k (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 ) n d ______ _    p(n)1 _ __ 2ϑ 1 __ Ö _ 2 ` _   _ d _ d   n ( _ l n %1/2 exp (Cl n ) )# 2ϑd _ n ( _ l % n 1 exp (Cl n /2 ) ) #O( exp (n 1/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 studyD k p(n), we deal with the generating functionF k (z)1( 1%z) k F(z effect of multiplying). TheF(z) by ( 1%z) k is that the singularity atz1 %1 increases in inthe function is increased by about 2 uence, as k near ¯ ¯ z1 % the other hand, the singularity at1. Onz11 diminishes in in Since uence.F(z) grows much faster than any polynomial in ( 1%z) %1 asz|1, this diminution is fairly small very close toz11, and therefore for largen, the size ofD k p(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

D k p(n)1a(n)#(%1 ) n b(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 onceD k p(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,D k p(n) alternates in sign fornup to aboutk /2.

Proposition 3.1. For anyΑ Π10( 0 , %10 )there is a k 1 (Α)such that if k³k 1 (Α)and 0σnσ( 1/2% Α)k, then

(%1 ) n D k p(n)20.

Proof that in the range 0. Noteσnσ( 1/2% Α)k, (%1 ) n D k p(n)1 j1 S n 0 (%1 ) j î ì n k %j ← ♠ p(j).

Now if 0σj0n,

- 7 -  

k % _ k __ % __ n __ # _ j _ #1 __ ³ _ k _ % __ n __ #1 __ ³1# Α. ì î n k %j ♠ î← ì n%j%1 ← ♠ 1 1 n%j n By the Hardy-Ramanujan approximation (1.1), we see thatp(j#1 )/ p(j)01# Αfor j³2m 0 (Α). Hence for everym 1 ³m 0 we have

(3.1) n ) j ì î n k %j ← ♠ p(j)³ m ë n 1 S  / m 2 ♥ 1 ì í î ì î n% k 2m ♠ ← p( 2m) î % ì n%2m k %1 ← ♠ p( 2m#1 ) ← ↔ ♠ 20 S (%1 j12m 1

since each term is positive.

To deal with the remaining sum, we note that 2m 1 %1 2 j m 1 S 1 0 %1 (%1 ) j ì î n k %j ← ♠ p(j)1 î ì k n ← ♠ j1 S 0 (%1 ) j î ì k n%j î ì ← ♠ k n ♠ ← %1 p(j). Now for 0σjσ2m 1 %1 andnσ( 1/2% Α)k, ì î n k %j ♠ ← ì î n k ♠ ← %1 1 i1 j P 1 _ k n  __ % % __ n j _ # # _ i i _ 1 î ì ï _ n k _ ♠ ï ← j ( 1#O(k %1  ,) )

(the constant in theO-notation depending onm 1 andΑ), so 2 j m 1 1 S 0 %1 (%1 ) j ì î n k %j ← ì♠ î k n ← ♠ %1 p(j)1 2 j m 1 S 1 0 %1 (%1 ) j ì ♠ j 1 ) î ï _ n k _ ← ï 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 somem 2 such that for all

- 8 -

m³2m 2 %1, and allzÎ[%( 1/2% Α) , ], 0 m S p(j)z j ³ ≅/2. j10 We now selectm 1 1max (m 0 ,m 2 ), so thatm 1 depends onΑalone, and discover from (3.2) that fork³k 1 (Α), 2m 1 S %1 (%1 ) j ï ì n ♠ j #O(k %1 )³ ≅/4 , j10 î _ k _ ← ï p(j) which proves the proposition.

(3.3)

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 ,l n 1(n%1/24 ) 1/2 . Then, for anyn³1, 1 υ n)m 1/2 _ d _ d n _ (l n %1 sinh (Cm %1 l n ) p(n)1 _ ϑ2 ___  1/ _ 2 _ m S 11 A m ( ) , where theA m (n) satisfy A 1 (n)11 andA 2 (n)1(%1 ) n forn³1 , ïA m (n)ï σmfor allm,n³1. (TheA m (n) are known explicitly in terms of Dedekind sums [1,2,3,7,8].) We de®ne, form,n³1,

(3.4) (3.5)

(3.9)

and

ïR n ï σ10f 3 (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) ,f 1 (n), andf 2 (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] ï m S 1 υ 5 A m (n)f m (n)ï σ2C 2 l % n 1 î í ì Cl n /12#25 %1 sinh (Cl n /4 ) ↔ ♠ ← together with the explicit formulas forf 3 (n) andf 4 (n) to prove (3.9) and (3.10).

p(n)1 ϑ %1 2 %1/2 ì í î f 1 (n)#(%1 ) n f 2 (n)#R n ♠ ← ↔ .

Lemma 3.2. For all n³1,

(3.7)

(3.8)

  ïR n ï σ _ 5 3 _ f 2 (n)

(3.6)

so that

υ R n 1 S A m (n)f m (n) , m13

/2 d __   f m (n)1m 1 dn ( _ l n %1 sinh (Cm %1 l n  ,) ) andf m ( 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 investigateD k p(n) for ranges ofnnot covered by Proposition 3.1.

Proposition 3.3. There are constants c 1 ,k 2 , andΑ 20such that if k³k 2 , then the following estimates hold:

(a) For2k /5σnσk%2,

ïD k f 1 (n)ï σc 1 k 1/2 î ì k n ♠ ← .

(b) For k%1σnσk#1, ïD k f 1 (n)ï σc 1 k 5 exp (c 1 k 1/2 ). (c) For k#2σn, ïD k f 1 (n)ï σc 1 n %k/10 exp (c 1 n 1/2 ). (d) For( 1/2% Α)kσnσk /2, 23 ì ïD k f 1 (n)ï σ ___  10 î k n ← ♠ .

(3.11)

(3.12)

(3.13)

(3.14)

Proof the proof of Rademacher's convergent series (3.3) (see [2; p. 109], for. From example) we ®nd that f 1 (n)1  ___ 2 a _ i _ ( ′ b) t %5/2 exp (t# Χ l 2 t %1 )dt, (3.15) n ϑ where