\input amstex

\documentstyle{amsppt}

\define\squ{\qed}

\define\Cau{{1\over2\pi i}\oint}

\define\cau{{1\over2\pi i}\int}

\define\nn{{n!\over n^{n-1}}}

\define\doo{d\omega}

\define\CC{{\Cal C}}

\define\({\left(}

\define\){\right)}

\refstyle{A}

\widestnumber\key{F-G-T-88}



\hfuzz=20pt

% centre page in printer

\hoffset=1.5cm

\voffset=2.0cm



\topmatter



\title On Ramanujan's  Q--Function${}^\dag$\endtitle

\author Philippe Flajolet, Peter J. Grabner,

Peter~Kirschenhofer and Helmut Prodinger\endauthor

\leftheadtext{P. Flajolet et al.}

\thanks\flushpar \dag Research of the four authors was supported 

by the French Austrian scientific

cooperation pro\-gramme. % \newline

Work of P.~Flajolet was  supported in part

by the ESPRIT~III

Basic Research Action Programme of the

E.C. under contract ALCOM~II (\#7141).

Work of P.~Grabner  was supported 

by the Austrian Science Foundation, Project Nr. P8274-PHY

\endthanks

\address

\hbox{\vbox{\hbox to 8 truecm{P. Flajolet\hfill\break}

\hbox to 8 truecm{Algorithms Project \hfill\break}

\hbox to 8 truecm{INRIA, Rocquencourt\hfill\break}

\hbox to 8 truecm{78153 Le Chesnay (France)\hfill\break}} 

\vbox

{\hbox to 4.5 truecm{P.J. Grabner\hfill\break}

\hbox to 4.5 truecm{Technische Universit\"at Graz\hfill\break}

\hbox to 4.5 truecm{Steyrergasse 30\hfill\break}

\hbox to 4.5 truecm{A--8010 Graz (Austria)\hfill\break}}}

\medskip

\noindent

P. Kirschenhofer \& H. Prodinger\newline

Technische Universit\"at Wien\newline

Wiedner Hauptstra\ss{}e 8--10\newline

A--1040 Vienna (Austria)\endaddress

 

\abstract

This study provides a detailed analysis

of a function which Knuth 

discovered to play a central r{\^ole}

in the analysis of hashing

with linear probing.

The function, named after Knuth $Q(n)$,

is related to several of Ramanujan's investigations.

It surfaces in the analysis

of a variety of algorithms and discrete probability prob\-lems including

hashing, the birthday paradox, random mapping

statistics, the ``rho'' method for integer factorization,

union--find algorithms, optimum caching, and the study of memory conflicts.

 

A  process related to the 

complex asymptotic methods of singularity analysis and saddle

point integrals permits to precisely quantify the behaviour of the

$Q(n)$ function.

In this way, tight bounds are derived.

They answer a question of Knuth

({\sl The Art of Computer Programming}, Vol.~1, 1968, [Ex.~1.2.11.3.13]),

itself a rephrasing of earlier questions of Ramanujan in 1911--1913.

\endabstract

 

\dedicatory Dedicated to D.~E.~Knuth, on the occasion of the 30th

Anniversary of his first analysis of an algorithm in 1962.\enddedicatory

\endtopmatter

 

\document

% \centerline{--- September $27$, $1992$ ---}

\centerline{--- August $25$, $1993$ ---}



%\smallskip\centerline{({\it Manuscript submitted to Journal of Algorithms\/})}

\smallskip\centerline{\ }



\heading 1. Introduction\endheading

In the 1911 issue of  the Journal of the  Indian Mathematical Society, 

Ramanujan \cite{Ra11}

poses the following problem: {\sl Show that}

$${1\over2}e^n=1+{n\over1!}+{n^2\over2!}+\cdots+{n^n\over n!}\theta,

\qquad\hbox{\sl where $\theta$ lies between ${1\over2}$ and ${1\over3}$.}

\tag1.1$$

% where $\theta$  lies between ${1\over2}$ and ${1\over3}$''.}

A solution was then outlined in~\cite{Ra12}.

Later in his first letter to Hardy 

dated January 16, 1913 (see \cite{Ra62, p.~xxvi},

\cite{Be69, p.~181} and \cite{Ha78}), Ramanujan

makes a stronger assertion, namely that

$$\theta={1\over3}+{4\over135(n+k)}

\qquad\hbox{\sl where $k$ lies between ${8\over45}$ and ${2\over21}$.}

\tag1.2$$



It is immediately clear nowadays, on probabilistic grounds, that the left hand side

member in (1.1) is approximated by the sum of the first $n$ terms

on the right. In fact, the sum $1+\cdots+n^{n-1}/(n-1)!$

multiplied by 

$e^{-n}$ represents the probability that a 

random variable with a Poisson distribution of mean $n$

be less than $n$. But by the Gaussian approximation of

Poisson laws of large mean, this probability is

close to ${1\over2}$ and the argument supplemented by

elementary real estimates

readily shows that $\theta\equiv\theta(n)=O(1)$. 

Thus Ramanujan's assertions appear as asymptotic refinements

of a basic probabilistic  observation.



Berndt's scholarly edition of Ramanujan's Notebooks contains a

complete bibliography on the original problem

which is closely related to Entries 47 and 48 of Chapter~12 

(p.~179--184 of~\cite{Be89}) as well as to Entry 6 of Chapter~13

(p.~193--195 of~\cite{Be89}).

Berndt qualifies the

problem as {\sl ``an ultimately famous problem''}. 

In his partial answer~\cite{Ra12} and in the notebooks,

Ramanujan provides in essence

a way of constructing  an asymptotic expansion for $\theta\equiv\theta(n)$.

>From his analysis there results that $\theta(\infty)={1\over3}$ while

we have $\theta(0)={1\over2}$.

This, translated in terms of $k\equiv

k(n)$ says that 

$k(\infty)={2\over21}$ and $k(0)={8\over45}$, and supported by a few

initial value computations, must have naturally led Ramanujan

to his assertion~(1.2).





A solution to the weaker inequality (1.1) was given by G.~Szeg\H o in

1928~\cite{Sz28}, and almost simultaneously Watson~\cite{Wa29}

wrote a paper where he proved~(1.1) and adds regarding~(1.2): 

{\sl `` I shall also give reasons, which seem to me fairly

convincing, for\/ {\rm  believing} that $k$ lies between $8/45$ and

$2/21$.''}

Our purpose here is to finally provide a complete proof of

Ramanujan's assertion~(1.2).



 

In 1962, which is exactly 50 years after Ramanujan's

original note~\cite{Ra12}

and 75 years after Ramanujan's birth, Knuth conducted his first average--case

analysis of an algorithm, namely the analysis of 

{\sl hashing with linear probing} (see the footnote on page~529

of~\cite{Kn73}).

That analysis is given in full in  Volume 3 of

{\sl The Art of Computer Programming} \cite{Kn73} and, 

in Volume~1, Knuth uses it as an illustration

of asymptotic analysis techniques \cite{Kn68, p.113}.

A key r\^ole in the analysis is played by a function closely related

to $\theta(n)$, the $Q(n)$--function, and 

in Exercise~1.2.11.3.13,

Knuth asks for a final solution to Ramanujan's problem~(1.2).

 

The variant form used 

by Knuth introduces the two functions

$$\aligned Q(n)&=1+{n-1\over n}+{(n-1)(n-2)\over n^2}+\cdots\cr

R(n)&=1+{n\over n+1}+{n^2\over (n+1)(n+2)}+\cdots,\endaligned\tag 1.3$$

and one finds easily 

$$Q(n)+R(n)=n!e^n/n^n.$$

Thus $Q(n)$ and $R(n)$ are closely related, and the asymptotics of one of them determines the other.

The relation of Knuth's definition (1.3) to Ramanujan's problem

should also be clear, considering the equality

$${n^n\over n!}Q(n)={n^{n-1}\over(n-1)!}+{n^{n-2}\over(n-2)!}+\cdots+1

,\tag 1.4$$

which entails

$${n^n\over n!}Q(n)={1\over2}e^n-\theta{n^n\over n!}

\qquad\hbox{and}\qquad

\theta(n)={1\over2}(R(n)-Q(n)).$$

In this way, Ramanujan's problem can be rephrased as:

{\sl ``Show that

$$R(n)-Q(n)={2\over3}+{8\over135(n+k)}$$

where $k\equiv k(n)$ lies between $2\over21$ and $8\over45$''.}

Following Knuth,

this is the form that we shall take as our starting point,

setting $D(n)=R(n)-Q(n)$,

so that $D(n)=2\theta(n)$.

 

The approaches followed by Ramanujan himself and later authors

all make use of {\sl real} integral representations

derived from

$$Q(n)=\int_0^\infty e^{-x}\big(1+{x\over n}\big)^n\,dx,\tag 1.5$$

and proceed using the Laplace method for the asymptotic

evaluation of integrals~\cite{DB81}.

>From this representation, $Q(n)$ is up to normalization an incomplete

gamma function, a ${}_1F_1$--hypergeometric, and accordingly, it

admits an explicit continued fraction representation of the Gauss

type, as already noticed by Ramanujan (Entry 47 in Chapter~12 of

\cite{Be89}).

% The mathematical literature available on this problem 

% is scholarly reviewed in Berndt's edition of Ramanujan's

% notebooks~\cite{Be89} to which

% we refer for all references. (Observe also the related Entry~6 of Chapter~13.)



% We shall work instead with a {\sl complex\/} integral representation

% that derives from a generating function of the $Q(n)$.

 

As a historical fantasy, it may be of interest to observe that,

quite possibly, Ramanujan was led to his conjecture by considerations

related to the distribution of prime divisors in integers.

The Erd\H os-Kac Theorem asserts that,

for integers,  the `number-of-divisors'

function is asymptotically Gaussian distributed over large ranges. 

A form of this theorem

does appear in Ramanujan's notes, under a

Poisson formulation:

{\sl The number of integers less than $n$ with

numbers of prime divisors at most $k$ is asymptotically

$${x\over\log x}\bigg[1+{\log\log x\over 1!}+{(\log\log x)^2\over 2!}+\cdots+

{(\log\log x)^k\over k!}\bigg].$$}

Letting $k$ vary with $n$ in the ``interesting''

region $k\approx\log\log x$ naturally leads to questions like (1.1).





It should also be said at this stage that, apart from sentimental value,

the $Q(n)$ function appears in a number of problems in

discrete probability and the analysis of algorithms:

\roster

\item $1+Q(n)$ is the expected number of persons

it takes in order to find two having the same birth date

(when the year has $n$ days!). This is the

classical birthday problem which is of interest

in random allocations and general

hashing algorithms (see Section~4.1 of

\cite{Kn73} or \cite{FGT92}).

For instance, on earth,

it takes on average only 24.61658 persons to find two

with the same birth date.

\item The analysis of hashing with linear probing,

when the table is full, is expressed  simply in terms of $Q(n)$.

The cost of a successful search is 

about ${1\over2}\sqrt{\pi n\over2}$, as results from the asymptotic

analysis of $Q(n)$

(see~\cite{Kn73, p.~530} and \cite{VF90, p.~509--511}).



\item Random mapping statistics involve $Q(n)$ in several places,

in relation to their cycle structure. There is a vast

literature on this topic, see~\cite{Kn69, p.~8} for the basic results,

\cite{KP89} for related problems,

and~\cite{FO90a} for a recent survey of random mapping statistics.

The corresponding analyses are also  relevant

to the study of random number generators \cite{Kn69, Sec.~3.1}.

It is starting from there that Pollard conceived one of his

integer factorization algorithms, the well known ``rho method'',

which itself permitted in its time the discovery of

the factorization of the eighth Fermat number $F_8=2^{2^8}+1$.

\item Analysis of Union--Find algorithms under the random spanning 

tree model essentially depends on  $Q(n)$ \cite{KS78}.

\item Analysis of optimum caching \cite{Kn85}

and the study of 

memory conflicts or deadlocks \cite{KR75,CR92} involve the function $Q(n)$.

\endroster



The paper is organized as follows. 

Section~2 develops a complex

 integral representation based on a generating

function of the $Q(n)$ from which yet another proof of its asymptotic

expansion follows.

Our approach is in fact a hybrid of singularity analysis

and saddle point in the following sense:

It starts with an integral representation

based on an expansion essentially dictated by the singularity

analysis method (see Eq.~(2.4), and the proof  of Proposition~2); then

a suitable change of variable is introduced that  causes the

integration contour to pass through

a saddle point (see Eq.~(2.5),(3.1),(3.2) and the

developments at the beginning of Section~3).

In Section~3, effective error bounds for the intervening

integrals are developed.

The various lemmas and estimates are then woven together

in Section~4, where 

the proof of the main inequality is completed. Section~5 offers a few

hindsights. 





\heading 2. Generating Functions, Asymptotics, and an Integral

Representation\endheading





An important function in combinatorial analysis is the function $y(z)$ defined

implicitly by the equation

$$y(z)=ze^{y(z)},\tag2.1$$

with $y(z)=z+z^2+3z^3/2+\cdots$.

By the Lagrange inversion formula, we have\footnote {We let $[z^n]f(z)$ denote

the coefficient of $z^n$ in the Taylor expansion of $f(z)$.}

\proclaim{Proposition 1} The Taylor coefficients of $y(z)=ze^{y(z)}$ 

and its powers are given by

$$[z^n]y(z)={n^{n-1}\over n!} \qquad\hbox{and}\qquad

[z^n]y^k(z)=k {n^{n-k-1}\over (n-k)!}.\tag2.2$$

Furthermore, a generating function of $Q(n)$ is expressible in terms

of  $y(z)$:

% $$Q(n)={n!\over n^{n-1}}[z^n]\log{1\over 1-y(z)}\,.\tag2.3$$

$$\sum_{n=1}^\infty Q(n)n^{n-1}{z^n\over n!}=\log{1\over 1-y(z)}\,.\tag2.3$$

\endproclaim

The well known  expansions (2.2) go back to

Legendre and Eisenstein. 

The companion facts from combinatorics

are classical (see \cite{GJ83} or \cite{FO90a}):

$y(z)$ is the exponential generating function (EGF) of rooted labelled

trees and 

the function appearing in (2.3), $L(z)=\log(1-y(z))^{-1}$, is the EGF

of functional graphs (mappings) that are connected.

Thus, $Q(n)/n$ also represents the probability that a random mapping be

connected, a result already known to R\'enyi and Harris.



Equation (2.3) has already appeared

in the literature~\cite{KS78,FO90a,KP89,VF90}. It constitutes

the starting point of a transparent analysis

of the asymptotics of $Q(n)$.

In this way, we rederive through generating functions the

asymptotic expansion of $Q(n)$ known from the works of Ramanujan, Watson, and

Knuth~\cite{Be89,Wa29,Kn68}.



\proclaim{Theorem~1}{\rm [Ramanujan, Watson, Knuth]}

The quantities $Q(n),R(n)$ admit full asymptotic expansions in

descending powers of $\sqrt{n}$:

$$

Q(n)\sim \sqrt{\pi n\over2}-{1\over3}+{1\over12}\sqrt{\pi\over2n} - 

{4\over135n}+ \cdots

$$

$$

R(n)\sim \sqrt{\pi n\over2}+{1\over3}+{1\over12}\sqrt{\pi\over2n} + 

{4\over135n}+ \cdots\,.

$$

\endproclaim



\demo{Proof}

We sketch here the proof based on singularity analysis

(see~\cite{VF90,KP89,FO90a} for related developments). 

The implicitly defined function $y(z)$ has a singularity

of the square--root type at $z=1/e$, and

$$y(z)=1-\varepsilon+{1\over3}\varepsilon^2-{11\over72}\varepsilon^3

+{43\over540}\varepsilon^4-\cdots,\qquad\varepsilon=\sqrt{2-2ez},

$$

% $$y(z)\sim 1-2^{1/2}\sqrt{1-ez}+{2\over3}(1-ez)-\cdots

as $z\to e^{-1}$. This induces

a logarithmic singularity for  $L(z)$ at $z=1/e$, 

$$L(z)=\log{1\over\varepsilon}

+{1\over3}\varepsilon-{7\over72}\varepsilon^2+

{133\over3240}\varepsilon^3+\cdots

={1\over2}\log(1-ez)^{-1}+\cdots\,.$$

By singularity analysis \cite{FO90b},

the asymptotic equivalent of $L(z)$ transfers to the coefficients,

which gives $[z^n]L(z)\sim{1\over2} e^{n}n^{-1}$, and

$Q(n)\sim \sqrt{\pi n/2}$. 

The full expansion of $L(z)$ in powers of $(1-ez)^{1/2}$

also

translates into a full asymptotic expansion of

$Q(n)$ in powers of $n^{1/2}$. The developments for $R(n)$ are

entirely similar.

\qed\enddemo





In preparation for the more detailed treatment

involving bounds for $D(n)$, we

next need to make fully explicit the

various expansions and representations related to its generating function.



We have $Q(n)+R(n)=n!e^n/n^{n}$

so that a generating function of $D(n)$ is

$$\sum_{n=1}^\infty D(n)n^{n-1}{z^n\over n!}=\log{(1-y)^2\over

2(1-ez)}.$$

Appeal to

% Thus, we proceed instead from 

Cauchy's integral formula for coefficients

of analytic functions. When applied to (2.3), it gives

% $$Q(n)={n!\over n^{n-1}}\Cau_{\Cal C} \log{1\over 1-y(z)}\,d\omega

$$D(n)={n!\over n^{n-1}}\Cau_{\Cal C} \log{(1-y(z))^2\over 2(1-ez)}\,d\omega

\qquad\hbox{with}\qquad d\omega={dz\over z^{n+1}},\tag2.4$$

where $\Cal C$ is a sufficiently small countour surrounding the origin.



% We mentioned earlier

% % shortly after 

% (1.3) that $Q(n)+R(n)=n!e^n/n^{n}$. Thus 

% $$Q(n)+R(n)=n!/n^{n-1}[z^n]\log(1-ez)^{-1},$$ from which we derive:

% $$D(n)={n!\over n^{n-1}}\Cau_{\Cal C} \log{(1-y)^2\over 2(1-ez)}\,{dz\over z^{n+1}}.\tag2.6$$

% 

A key step is now to allow $y$ to be taken as

the independent variable (this is precisely inspired by

the analytic proof of the Lagrange inversion 

theorem) so that $z=ye^{-y}$.

The result is an alternative form of Eq.~(2.4).



\proclaim{Proposition 2} Quantity $D(n)=R(n)-Q(n)$ satisfies

$$

D(n)={n!\over n^{n-1}}\Cau_{\Cal C} \log{(1-y)^2\over 2(1-ye^{1-y})}\,

d\omega \quad\text{with}~~

\doo=\frac{dz}{z^{n+1}}=(1-y)e^{ny}\frac{dy}{y^{n+1}}, \tag 2.5

$$

where $\Cal C$ is a small contour around the origin in either

the $z$--plane (the first form of $d\omega$ is used with $y$

implicitly defined by $y=ze^y$) 

or in the $y$--plane 

(the second form is used with $y$ being the independent variable).

\endproclaim







In order to make use of~(2.5), we  first observe that, from (2.2), 

the coefficients of $(y-1)^k$ form an 

asymptotic scale:

$$\gathered\nn [z^n](y-1)=1,\quad \nn [z^n](y-1)^2=-{2\over n},\cr

\nn [z^n](y-1)^3=-{3\over n}+{6\over n^2},\quad

\nn [z^n](y-1)^4={20\over n^2}-{24\over n^3},\cr

\nn [z^n](y-1)^5={15\over n^2}-{130\over n^3}+{120\over n^4},\quad

\ldots\endgathered\tag2.6$$

with $n!n^{-n-1}[z^n](y-1)^k$ being $O(n^{-\lfloor k/2\rfloor})$ and comprising $\lceil k/2\rceil$ terms.



If we expand the integrand  of~(2.5) in powers of $(y-1)$ and use the 

{\sl first\/} form of $d\omega$,

$d\omega=dz/z^{n+1}$, then through (2.6) we

get an asymptotic expansion for $D(n)$:

$$D(n)\sim \sum_{k\ge 1}c_k\cdot[z^n](y-1)^k\tag2.7$$

where ($\delta =y-1$):

$$\aligned &\log{\delta ^2\over 2

(1-(1+\delta )e^{-\delta })}=\sum_{k\ge1} c_k \delta ^k\cr

& ={2\over3}\delta-{1\over36}\delta^2-{1\over810}\delta^3+

{1\over12960}\delta^4\cr

&\ \ +{1\over68040}\delta^5+{1\over12247200}\delta^6-{1\over6123600}\delta^7

-{13\over1175731200}\delta^8+\cdots.\endaligned\tag 2.8$$

By~(2.6), Eq.~(2.7) itself transforms into a standard expansion,

$$D(n)\sim\sum_{k\ge0} {d_k \over n^k},\tag2.9$$

whose first few terms are

$$D(n)\sim {2\over 3}+{8\over 135 n}-{16\over 2835 n^2}-{32\over 8505 n^3}+{1794\over 12629925 n^4}+\cdots .$$

Analytically, the 

complete process leading to~(2.9) is again justified by the

singularity analysis theorems.

It is quite parallel to the proof of Theorem~1 (only $y-1$ is used instead of

the asymptotically related $\varepsilon$) and refinements of it

are going to provide the required bounds.



 

\heading 3. Expansions with Effective Error Bounds

\endheading

 

The main device employed here follows the outline given in the equations 

(2.7)--(2.9). 

We use a {\sl terminating\/} form of (2.8) inside our main integral

representation,

$${n^{n-1}\over n!}D(n)=\Cau_{\Cal C}\bigg(\sum_{k=0}^K c_k (y-1)^k \bigg)\,\doo

+\Cau_{\Cal C} R_{K}(y-1)\,\doo,\tag3.1$$

where the $c_k$ are defined by (2.8) and

$$R_{K}(y-1)=\log{(1-y)^2\over 2(1-ye^{1-y})}-\sum_{k=1}^K c_k (y-1)^k

=\sum_{k\ge K+1}c_k(y-1)^k.\tag3.2$$

The integral with the finite sum in (3.1) is known {\sl exactly} from

Section~2 and Eq.~(2.6); our aim is 

to derive constructive bounds for the integral containing the remainder.



To estimate the remainder  integral, we make use the

{\sl second\/} form of $d\omega$, namely $d\omega=(1-y)e^{ny}dy/y^{n+1}$

together with a contour

{\sl in the $y$--plane} whose choice is dictated by a {\sl saddle

point heuristic}.

The quantity $e^{ny}y^{-n}$ has a saddle point at $y=1$ with axis

perpendicular to 

the real line;  accordingly, we take $\CC=\CC_1\cup\CC_2$ where

$$\CC_1=\big\{1+i\tau\ /\ -1\le \tau\le 1\big\}

\ \ \hbox{and}\ \ 

\CC_2=\big\{y\ /\ |y|=\sqrt2,\ \Re(y)\le1\big\}.\tag3.3$$

Our proof,

that will eventually fix $K=10$, consists of two simple phases.

\roster

\item"(a)" The integral of the remainder term along $\CC_2$ is small

since there $y^{-n}=O(2^{-n/2})$; 

in addition, it can be effectively bounded.

\item"(b)" Along $\CC_1$, quantity $R_{K}$ is small since it was

obtained by subtracting from 

a function the first $K$ terms of its locally convergent Taylor

expansion;

in addition, constructive bounds can be derived.

\endroster





\topinsert



\vskip 7.5cm

\special{psfile=rama1.ps hscale=42 vscale=42 hoffset=0}

\special{psfile=rama2.ps hscale=18 vscale=18 hoffset=230}

\vskip0.3cm

\noindent

{\bf Figure~1.} The transform by $f(z)$ of the square of

side $2\pi$ centered at the origin together with a blow up of the

picture near the origin (lower right).



\medskip\noindent\hrule\medskip

\endinsert





We thus proceed with this programme, starting with 

estimates of the $c_k$ coefficients,

continuing with the estimates along $\CC_2$ then $\CC_1$, which

we give for a general $K$. To take care of recurring factors

of the form $n!/n^n$, we appeal to a weak form of Stirling's formula

valid for all $n\ge1$,

$$n!<{\textstyle 11\over 10} n^n e^{-n}\sqrt{2\pi n}.\tag3.4$$



\proclaim{Lemma 1} For all $k\ge1$, we have

$$|c_k|<{10.96714833\over \pi^k}.\tag3.5$$

\endproclaim



\define\QQQ{{\Cal Q}}



\demo{Proof}

>From Eq.~(2.8) We estimate the coefficients of $\log f(z)$

where

$$f(z)=\frac{z^2}{2(1-(z+1)e^{-z})}$$

by means of  Cauchy's formula:

$$c_k=\Cau_\QQQ\log f(z)\frac{dz}{z^{k+1}},\tag3.6$$

where $\QQQ$ is any small enough simple contour encircling the origin.

We propose to take here as contour $\QQQ$ the boundary of the square

$|\Re z|\leq\pi$, $|\Im z|\leq\pi$.



First, elementary computations 

show that there are no zeros nor poles of $f(z)$ within $\QQQ$.

The graph of Figure~1 which represents the image of $\QQQ$ by $f(z)$

confirms this via the principle of the argument since $f(\QQQ)$ has

winding number~0 with respect to the origin.

Thus $\log f(z)$ is analytic in and on $\QQQ$ and the Cauchy

integral~\thetag{3.6} 

for $c_k$ can be evaluated by taking $\QQQ$ as the integration contour.





By considering the four sides of the square $|\Re z|\leq\pi$, $|\Im z|\leq\pi$

and using trivial estimates we obtain:

$$\frac{\pi^2}{2(1+(2\pi+1)e^\pi)}\leq\left|f(z)\right|\leq

\frac{\pi^2}{1-(\pi+1)e^{-\pi}}.$$

We next  have to consider the argument of $f(z)$. 

For this purpose we investigate

the argument of the denominator of $f(z)$. We restrict our investigation

to the part of the square with $\Im z>0$. By examining the behaviour of the sign

of the real and imaginary part of $g(z)=1-(z+1)e^{-z}$ on the three lines

$\Re z=\pi,0\leq\Im z\leq\pi$, $-\pi\leq\Re z\leq\pi,\Im z=\pi$ and

$\Re z=-\pi,0\leq\Im z\leq\pi$, we find that $g(z)$ does not enter the

third quadrant. Thus we have $-\frac\pi2<\arg g(z)<\pi$. On the other hand

we have $0\leq\arg z^2\leq2\pi$. Combining the two bounds yields

$$|\arg f(z)|\leq\frac52\pi.$$

 

Thus we obtain

$$\left|\log f(z)\right|\leq\(\log^2\frac{\pi^2}{2((2\pi+1)e^\pi+1)}+\frac{25}4\pi^2\)^{\frac12}=8.613578\ldots.$$

Bounding the integral~\thetag{3.6}  trivially, we arrive at

$$|c_k|\le {1\over2\pi}\left({8.613578\over \pi^{k+1}}\right)(8\pi),$$

which is equivalent to \thetag{3.5}.

\qed\enddemo







% The proof is split  into two parts: We first show that there are no zeros

% or poles of

% $$f(z)=\frac{z^2}{2(1-(z+1)e^{-z})}$$

% in the strip $|\Im z|\leq\pi$; then we show estimates for $f(z)$ on the

% boundary of the square $|\Re z|\leq\pi$, $|\Im z|\leq\pi$ and use these

% estimates and Cauchy's formula to prove \thetag{3.5}.

%  

% Trivially we have to consider only the denominator of $f(z)$. We set $z=u+iv$,

% split the equation $1-(z+1)e^{-z}=0$ into real and imaginary part and obtain

% the system of equations

% $$\align &1+u=e^u\cos v\cr&v=e^u\sin v.\endalign$$

% It is easy to see that this equations have no solution for $|v|\leq\pi$

% except $u=v=0$. This corresponds to $z=0$ which is not a  zero of $f(z)$.

% Thus $\log f(z)$ has no singularity in the strip $|\Im z|\leq\pi$.



Numerical computations 

suggest that the $c_k$ decrease roughly like $7^{-k}$, so

that the estimate of Lemma~1 is not too tight.

It is however amply sufficient for our purposes.

With it, we next bound the remainder integral along $\CC_2$.



\proclaim{Lemma 2}

We have

$$\left|\nn\cau_{\CC_2}R_{K}(y-1)\doo\right|\leq H(K)n^{\frac32}2^{-\frac n2},\tag3.7$$

where

$$H(K)=181.7306404 \(\frac{1+\sqrt2}\pi\)^K.$$

\endproclaim

\demo{Proof}

Estimate \thetag{3.2} by the triangle inequality applying the bounds

\thetag{3.5} 

of Lemma~1 for the coefficients $c_k$;

use Stirling's formula \thetag{3.4} to eliminate the

factorials. This gives the upper bound

$$\left({11\over10}\,{ne^{-n}\sqrt{2\pi n}\over 2\pi}\right)

\left(M{ {1+\sqrt{2}\over\pi}\over1-{1+\sqrt{2}\over\pi}}\right)

\left({1+\sqrt{2}\over\pi}\right)^k

\left( {

(1+\sqrt{2})e^n\over\sqrt{2}}2^{-n/2}\right)

\left(2\pi\sqrt{2}{3\over4}\right),

$$

with $M=10.96714833$ being the constant appearing in Lemma~1. All

reductions done, this provides the stated bound.

\qed\enddemo





It remains to evaluate the remainder integrals along $\CC_1$.



\proclaim{Lemma 3} For all $n\ge1$, we have the bound

$$\left|{n!\over n^{n-1}}\Cau_{\CC_1} R_{K}(y-1)\,\doo\right|

\le G(K) {1\over n^{K/2}}\tag3.8$$

where

$$G(K)={11\over 10}{2^{K+3}\over\sqrt{2\pi}}{\mu_{K}\Gamma\({K+3\over2}\)}

\qquad\hbox{\sl and}\qquad\mu_{K}=\max_{y\in

\CC_1}\left|{R_{K}(y-1)\over(y-1)^K}\right|\tag3.9$$

\endproclaim

\demo{Proof} Setting $y=1+i\tau$, and 

bounding the integral in (3.8), we 

find

$$\left|{n!\over n^{n-1}}\cau_{\CC_1} R_{K}(y-1)\,\doo\right|\le 

{11\over 10}\,{n\sqrt{2\pi n}\over 2\pi} \mu_{K}J(K),\tag3.10$$

with $\mu_{K}$ defined in (3.9) and

$$\eqalign{J(K)&=\int_{-1}^{+1}|\tau|^{K+2}\,{d\tau\over |1+i\tau|^{n+1}}\cr &<2\int_0^1 \tau^{K+2}\, {d\tau\over(1+\tau^2)^{n/2}}.\cr}\tag3.11$$

Since, in the given range, we have $1+u\ge e^{u/2}$, we find

$$J(K)<2\int_0^\infty \tau^{K+2}e^{-n\tau^2/4}\,d\tau$$

and a change of variable shows that the right hand side

coincides with a gamma function, namely

$$J(K)<2^{K+3}\Gamma\({K+3\over2}\)n^{-(K+3)/2}.\tag3.12$$

Using (3.12) inside (3.10) yields the statement

of the lemma.~\squ\enddemo



\heading 4. Ultimate inequalities and the main theorem \endheading





We are finally in a position to

combine the effective bounds provided by Lemmas 1, 2 and 3

and derive the main result of the paper.



\proclaim{Theorem 2}

With the quantity $\theta\equiv\theta(n)$ being defined by

$${1\over2}e^n=1+{n\over1!}+{n^2\over2!}+\cdots+{n^n\over

n!}\theta,$$

one has, for all integers $n\ge0$, 

$$\theta={1\over3}+{4\over135(n+k)},$$

where $k\equiv k(n)$ lies between $8\over45$ and $2\over 21$.

\endproclaim



\demo{Proof} The proof uses the decomposition \thetag{3.1} together with

the estimates derived in the last section. We fix the value

$K=10$. The remainder integral containing $R_K$ is estimated along

$\CC_2$ and $\CC_1$. Then we consider the main terms.



(i). The remainder integral along $\CC_2$

is estimated by Lemma~2.

For $K=10$, we get $H(10)=13.05227701$ so that we find

$$\aligned

\left|{n!\over n^{n-1}}\cau_{\CC_2} R_{10}(y-1)\,\doo\right|\ 

& < 13.06n^{3/2}2^{-n/2} \cr

& <\ 10^{-7} {1\over n^3} \qquad\hbox{for }n\geq n_0=116.

\endaligned

\tag4.1$$

(Numerical studies show that much better could be done, 

but the effect on $n_0$ is marginal.)

 

(ii).~The remainder integral along $\CC_1$

is estimated by Lemma~3.

This requires estimating the quantity $\mu_{K}$

appearing in the bound (3.8). 

The smallness of the $\mu_K$'s is naturally related to the exponential

decay of the coefficients $c_K$ since $\mu_K\approx c_K$.

% and numerical evidence shows that

% $c_K\approx 7^{-K}$. We use again Cauchy's 

% formula to prove a weaker exponential bound on the $c_K$'s:



>From Lemma~1, we find with $M=10.96714833$, 

$$\mu_{K}\le M\sum_{j>K}{1\over\pi^j}={M\over \pi-1}\({1\over\pi}\)^K,$$

and in particular, for $K=10$:

$$\mu_{10}<0.00005468 \qquad\hbox{so that}\qquad G(10)=56.59398.$$

(From numerical experiments, we expect a slightly better bound

to hold: $\mu_{10}<10^{-7}$---but once more the effect is marginal.)



(iii).~We finally consider the first 10 ($=K$) terms in the expansion

\thetag{3.1} which contribute a polynomial of degree 9 in $1\over n$

to $D(n)$.

Define

$$\aligned D_{10}(n) &  =  \nn\Cau_{\CC}\sum_{k=0}^{10}c_k(y-1)^k\doo \cr

& = \frac{2}{3}+{\frac {8}{135\,n}}-{\frac

{16}{2835\,n^{2}}}-{\frac{32}{8505\,n^

{3}}}+{\frac {17984}{12629925\,n^{4}}}+{\frac {13159709}{9699782400\,n

^{5}}} \cr

& \ \ -{\frac {977069}{1039262400\,n^{6}}}-{\frac {36669961}{

28291032000\,n^{7}}}+{\frac {117191}{56582064\,n^{8}}}-{\frac {479}{

561330\,n^{9}}} \, .

\endaligned $$

% $$D_{10}(n)=\nn\Cau_{\CC}\sum_{k=0}^{10}c_k(y-1)^k\doo

% $$

% $$=

% \frac{2}{3}+{\frac {8}{135\,n}}-{\frac {16}{2835\,n^{2}}}-{\frac{32}{8505\,n^

% {3}}}+{\frac {17984}{12629925\,n^{4}}}+{\frac {13159709}{9699782400\,n

% ^{5}}}

% $$

% $$-{\frac {977069}{1039262400\,n^{6}}}-{\frac {36669961}{

% 28291032000\,n^{7}}}+{\frac {117191}{56582064\,n^{8}}}-{\frac {479}{

% 561330\,n^{9}}} \, .

% $$

Equation \thetag{3.1} and the bounds found for $K=10$ yield

$$

D_{10}(n)-\Delta(n)\le D(n)\le D_{10}(n)+\Delta(n) \tag{4.2}$$

where

$$\Delta(n)= {10^{-7}\over n^3}+{57\over n^5},$$

under the sole condition that $n\ge n_0=116$.



The two basic inequalities

$$\aligned & D_{10}(n)-\Delta(n) \geq \frac23+\frac 8{135(n+\frac8{45})}

\qquad\text{for }n\geq n_1=24\cr

& D_{10}(n)+\Delta(n) \leq \frac23+\frac 8{135(n+\frac2{21})}

\qquad \text{for }n\geq n_2= 116,

\endaligned$$

are verified by normalizing the involved rational fractions and studying the

variations of the numerator polynomials that are of degrees~8 and~7

respectively. Thus, from~\thetag{4.2}, the main assertion of the theorem is 

established for

$$n\geq \max(n_0,n_1,n_2)=116.$$





% $$\aligned &D_{10}(n)\geq \frac23+\frac 8{135(n+\frac8{45})}+\frac{10^{-7}}{n^3}+\frac{G(10)}{n^5}\quad\text{for }n\geq 24\cr

% &D_{10}(n)\leq\frac23+\frac8{135(n+\frac2{21})}-\frac{10^{-7}}{n^3}-\frac{G(10)}{n^5}\quad\text{for }n\geq 106.\endaligned$$

% 



To finish the proof,

it suffices to calculate $k(n)$ for $n\leq 115$ by computer and to

verify the inequality in these cases (see Fig.~2 for a display).

\qed\enddemo





{\sl Proof and Computation.}

The symbolic manipulations needed by our proof 

were performed with the help of the computer algebra system {Maple}.

Computer algebra intervened at most  stages in the construction

of the proof: in performing various expansions like (2.6),(2.8),(2.9),

and in obtaining the various bounds of Sections 3 and 4.

As soon as enough terms have been gathered in

the asymptotic expansion of $Q(n)$, the truth of the conjecture 

in its weaker asymptotic form, for ``large enough'' $n$, is immediate.

The difficulty in obtaining a complete proof of Theorem~2 is then twofold:

(i).~the proof of asymptotic estimates should be suitably transformed 

in order to yield inequalities valid for large enough $n$;

(ii).~the range of excluded values of $n$ should be small enough that

the remaining cases, here $n<116$, be amenable to exhaustive verification.

The second of these conditions 

has necessitated a rather delicate tuning process

that could be done rather painlessly with the help of a few

hours of interaction

with our computer algebra system. A hand carved proof

along our lines, though perhaps conceivable, would have involved a rather

formidable calculational effort.







\topinsert



\vskip 8cm

\special{psfile=rama3.ps hscale=45 vscale=45 hoffset=36}



\vskip 0.3cm



\noindent

{\bf Figure~2.} A plot of the first 120 values of $k(n)$ confirms that

they all lie inside the interval $[{2\over21},{8\over45}]$.





\medskip\noindent\hrule\medskip

\endinsert



 

\heading 5. Some Conclusions \endheading

 

It may be of interest, at last, to reflect on the various alternatives

that offer themselves in order to estimate 

asymptotically sequences like $Q(n)$ or $D(n)$.

 

1. {\sl Laplace Method.} The Laplace method for integrals, based on 

the integral representation (1.5) was the starting point of earlier approaches.

As Szeg\"o and Watson show, it can be made ``constructive'' (instead of providing

only $O$-bounds) but its operation

becomes then somewhat intricate.

 

2. {\sl Singularity Analysis.} 

This is the method that gave us here the expansion of Theorem~1.

It is based on the fact that the implicitly defined function $y(z)$ 

has an algebraic singularity of the $\sqrt{\ }$--type, from which the 

singularity types of the generating functions associated with $Q(n)$ or

$D(n)$ follow.

The method can also accommodate

constructive bounds on a function's coefficients~\cite{FO90b}.

Consequently  it might be applicable to derive Theorem~2, 

although, in this case, bounding

$y(z)$ in the appropriate region would probably prove unwieldy.







3. {\sl Darboux's Method.} 

Darboux's method also leads to a full asymptotic expansion by a route

very similar to singularity analysis. However it does not have the

capacity to provide bounds since it is intrinsically based on a

non--constructive lemma on Fourier series.

 

4. {\sl Saddle Point.} This is in essence

the route that we took, after a suitable change of variable.

Its application in the case of implicitly defined functions

and Lagrange series is also to be

traced in Darboux's works, an interesting combinatorial application occurring

in \cite{MM78}. By this method, we were able

to reduce the problem

to the task of finding simple bounds for elementary functions

on circles and line segments. Interestingly enough,

when considering the conformal mapping defined by $y^{(-1)}(z)$,

it appears that  the induced contour in the $z$--plane closely

resembles the type of ``Hankel'' contour used in the $z$--plane under the

singularity analysis approach. This establishes a perhaps unexpected

relation between two seemingly unrelated methods---singularity

analysis and saddle point---at least in the context of implicitly

defined functions and Lagrange series.

 

 

% \newpage

 

\Refs

\ref\key Be89

\by B. Berndt

\book Ramanujan's Notebooks, Part II

\publ Springer\publaddr Berlin

\yr 1989

\endref



\ref\key CR92

\by K. Compton and C. Ravishankar

\paper Mean Deadlock Time in a Multiprocessing System

\yr 1992

\jour Preprint

\endref



\ref\key DB81

\by N. G. de Bruijn

\book Asymptotic Methods in Analysis

\publ Dover

\yr 1981

\endref





\ref\key FGT92

\by P. Flajolet, D. Gardy and L. Thimonier

\paper Birthday paradox, coupon collectors, caching algorithms,

and self--organizing search

\jour Discrete Applied Mathematics

\yr 1992

\vol 42

\pages In press

\endref



\ref\key FO90a

\by P. Flajolet and A.M. Odlyzko

\paper Random Mapping Statistics

\jour Lect. Notes in Comp. Sc.

\vol 434

\pages 329--354. 

In {\it Advances in Cryptology},

Proceedings of {Eurocrypt'89}, % Houtalen, Belgium, April 1989.

J-J. Quisquater and J. Vandewalle Editors.

\yr 1990

\endref





\ref\key FO90b

\by P. Flajolet and A.M. Odlyzko\paper Singularity Analysis of

Generating Functions\jour SIAM J. Disc. Math.\vol 3\pages 216--240\yr 1990\endref



\ref\key GJ83

\by I.P. Goulden and D.M. Jackson\book Combinatorial Enumeration

\publ J. Wiley\publaddr New York\yr 1983\endref



\ref\key Ha78

\by G. H. Hardy

\book Ramanujan: {T}welve Lectures on Subjects Suggested by his Life

and Work

\publ Chelsea Publishing Company \publaddr New York

\yr 1978

\endref



\ref\key He77\by P. Henrici\book Applied and Computational Complex Analysis

\publ J. Wiley\publaddr New York\yr 1977\endref



\ref\key Kn68\by D.E. Knuth\book The Art of Computer Programming\vol 1\publ

Addison Wesley\publaddr Reading\yr 1968\endref



\ref\key Kn69\by D.E. Knuth\book The Art of Computer Programming\vol 2\publ

Addison Wesley\publaddr Reading\yr 1969\endref



\ref\key Kn73\by D.E. Knuth\book The Art of Computer Programming\vol 3\publ

Addison Wesley\publaddr Reading\yr 1973\endref



\ref\key Kn85\by D.E. Knuth\paper An analysis of optimal caching

\yr 1985\jour J. of Algorithms \pages 181--199\endref



\ref\key KP89

\by D. E. Knuth and B. Pittel

\paper A recurrence related to trees

\yr 1989

\jour Proc. Amer. Math. Soc.

\vol 105

\pages 335--349

\endref



\ref\key KR75

\by D. E.  Knuth and G. S. Rao

\paper  Activity in an Interleaved Memory

\yr 1975

\jour IEEE Transactions on Computers

\vol C-24

\pages 943--944

\endref





\ref\key KS78

\by D. E. Knuth and A. Sch{\"o}nhage

\paper The expected linearity of a simple equivalence algorithm

\yr 1978

\vol 6

\jour Theoret. Comp. Science

\pages 281--315

\endref







\ref\key MM78\by A. Meir and J.W. Moon\paper 

On the altitude of nodes in random trees\yr 1978

\jour Canadian Journal of Mathematics\vol 30\pages 997--1015\endref



\ref\key Ra11

\by S. Ramanujan

\paper Question 294

\jour J. Indian Math. Soc.

\vol 3

\yr 1911

\pages 128

\endref



\ref\key Ra12

\by S. Ramanujan

\paper On question 294

\jour J. Indian Math. Soc.

\vol 4

\yr 1912

\pages 151--152

\endref



\ref\key Ra62

\by S. Ramanujan

\book Collected Papers

\publ Chelsea Publishing Company \publaddr New York

\yr 1962

\endref





\ref\key Sz28\by G. Szeg\H o\paper \"Uber einige von S. Ramanujan gestellte

Aufgaben\jour J. London Math. Soc.\pages 225--232\vol 3\yr 1928\endref



\ref\key VF90

\by J. S. Vitter and P. Flajolet

\paper Analysis of Algorithms and Data Structures

\jour

In Handbook of Theoretical Computer Science. Vol~A: Algorithms and

Complexity (J. van Leeuwen Ed.), Chapter~9

\yr 1990

\pages 431--524

\endref





\ref\key Wa29\by G.N. Watson\paper Theorems Stated by Ramanujan (V): Approximations

Connected with $e^x$\jour Proc. London Math. Soc. (2)\vol 29\pages 293--308

\yr 1929\endref



\endRefs

\enddocument

 





