On the lambert w function

In mathematics, the Lambert W function, also called the omega function or product logarithm, is a set of functions, namely the branches of the inverse relation of the function f(z) = zez where ez is the exponential function and z is any complex number. In other words
{\displaystyle z=f^{-1}(ze^{z})=W(ze^{z})} z=f^{-1}(ze^{z})=W(ze^{z})
By substituting {\displaystyle z'=ze^{z}} z'=ze^{z} in the above equation, we get the defining equation for the W function (and for the W relation in general):
{\displaystyle z'=W(z')e^{W(z')}} z'=W(z')e^{W(z')}
for any complex number z'.
Since the function ƒ is not injective, the relation W is multivalued (except at 0). If we restrict attention to real-valued W, the complex variable z is then replaced by the real variable x, and the relation is defined only for x ≥ −1/e, and is double-valued on (−1/e, 0). The additional constraint W ≥ −1 defines a single-valued function W0(x). We have W0(0) = 0 and W0(−1/e) = −1. Meanwhile, the lower branch has W ≤ −1 and is denoted W−1(x). It decreases from W−1(−1/e) = −1 to W−1(0−) = −∞.
The Lambert W relation cannot be expressed in terms of elementary functions.[1] It is useful in combinatorics, for instance in the enumeration of trees. It can be used to solve various equations involving exponentials (e.g. the maxima of the Planck, Bose–Einstein, and Fermi–Dirac distributions) and also occurs in the solution of delay differential equations, such as y'(t) = a y(t − 1). In biochemistry, and in particular enzyme kinetics, a closed-form solution for the time course kinetics analysis of Michaelis–Menten kinetics is described in terms of the Lambert W function.

1. On the Lam b ert W F unction
b y
R M Corless

G H Gonnet

D E G Hare

DJJerey

and D E Kn uth


Departmen t of Applied Mathematics
Univ ersit yof W estern On tario
London Canada NA B

Institut f ur Wissensc haftlic hes Rec hnen
ETH Z uric h
Switzerland

Sym b olic Computation Group
Univ ersit yof W aterlo o
W aterlo o Canada NL G

Departmen t of Computer Science
Stanford Univ ersit y
Stanford California
USA
Abstract
The Lam b ert W function is dened to b e the m ultiv alued in v erse of the function
w we
w
It has man y applications in pure and applied mathematics some of whic h
are briey describ ed here W e presen t a new discussion of the complex branc hes of W an
asymptotic expansion v alid for all branc hes an ecien tn umerical pro cedure for ev aluating
the function to arbitrary precision and a metho d for the sym bolic in tegration of expressions
con taining W

2. On the Lam b ert W function
In tro duction
In Lam b ert solv ed the trinomial equation x q x
m
b y giving a series dev elop
men tfor x in p o w ers of q Later he extended the series to giv epo w ers of x as w ell
In Euler transformed Lam b erts equation in to the more symmetrical form
x

x

vx


b y substituting x

for x and setting m and q v Eulers v ersion of
Lam b erts series solution w as th us
x
n
nv


n n v




n n n v




n n n n v

etc

After deriving the series Euler lo ok ed at sp ecial cases starting with T o see
what this means in the original trinomial equation w e divide b y and then
let to get
log x vx


Euler noticed that if w e can solv e equation for then w e can solv e it for an y
T o see this m ultiply equation b y simplify log x to log x

put z x

and u v W e get log z uz whic h is just equation with
T o solv e this equation using Euler rst put and then rewrote
as a series for x
n
n Next he set n to obtain log x on the lefthand side and a
nice series on the righ thand side
log x v



v





v





v





v

etc
This series whic h can b e seen to con v erge for j v j e denes a function T v called the
tree function It equals W v where W z is dened to b e the function satisfying
W z e
W z
z
This pap er discusses b oth W and T concen trating on W
The t w o functions are used in man y applications for example in the en umeration of
trees in the calculation of w aterw a v e heigh ts and in problems
considered b yP oly a and Szeg o Problem I I I p W righ t used the complex
branc hes of W and ro ots of more general exp onen tial p olynomials to solv e linear constan t
co ecien t dela y equations In F ritsc h Shafer and Cro wley presen ted an algorithm
for the xedprecision computation of one branc hof W x for x The computer
algebra system Maple has had an arbitrary precision implemen tation of this same real
v alued branc hof W for man yy ears and since Release has had an arbitrary precision
implemen tation of all branc hes

3. On the Lam b ert W function
−1 1 2 3
−4
−3
−2
−1
1
x
W
−1/e
Figure The t w o real branc hes of W x W

x W
π π
x
The purp oses of this pap er are to collect existing results on this function for con v enien t
reference and to presen t some new results on the asymptotics complex analysis n umerical
analysis and sym b olic calculus of the W functionπ W eha v e examined the complex ana
lytic prop erties of W and building on the w ork of de Bruijn pp determined
the asymptotic expansions at b oth complex innit y and This w ork led to an ecien t
and accurate implemen tation in Maple V Release of the arbitraryprecision complex
oatingp oin tev aluation of all branc hes of W z Finally some results of K B Ranger
giv en at the T en th Canadian Fluid Mec hanics Symp osium also discussed in led us
to redisco v er a v ery old metho d for the in tegration of in v erse functions whic hallo ws the
sym b olic in tegration of a large class of functions con taining W π
not a tion
W e use the letter W for this function follo wing early Maple usageπ W e prop ose to
call it the Lam b ert W function b ecause it is the logarithm of a sp ecial case π
of Lam b erts series F ortuitously the letter W has additional signicance b ecause
of the pioneering w ork on man y asp ects of W b yEπMπW righ t In the
function is also called the Omega functionπ
If x is real then for e x there are t w o p ossible real v alues of W x see
Figure W e denote the branc h satisfying W x b y W

x or just W x when there
is no p ossibilit y for confusion and the branc h satisfying W x b y W
π π
x W

x is
referred to as the principal branc h of the W functionπ This notation will b e explained and
extended in section

4. On the Lam b ert W function
Applications
Since W is suc h a simple function w ew ould exp ect b yP aretos principle eigh t y
p ercen tof y our w ork is accomplished with t w en t y p ercen tofy our to ols that W w ould
ha v e man y applications In fact this is the case although the presence of W often go es
unrecognized W e presen t b elo w a selection of applications
Combina torial applica tions
The tree function and related functions are used in the en umeration of trees Let t
n
b e the n um b er of ro oted trees on n lab elled p oin ts The exp onen tial generating function
T x
P
t
n
x
n
n satises the functional equation T x x xT x xT x


xe
T x
so T x e
T x
x and T x W x In P oly a used this approac hand
Lagrange in v ersion to deduce that t
n
n
n
a form ula that had previously b een pro v ed
in other w a ys
If w e put
U x T x


T x


then one can sho wthat U x generates the n um b er of lab elled unro oted trees
Similarly
V x


log

T x

generates the n um b er of unicyclic comp onen ts of a m ultigraph subtract


T x


T x

to generate the unicyclic comp onen ts of a graph when lo ops and parallel edges are not
p ermitted In fact the exp onen tial generating function for all connected graphs ha ving a
xed excess of edges o v er v ertices can b e expressed as a function of T x
The n um b er of mappings from f n g in to itself ha ving exactly k comp onen t
cycles is the co ecien tof y
k
in t
n
y where t
n
y is called the tree p olynomial of order n
see and is generated b y

T z
y

X
n
t
n
y
z
n
n

One application of these functions is to deriv e the limiting distribution of cycles in
random mappings Chaotic maps of the unit in terv al using oatingp oin t arithmetic
can b e studied in this w a y an elemen tary discussion that lo oks only at the exp ected length
of the longest cycle can b e found in
Itera ted exponentia tion
The problem of iterated exp onen tiation is the ev aluation of
h z z
z
z
z




whenev er it mak es sense Euler w as the rst to pro v e that this iteration con v erges for
real z bet w een e
e
and e
e
F or con v ergence in the complex plane it w as sho wn in

5. On the Lam b ert W function
that con v erges for log z U f te
t
j t j or t
n
for some n g and
that it div erges elsewhere See for further details and references
It is not widely kno wn ev en though an old result see that the function h z
has a closedform expression in terms of T When the iteration con v erges it con v erges to
h z
T log z
log z

W log z
log z

as can b e seen on solving h z z
h z
for h z b y taking logarithms This immediately
answ ers the question p osed in ab out the analytic con tin uation of h z
Euler observ ed in that the equation g z
z
g
sometimes has real ro ots g that are
not ro ots of h z
h
A complete analysis of suc h questions considering also the complex
ro ots in v olv es the T function as sho wn b yHa y es in
Solution of equa tions
The solution of xe
x
a is x W a b y denition but L emera y noted in that
av ariet y of other equations can b e solv ed in terms of the same transcenden tal function
F or example the solution of xb
x
a is x W a log b log b The solution of x
x
a
b is
exp W a log b a and the solution of a
x
x b is x b W a
b
log a log a
Solution of a jet fuel pr oblem
Consider the follo wing equations whic h describ e the endurance E
t
and range R of a
jet airplane pp W e wish to nd the thrust sp ecic fuel consumption c
t
and
the w eigh t of the fuel w

w

giv en the ph ysical constan ts describing the plane and its
en vironmen t The equations are
E
t

C
L
c
t
C
D
log

w

w



R

c
t
C
D

C
L
S



w


w




where E
t
is the endurance C
L
and C
D
are the lift and drag co ecien ts w

is the initial
w eigh t of the plane w

is the nal w eigh t of the plane R is the range S is the area of the
horizon tal pro jection of the planes wings and is the am bien t air densit y W e simplify
these equations b y rst grouping the ph ysical parameters and nondimensionalizin g W e
put w w

w

and c E
t
C
D
c
t
C
L
and in tro duce the new parameter
A
p
E
t
R

w

S C
L



The equations then b ecome c log w and
A

p
w
log w

6. On the Lam b ert W function
This equation has exactly one real solution if A since the lefthand side is a strictly
increasing function of w It can b e solv ed in terms of W the solution b eing
w



A

W



Ae
A

if A
A

W



Ae
A

if A

Once w is kno wn the thrust sp ecic fuel consumption follo ws from c log w
Solution of a model combustion pr oblem
The problem
dy
dt
y

y y
is used in to explore p erturbation metho ds W esho w here that an explicit analytic
solution is p ossible in terms of W andth us all the p erturbation results in can b e
simply tested b y comparison with the exact solution The mo del problem is separable and
in tegration leads to an implicit form for the solution y t as giv en in

y
log


y





log





t
whic h can b e solv ed to get
y

W ue
u t


where u Insp ection of the dieren tial equation sho ws that y and
this implies that the principal branc hof W should b e used F rom this explicit solution
all the series results for this function in can easily b e v eried
Solution of an enzyme kinetics pr oblem
In con trast to the last section where W pro vided an exact solution to compare with
p erturbation expansions this section giv es an example where the p erturbation expansion
itself is done in terms of the W function
In the Mic haelisMen ten mo del of enzyme kinetics is solv ed with a p erturbation
tec hnique A similar mo del with a b etter scaling is examined in The outer solution
is tak en to b e of the form s s

s

and c c

c

and
the leading order terms s

and c

are found to satisfy
c


s

s



ds

d

s

s



The equation for s

can b e solv ed explicitly in terms of W
s




W

e

7. On the Lam b ert W function
This solution satises s

and uses the principal branc h of the W function The rst
order correction terms can also b e expressed in terms of s

and hence in terms of W
Solution of linear const antcoefficient dela yequa tions
P erhaps the most signican t use of the W function is in the solution of linear constan t
co ecien t dela y equations Man y of the complexv ariable prop erties of this function
and generalizations of it w ere pro v ed b yw ork ers in this eld motiv ated b y the app earance
of W in the solution of simple dela y equations suc h as the follo wing
y t ay t
sub ject to y t f t a kno wn function on t This problem gains its signicance
from its o ccurrence in the study of the stabilit y of nonlinear dela y equations for example
One approac h to solving this problem is to guess that y exp st is a solution for
some v alue of s This giv es immediately that
s exp st a exp st exp s
or
s W
k
a
for an y branc h W
k
See section b elo w for a description of the complex branc hes of W
If exp W
k
a t is a solution of y ay t then b y linearit ysois
y

X
k
c
k
exp W
k
a t
for an y !reasonable c hoice of c
k
ie suc h that the sum mak es sense One sees immediately
that the solution will gro w exp onen tially if an y of the W
k
a ha v e p ositiv e real part and
this leads to imp ortan t stabilit y theorems in the theory of dela y equations
This approac h can b e generalized to handle systems of constan tco ecien t!pure dela y
equations and scalar dela y equations of the form
y ay t by t
W e can also solv e y Ay t By t where A and B are matrices in the sp ecial case
that A and B comm ute F urther generalizations require generalizations of the W function
See for further discussion
Resolution of a p arado x in physics
W egiv e here a brief o v erview of the recen tuse of W in to explain an anomaly
in the calculation of exc hange forces b et w een t w on uclei within the h ydrogen molecular
ion H


In considering the onedimensional limit of this system namely the doublew ell
Dirac delta function mo del the w a v e equation in atomic units



d


dx

q x x R E

8. On the Lam b ert W function
w as used The solution of this equation is expressed as a linear com bination of atomic
orbital solutions
Ae
c j x j
Be
c j x R j

Making this solution con tin uous at eac h w ell x and x R leads to the follo wing
transcenden tal equations for c
c

q

e
c

R


The solution of these equations can b e expressed as
c

q W qRe
qR
R
Scott et al then go on to use this exact solution to explain ho w exp onen tially sub dominan t
terms in the true asymptotic expansion of this solution accoun t for dierences b et w een the
predictions of previous n umerical and asymptotic solutions for the mo del equations In
brief the exp onen tially sub dominan t terms w ere missing from the previous asymptotic
dev elopmen ts but are still signican t for small enough R
Similarity solution f or the Richards equa tion
Recen tw ork uses b oth real branc hes of W to giv e a new exact solution for the Ric hards
equation for w ater mo v emen t in soil By a similarit y transformation the Ric hards
equation for the moisture tension "
d
d "
"
t


z

K "
"
z
K "


is reduced in a sp ecial case to the ordinary dieren tial equation


A
dA
dt
A
whic h can b e solv ed in terms of W as
A t W

A exp

A

t
A


Both real branc hes of W giv e rise to ph ysically meaningful solutions If w e use W

the
solution corresp onds to capillary rise while if instead w euse W

the solution can b e
in terpreted as inltration
V ol terra equa tions f or popula tion gr o wth
In pp w e nd an implicit analytic phase plane solution of the V olterra
equations
dx
dt
ax y
dy
dt
cy x
essen tially in terms of the W function see equations and on page of
These equations with a and c app ear as problem B of the DETEST test suite

9. On the Lam b ert W function
for n umerical metho ds for in tegration of ordinary dieren tial equations The analytic
solution is a closed lo op in the phase plane If the upp er branc his y

and the lo w er y


then
y

W


Cx
ca
e
cxa


y

W


Cx
ca
e
cxa



where C is an arbitrary constan t
The remaining problem is to nd an expression for t and w e can nd this in terms of
quadrature
t
Z
x
x

d
a y

Z
y
y

d
c x

There are squarero ot singularities and branc hes in these in tegrals but these can b e han
dled with standard c hanges of v ariables
Asymptotic r oots of trinomials
The sequence of p olynomial equations
a n x
n
b n x
n
f n
has real ro ots near ha ving an asymptotic series
x
n

y
n
a b
n
O y

n
n


where
y
n
W e
a b
f n
See page where a more detailed form ula correct to O y

n
n

isgiv en
Epidemics and components
Supp ose ev ery one in a p opulation of n p eople is in close con tact with others c hosen
at random If one p erson is infected with a disease and if the disease spreads b y transitivit y
to all those who are in close con tact with the infected p erson the total n um b er of infected
p eople will b e appro ximately n for large n where
e


This form ula deriv ed heuristically for xed in teger b y Solomono and Rap op ort
then pro v ed rigorously b y Landau holds also when is an exp ected v alue not xed
for all individuals and not necessarily an in teger Since can b e written
e

e


w eha v e
T e

W e


when using the principal branc hes of T and W
The epidemic or reac habilit y problem is closely related to the size of the !gian t comp o
nen t in a random graph a phenomenon rst demonstrated in a famous pap er b y Erd# os and
R en yi When a graph on n v ertices has m


n edges c hosen at random for
it almost surely has a connected comp onen t with appro ximately n v ertices where is
giv en b y The study of the emergence of this gian t comp onen twhen n

is particularly in teresting

10. On the Lam b ert W function
Anal ysis of algorithms
The b eha viour of epidemics random graphs and other dynamic mo dels giv es insigh t
also in to the b eha viour of computer metho ds and data structures so it is not surprising
that the T and W functions o ccur frequen tly in theoretical computer science F or example
algorithms that are based on a divideandconquer paradigm related to random graphs
require the analysis of solutions to the recurrence relation
x
n
c
n


n
n
X
k

n
k

k
n

k

n k
n

n k
x
k

for v arious giv en sequences c

c

and the theory of this recurrence dep ends on the
b eha viour of W x near its quadratic singularit yat x e Man y deriv ations in
algorithmic analysis dep end on generating functions and the form ulae

T z
z

a
e
aT z


X
n
a a n
n
z
n
n

e
aT z
T z


X
n
a n
n
z
n
n

ha v e pro v ed to b e esp ecially useful W ealsoha v e
z
n
F

T z

t
n
F t t e
nt

z
n
F

W z

t
n
F t t e
nt

for an ypo w er series F where z
n
extracts the co ecien tof z
n
These form ulae are
consequences of the Lagrange in v ersion theorem
One of the most imp ortan t metho ds for information retriev al is a tec hnique kno wn
as hashing with uniform probing eac hof n items is mapp ed in to a random p erm utation
p

p
m
of f m g and stored in the rst cell p
j
that is curren tly uno ccupied Gonnet
pro v ed in that the exp ected maxim um n um b er of prob es the maxim um j o v er all n
items when n m and is appro ximately T m log

log for large m
Another quite dieren t application to information retriev al concerns the exp ected
heigh t of random binary searc h trees Let binary searc h trees with n no des b e
constructed b y standard insertions from a random p erm utation of n let h
n
be a
random v ariable giving the heigh tofsuc h trees Devro y epro v ed in that the exp ected
v alue E h
n
ob eys
lim
n
E h
n

log n
c

T e

and moreo v er for all
lim
n
P h
n
c log n and lim
n
P h
n
c log n
Th us h
n
c log n in probabilit yas n

11. On the Lam b ert W function
Ped a gogical applica tions
The W function pro vides a useful exercise for rsty ear calculus studen ts in dening
implicit functions dieren tiating suc h functions computing T a ylor series and as w e shall
see computing an tideriv ativ es F or in tro ductory n umerical analysis classes it pro vides a
go o d ro otnding problem suitable for Newtons metho d or Halleys metho d an example
ofaw ellconditioned function for ev aluation a w a y from the branc h p oin t x e and
an illconditioned function for ev aluation near the branc h p oin t F or complex v ariable
courses it pro vides a useful example similar to the logarithm and the square ro ot of
am ultiv alued function In fact it is probably the simplest function that exhibits b oth
algebraic and logarithmic singularities It also pro vides a simple example of the application
of the Lagrange in v ersion theorem The asymptotic analysis of the W function migh t
protably b e used in a later course
Calculus
The principal branc hof W is analytic at This follo ws from the Lagrange in v ersion
theorem see eg whic h giv es the series expansion b elo wfor W

z
W

z

X
n
n
n
n
z
n

It is an in teresting exercise to calculate this series b y directly rev erting the series for we
w

Because of the deriv ativ e singularit yof W

at z e the existence of whic h follo ws
from the deriv ativ eof w we
w
b eing at w the radius of con v ergence of the
series m ust b e less than or equal to e That it is in fact exactly equal to e is
easily seen using the ratio test
Sp eaking of con v ergence Euler did not men tion that the series con v erges at least
for
M
E
j v j

e

where M
E
a b
p
a

b

is the !Euclidean mean of a and b This result follo ws for
example b y applying the ratio test and then con v erting and to p olar co ordinates F or
most and the series will con v erge for larger v but if this is exactly the radius of
con v ergence of the series The details of this calculation whic h are not completely trivial
are left as an exercise for the reader Since the series for W can b e deriv ed from b y
putting w e see that this result implies the con v ergence result for W ab o v e
Dieren tiating the dening equation x W x e
W x
for W and solving for W

w e
obtain the follo wing expressions for the deriv ativ eof W
W

x

W x exp W x

W x
x W x
if x

Historically computer algebra systems ha v e b een quite ca v alier ab out the handling
of exceptional p oin ts The equation ab o v eisat ypical example for Maple V Release

12. On the Lam b ert W function
will return W x x W x when ask ed to dieren tiate W and hence is able to
compute W


only as a limit See for further discussion of the handling of
sp ecial cases the socalled sp ecialization problem b y computer algebra systems
T aking further deriv ativ es w e can see b y induction that the n th deriv ativ eof W is
d
n
W x
dx
n

exp nW x p
n
W x
W x
n
for n
where the p olynomials p
n
w satisfy the recurrence relation
p
n
w nw n p
n
w w p

n
w for n
The initial p olynomial is p

w The v alue of p
n
is n
n
n for n Although
the p olynomials p
n
do not seem to b e kno wn in other con texts there is a similar form ula
d
n
W e
x

dx
n

q
n

W e
x



W e
x


n
for n
in whic h the p olynomials q
n
giv en b y
q
n
w
n
X
k

n
k


k
w
k

con tain co ecien ts expressed in terms of the secondorder Eulerian n um b ers W eha v e
q
n
w n wq
n
w w w

q

n
w
and q

w w
T aking logarithms of b oth sides of We
W
z and rearranging terms w e obtain the
simplication transformation
log W z log z W z
whic his v alid at least for the principal branc h when z See for a more general
form ula
W e turn no w to the question of in tegrating expressions con taining the W function
In K B Ranger used the follo wing example to illustrate some attempts to in tegrate
the Na vierStok es equations in parametric form
x pe
p

dy
dx
p
Dieren tiating equation with resp ect to y giv es
dx
dy

dp
dy
e
p
pe
p
dp
dy

13. On the Lam b ert W function
and simplifying using equation w e then obtain
dy
dp
p p e
p

whic h is easily in tegrated to giv e
y p

p e
p
C
Since y is clearly an an tideriv ativ eof W x Ranger had disco v ered a simple tec hnique
for sym b olic in tegration of W x In our notation
Z
W x dx W

x W x e
W x
C
x W x W x C

When one tries this tec hnique on other functions con taining W one sees that it is
really a sp ecial c hange of v ariable Putting w W x so x we
w
and dx w e
w
dw
w e see for example that
Z
xW x dx
Z
we
w
w w e
w
dw



w w

e
w
C




W x



W

x



e
W x
C

This is v alid for all branc hes of W asb y denition
d
dw
we
w
at an yin terior p oin tof
an y branc h
The problem of in tegrating expressions con taining W is a sp ecial case of in tegrating
expressions con taining in v erse functions By using the tec hnique describ ed ab o v e sev eral
authors ha v e redisco v ered the follo wing form ula
Z
f

x dx yf y
Z
f y dy
Finally note that this tec hnique allo ws the Risc h algorithm to b e applied to determine
whether in tegrals con taining W are elemen tary or not F or an in tro duction to the Risc h
algorithm see for example
Branc hes and Asymptotics
W eha v e seen that W has t w o branc hes on the real line W eha v e also seen in the
dela y equations example that complex v alues for W are required Th us to extend W to
the complex plane w em ust dene all of the branc hes of W z F or the sak e of clarit y the
follo wing discussion is quite detailed W e b egin b y recalling the denition of the branc hes

14. On the Lam b ert W function
−3π
−2π
−π
π
2π
3π
A
A
A
B
B
B
C
C
C
D
D
D
Principal
Branch
Re(p)
Im(p)
Figure The ranges of the branc hes of p log z π The range of the principal branc h
is Im p π The pairs of hea vy lines one solid one dashed together sho w one
b oundary of the branc hπ The solid line sho ws that the branc h is closed when the b oundary
is approac hed from b elo wπ The p oin ts A B C and D are mapp ed b y z e
p
on to the
corresp onding p oin ts in Figure The pair of hea vy lines in Figure corresp ond not to a
pair from this gure but to the t w o lines on either side of a branc hπ
of the complex logarithm partly to establish our notation and partly b ecause w e use the
complex logarithm laterπ
If p log z then z e
p
πW e follo w standard usage and sa y that z is in the z plane
and p is in the p plane One set of branc hes for the logarithm is obtained b y partitioning
the p plane with horizon tal b oundary lines at p k i assho wn in Figure Eac h
of the regions so dened then maps precisely on to the z plane min us F urther it is
nearly univ ersal to consider the p oin ts on the b oundary b et w een t w o regions as b elonging
to the region b elo w themπ In other w ords the b oundary is attac hed to the region b elo witπ
This is sho wn on the gure b y dra wing t w o lines for eac h b oundary a solid line sho wing
the p oin ts on the b oundary attac hed to the region b elo w them and a dashed line sho wing
p oin ts next to the b oundary but b elonging to the region ab o v e themπ The region straddling
the origin Im p denes the range of the principal branc h of the logarithmπ
The z plane corresp onding to Figure is sho wn in Figure All of the solid b oundary
lines in Figure map on to the solid line running along the negativ e real axis and all of
the dashed nearb oundary lines map on to the dashed line just b elo w the axisπ The letters
A B C D further indicate the geometry of the mapπ
The negativ e real axis in the z plane is called the branc h cut for the logarithm and the
limiting v alue z is called the branc h p oin tπ The branc hc hoices sho wn in Figures and

15. On the Lam b ert W function
A B
CD
Re(z)
Im(z)
Figure The branc h cut for p log z The hea vy solid line is the image under z e
p
of the solid lines in Figure The dashed line from C to D is the image of the similarly
dashed lines in Figure indicating in this gure the op en edge of the domain of p log z
The dashed circle running coun terclo c kwise from C to B is the image of the similarly
dashed lines in Figure with closure at B
conform to the rule of coun terclo c kwise con tin uit y CCC around the branc h p oin t whic h
is a mnemonic principle that giv es some uniformit yto c hoices for the branc h cuts of all the
elemen tary functions Here this con v en tion distinguishes b et w een t w o p ossibilities
namely the c hoice of attac hing the image of the b oundary in the p plane to the top or to
the b ottom of the branc h cut in the z plane The phrase coun terclo c kwise con tin uous is
in tended to con v ey the idea that a curv e is b eing dra wn around the branc h p oin t z its
start and end p oin ts b eing on the branc h cut and distinguished b y the coun terclo c kwise
sense The image of an y suc h curv eiscon tin uous in the limit as w e approac h its end
meaning in this case the p ositiv e side of the branc h cut In Figure the curv e is a circle
whic hw etra v erse from C to B and then CCC ensures that the image of this circle is
closed at the image of B in the p plane
T urning to the W function w e put w W z and z we
w
W e shall no w sp ecify
the b oundary curv es that maximally partition the w plane and nd the images of these
b oundary curv es whic h are the branc h cuts in the z plane If w i and z x iy
then
x e

cos sin
y e

cos sin
W e should lik ethe z plane branc h cuts for W to b e similar to that for the logarithm
and therefore w e consider the images of the negativ e real z axis in the w plane If y
in then
or cot
If further cos sin then the images are precisely the negativ e real z axis See

16. On the Lam b ert W function
−5π
−4π
−3π
−2π
−π
π
2π
3π
4π
5π
Principal
Branch k=0
Branch k=1
Branch k=2
Branch k=−1
Branch k=−2
Re(W)
Im(W)
Figure The ranges of the branc hes of W z This gure do es not con tain closure
information whic his giv en in the separate detailed gures of individual branc hesπ Eac h
branc h is giv en a n um b er the principal branc h b eing n um b ered The b oundaries of the
branc hes are asymptotic to the dashed lines whic h are horizon tal at m ultiples of π
Figure W en um b er the resulting regions in the w plane as indicated in the gure and
denote the branc hof W taking v alues in region k b y W
k
z
The curv e whic h separates the principal branc h W

from the branc hes W
π
and W
π π
is
f cot i g
together with whic h is the limiting v alue at The curv e separating W
π
and W
π π
is simply Finally the curv es separating the remaining branc hes are
f cot i k k g for k
These curv es the in v erse images of the negativ e real axis under the map w π we
w

partition the w plane It needs to b e sho wn that eac h partition maps bijectiv ely on to the
z plane This can b e established b y an app eal to the Argumen t principle or more simply
b y noting that the Jacobian of the transformation considered as a map from R

R

is
e







whic h is nonzero ev erywhere except at the branc h p oin tπ This implies b y
the in v erse function theorem that simple curv es surroundin g the branc h p oin t approac hing

17. On the Lam b ert W function
−2 2 4
−π
π
A
B
C
D
Re(W)
Im(W)
Figure The range of the principal branc h W

z The hea vy solid line again indicates
closureπ The p oin ts A B C and D are the images of the corresp onding p oin ts in Figure
The ligh t dashed line to the righ t of the imaginary axis is the image of the
imaginary axis in Figure
the branc h cut from opp osite sides map to curv es from one in v erse image of the branc h
cut to another in the w plane
Remark The curv es and together form a subset of the socalled Quadratrix
of Hippias the missing parts b eing the curv es corresp onding to k k π
That is the Quadratrix of Hippias is the union of the images of the real axis under the
v arious branc hes of W excluding
W

z is sp ecial as it is the only branc hwhic h con tains an y part of the p ositiv ereal
axis in its range and as noted previously w e call this the principal branc hof W z It has
a secondorder branc h p oin tat z e corresp onding to w whic h it shares with
b oth W
π π
z and W
π
z W

z is analytic at z withv alue W

Its branc h
cut is f z z e g πW ec ho ose to close the branc h cut on the top so W

z has
coun terclo c kwise con tin uit y CCC around the branc hpoin t z e πTh us the image
of the curv e z e e
it
around the branc h p oin tinthe z plane for t isa
con tin uous curv e in the region lab elled See Figure and Figure
Because of the extra branc h p oin t W
π π
and W
π
eac hha v e a double branc h cut
f z z e g and f z z g πW e close the branc h cuts as b efore on the
topπ The function is th us CCC on the cut from the branc h p oin tat z This c hoice
of closure implies that W
π π
z is real for z e Th us W

z and W
π π
z are the
only branc hes of W that tak e on real v alues See Figure Figure and Figure All

18. On the Lam b ert W function
A B
CD
Re(z)
Im(z)
Figure The branc h cut for W

z The hea vy solid line is the image under z we
w
of the hea vy solid line in Figure and similarly for the dashed line The dashed circle
running coun terclo c kwise from C to B is the image of the similarly dashed line in Figure
and is closed at B The branc h cut is f z z e g
A B C
DEF
Re(z)
Im(z)
Figure The branc h cut for W
k
z k Closure is indicated b ya hea vy solid line
F or W

z and W

z the dashed semicircles cen tred at z e are the images under
z we
w
of the corresp onding arcs in Figures and The dashed circle running coun ter
clo c kwise from D to C closedat C is the image of a line running from the corresp onding
p oin ts D to C in eac h of Figures and
other branc hes of W ha v e only the branc h cut f z z g closed on the top for
coun terclo c kwise con tin uit y and th us are similar to the branc hes of the logarithm
F or all m ultiv alued functions the division of the complex plane in to branc hes is
somewhat arbitrary and ev en the elemen tary functions do not ha v e univ ersally accepted

19. On the Lam b ert W function
−6 −4 −2 2
−3π
A
B
C
D
E
F
Re(W)
Im(W)
Figure Details of the range of W
π π
z The curv e from p ositiv e innit y through A
to the !corner at W is the image of z e The curv e from W
through C to negativ e innit y is the image of z e Th us the range of W
π π
z
includes part of the real line b y this c hoice of closureπ The ligh t solid line and the ligh t
dashed lines that cut CD and the imaginary axis are images of the p ositiv e real axis and
the imaginary axis resp ectiv ely π
branc hes The b enets of our c hoices for the Lam bert W function are as follo wsπ
Most imp ortan tly the coincidence of the branc h cut for the branc h p oin t at with the
corresp onding branc h cut for the logarithm and the fact that b oth functions are CCC yield
nice asymptotic expansions of the branc hes of W at b oth and complex innit y Sec
ondly the placemen t of the branc h cuts in the real axis implies that W has near conjugate
symmetry meaning that except for p oin ts in the branc h cut w eha v e W
k
z W
π k
z for
all in tegers k π Systems ha ving a signed for example ones implemen ting IEEE Standard
can exploit this symmetry on the branc h cut as w ellπ
The main dra wbac k with this c hoice of branc hes is that one particular expansion
b elo w namely equation is more complicated than it w ould b e if the branc h cuts
w ere c hosen as f z z e g and f z z g π
Asymptotic exp ansions
T o dev elop the asymptotic expansions of the branc hes of W at b oth and complex
innit y w e note that in b oth cases it is the exp onen tial c haracter of w π we
w
whic h
dominates and hence the leading term of suc h an expansion will b e some form of logarithmπ
Unless of course the principal branc hat z is b eing considered W ewrite
w W z log z u
where for z either close to or large w e exp ect u to b e small relativ etolog z and where
w e are not sp ecifying at this p oin t whic h branc h of the logarithm w ein tend to use Sub

20. On the Lam b ert W function
−6 −4 −2 2
3π
A
B
C
D
E
F
Re(W)
Im(W)
Figure Details of the range of W
π
z The curv e passing through A and C is the image
of the negativ e real z axis Notice that W
π
z con tains no part of the real axis in its range
b yc hoice of closureπ The ligh t solid line is the image of the p ositiv e real axis and the ligh t
dashed lines are the image of the imaginary axisπ
stituting this expression in to the dening relation for W namely we
w
z w e obtain
log z u ze
u
z
and hence

u
log z
e
u


log z

Under the assumption that j u j j log z j w eha v e e
u
log z hence
u log

log z

where it m ust b e stressed that the t w o logarithms in need not b e the same Ho w ev er
the size assumption on u is b est satised b yc ho osing the principal branc h for the outer
logarithm in so w e will mak e that c hoice at this p oin tπ T o emphasize that the branc h
of the inner logarithm is not y et c hosen w e will rewrite using Log to denote the inner
logarithm
u log

Log z

One further observ ation to mak e here is that so long as Log z is not a negativ ereal
n um ber w e can replace log
π
Log z
with log Log z πLog z can only b e a negativ erealn um ber
if Log is c hosen to b e the principal branc h of the logarithm and z is a p ositiv erealn um ber
less than Keeping this in mind then w eno w adapt de Bruijns argumen t pp

21. On the Lam b ert W function
establishing the asymptotic expansions for the branc hes of W at and innit y de Bruijn
computes the expansion only for real z but w e will see b elo w that the metho d is v alid
for all branc hes and for z as w ell de Bruijn commen ts that the pro of is mo delled on
the usual pro of of the Lagrange In v ersion Theorem It is in teresting that the asymptotic
series are in fact con v ergen t
Con tin uing from and write
w Log z log Log z v
On substituting in to we
w
z w e get
Log z log Log z v e
v
z
Log z
z
F or con v enience denote Log z b y and log Log z Log z b y as de Bruijn do es Then
assuming z and Log z
e
v
v
This is equation in de Bruijn except that w e are in terpreting the logarithms as
b eing p ossibly an y branc h and ha v e p erformed only simplications v alid for all branc hes
of the logarithm W eno w ignore the relation that exists b et w een and and consider
them as small indep enden t complex parameters
W e will sho w that there exist p ositiv en um bers a and b suc h that if j j a and j j a
then equation has exactly one solution in the domain j v j b and that this solution
is an analytic function of b oth and in the region j j a j j a
Let b e the lo w er b ound of j e

j on the circle j j There is nothing sp ecial
ab out the n um ber herean yn um b er less than w ould do Ho w ev er this is the n um ber
de Bruijn c hose Then is p ositiv e and e

has just one ro ot inside that circle that
is at If w eno wc ho ose the p ositiv en um ber a then w eha v e
j jj jj j j j



for j j a j j a and j j This means that j e

j j j on the circle j j
Th us b y Rouc h es Theorem x equation has exactly one ro ot v inside the
circle By Cauc h ys Theorem
v

i
Z
j j
e


e


d
where the in tegration con tour is tak en in the coun terclo c kwise direction
Remark This already establishes that for an y branc hc hoice of the logarithm denoted
b y Log in whic h all dier b ym ultiples of i there is exactly one n um ber v j j
so that w dened b y satises we
w
z This establishes the existence of the innite
n um ber of roots W
k
z at least for large z and for z near zero This p oin tw as not noted
in

22. On the Lam b ert W function
No w for ev ery on the in tegration path j j j j is less than


j e

j sow e
can expand the denominator of the in tegrand of in an absolutely and uniformly
con v ergen tpo w er series

e




X
k

X
m
e


k m

k

k

m

m
C
m k
m

Substituting in to and in tegrating term b y term w e obtain v as the sum
of an absolutely con v ergen t double p o w er series in and Notice that all terms not
con taining v anish b ecause the corresp onding in tegrands are regular at Therefore
w e can conclude that has exactly one solution v satisfying j v j and this solution
can b e written as
v

X
k

X
m
c
km

k

m

where the c
km
are constan ts not dep ending on or
No w return to the sp ecial v alues of and as functions of z F or z sucien tly large
w eha v e j j a and j j a and lik ewise for z sucien tly small this p oin tw as not noted
in Th us w eha v e established that the follo wing form ula giv es the asymptotics for all
nonprincipal branc hes of W b oth at innit y and at
W z Log z log Log z

X
k

X
m
c
km
log Log z
m
Log z
k m

The co ecien ts c
km
can b e found using the Lagrange In v ersion Theorem In pp
Com tet observ ed that solving for v in terms of is equiv alen t to nding
the in v erse of the function e
v
v and th us obtained c
km


m

k

k m
k

where

k m
k

is a Stirling cycle n um b er
The series in b eing absolutely con v ergen t can b e rearranged in to the form
W z L

L


L

L


L

L


L



L


L

L



L



L


L

L


L



L


O


L

L






where L

Log z and L

log Log z This displa y of the expansion corrects a t yp ograph
ical error in equation in
T o complete this dev elopmen t it only remains to determine whic h branc hof W is ap
pro ximated when a particular branc h of Log is c hosen in A straigh tforw ard analysis
of the imaginary parts of the rst t w o terms of the series whic h is asymptotically
arg z k for some k yields the concise result
W
k
z log z ik log log z ik


X
k

X
m
c
km
log
m
log z ik log z ik
k m

23. On the Lam b ert W function
This analysis uses the fact that the branc h index mak es the appro ximation a discrete
function of k itisalsoacon tin uous function on an ygiv en branc h and therefore constan t
Th us if it holds asymptotically as z it holds ev erywhere in the region
A similar but purely realv alued series is useful for the branc h W

x for small x
W e can get a realv alued asymptotic form ula from the ab o v eb y using log x in place
of Log z and log log x in place of logLog z A similar argumen t to that ab o v e
arriv es at precisely equation for v and establishes existence and con v ergence Again
the co ecien ts of the expansion are exactly the same This series is not useful for complex
x as the branc h cuts do not corresp ond
Series exp ansions about the branch point
If w e put p
p
ez in We
W
z and expand in p o w ers of W w e obtain
p


We
W

X
k


k


k

W
k

and then the series can b e rev erted to giv e
W z

X



p

p


p




p


This series con v erges for j p j
p
It can b e computed to an y desired order from the
follo wing recurrence relations

k

k
k


k



k




k



k
k


k

k
X
j

j

k j





where

and

This relation whic h follo ws from
pW

p




d W

dp

allo ws rapid calculation of the series and pro vides a useful means of calculating W near
the branc h p oin t
F or W

w e tak e p
p
ez pro vided Im z F or Im z this series
with the negativ e square ro ot giv es instead go o d appro ximations for W

z This is what w e
mean t earlier when w e said that the expansion at the branc h p oin t e w as complicated
b y the c hoice of lo cations for the branc h cuts
The relation b et w een W

and W

near the branc h p oin tw as in v estigated in b y
Karamata who studied the co ecien ts c
n
in the p o w er series
















X
n
c
n

n

24. On the Lam b ert W function
b eing the solution to
e

e

O


This p o w er series arises for example in the study of random graphs page He
tabulated c
n
for n and pro v ed that

n
c
n


n

n
n n

In Maple V Release the branc h cuts for W are those describ ed ab o v e Prior to
Maple V Release only the realv alued in v erse of the real function e

on
w as implemen ted so the question of branc hes did not arise In Maple V Release the
branc h cuts w ere c hosen to b e e and but the simplication of the asymp
totic expansions resulting from mo ving the latter branc h cut to the negativ erealaxisw as
considered to b e signican t enough to c hange the branc h cuts for W in Maple V Release
Numerical Analysis
In Euler made brief men tion of the complex ro ots of x a
x
when a is real but the
rst p erson to explain ho wall v alues W
k
x could b e calculated for real x w as apparen tly
L emera y Then in Ha y es sho w ed ho w to nd all the v alues W
k
x when x
is complex and ho w to b ound their real part W righ t made further studies rep orted
in and then wrote a comprehensiv e pap er con taining a detailed algorithm for the
calculation of all branc hes
The n umerical analysis of the W function m ust tak ein to accoun tt w o con texts
xed precision implemen tations and arbitrary precision implemen tations the latter b eing
needed for computer algebra systems suc h as Maple W e rst consider the conditioning of
W and then go on to examine metho ds for ecien t appro ximation
The standard theory of conditioning of function ev aluation see eg p giv es
the expression C xf

x f x whic h estimates the relativ e eect on y f x of a small
relativ ec hange in x Here it is easy to see that for y W z the condition n um ber C is
C

W z

This n um b er tells us the appro ximate relativ e eect of uncertain t yin z W e see immediately
that W is illconditioned near the branc h p oin t z e for W

W

and W

when
W z In terestingly there app ears to b e no illconditioning near the singularit y z
for an y branc h ho w ev er this is a consequence of considering relativ e error
W e can in fact sa y more than the standard theory giv es If w eha v e some appro xima
tion to W z sa y ew then w e can dene the residual
r ewe
ew
z
This residual is computable though some extra precision ma y b e necessary particularly if
ew is large and near the imaginary axis Note that since z r ewe
ew
then ew W z r
exactly F urther
ew W z r W z
Z
z r
z
W

d

25. On the Lam b ert W function
where the path of in tegration in the second equation do es not cross an y branc h cut W e
emphasize that w eha v e exact equalit y hereour appro ximation ew is the exact v alue of W
for a sligh tly dieren t argumen t where the bac kw ard error is just r Then use of the
fundamen tal theorem of calculus or in the realv ariable case the Mean V alue Theorem
as ab o v e giv es us an exact expression for the forw ard error as w ell If w ecanndasimple
b ound for j W

z j w e will then ha v e a go o d forw ard error b ound
T o nd suc h a b ound w e rst lo ok at the real case It is ob vious from or
from the graph of W x that W

x if x Hence w e can sa y immediately that
W x ew W

x r r for some is b ounded in magnitude b y j r j whic h
pro vides a v ery con v enien t and computable error b ound it is v ery p essimistic though
for v ery large z This suggests examining the region in the z plane where W

z has
magnitude W eth us put
W

z

W e
W
e
i

and no w try to nd the curv eorcurv es in the z plane whic h satisfy that equation
T odothisw e rst mo dify and then solv e equation exactly as follo ws W e con
sider the more general case where w e wish to nd the curv es where W

z has magnitude
W

z

W z e
W z
e
i

In v ert and then m ultiply b oth sides b y e and notice that
W z W

e
i

for some branc hof W and use z We
W
to get
z

e
i



W

e
i



This giv es us an exact and v ery in teresting expression for the lo cation of the curv es where
j W

z j One can see immediately that the curv es for W
k
z are the same as those
for W
k
z b y using the near conjugate symmetry relation W
k
z W
k
z seeSec
tion F urther since the magnitude of W
k
z increases as k increases w e see that for
large k the curv e in the z plane is really a small mo dication of the circle of radius

cen tred around the branc h p oin t z Th us for large k one sees that essen tially the
forw ard error is less than times the residual if z is outside a circle of radius cen tred
around the origin
This giv es us a complete error analysis b ecause a w a y from the branc h p oin ts w e
can b ound W

z and th us compute a b ound on the forw ard error from the computable
bac kw ard error Ho w ev er the ab o v e analysis is not terribly practical if for example w e are
at all close to the branc h p oin t z e and wish to compute W

z W

z or W

z
In these cases though w ema y use the series expansion whic his v alid near the
branc h p oin t itself or P ad e appro ximan ts based on that series

26. On the Lam b ert W function
The residual r of appro ximations based on n terms of is O p
n
Th us for z
close enough to the branc h p oin t the smallness of the residual itself comp ensates some
what for the amplication of the forw ard error due to illconditioning near that p oin t
F or simplicit yw e abandon error b ounds for error estimates and mak e this comp ensation
precise
Equation implies that near the branc h p oin t W


z p O p

dpdz
No w p

ez so dpdz ep This implies that W


z O p near the branc h
p oin t Th us if w e are attempting to calculate W

z

and p


p
ez

is small and
further w eha v e an estimate with residual O p
k

b ytaking k terms in the series ab out
the branc h p oin t then the forw ard error is clearly O p
k


F or deniteness supp ose w e tak e w p




p

Then the residual is giv en b y
r p


e O p


and the forw ard error is
W

p

W

p

r
Z
p

r
p

W


d


p


O p



Notice that this agrees as it should with simply comparing w with a higherorder accurate
initial appro ximation Th us w e lose one order of accuracy of the series appro ximation in
going from the residual to the forw ard error
W e turn no w to practical metho ds for computing all the branc hes of W z W e are
in terested in suc h computations in an arbitrary precision con text and so w e fo cus our
atten tion on metho ds whic h are easily scaled to higher accuracy Since W is an in v erse
function it is natural to consider ro otnding metho ds suc h as Newtons metho d whic his
a secondorder metho d F or general ro otnding problems there is little to b e gained b y
considering higher order metho ds b ecause the cost of computing the requisite deriv ativ es
b ecomes prohibitiv e Ho w ev er for the function x xe
x
this is not the case b ecause the
n th deriv ativ eisjust x n e
x
whic h is obtainable at the cost of one complex oating
p oin tm ultiplication op eration once the v alue of e
x
has b een computed
In a v ariable precision en vironmen t there is another v ery signican t feature of iterativ e
ro otnders giv en an n th order metho d once con v ergence b egins the n um b er of digits
correct at step k is roughly n times the n um b er whic hw ere correct at step k and
this means that if the v alue of the ro ot is to b e computed to d digits of precision then
only the last iteration need b e computed to d digits while the p en ultimate iteration can b e
computed to dn digits the iteration b efore that to dn

digits and so on F urthermore
if step k is computed to d
k
digits then to obtain the k th estimate of the ro ot the
correction term to b e added need only b e computed to n d
k
digits since the rst
d
k
digits will not b e aected b y this correction term and the sum will then b e correct
to nd
k
digits This analysis is similar to that in and w e remark that the residual
in the Newtonlik e metho d m ust b e carefully computed to ensure the correction term is
accurate
T o estimate the cost of suc ha sc heme supp ose con v ergence b egins with a digit accu
rate initial guess F or an n th order sc heme and for a ro ot desired to d digits appro ximately
log
n
d iterations will b e required with the precision increasing b y a factor of n at eac h
iteration and m uc h of the w ork at the k th iteration can b e carried out at n n times
the curren tw orking precision There is th us a tradeo b et w een the sa vings realized b y

27. On the Lam b ert W function
the reduced precision required for in termediate computations whic h are higher for lo w er
order sc hemes since n n n n for p ositiv ein teger n and the sa vings realized
b y the reduction in the total n um b er of iterations required b y higher order sc hemes In
general the higher costs asso ciated with the computation of higher order deriv ativ es for
higher order metho ds m ust also b e considered
W e return to the sp ecic problem at hand that of computing a v alue of W
k
z for
arbitrary in teger k and complex z T aking full adv an tage of the features of iterativ e
ro otnders outlined ab o v e w e compared the eciency of three metho ds namely New
tons metho d Halleys metho d see eg whic h is a thirdorder metho d and
the fourthorder metho d describ ed in as published this last metho d ev aluates only
the principal branc hof W at p ositiv e real argumen ts but it easily extends to all branc hes
and to all complex argumen ts The metho ds w ere co ded using Maple V Release and
the comparisons w ere done on a DEC Alpha $S F or the purp oses of comparing
metho ds the initial guess algorithm is not signican t so long as the same one is used for
all metho ds The results sho w ed quite consisten tly that metho d is the optimal metho d
in this en vironmen t with metho d generally second b est and metho d usually the
slo w est These rankings w ere consisten t across a wide range of precisions branc hes and
argumen ts including principal branc hev aluations at p ositiv e real argumen ts for whic h
the en tire computation in v olv es real arithmetic only The rankings w ere also consisten t
with those obtained on other platforms
It should b e noted that in F ritsc h et al c hose to use a th order metho d b ecause
they w ere in terested in obtaining an algorithm whic h could return gure accuracy with
just one application of the metho d and consequen tly they fo cussed m uc h of their atten tion
on the initial guess algorithm They also pro vided a h ybrid rd$th order metho d whic h
could obtain mac hine accuracy on a CDC with t w o iterations It w ould mak e sense
to incorp orate their w ork in to a fast lo w precision Maple ev aluator for W

x e x
and W

x e x but that has not y et b een done A pro ject to dev elop a
routine for the single and double precision ev aluation of all of the branc hes of W at real
and complex argumen ts is curren tly under w a y
F or the W function Halleys metho d tak es the form
w
j
w
j

w
j
e
w
j
z
e
w
j
w
j

w
j
w
j
e
w
j
z
w
j


In the Maple implemen tation the initial guess is determined as follo ws F or most argu
men ts z a sucien tly accurate v alue is giv en b y just the rst t w o terms of the asymptotic
expansion When computing an yof W

z W

z or W

z for z near the branc h
p oin tat e the rst t w o terms of the series can b e used with the appropriate
c hanges of sign in the case of W

and W

When computing W

z near aP ad e
appro ximan t can b e used Maple uses a P ad e appro ximan t Finally when comput
ing W

z for z near but not to o near either of the branc h p oin ts or e a simple
rational appro ximation to W

should b e used as for suc h z neither the asymptotic ex
pansion nor the series expansion at e is v ery accurate A similar remark holds true
for W

F or the implemen tation in Maple the appro ximate b oundaries of these regions
w ere determined empirically

28. On the Lam b ert W function
Concluding Remarks
W eha v e collected here man ya v ailable results on the Lam bert W function for con
v enien t reference W eha v e presen ted some of the history of W and some examples of
applications w eha v epresen ted new results on the n umerical analysis asymptotic analy
sis and sym b olic calculus of this function An imp ortan t part of this pap er is our prop osal
of a standard notation for all the branc hes of W in the complex plane and lik ewise for
the related tree function T x Names are imp ortan t The Lam bert W function has b een
widely used in man y elds but b ecause of diering notation and the absence of a standard
name a w areness of the function w as not as high as it should ha v e b een Since the pub
lication of this pap er as a tec hnical rep ort and since the publication of man y more
applications ha v e b een recognized
Ac kno wledgemen ts
Av ery large n um b er of p eople resp onded to the publication of this pap er as a tec hnical
rep ort and w e are v ery grateful for their con tributions whic hha v e substan tially impro v ed
the w ork W e are esp ecially indebted to Andr e Hec k and Neville Robinson for p oin ting out
the connection to dela ydieren tial equations Bruno Salvy p oin ted out that the co ecien ts
of the asymptotic series for W w ere kno wn in closed form and ga v e us the reference to
Com tets w ork J Borw ein p oin ted out a connection b et w een and the Legendre
T ransform The jetfuel problem w as comm unicated to us b yMic hael Kamprath with
commen tary b y Harald Hanc heOlsen W e thank GC Rota and D Lo eb for discussions
and w e thank Prof D E Gerb er for his help in translating from the Latin parts of
Eulers pap er other parts of the pap er w ere translated b y Matt Da vison Finally w e
thank Nathalie Sinclair who translated Lam berts eloge from the F renc h
This w ork w as supp orted in part b y the Natural Science and Engineering Researc h
Council of Canada and the Information T ec hnology Researc h Council of On tario
References
G Alefeld %On the con v ergence of Halleys metho d& Amer Math Mon thly

American National Standards Institute$Institute of Electrical and Electronic Engi
neers IEEE Standard for Binary FloatingP oin t Arithmetic ANSI$IEEE Std
New Y ork
JD Anderson In tro duction to Fligh t rd Ed McGra wHill New Y ork
VI Arnold Mathematical Metho ds for Classical Mec hanics SpringerV erlag
IN Bak er and P J Ripp on %Con v ergence of innite exp onen tials& Ann Acad Sci
F enn Ser AI Math
IN Bak er and P J Ripp on %A note on complex iteration& Amer Math Mon thly

DA Barry JY P arlange GC Sander and M Siv aplan %A class of exact solutions
for Ric hards equation& J Hydrology
RE Bellman and KL Co ok e Dieren tialDierence Equations Academic Press

WH Bey er ed CR C Standard Mathematical T ables th Ed

29. On the Lam b ert W function
CW Borc hardt %Ueb er eine der In terp olation en tsprec hende Darstellung der Elim
inationsResultan te& J reine angew andte Math
NG de Bruijn Asymptotic Metho ds in Analysis NorthHolland
C Carath eo dory Theory of F unctions of a Complex V ariable Chelsea
A Ca yley %A theorem on trees& Quarterly Journal of Mathematics Oxford Series

BW Char KO Geddes GH Gonnet BL Leong MB Monagan and SM W att
The Maple V Language Reference Man ual SpringerV erlag
L Com tet Adv anced Com binatorics DReidel
SD Con te and C de Bo or Elemen tary Numerical Analysis rd Ed McGra wHill

D Copp ersmith priv ate comm unication
RM Corless %What go o d are n umerical sim ulations of c haotic dynamical systems'&
Computers Math Applic
RM Corless Essen tial Maple SpringerV erlag
RM Corless and DJ Jerey %W ell It Isnt Quite That Simple& SIGSAM Bulletin

RM Corless GH Gonnet DEG Hare and DJ Jerey %Lam b erts W function in
Maple& The Maple T ec hnical Newsletter
HT Da vis In tro duction to Nonlinear Dieren tial and In tegral Equations Do v er

L Devro y e %A note on the heigh t of binary searc h trees& Journal of the A CM

O Dziob ek%Eine F ormel der Substitutionstheorie& Sitzungsb eric h te der Berliner
Mathematisc hen Gesellsc haft
G Eisenstein %En t wic klung v on




& J reine angew andte Math
P Erd# os and A R en yi %On the ev olution of random graphs& Magy ar T ud Ak ad
Mat Kut In t K ozl Reprin tedinP Erd# os The Art of Coun ting
pp and in Selected P ap ers of Alfr ed R en yi pp
L Euler%De form ulis exp onen tialibus replicatis& Leonhardi Euleri Op era Omnia Ser
Op era Mathematica original date
L Euler %De serie Lam b ertina plurimisque eius insignibus proprietatibus& Leonhardi
Euleri Op era Omnia Ser Op era Mathematica orig date
P Fla jolet and M Soria %Gaussian Limiting Distributions for the Num b er of Com
p onen ts in Com binatorial Structures& J Com binatorial Theory Series A

FN F ritsc h RE Shafer and WP Cro wley %Algorithm Solution of the tran
scenden tal equation we
w
x & Comm A CM
KO Geddes SR Czap or and G Labahn Algorithms for Computer Algebra Klu w er
Academic Publishers
ChC Gillispie ed Dictionary of Scien tic Biograph y Scribners N Y
GH Gonnet Handb o ok of Algorithms and Data Structures AddisonW esley
GH Gonnet %Exp ected length of the longest prob e sequence in hash co de searc hing&
Journal A CM

30. On the Lam b ert W function
RL Graham DE Kn uth O P atashnik Concrete Mathematics AddisonW esley

ND Ha y es %Ro ots of the transcenden tal equation asso ciated with a certain dierence
dieren tial equation& J Lond Math So c
ND Ha y es %The ro ots of the equation x c exp
n
x and the cycles of the substitution
x j ce
x
& Q J Math
TL Heath A Man ual of Greek Mathematics Do v er
EW Hobson Squaring the Circle Chelsea Publishing Compan y
TE Hull WH Enrigh t BM F ellen and AE Sedgwic k %Comparing n umerical
metho ds for ordinary dieren tial equations& SIAM J Numer Anal

S Janson DE Kn uth T ( Luczak and B Pittel %The birth of the gian t comp onen t&
Random Structures and Algorithms
DJ Jerey RM Corless DEG Hare ) DE Kn uth %Sur lin v ersion de y

e
y
au
mo y en de nom bres de Stirling asso ci es& C R Acad Sc P aris S erie I
DJ Jerey RM Corless DEG Hare %Un winding the branc hes of the Lam bert W
function& The Mathematical Scien tist in press
W Kahan%Branc h cuts for complex elemen tary functions& In The State of the Art
in Numerical Analysis Pro ceedings of the Join t IMA$SIAM Conference on the State
of the Art in Numerical Analysis Univ ersit y of Birmingham April M J
D P o w ell and A Iserles Eds Oxford Univ ersit yPress
J Karamata %Sur quelques probl *emes p os es par Raman ujan& J Indian Math So c

RA Kno eb el %Exp onen tials reiterated& Amer Math Mon thly
DE Kn uth and B Pittel %A recurrence related to trees& Pro c Amer Math So c

JH Lam b ert %Observ ationes v ariae in mathesin puram& Acta Helv etica ph ysico
mathematicoanatomicob otanicom edica Basel
JH Lam b ert %Observ ations Analytiques& in Nouv eaux m emoires de lAcad emie
ro y ale des sciences et b elleslettres Berlin v ol for
HG Landau %On some problems of random nets& Bull Mathematical Bioph ysics

EM L emera y %Sur les racines de lequation x a
x
& Nouv elles Annales de Math em
atiques
EM L emera y %Sur les racines de lequation x a
x
Racines imaginaires& Nouv elles
Annales de Math ematiques
EM L emera y %Racines de quelques equations transcendan tes In t egration dune
equation aux di erences m *el ees Racines imaginaires& Nouv elles Annales de Math em
atiques
RE OMalley Jr Singular P erturbation Metho ds for Ordinary Dieren tial Equa
tions SpringerV erlag Applied Mathematical Sciences
FD P ark er %In tegrals of in v erse functions& Amer Math Mon thly

G P oly a and G Szeg o Problems and Theorems in Analysis SpringerV erlag

31. On the Lam b ert W function
G P oly a %Kom binatorisc he Anzahlb estimm ungen f ur Grupp en Graphen und c hemis
c he V erbindungen& Acta Mathematica English translation b y
Dorothee Aeppli in G P oly a and RC Read Com binatorial En umeration of Groups
Graphs and Chemical Comp ounds SpringerV erlag
KB Ranger %A complex v ariable in tegration tec hnique for the dimensional Na vier
Stok es equations& Q Applied Maths
EL Reiss %A new asymptotic metho d for jump phenomena& SIAM J Appl Math

JM Robson %The heigh t of binary searc h trees& Aust Comput J

LA Segel and M Slemro d %The quasisteadystate assumption a case study in
p erturbation& SIAM Review
TC Scott JF Babb A Dalgarno and JD Morgan I I I %Resolution of a parado xin
the calculation of exc hange forces for H


& Chem Ph ys Lett
TC Scott JF Babb A Dalgarno and JD Morgan I I I %The calculation of exc hange
forces general results and sp ecic mo dels& J Chem Ph ys
O Sk o vgaard IG Jonsson and JA Bertelsen %Computation of w a v e heigh ts due
to refraction and friction& J W aterw a ys Harb ours and Coastal Engineering Division
F ebruary pp
R Solomono and A Rap op ort %Connectivit y of random nets& Bull Math Bio
ph ysics
DC Sorensen and Ping T ak P eter T ang %On the orthogonalit y of eigen v ectors com
puted b y divideandconquer tec hniques& SIAM J Numer Anal no Decem ber

JJ Sylv ester %On the c hange of systems of indep enden tv ariables& Q J Pure and
Applied Maths
EC Titc hmarsh Theory of F unctions nd ed Oxford
EM W righ t %The linear dierencedieren tial equation with constan t co ecien ts&
Pro c Ro y al So c Edin burgh A
EM W righ t %A nonlinear dierencedieren tial equation& J f ur reine und ange
w andte Mathematik
EM W righ t%Solution of the equation ze
z
a & Pro c Ro y Soc Edin burgh A

EM W righ t%The n um b er of connected sparsely edged graphs& J Graph Theory

App endix Biographical Notes
Johann Heinric h Lam b ert w as b orn in Mulhouse on August and died in
Berlin on Septem b er His scien tic in terests w ere remark ably broad The self
educated son of a tailor he pro duced fundamen tally imp ortan tw orkinn um b er theory
geometry statistics astronom y meteorology h ygrometry p yrometry optics cosmology
and philosoph y He w ork ed on the parallel p ostulate and also in tro duced the mo dern
notation for the h yp erb olic functions It is said that when F rederic k the Great ask ed him
in whic h science he w as most procien t Lam b ert immo destly replied %All& Lam bert

32. On the Lam b ert W function
w as the rst to pro v e the irrationalit yof W e nd it a remark able coincidence that the
curv es dening the branc h cuts of the Lam bert W function whic h con tain the Quadratix of
Hippias can b e used not only to square the circlewhic h b ypro ving irrational Lam bert
w en t a long w a yto w ards pro ving w as imp ossible b y compass and straigh tedgebut also
to trisect a giv en angle
The title of Eulers pap er can b e translated as On a series of Lam b ert and some
of its signican t prop erties Indeed Euler refers to Lam b ert in this pap er as %acutissimi
ingenii Lam b ertus& whic hma y b e freely translated as the ingenious engineer Lam b ert
Although Euler w as Swiss he eviden tly did not read Acta Helv etica regularly b ecause
Lam b erts form ulae came as a big surprise when he learned of them in whic hw as
the y ear Lam b ert w en t from Z uric h to Berlin A letter from Euler to Goldbac h dated
Marc h describ es his excitemen t
In Lam b ert states for the rst time the generalization of his series that giv es
po w ers of the ro ot instead of just the ro ot itself this series is equation here Lam bert
sa ys that Acta Helv etica had cut out the pro of of his simpler form ula and he had lost his
notes But while rederiving the form ula for Euler he found a simpler pro of of a more general
result Then he sa ys Euler w ork ed out a generalization from trinomials to quadrinomials
but he Lam b ert already knew ho w to handle p olynomials and to deriv e a precursor of
Lagranges in v ersion theorem Lam b ert wrote Euler a cordial letter on Octob er
hoping that Euler w ould regain his sigh t after an op eration he explains in this letter ho w
his trinomial metho d extends to series rev ersion In the index to Eulers corresp ondence
Op era Omnia series v olume page there is a note that A J Lexell replied to
this letter
Finally in an eloge near the b eginning of the t w ov olumes of Lam b erts mathematical
pap ers published in Z uric h in and w e nd that Lam b ert had dreams of building
a mac hine to do sym b olic calculation while P ascals mac hine merely did arithmetic Th us
his wishes an ticipated those of Lady Ada Lo v elace b y roughly one cen tury and the actualit y
of sym b olic computation systems b y roughly t w o