.PH ""
.EQ
delim $$
gsize 10
define sstar % size 10 * %
define pprime % size 10 prime %
define gcd % roman "gcd" %
.EN
.ds HP 10 10 10
.nr Pt 1
.am DE
.sp
.ls 2
..
.ce 99
.B
On the Unimodality of High Convolutions
of Discrete Distributions
.I
.sp
A. M. Odlyzko
.sp
.R
AT&T Bell Laboratories
Murray Hill, New Jersey 07974
USA
.sp
.I
L. B. Richmond
.sp
.R
University of Waterloo
Waterloo, Ontario
Canada
.sp 3
.I
Abstract
.R
.sp 2
.ce 0
.P
It is shown that if $"{" p sub j "}"$ is a discrete
density function on the integers with support contained
in $"{" 0,~1, "..." ,~ d "}"$,
and
$p sub 0 ~>~0$, $p sub 1 ~>~0$,
$p sub d-1 ~>~0$, $p sub d ~>~0$,
then there is an $n sub 0$ such that the $n$-fold convolution
$"{" p sub j "}" sup {sstar n}$ is unimodal for all
$n~>=~n sub 0$.
Examples show that this result is nearly best possible,
but weaker results are proved under less restrictive assumptions.
.bp
.ce 99
.B
On the Unimodality of High Convolutions
of Discrete Distributions
.I
.sp
A. M. Odlyzko
.sp
.R
AT&T Bell Laboratories
Murray Hill, New Jersey 07974
USA
.sp
.I
L. B. Richmond
.sp
.R
University of Waterloo
Waterloo, Ontario
Canada
.sp 3
.ce 0
.ls 2
.H 1 Introduction
The unimodality of distribution functions has been of substantial
interest, especially in connection with the question of whether
all class $L$ distributions are unimodal (which was finally answered
in the affirmative by Yamazato [7]).
.PH "''- \\\\nP -''"
.pn 2
In view of the (at that time unproved, but widely conjectured) unimodality
of the limiting distributions of class $L$,
A. Re\*'nyi conjectured [4]
that something stronger ought to hold for a discrete distribution
$"{" p sub j  "}"$
on the integers, namely that for each such distribution there
ought to be an integer $n sub 0$ such that the $n$-fold
convolution $"{" p sub j "}" sup {sstar n}$ is unimodal for all
$n~>=~n sub 0$.
Medgyessy [4] extended this conjecture to continuous distribution
functions.
However, the Re\*'nyi and Medgyessy conjectures are both false,
as was recently shown by Brockett and Kemperman [1]
and by Ushakov [6].
Their counterexamples show that it is hard to guarantee
unimodality even for high convolutions of a discrete
distribution if the distribution has
infinite support.
However, Brockett and Kemperman conjectured that if
$p sub 0 , p sub 1 , "..." , p sub d~>~0$ and $p sub k~=~0$ for
$k~<~0$ and $k~>~d$, then for $n~>=~n sub 0$ the $n$-fold
convolution $"{" p sub j "}" sup {sstar n}$ is unimodal, and
they proved this conjecture for $d~=~2$.
A similar question was raised by B. McKay (unpublished).
This paper proves a result stronger than that conjectured by
Brockett and Kemperman,
namely that $"{" p sub j "}" sup {sstar n}$ is even strongly unimodal.
.P
A probability distribution $"{" p sub j "}"$ on the integers
is called unimodal if the sequence
$"{" p sub j+1 - p sub j "}" sub {- inf} sup inf$ has exactly
one change of sign.
Various results about unimodal distributions are contained
in [2,4].
A more restrictive concept than that of unimodality is that of
strong unimodality; a discrete distribution $"{" p sub j "}"$
is strongly unimodal if $"{" p sub j "}"~*~"{" q sub j "}"$
is unimodal for any unimodal discrete distribution
$"{" q sub j "}"$.
A strongly unimodal distribution is unimodal, but not conversely.
A discrete distribution $"{" p sub j "}"$ is strongly
unimodal if and only if it is log concave; i.e.,
$p sub j sup 2~>=~p sub j-1 p sub j+1$ for all $j~member~Z$ [3].
We prove:
.sp
.I
Theorem 1.
If $"{" p sub j "}"$ is a discrete distribution with $p sub j~=~0$
for $j~<~0$ and
$j~>~d$, while
$p sub 0~>~0$,
$p sub 1 ~>~0$,
$p sub d-1 ~>~0$,
$p sub d ~>~0$,
then there exists an integer $n sub 0$ such that for $n~>~n sub 0$
the $n$-fold convolution $"{" p sub j "}" sup {sstar n}$ is strongly
unimodal.
.sp
.I
Theorem 2.
If $"{" p sub j "}"$ is a discrete distribution with $p sub j~=~0$
for $j~<~0$ and $j~>~d$, while
$p sub 0~>~0 ,~ p sub d ~>~0$, and
.DS 2
.EQ (1.1)
gcd "{" j~:~p sub j != 0 "}"~=~1~,
.EN
.DE
then for any $delta~>~0$ there is an $n sub 0~=~n sub 0 ( delta )$
such that if $a sub k,n$ denotes the value of the $n$-fold
convolution $"{" p sub j "}" sup {sstar n}$ at $k$, then
for $n~>=~n sub 0$,
.DS 2
.EQ
a sub k,n sup 2~>=~a sub k-1,n~a sub k+1,n
.EN
.DE
for $delta n~<=~k~<=~(d- delta )n$.
.R
.P
The greatest common divisor condition (1.1) of Theorem 2 is
obviously necessary for the conclusions of that theorem to hold
(as otherwise the distribution
and all multiple convolutions
of it with itself are concentrated
on multiples of that greatest
common divisor),
but it is not sufficient to obtain the conclusions of Theorem 1.
In Section 2 we show that for any $epsilon~>~0$, there is a
distribution satisfying the hypotheses of Theorem 2, and for
which the inequalities
.DS 2
.EQ (1.2)
a sub k,n~>~a sub k+1,n ~,~a sub k+1,n~<~a sub k+2,n
.EN
.DE
hold for $k$ as large as $n sup {1- epsilon}$
and $n~>=~n sub 0 ( epsilon )$.
.P
It is possible to obtain results stronger than those of our
theorems 1 and 2 by more careful analysis.
For example, it can be shown that high convolutions
of distributions satisfying the\p
.bp
hypotheses of Theorem 1
have stronger variation-diminishing properties than that
guaranteed by strong unimodality.
(See [2] for a discussion of such properties.)
.P
Our proofs also provide quantitative information about the
distribution $"{" p sub j "}" sup {sstar n}$.
For example, it can be deduced easily from our proofs that if the $"{" p sub j "}"$
satisfy the conditions of Theorem 1, if $k~->~inf$ in such a way that
$nd-k~->~inf$, and $alpha$ is defined as the unique positive solution to
.DS 2
.EQ (1.3)
{e sup alpha p prime ( e sup alpha )} over
{p (e sup alpha )}~=~k over n~,
.EN
.DE
where
.DS 2
.EQ (1.4)
p(z)~=~sum from j=0 to d~p sub j z sup j~,
.EN
.DE
then $a sub k,n$, the value of $"{" p sub j "}" sup {sstar n}$ at
$k$, satisfies
.DS 2
.EQ (1.5)
a sub k,n~wig~
{e sup {- alpha k} p (e sup alpha ) sup n} over
{2 sqrt {pi n~beta sub k (n)}}~~~roman as~~n~->~inf~,
.EN
.DE
where
.DS 2
.EQ (1.6)
beta sub k (n)~=~
1 over 2~partial sup 2 over {partial x sup 2}~
log~p(e sup x ) size 18 | sub {x = alpha}~.
.EN
.DE
.P
Finally we mention that related results and references to
many unimodality results from combinatorial theory are
contained in [5].
.P
The authors thank the referee for
several useful comments and
corrections.
.H 1 "Examples and elementary proofs"
In this section we show that under the hypotheses of
Theorem 2, its conclusions cannot be strengthened
significantly.
We also prove Theorem 1 for $0~<=~k~<=~n sup 1/4$ and
$dn-n sup 1/4~<=~k~<=~dn$, provided $n$ is large enough.
.P
To show that Theorem 2 is nearly best possible, consider
the distribution
.DS 2
.EQ
p sub 0 ~=~p sub 2~=~p sub m~=~1/3~,~~~p sub j~=~0~~~for~~j~!=~0,~2,~ m~,
.EN
.DE
where $m$ is an odd integer
$>=~3$.
Then condition (1.1)
is satisfied.
We will show that for
this distribution, (1.2)
holds for $k~<=~n sup {1-2/m}$
if $n$ is large enough.
This result can also be proved
by a more elementary argument
that uses estimates of multinomial
coefficients, but we prefer to use
the analytic proof given below,
since it introduces the techniques
which we find necessary to use in
later sections.
.P
The value of the $n$-fold
convolution $"{" p sub j "}" sup {* n}$
at the integer $k$ is
at the integer $k$ is $3 sup -n a sub k,n$ where $a sub k,n$
is the coefficient of $z sup k$ in
$p (z) sup n$, $p(z)~=~1+z sup 2 + z sup m$.
Now $a sub k,n$ is given by
.DS 2
.EQ (2.1)
a sub k,n~=~1 over {2 pi i}~int from {| z | =r} ~
p(z) sup n z sup -k-1 dt~,
.EN
.DE
where $r~>~0$ is any constant.
Choose $r~=~k sup 1/2 (2n-k) sup -1/2$, $0~<=~k~<=~n$.
Then, on $| z |~=~r$,
for $k~<=~n$, we have
.DS 2
.EQ
p(z)~=~1+z sup 2 + O (r sup m )~=~ (1+ z sup 2 ) (1+O(r sup m ))~,
.EN
.DE
and so
for $nr sup m~=~O(1)$, say,
which we assume from now on,
.DS 2
.EQ
p(z) sup n~=~(1+z sup 2 ) sup n (1+O (r sup m )) sup n~=~
(1+z sup 2 ) sup n (1+O (n r sup m ))~.
.EN
.DE
Therefore
for $nr sup m~=~O(1)$,
.DS 2
.EQ (2.2)
a sub k,n~=~1 over {2 pi i}~
int from {| z |~=~r}~
(1+z sup 2 ) sup n z sup -k-1 dz + O (nr sup m-k-1~
int from { | z | =r} ~| 1+z sup 2 | sup n dz )~.
.EN
.DE
Now the first integral above is just the coefficient of $z sup k$
in $(1+z sup 2 ) sup n$, which equals $( pile {n above k/2} )$
if $k$ is even and 0 otherwise.
On the other hand,
.DS 2
.EQ (2.3)
int from {| z | =r}~
|1 + z sup 2 | sup n dz~=~O (r(1+r sup 2 ) sup n )~=~O
(r ^exp (k/2))~.
.EN
.DE
If $h~=~[k/2]$ (the greatest integer $<=~k/2$), then the last
term in (2.2) is
.DS 2
.EQ
O (n sup (3-m)/2 h sup (m-1)/2 (ne/h) sup h~exp (-9h sup 2 / (10n))~.
.EN
.DE
But $h!~wig~(2 pi h) sup 1/2 (h/e) sup h$ as $h~->~inf$, so for large $h$,
.DS 2
.EQ
left ( pile {n above h} right )~=~
{n(n-1) "..." (n-h+1)} over h!~>=~
(3 pi h) sup -1/2~
left ( ne over h right ) sup h ~prod from j=0 to h-1 ~
left ( 1~-~j over n right )~>=~(100h) sup -1/2~
left ( ne over h right ) sup h~exp (-2h sup 2 /(3n))~.
.EN
.DE
Therefore the quantity in (2.3) is
.DS 2
.EQ
O(n sup 3 (h/n) sup m/2 left ( pile {n above h} right ) ~
exp (-h sup 2 / (5n) )~.
.EN
.DE
This is $o ( ( pile {n above h } ) )$ as
$n~->~inf$ if $h~=~O(n sup 1-2/m )$, (which guarantees $nr sup m~=~O(1)$), and so in that range
.DS 2
.EQ
a sub 2h-2,n~>~a sub 2h-1,n ~~,~~
a sub 2h-1,n~<~a sub 2h,n ~,
.EN
.DE
which shows that the sequence oscillates in that range.
.P
We next prove Theorem 1 for $k$ very small.
Suppose that $p sub 0 , p sub 1 ~>~0$,
.DS 2
.EQ
p(z)~=~sum from j=0 to d~p sub j z sup j~,
.EN
.DE
and we are interested in the value $a sub k,n$
of the $n$-fold convolution $"{" p sub j "}" sup {sstar n}$
at $k$.
Then $a sub k,n$ is again given by (2.1).
This time we choose $r~=~p sub 0^ p sub 1 sup -1 k (n-k) sup -1$.
On $| z |~=~r$, as $n~->~inf$, $k~=~o ( sqrt n )$,
.DS 3
.EQ
p(z)~mark =~
p sub 0 + p sub 1 z + O ( k sup 2 n sup -2 )~,
.EN
.sp
.EQ
p(z) sup n~=~(p sub 0 + p sub 1 z ) sup n ( 1 + O ( k sup 2 n sup -1 ))~,
.EN
.DE
so
.DS 3
.EQ
a sub k,n~mark =~
1 over {2 pi i} ~int from {| z | =r}~
(p sub 0 + p sub 1 z ) sup n z sup -k-1 dz~+~
O (k sup 2 n sup -1 ~int from {| z | =r}~
| p sub 0 + p sub 1 z | sup n | z | sup -k-1 dz )
.EN
.sp
.EQ
lineup =~
left ( pile {n above k} right ) p sub 0 sup n-k p sub 1 sup k~+~
O (k sup 2-k n sup k-1 p sub 0 sup n-k p sub 1 sup k e sup k )~.
.EN
.DE
Now for $n~->~inf$, $k~=~o( sqrt n )$,
.DS 2
.EQ
( pile {n above k} )~>=~
n sup k over k!~>=~
(c k ) sup {- half} ~ ( ne over k ) sup k~,
.EN
.DE
for some constant $c~>~0$,
so
.DS 2
.EQ
a sub k,n~=~( pile {n above k} ) p sub 0 sup n-k p sub 1 sup k
( 1 + O ( k sup 5/2 n sup -1 ))~.
.EN
.DE
Hence if $k~=~o ( n sup 2/7 )$, then $a sub k,n sup 2 ~>~a sub k-1,n~a sub k+1,n$
for large $n$, which is the desired result.
(By a more careful analysis, the range of values of $k$
for which this inequality holds can be extended.)
Note that in this part of the proof we did not use the fact
that $p sub d-1 ~>~0$.
.P
To conclude this section, we only have to consider the range
$dn-n sup 1/4~<=~k~<=~dn$.
However, this range corresponds to the range
$0~<=~k~<=~n sup 1/4$ for the $n$-fold convolution of the
distribution $p sub j sup sstar~=~p sub d-j$, $0~<=~j~<=~d$,
and so is covered by the preceding discussion.
(Note that this part
of the proof uses
$p sub d-1 ~>~0$ but
not $p sub 1 ~>~0$.)
.H 1 "Main part of the proofs of theorems 1 and 2"
In view of the preceding results, it will suffice to prove
that $a sub k,n sup 2~>=~a sub k-1,n a sub k+1,n$ holds
for $n sup 1/4 ~<=~k~<=~dn-n sup 1/4$ under the conditions
of Theorem 1, and for $delta  n~<=~k~<=~(d- delta )n$ under
the conditions of Theorem 2.
From Cauchy's theorem we have
.DS 2
.EQ (3.1)
a sub k,n~=~1 over {2 pi i}~
int from {| z | =e sup alpha} ~
p (z) sup n z sup -k-1 dz~,
.EN
.DE
where $alpha$ is any constant.
We can write this as
.DS 2
.EQ (3.2)
a sub k,n~=~1 over {2 pi} ~
e sup {- alpha k} ~int from {- pi} to pi~
exp ( n~log~p ( e sup {alpha + i theta } ) - ik theta ) d theta~.
.EN
.DE
Eq. (3.2) now defines $a sub k,n$ as a real function of the
real variable $k$ for any fixed value of $alpha$.
(There is a mistake in [5] on this point in the proof
of Theorem 2 of that paper, but it is easily corrected along the lines used in this
paper.)
It is immediate from the definition that as a function of $k$,
$a sub k~=~a sub k,n ( alpha )~member~C sup inf (- inf , inf )$.
To prove our results it suffices to show that
.DS 2
.EQ (3.3)
a sub k sup 2 ~>=~a sub k-1 a sub k+1
.EN
.DE
for $k$ in the appropriate ranges.
To prove (3.3) for $k~=~k sub 0$, we choose $alpha~=~alpha (k sub 0 )$ by
.DS 2
.EQ (3.4)
e sup alpha~
{p prime (e sup alpha )} over {p (e sup alpha )} ~=~
k sub 0 over n~,
.EN
.DE
and, defining $a sub k~=~a sub k,n$ by (3.2) with $alpha$ defined by (3.4), show that
.DS 2
.EQ (3.5)
partial sup 2 over {partial k sup 2 } ~log~a sub k~<~0
.EN
.DE
for $k~member~[k sub 0 - 1, k sub 0 +1 ]$.
.P
To prove (3.5) with the $alpha$ given by (3.4), we define for
$m~=~0,~1$, and 2,
.DS 2
.EQ
J sub m~=~int from {- pi} to pi ~theta sup m ~
exp ( n~log~p (e sup {alpha + i theta } ) - i k theta ) d theta~.
.EN
.DE
Note that $J sub 0$ and $J sub 2$ are
real, whereas $J sub 1$ is purely
imaginary.
Inequality (3.5) is equivalent to
.DS 2
.EQ (3.6)
J sub 0 J sub 2 ~>~J sub 1 sup 2~.
.EN
.DE
Since $J sub 1$ is purely imaginary,
(3.6) will follow if we show
$J sub 0~>~0$,
$J sub 2 ~>~0$.
To prove (3.6), we estimate the $J sub m$.
We first consider $p(z)$ that satisfies the conditions
of Theorem 1, i.e., $roman deg~p(z)~=~d$,
$p sub 0 , p sub 1 , p sub d-1 , p sub d~>~0$.
It is also sufficient to consider
$n sup 1/4~<=~k sub 0~<=~3dn/4$, since the range
$k sub 0~>~3dn/4$ can be treated by considering the polynomial
$z sup d p(1/z)$.
.P
Define, for any $k~member~[k sub 0 -1 , k sub 0 +1 ]$,
.DS 2
.EQ (3.7)
theta sub 0~=~n sup 1/30 k sup -1/2~.
.EN
.DE
Since $k sub 0~<=~3dn over 4$, $alpha~<=~c$ for some constant $c$,
and so for $theta~member~[ theta sub 0 , 2 pi - theta sub 0 ]$,
.DS 2
.EQ
left | ^p ( e sup {alpha + i theta } ) right |~<=~
left | p sub 0 + p sub 1 e sup {alpha + i theta } right |~+~
sum from j=2 to d~p sub j e sup {j alpha}~.
.EN
.DE
But
.DS 3
.EQ
left | ^p sub 0 + p sub 1 e sup {alpha + i theta } right |^ "" sup 2~mark =~
p sub 0 sup 2 ~+~ 2 p sub 0 p sub 1 e sup alpha ~cos~
theta  ~+~p sub 1 sup 2 e sup {2 alpha}
.EN
.sp
.EQ
lineup =~
( p sub 0 + p sub 1 e sup alpha ) sup 2 ~+~
2 p sub 0 p sub 1 e sup alpha ( cos~theta -1 )
.EN
.sp
.EQ
lineup <=~
( p sub 0 + p sub 1 e sup alpha ) sup 2 ( 1 - c prime e sup alpha theta sub 0 sup 2 ) sup 2
.EN
.DE
for some constant $c prime~>~0$, and so
.DS 2
.EQ (3.8)
left | ^p ( e sup {alpha + i theta } ) right |~<=~
p ( e sup alpha ) exp ( -c prime prime e sup alpha theta sub 0 sup 2 )
.EN
.DE
for some $c prime prime~>~0$.
Therefore if
.DS 2
.EQ (3.9)
J sub m sup sstar~=~
int from {- theta sub 0} to {theta sub 0} ~theta sup m~
exp ( n~log~p (e sup {alpha + i theta } ) - ik theta ) d theta~,
.EN
.DE
then
.DS 2
.EQ (3.10)
J sub m~=~J sub m sup sstar~+~
O ( p ( e sup alpha ) sup n~exp ( -c prime prime ne sup alpha
theta sub 0 sup 2 ) )~.
.EN
.DE
Next, we consider $J sub m sup sstar$.
Since $theta sub 0 ~->~0$ as $n~->~inf$, for $| theta |~<=~theta sub 0$
we have
.DS 2
.EQ (3.11)
log~p(e sup {alpha + i theta } )~=~log~p (e sup alpha )~+~
i theta e sup alpha~ {p prime (e sup alpha )} over
{p ( e sup alpha )}~-~
theta sup 2 beta~+~O ( | theta | sup 3 gamma )~,
.EN
.DE
where
.DS 3
.EQ (3.12)
beta~=~beta ( k sub 0 )
~mark =~1 over 2~partial sup 2 over {partial x sup 2}~
log~p (e sup x ) size 18 | sub {x = alpha}~,
.EN
.sp
.EQ (3.13)
gamma~=~gamma ( k sub 0 )~lineup =~
max from {| theta |~<=~theta sub 0}~
left | partial sup 3 over {partial y sup 3}~
log~p (e sup {alpha +iy} ) right | size 18 | sub {y = theta }~.
.EN
.DE
Since $p sub 0~>~0 ,~ p sub 1~>~0$, and $alpha$ is
bounded above,
$beta  e sup {- alpha} ,~ gamma e sup {- alpha}~member~
( a sub 1 , a sub 2 )$ for some constants $a sub 1 ,~ a sub 2 $, $0~<~a sub 1 ~<~a sub 2~<~inf$.
Therefore, by (3.4) and (3.11),
.DS 2
.EQ
J sub m sup sstar ^ p ( e sup alpha ) sup -n~=~
int from {- theta sub 0} to theta sub 0 ~
theta sup m ~exp ( - n theta sup 2 beta ~+~
O (n | theta | sup 3 gamma )~+~i(k sub 0 - k) theta )~~d theta~.
.EN
.DE
By (3.4), $gamma n/k ~member~( a sub 1 sup pprime , a sub 2 sup pprime )$
for some constants $a sub 1 sup pprime ,~ a sub 2 sup pprime $, $0~<~a sub 1 sup pprime~<~a sub 2 sup pprime~<~inf$,
so
.DS 2
.EQ
n | theta | sup 3 gamma~=~O ( | theta | n sup 1/15 )
.EN
.DE
in $| theta | ~<=~theta sub 0$.
Hence
.DS 3
.EQ
J sub m sup *^
p ( e sup alpha ) sup -n~mark =~
int from {- theta sub 0} to {theta sub 0}~
theta sup m ~ exp ( -n ~ beta theta sup 2 +
O ( | theta | n sup 1/15 ) ) ~~~d theta
.EN
.sp
.EQ
lineup =~
int from {- theta sub 0} to {theta sub 0}~
theta sup m exp ~
( - n ~ beta theta sup 2 ) ~ d theta ~+~
O ( int from {- theta sub 0} to {theta sub 0} n sup 1/15
| theta | sup m+1 ~exp~(
- n ~ beta  theta sup 2 ) d theta )
.EN
.sp
.EQ
lineup =~
c sub m ( n beta ) sup -(m+1)/2 ~+~O
( n sup 1/15 ( n beta ) sup {-^(m+2)/2} )~,
.EN
.DE
where
$c sub 1 ~=~0$
(since the integrand is odd),
$c sub 0~=~pi sup 1/2$,
$c sub 2 ~=~pi sup 1/2 /2$.
Therefore $J sub 0~>~0$,
$J sub 2 ~>~0$, and (3.6)
holds for $n$ sufficiently large,
$n sup 1/4 ~<=~k~<=~3d n/4$,
and this completes the proof of Theorem 1.
.P
The estimates of the $J sub m$
obtained above yield easily the
estimates for the coefficients
$a sub {k,~n}$ that were mentioned
in the Introduction.
.P
The proof of Theorem 2 is very similar,
and will not be presented in detail.
The major difference is that $alpha$
is bounded below as well as above,
and so an estimate like (3.8) can be
obtained (under the
assumptions of Theorem 2) even when
$p sub 1~=~0$.
To see this we first show that
if (1.1) holds then for large $n$,
for each $theta$ satisfying
$theta sub 0~<=~| theta | ~<=~pi$
($theta sub 0$ defined by (3.7) as before)
there is at least one $j$ with
$p sub j~>~0$ such that the inequality
.DS 2
.EQ (3.14)
cos~ ( theta j ) ~<=~
1~-~ theta sub 0 sup 2 / 4
.EN
.DE
holds.
If there were no such $j$, then for
each $j~>~0$ with $p sub j ~!=~0$
there would be an integer $m sub j~!=~0$
such that
$| ^ m sub j | ~<~j$ and
.DS 2
.EQ
| ^ theta j ~-~ 2 pi m sub j |~<~theta sub 0~.
.EN
.DE
But then
.DS 2
.EQ
| ^ theta ~-~
2 pi m sub j / j | ~<=~ theta sub 0 / j ~<=~theta sub 0
.EN
.DE
for all $j~>~0$ with
$p sub j~!=~0$, and so if $n$ is
sufficiently large (and $delta n~<=~
k~<=~(d- delta ) n )$)
then
.DS 2
.EQ (3.15)
| ^ m sub i j ~-~ m sub j i | ~<~1/2
.EN
.DE
for all $i~>~0$, $j~>~0$ with
$p sub i ~!=~ 0$,
$p sub j ~!=~0$.
But (3.15) means that
.DS 2
.EQ
m sub i j ~=~m sub j i
.EN
.DE
for all $i~>~0$, $j~>~0$ with
$p sub i~!=~ 0$, $p sub j ~!=~ 0$.
If $j sub 0$ denotes the smallest
$j~>~0$ for which $p sub j~!=~0$,
then for each $i~>~0$ with
$p sub i ~!=~0$
we have
.DS 2
.EQ (3.16)
i~=~ m sub i j sub 0 / m sub j sub 0~.
.EN
.DE
Now
$| ^ m sub j |~<~j$, so if $D$ is
the greatest common divisor of
$j sub 0$ and $m sub j sub 0$, then
$j sub 0 / D~!=~1$, and by (3.16),
$j sub 0 / D$ divides all $i~>~0$
with $p sub i ~!=~ 0$, which
contradicts (1.1).
Hence we have shown that (3.14)
holds for every $theta$,
$theta sub 0~<=~| theta | ~<=~pi$,
and some $j$ with $p sub j~!=~0$.
.P
Once (3.14) is established,
an estimate of the form (3.8)
is easily obtained for
$theta sub 0~<=~| ^ theta |~<=~pi$.
Theorem 2 then follows easily from
the estimates for $J sub 0$ obtained
in the proof of Theorem 1.
.bp
.ce
.B
REFERENCES
.R
.sp
.RL
.LI
P. L. Brockett and J. H. B. Kemperman,
On the unimodality of high convolutions,
Ann. Prob. \f210\f1
(1982), 270-277.
.LI
S. Karlin,
\f2Total Positivity\f1,
vol. 1, Stanford Univ. Press, 1968.
.LI
J. Keilson and H. Gerber,
Some results for discrete unimodality,
J. Amer. Statist. Assoc. \f266\f1
(1971), 386-389.
.LI
P. Medgyessy,
\f2Decomposition of Superpositions of
Density Functions and Discrete Distributions\f1,
Wiley, 1977.
.LI
A. M. Odlyzko
and L. B. Richmond, On the unimodality of
some partition polynomials, European J. Comb.,
\f23\f1 (1982), 69-84.
.LI
N. G. Ushakov,
On a problem of Re\*'nyi,
Theory Prob. Appl.,
\f227\f1
(1982), 361-362.
.LI
M. Yamazato, Unimodality of infinitely
divisible distribution functions of class L,
Ann. Prob. \f26\f1 (1978), 523-531.
.LE