.PH ""
.nr Pt 1
.EQ
delim $$
gsize 12
define Cbar % size 9 bold up 14 | back 35 size 12 roman C %
.EN
.am DE
.sp
..
.ds HP 12 12 12 12 12 12 12
.ds HF 3 3 3 3 3 3 3
.ls 1
.ce 99
.B
.S 12
Differences of the partition function
.R
.sp
.I
A. M. Odlyzko
.R
.sp .2
AT&T Bell Laboratories
Murray Hill, New Jersey 07974
.sp 1.5
.B
ABSTRACT
.R
.ce 0
.sp
.ls 2
.P
Let $p(n)$ denote the number of unrestricted partitions
of $n$, and let $DELTA p(n) ~=~ p(n) ~-~ p(n-1)$,
$DELTA sup k ~p(n) ~=~ DELTA ( DELTA sup k-1 ^p) (n)$.
This note answers several questions
about the behavior of the $k$-difference $DELTA sup k ^p(n)$
by proving that if $k$ is large enough, there is an integer
$n sub 0 ^(k)$ such that $DELTA sup k ^p(n)$ alternates
in sign for $n ~<~ n sub 0 ^(k)$ and is nonnegative
for $n ~>=~ n sub 0 ^(k)$.
It is also shown that $n sub 0 ^(k) ~wig~ 6 over {pi sup 2} ~k sup 2 ^( log ^k ) sup 2$
as $k ~->~ inf$.
.bp
.ls 1
.ce 99
.B
Differences of the partition function
.R
.sp
.I
A. M. Odlyzko
.R
.sp .2
AT&T Bell Laboratories
Murray Hill, New Jersey 07974
.ce 0
.sp
.nf
.ta 4i
	Dedicated to Paul Erdo\*:s on the occasion
	of his 75th Birthday.
.fi
.sp
.ls 2
.H 1 "Introduction"
If $f(n)$ is any function on the nonnegative integers,
define its first difference $DELTA f$ by
$DELTA f (n) ~=~ f(n) ^-^ f(n-1)$ for $n ~>=~ 1$,
$DELTA f (0) ~=~ f(0)$.
The $k$-th difference $DELTA sup k ^f$ of $f$ is then defined
recursively by $DELTA sup k ^f ~=~ DELTA ^( DELTA sup k-1 ^f)$.
A few years ago, I. J. Good [5a] asked about the behavior
of $DELTA sup k ^p(n)$, where $p(n)$ denotes the number of
unrestricted partitions of $n$.
.pn 2
.PH "''- \\\\nP -''"
He initially conjectured [5a] that if $k ~>~ 3$, then the
sequence $DELTA sup k ^p(n)$, $n ~=~ 0,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 fixed $k$,
$DELTA sup k ^p(n) ~>~ 0$ for $n$ sufficiently large.
I. J. Good [5b] even made the stronger conjecture that for
each $k$, there is an $n sub 0 ^(k)$ such that $DELTA sup k ^p(n)$
alternates in sign for $n ~<~ n sub 0 ^(k)$, and
$DELTA sup k ^p(n) ~>=~ 0$ for $n ~>=~ n sub 0 ^(k)$.
He also suggested that $6(k-1) ^(k-2) ~+~ k sup 3 /2$ might
be a good approximation to $n sub 0 ^(k)$.
Some further computations by R. A. Gaskins led I. J. Good to
revise his conjecture about the size of $n sub 0 ^(k)$, and suggest
that $pi ^k sup 5/2$ might be a good approximation to it [5c].
.P
At about the same time as the first publication of I. J. Good's
problem, the same question about the sign of $DELTA sup k ^p(n)$
was also raised independently by G. E. Andrews, and was
answered by H. Gupta [6].
Gupta noted that $DELTA p(n) ~>~ 0$ for all $n$, and gave a
simple proof of the result that
$DELTA sup 2 ^p(n) ~>=~ 0$ for $n ~>=~ 2$, while $DELTA sup 2 ^p(0) ~=~ 1$,
$DELTA sup 2 ^p(1) ~=~ -1$.
Gupta also noted that it can be shown easily using the
Hardy-Ramanujan-Rademacher series [1,2,3,7,8] for $p(n)$
that for each $k$, $DELTA sup k ^p(n) ~>~ 0$ if $n$ is
sufficiently large.
In fact, this result can be obtained from some of the earliest of
the Hardy-Ramanujan approximations [7] to $p(n)$:
.DS 3
.EQ (1.1)
p(n) ~=~ 1 over {2^ pi ^sqrt 2} ~d over dn ~( lambda sub n sup -1
~exp (C lambda sub n )) ~+~ O ( exp (( C/2 + epsilon ) n sup 1/2 )) ^,
.EN
.DE
for every $epsilon ~>~ 0$, where $C ~=~ pi ( 2/3 ) sup 1/2$ and
$lambda sub n ~=~ ( n ^-^ 1/24 ) sup 1/2$.
The $k$-th difference of the second term on the right side of
(1.1) is of the same order of magnitude as that term (for $k$ fixed,
$n ~->~ inf$), while the $k$-th difference of the first
term is very close to its $k$-th derivative.
Thus we obtain the estimate
.DS 3
.EQ (1.2)
DELTA sup k ^p(n) ~=~ C sub k ~n sup {-^ k/2} ~p(n) ^( 1 ~+~ O( n sup {-^ 1/2} )) ~~roman as~~
n ~->~ inf ^,
.EN
.DE
where $C sub k ~=~ ( pi / sqrt 6 ) sup k$.
(Gupta's asymptotic estimate of $DELTA sup k ~p(n)$ in
[6] is incorrect.)
Gupta's computations led him to the same conjecture as Good's
about $DELTA sup k ^p(n)$ alternating up to some $n sub 0 ^(k)$ and
then immediately becoming positive, but Gupta conjectured that
$n sub 0 ^(k) ~wig~ k sup 3$ as $k ~->~ inf$.
.P
Another easy proof that $DELTA sup k ^p(n)$ is positive for large
$n$ can be obtained by applying the theorem of Bateman and
Erdo\*:s [4].
They showed that if $p sub A ^(n)$ denotes the number of partitions
of $n$ into summands taken from some set $A$ of positive integers
(repetitions allowed), then $DELTA sup k ^p sub A ^(n) ~>=~ 0$
for all large $n$ if and only if the greatest common divisor of each
subset $B ~!subset~ A$ with $| A ^\e^ B | ~=~ k$ is equal to 1.
The Bateman and Erdo\*:s result is far too general, though,
to provide information about initial segments of $DELTA sup k ^p sub A ^(n)$.
.P
This paper carries the investigation of $DELTA sup k ^p(n)$ further,
and largely settles the Good-Gupta conjectures.
The main result is the following.
.sp
.I
Theorem.
There is a $k sub 0$ so that if $k ~>=~ k sub 0$, then there is
an integer $n sub 0 ^(k)$ such that $( -1 ) sup n ~DELTA sup k ^p(n) ~>~ 0$
for $0 ~<=~ n ~<~ n sub 0 ^(k)$ and $DELTA sup k ^p(n) ~>=~ 0$ for
$n ~>=~ n sub 0 ^(k)$.
Furthermore,
.R
.DS 3
.EQ (1.3)
n sub 0 ^(k) ~wig~ 6 over {pi sup 2} ~k sup 2 ^( log ^ k ) sup 2 ~~as~~
k ~->~ inf ~.
.EN
.DE
.P
With more work it would probably be possible to establish the
above result for all $k$.
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 $DELTA sup k ^p(n) ~=~ 0$ might occur.
In fact, the proof shows that for each large $k$, $DELTA sup k ^p(n) ~=~ 0$
can hold for at most one value of $n$, and it can be shown with
more effort that values of $k$ for which $DELTA sup k ^p(n) ~=~ 0$
occurs for some $n$ are very rare.
It is probably true that $DELTA sup k ^p(n) ~=~ 0$ has only finitely
many solutions among all pairs $k,n$,
but this conjecture seems to be hard to prove.
.P
The asymptotic approximation (1.3) is not very accurate
for small $k$.
For example, from the computational results quoted in [5c],
it appears that $n sub 0 ^(30) ~=~ 15416$.
Now for $k ~=~ 30$, $pi ^k sup 5/2 ~=~ 15486.49...,$ while
$6 ^ pi sup -2 ~k sup 2 ^( log ^k ) sup 2 ~=~ 6329.32...^$.
The proof of (1.3) can be used to obtain more accurate
estimates of $n sub 0 ^(k)$, however.
.H 1 "Intuitive explanation of result"
If $F(z)$ denotes the generating function of $p(n)$,
.DS 3
.EQ (2.1)
F(z) ~=~ sum from n=0 to inf ~p(n) ^z sup n ^,
.EN
.DE
then it is well known (and easy to see) that
.DS 3
.EQ (2.2)
F(z) ~=~ prod from m=1 to inf ~( 1 ^-^ z sup m ) sup -1 ~.
.EN
.DE
If we define $F sub k ^(z)$ to be the generating function of
$DELTA sup k ^p(n)$,
.DS 3
.EQ (2.3)
F sub k ^(z) ~=~ sum from n=0 to inf ~DELTA sup k ^p(n) ^z sup n ^,
.EN
.DE
then
.DS 3
.EQ (2.4)
F sub k ^(z) ~=~ (1 ^-^ z ) sup k ~F(z) ~=~ ( 1 ^-^ z ) sup k ~prod from
m=1 to inf ~( 1 ^-^ z sup m ) sup -1 ~.
.EN
.DE
The theorem could be proved by investigating the analytic behavior
of $F sub k ^(z)$,
but we will only use $F sub k ^(z)$ to explain why the
Good-Gupta conjectures are true.
.P
The basic philosophy in the use of generating functions for
asymptotic analysis is that the singularities of the function
determine the behavior of the coefficients.
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 function $F(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 refinement of (1.1):
.DS 3
.EQ
p(n) ~=~ 1 over {2 ^ pi ^sqrt 2} ~d over dn ^( lambda sub n sup {-^1/2} ~
mark exp (C lambda sub n )) ~+~ {( -1 ) sup n} over {2^ pi} ~d over dn
^( lambda sub n sup -1 ~exp (C lambda sub n /2 ))
.EN
.sp
.EQ (2.5)
~ lineup +~ O( exp ( n sup 1/2 ^( C/3 ^+^ epsilon )))
.EN
.DE
for any $epsilon ~>~ 0$.
(Taking other points on $| z | ~=~ 1$ into account led Hardy-Ramanujan
to their famous asymptotic series [7].)
The first term on the right in (2.5) comes from $z=1$, the second
from $z^=^ -1$, and the remainder is the contribution of the
rest of the circle.
.P
The importance of the fact that $z=1$ is the dominant singularity
of $F(z)$ and $z ^=^ -1$ is next most dominant is that when
we study $DELTA sup k ^p(n)$, we deal with the generating function
$F sub k ^(z) ~=~ (1-z ) sup k ~F(z)$.
The effect of multiplying $F(z)$ by $(1-z ) sup k$ is that the
singularity at $z ^=^ -1$ increases in influence, as the function
is increased by about $2 sup k$ near $z ^=^ -1$.
On the other hand, the singularity at $z=1$ diminishes in influence.
Since $F(z)$ grows much faster than any polynomial in $(1-z ) sup -1$
as $z ~->~ 1$, this diminution is fairly small very close to $z=1$,
and therefore for large $n$, the size of $DELTA sup k ^p(n)$ largely
reflects the influence of the singularity at $z=1$.
However, for small $n$, this diminution is nontrivial, and allows
$z ^=^ -1$ to dominate.
All the other points on $| z | ~=~ 1$ make contributions that
are still smaller than that of $z ^=^ -1$.
The reason that the transition from alternation of
signs to positivity is very sharp is that in the
transition zone, the singularity at $z ^=^ 1$ begins
to dominate very rapidly.
Let us write
.DS 3
.EQ
DELTA sup k ^p(n) ~=~ a(n) ~+~ ( -1 ) sup n ~b(n) ~+~ c(n) ^,
.EN
.DE
where $a(n)$ is the positive contribution from $z ^=^ 1$,
$b(n)$ is the absolute value of the contribution from
$z ^=^ -1$, and $c(n)$ is the remainder.
Then in the transition region $a(n+1) ~-~ a(n)$ is about
$2(b(n+1) ~-~ b(n))$, and is much larger than $c(n)$, so
that once $DELTA sup k ^p(n)$ becomes nonnegative, it stays
nonnegative.
.P
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 of $n$
requires more delicate analysis, and so the proof presented
below uses the Rademacher convergent series expansion for $p(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).
.H 1 "Detailed proof"
We first use a very simple argument to show that for $k$
large, $DELTA sup k ^p(n)$ alternates in sign for $n$ up to
about $k/2$.
.sp
.I
Proposition 3.1.
For any $epsilon ~member~ ( 0, ^10 sup -10 )$ there is a $k sub 1 ^( epsilon )$
such that if $k ~>=~ k sub 1 ^( epsilon )$ and
$0 ~<=~ n ~<=~ ( 1/2 ~-~ epsilon )k$, then
.DS 3
.EQ
(-1 ) sup n ~DELTA sup k ^p(n) ~>~ 0 ~.
.EN
.DE
.R
\f2Proof\f1.
Note that in the range $0 ~<=~ n ~<=~ ( 1/2 ~-~ epsilon ) k$,
.DS 3
.EQ
( -1 ) sup n ~DELTA sup k ^p(n) ~=~ sum from j=0 to n ~( -1 ) sup j ~
left ( {pile {k above n-j}} right ) ~p( j) ~.
.EN
.DE
Now if $0 ~<=~ j ~<~ n$,
.DS 3
.EQ
left ( {pile {k above n-j}} right ) ~left ( {pile {k above n-j-1}} right ) sup -1
~=~ {k ^-^ n+j+1} over {n-j} ~>=~ {k ^-^ n+1} over n ~>=~ 1 ~+~ epsilon ~.
.EN
.DE
By the Hardy-Ramanujan approximation (1.1), we see that
$p(j+1) ^/^ p(j) ~<~ 1 ~+~ epsilon$ for $j ~>=~ 2 m sub 0 ^( epsilon )$.
Hence for every $m sub 1 ~>=~ m sub 0$ we have
.DS 3
.EQ (3.1)
~~~~
.EN
.sp
.EQ
sum from {j= 2 m sub 1} to n ^( -1 ) sup j ^left ( {pile {k above n-j}} right )
^ p(j) ~>=~ sum from {m= m sub 1} to {left floor n/2 right floor} ~
left { left ( {pile {k above n- 2m}} right ) ^p(2m) ^-^ left ( {pile {k above n-2m-1}} right )
^p( 2m+1 ) right } ^>^ 0
.EN
.DE
since each term is positive.
.P
To deal with the remaining sum, we note that
.DS 3
.EQ
sum from j=0 to {2 m sub 1 -1} ^( -1 ) sup j ^ left ( {pile {k above n-j}} right )
^p(j) ~=~ left ( {pile {k above n}} right ) ~sum from j=0 to {2 m sub 1 -1}
~( -1 ) sup j ^ left ( {pile {k above n-j}} right ) ~left ( {pile {k above n}} right ) sup -1 ~p(j)~.
.EN
.DE
Now for $0 ~<=~ j ~<=~ 2 m sub 1 -1$
and $n ~<=~ ( 1/2 ^-^ epsilon ) k$,
.DS 3
.EQ
left ( {pile {k above n-j}} right ) ^left ( {pile {k above n}} right ) sup -1
~=~ prod from i=1 to j~{n^-^ j+i} over {k ^-^ n+i} ~=~ left ( n over k right ) sup j ~
( 1 ~+~ O( k sup -1 )) ^,
.EN
.DE
(the constant in the $O$-notation depending on $m sub 1$ and $epsilon$), so
.DS 3
.EQ (3.2)
sum from j=0 to {2 m sub 1 -1} ~( -1 ) sup j ^ left ( {pile {k above n-j}} right )
^left ( {pile {k above n}} right ) sup -1 ~p(j) ~=~ sum from j=0 to {2 m sub 1 -1}
^( -1 ) sup j ~left ( n over k right ) sup j ~p(j) ~+~ O( k sup -1 ) ~.
.EN
.DE
The infinite sum (2.1) for $F(z)$ does not vanish on the segment
$[- ^( 1/2 ^-^ epsilon ), ~0]$ because it has the convergent infinite
product (2.2) in which all the terms are nonzero, and therefore
for some $delta ~=~ delta ( epsilon ) ~>~ 0$, we must have
$F(z) ~>=~ delta$ for $z ~member~ [ -^ (1/2 ^-^ epsilon ), ~0]$.
Since the partial sums of the infinite sum in (2.1) converge to
$F(z)$ uniformly on compact subsets of the unit disk, there is
some $m sub 2$ such that for all $m ~>=~ 2^ m sub 2 -1$, and
all $z ~member~ [-^(1/2 ^-^ epsilon ), ~0]$,
.DS 3
.EQ
sum from j=0 to m ~p(j) z sup j ~>=~ delta /2 ~.
.EN
.DE
We now select $m sub 1 ~=~ max ( m sub 0 , ^m sub 2 )$, so that
$m sub 1$ depends on $epsilon$ alone, and discover from (3.2)
that for $k ~>=~ k sub 1 ^( epsilon )$,
.DS 3
.EQ
sum from j=0 to {2 m sub 1 -1} ~( -1 ) sup j ~left ( n over k right ) sup j
~p( j) ~+~ O ( k sup -1 ) ~>=~ delta /4 ^,
.EN
.DE
which proves the proposition.
.nf
.ta 6iR
	\(sq
.fi
.P
We next consider slightly larger values of $n$.
First we
recall the Rademacher convergent series expansion for $p(n)$
[1,2,3,8].
As before, we let
.DS 3
.EQ
C ~=~ pi ^( 2/3 ) sup 1/2 ~~,~~ lambda sub n ~=~ (n ~-~ 1/24 ) sup 1/2 ~.
.EN
.DE
Then, for any $n ~>=~ 1$,
.DS 3
.EQ (3.3)
p(n) ~=~ 1 over {pi ^ 2 sup 1/2} ~sum from m=1 to inf ~A sub m ^(n)
m sup 1/2 ~d over dn ^( lambda sub n sup -1 ~ sinh ( C m sup -1 ^lambda
sub n )) ^,
.EN
.DE
where the $A sub m ^(n)$ satisfy
.DS 3
.EQ (3.4)
A sub 1 ^(n) ~mark =~ 1 ~and~ A sub 2 ^(n) ~=~ ( -1 ) sup n ~~roman for~~
n ~>=~ 1 ^,
.EN
.sp
.EQ (3.5)
| A sub m ^( n) | ~lineup <=~ m ~~{roman {for~all}}~~ m, n ~>=~ 1 ~.
.EN
.DE
(The $A sub m ^(n)$ are known explicitly in terms of Dedekind
sums [1,2,3,7,8].)
.P
We define, for $m,n ~>=~ 1$,
.DS 3
.EQ (3.6)
f sub m ^(n) ~=~ m sup 1/2 ~d over dn ^( lambda sub n sup -1 ~ sinh ( C m sup
-1 ^ lambda sub n )) ^,
.EN
.DE
and $f sub m ^(0) ~=~ 0$, and we let
.DS 3
.EQ (3.7)
R sub n ~=~ sum from m=3 to inf ~A sub m ^(n) ~f sub m ^(n) ^,
.EN
.DE
so that
.DS 3
.EQ (3.8)
p(n) ~=~ pi sup -1 ~2 sup {-^ 1/2} ~left { f sub 1 ^(n) ~+~ ( -1 ) sup n
~f sub 2 ^(n) ~+~ R sub n right } ~.
.EN
.DE
.sp
.I
Lemma 3.2.
For all $n ~>=~ 1$,
.R
.DS 3
.EQ (3.9)
| R sub n | ~<=~ 3 over 5 ~f sub 2 ^(n)
.EN
.DE
.I
and
.R
.DS 3
.EQ (3.10)
| R sub n | ~<=~ 10 ~f sub 3 ^(n)
~.
.EN
.DE
\f2Proof of Lemma\f1.
The estimates (3.9) and (3.10) can be verified numerically for
$1 ~<=~ n ~<=~ 50$ by computing $p(n), ~f sub 1 ^(n)$, and
$f sub 2 ^(n)$.
(Tables of values of $p(n)$ are contained in [1,7], for example,
or they can be computed using the recurrences in [1,3,7].)
For $n ~>~ 50$, we use the estimate [3; pp. 191-192]
.DS 3
.EQ
| sum from m=5 to inf ~A sub m ^(n) ~f sub m ^(n) | ~<=~ 2 ^C sup 2
^lambda sub n sup -1 ^left { C ^lambda sub n /12 ~+~ 25 sup -1 ~ sinh
(C ^ lambda sub n /4 ) right }
.EN
.DE
together with the explicit formulas for $f sub 3 ^(n)$ and
$f sub 4 ^(n)$ to prove (3.9) and (3.10).
.nf
.ta 6i
	\(sq
.fi
.P
The estimate (3.9) is tight only for very small $n$, while
the constant 10 in (3.10) could easily be decreased with slightly
more careful work.
.P
We next investigate $DELTA sup k ^p(n)$ for ranges of $n$ not
covered by Proposition 3.1.
.sp
.I
Proposition 3.3.
There are constants $c sub 1 , ^k sub 2$, and $epsilon ~>~ 0$ such
that if $k ~>=~ k sub 2$, then the following estimates hold:
.sp
(a) For $2k/5 ~<=~ n ~<=~ k ~-~ 2$,
.DS 3
.EQ (3.11)
| DELTA sup k ^f sub 1 ^(n) | ~<=~ c sub 1 ~k sup 1/2 ^left ( {pile {k above n}} right ) ~.
.EN
.DE
(b) For $k-1 ~<=~ n ~<=~ k+1$,
.DS 3
.EQ (3.12)
| DELTA sup k ^f sub 1 ^(n) | ~<=~ c sub 1 ~k sup 5 ~exp ( c sub 1 ^k sup 1/2 ) ~.
.EN
.DE
(c) For $k+2 ~<=~ n$,
.DS 3
.EQ (3.13)
| DELTA sup k ^f sub 1 ^(n) | ~<=~ c sub 1 ~n sup {-^k/10} ~exp ( c sub 1 ^n sup 1/2 )~.
.EN
.DE
(d) For $( 1/2 ^-^ epsilon )k ~<=~ n ~<=~ k/2$,
.DS 3
.EQ (3.14)
| DELTA sup k ^f sub 1 ^(n) | ~<=~ 23 over 10 ~left ( {pile {k above n}} right ) ~.
.EN
.DE
.R
.sp
\f2Proof\f1.
From the proof of Rademacher's convergent series (3.3) (see
[2; p. 109], for example) we find that
.DS 3
.EQ (3.15)
f sub 1 ^(n) ~=~ alpha over {2 ^pi ^i} ~int from {( beta )} ~t sup {-^ 5/2}
~exp ( t ~+~ gamma ^lambda sub n sup 2 ^t sup -1 ) ~dt ^,
.EN
.DE
where
.DS 3
.EQ (3.16)
alpha ~=~ pi sup 7/2 ~6 sup {-^ 3/2} ~~,~~ gamma ~=~ pi sup 2 /6 ^,
.EN
.DE
$beta$ is any constant with $beta ~>~ 0$, and $( beta )$ denotes
the straight line from $beta ~-~ i ^inf$ to $beta ~+~ i^ inf$.
Therefore, if
.DS 3
.EQ (3.17)
| z | ~e sup {gamma / beta} ~<~ 1 ^,
.EN
.DE
then
.DS 3
.EQ
sum from n=1 to inf ~f sub 1 ^(n) z sup n ~mark =~ alpha over {2^ pi ^i} ~
int from {( beta )} ~t sup {-^ 5/2} ~exp (t ~-~ gamma /(24t)) ~sum from n=1
to inf ~z sup n ~e sup {gamma ^n/t} ~dt
.EN
.sp
.EQ (3.18)
~~~~
.EN
.sp
.EQ
~lineup =~ alpha over {2^pi^ i} ~int from {( beta )} ~t sup {-^ 5/2} ~z
~exp (t ~+~ {23 gamma} over {24 t} ) ~dt over {1 ^-^ z ^e sup {gamma /t}} ^,
.EN
.DE
and so
.DS 3
.EQ
G sub k ^(z) ~mark =~ sum from n=1 to inf ~z sup n ~DELTA sup k ^f sub 1 ^(n)
.EN
.sp
.EQ (3.19)
~~~~
.EN
.sp
.EQ
~lineup =~ {alpha ^( 1-z ) sup k} over {2 ^pi^ i} ~int from {( beta )} ~t
sup {-^ 5/2} ~z~ exp ( t ~+~ {23 gamma} over {24t} ) ~dt over {1 ^-^ z ^e sup {gamma /t}} ~.
.EN
.DE
The expansion (3.18) has been obtained only under the assumption
(3.17), but the integral on the right hand side of (3.18) is
analytic in all of
$Cbar ^\e^ [ e sup {-^ gamma / beta} , ~inf )$ (i.e., the entire
complex plane with a slit along the positive real axis from
$e sup {-^ alpha / beta}$ to infinity removed).
Thus (3.19) gives an analytic continuation of $G sub k ^(z)$ to
the domain $Cbar ^\e^ [1, inf )$, provided that when $z$ is
real, $z ~member~ (0,1)$, we choose $beta ~>~ - gamma / log ~z$.
.P
We now use (3.19) to obtain bounds for $DELTA sup k ^f sub 1 ^(n)$.
If $Re (z) ~<~ 1$, $| 1-z | ~>=~ 1/100$, we choose $beta ~=~ 1000$,
and then for $Re (t) ~=~ beta$ we have
.DS 3
.EQ
left | {z^ exp (t ~+~ {23 gamma} over 24t )} over {1 ~-~ z ^e sup {gamma /t}}
right | ~<=~ c sub 2
.EN
.DE
for some constant $c sub 2 ~>~ 0$.
Therefore for some $c sub 3 ~>~ 0$,
.DS 3
.EQ (3.20)
| G sub k ^(z) | ~<=~ c sub 3 ^ | 1-z | sup k
.EN
.DE
holds for all $z$ with $Re (z) ~<~ 1$, $| 1-z | ~>=~ 1/100$.
.P
Suppose next that $Re (z) ~<~ 1$, $0 ~<~ | 1-z | ~<~ 1/100$.
In this case we let $w ~=~ 1 ~-~ Re (z)$ and $beta ~=~ 2^ gamma /w$.
Then
$| z | ~>=~ 1-w, ~| e sup {gamma /t} | ~<=~ e sup w/2$,
.DS 3
.EQ
left | 1 ~-~ z ^e sup {gamma /t} right | ~>=~(1-w) ^e sup {w/2} ~-~1 ~>=~ w/10^,
.EN
.DE
and so
.DS 3
.EQ (3.21)
| G sub k ^(z) | ~<=~ {c sub 4} over w ~ | 1-z | sup k ~exp ( 2^ gamma /w ) ~.
.EN
.DE
.P
We now use the estimates (3.20) and (3.21) to bound
$DELTA sup k ^f sub 1 ^(n)$.
We have
.DS 3
.EQ (3.22)
DELTA sup k ^f sub 1 ^(n) ~=~ 1 over {2^pi^i} ~int from S ~G sub k ^(z)
~dz over {z sup n+1} ^,
.EN
.DE
where $S$ is any simple closed curve around the origin in the
domain $Cbar ^\e^ [1, inf )$.
We will select a radius $r ~>~ 0$ later.
Given $r$, we choose $S$ to consist of $S sub 1$, that portion of
the circle $| z | ~=~ r$ that lies to the left of the line
$Re (z) ~=~ 1 ~-~ (2 ^gamma /n ) sup 1/2$ (which might be all of that circle)
together with $S sub 2$, the straight line segment formed
by the intersection of the disk $| z | ~<=~ r$ and the line
$Re (z) ~=~ 1 ~-~ (2^ gamma /n ) sup 1/2$ when there is such an
intersection.
By (3.20), we find that
.DS 3
.EQ
left | 1 over {2^pi^i} ~int from {S sub 1} ~G sub k ^(z) ~dz over
{z sup n+1} right | ~<=~ c sub 5 ~{(1+r ) sup k} over {r sup n} 
~+~ c sub 5 ^n sup 1/2 ^100 sup -k ^r sup -n ~exp (( 2 ^ gamma ^n ) sup 1/2 )~.
.EN
.DE
On the other hand, by (3.21) we find that when $S sub 2$ exists,
.DS 3
.EQ
left | 1 over {2^pi^i} ~int from {S sub 2} ~G sub k ^(z) ~dz over {z sup n+1}
right | ~<=~ c sub 6 ^n sup 1/2 ~exp ( ( 2^ gamma n ) sup 1/2 ) ^int from
{S sub 2} ~{ | 1-z | sup k} over {| z | sup n+1} ~ | dz | ~.
.EN
.DE
Hence we conclude that for any $r ~>~ 0$,
.DS 3
.EQ
| DELTA sup k ^f sub 1 ^(n) | ~mark <=~ c sub 7 ^( 1+ r ) sup k ^r sup -n
~+~ c sub 7 ^n sup 1/2 ^100 sup -k ^r sup -n ~exp (( 2 ^ gamma ^n ) sup 1/2 )
.EN
.sp
.EQ (3.23)
~~~~
.EN
.sp
.EQ
~lineup +~ c sub 8 ^n sup 1/2 ~exp (( 2 ^ gamma n ) sup 1/2 ) ^ int from 0
to omega ~{( 2^ gamma^ n sup -1 ^+^ v sup 2 ) sup k/2 ~~dv} over
{(1 ^-^ 2( 2 ^gamma /n ) sup 1/2 ^+^ 2 gamma /n ^+^ v sup 2 ) sup {(n+1) /2}} ^,
.EN
.DE
where
.DS 3
.EQ (3.24)
omega ~=~ left {
matrix {
lcol {0 above ( r sup 2 ~-~ 1+2 ( 2^ gamma /n ) sup 1/2 ~-~ 2^ gamma /n ) sup 1/2}
lcol {roman if ~r ~<=~ 1 ~-~ (2 ^ gamma /n ) sup 1/2 ^, above roman if ~r ~>~ 1 ~-~ (2^ gamma /n ) sup 1/2 ~.}
}
.EN
.DE
.P
For $2k/5 ~<=~ n ~<=~ k-2$, we now select $r ~=~ n/ (k-n)$.
We have for $k$ sufficiently large and
for $0 ~<=~ v ~<=~ omega$,
.DS 3
.EQ
{( 2^ gamma ^n sup -1 ~+~ v sup 2 ) sup k/2} over {( 1-2 (2^ gamma^ n sup -1 ) sup 1/2 ^+^ 2 gamma /n ^+^ v sup 2 ) sup (n+1)/2} ~mark <=~
{(2^ gamma ^n sup -1 ~+~ omega sup 2 ) sup k/2} over {(1- 2( 2^ gamma^ n sup -1 ) sup 1/2 ^+^ 2 gamma /n ^+^ omega sup 2 ) sup (n+1)/2}
.EN
.sp
.EQ
~lineup =~ {left ( r sup 2 ^-^ 1 right ) sup k/2} over {r sup n+1} ^,
.EN
.DE
so that
.DS 3
.EQ
| DELTA sup k ^f sub 1 ^(n) | ~mark <=~ c sub 9 ^(1+r ) sup k ^r sup -n ~+~
c sub 10 ^n sup 1/2 ^( r sup 2 ^-^ 1 ) sup k/2 ~r sup -n ~exp ( ( 2^ gamma
^n ) sup 1/2 )
.EN
.sp
.EQ (3.25)
~lineup <=~ c sub 11 ^(1+r ) sup k ^r sup -n ~<=~ c sub 12 ^k sup 1/2 ^left (
{pile {k above n}} right ) ~.
.EN
.DE
.P
For $k-1 ~<=~ n ~<=~ k+1$, we select $r ~=~ k$ and obtain from
(3.23) the bound
.DS 3
.EQ
| DELTA sup k ^f sub 1 ^(n) | ~mark <=~ c sub 13 ^k sup k-n ~+~ c sub 14
^k sup 3/2 ~exp (( 2^ gamma ^k ) sup 1/2 ) ~{left ( k sup 2 ^-^ 1 right ) sup k/2} over {k sup n+1}
.EN
.sp
.EQ (3.26)
~lineup <=~ c sub 15 ^k sup 5 ~exp (( 2^ gamma ^k ) sup 1/2 ) ~.
.EN
.DE
.P
Finally, for $k+1 ~<~ n$, we let $r ~->~ inf$ and obtain, for
$a ~=~ 1 ~-~ 2( 2^ gamma ^ n sup -1 ) sup 1/2 ~+~ 2^ gamma ^ n sup -1$,
.DS 3
.EQ
| DELTA sup k ^f sub 1 ^(n) | ~<=~ c sub 16 ^n sup 1/2 ~exp ((2^ gamma ^n
) sup 1/2 ) ~int from 0 to inf ~{(2^ gamma^ n sup -1 ~+~ v sup 2 ) sup k/2 ~~dv}
over {(1 ~-~ 2(2^gamma^ n sup -1 ) sup 1/2 ^+^ 2 gamma /n ^+^ v sup 2 ) sup (n+1)/2}
~.
.EN
.DE
Now the integral on the right side above is (for large $k$ and
$n ~>=~ k+2$)
.DS 3
.EQ
mark <=~ int from 0 to {n sup {-^ 1/10}} ~{(2^ n sup {-^ 1/5} ) sup k/2 ~dv}
over {( 1 ~-~ 2( 2 ^gamma ^n sup -1 ) sup 1/2 ) sup (n+1)/2} ~+~
int from {n sup {-^1/10}} to inf ~dv over {( 1 ~-~ 2( 2 ^gamma ^n sup -1 ) sup 1/2 ~+~ v sup 2 ) sup (n+1-k)/2}
.EN
.sp
.EQ
lineup <=~ 2 sup k ^n sup {-^ k/10} ~exp ( c sub 17 ^n sup 1/2 ) ~+~ int
from {n sup {-^ 1/5}} to inf ~{u sup {-^ 1/2} ~du} over
{( 1 ~-~ 2( 2^gamma ^n sup -1 ) sup 1/2 ~+~ u ) sup (n+1-k)/2}
.EN
.sp
.EQ
lineup <=~ 2 sup k ^n sup {-^ k/10} ~exp ( c sub 17 ^n sup 1/2 ) ~+~
( 1 ~-~ 2( 2 ^gamma^ n sup -1 ) sup 1/2 ~+~ n sup {-^ 1/5} ) sup {-^(n-1-k)/2} ^,
.EN
.DE
and this yields the estimate
.DS 3
.EQ (3.27)
| DELTA sup k ^f sub 1 ^(n) | ~<=~ c sub 18 ^n sup {-^ k/10} ~exp ( c sub 19
^n sup 1/2 ) ~.
.EN
.DE
.P
To complete the proof of the proposition, we consider
$( 1/2 ^-^ epsilon )k ~<=~ n ~<=~ k/2$, where $epsilon ~member~ (0, ^10 sup -10 )$
will be selected later.
We use the same contour of integration as before, with
$r ~=~ n/(k-n)$, except that we let
.DS 3
.EQ (3.28)
S sub 3 ~=~ left { z ~member~ S: ~ | z+r | ~<=~ k sup {-^ 1/3} right } ~.
.EN
.DE
Then, by using estimates similar to those developed earlier, but
bounding $| 1-z |$ on $S ^\e^ S sub 3$ more carefully, we obtain
.DS 3
.EQ
left | 1 over {2^pi^i} ~int from {S ^\e^ S sub 3} ~{G sub k ^(z)} over
{z sup n+1} ~dz right | ~mark <=~ c sub 20^ r sup -n ~max from {z ^member^ S ^\e^ S sub 3} ~ | 1-z | sup k
.EN
.sp
.EQ (3.29)
~~~~
.EN
.sp
.EQ
~lineup +~ c sub 21^ n sup 1/2 ^( r sup 2 ^-^ 1) sup k/2 ~r sup -n ~exp (( 2^ gamma ^n
) sup 1/2 ) ~.
.EN
.DE
Now for $z ~member~ S ^\e^ S sub 3$, and $k$ sufficiently large,
.DS 3
.EQ
| 1-z | ~<=~ (1+r) ^( 1 ^-^ k sup -2/3 /10 ) ^,
.EN
.DE
and so
for $k$ large,
.DS 3
.EQ (3.30)
left | 1 over {2^pi^i} ~int from {S ^\e^ S sub 3} ~{G sub k ^(z)} over
{z sup n+1} ~dz right | ~<=~ c sub 22 ^( 1+r ) sup k ^r sup -n ~exp ( -^
k sup 1/4 ) ~.
.EN
.DE
.P
We next estimate the integral over $S sub 3$ by the saddle
point method.
Using (3.19) and interchanging orders of integration, we obtain
.DS 3
.EQ (3.31)
1 over {2^pi^i} ~int from {S sub 3} ~{G sub k ^(z)} over {z sup n+1} ~dz
~=~ alpha over {2^pi^i} ~int from {( beta )} ~t sup {-^ 5/2} ~exp
(t ~+~ {23 gamma} over 24t ) dt ~cdot~ g(n, ^z,^t) ^,
.EN
.DE
where
.DS 3
.EQ
g(n,^z,^t) ~=~ 1 over {2^pi^i} ~int from {S sub 3} ~{z(1-z ) sup k} over
{1 ^-^ z ^e sup {gamma /t}} ~dz over {z sup n+1} ~.
.EN
.DE
Making the change of variable $z ~=~ -~ r ^e sup {i theta}$,
$-^ theta sub 0 ~<=~ theta ~<=~ theta sub 0$, where
$theta sub 0 ~wig~ r sup -1 ^k sup {-^1/3}$ as $k ~->~ inf$,
we find that
.DS 3
.EQ (3.32)
g(n,^z,^t) ~=~ {( -1 ) sup n-1 ^r sup 1-n} over {2^ pi} ~int from {-^ theta sub 0} to {theta sub 0}
~{( 1 ^+^ r ^e sup {i theta} ) sup k} over {1 ^+^ r ^e sup {i theta ^+^ gamma /t}}
~e sup {-^(n-1) i theta} ~d theta ~.
.EN
.DE
We now select $beta ~=~ 100$, say.
Then $gamma /t$ is bounded for all $t$ on the line from $beta ~-~ i^inf$
to $beta ~+~ i^inf$, and $1 ~+~ r~exp ( i theta ^+^ gamma /t)$ is
bounded away from 0.
Furthermore,
.DS 3
.EQ (3.33)
1 ~+~ r ^e sup {i theta} ~=~ (1+r) ~exp ( ir over 1+r ^theta ~-~ {r^ theta sup 2} over {2(1+r ) sup 2}
~+~ O( | theta | sup 3 )) ^,
.EN
.DE
where the constant in the $O$-term is independent of $r$.
(Recall that $1 ^-^ 10 sup -5 ~<=~ r ~<=~ 1$.)
Next $k r /( 1+r ) ~=~ n^ theta$, so
.DS 3
.EQ
g(n,^z,^t) ~mark =~ {( -1 ) sup n-1 ^r sup 1-n ^(1+r) sup k} over {2^ pi}
~int from {-^ theta sub 0} to {theta sub 0} ~{exp (-^ {r ^k^ theta sup 2} over {2(1+r ) sup 2} ~+~ O( k | theta | sup 3 ) ~+~ i^theta ) ~dt} over
{1 ~+~ r^ e sup {i theta ^+^ gamma /t}}
.EN
.sp
.EQ (3.34)
~~~
.EN
.sp
.EQ
~lineup =~ {( -1 ) sup n-1 ^r sup 1-n ^(1+r ) sup k+1} over {{sqrt {2^pi ^r^k}}}
~{1 ~+~ O( k sup {-^1/3} )} over {1 ~+~ r ^e sup {gamma /t}} ^,
.EN
.DE
and therefore
.DS 3
.EQ
DELTA sup k ^f sub 1 ^(n) ~mark =~ {alpha ( -1 ) sup n-1 ^r sup 1-n ^(1+r) sup k+1} over
{{sqrt {2^pi^r^k}}} ~1 over {2^pi^i} ~int from {( beta )}
~t sup {-^5/2} ~{exp (t ~+~ {23 gamma} over 24t )} over {1 ~+~ r^e sup {gamma /t}} ~dt
.EN
.sp
.EQ (3.35)
~~~~
.EN
.sp
.EQ
~lineup +~ O( k sup {-^ 5/6} ~( 1+r ) sup k ~r sup -n ) ~.
.EN
.DE
Let
.DS 3
.EQ (3.36)
h(r) ~=~ 1 over {2^pi^i} ~int from {( beta )} ~t sup {-^ 5/2} ~{exp (t ~+~ {23 gamma} over 24t )} over {1 ~+~ r ^e sup {gamma /t}} ~dt ~.
.EN
.DE
Then $h(r)$ is a continuous function of $r$ for $0 ~<~ r ~<~ 2$,
say, and we will evaluate $h(r)$ for $r ~<~ 1$ but close to 1.
Consider first $r ~>~ 1$.
Then we have (using the usual Bessel function expansions that
come up in Rademacher's proof)
.DS 3
.EQ
h(r) ~mark =~ 1 over {2^pi^i} ~int from {( beta )} ~t sup {-^ 5/2} ~
{exp (t ~+~ {23 gamma} over 24t )} over {r ^e sup {gamma /t} ^(1 ^+^ r sup -1 ^e sup {-^ gamma /t} )} ~dt
.EN
.sp
.EQ
~lineup =~ 1 over {2^pi^i} ~int from {( beta )} ~t sup {-^ 5/2} ~exp
(t ~+~ {23 gamma} over 24t ) ~sum from m=1 to inf ~( -1 ) sup m-1 ~r sup -m
~e sup {-m gamma /t} ~dt
.EN
.sp
.EQ
~lineup =~ sum from m=1 to inf ~( -1 ) sup m-1 ~r sup -m ~1 over {2^pi^i}
~int from {( beta )} ~t sup {-^ 5/2} ~exp ( t ~-~ (m ^-^ 23/24 ) gamma /t ) ~dt
.EN
.sp
.EQ
~lineup =~ sum from m=1 to inf ~( -1 ) sup m-1 ~r sup -m ~J sub 3/2 ~
( eta sub m ) ^( eta sub m /2 ) sup {-^ 3/2}
.EN
.sp
.EQ (3.37)
~lineup =~ pi sup {-^ 1/2} ^gamma sup -1 ~sum from m=1 to inf ~
{( -1 ) sup m-1 ^r sup -m} over {m ^-^ 23 over 24} ~left ( {sin ( eta sub m )}
over {eta sub m} ~-~ cos ( eta sub m ) right ) ^,
.EN
.DE
where $eta sub m ~=~ 2^ gamma sup 1/2 ^( m ~-~ 23/ 24 ) sup 1/2$.
Now
.DS 3
.EQ
left | sum from m=1000 to inf ~{( -1 ) sup m-1 ^r sup -m ^sin ( eta sub m )} over
{eta sub m ^( m ^-^ 23 over 24 )} right | ~<=~ 1 over {2^ gamma sup 1/2}
~sum from m=1000 to inf ~left ( m ~-~ 23 over 24 right ) sup {-^ 3/2}
.EN
.sp
.EQ (3.38)
~~~~
.EN
.sp
.EQ
~lineup <=~ 1 over {2^ gamma sup 1/2} ~int from 998 to inf ~u sup {-^ 3/2}
~du ~=~ gamma sup {-^ 1/2} ~998 sup {-^1/2} ~<=~ 0.025 ~.
.EN
.DE
On the other hand, for some $v ~member~ [m, ^m+1 ]$
.DS 3
.EQ
left ""
{r sup -m ^ cos ( eta sub m )} over {m ^-^ 23 over 24} ~mark -~ {r sup -m-1 ^ cos ( eta sub m+1 )} over
{m ^+^ 1 over 24} ~=~ -~ d over du ~{r sup -u ^ cos ( eta sub u )} over {u ^-^ 23 over 24}
right | sub u=v ^,
.EN
.sp
.EQ
~lineup =~ {cos ( eta sub v )} over {(v ^-^ 23 over 24 ) sup 2} ~+~
{gamma sup 1/2 ^sin ^( eta sub v )} over {( v ^-^ 23 over 24 ) sup 3/2}
~+~ {r sup -v ^( log ^r) ~ cos ( eta sub v )} over {v ~-~ 23 over 24} ^,
.EN
.DE
so
for $r ~member~ (1, ~1 ^+^ 10 sup -10 )$,
.DS 3
.EQ
left | sum from m=1000 to inf ~{( -1 ) sup n-1 ~cos ( eta sub m )} over
{m ^-^ 23 over 24} right | ~mark <=~ sum from q=500 to inf ~left {
1 over {( 2q ^-^ 1 ) sup 2} ~+~ {gamma sup 1/2} over
{( 2q ^-^ 1 ) sup 3/2}
~+~ {r sup -2q ^ log ^r} over {2q ~-~ 1} right }
.EN
.sp
.EQ (3.39)
~~~~~~
.EN
.sp
.EQ
~lineup <=~ int from 498 to inf ~du over {(2u) sup 2} ~+~ int from 498 to inf
~{gamma sup 1/2 ^du} over {(2u) sup 3/2}
~+~ ( log ^r) ^int from 498 to inf ~{r sup -2u ~du} over 2u
.EN
.sp
.EQ
~lineup <=~ 0.042 ~.
.EN
.DE
Therefore
for $r ~member~ (1, ~1 ^+^ 10 sup -10 )$,
.DS 3
.EQ
h(r) ~=~ pi sup {-^ 1/2} ~gamma sup -1 ~( A ~+~ B ) ^,
.EN
.DE
where
.DS 3
.EQ
A ~=~ sum from m=1 to 998 ~{( -1 ) sup m-1 ^r sup -m} over {m ^-^ 23 over 24} ~left (
{sin ( eta sub m )} over {eta sub m} ~-~ cos ( eta sub m ) right ) ~=~
1.415972...
.EN
.DE
by direct calculation, and $| B | ~<=~ 0.042 ~+~ 0.025 ~<=~ 0.07$.
Hence
for $r ~member~ (1, ~1 ^+^ 10 sup -10 )$,
.DS 3
.EQ (3.40)
0.46 ~<=~ h(r) ~<=~ 0.51 ^,
.EN
.DE
Since $h(r)$ is continuous for $0 ~<~ r ~<~ 2$, we must have
.DS 3
.EQ (3.41)
| h(r) | ~<=~ 0.6 ~~roman for~~ 1- epsilon ~<=~ r ~<=~ 1/2
.EN
.DE
if $epsilon ~<~ 10 sup -10$ is small enough.
.P
We now combine all the above estimates to obtain the claims
of
the proposition, valid for $c sub 1$ and $k$ large enough and $epsilon$ small enough.
.nf
.ta 6iR
	\(sq
.fi
.P
We now proceed to the proof of the theorem.
We select an $epsilon$ given by Proposition 3.3.
Then, applying Proposition 3.1 with this value of $epsilon$,
we see that $( -1 ) sup n ~DELTA sup k ^p(n) ~>~ 0$ for
all $n$, $0 ~<=~ n ~<=~ (1/2 ~-~ epsilon )k$, and all
$k ~>=~ k sub 3 ~=~ max ( k sub 1 ^( epsilon ), ~k sub 2 )$.
.P
Next, for $k ~>=~ k sub 3$ and $( 1/2 ~-~ epsilon ) k ~<=~ n ~<=~ k/2$,
we have
.DS 3
.EQ
( -1 ) sup n ^DELTA sup k ^p(n) ~mark =~ sum from j=0 to n ~( -1 ) sup j
^left ( {pile {k above n-j}} right ) ~p(j)
.EN
.sp
.EQ (3.42)
~lineup =~ left ( {pile {k above n}} right ) ~mark +~ ( -1 ) sup n ~pi sup -1
~2 sup {-^ 1/2} ~DELTA sup k ^f sub 1 ^(n)
.EN
.sp
.EQ
~lineup +~ pi sup -1 ~2 sup {-^ 1/2} ~sum from j=1 to n ~left ( {pile {k above n-j}} right )
^( f sub 2 ^(j) ~+~ ( -1 ) sup n-j ~R sub j ) ~.
.EN
.DE
By Lemma 3.2, each term in the $n$-term sum above is $>~ 0$, while
by (3.14),
.DS 3
.EQ (3.43)
| pi sup -1 ~2 sup {-^ 1/2} ~DELTA sup k ~f sub 1 ^(n) | ~<~ 3 over 5 ~
left ( {pile {k above n}} right ) ~.
.EN
.DE
Therefore $( -1 ) sup n ~DELTA sup k ^p(n) ~>~ 0$ in this range also.
.P
Consider now $k/2 ~<=~ n ~<=~ k-2$.
In this range, in view of Lemma 3.2, it suffices to show that
.DS 3
.EQ
G ~=~ sum from j=1 to n ~left ( {pile {k above n-j}} right ) ~f sub 2 ^(j)
.EN
.DE
satisfies $| G | ~>~ 3^ | DELTA sup k ^f sub 1 ^(n) |$.
However, by (3.11) we have $3^ | DELTA sup k ^f sub 1 ^(n) | ~<~ c sub 23 ~2 sup k$.
On the other hand, if $J ~=~ left floor n ~-~ k/2 ~+~ 1 right floor$, then
for $k$ sufficiently large, $J ~+~ k sup 1/4 ~<=~ j ~<=~ J ~+~ 2 ^k sup 1/4$,
.DS 3
.EQ
left ( {pile {k above n-j}} right ) ~>=~ 10 sup -1 ~k sup {-^ 1/2} ~2 sup k ^,
.EN
.DE
and so
.DS 3
.EQ (3.44)
G ~>=~ {2 sup k} over {10 ^k sup 1/2} ~f sub 2 ^( J ~+~ left floor k sup 1/4 right floor )
~>=~ 2 sup k ~exp ( 10 sup -1 ~C ~k sup 1/8 ) ^,
.EN
.DE
which gives the desired result for $k ~>=~ k sub 4 ~>=~ k sub 3$.
The same lower bound for $G$ holds also for $k-1 ~<=~ n ~<=~ k$,
and so by (3.12) we obtain the result of the theorem for that range
also if $k ~>=~ k sub 5 ~>=~ k sub 4$.
.P
Next, consider $n ~>=~ k+1$.
By Lemma 3.2, to obtain $( -1 ) sup n ~DELTA sup k ^p(n) ~>~ 0$ it suffices to show that if
.DS 3
.EQ
H ~=~ sum from j=0 to k ~left ( {pile {k above j}} right ) ~f sub 2 ^(n-j ) ^,
.EN
.DE
then $H$ satisfies $H ~>~ 3 ~| DELTA sup k ^f sub 1 ^(n) |$.
However, $f sub 2 ^(m) ~>=~ 10 sup -3$ for all $m ~>=~ 1$, so
.DS 3
.EQ
H ~>=~ 10 sup -3 ~sum from j=0 to k ~left ( {pile {k above j}} right ) ~=~
10 sup -3 ~2 sup k ^,
.EN
.DE
and by (3.12) and (3.13), we have $( -1 ) sup n ~DELTA sup k ^p(n) ~>~ 0$
for all $n$ with $k+1 ~<=~ n ~<=~ 10 sup -3 ^c sub 1 sup -2 ^k sup 2 ~( log ^k ) sup 2$,
provided $k ~>=~ k sub 5 ~>=~ k sub 4$.
.P
Before proceeding to consider the range $n ~>~ 10 sup -3 ^c sub 1 sup -2 ^k sup 2 ~( log ^k ) sup 2$, we
make the following general observation.
If $f(x)$ is a $C sup inf ~[ 1/2, ~inf )$ function, say, then
for $x ~>~ 3/2$,
.DS 3
.EQ (3.45)
DELTA ^f(x) ~=~ f(x) ~-~ f(x-1) ~=~ int from x-1 to x ~f prime ^(t) ~dt ~.
.EN
.DE
More generally, for $x ~>~ k+ 1/2$,
.DS 3
.EQ (3.46)
DELTA sup k ^f(x) ~=~ int from 1/2 to inf ~f sup (k) ^(u) ~chi sub k ^(x-u)
~du ^,
.EN
.DE
where
.DS 3
.EQ (3.47)
chi sub k ^(t) ~=~ chi sub 1 ^*...*^ chi sub 1 ~(t)
.EN
.DE
is the $k$-fold convolution of the characteristic
function of the unit interval,
.DS 3
.EQ
chi sub 1 ^(t) ~=~ left {
matrix {
lcol {1 above nothing above 0}
lcol {~~~0 ~<=~ t ~<=~ 1 ^, above nothing above ~~~roman otherwise .}
}
.EN
.DE
The formula (3.46) reduces to (3.45) for $k ^=^ 1$.
For higher values, it is easily proved by induction.
If we assume that (3.46) holds for $k-1 ~>=~ 1$, then
(since $( DELTA g ) prime ~=~ DELTA g prime$)
.DS 3
.EQ
DELTA sup k ^f(x) ~mark =~ int from x-1 to x ~( DELTA sup k-1 ^f(t) ) prime ~dt
.EN
.sp
.EQ
~lineup =~ int from x-1 to x ~( DELTA sup k-1 ^f prime ^(t) ) ~dt
.EN
.sp
.EQ
~lineup =~ int from x-1 to x ~dt ~int from 1/2 to inf ~f sup (k) ^(u) ~chi
sub k-1 ^(t-u) ~du
.EN
.sp
.EQ
~lineup =~ int from 1/2 to inf ~f sup (k) ^(u) ^du ~int from x-1 to x
~chi sub k-1 ^(t-u) ~dt
.EN
.sp
.EQ
~lineup =~ int from 1/2 to inf ~f sup (k) ^(u) ~chi sub k ^(x-u ) ~du ^,
.EN
.DE
which proves (3.46) for $k$.
.P
All that we will need to know about the $chi sub k ^(t)$ is that
$chi sub k ^(t) ~>=~ 0$, $chi sub k ^(t) ~=~ 0$ for
$t ~<~ 0$ and $t ~>~ k$, and
.DS 3
.EQ (3.48)
int from {-^ inf} to inf ~chi sub k ^(t) ~dt ~=~ 1 ~.
.EN
.DE
.P
To deal with the remaining range, $n ~>=~ 10 sup -3 ^c sub 1 sup -2 ^k sup 2 ^( log ^k ) sup 2$,
we need to investigate the derivatives of $f sub 1 ^(x)$ more
precisely than before.
Let $g(y) ~=~ f sub 1 ^( y ~+~ 1/24 )$, so that
$f sub 1 sup (r) ^(x) ~=~ g sup (r) ^( x ~-~ 1/24 )$.
We consider $r sup 2 ~ log ~r ~<=~ y$.
Then
.DS 3
.EQ
g sup (r) ^(y) ~mark =~ {d sup r+1} over {dy sup r+1} ~left { y sup {-^ 1/2}
~ sinh ( C y sup 1/2 ) right }
.EN
.sp
.EQ (3.49)
~lineup =~ sum from j=0 to inf ~{C sup 2j+1 ^( j ) sub r+1} over
{( 2j +1)!} ~y sup j-r-1 ^,
.EN
.DE
where
.DS 3
.EQ
(z) sub m ~=~ z( z-1 ) ^...^ (z ~-~ m+1 ) ~.
.EN
.DE
Let $a sub j$ denote the $j$-th term in the sum in (3.49).
By looking at the ratio $a sub j+1 / a sub j$, we see that
the maximum occurs for $j ~=~ J ~+~ O(1)$, where
.DS 3
.EQ (3.50)
J ~=~ left floor (r ~+~ ( C sup 2 ^y ^+^ r sup 2 ) sup 1/2 ) /2 right floor ^,
.EN
.DE
and that for $m ~=~ j-J$, $| m | ~<=~ J sup 5/9$,
.DS 3
.EQ
{a sub j} over {a sub J} ~mark =~ left ( 1 ~+~ O( J sup {-^ 1/3} ) right )
^ left [ {C sup 2 ^y} over {2(2J+3) ^(J-r)} right ] sup m
~prod from h=0 to {| m | ^-^ 1} ^ left { left ( 1 ~+~ h over J-r right )
^ left ( 1 ~+~ 2h over 2J+3 right ) right } sup -1
.EN
.sp
.EQ
~lineup =~ left ( 1 ~+~ O( J sup {-^ 1/3} ) right ) ~ exp left ( -~ {m sup 2
^(J-r/2)} over {J(J-r)} right ) ^,
.EN
.DE
while
.DS 3
.EQ
sum from {| j-J | ~>=~ J sup 5/9} ~a sub j ~=~ O( J sup -1 ~a sub J ) ~.
.EN
.DE
Therefore we conclude that for $y ~>~ r sup 2 ^ log ^r$,
$r ~>=~ 2$,
.DS 3
.EQ (3.51)
g sup (r) ^(y) ~=~ left (  pi ^J right ) sup 1/2 ~a sub J~ ( 1 ~+~
O( y sup {-^ 1/6} )) ^,
.EN
.DE
where the constant implied by the $O$-notation is
independent of $y$ and $r$, and $J ~=~ J(y,r)$ is given by (3.50).
Furthermore, if in fact $y ~>~ (r+1 ) sup 2 ~ log ~(r+1)$, then
.DS 3
.EQ
| J( y, ^r+1) ~-~ J(y,r) | ~=~ O(1) ^,
.EN
.DE
and therefore
.DS 3
.EQ
g sup (r+1) ^(y) ~mark =~ J-r over y ~g sup (r) ^(y) ^( 1 ~+~ O( y sup
{-^ 1/6} ))
.EN
.sp
.EQ (3.52)
~lineup =~ C over {2 y sup 1/2} ~g sup (r) ^(y) ^( 1 ~+~ O( y sup {-^ 1/6}
~+~ r  ^y sup {-^ 1/2} )) ~.
.EN
.DE
Also,
.DS 3
.EQ
| J ( y+r, ~r ) ~-~ J(y,r) | ~=~ O(1) ^,
.EN
.DE
so for $0 ~<=~ t ~<=~ r$,
.DS 3
.EQ (3.53)
g sup (r) ^(y+t) ~=~ g sup (r) ^(y) ^(1 ~+~ O ( y sup {-^ 1/6} )) ~.
.EN
.DE
.P
We first show that if $eta ~member~ (0, ~10 sup -2 )$ is given,
then for $10 sup -3 ^c sub 1 sup -2 ^k sup 2 ^( log ^k ) sup 2 ~<=~ n ~<=~ (1- eta ) ^6 pi sup -2 ~k sup 2 ^( log ^k ) sup 2$,
.DS 3
.EQ (3.54)
f sub 1 sup (k) ^(n) ~<=~ (1 ~+~ O( k sup {-^ 1/5} )) 2 sup k ~f sub 2 ^
( n-k ) sup {(1- eta /100)} ^,
.EN
.DE
and that for $(1+ eta ) 6 pi sup -2 ~k sup 2 ^( log ^ k ) sup 2 ~<=~ n$,
.DS 3
.EQ (3.55)
f sub 1 sup (k) ^(n-k) ~>~ (1 ~+~ O( k sup {-^ 1/5} )) 2 sup k ~f sub 2 ^
(n) sup {(1+ eta /100)} ~.
.EN
.DE
We consider only (3.55) in detail.
Suppose therefore that $eta ~member~ (0, ~10 sup -2 )$ is
given, and we have
.DS 3
.EQ (3.56)
n ~>=~ (1 ^+^ eta ) ^6 pi sup -2 ~k sup 2 ^( log ^k ) sup 2 ^,
.EN
.DE
where we can take $k$ very large.
We define $J$ by (3.50) with $r ~=~ k, ~y ~=~ n-k- 1/24$.
Then
.DS 3
.EQ
J ~=~ 1 over 2 ^C n sup 1/2 ^+^ 1 over 2 ^k ^+^ o(k) ~~roman as~~ k ~->~ inf
.EN
.DE
with $n$ satisfying (3.56), and
.DS 3
.EQ
f sub 1 sup (k) ~(n-k) ~mark >=~ a sub J ~>=~ J sup -1 ~C sup 2J ~((
2J )! ) sup -1 ~(J ) sub k+1 ~( n-k-1 ) sup J-k-1
.EN
.sp
.EQ
~lineup >=~ J sup -2 ~C sup 2J ~2 sup -2J ~J sup -2J ~e sup +2J ~
J sup k+1 ~n sup J-k-1 ~cdot~ T ^,
.EN
.DE
where
.DS 3
.EQ
T ~=~ left ( 1 ^-^ k+1 over n right ) sup J-k-1 ~cdot~ prod from m=1 to k
^left ( 1 ^-^ m over J right ) ~>=~ exp (-^ c sub 24 ^k ^( log ^k ) sup -1 ) ~.
.EN
.DE
Furthermore,
.DS 3
.EQ
2 sup 2J ~J sup 2J ~n sup -J ~=~ C sup 2J ~ exp ( k ~+~ o(k)) ^,
.EN
.DE
so
.DS 3
.EQ
f sub 1 sup (k) ~(n-k) ~mark >=~ n sup -2 ~J sup k ~n sup -k ~ exp ( C ^
n sup 1/2 ~1 ~+~ o(1))
.EN
.sp
.EQ
~lineup >=~ n sup -k/2-2 ~2 sup -k ~C sup k ~ exp ( C ^n sup 1/2 ~1 ~+~ o(1))
~~roman as~~ k ~->~ inf ^,
.EN
.DE
which now implies (3.55) (subject to (3.56)) for large enough $k$.
.P
Given (3.54) and (3.55), it is clear that for
$k ~>=~ k sub 6 ~=~ k sub 6 ^( eta )$
$( k sub 6 ~>=~ k sub 5 )$
.DS 3
.EQ
( -1 ) sup n ~DELTA sup k ^p(n) ~>~ 0 ~~roman for~~ 0 ~<=~ n ~<=~ (1-
eta ) 6 pi sup -2 ~k sup 2 ^( log ^k ) sup 2 ^,
.EN
.sp
.EQ
DELTA sup k ^p(n) ~>~ 0 ~~roman for~~ n ~>=~ (1+ eta ) 6 pi
sup -2 ~k sup 2 ^( log ^k ) sup 2 ^,
.EN
.DE
since by (3.46) and the monotonicity of $f sub 1 sup (k) ^(x)$ we have
.DS 3
.EQ
f sub 1 sup (k) ^( n-k ) ~<=~ DELTA sup k ^f sub 1 ^(n) ~<=~ f sub 1 sup (k)
^(n) ^,
.EN
.DE
while
.DS 3
.EQ
2 sup k ^ f sub 2 ^(n-k ) ~<=~ sum from j=0 to k ~left ( {pile {k above j}}
right ) ~f sub 2 ^( n-j ) ~<=~ 2 sup k ^f sub 2 ^(n) ^,
.EN
.DE
and by Lemma 3.2,
.DS 3
.EQ
sum from j=0 to k ~ | left ( {pile {k above j}} right ) ~R sub n-j |
~<~ 10 ~cdot~ 2 sup k ^f sub 3 ^(n) ~.
.EN
.DE
Since this holds for every $eta ~member~ (0, ~10 sup -2 )$
(with $k sub 6$ depending on $eta$), this shows that
if $n sub 0 ^(k)$ exists, then $n sub 0 ^(k) ~wig~ 6 pi sup -2 ~k sup 2 ^( log ^k ) sup 2$
as $k ~->~ inf$.
.P
At this point, to complete the proof of our theorem it only
remains to show that one can choose $eta ~member~ (0, ~10 sup -2 )$
so small that for $k ~>=~ k sub 7 ~=~ k sub 7 ^( eta )$,
$DELTA sup k ^p(n)$ will alternate in sign and then become
nonnegative and stay nonnegative as $n$ ranges over
$n sub 1 ~<=~ n ~<=~ n sub 2$, where
.DS 3
.EQ
n sub 1 ~mark =~ left floor (1- eta ) ^6 pi sup -2 ~k sup 2 ^( log
^k ) sup 2 right floor ^,
.EN
.sp
.EQ
n sub 2 ~lineup =~ left floor (1+ eta ) ^6 pi sup -2 ~k sup 2 ^( log
^k ) sup 2 right floor ~.
.EN
.DE
Let
.DS 3
.EQ
S(n) ~=~ sum from j=0 to k ~left ( {pile {k above j}} right ) ~f sub 2
^( n-j ) ~.
.EN
.DE
Then we know that for any $eta ~member~ (0, ~10 sup -2 )$ and
$k$ large enough (depending only on $eta$)
.DS 3
.EQ
DELTA sup k ^f sub 1 ^( n sub 1 ) ~mark <~ 10 sup -3 ~S( n sub 1 ) ^,
.EN
.sp
.EQ
DELTA sup k ^f sub 1 ^( n sub 2 ) ~lineup >~ 10 sup -3  ~S ( n sub 2 ) ^,
.EN
.DE
while for any $n ~member~ [ n sub 1 , ~n sub 2 ]$,
.DS 3
.EQ
| DELTA sup k ~R sub n | ~<~ n sup {-^ 10} ~S (n) ~.
.EN
.DE
Now it is easy to see from the explicit definition of
$f sub 2 ^(n)$ that it is monotone increasing, and
.DS 3
.EQ
f sub 2 ^( n+1 ) ~<=~ f sub 2 ^( n ) ~+~ 3C over {10 n sup 1/2} ~
f sub 2 ^( n)
.EN
.DE
for large enough $n$, so that if $k$ is large enough and
$n ~member~ [ n sub 1 , ~n sub 2 ]$, then
.DS 3
.EQ
S(n) ~<=~ S(n+1) ~<=~ S(n) ~+~ CS( n) /( 3 n sup 1/2 ) ~.
.EN
.DE
On the other hand, by (3.46),
.DS 3
.EQ
DELTA sup k ^f sub 1 ^( n+1 ) ~mark -~ DELTA sup k ^f sub 1 ^(n) ~=~
DELTA sup k+1 ^f sub 1 ^( n)
.EN
.sp
.EQ
~lineup =~ int from n-k-1 to n ~f sub 1 sup (k+1) ~(u) ~chi sub k+1 ^(n-u)
~du
.EN
.sp
.EQ
~lineup >=~ f sub 1 sup (k+1) ~( n-k-1 ) ^,
.EN
.DE
and by (3.46) and (3.53), this last quantity is
.DS 3
.EQ
>=~ 2 C ( DELTA sup k ^f sub 1 ^(n )) / ( 5 ^ n sup 1/2 ) ^,
.EN
.DE
provided $k$ is large enough.
It is now easy to conclude the proof of the Theorem.
Let $N$ be the least integer $>=~ n sub 1$ such that
$DELTA sup k ^f sub 1 ^(N) ~>=~ S(N)$.
Then, by the above discussion,
.DS 3
.EQ
DELTA sup k ^f sub 1 ^(n) ~+~ sum from j=0 to k ~left ( {pile {k above j}}
right ) ~ | R sub n-j | ~<~ S(n)
.EN
.DE
for all $n ~<~ N$, $n ~>=~ n sub 1$, so that
$( -1 ) sup k ~DELTA sup k ^p(n) ~>~ 0$ for $n ~<~ N$.
On the other hand, for $n ~>~ N$, $n ~<=~ n sub 2$,
.DS 3
.EQ
DELTA sup k ^f sub 1 ^(n) ~>~ S(n) ~+~ sum from j=0 to k ~left (
{pile {k above j}} right ) ~ | R sub n-j | ^,
.EN
.DE
so that $DELTA sup k ^p(n) ~>~ 0$ for all $n ~>~ N$.
Finally, $DELTA sup k ^p(N)$ can only be negative if $N$ is odd.
This completes the proof of the theorem.
.HU "Acknowledgement"
The author thanks T. H. Foregger for his comment, on an earlier
version of the manuscript.
.bp
.ce
.B
References
.R
.sp
.AL
.LI
G. E. Andrews, \f2The Theory of Partitions\f1, Addison-Wesley, 1976.
.LI
T. M. Apostal, \f2Modular Functions and Dirichlet Series in Number Theory\f1,
Springer 1976.
.LI
R. Ayoub, \f2An Introduction to the Analytic Theory of Numbers\f1,
Math. Surveys #10, Am. Math. Soc. 1963.
.LI
P. T. Bateman and P. Erdo\*:s, Monotonicity of partition functions,
\f2Mathematika\f1 \f23\f1 (1956), 1-14.
.LI
(a) I. J. Good, The differences of the partition function,
Problem 6137, \f2Am. Math. Monthly\f1 \f284\f1 (1977), 141.
.br
(b) Partial solutions by R. Razen and I. J. Good, \f2ibid.\f1 \f285\f1 (1978),
830-831.
.br
(c) Comments by I. J. Good, \f2ibid.\f1 \f288\f1 (1981), 215.
.LI
H. Gupta, Finite differences of the partition function,
\f2Math. Comp.\f1 \f232\f1 (1978), 1241-1243.
.LI
G. H. Hardy and S. Ramanujan, Asymptotic formulae in
combinatory analysis, \f2Proc. London Math. Soc.\f1 (2) \f217\f1
(1918), 75-115.
.LI
H. Rademacher, On the partition function $p(n)$,
\f2Proc. London Math. Soc.\f1 (2) \f243\f1 (1937), 241-254.
.LE