%%%         Examples of Automatic Asymptotic Expansions
%%%
%%%                        B. Salvy
%%%                 (salvy@inria.inria.fr)
%%%
%%%                        based on 
%%%              INRIA TECHNICAL REPORT NO 114
%%%                     December 1989
\documentstyle[twoside]{article}
%%%%                 MACROS              %%%%%%%%%%%%%%
\newcounter{example}
\newcommand{\ex}{\addtocounter{example}{1}\smallskip\par
\noindent{\sc Example \theexample: \nopagebreak}}
\newcommand{\exs}{\addtocounter{example}{1}}
\def\LUO{\leavevmode
{\char'3\kern -.2em\lower 0.666ex\hbox{\char'7}\kern-.125 em
\raise0.2ex\hbox{\char'12}}}
\def\thesection {\Roman{section}}
\def\thesubsection {\thesection.\arabic{subsection}}
\newtheorem{definition}{Definition}
\marginparwidth 0pt
\oddsidemargin 0pt
\evensidemargin 0pt
\marginparsep 0pt
\topmargin 0pt
\textwidth 6.5in
\textheight 8.5 in
%%%%                DOCUMENT            %%%%%%%%%%%%%%%
\begin{document}
\title{\bf Introductory Guide to Gdev}
\author{{\sl Bruno Salvy}\\LIX, Ecole Polytechnique\\91128 Palaiseau
Cedex (France)\\and\\INRIA, Rocquencourt\\78150 Le Chesnay (France)}
\date{}
\maketitle
\begin{abstract}
We describe the current state of a Maple library, {\sl gdev}, designed
to perform asymptotic  expansions for  a  large class of  expressions.
Many  examples  are  provided, along  with   a  short  sketch  of  the
underlying principles.  At the  time when this  report is  written,  a
striking feature  of these  examples is   that none  of   them  can be
computed   directly with  any  of  today's  most  widespread  symbolic
computation     systems     (Macsyma\footnote{Sun    Release   309.6},
Mathematica\footnote{Version 1.2, beta  test},  Maple\footnote{Version
4.3} or Scratchpad~II\footnote{Version 4J}).

This document  is part of  a technical report~\cite{Salvy89} available
from INRIA.
\end{abstract}

\section*{Introduction}
Current symbolic computation systems generally lack facilities for
manipulating asymptotic expansion computations of a form more complex
than the first terms of a Taylor series or a Puiseux expansion (involving
fractional powers). We introduce a set of programs whose aim 
is to contribute to fill this gap. The emphasis here is on examples
displaying the variety of difficulties a general purpose program must
be prepared to encounter. With each of these examples is given a
glimpse of the built-in choices which make these procedures work where others
won't. 

All these examples have been attempted using the built-in asymptotic
capabilities of Maple, Mathematica, Macsyma and Scratchpad.
In all the cases (although Maple seems to perform better on simpler
examples) none of these systems could solve the problem directly, their
answers ranging from non-evaluated expressions or error messages to
segmentation faults or (apparently) infinite computations.

In the first part of this report, we give an overview of automatic
asymptotic expansions of functions given in an explicit form. Once
this is obtained, it becomes feasible to implement methods that deal
with non explicit expressions. Two such applications are presented in
part 2 and 3.
The first one is specialized in discrete problems for which a
generating function is available and the second one deals with a
large class of expressions given as integrals. In these two last
parts, not many details are given and the reader is supposed to
know or to accept the principles of the methods which are implemented.

\section*{Foreword}
In all the following examples, the toplevel procedure is {\em gdev},
which stands for ``generalized development''.
Its synopsis is:

\centerline{\tt gdev(expr,var=limpoint,<nbterms>,<dir>)}
\noindent where
\begin{itemize}
\item[--]{\em expr} is the expression to be studied,
\item[--]{\em var=limpoint} is an equation indicating the variable with
respect to which the expansion will be computed and the point this
variable is approaching, this point being any complex point or
plus or minus infinity,
\item[--]{\em nbterms} is an optional parameter specifying the number of terms
required in the expansion (the default is 1),
\item[--]{\em dir} is an optional parameter specifying the direction taken by
the variable to approach its limit. This may be one of {\em straight}
or {\em inverse}. The former means that the variable tends to its
limiting point following a straight line starting from 0 and the latter means
that it follows a straight line coming from infinity. At the origin,
`straight' means from the right on the real axis and `inverse' means
from the left. At plus or minus infinity, the variable always comes
from 0. The default is `straight'.
\end{itemize}

Another procedure {\em glimit} is built on top of {\em gdev} and
computes only the limit of the expression. The synopsis is the same,
except that no number of terms is required.

\section{Expansions of expressions given in a closed form}

Usually systems perform well on Puiseux scales and poorly on more
general scales. It is then necessary to define clearly what is meant
by `asymptotic scale' and `asymptotic expansion'.
\begin{definition} Let $\cal P$ be a point set and $\cal L$ a limiting point
of $\cal P.$ Let $\cal S_P$ be a set of functions defined on $\cal P,$
with values in the complex plane. $\cal S_P$ is said to be an
{\em asymptotic scale at $\cal L$} when for any couple
$(\varphi_1,\varphi_2)$ of 
functions in $\cal S_P,$ the limit of $\varphi_1(x)/\varphi_2(x)$ when
$x$ tends
to $\cal L$ in $\cal P$ is defined and is one of $\,0,+\infty.$
\end{definition}
\begin{definition}
Let $\cal S_P$ be an asymptotic scale at $\cal L$ and $f$ a complex
valued function defined on $\cal P.$ Then $f$ is said to admit {\em an
asymptotic expansion of Poincar{\'e} type} at $\cal L$ when there
exist an $n$-tuple $(a_1,\ldots,a_n)$ of complex numbers and an $n$-tuple
$(\varphi_1,\ldots,\varphi_n)$ of elements of $\cal S_P$ such that
\[\forall i\in\{1,\ldots n\},\forall\varphi\in{\cal S_P}\quad
\varphi_i=o(\varphi)\Longrightarrow
f-\sum_{j=1}^i{a_j\varphi_j}=o(\varphi).\]
\end{definition}
Usually, scales at a finite point $a$ with which systems are at ease
include $\{(x-a)^n,n\in{\bf N}\}$ (Taylor scale), $\{(x-a)^p,p\in{\bf
Z}\}$ (Laurent scale) or $\{(x-a)^r,r\in {\bf Q}\}$ (Puiseux scale)
and the analogous of these scales at plus or minus infinity. 

Beyond these scales, systems are usually at a loss, being unable to
determine automatically in which scale the computation must be
performed.
The following examples show some typical instances of what basic cases
our library is able to handle, that were unobtainable previously.
\subsection{Examples at a finite distance on the real axis}
\subsubsection{An exponential scale}
\ex

\noindent\begin{verbatim}> gdev(exp(tan(x))-1,x=Pi/2,2);
\end{verbatim}
\hbox{\vbox{\begin{verbatim}
                             /     1  \
                             |- 2 ----|
            /       1       \\     Pi /
           (|---------------|          )
            |        1      |
            |exp(----------)|
            |           x   |
            |    1 - 2 ---- |
            \           Pi  /
\end{verbatim}}}
\hbox{\vbox{\begin{verbatim}
                                                          /     1  \
                                                          |- 2 ----|
                            /       x  \ /       1       \\     Pi /
                + (- 1/6 Pi |1 - 2 ----| |---------------|          )
                            \       Pi / |        1      |
                                         |exp(----------)|
                                         |           x   |
                                         |    1 - 2 ---- |
                                         \           Pi  /
\end{verbatim}}}
\hbox{\vbox{\begin{verbatim}
                     /       x  \2            1        2
                + (O(|1 - 2 ----|  exp(---------------) ))
                     \       Pi /      /       x  \
                                       |1 - 2 ----| Pi
                                       \       Pi /
\end{verbatim}}}
In this example, there is an essential  singularity at $\pi/2$ and the
program automatically determines that the expansion's natural scale is
\[\left\{(1-{x\over \pi/2})^k e^{2\over\pi-2x}\right\}_{k\in\bf N}.\]
\subsubsection{An extended definition of asymptotic expansions}

Many extensions of the definition of asymptotic expansions given
above appear in the literature (see e.g. \cite{ErWy63,Schmidt36}) and
we choose an intermediate one which allows 
more general expansions without sacrificing implementability: In
our program, the coefficients $a_i$ are allowed to be functions of
bounded variation. The following example shows a use of this extended
definition: 
\ex

\noindent\begin{verbatim}> gdev(x^2*sin(1/x)/sin(x),x = 0,2);
\end{verbatim}\hbox{\vbox{\begin{verbatim}
                                                 3        5
                   (sin(1/x) x) + (1/6 sin(1/x) x ) + (O(x ))
\end{verbatim}}}
\subsubsection{A careful look at orders of expansion}
One must be very cautious concerning the management of the orders of
the expansions of the subexpressions, this is critical in examples
with numerous cancellations. In Maple, the given order is the order
taken in the intermediate computations, 
to get the following result, it is necessary to specify an order of 44~! In
Mathematica, the program does not seem to terminate.
\ex

\noindent\begin{verbatim}> gdev((tan(sin(x^4))-sin(tan(x^4)))/x^28,x = 0,2);
\end{verbatim}\hbox{\vbox{\begin{verbatim}
                                     29  8        16
                          (1/30) + (--- x ) + (O(x  ))
                                    756
\end{verbatim}}}
This example needs another comment. Some systems have chosen to
compute expansions with an absolute order. However, as soon as we
allow expansions in more general scales, there is no other choice than
to define the order as the number of terms in the expansion. 
\subsection{At infinity}
There is no real difference between expansions at a finite point and
expansions at infinity. The following example involves an intermediate
expansion in the scale $\{\exp(-nx)/x^n\}$ which does not appear in
the result:
\ex

\noindent\begin{verbatim}> f:=ln(x)^2-ln(x)*ln(x+exp(-x))+arctan(ln(x));
\end{verbatim}\hbox{\vbox{\begin{verbatim}
                        2
              f := ln(x)  - ln(x) ln(x + exp(- x)) + arctan(ln(x))
\end{verbatim}}}\begin{verbatim}
> gdev(f,x=infinity,2);
\end{verbatim}\hbox{\vbox{\begin{verbatim}
                                       1           1
                       (1/2 Pi) + (- -----) + (O(------))
                                     ln(x)            3
                                                 ln(x)
\end{verbatim}}}
\ex Euler's $\Gamma$ function is defined as
\[\Gamma(x)=\int_0^\infty{e^{-t}t^{x-1}dt},\]
and is known in Maple as GAMMA. Asymptotic expansions of expressions
involving it often necessitate difficult intermediate scales, even
though they may not appear in the result. In the following example,
the final result necessitates an ``extended'' expansion:

\noindent\begin{verbatim}> f:=GAMMA(x+sin(x))/GAMMA(x)*x^(-sin(x));
\end{verbatim}\hbox{\vbox{\begin{verbatim}
                                               (- sin(x))
                            GAMMA(x + sin(x)) x
                       f := -----------------------------
                                      GAMMA(x)
\end{verbatim}}}\begin{verbatim}
> gdev(f,x=infinity,2);
\end{verbatim}\hbox{\vbox{\begin{verbatim}
                               2
                     1/2 sin(x)  - 1/2 sin(x) - 1/12        1
              (1) + (-------------------------------) + (O(----))
                                    x                        2
                                                            x
\end{verbatim}}}
\ex The $W$ function is defined in Maple by
\[W(x)\exp(W(x))=x.\]
The limit and the scale of the following expansion are not totally obvious by
hand:

\noindent\begin{verbatim}> gdev(x^(1/W(x)),x=infinity,2);
\end{verbatim}\hbox{\vbox{\begin{verbatim}
                                                            2
                            exp(1) ln(ln(x))       ln(ln(x))
                (exp(1)) + (----------------) + (O(----------))
                                 ln(x)                    2
                                                     ln(x)
\end{verbatim}}}
\ex The following function is taken from Hardy \cite{Hardy10}
who uses it 
to describe the difficulty of finding a scale:

\noindent\hbox{\vbox{\begin{verbatim}> f:=sqrt(x)*(ln(x))^2*exp(sqrt(ln(x))*(ln(ln(x)))^2*exp(sqrt(ln(ln(x)))*
> (ln(ln(ln(x))))^3)):\end{verbatim}}}
\noindent which reads
\[f=\sqrt{x}\ln^2x\exp\left\{\sqrt{\ln x}\left(\ln\ln
x\right)^2\exp\left[\sqrt{\ln\ln x}\left(\ln\ln\ln x\right)^3\right]\right\}.\]

\noindent Then the following limit is difficult to obtain:

\hbox{\vbox{\begin{verbatim}
> glimit(f/exp(x),x=infinity);
                                       0
\end{verbatim}}}
What happens is that the only simple scale in which this function can be
expanded is a scale containing the function itself:

\hbox{\vbox{\begin{verbatim}
> gdev(f/exp(x),x=infinity,2);
      1/2      2          1/2          2              1/2              3
     x    ln(x)  exp(ln(x)    ln(ln(x))  exp(ln(ln(x))    ln(ln(ln(x))) ))
    (---------------------------------------------------------------------)
                                    exp(x)
\end{verbatim}}}
Of course special functions can be handled by the same tools and
sometimes they even need our generalized definition of an expansion:
\ex

\noindent\hbox{\vbox{\begin{verbatim}> gdev(BesselJ(2,ln(x)),x=infinity,2);
                                1/2                                 1/2
           sin(ln(x) + 1/4 Pi) 2               cos(ln(x) + 1/4 Pi) 2
        (- ------------------------) + (- 15/8 ------------------------)
                  1/2      1/2                        1/2      3/2
                Pi    ln(x)                         Pi    ln(x)
\end{verbatim}}}
\hbox{\vbox{\begin{verbatim}
                     1
             + (O(--------))
                       5/2
                  ln(x)
\end{verbatim}}}

With this first section, we have given a general view of the
capabilities of our library in the case of expressions in closed form.
This in turn will become the basic engine for specific applications
such as the ones we describe in the next two sections of~\cite{Salvy89}.
\section*{Conclusion}
Non trivial automatic asymptotic expansions can be derived, provided
asymptotic scales are carefully handled. Once a good engine for
performing expansions in large scales is implemented,
expansions which were not even expressible in symbolic computation
systems previously can be obtained quite easily. Work is in progress
to take benefit of this implementation of asymptotic scales
to program various asymptotic methods in a general setting. The
nuts and bolts of our implementation of asymptotic scales will be described
elsewhere.
\begin{thebibliography}{10}

\bibitem{AbSt73}
{\sc Abramowitz, M., and Stegun, I.~A.}
\newblock {\em Handbook of Mathematical Functions}.
\newblock Dover, 1973.

\bibitem{ErWy63}
{\sc Erd{\'e}lyi, A., and Wyman, M.}
\newblock The asymptotic evaluation of certain integrals.
\newblock {\em Archive for Rational Mechanics and Analysis 14\/} (1963),
  217--260.

\bibitem{Hardy10}
{\sc Hardy, G.~H.}
\newblock Orders of infinity.
\newblock {\em Cambridge Tracts in Mathematics 12\/} (1910).

\bibitem{Salvy89}
{\sc Salvy, B.}
\newblock Examples of automatic asymptotic expansions.
\newblock Technical Report 114, Institut National de Recherche en Informatique
  et en Automatique, 1989.

\bibitem{Schmidt36}
{\sc Schmidt, H.}
\newblock Beitr{\"a}ge zu einer {T}heorie der allgemeinen asymptotischen
  {D}arstellungen.
\newblock {\em Mathematische Annalen 113\/} (1936), 629--656.

\end{thebibliography}
\end{document}
