.PH ""
.nr Au 0
.nr Hs 7
.nr Hb 7
.ds HP 10 10 10
.nr Pt 1
.am DE
.ls 2
.sp
..
.EQ
delim $$
gsize 10
define sstar % {size 10 *} %
define pprime % {fat prime } %
ndefine CC % C under %
tdefine CC % bold C %
define eqsl % "\o'\(==\(sl'" %
define XX % "=\v'-.1n'\h'-.7m'>" %
define roR % {size 7 bold up 6 | back 10 size 10 roman R } %
.EN
.de ST
.nf
.ta 6iR
	\(sq
.fi
..
.ce 99
.B
Limit Distributions for Coefficients of Iterates of
Polynomials with Applications to Combinatorial Enumerations
.I
.sp
P. Flajolet
.R
.sp
INRIA
78150 Rocquencourt
France
.sp
.I
A. M. Odlyzko
.sp
.R
Bell Laboratories
Murray Hill, New Jersey 07974
USA
.sp 2
.I
ABSTRACT
.sp 2
.R
.ce 0
.P
This paper studies coefficients $y sub h,n$ of
sequences of polynomials
.sp
.ce
$y sub h ( x ) ~=~ sum from {n >= 0} ~y sub h,n x sup n$
.sp
defined by non-linear recurrences.
A typical example to which the results
of this paper apply is that of the sequence
.sp
.ce
$B sub 0 (x) ~=~ 1 , ~~ B sub h+1 (x) ~=~ 1 ~+~x B sub h (x) sup 2 ~~~~roman for~h ~>=~ 0 ~,$
.sp
which arises in the study of binary trees.
For a wide class of similar sequences a
general distribution law for the coefficients
$y sub h,n$ as functions of $n$ with
$h$ fixed is established.
It follows from this law that in many interesting cases
the distribution is asymptotically Gaussian near the peak.
The proof relies on the saddle point
method applied in a region where the polynomials
grow doubly exponentially as
$h ~->~ inf$.
Applications of these results
include enumerations of binary trees
and 2-3 trees.
Other structures of interest in computer
science and combinatorics can also be
studied by this method or its extensions.
.bp
.ce 99
.B
Limit Distributions for Coefficients of Iterates of
Polynomials with Applications to Combinatorial Enumerations
.I
.sp
P. Flajolet
.R
.sp
INRIA
78150 Rocquencourt
France
.sp
.I
A. M. Odlyzko
.sp
.R
Bell Laboratories
Murray Hill, New Jersey 07974
USA
.sp 3
.ce 0
.H 1 "Introduction"
.ls 2
In many enumerative problems in computer
science and combinatorics one encounters
the difficulty that no closed form formulae
exist for the quantities of interest
and only recurrences for generating
functions are available.
.nr P 1
.PH "''- \\\\nP -''"
For example, if $B sub {h,n}$ is the number
of binary trees with $n$ internal nodes
and height $<=~h$, then the
generating polynomials
.DS 3
.EQ
B sub h (z) ~=~ sum from {n >= 0} ~
B sub h,n z sup n
.EN
.DE
satisfy the recurrence [5]
.DS 3
.EQ
left "{"
matrix {
lcol {B sub h (z) ~=~ 1 ~+~ z ( B sub h-1 (z) ) sup 2 above
B sub 0 (z) ~=~ 1 ~.}
lcol {roman for ~ h ~>=~ 1 ~, above nothing}
}
.EN
.DE
In this paper, we introduce a new
method for studying coefficients of
sequences of polynomials that satisfy
recurrences of similar types.
.P
We study sequences of polynomials
$y sub h (z)$, which we will refer to
as PNI-sequences (for positive nonlinear
iteration), with
.DS 3
.EQ (1.1)
y sub h (z) ~=~ sum from n ~ y sub h,n z sup n ~.
.EN
.DE
They are defined by some initial
$y sub 0 (z) ~!=~ 0$ which has
non-negative coefficients and a
recurrence
.DS 3
.EQ (1.2)
y sub h+1 (z) ~=~ P (z , y sub h (z)) ~, ~~~
h ~>=~ 0 ~,
.EN
.DE
where $P (z,y)$ is a polynomial with non-negative
coefficients,
.DS 3
.EQ (1.3)
P ( z , y ) ~=~ sum from {0 <= k <= d} ~
P sub k (z) y sup k ~~~~roman with~ ~ p sub d (z) ~!=~ 0 ~, ~~~
d ~>~ 1 ~.
.EN
.DE
We define
.DS 3
.EQ (1.4)
mu ~ mark =~ lim from {h -> inf} ~ d sup -h ~
roman deg ~ y sub h (z) ~,
.EN
.sp
.EQ (1.5)
rho ~ lineup =~ roman "inf" ~ "{" x ~:~ x epsilon roR sup + ~, ~~
y sub h (x) ~->~ inf ~ roman as ~
h ~->~ inf "}" ~.
.EN
.DE
Clearly $mu$ and $rho$ exist and are finite for every PNI-sequence
$"{" y sub h (z) "}"$
that contains non-constant polynomials.
As will be explained below, it is
sufficient to consider
PNI-sequences which
$P ( z , y )$ and $y sub 0 (z)$
satisfy the following conditions:
.VL 10 5
.LI "(A)"
$P ( z , y )$ is not a
monomial (i.e., $P ( z,y) ~!=~ bz sup a y sup d )$.
.LI "(B)"
At least one of the $y sub h , ~ 0 ~<=~ h ~<=~ 2$
has the property that
$| y sub h (z) | ~=~ y sub h (1) ~
and ~ | z | ~=~ 1 ~XX~ z ~=~ 1 $.
.LE
We prove two main results.
.sp
.I
Theorem 1.
Suppose that $"{" y sub h (z) "}"$ is a
PNI-sequence that satisfies conditions (A) and (B),
and
let $lambda sub 1$ and $lambda sub 2$ be any
real numbers that satisfy
.DS 3
.EQ
0 ~<~ lambda sub 1 ~<~ lambda sub 2 ~<~ mu ~.
.EN
.DE
Then for any integers $n$ and $h$ with
.DS 3
.EQ
lambda sub 1 ~<=~ nd sup -h ~<=~ lambda sub 2
.EN
.DE
we have, uniformly in $n$ and $h$,
.DS 3
.EQ (1.6)
y sub h,n ~=~
{r p sub d (r) sup {-1 /(d-1)} exp
(d sup h ( beta (r) - r beta prime (r) ~
log ~ r ))} over
{d sup h/2 ~ sqrt {2 pi ( r sup 2 beta prime prime
(r) ~+~ r beta prime (r) ) }} ~
( 1 ~+~ O ( d sup {- h/2 } )) ~,
.EN
.DE
where $r$ is the unique solution
in $( rho , inf )$ of
.DS 3
.EQ
r beta prime (r) ~=~ n d sup -h ~,
.EN
.DE
and $beta (z) $ is a function which is
defined on $( rho , inf )$ by
.DS 3
.EQ (1.7)
beta (z) ~=~ log ~ y sub 0 (z) ~+~
1 over {d-1} ~ log ~
p sub d (z) ~+~
sum from {j=0} to inf ~
d sup {-j-1} ~
log ~ left "{"
{y sub {j+1} (z) } over
{p sub d (z) y sub j (z) sup d } right "}" ~,
.EN
.DE
and is analytic there.
.sp
Theorem 2.
Suppose that $"{" y sub h (z) "}"$
satisfies the conditions of Theorem\ 1.
Let $N sub h sup sstar$ denote some
$n$ for which $y sub h,n$ is maximal.
If $rho ~>=~ 1$, then
.DS 3
.EQ
lim from {h -> inf} ~
d sup -h N sub h sup sstar ~=~ 0 ~.
.EN
.DE
If $rho ~<~ 1$, then
.DS 3
.EQ (1.8)
N sub h sup sstar ~ wig ~
beta prime (1) d sup h ~~ roman as ~~
h ~->~ inf ~,
.EN
.DE
and the $y sub {h,~n}$ are
asymptotically Gaussian near the peak; for
.DS 3
.EQ 
| n - N sub h sup sstar | ~=~ 
O (d sup {2 h / 3} )
.EN
.DE
we have
.DS 3
.EQ (1.9)
{y sub h,n} over
{y sub {h , N sub n sup sstar}} ~=~
exp ( ~-~ 1 over 2 ~ sigma sup -2
d sup -h ( n - N sub h sup sstar ) sup 2 )
( 1 + O ( d sup -2h
| n - N sub h sup sstar | sup 3 )) ~,
.EN
.DE
where
.DS 2
.EQ
sigma sup 2~=~
beta prime (1) + beta prime prime (1)~.
.EN
.DE
.R
.P
In the remainder of this section we
first make some remarks
about these theorems, and then discuss
their connections
to other work.
Section 2 proves a series of auxiliary
results that are at the heart of our
method, and from which theorems 1 and 2
are easily deduced in Section 3.
Section 4 presents some applications,
possible extension, and numerical results.
.P
Both theorems 1 and 2 give information about
the coefficients of the polynomials
$y sub h (z)$ in terms of the
function $beta (z)$, which is defined by
(1.7) in terms of the polynomials
$y sub h (z)$.
This is not circular, however, since the
series in (1.7) is extremely rapidly
convergent, and is determined to great
accuracy by just a few initial terms.
Differentiating the basic recurrence (1.2)
yields a recurrence for $y sub h+1 sup pprime (z)$
in terms of $y sub h (z)$ and $y sub h sup pprime (z)$,
and therefore the definition (1.7) of $beta (z)$
also gives a rapid way to compute the derivatives
of $beta (z)$.
As is shown by the examples in Section 4,
the approximations (1.6) and (1.9) are
very accurate even for small values of $h$.
.P
Many of the hypotheses of our theorems can be
weakened.
It is not essential, for example, that all
the coefficients of $P(z,y)$ or of the $y sub h (z)$
be nonnegative.
What is really crucial is that the $y sub h (z)$
should grow very rapidly as $h~->~inf$ on the
positive real axis and should be relatively
small elsewhere.
(cf. [6,7,14].)
However, the appropriate growth conditions are
not always easy to check, and so we have
chosen to restrict our presentation to PNI-sequences,
which are easy to characterize, and which are
of greatest interest in computer science and
combinatorics.
.P
Condition (A) is not necessary for
the success of our method.
In fact, Theorem\ A holds for PNI-sequences
which satisfy condition (B) but not condition
(A), except that $lambda sub 1$ may have
to be bounded below away from 0.
However, for PNI-sequences that do not satisfy
condition (A), the definition of
$beta (z)$ can be simplified.
We note that if $y sub h (z)$ is a
PNI-sequence for which condition (A)
fails to hold, then
.DS 3
.EQ
P ( z , y ) ~=~ b z sup a y sup d ~,
.EN
.DE
for some $b ~>~ 0 $, $a ~>=~ 0$ and so
.DS 3
.EQ
y sub h (z) ~=~ ( b z sup a ) sup
{{d sup h -1} over {d-1}}
y sub 0 (z) sup {d sup h} ~,
.EN
.DE
and we can reduce to the study of
coefficients of high powers
of $y sub 0 (z)$.
These, however, can be investigated
much more directly, without developing
most of the analytic machinery of
paper through use of the central
limit theorem.
Much stronger results can also be proved in
this situation [12].
.P
Condition (B) is very easy to check,
since a polynomial
.DS 3
.EQ
y (z) ~=~ sum from k=0 to m ~
a sub k z sup {e sub k} , ~~~
0 ~<=~ e sub 0 ~<~ e sub 1 ~<~  . . . 
~<~ e sub m , ~~~
a sub 1 , . . . , a sub m ~>~ 0 ~,
.EN
.DE
has the property that $| y (z) | ~=~ y (1)$
and $| z | ~=~ 1$ imply
$z ~=~ 1$ if and only if
.DS 3
.EQ
roman gcd ( e sub 1 - e sub 0 , ~ e sub 2 - e sub 0 , . . . ,
e sub m - e sub 0 ) ~=~ 1 ~,
.EN
.DE
which holds if and only if $y (z)$ is not of the form
.DS 3
.EQ (1.10)
y (z) ~=~ z sup {e sub 0} y * ( z sup d )
.EN
.DE
for some polynomial $y * (z)$ and some
$d ~>~ 1$.
The function of condition (B) is to ensure
(see Lemma\ 2.1) that for large $h$, the
$y sub h (z)$ are not of the form (1.10),
since in that case our theorems are obviously
not true.
However, PNI-sequences of polynomials $y sub h (z)$ for
which each $y sub h (z)$ is of the form
.DS 2
.EQ
z sup e sub h y sub h sup sstar (z sup d )
.EN
.DE
can be studied by our method by looking at the
sequences $y sub h sup sstar (z)$, provided
$d$ is chosen to be maximal.
We also note that by the proof of
Lemma\ 2.1, condition (B) is equivalent
to only $y sub 2 (z)$ having the
specified property.
Lemma\ 2.2 shows that condition (B)
cannot be weakened.
.P
Theorems 1 and 2 are proved in Section\ 3,
while Section\ 2 proves a number of
auxiliary lemmas.
The proofs rely on an analysis of the
behavior of the polynomials $y sub h (z)$
as $h ~->~ inf$, for
$z member CC ~,~ | z | ~>~ rho$.
It is shown that for $z$ in a narrow
strip of the form
$ Re ~ z ~>~ rho ~+~ delta $,
$| Im  ~ z | ~<~ delta$ for some
fixed $delta ~>~ 0$, the polynomials
$y sub h (z)$ exhibit doubly
exponential growth:
.DS 3
.EQ (1.11)
y sub h (z) ~=~ g ( z) alpha (z) sup
{d sup h} ( 1 + o (1) ) ~~~~~
roman as ~ h ~->~ inf
.EN
.DE
for certain functions $alpha (z)$,
$g (z)$, and that the
$y sub h (z)$ are considerably
smaller away from the real axis.
The precise estimates we obtain enable us
to determine the asymptotic behavior
of the
$y sub {h,n}$ by expressing
them as contour integrals and using
the saddle point method.
.P
The key to the success of this
method is the doubly exponential growth (1.11)
of the $y sub h (z)$.
Equation (1.11) generalizes the
results of Aho and Sloane [2] about
integer sequences satisfying nonlinear
recurrences of the type
.DS 3
.EQ
x sub {n+1} ~=~ x sub n sup 2 ~+~ g sub n
.EN
.DE
with $| g sub n | ~<~ {x sub n} over 4$
for $n ~>=~ n sub 0$.
.P
Our results are related to the immense
literature on the subject of rational
iteration.
(See, for example, [3,4,8].)
Most of the papers in that area
are concerned with questions of convergence
of iteration.
In this paper, on the other hand,
we are operating almost exclusively
in the region of divergence, and we
concentrate on the rate and nature
of divergence.
In other situations, such as those of
[5,10,11,13], it is advantageous to study
the iteration either within the convergence
region or else right on the boundary
between convergence and divergence.
Methods similar to some of those used
in those papers could also be used to
obtain more information than is provided
by Theorem\ 2 when $rho ~>=~ 1$.
.H 1 "Proofs of Auxiliary Results"
As a first step, we prove a technical
result which will enable us to show
that the polynomials $y sub h (z)$
are very small away from the positive
real axis.
.sp
.I
Lemma 2.
If $"{" y sub h (z) "}"$ is a PNI-sequence
of polynomials that satisfies
Condition\ (B), then for every $h ~>=~ 2$
and every $r epsilon roR sup +$,
.DS 3
.EQ
| y sub h (z) | ~=~ y sub h (r) ~ ~~and~~ ~
| z | ~=~ r ~~~XX~~ ~ z ~=~ r ~.
.EN
.DE
.sp
Proof.
.R
Let $"{" y sub h (z) "}"$ satisfy the
hypotheses of the lemma.
Since $y sub n (z)$ has nonnegative
coefficients, for $| z |~=~r$, $z~!=~0$,
we have
.DS 3
.EQ (2.1)
| y sub h (z) | ~=~ | sum from n ~ y sub h,n
z sup n | ~<=~ sum from n ~ y sub h,n r sup n ~=~
y sub h ( r ) ~,
.EN
.DE
and equality can hold if and only if for
some $gamma epsilon CC$ with
$| gamma | ~=~ 1$,
.DS 3
.EQ (2.2)
y sub h,n z sup n ~~=~ gamma y sub h,n r sup n ~~~~
roman {for~all~} n ~.
.EN
.DE
Let $u~=~z/r~=~z/ | z |$. Then
(2.2) is equivalent to
.DS 3
.EQ
y sub h,n u sup n ~=~ gamma y sub h,n ~~~~
roman {for~all~} n ~,
.EN
.DE
which is equivalent to
$| y sub h (u) | ~=~ y sub h (1) $.
Thus $| y sub h (z) | ~=~ y sub h (r)$
holds for some $z ~!=~ r $, $| z | ~=~ r$
if and only if
$| y sub h (u) | ~=~ y sub h (1)$ holds
for some $u ~!=~ 1$, $| u | ~=~ 1$.
.P
Suppose now that $m ~>=~ 1$ and that for
some $z$ with $| z | ~=~ 1$ we have
$| y sub m (z) | ~=~ y sub m (1)$.
The recurrence (1.1) implies that
.DS 3
.EQ (2.3)
| sum from k=0 to d ~ p sub k (z)
y sub m-1 (z) sup k | ~=~ sum from k=0 to d ~
p sub k (1) y sub m-1 (1) sup k ~.
.EN
.DE
Since all the coefficients of
$y sub m-1 (z)$ and of the
$p sub k (z)$ are nonnegative,
.DS 3
.EQ
| p sub k (z) | ~ mark <=~ p sub k (1) ~, ~~~
0 ~<=~ k ~<=~ d ~,
.EN
.sp
.EQ
| y sub m-1 (z) | ~ lineup <=~ y sub m-1 (1) ~,
.EN
.DE
and so (2.3) can hold only if
$| y sub m-1 (z) | ~=~ y sub m-1 (1)$.
Repetition of this argument shows
that if for some
$z ~!=~ 1$, $| z | ~=~ 1$, we have
$| y sub h (z) | ~=~ y sub h (1)$
for some $h ~>=~ 2$, then
$| y sub m (z) | ~=~ y sub m (1)$ for
$0 ~<=~ m ~<=~ h$, and this contradicts
Condition\ (B) and proves the lemma.
.ST
.sp
.P
Lemma 2.1 guarantees that for PNI-sequences
$"{" y sub h (z) "}"$ that satisfy
Condition\ (B), $y sub h (z)$ for
$h ~>=~ 2$ achieves a unique
maximum on $| z | ~=~ r$ at $r$.
This means, in particular, that
for large $h$, $y sub h (z)$ will not
be of the form
.DS 3
.EQ (2.4)
y sub h (z) ~=~ z sup {a sub h} y sub h
sup sstar (z sup m )
.EN
.DE
for some polynomials $y sub h sup sstar (u)$
and some $m ~>~ 1$.
The next Lemma shows that Condition\ (B) is
in a sense
best possible for our problem because
if it is violated, then the polynomials
$y sub h (z)$ can be written in the form (2.4),
and theorems\ 1 and 2 clearly
cannot hold for such polynomials.
The same result would not follow if we only
imposed conditions on $y sub 0 (z)$
and $y sub 1 (z)$, as is shown by the
PNI-sequence defined by
$y sub 0 (z) ~=~ 1$,
$P ( z , y ) ~=~ zy + z sup 3 y sup 2$.
In this example
$| y sub h (-1) |~=~y sub h (1)$ for $h~=~0,1$,
but not for $h~=~2$, and this sequence does
satisfy Condition (B).
.sp
.I
Lemma 2.2.
If $"{" y sub h (z) "}"$ is a PNI-sequence
of polynomials, and there is a
$z ~!=~ 1$, $| z | ~=~ 1$,
such that $| y sub 2 (z) | ~=~ y sub 2 (1)$,
then there is an integer $r ~>=~ 2$ such that
for each $h ~>=~ 0$,
.DS 3
.EQ (2.5)
y sub h (z) ~=~ z sup {a sub h } y sub n sup sstar
( z sup r ) ~,
.EN
.DE
where the $y sub h sup sstar (n)$ are polynomials.
.sp
Proof.
.R
Suppose that $z ~!=~ 1$,
$| z | ~=~ 1$, and
$"{" y sub h (z) "}"$ satisfy
the hypotheses of the lemma.
By the arguments used in the proof
of Lemma\ 2.1, we see that
$| y sub 1 (z) | ~=~ y sub 1 (1)$ and
$| y sub 0 (z) | ~=~ y sub 0 (1)$ as well.
.P
If $y sub {2,n} ~=~ 0$ for $n ~<~ m$ and
$y sub {2,m} ~!=~ 0$, then
$| y sub 2 (z) | ~=~ y sub 2 (1)$ implies that
.DS 3
.EQ (2.6)
| sum from {n >= m} ~
y sub 2,n z sup n-m | ~=~
sum from {n >= m} ~ y sub 2,n ~.
.EN
.DE
Since the first term inside the absolute
value sign in (2.6) is
$y sub 2,n ~>~ 0$, equality can hold
if and only if
.DS 3
.EQ
y sub 2,n z sup n-m ~=~ y sub 2,n ~~~~
roman {for~all}~ n ~.
.EN
.DE
Therefore either $y sub 2,n ~=~ 0$ for all
$n ~>~ m$ (i.e., $y sub 2 (x)$ is a monomial) or
else $z sup g ~=~ 1$ for some integer
$g ~>=~ 2$, and if $g$ is chosen to be minimal
such that $z sup g ~=~ 1$, then $y sub 2,n ~=~ 0$
if $n ~ eqsl ~m$ (mod $g$).
In the second case, if $r$ is
any prime factor of $g$, then
$y sub 2,n ~=~ 0$ if
$n ~ eqsl ~ m $ (mod $r$).
The same arguments show that each of
$y sub h (x)$, $h ~=~ 0,1$ is either
a monomial or else has the property
that $y sub h,n ~=~ 0$ if
$n ~ eqsl ~ e sub h $ (mod $r$),
where $e sub h$ is the smallest
integer $n$ such that
$y sub h,n ~ eqsl ~ 0$.
Therefore each $y sub h (x)$,
$0 ~<=~ h ~<=~ 2$, which is
not a monomial, can be written
in the form
.DS 3
.EQ (2.8)
y sub h (x) ~=~ x sup {e sub h }
y sub h sup sstar (x sup r ) ~,
.EN
.DE
where $y sub h sup sstar (t)$ is
a polynomial.
But any monomial can obviously be written
in the form (2.8), so we conclude
that a representation of that form exists
for each $y sub h (x) $,
$0 ~<=~ h ~<=~ 2$.
.P
Write
.DS 3
.EQ (2.9)
P ( x , y ) ~=~ sum from
{0 <= i , j < r} ~
g sub i,j ( x sup r , y sup r ) x sup i
y sup j ~,
.EN
.DE
where the $g sub i,j ( u , v )$ are
polynomials with nonnegative coefficients
which are uniquely determined by (2.9).
Then by the basic recurrence (1.2),
.DS 3
.EQ
y sub 1 (x) ~=~ x sup {e sub 1}
y sub 1 sup sstar ( x sup r ) ~=~
sum from i,j ~ g sub i,j 
( x sup r , y sub 0 
(x) sup r ) x sup {i + e sub 0 j}
y sub 0 sup sstar ( x sup r ) sup j ~,
.EN
.DE
so we must have
.DS 3
.EQ (2.10)
e sub 1 ~==~ i ~+~ e sub 0 j ~~
( roman mod ~ r )
.EN
.DE
for each pair $( i , j )$ such that
$g sub i,j ( u , v) ~!=~ 0$.
Similarly,
.DS 3
.EQ
y sub 2 (x) ~=~ x sup {e sub 2}
y sub 2 sup sstar ( x sup r ) ~=~
sum from i,j ~ g sub i,j
( x sup r , y sub 1 (x) sup r ) 
x sup {i + e sub  1 j}
y sub 1 sup sstar ( x sup r ) sup j ~,
.EN
.DE
so that we must have
.DS 3
.EQ (2.12)
e sub 2 ~==~ i ~+~ e sub 1 j
~~ ( roman mod ~ r )
.EN
.DE
for each pair $( i, j )$ with
$g sub i,j ( u , v ) ~!=~ 0 $.
.P
Suppose first that there are
two distinct pairs $( i,j )$
such that $g sub i,j ( u , v ) ~!=~ 0$.
Call them $( i sub 1 , j sub 1 )$
and $( i sub 2 , j sub 2 )$.
Then by (2.11),
.DS 3
.EQ (2.13)
i sub 1 ~ mark ==~ e sub 1 ~-~
e sub 0 j sub 1 ~~~~ ( roman mod ~ r ) ~,
.EN
.sp
.EQ
i sub 2 ~ lineup ==~ e sub 1 ~-~
e sub 0 j sub 2 ~~~~ ( roman mod ~ r ) ~,
.EN
.DE
and if $j sub 1 ~==~ j sub 2 $ (mod $r$),
then we would have $i sub 1 ~==~ i sub 2$
(mod $r$), which is a contradiction,
since $0 ~<=~ i sub 1 , i sub 2 , j sub 1 , j sub 2 ~<=~ r ~-~ 1$
and $( i sub 1 , j sub 1 ) ~!=~ ( i sub 2 , j sub 2 )$.
Hence $j sub 1 ~eqsl~ j sub 2$ (mod $r$).
Then by (2.12) and (2.13)
.DS 3
.EQ
e sub 2 ~==~ e sub 1 ~+~ ( e sub 1 - e sub 0 )
j sub 1 ~==~ e sub 1 ~+~ ( e sub 1 - e sub 0 )
j sub 2 ~~~~ ( roman mod ~ r ) ~,
.EN
.DE
which implies that $e sub 1 ~==~ e sub 0$
(mod $r$), since
$j sub 1 ~ eqsl ~ j sub 2 $ (mod $r$) and
$r$ is prime.
But in that case
.DS 3
.EQ
e sub 0 ~==~ i ~+~ e sub 0 j ~~ ( roman mod ~ r )
.EN
.DE
for all pairs $( i , j )$ with
$g sub i,j ( u , v ) ~!=~ 0$,
and then an inductive argument
using (2.9) shows that
.DS 3
.EQ
y sub h (x) ~=~ x sup {e sub 0} y sub n sup sstar
( x sup r )
.EN
.DE
for all $h ~>=~ 0$, and this gives
the desired result.
.P
To conclude the proof of the lemma,
it only remains to consider the case
that there is only one pair
$( i, j )$ with $g sub {i,j} ( u, v ) ~!=~ 0$.
But then
.DS 3
.EQ (2.14)
y sub h+1 (x) ~=~ g sub i,j
( x sup r , y sub h ( x ) sup r ) x sup i
y sub h ( x ) sup j ~,
.EN
.DE
and since (2.8) holds for
$0 ~<=~ h ~<=~ 2$, (2.14) shows
that it holds for all
$h ~>=~ 2$ with appropriate $e sub h$.
Thus the lemma is true in this case as well.
.ST
.P
We now derive a series of lemmas
giving size estimates for the polynomials
$y sub h (z)$ which will lead to proofs
of theorems\ 1 and 2.
.sp
.I
Lemma 2.3.
Suppose that $"{" y sub h (z) "}"$ is a
PNI-sequence of polynomials and define
.DS 3
.EQ
rho ~=~ roman "inf" ~ "{" x ~: ~ x member roR sup + , ~
y sub h (x) ~->~ inf ~ roman as
~ h ~->~ inf "}" ~.
.EN
.DE
Then for every $delta ~>~ 0$, there exist
positive constants $gamma$, $eta$, $xi$
such that for $z$ in the region
.DS 3
.EQ (2.15)
R ( delta ) ~=~ "{" z ~: ~ | Im
(z) | ~<=~ eta , ~ rho ~+~ delta ~<=~
Re (z) ~<=~ delta sup -1 "}"
.EN
.DE
we have
.DS 3
.EQ (2.16)
| y sub h (z) | ~>=~ gamma ~
exp ( xi d sup h ) ~.
.EN
.DE
.sp
Proof.
.R
Choose $eta sub 1 ~>~ 0$ so small
that $p sub d (z)$ has no zeros
in the region
.DS 3
.EQ
R sub 1 ~=~ "{" z ~: ~ | Im
(z) | ~<=~ eta sub 1 , ~
rho ~+~ delta ~<=~ Re (z) ~<=~ delta sup -1 "}" ~,
.EN
.DE
and let
.DS 3
.EQ
a ~=~ min left "{" min from {z member R sub 1} ~
left | 1 over 2 ~ p sub d (z) right | , ~
1 over 2 right "}" ~.
.EN
.DE
Then for any large enough $K sub 1$ we must have
.DS 3
.EQ (2.17)
| P ( z , y ) | ~>~ a | y | sup d
.EN
.DE
if $z member R sub 1$ and
$| y | ~>=~ K sub 1 $, as can be seen
from the inequality
.DS 3
.EQ
| P ( z , y ) | ~>~ | p sub d (z) | ~
| y | sup d ~ | 1 ~-~ sum from k=0 to
d-1  ~ | {p sub k (z)} over {p sub d (z)} | ~
|y | sup k-d | ~,
.EN
.DE
and the fact that the $p sub k (z)$
are bounded for $z member R sub 1$.
.P
If
.DS 3
.EQ
| y | ~ >~ a sup {- 1/(d-1)} ~, 
.EN
.DE
then
.DS 2
.EQ
a | y | sup d ~ >~ | y | ~,
.EN
.DE
so that if
.DS 3
.EQ
K sub 2 ~=~ max ( K sub 1 , a sup {- 1/(d-1)} ) ~,
.EN
.DE
and if
.DS 3
.EQ
u sub 0 ~=~ y ~ ~~and~~ ~
u sub n+1 ~=~ P ( z , u sub n ) ~ ~~for~~ ~
n ~>=~ 0 ~,
.EN
.DE
then for $z member R sub 1 , | y | ~>=~ K sub 2$
we have
.DS 3
.EQ (2.18)
u sub k ~>=~ a sup
{{d sup k - 1} over {d-1}} | y | sup
{d sup k} ~.
.EN
.DE
Therefore, if $| y |$ is large enough,
the $u sub k$ exhibit doubly exponential
growth.
.sp
Set
.DS 3
.EQ
K sub 3 ~=~ max ( K sub 2 , 2 a sup -1 ),
.EN
.DE
and let $h sub 0$ be such that
.DS 3
.EQ
y sub h sub 0 ( rho + delta ) ~>=~ 2 ^ K sub 3 ~.
.EN
.DE
Since $y sub h sub 0 (z)$ is continuous
and increasing along the positive
real axis, we can find $eta sub 2$
such that $0 ~<~ eta sub 2 ~<~ eta sub 1$ and if
.DS 3
.EQ
R sub 2 ~=~ "{" z ~:~ | Im (z)
| ~<=~ eta sub 2 , ~ rho + delta ~<=~
Re (z) ~<=~ delta sup -1 "}" ~,
.EN
.DE
then
.DS 3
.EQ
| y sub {h sub 0} (z) | ~>=~ K sub 3
.EN
.DE
for $z member R sub 2 $.
But then the estimate (2.18) applies, and
.DS 3
.EQ
| y sub {h sub 0 +k} ( z ) |~>=~
a sup {{d sup k -1} over {d-1}}
K sub 3 sup {d sup k} ~>=~
left ( K sub 3 a sup {- 1/(d-1)} right ) sup {d sup k} ~>=~
2 sup {d sup k} ~,
.EN
.DE
so that the estimate (2.16)
of the lemma clearly applies for
$h ~>=~ h sub 0$ and
$z member R sub 2$ if we take
$gamma$ and $xi$ small enough.
.P
To complete the proof, it suffices
to extend the estimate (2.16) to all $h$.
We note that if $eta epsilon ( 0 , eta sub 2)$
is chosen small enough, then none of the
polynomials $y sub 0 (z) , . . . , y sub {h sub 0 -1} (z)$
will have a zero in the region
$R ( delta ) ~\(ib~ R sub 2$ defined
by (2.15), so that (2.16) will hold
for these $y sub h (z)$ also in that region
if we take $gamma$ small enough.
.ST
.sp
.I
Lemma 2.4.
If $"{" y sub h (z) "}"$ is a PNI-sequence
that satisfies Condition\ (B),
then for any $delta , eta ~>~ 0$ there
is a constant $omega ~>~ 0$ such that
for $h ~>=~ 2$, $rho ~+~ delta ~<=~ | z | ~<=~ delta sup -1$,
and
.DS 3
.EQ
z nomem R ( delta , eta ) ~=~ "{" z ~: ~ rho ~+~
delta ~<=~ | z | ~<~ delta sup -1 , ~
| Im (z) | ~<~ eta "}" ~,
.EN
.DE
we have
.DS 3
.EQ (2.19)
| y sub h (z) | ~<=~ y sub h ( | z | ) ~
exp ( - omega d sup h ) ~.
.EN
.DE
.sp
Proof.
.R
By Lemma 2.3, if $h$ is large enough,
say $h ~>=~ h sub 0$, and
.DS 3
.EQ
| y sub h (z) | ~<=~ y sub h ( | z | ) ~
exp ( - c )
.EN
.DE
for some positive $c$,
$e sup c ~<=~ y sub h ( | z | ) sup half $, then
.DS 3
.EQ
| y sub h+1 (z) | ~ mark <=~
P ( | z | , y sub h ( | z | ) e sup -c )
.EN
.sp
.EQ
lineup <=~ p sub d ( | z | )
y sub h ( | z | ) sup d e sup { - cd} ~
sum from k=0 to d ~
{p sub d-k ( | z | )} over
{p sub d ( | z | )} ~
y sub h ( | z | ) sup -k
e sup ck
.EN
.sp
.EQ (2.20)
lineup <=~ y sub h+1 ( | z | ) e sup -cd
( 1 ~+~ O ( e sup c y sub h ( | z | ) sup -1 )) 
.EN
.sp
.EQ
lineup <=~ y sub h+1 ( | z | ) ~ exp
( - cd + 2c xi sup -1 d sup -h ) ~<=~ y sub h+1
( | z | ) ~ exp ( - cd ( 1 - d sup -h/2 )) ~.
.EN
.DE
By Lemma 2.1, 
.DS 3
.EQ (2.21)
| y sub {h sub 0} ( z ) | ~<=~
y sub {h sub 0 } ( | z | ) e sup {- epsilon }
.EN
.DE
for all $z$, $z nomem R ( delta )$,
$rho ~+~ delta ~<=~ | z | ~<=~ delta sup -1$
and some $epsilon ~>~ 0$, so that (2.20)
implies
.DS 3
.EQ (2.22)
| y sub {h sub 0 +k} (z) |
~ mark <=~ y sub {h sub 0 + k}
( | z | ) ~ exp ( - epsilon d sup k
~ PI from {j = h sub 0 } to
{h sub 0 + k-1} ~
( 1 - d sup {- j /2} ))
.EN
.sp
.EQ
lineup <=~ y sub {h sub 0 + k} ( | z | ) ~
exp ( - epsilon d sup k / 2 ) ~,
.EN
.DE
which proves the lemma for
$h ~>=~ h sub 0$.
But the estimate (2.19) follows
trivially for $2 ~<=~ h ~<=~ h sub 0 ~-~ 1$
from Lemma\ 2.1 if we choose $omega$ small enough.
.ST
.sp
.I
Lemma 2.5.
If $"{" y sub h ( z ) "}"$ is a PNI-sequence,
then for any $delta ~>~ 0$ there is a
$xi ~>~ 0$ such that for
$z member R ( delta )$ (defined as in
Lemma\ 2.3 ) we have
.DS 3
.EQ
y sub h ( z ) ~=~ exp ( d sup h beta (z) ~-~
1 over {d - 1} ~ log ~ P sub d ( z ) )
( 1 ~+~ O ( exp ( - xi d sup h ))) ~,
.EN
.DE
where $beta (z)$ is defined
as in Theorem\ 1 and is analytic
in $R ( delta )$.
.sp
Proof.
.R
Since none of the $y sub h (z)$ has a zero
in $R ( delta )$, we can define
.DS 3
.EQ (2.23)
v sub h ( z ) ~=~ log ~ y sub h (z) ~,
.EN
.DE
where for real $z$, we take the
principal value of the logarithm, and
for $z member R ( delta ) ~-~ roR$, the
logarithm is determined by analytic continuation.
The basic recurrence (1.2) can be written
.DS 3
.EQ (2.24)
y sub h+1 ( z ) ~=~ p sub d (z) y sub h (z) sup d
left ( 1 ~+~
{q ( z , y sub h ( z ) )} over
{p sub d ( z ) y sub h ( z ) sup d} right ) ~,
.EN
.DE
where
.DS 3
.EQ (2.25)
q ( z , y ) ~=~ P ( z , y ) ~-~ p sub d
(z) y sup d ~.
.EN
.DE
Taking logarithms of both sides of
(2.24), we obtain
.DS 3
.EQ (2.26)
v sub h+1 (z) ~=~ d v sub h (z) ~+~
log ~ p sub d (z) ~+~ log left (
1 ~+~ {q ( z , y sub h (z) )} over
{p sub d (z) y sub n (z) sup d }
right )~.
.EN
.DE
Since
.DS 3
.EQ
v sub 0 (z) ~=~ log ~
y sub 0 (z) ~,
.EN
.DE
iterating (2.26) yields
.DS 3
.EQ (2.27)
v sub h (z) ~=~ d sup h
log ~ y sub 0 (z) ~~+~
{d sup h -1} over {d-1} ~
log ~ p sub d (z) ~+~
sum from m=1 to h ~
d sup j-1 r sub h-j (z)~,
.EN
.DE
where
.DS 3
.EQ (2.28)
r sub j (z) ~=~ log
left ( 1 ~+~
{q ( z , y sub j (z))} over
{p sub d (z) y sub j (z) sup d}
right ) ~.
.EN
.DE
.P
We now introduce the function
.DS 3
.EQ (2.29)
beta (z) ~=~ log ~ y sub 0 (z)
~+~ 1 over d-1 ~ log ~ p sub d (z) ~+~
sum from j=0 to inf
~ d sup {- j - 1} r sub j (z) ~.
.EN
.DE
By Lemma 2.3, the $r sub j (z)$ are
bounded in $R ( delta )$, so
the series in (2.29)
converges and makes $beta (z)$
an analytic function for $z member R ( delta )$.
Furthermore, (2.27) shows that
.DS 3
.EQ (2.30)
v sub h ( z ) ~=~ d sup h
beta (z) ~-~ 1 over d-1 ~ log ~
p sub d (z) ~-~ sum from j=0 to inf ~
d sup {-j-1} r sub h+j (z) ~,
.EN
.DE
and by Lemma 2.3 the last sum in (2.30) is
.DS 3
.EQ
O ( exp ( - xi d sup h ))
.EN
.DE
for some $xi ~>~ 0$, which concludes
the proof of the lemma.
.ST
.P
For further reference, we note that it
follows from (2.23), (2.29), and (2.30) that
.DS 3
.EQ (2.31)
beta (z) ~=~ lim from {h -> inf} ~
d sup -h v sub h (z) ~=~ lim from
{h -> inf} ~
d sup -h ~ log ~ y sub h (z)~.
.EN
.DE
In Lemma 2.5, $beta (z)$ was defined
for $z member R ( delta )$.
However, the definition of $beta (z)$ does
not depend on $delta$, so we conclude
that $beta (z)$ is defined and analytic
in the union of all the $R ( delta )$ for
$delta ~>~ 0$.
.P
Before proceeding to the proofs of the
theorems, we prove some auxiliary results
about $beta (z)$.
.sp
.I
Lemma 2.6.
Suppose $"{" y sub n (z) "}"$ is a
PNI-sequence which satisfies conditions\ (A) and (B),
and let $mu , rho$ be defined by
(1.4) and (1.5), respectively.
Then
.DS 3
.EQ (2.32)
( z beta prime (z) ) prime ~>~ 0 ~~~~
for ~ z member (  rho , inf ) ~,
.EN
.DE
and
.DS 3
.EQ (2.33)
lim from {z -> inf} ~
z beta prime (z) ~=~
mu~.
.EN
.DE
If $P ( z , y ) $ is not a monomial
(i.e., $P ( z , y ) ~!=~ bz sup a y sup d ) $,
then
.DS 3
.EQ (2.34)
lim from {z -> rho +} ~ z beta prime (z) ~=~ 0 ~.
.EN
.DE
.sp
Proof.
.R
By (2.31), for any $z member ( rho , inf )$, we have
.DS 3
.EQ (2.35)
z beta prime (z) ~=~ lim from
{h -> inf } ~ d sup -h ~
{z y sub h sup pprime (z)} over
{y sub h (z) } ~.
.EN
.DE
We first observe that for any entire
function $f (z)~!=~0$ with nonnegative Taylor
series coefficients,
.DS 3
.EQ
f (z) ~=~ sum from k=0 to inf ~
f sub k z sup k ~, ~~~~ f sub k ~>=~ 0 ~,
.EN
.DE
the quotient
.DS 3
.EQ
g (z) ~=~ {z f prime (z)} over
{f (z) }
.EN
.DE
is an increasing function of $z$ for
$z member roR sup +$, since
computing the derivative of $g (z)$
yields
.DS 3
.EQ (2.36)
z g prime (z) ~=~ z sup 2 ~
{f prime prime (z)} over {f (z)} ~+~
z ~ {f prime (z)} over {f (z)} ~-~
left ( { z f prime (z)} over
{f (z)} right ) sup 2 ~,
.EN
.DE
and the quantity on the right side
of (2.36) is the variance of the random
variable $X$ such that
.DS 3
.EQ
roman Pr ( X = k ) ~=~
{f sub k z sup k} over {f (z)} ~.
.EN
.DE
Moreover, we see that
$g prime (z) ~=~ 0$ is possible if and
only if only one of the $f sub k$ is $!=~0$.
.P
Next, we prove that if
$f (z) ~=~ f sub 1 (z) ~+~ f sub 2 (z)$,
where $f sub 1 (z)$ and $f sub 2 (z)$ are
both nonzero entire functions with nonnegative Taylor
coefficients,
.DS 3
.EQ
f sub i (z) ~=~ sum from k=0 to inf ~
f sub i,k z sup k ~, ~~~~ i ~=~ 1,2,
.EN
.DE
then
.DS 3
.EQ (2.37)
z  left ( {z f prime (z)} over {f (z)} right ) sup pprime ~>=~
{f sub 1 (z) } over {f (z)} ~cdot~
z left ( {z f sub 1 prime (z)} over {f sub 1 (z)} right ) sup pprime
.EN
.DE
for any $z member roR sup +$.
To see this, note that by the preceding
paragraph, the quantity on the left side
of (2.37) is the variance of the random
variable $X$ such that
.DS 3
.EQ
roman Pr ( X = k ) ~=~ {f sub k z sup k} over
{f (z)} ~.
.EN
.DE
But $X$ is a mixture of the random variables
$X sub 1$ and $X sub 2$, where
.DS 3
.EQ
roman Pr ( X sub i = k ) ~=~
{f sub i,k z sup k} over {f sub i (k)} ~,
.EN
.DE
with weights $f sub i (z) / f (z)$.
(A mixture $lambda Y sub 1 ~+~ ( 1 - lambda ) Y sub 2$
of random variables $Y sub 1$ and $Y sub 2$
with weights $lambda$ and $ 1 - lambda$ corresponds
to choosing $Y sub 1$ with probability $lambda$ and
$Y sub 2$ with probability $1 - lambda$.)
Thus to prove (2.37), it will suffice
to show that if $Y sub 1$ and $Y sub 2$ are any
real-valued random variables, and $lambda member [0,1]$,
then
.DS 3
.EQ (2.38)
roman Var ( lambda Y sub 1 ~+~ ( 1 - lambda ) Y sub 2 ) ~>=~
lambda ~ roman Var ( Y sub 1 ) ~+~
(1 - lambda ) ~ roman Var ( Y sub 2 ) ~.
.EN
.DE
If $F sub i$ denotes the distribution
function of $X sub i$, then (2.38) is
equivalent to
.DS 3
.EQ
lambda int x sup 2~ d F sub 1 ~+~
( 1 - lambda ) int x sup 2~ d F sub 2 ~-~
( lambda int x~ d F sub 1 ~+~ ( 1 - lambda ) int
x~ d F sub 2 ) sup 2
.EN
.sp
.EQ
>=~ lambda int x sup 2~ d F sub 1 ~-~
lambda ( int x~ d F sub 1 ) sup 2 ~+~
( 1 - lambda ) int x sup 2~ d F sub 2 ~-~
( 1 - lambda ) ( int x~ d F sub 2 ) sup 2 ~,
.EN
.DE
which is easily seen to hold.
This completes the proof of (2.37).
.P
We now apply (2.37) is with
.DS 3
.EQ
f sub 1 (z) ~=~
p sub d (z) y sub h (z) sup d , ~~~
f sub 2 (z) ~=~ y sub h+1 (z) ~-~
f sub 1 (z) ~=~ P ( z , y sub h (z)) ~-~
p sub d (z) y sub h (z) sup d ~.
.EN
.DE
We discover
.DS 3
.EQ
z left ( {z y sub h+1 sup pprime (z)} over
{y sub h+1 (z)} right ) sup pprime ~ mark >=~
{p sub d (z) y sub h (z) sup d} over
{y sub h+1 (z)} ~cdot~ z ~cdot~
left ( {z p sub d sup pprime (z)} over
{p sub d (z)} ~+~ d ~
{z y sub h sup pprime (z)} over
{y sub h (z)} right ) sup pprime
.EN
.sp
.EQ
lineup >=~ d~
{p sub d (z) y sub h (z) sup d} over
{y sub h+1 (z)} ~cdot~ z left (
{z y sub h sup pprime (z) } over
{y sub n (z) } right ) sup pprime ~.
.EN
.DE
If we iterate this inequality, we obtain
.DS 3
.EQ (2.39)
z left ( {z y sub h+1 sup pprime (z)} over
{y sub h+1 (z)} right ) sup pprime ~>=~ d sup h-2 
z left ( {z y sub 2 sup pprime (z)} over
{y sub 2 (z)} right ) sup pprime ~cdot ~
prod from j=2 to h ~
{p sub d (z) y sub j (z) sup d } over
{y sub j+1 (z) } ~.
.EN
.DE
Now Lemma 2.3 implies that the product
.DS 3
.EQ
prod from j=2 to inf ~ {p sub d (z) y sub j (z) sup d} over
{y sub j+1 (z)}
.EN
.DE
converges to a number $b ~=~ b (z) ~>~ 0$,
and since each factor is $<=~ 1$, we deduce
from (2.39) that
.DS 3
.EQ (2.40)
d sup -h z left ( {z y sub h sup pprime (z)} over
{y sub h (z)} right ) sup pprime ~>=~ d sup -1 b
~ z left ( {z y sub 2 sup pprime (z) } over
{y sub 2 (z) } right ) sup pprime ~,
.EN
.DE
and the last factor on the right side in
(2.40) is $>~ 0$ by Condition\ (B).
Since $z ( z beta prime (z) ) prime $ is
the limit of the left side of (2.40) as
$h ~->~ inf$, we obtain the claim (2.32)
of the lemma.
.P
To prove (2.33), we note that if
$f (z)$ is any polynomial with nonnegative
coefficients, then
.DS 3
.EQ
z f prime (z) ~<=~ roman deg ( f (z)) ~cdot~
f (z) ~, ~~~ z member roR sup + ~,
.EN
.DE
and so
.DS 3
.EQ (2.41)
z beta prime (z) ~<=~ lim from {h -> inf} ~
d sup -h ~ roman deg ~ y sub h (z) ~=~mu~.
.EN
.DE
To complete the proof of (2.33), note that
for $h ~>=~ h sub 0$,
.DS 3
.EQ
roman deg ~ y sub h+1 (z) ~=~ d ~ roman deg ~
y sub h (z) ~+~ roman deg ~ p sub d (z) ~,
.EN
.DE
and so
.DS 3
.EQ (2.42)
roman deg ~ y sub {h sub 0 + k} (z) ~=~
d sup k ~ roman deg ~ y sub {h sub 0} (z) ~+~
{d sup k -1} over d-1 ~ roman deg ~ p sub d (z) ~.
.EN
.DE
Next, note that for $z member roR sup +$,
.DS 3
.EQ
y sub h+1 prime (z) ~>=~ d p sub d (z) y sub h
(z) sup d-1 y sub h sup pprime (z) ~,
.EN
.DE
and so
.DS 3
.EQ
{y sub h+1 sup pprime (z)} over {y sub h+1 (z)} ~>=~
d ~ {y sub h sup pprime (z)} over
{y sub h (z) } ~ ( 1 ~-~ gamma e sup {- xi d sup h} )
.EN
.DE
for some $gamma$, $xi ~>~ 0$,
where this holds uniformly for all
$h ~>=~ 1$ and all $z member ( rho + 1 , inf )$
by Lemma\ 2.3 (applied with any
$delta ~<~ 1$ such that
$R ( delta ) ~!=~ phi$) and the fact
that each of the $y sub h (z)$ is
increasing on $roR sup +$.
Therefore for any $epsilon ~>~ 0$,
if we choose $h sub 1$ such that
.DS 3
.EQ
prod from {h=h sub 1} to inf~
( 1 - gamma e sup {- xi d sup h } ) ~>~
1 ~-~ epsilon / 2 ~,
.EN
.DE
then for any $z member ( rho + 1 , inf )$
and any $h ~>=~ h sub 1 $ we will
have
.DS 3
.EQ (2.43)
z beta prime (z) ~>=~ d sup -h ~
{z y sub h sup pprime (z)} over
{y sub h (z)} ~
( 1 - epsilon / 2 ) ~.
.EN
.DE
If we now choose $h sub 2 ~>=~ max
~ ( h sub 0 , h sub 1 ) ~,$
and $z$ so large that
.DS 3
.EQ
{z y sub {h sub 2} sup pprime (z)} over
{y sub {n sub 2} (z)} ~>=~
( 1 - epsilon /10 ) ~ roman deg ~
y sub {h sub 2} (z) ~,
.EN
.DE
then by (2.43) we will have
.DS 3
.EQ
z beta prime (z) ~>=~ ( 1 - epsilon )
d sup {- h sub 2} ~ roman deg~
y sub {h sub 2} (z) ~.
.EN
.DE
Since by (2.42)
.DS 3
.EQ
d sup {- h sub 2} ~ roman deg ~
y sub {h sub 2} (z) ~=~
lim from {h -> inf} ~
d sup -h ~ roman deg ~ y sub h (z) ~=~mu~,
.EN
.DE
this together with (2.41) proves (2.33).
.P
To complete the proof of the lemma, we need
to prove (2.34) when $P ( z , y )$ is
not a monomial.
Define
.DS 3
.EQ (2.44)
t sub h (z) ~ mark =~ d sup -h ~
{y sub h sup pprime (z)} over
{y sub h (z) } ~,
.EN
.sp
.EQ (2.45)
a sub h (z) ~ lineup =~
{sum from k ~ p sub k sup pprime (z)
y sub h (z) sup k} over
{sum from k ~ p sub k (z) y sub h (z) sup k} ~,
.EN
.sp
.EQ (2.46)
b sub h (z) ~ lineup =~
{sum from k ~ k over d p sub k (z)
y sub h (z) sup k } over
{sum from k ~ p sub k (z) y sub h (z) sup k } ~.
.EN
.DE
Then the recurrence (1.2) gives
.DS 3
.EQ (2.47)
t sub h+1 (z) ~=~ d sup {- h - 1}
a sub h (z) ~+~ b sub h (z) t sub h (z) ~.
.EN
.DE
If $E ~=~ max "{" roman deg ~ p sub k (z) "}"$,
then comparison of terms in the numerators
and denominators of (2.45) and (2.46)
shows that for any
$z member roR sup +$,
.DS 3
.EQ
0 ~<=~ a sub h (z) ~<=~ E z sup -1 ~,
.EN
.sp
.EQ
0 ~<=~ b sub h (z) ~<=~ 1 ~.
.EN
.DE
Hence
.DS 3
.EQ (2.48)
t sub h+1 (z) ~<=~ t sub h (z) ~+~ O
( d sup -h z sup -1 ) ~,
.EN
.DE
and therefore
.DS 3
.EQ (2.49)
t sub h+m (z) ~<=~ t sub h (z) ~+~ C d sup -h z sup -1 
.EN
.DE
for all $m member Z sup +$ and some $C ~>~ 0$.
.P
Let us first suppose that $rho~!=~0$.
We show that in this case $y sub h ( rho )$
is bounded as $h ~->~ inf$.
To see this, note that for every
$r member roR sup +$ there is a
$Y (r ) ~>~ 0$ such that
$P (z , y ) ~>~ 2 y$ for
$z ~>=~ r $, $y ~>=~ Y (r)$.
Now if $y sub h ( rho )$ is unbounded
as $h ~->~ inf$, then by continuity
we must have $y sub k ( rho prime ) ~>~ Y ( rho / 2 )$
some large $k$ and
for some $rho prime member ( rho / 2 , rho )$,
and
then $y sub h ( rho prime )$ is also
unbounded as $h ~->~ inf$ by the
argument above, which contradicts
the definition of $rho$.
.P
Since $y sub h ( rho )$ is bounded
and $P (x,y)$ is not a monomial,
we see from (2.46) that there is some
$B ~<~ 1$ such that
.DS 3
.EQ
b sub n ( rho ) ~<=~ B ~, ~~~~ h ~>=~ 0 ~.
.EN
.DE
Hence
.DS 3
.EQ (2.50)
t sub h+1 ( rho ) ~<=~ B t sub h ( rho ) ~+~ O (d sup -h ) ~.
.EN
.DE
Since the $ t sub h ( rho )$ are
bounded as $h ~->~ inf$,
as is shown by (2.49),
we find by iterating (2.50)
that for some $C sub 1 ~>~ 0$
.DS 3
.EQ (2.51)
t sub 2h ( rho ) ~<=~ C sub 1 ( B sup h ~+~
d sup -h ) , ~~~
t sub 2h+1 ~<=~ C sub 1 ( B sup h ~+~
d sup -h ) ~.
.EN
.DE
Hence $t sub h ( rho ) ~->~ 0$ as
$h ~->~ inf$.
Given $epsilon ~>~ 0$, let
us choose $h sub 0$ so that
.DS 3
.EQ (2.52)
C d sup {- h sub 0} ~+~
C sub 1 ( B sup {h sub 0} ~+~ d sup {- h sub 0} ) ~<~
epsilon / 4 ~.
.EN
.DE
Then there is a $delta ~>~ 0$ such that
.DS 3
.EQ
t sub {2 h sub 0 } (z) ~<=~ epsilon / 2
.EN
.DE
for $rho ~<=~ z ~<=~ rho ~+~ delta $.
But then (2.49) and (2.52) imply that
.DS 3
.EQ
t sub h (z) ~<=~ epsilon
.EN
.DE
for all $h ~>=~ 2 h sub 0$ and
$z member [ rho , rho + delta ] $, which
implies that $beta prime (z) ~<=~ epsilon$ for
$z$ in that interval.
Since this holds for every $epsilon ~>~ 0$,
we must have $beta prime (z) ~->~ 0$ as
$z ~->~ rho$.
.P
To complete the proof of the lemma, we need
to prove (2.34) when $rho ~=~ 0$.
We first observe that it will suffice
to show that
.DS 3
.EQ (2.53)
lim from {h -> inf} ~
lim from {z -> 0 sup +} ~
z~ t sub h (z) ~=~ 0 ~.
.EN
.DE
To see this, note that if (2.53) holds,
then for any $epsilon ~>~ 0$ we can find
$h sub 0$ and $delta ~>~ 0$ such that
for $z member ( 0 , delta ) $,
.DS 3
.EQ
z~ t sub {h sub 0} (z) ~<=~ epsilon / 4 , ~~~
C d sup {- h sub 0} ~<=~ epsilon / 4 ~.
.EN
.DE
But then (2.49) shows that
.DS 3
.EQ
z~ t sub {h sub 0 + m} (z) ~<=~ epsilon ~, ~~~
m member Z sup + ~, ~~~ z member ( 0 , delta ) ~,
.EN
.DE
which proves the claim.
.P
Suppose now that $rho ~=~ 0$ and that
$y sub h ( 0 ) ~=~ 0$ for all large $h$.
If we write
.DS 3
.EQ
y sub h (z) ~=~ z sup {v sub n} y sub h sup sstar (z) ~,
.EN
.DE
where $y sub h sup sstar (z)$ is a polynomial
with $y sub h sup sstar (0 ) ~!=~ 0$,
then
.DS 3
.EQ
lim from {z -> 0 sup +} ~
{z y sub n sup pprime (z) } over
{y sub h (z) } ~=~ v sub h ~.
.EN
.DE
But $P (x,y)$ is not a monomial,
so $v sub n+1 ~<=~ ( d -1 ) v sub h $,
and therefore
.DS 3
.EQ
lim from {z -> 0 sup +} ~
z~ t sub n (z) ~<=~ ( 1 - d sup -1 ) sup h ~,
.EN
.DE
which proves (2.53) in this case.
On the other hand, if
$y sub h (0) ~!=~ 0$, then
.DS 3
.EQ
lim from {z -> 0} ~
{z y sub h sup pprime (z)} over
{y sub h (z)} ~=~ 0 ~,
.EN
.DE
and (2.53) again holds.
This finally concludes the proof
of the lemma.
.ST
.H 1 "Proofs of the Theorems"
We now use the results of Section\ 2 to
prove Theorem\ 1.
Suppose that all the hypotheses
of that theorem are satisfied.
We use the Cauchy integral representation
.DS 3
.EQ (3.1)
y sub h,n ~=~ 1 over {2 pi i} ~
int from GAMMA ~ y sub h (z)
z sup {-n-1} d z ~,
.EN
.DE
which is valid for any simple
closed curve with the origin
in its interior.
.P
Let
.DS 3
.EQ (3.2)
lambda ~=~ n over {d sup h} ~,
.EN
.DE
so that $lambda sub 1 ~<=~ lambda ~<=~ lambda sub 2$.
We choose for $GAMMA$ the circle centered
at the origin of radius $r$, where
.DS 3
.EQ (3.3)
r beta prime ( r ) ~=~ lambda ~.
.EN
.DE
Since $z beta prime (z)$ is
strictly increasing from 0 to $mu$
between $z ~=~ rho$ and $z ~=~ inf$
by Lemma\ 2.6, Eq.\ (3.3) defines $r$
uniquely and shows that for
$lambda member [ lambda sub 1 , lambda sub 2 ]$,
$r member [ r sub 1 , r sub 2 ]$,
where $rho ~<~ r sub 1 ~<~ r sub 2 ~<~ inf$.
The choice of the above contour is inspired
by the fact that $r$ satisfying (3.3)
is an approximate saddle point of the
integrand in (3.1).
.P
By Lemma 2.5, we find that
there is a constant $theta sub 0 ~>~ 0$ such that
$beta (z)$ is analytic in the region
.DS 3
.EQ
r sub 1 ~<=~ | z | ~<=~ r sub 2 ~, ~~
-~ theta sub 0 ~<=~ roman Arg (z) ~<=~ theta sub 0 ~.
.EN
.DE
In that region we have the expansion
.DS 3
.EQ (3.4)
Re ~beta ( r e sup {i theta} ) ~=~
beta (r) ~-~ 1 over 2 ~ theta sup 2
( r sup 2 beta prime prime ( r ) ~+~
r beta prime (r )) ~+~
O ( theta sup 4 ) ~,
.EN
.DE
and, by taking $theta sub 0$ small enough,
we can ensure that
.DS 3
.EQ (3.5)
Re ~beta ( r e sup {i theta} ) ~<=~
beta (r) ~-~ 1 over 4 ~ theta sup 2 ( r sup 2
beta prime prime (r) ~+~ r beta prime
(r)) ~.
.EN
.DE
.P
If $GAMMA sub 1$ denotes the section
of the circle $z ~=~ r e sup {i theta}$
with $theta sub 0 ~<=~ theta ~<=~ 2 pi ~-~ theta sub 0$,
then by lemmas\ 2.4 and 2.5,
.DS 3
.EQ
1 over {2 pi i} ~ int from {GAMMA sub 1} ~
y sub h (z) z sup {-n-1} dz ~=~ O
( r sup -n ~ exp ( d sup h ( beta (r) ~-~
w ))) ~,
.EN
.DE
where $w ~>~ 0$ depends only on
$r sub 1$, $r sub 2$, and $theta sub 0$.
If $GAMMA sub 2$ denotes the section
of this same circle with
$-~ theta sub 0 ~<=~ theta ~<=~ theta sub 0$,
then Lemma\ 2.5 implies that
.DS 3
.EQ
1 over {2 pi i} ~ int from {GAMMA sub 2} ~
y sub h (z) z sup -n-1 d z ~ mark =~ 1 over
{2 pi i } ~ int from { GAMMA sub 2} ~
p sub d (z) sup {- 1/(d-1)} ~exp
(d sup h beta (z) ) z sup {-n-1} d z
.EN
.sp
.EQ (3.6)
lineup +~ O ( r sup -n ~ exp
( d sup n ( beta (r) - w prime ))) ~,
.EN
.DE
where $w prime ~>~ 0$ again depends
only on $r sub 1$, $r sub 2$, and $theta sub 0$.
To estimate the integral on the right
side of (3.6), we write
.DS 3
.EQ
GAMMA sub 2 ~=~ GAMMA sub 3 ~ \(cu ~ GAMMA sub 4 ~,
.EN
.DE
where
.DS 3
.EQ
GAMMA sub 3 ~=~ "{" r e sup {i theta} ~: ~
- theta sub 1 ~<=~ theta ~<=~ theta sub 1 ~, ~~
theta sub 1 ~=~ hd sup {- h/2} "}" ~.
.EN
.DE
On $GAMMA sub 4 ~=~ GAMMA sub 2 \e GAMMA sub 3$,
(3.5) yields
.DS 3
.EQ
Re ~ beta ( r e sup {i theta} ) ~<=~
beta (r) ~-~ w prime prime h sup 2 d sup -h
.EN
.DE
for some $w prime prime ~>~ 0$ which
depends only on $r sub 1$ and $r sub 2$, and so
.DS 3
.EQ
1 over {2 pi i} ~
int from {GAMMA sub 4} ~ p sub d (z) sup
{-1/(d-1)} exp ( d sup h beta (z) )
z sup -n-1 dz ~=~ O
( r sup -n ~ exp ( d sup h beta (r) ~-~
w prime prime h sup 2 ))~.
.EN
.DE
Finally, if
.DS 3
.EQ
J ~=~ 1 over {2 pi i } ~ int from {GAMMA sub 3}
~ p sub d (t) sup {-1 / ( d-1)} exp
(d sup h beta (z)) z sup -n-1 dz ~,
.EN
.DE
then
.DS 3
.EQ
J ~=~ 1 over {2 pi} ~ int
from {- theta sub 1} to {theta sub 1} ~
p sub d ( r e sup {i theta} ) sup {- 1 / ( d - 1)}
exp ( d sup h beta ( r e sup {i theta} )
~-~n ~ log ~ r ~-~ n i theta ) d theta ~.
.EN
.DE
But (3.2), (3.4), and
.DS 3
.EQ
p sub d ( r e sup {i theta } ) sup
{- 1 / ( d - 1 )} ~=~
p sub d (r) sup {-1/(d-1)}
( 1 + O ( | theta | ) )
.EN
.DE
imply that
.DS 3
.EQ
J ~ mark =~ (2 pi ) sup -1
A(r,n)~
int from {- theta sub 1 } to {theta sub 1} ~
exp ( - ~ 1 over 2 ~ d sup h ( r sup 2
beta prime prime (r) ~+~ r beta prime
(r) ) theta sup 2 ) ~cdot~
( 1 + O ( | theta | ) ~+~ O ( d sup h | theta | sup 3 )) d | theta |
.EN
.sp
.EQ
lineup =~
A(r,n)
d sup {-h/2} ( 2 pi ( r sup 2 beta prime prime
(r) ~+~ r beta prime (r) ) sup -1/2 ~cdot~
( 1 + O ( d sup -h/2 )) ~,
.EN
.DE
where
.DS 2
.EQ
A(r,n)~=~
p sub d (r) sup -1/(d-1) exp (d sup h beta (r)-n~log~r)~,
.EN
.DE
which together with the previous
estimates proves Theorem\ 1.
.P
From Theorem\ 1, we see that the
largest values of $y sub h,n$ when
$n$ varies correspond to values
of $n$ (defined by (3.3)) which
maximize
.DS 3
.EQ
g (r) ~=~ beta (r) ~-~ r beta prime (r) ~
log ~ r ~.
.EN
.DE
Now
.DS 3
.EQ
g prime (r) ~=~ -~ ( beta prime (r) ~+~
r beta prime prime (r) ) ~ log~ r ~,
.EN
.DE
and since $beta prime (r) ~+~ r beta
prime prime (r) ~>~ 0$ for
$r ~>~ rho$ by Lemma\ 2.6,
$g prime (r)$ will have a unique
maximum at $r ~=~ 1$ if
$rho ~<~ 1$, and will be $<~ 0$ in
$( rho , inf )$ if $rho ~>=~ 1$.
To complete the proof of Theorem\ 2,
we need to consider $rho ~<~ 1$ and study
the distribution of $y sub h,n$ for $r$
near the peak.
Define
.DS 3
.EQ
n sub 0 ~=~ n sub 0 (h) ~=~
beta prime (1) d sup h ~,
.EN
.DE
and set
.DS 3
.EQ
x ~=~ ( n - n sub 0 ) d sup -h/2 ~.
.EN
.DE
We will consider
.DS 3
.EQ
| x | ~<=~ d sup {h/6} ~.
.EN
.DE
If $r$ is defined by
.DS 3
.EQ
r beta prime (r) ~=~ n d sup -h ~,
.EN
.DE
then
.DS 3
.EQ
(n - n sub 0 ) d sup -h ~ mark =~
r beta prime (r ) ~-~ beta prime (1)
.EN
.sp
.EQ
lineup =~ ( r - 1 ) sigma sup 2 ~+~ O
( ( r - 1 ) sup 2 ) ~,
.EN
.DE
where
.DS 3
.EQ
sigma sup 2 ~=~ beta prime (1) ~+~
beta prime prime (1) ~.
.EN
.DE
Hence we have
.DS 3
.EQ
r ~-~ 1 ~=~ x d sup {-h/2} sigma sup 2 ~+~
O ( x sup 2 d sup -h ) ~.
.EN
.DE
Expanding the quantities that occur
in the statement of Theorem\ 1 in a
similar way, we obtain Theorem\ 2.
.H 1 "Applications and Extensions"
The problem that originally led to our
investigation was that of estimating $B sub h,n$,
the number of binary trees of height
$<=~ h$ and having $n$ internal nodes.
The recurrence for the generating
polynomials is given in the first paragraph
of this paper.
It is easy to see that $rho~=~0$ and
$mu~=~1$.
Theorems\ 1 and 2 imply that for large
but fixed $h$,
$B sub h,n$ is maximized for
.DS 3
.EQ (4.1)
n ~ wig ~ 2 sup h ~ 0.628968 ~ . . . ,
.EN
.DE
and that its maximum value is
asymptotic to
.DS 3
.EQ (4.2)
2 sup {- h/2} ~cdot~ exp
( 2 sup h ~cdot ~ 0.407354 . . . ) ~cdot~
0.685517 "..." ~.
.EN
.DE
For $h ~=~ 9$,
$B sub 9,n$ is maximized for
$n~=~ 322$, as predicted by (4.1),
and the value of $B sub {9,322}$ differs
from that predicted by (4.2) by less than 0.05%,
which demonstrates how accurate the asymptotic
approximations of our theorems are.
Fig. 1 presents a graph of the function
$beta ( r )$, defined as in Theorem 1.
Fig. 2 shows a graph of the function
.DS 2
.EQ
f ( lambda ) ~=~ beta ( r ) - r beta prime
(r) ~ log ~r~,
.EN
.DE
where $r$ is determined by
$0~<~r~<~1$, and $r$ is determined by
.DS 2
.EQ
r beta prime ( r )~=~lambda ~.
.EN
.DE
This function dominates the behavior
of $B sub {h,~n}$, so that if
$h~->~ inf$ and
.DS 2
.EQ
n~wig~ lambda 2 sup h ~~roman as~~
h ~->~ inf~,
.EN
.DE
then
.DS 2
.EQ
lim from {h -> inf}~
2 sup -h ~ log ~ B sub {h,~n} ~=~f ( lambda )~.
.EN
.DE
.P
There are many enumerative problems which
involve nonlinear iterations of polynomial
generating functions, but which are not
covered by our theorems.
As an example, enumeration of AVL-trees
(also known as height-balanced binary trees
[1,9]) leads [11] to the polynomial sequence defined by
.DS 3
.EQ
y sub 0 (z) ~ mark =~ z , ~~~
y sub 1 (z) ~=~ z sup 2 ~,
.EN
.sp
.EQ
y sub h+1 (z) ~ lineup =~ y sub h (z)
( y sub h (z) ~+~ 2 ^ y sub h-1 (z)) ~~~ for~~~
h ~>=~ 1~.
.EN
.DE
Since $y sub h+1 (z)$ depends on
$y sub h-1 (z)$ as well as on
$y sub h (z)$, our results do not
apply directly.
However, it should be possible to use
the methods of this paper to prove
results analogous to theorems\ 1 and 2
for these polynomials, as well as for many
other sequences satisfying similar
recurrences.
.P
It is also possible to use the methods of this paper to study
recurrences such as (1.2) where
the $y sub h (z)$ are entire
functions with nonnegative coefficients
and where $P(z,y)$ might also not be a polynomial.
However, in many cases it is simpler
to use the results of [6,7,14].
.P
Finally, we mention that it should
be possible to use our methods to study multivariate
polynomials satisfying nonlinear
recurrences.
Such polynomials occur, for example,
in studies of 2,3-trees [15], where one
is interested in the coefficients
of the polynomials $A sub h (x,y)$ defined
by $A sub 0 ( x,y) ~=~ 1$, and
.DS 3
.EQ
A sub h+1 (x,y) ~=~ xy A sub h (x,y) sup 2 ~+~
xy sup 2 A sub h ( x,y) sup 3 ~~~for~h~>=~0~.
.EN
.DE
By applying our theorems to the sequences $A sub n (x,1)$ and
$A sub h (1,y)$, we can obtain more precise
information than is provided by [15],
but it might be interesting to obtain
estimates for the full distribution
of the coefficients of the
$A sub h (x,y)$.
.PH ""
.bp
.ce
.B
FIGURE CAPTIONS
.R
.sp
.VL 8
.LI "Fig. 1."
The function $beta (r)$ for binary trees.
.LI "Fig. 2."
The function $f( lambda )$, which equals
the limit of $2 sup -h ~log~B sub {h,~n}$
as $h,~n~->~ inf$ with
$n~wig~lambda 2 sup h$.
.LE
.bp
.ce
.B
REFERENCES
.R
.sp 2
.RL
.LI
A. V. Aho, J. E. Hopcroft, and
J. D. Ullman, \f2The Design and Analysis
of Computer Algorithms\f1, Addison-Wesley, 1974.
.nr P 1
.PH "''R-\\\\nP''"
.LI
A. V. Aho and N. J. A. Sloane, Some doubly
exponential sequences, Fibonacci Quart. \f211\f1
(1973), 429-437.
.LI
H. Brolin, Invariant sets under iteration
of rational functions, Arkiv fo\*:r Mat. \f26\f1
(1965), 103-144.
.LI
P. Fatou, Memoire sur les e\*'quations
fonctionnelles, Bull. Soc. Math. France
\f247\f1 (1919), 161-271; \f248\f1 (1920),
33-94 and 208-314.
.LI
P. Flajolet and A. M. Odlyzko, The average
height of binary trees and other simple trees,
J.\ Computer Syst. Sci.,
\f225\f1 (1982), 171-213.
.LI
B. Harris and L. Schoenfeld, Asymptotic
expansions for the coefficients of analytic
functions, Illinois J.\ Math. \f212\f1 (1968),
264-277.
.LI
W. K. Hayman, A generalization of Stirling's
formula, J.\ reine angew. Math. \f2196\f1 (1956),
67-95.
.LI
G. Julia, Me\*'moire sur l'iteration des
fonctions rationnelles,
J.\ Math. Pures Appl. (8) \f21\f1 (1918),
47-245.
.LI
D. E. Knuth, \f2The Art of Computer
Programming.  Vol.\ 1: Fundamental Algorithms\f1,
Addison-Wesley, 1968.
.LI
A. M. Odlyzko, Periodic oscillations of
coefficients of power series that satisfy
functional equations, Adv. Math. \f244\f1 (1982),
180-205.
.LI
A. M. Odlyzko,
Enumeration of AVL-trees, manuscript in preparation.
.LI
A. M. Odlyzko and L. B. Richmond, On the
unimodality of high convolutions of discrete
distributions, to be published.
.LI
A. M. Odlyzko and L. B. Richmond,
manuscript in preparation.
.LI
A. M. Odlyzko and L. B. Richmond,
Asymptotic expansions for the
coefficients of analytic generating functions,
Aequationes Math., to appear.
.LI
E. M. Reingold, A note on 3-2 trees,
Fibonacci Quart. \f217\f1 (1979), 151-157.
.LE