# Uniqueness of polynomial canonical representations.

Let P (z) and Q (y) be polynomials of the same degree k [greater
than or equal to] 1 in the complex variables z and y, respectively. In
this extended abstract we study the non-linear functional equation P(z)
= Q (y(z) ), where y(z) is restricted to be analytic in a neighborhood
of z = 0. We provide sufficient conditions to ensure that all the roots
of Q (y) are contained within the range of y(z) as well as to have y(z)
= z as the unique analytic solution of the non-linear equation. Our
results are motivated from uniqueness considerations of polynomial canonical representations of the phase or amplitude terms of oscillatory integrals encountered in the asymptotic analysis of the coefficients of
mixed powers and multivariable generating functions via saddle-point
methods. Uniqueness shall prove important for developing algorithms to
determine the Taylor coefficients of the terms appearing in these
representations. The uniqueness of Levinson's polynomial canonical
representations of analytic functions in several variables follows as a
corollary of our one-complex variables results.

Keywords: analytic functions, Airy phenomena, asymptotics, coalescing saddle-point method, multivariable generating functions, polynomial canonical representations

1 Introduction

Unless otherwise stated d [greater than equal to] 2 is a fixed integer and i := [square root of (-1)]. We use boldface notation to denote vectors in (C.sup.d]. We reserve the script 0 to refer to the zero vector. The script r is reserved for a vector with strictly positive real coordinates. We refer to r as a polyradius. The coordinates of a vector t are denoted ([t.sub.1], . . . , [t.sub.d]). We define t' := ([t.sub.l], . . . , [t.sub.d-1]), in particular, t = (t', [t.sub.d]). The notation [absolute value of t] < r means that |[t.sub.i]| < [r.sub.i] for all i. Similarly, |t| [less than or equal to] < r means that |[t.sub.i]| < [r.sub.i] for all i.

Problem description. A classical example of a polynomial canonical representation is the Weierstrass preparation theorem [Tay02] which asserts the following. If U(t) is a complex-valued analytic function in a neighborhood of t = 0 and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

then there exists a polyradius r and analytic functions V, [u.sub.0], . . . , [u.sub.k-1] such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for |t| < r. We refer to 1 as the order of vanishing of U about the origin with respect to the variable [t.sub.d]. The factor within the parenthesis above is called the Weierstrass polynomial of U about the origin and it will be denoted as P(t). It satisfies the following important property. For all |t'| < r' the polynomial equation in the variable [t.sub.d]: P(t', [t.sub.d) = 0, with |[t.sub.d]|< [r.sub.d], has exactly k solutions repeated according to their multiplicity. Since V(0) [not equal to] 0, and since the roots of a monic polynomial identify it uniquely, the factorization in (1) is unique.

The problem of whether U(t) itself can be represented as a polynomial with respect to a possibly auxiliary variable dates back to the investigations of Chester, Friedman and Ursell [CFU57] who studied this problem for the special case of d = 2. Later work by Levinson [Lev60b] provided a way to represent certain analytic functions of d = 2 complex variables in a canonical way as a polynomial in two auxiliary variables. More generally, for d [greater then or equal to] 2, Levinson proved the following [Lev60a]. If U(t) is like before then there exists a polyradius r and analytic functions [v.sub.0], . . . , [v.sub.k], x such that

U (t) = 1: [k. summation of [j=0]] [v.sub.j] (t') [{x(t)}.sup.j]

for |t| < r, with [v.sub.j] (0') = 0 for j < k , [v.sub.k] (0') [not equal to] 0, and x (t', 0) = 0 and [delta]x]/[delta][t.sub.d] (t', 0) = 1 = 1 for |t'| < r'.

Unlike the representation in (1), it is unclear that the representation in (2) is unique. Indeed, the issue of uniqueness was omitted in [Lev60a] and to the best of our knowledge it has not been addressed further. The main issue surrounding the uniqueness of this representation as well as other canonical representations is the introduction of auxiliary variables. Loosely speaking, the problem is how to certify in general the validity of the following implication

[MATHEMATICAL EXPRESS NOT REPRODUCIBLE IN ASCII]

under the assumption that x = x(t) = [t.sub.d] + O([t.sup.2.sub.d]) and y = y(t) = [t.sub.d] + O([t.sup.2.sub.d]) uniformly for all t sufficiently close to the origin. Clearly, to assert the uniqueness of the above factorization, it suffices to have x = y in some open neighborhood of the origin in [C.sup.d]. In fact, since x(t', [t.sub.d]) and y(t' [t.sub.d]) are--as functions of [t.sub.d]--locally invertible about the origin, we shall see at the end of Section 2 that the validity of the above implication is closely related to the uniqueness of y(z) = z as an analytic solution of the non-linear functional equation

[MATHEMATICAL EXPRESS NOT REPRODUCIBLE IN ASCII]

where R > 0 is a given radius and [z.sub.1], . . . , [z.sub.k] [member of ] C are fixed complex numbers such that |[z.sub.i]| < R.

There is one case where the uniqueness issue of the above equation can be addressed directly. If y(z) is an entire function i.e. R = [infinity] then, according to (3), [|y(z)/z|.sup.k] [right arrow ] 1 as |z| [right arrow] [infinity]. Since y(0) = 0, y(z)/z is abounded entire function. Hence, due to Lionville's theorem [Rud87], y(z)/z must be constant and therefore y(z) = z because y'(0) = 1. Unfortunately, the case with R = [infinity] is not of much use to address uniqueness issues of polynomial canonical representations because--almost always--they only apply locally.

Connections with mixed powers generating functions. Polynomial canonical representations are pivotal for analyzing the asymptotic behavior of oscillatory integrals [BH86]. Integrals of this type arise frequently in the context of asymptotic enumeration or the analysis of discrete random structures [PW05].

A mixed power generating function is a generating function of the form [PI].sup.d.sub.i=1] [{[f.sub.i] (z)]}.sup.ni], where the factors [f.sub.l], . . . , [f.sub.d] are complex-valued analytic functions near z = 0 a[n.sub.d] [n.sub.1], . . . , [n.sub.d] are nonnegative integers. The term of mixed power was introduced in [Lla06a] to emphasize the fact that one is usually interested in the coefficient of [z.sup.no] of [PI].sup.d.sub.i=1] [{[f.sub.i] (z)]}.sup.ni] as max {[n.sub.0], [n.sub.1].... , [n.sub.d] [right arrow] [infinity]. If one defines n := ([n.sub.1], . . . , [n.sub.d]), this is equivalent to request that [parallel]([n.sub.0], n) [parallel] [right arrow] [infinity] where [parallel]. [parallel] is any norm in [R.sup.1+d].

Generating functions of the above form occur naturally in the context of the Lagrange inversion formula [GJ04, Wil90] with d = 1. More recent applications include the case of d = 2, 3 to analyze the core size of various types of random planar maps [BFSSOI].

Coefficients of mixed powers generating functions have been considered in the literature for factors [f.sub.i] with nonnegative coefficients by Drmota [Drm94], for d = 1 and [n.sub.0], [n.sub.1] [right arrow] [infinity] at a comparable rate. Gardy [Gar95] considered the case of nonnegative coefficients for d [greater than or equal to] 1 with [n.sub.0] = [THETA]([n.sub.1]) or [n.sub.0] = 0([n.sub.1]) and [n.sub.i] = 0([n.sub.1]/[square root of [n.sub.0]] for i > 1. A geometrically based approach, in the lines used by Pemantle and Wilson [PW02, PW04], was proposed in [Lla06a] to handle factors [f.sub.i] with possibly negative Taylor coefficients. Given ([t.sub.0], t) [member of] [R.sup.1+d] with nonnegative coordinates and such that [parallel] ([t.sub.0], t) [parallel] = 1, say that x is a strictly minimal critical point associated with ([t.sub.0], t) provided that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for all z such that |z| = |x| and z [nor equal to] x. If the above conditions hold and some pathological behavior is ruled out, it follows from [Lla06a] that

for ([n.sub.0], n) such that ([n.sub.0], n)/[parallel] ([n.sub.0], n) [parallel] = ([t.sub.0], t), as [parallel]([n.sub.0], n) [parallel] [right arrow] [infinity]. The function F is a computable function that is continuous in its (d + 2) arguments however it is also analytic in the variable [theta]. For a fixed ([t.sub.0], t), it satisfies that F = [delta]F/[delta][theta] = 0 at [delta] = 0, and the real-part of F is minimized at [theta] = 0. Furthermore, the above expansion applies uniformly for all ([n.sub.0], n) / [parallel] ([n.sub.0], n) [parallel] [member of] T, provided that T is a compact set such that for all ([t.sub.0], t) [member of] T, x = x([t.sub.0], t) is a strictly critical point associated with ([t.sub.0], t) that depends continuously on ([t.sub.0], t). In particular, the asymptotic analysis of the above integral is amenable for the saddle-point method to obtain uniform asymptotic expansions for the coefficients in (4) for ([n.sub.0], n) [member of ] [parallel]([n.sub.0], n) JI . T, as [paralle] ([n.sub.0], n)[parallel] [right arrow] [infinity].

It is precisely for the asymptotic analysis of integrals such as the one occurring in (4) that polynomial canonical representations of the type in (2) play a crucial role. In particular, uniqueness of these representations shall prove important to determine the Taylor coefficients of the various terms and auxiliary variables occurring in these representations. This should aid in automatizing the extraction of asymptotic formulae for coefficients of mixed powers generating functions as well as multivariable generating functions.

The lack of analyticity of F in (4) with respect to the variable ([t.sub.0], t) can be over passed by thinking of F as a function of ([theta]; ([t.sub.0], t); x). The original function F can then be recovered by evaluating this new function at ([delta]; t; x([t.sub.0], t)). In order to apply the saddle-point method let 1 be the order of vanishing of F about (0; ([t.sub.0], t); x([t.sub.0], t)) with respect to the variable [theta]. Since F = [delta]F/[delta][theta] = 0 at points of this type, it follows from [Lla06b] that Levinson's polynomial cannonical representation takes the form

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

with y = 0 and [delta]y/[delta][theta] = 1 at points of the form (0; ([s.sub.0], s); x) that are near (0; ([t.sub.0], t); x([t.sub.0], t)). If k = 2 the above translates into having the integral appearing in (4) to be described asymptotically by the Gamma function. In particular, the integral is of order [[paralle]([n.sub.0], n) [parallel].sup.-1/2] as 11([n.sub.0], n)[parallel] [infinity]. On the other hand, if I = 3 the integral is described asymptotically by the Airy function. In this case the integral in (4) has typically an asymptotic series expansion which is a linear combination of terms of order ([[parallel]([n.sub.0], n)[parallel].sup.-l-1/3)] l[greater than or equal to]0 and also of order ([[parallel] ([n.sub.0],n)[parallel].sup.-l-2/3)]l[greater than equal to] 0. See [BH86, Lla03] to follow up on uniform asymptotics for integrals that involve the Gamma and Airy function.

The interested reader is referred to [L1a06a] for concrete applications of the above methodology with I = 2, 3. The reader is also referred to [BFSSOI] for a related yet more specialized discussion with k = 3. Although our motivation to study the uniqueness of polynomial canonical representations has been argued in the context of mixed powers generating functions, they also play a fundamental role in the extraction of asymptotics of multivariable generating functions. The reader is referred to [PW02, PW04, L1a06b] to follow up on this last remark.

2 Main results

We first introduce two one-complex variable results. Theorem 2.1 provides sufficient conditions to ensure that all the roots of a polynomial Q (y) are contained in the range of an analytic function y (z) when there exists another polynomial P(z), of the same degree as Q (y), such that P(z) = Q (y(z)) in a neighborhood of z = 0. Under an appropriate rescaling, this translates into having [[PI].supk.sub.i=1](z - [z.sub.i) = [[PI].sup.k.sub.i=1](y (z) - y ([z.sub.i])) , where 1 is the degree of P(z) and [z.sub.1], . . . , [z.sub.k] are the roots of P(z) repeated according to their multiplicity. Theorem 2.2 provides sufficient conditions in order to conclude from this that y(z) = z. Our main two theorems are refined versions of some of the results obtained by the author in his doctoral dissertation [Lla03]. These are used to show the uniqueness of Levinson's representation in (2).

Auxiliary results. In what follows, R > 0 is a given radius and we use the notation

D := {z [member of ] C:|z| < R},

H := {y: D [right arrow] C such that y is analytic}.

For 0 [less than or equal to] r < R, we define

[parallel] f [parallel] := sup |f (z)| = sup |f (z)|, |z| [greater than or equal to] r |z| = r

where the last identity is justified by the maximum modulus principle [Rud87].

Theorem 2.1 Let P and Q be polynomials of the same degree k [greater than or equal to] 1 and assume that D contains all the roots [z.sub.1], . . . , [z.sub.k] of P repeated according to their multiplicity. If y [member of] H-L is such that P(z) = Q(y(z)), for all z [member of] D, then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

Furthermore, if either of the conditions in (5) apply then there exists a constant q E C such that

Q(y) = q * [[PI].sup.k.sub.i-1] (Y - y([z.sub.i])) (6)

Theorem 2.2 For all P and r such that 0 [less than or equal to] 2p < r < R there exists a [delta] > 0 such that if [max.sub.i] |[z.sub.i]| [less than or equal to] p then y(z) = z is the only solution of the non-linear functional equation

[MATHEMATICAL EXPRESS NOT REPRODUCIBLE IN ASCII] (7)

that satisfies the condition [parallel] y(z) - z [parallel] r [less than or equal to] [delta].

Proof of uniqueness of Levinson's representation. We use the stated theorems to show the uniqueness of Levinson's polynomial canonical representation in (2). Thus consider U (t) analytic in a neighborhood t = 0 and assume that

U (t) = [summation].sup.k.sub.j=0] [v.sub.j] (t') * [S.sup.j] = [summation].sup.k.sub.j=0] [w.sub.j] (t') . [t.sup.j] (8)

where [v.sub.j] (0') - [w.sub.j] (0') - 0 for j < k , [v.sub.k] (0') [not equal to] 0, and s = t = 0 and [delta]s/[[delta]t.sub.d] = [delta]t/[[delta]t.sub.d]] = 1 at all points in the domain of s and t of the form (t', 0). We show that [v.sub.j] - [w.sub.j], for all j, and that s = t. For this consider the transformation [PHI](t) - (t', s(t)). Since [PHI](0) - 0 and the Jacobian matrix of [PHI] at 0 is lower-triangular with non-zero entries along the diagonal, the inverse mapping theorem [Tay02] implies that (D-1 is a well-defined analytic function in some open neighborhood of the origin in [C.sup.d]. Define V (t', z) := U ([[PHI]sup.-1](t', z)) and x = x (t', z) := t([[PHI].sup-1](t', z)). It follows from (8) that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (9)

Observe that x = 0 and [delta]x/[delta] z - 1 at all points in the domain of x of the form (t', 0). Furthermore, according to the first identity above, V vanishes to degree I about the origin in the variable z. In particular, the Weierstrass preparation theorem [Tay02] implies that, for all t' sufficiently close to 0', the roots of V (t', z) can be listed as [z.sub.1](t'), .... [z.sub.k] (t'), repeated according to their multiplicity. Since for t' sufficiently close to the origin the transformation z [right arrow] x(t', z) is a one-to-one transformation, we may use Theorem 2.1 in (9) to conclude that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Observe that, according to (9), x(0', z) = z * [([v.sub.k](0')/ [w.sub.k](0')).sup.1/k] provided that the appropriate branch for the k-th root is selected. With this choice of branch, introduce the auxiliary variable

y = y(t', z) = x(t', z) * [{[v.sub.k (t')/[w.sub.k] (t')}]sup.-1/k]

Notice that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for all t' sufficiently close to the origin in [C.sup.d-1] and z such that |z| I < R, where R > 0 is certain real parameter independent of t'. But observe that, according to the Weierstrass preparation theorem, if t' is sufficiently close to the origin then |[z.sub.j](t')| < R/4, for all j. On the other hand, since y(O', z) = z and y is uniformly continuos over compact subsets of its domain, it follows for r = 3R/4 that

lim [parallel]y (t', z) - [z[parallel].sub.r = 0. t' [arrow right]0'

Theorem 2.2 implies that y(t', z) = z, for all t' sufficiently close to the origin and all z such that |z| < R. In particular, x(t', z) = z * [([v.sub.k](t')/[w.sub.k](t'))sup.1/k]. Since [delta]x/[delta]z = 1 at all points in the domain of x of the form (t', 0), we conclude that x(t', z) = z. This in (9) implies that [v.sub.j] = [w.sub.j], for all j. Furthermore, since x(t', z) := t([[PHI].sup.-1](t', z)), with [PHI](t) = (t', s(t)), we find s = t. This shows that Levinson's polynomial canonical representations are unique. 0

received 23rd January 2008, revised soon, accepted tomorrow.

References

[BFSS01] C. Banderier, P. Flajolet, G. Schaeffer, and M. Soria. Random maps, coalescing saddles, singularity analysis, and airy phenomena. Random Structures and Algorithms 19(3-4), 194246,2001.

[BH86] N. Bleistein and R. Handelsman. Asymptotic expansion of integrals. Dover Publications, 1986.

[CFU57] C. Chester, B. Friedman, and F. Ursell. An extension of the method of steepest descents. Proc. Camb. Phil. Soc. 53, 599-611, 1957.

[Drm94] M. Drmota. A bivariate asymptotic expansion of coefficients of powers of generating functions. Europ. J. Combinatorics 15, 139-152, 1994.

[Gar95] D. Gardy. Some results on the asymptotic behavior of coefficients of large powers of functions. Discrete Mathematics, vol 139, 189-217, 1995.

[GJ04] I. P. Goulden and D. M. Jackson. Combinatorial enumeration. Dover Publications, 2004.

[Lev60a] N. Levinson. A canonical form for an analytic function of several variables at a critical point. Bulletin of the American Mathematical Society, vol 66, 68-69, 1960.

[Lev60b] N. Levinson. A polynomial canonical form for certain analytic functions of two variables at a critical point. Bulletin of the American Mathematical Society, vol 66, 366-368, 1960.

[L1a03] M. Lladser. Asymptotic enumeration via singularity analysis. Doctoral dissertation, Ohio State University, 2003.

[L1a06a] M. Lladser. Mixed powers of generating functions. In Proceedings of the fourth colloquium on mathematics and computer science, pages 171-182, Nancy, France, 2006. DMTCS.

[L1a06b] M. Lladser. Uniform formulae for coefficients of meromorphic functions in two variables. Part I. SIAM J. Discrete Math. 20, 811-828, 2006.

[PW02] R. Pemantle and M. Wilson. Asymptotics of multivariate sequences, part I: smooth points of the singular variety. J. Comb. Theory, Series A, vol. 97, 129-161, 2002.

[PW04] R. Pemantle and M Wilson. Asymptotics of multivariate sequences, part II: multiple points of the singular variety. Combinatorics, Probability and Computing 13, 735-761, 2004.

[PW05] R. Pemantle and M. Wilson. Twenty combinatorial examples of asymptotics derived from multivariate generating functions. Preprint, 2005.

[Rud87] W. Rudin. Real and complex analysis. McGraw-Hill series in Higher Mathematics, third edition, 1987.

[Tay02] J. Taylor. Several Complex variables with Connections to Algebraic Geometry and Lie Groups. Graduate Studies in Mathematics 46, 2002.

[Wi190] Herbert S. Wilf. Generatingfunctionology. Academic Press, 1990.

Manuel Lladser

University of Colorado, Department of Applied Mathematics, SCOT Room #232 /or PO Box 526 UCB, Boulder, CO 80309-0526, The United States

Keywords: analytic functions, Airy phenomena, asymptotics, coalescing saddle-point method, multivariable generating functions, polynomial canonical representations

1 Introduction

Unless otherwise stated d [greater than equal to] 2 is a fixed integer and i := [square root of (-1)]. We use boldface notation to denote vectors in (C.sup.d]. We reserve the script 0 to refer to the zero vector. The script r is reserved for a vector with strictly positive real coordinates. We refer to r as a polyradius. The coordinates of a vector t are denoted ([t.sub.1], . . . , [t.sub.d]). We define t' := ([t.sub.l], . . . , [t.sub.d-1]), in particular, t = (t', [t.sub.d]). The notation [absolute value of t] < r means that |[t.sub.i]| < [r.sub.i] for all i. Similarly, |t| [less than or equal to] < r means that |[t.sub.i]| < [r.sub.i] for all i.

Problem description. A classical example of a polynomial canonical representation is the Weierstrass preparation theorem [Tay02] which asserts the following. If U(t) is a complex-valued analytic function in a neighborhood of t = 0 and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

then there exists a polyradius r and analytic functions V, [u.sub.0], . . . , [u.sub.k-1] such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for |t| < r. We refer to 1 as the order of vanishing of U about the origin with respect to the variable [t.sub.d]. The factor within the parenthesis above is called the Weierstrass polynomial of U about the origin and it will be denoted as P(t). It satisfies the following important property. For all |t'| < r' the polynomial equation in the variable [t.sub.d]: P(t', [t.sub.d) = 0, with |[t.sub.d]|< [r.sub.d], has exactly k solutions repeated according to their multiplicity. Since V(0) [not equal to] 0, and since the roots of a monic polynomial identify it uniquely, the factorization in (1) is unique.

The problem of whether U(t) itself can be represented as a polynomial with respect to a possibly auxiliary variable dates back to the investigations of Chester, Friedman and Ursell [CFU57] who studied this problem for the special case of d = 2. Later work by Levinson [Lev60b] provided a way to represent certain analytic functions of d = 2 complex variables in a canonical way as a polynomial in two auxiliary variables. More generally, for d [greater then or equal to] 2, Levinson proved the following [Lev60a]. If U(t) is like before then there exists a polyradius r and analytic functions [v.sub.0], . . . , [v.sub.k], x such that

U (t) = 1: [k. summation of [j=0]] [v.sub.j] (t') [{x(t)}.sup.j]

for |t| < r, with [v.sub.j] (0') = 0 for j < k , [v.sub.k] (0') [not equal to] 0, and x (t', 0) = 0 and [delta]x]/[delta][t.sub.d] (t', 0) = 1 = 1 for |t'| < r'.

Unlike the representation in (1), it is unclear that the representation in (2) is unique. Indeed, the issue of uniqueness was omitted in [Lev60a] and to the best of our knowledge it has not been addressed further. The main issue surrounding the uniqueness of this representation as well as other canonical representations is the introduction of auxiliary variables. Loosely speaking, the problem is how to certify in general the validity of the following implication

[MATHEMATICAL EXPRESS NOT REPRODUCIBLE IN ASCII]

under the assumption that x = x(t) = [t.sub.d] + O([t.sup.2.sub.d]) and y = y(t) = [t.sub.d] + O([t.sup.2.sub.d]) uniformly for all t sufficiently close to the origin. Clearly, to assert the uniqueness of the above factorization, it suffices to have x = y in some open neighborhood of the origin in [C.sup.d]. In fact, since x(t', [t.sub.d]) and y(t' [t.sub.d]) are--as functions of [t.sub.d]--locally invertible about the origin, we shall see at the end of Section 2 that the validity of the above implication is closely related to the uniqueness of y(z) = z as an analytic solution of the non-linear functional equation

[MATHEMATICAL EXPRESS NOT REPRODUCIBLE IN ASCII]

where R > 0 is a given radius and [z.sub.1], . . . , [z.sub.k] [member of ] C are fixed complex numbers such that |[z.sub.i]| < R.

There is one case where the uniqueness issue of the above equation can be addressed directly. If y(z) is an entire function i.e. R = [infinity] then, according to (3), [|y(z)/z|.sup.k] [right arrow ] 1 as |z| [right arrow] [infinity]. Since y(0) = 0, y(z)/z is abounded entire function. Hence, due to Lionville's theorem [Rud87], y(z)/z must be constant and therefore y(z) = z because y'(0) = 1. Unfortunately, the case with R = [infinity] is not of much use to address uniqueness issues of polynomial canonical representations because--almost always--they only apply locally.

Connections with mixed powers generating functions. Polynomial canonical representations are pivotal for analyzing the asymptotic behavior of oscillatory integrals [BH86]. Integrals of this type arise frequently in the context of asymptotic enumeration or the analysis of discrete random structures [PW05].

A mixed power generating function is a generating function of the form [PI].sup.d.sub.i=1] [{[f.sub.i] (z)]}.sup.ni], where the factors [f.sub.l], . . . , [f.sub.d] are complex-valued analytic functions near z = 0 a[n.sub.d] [n.sub.1], . . . , [n.sub.d] are nonnegative integers. The term of mixed power was introduced in [Lla06a] to emphasize the fact that one is usually interested in the coefficient of [z.sup.no] of [PI].sup.d.sub.i=1] [{[f.sub.i] (z)]}.sup.ni] as max {[n.sub.0], [n.sub.1].... , [n.sub.d] [right arrow] [infinity]. If one defines n := ([n.sub.1], . . . , [n.sub.d]), this is equivalent to request that [parallel]([n.sub.0], n) [parallel] [right arrow] [infinity] where [parallel]. [parallel] is any norm in [R.sup.1+d].

Generating functions of the above form occur naturally in the context of the Lagrange inversion formula [GJ04, Wil90] with d = 1. More recent applications include the case of d = 2, 3 to analyze the core size of various types of random planar maps [BFSSOI].

Coefficients of mixed powers generating functions have been considered in the literature for factors [f.sub.i] with nonnegative coefficients by Drmota [Drm94], for d = 1 and [n.sub.0], [n.sub.1] [right arrow] [infinity] at a comparable rate. Gardy [Gar95] considered the case of nonnegative coefficients for d [greater than or equal to] 1 with [n.sub.0] = [THETA]([n.sub.1]) or [n.sub.0] = 0([n.sub.1]) and [n.sub.i] = 0([n.sub.1]/[square root of [n.sub.0]] for i > 1. A geometrically based approach, in the lines used by Pemantle and Wilson [PW02, PW04], was proposed in [Lla06a] to handle factors [f.sub.i] with possibly negative Taylor coefficients. Given ([t.sub.0], t) [member of] [R.sup.1+d] with nonnegative coordinates and such that [parallel] ([t.sub.0], t) [parallel] = 1, say that x is a strictly minimal critical point associated with ([t.sub.0], t) provided that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for all z such that |z| = |x| and z [nor equal to] x. If the above conditions hold and some pathological behavior is ruled out, it follows from [Lla06a] that

for ([n.sub.0], n) such that ([n.sub.0], n)/[parallel] ([n.sub.0], n) [parallel] = ([t.sub.0], t), as [parallel]([n.sub.0], n) [parallel] [right arrow] [infinity]. The function F is a computable function that is continuous in its (d + 2) arguments however it is also analytic in the variable [theta]. For a fixed ([t.sub.0], t), it satisfies that F = [delta]F/[delta][theta] = 0 at [delta] = 0, and the real-part of F is minimized at [theta] = 0. Furthermore, the above expansion applies uniformly for all ([n.sub.0], n) / [parallel] ([n.sub.0], n) [parallel] [member of] T, provided that T is a compact set such that for all ([t.sub.0], t) [member of] T, x = x([t.sub.0], t) is a strictly critical point associated with ([t.sub.0], t) that depends continuously on ([t.sub.0], t). In particular, the asymptotic analysis of the above integral is amenable for the saddle-point method to obtain uniform asymptotic expansions for the coefficients in (4) for ([n.sub.0], n) [member of ] [parallel]([n.sub.0], n) JI . T, as [paralle] ([n.sub.0], n)[parallel] [right arrow] [infinity].

It is precisely for the asymptotic analysis of integrals such as the one occurring in (4) that polynomial canonical representations of the type in (2) play a crucial role. In particular, uniqueness of these representations shall prove important to determine the Taylor coefficients of the various terms and auxiliary variables occurring in these representations. This should aid in automatizing the extraction of asymptotic formulae for coefficients of mixed powers generating functions as well as multivariable generating functions.

The lack of analyticity of F in (4) with respect to the variable ([t.sub.0], t) can be over passed by thinking of F as a function of ([theta]; ([t.sub.0], t); x). The original function F can then be recovered by evaluating this new function at ([delta]; t; x([t.sub.0], t)). In order to apply the saddle-point method let 1 be the order of vanishing of F about (0; ([t.sub.0], t); x([t.sub.0], t)) with respect to the variable [theta]. Since F = [delta]F/[delta][theta] = 0 at points of this type, it follows from [Lla06b] that Levinson's polynomial cannonical representation takes the form

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

with y = 0 and [delta]y/[delta][theta] = 1 at points of the form (0; ([s.sub.0], s); x) that are near (0; ([t.sub.0], t); x([t.sub.0], t)). If k = 2 the above translates into having the integral appearing in (4) to be described asymptotically by the Gamma function. In particular, the integral is of order [[paralle]([n.sub.0], n) [parallel].sup.-1/2] as 11([n.sub.0], n)[parallel] [infinity]. On the other hand, if I = 3 the integral is described asymptotically by the Airy function. In this case the integral in (4) has typically an asymptotic series expansion which is a linear combination of terms of order ([[parallel]([n.sub.0], n)[parallel].sup.-l-1/3)] l[greater than or equal to]0 and also of order ([[parallel] ([n.sub.0],n)[parallel].sup.-l-2/3)]l[greater than equal to] 0. See [BH86, Lla03] to follow up on uniform asymptotics for integrals that involve the Gamma and Airy function.

The interested reader is referred to [L1a06a] for concrete applications of the above methodology with I = 2, 3. The reader is also referred to [BFSSOI] for a related yet more specialized discussion with k = 3. Although our motivation to study the uniqueness of polynomial canonical representations has been argued in the context of mixed powers generating functions, they also play a fundamental role in the extraction of asymptotics of multivariable generating functions. The reader is referred to [PW02, PW04, L1a06b] to follow up on this last remark.

2 Main results

We first introduce two one-complex variable results. Theorem 2.1 provides sufficient conditions to ensure that all the roots of a polynomial Q (y) are contained in the range of an analytic function y (z) when there exists another polynomial P(z), of the same degree as Q (y), such that P(z) = Q (y(z)) in a neighborhood of z = 0. Under an appropriate rescaling, this translates into having [[PI].supk.sub.i=1](z - [z.sub.i) = [[PI].sup.k.sub.i=1](y (z) - y ([z.sub.i])) , where 1 is the degree of P(z) and [z.sub.1], . . . , [z.sub.k] are the roots of P(z) repeated according to their multiplicity. Theorem 2.2 provides sufficient conditions in order to conclude from this that y(z) = z. Our main two theorems are refined versions of some of the results obtained by the author in his doctoral dissertation [Lla03]. These are used to show the uniqueness of Levinson's representation in (2).

Auxiliary results. In what follows, R > 0 is a given radius and we use the notation

D := {z [member of ] C:|z| < R},

H := {y: D [right arrow] C such that y is analytic}.

For 0 [less than or equal to] r < R, we define

[parallel] f [parallel] := sup |f (z)| = sup |f (z)|, |z| [greater than or equal to] r |z| = r

where the last identity is justified by the maximum modulus principle [Rud87].

Theorem 2.1 Let P and Q be polynomials of the same degree k [greater than or equal to] 1 and assume that D contains all the roots [z.sub.1], . . . , [z.sub.k] of P repeated according to their multiplicity. If y [member of] H-L is such that P(z) = Q(y(z)), for all z [member of] D, then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

Furthermore, if either of the conditions in (5) apply then there exists a constant q E C such that

Q(y) = q * [[PI].sup.k.sub.i-1] (Y - y([z.sub.i])) (6)

Theorem 2.2 For all P and r such that 0 [less than or equal to] 2p < r < R there exists a [delta] > 0 such that if [max.sub.i] |[z.sub.i]| [less than or equal to] p then y(z) = z is the only solution of the non-linear functional equation

[MATHEMATICAL EXPRESS NOT REPRODUCIBLE IN ASCII] (7)

that satisfies the condition [parallel] y(z) - z [parallel] r [less than or equal to] [delta].

Proof of uniqueness of Levinson's representation. We use the stated theorems to show the uniqueness of Levinson's polynomial canonical representation in (2). Thus consider U (t) analytic in a neighborhood t = 0 and assume that

U (t) = [summation].sup.k.sub.j=0] [v.sub.j] (t') * [S.sup.j] = [summation].sup.k.sub.j=0] [w.sub.j] (t') . [t.sup.j] (8)

where [v.sub.j] (0') - [w.sub.j] (0') - 0 for j < k , [v.sub.k] (0') [not equal to] 0, and s = t = 0 and [delta]s/[[delta]t.sub.d] = [delta]t/[[delta]t.sub.d]] = 1 at all points in the domain of s and t of the form (t', 0). We show that [v.sub.j] - [w.sub.j], for all j, and that s = t. For this consider the transformation [PHI](t) - (t', s(t)). Since [PHI](0) - 0 and the Jacobian matrix of [PHI] at 0 is lower-triangular with non-zero entries along the diagonal, the inverse mapping theorem [Tay02] implies that (D-1 is a well-defined analytic function in some open neighborhood of the origin in [C.sup.d]. Define V (t', z) := U ([[PHI]sup.-1](t', z)) and x = x (t', z) := t([[PHI].sup-1](t', z)). It follows from (8) that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (9)

Observe that x = 0 and [delta]x/[delta] z - 1 at all points in the domain of x of the form (t', 0). Furthermore, according to the first identity above, V vanishes to degree I about the origin in the variable z. In particular, the Weierstrass preparation theorem [Tay02] implies that, for all t' sufficiently close to 0', the roots of V (t', z) can be listed as [z.sub.1](t'), .... [z.sub.k] (t'), repeated according to their multiplicity. Since for t' sufficiently close to the origin the transformation z [right arrow] x(t', z) is a one-to-one transformation, we may use Theorem 2.1 in (9) to conclude that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Observe that, according to (9), x(0', z) = z * [([v.sub.k](0')/ [w.sub.k](0')).sup.1/k] provided that the appropriate branch for the k-th root is selected. With this choice of branch, introduce the auxiliary variable

y = y(t', z) = x(t', z) * [{[v.sub.k (t')/[w.sub.k] (t')}]sup.-1/k]

Notice that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for all t' sufficiently close to the origin in [C.sup.d-1] and z such that |z| I < R, where R > 0 is certain real parameter independent of t'. But observe that, according to the Weierstrass preparation theorem, if t' is sufficiently close to the origin then |[z.sub.j](t')| < R/4, for all j. On the other hand, since y(O', z) = z and y is uniformly continuos over compact subsets of its domain, it follows for r = 3R/4 that

lim [parallel]y (t', z) - [z[parallel].sub.r = 0. t' [arrow right]0'

Theorem 2.2 implies that y(t', z) = z, for all t' sufficiently close to the origin and all z such that |z| < R. In particular, x(t', z) = z * [([v.sub.k](t')/[w.sub.k](t'))sup.1/k]. Since [delta]x/[delta]z = 1 at all points in the domain of x of the form (t', 0), we conclude that x(t', z) = z. This in (9) implies that [v.sub.j] = [w.sub.j], for all j. Furthermore, since x(t', z) := t([[PHI].sup.-1](t', z)), with [PHI](t) = (t', s(t)), we find s = t. This shows that Levinson's polynomial canonical representations are unique. 0

received 23rd January 2008, revised soon, accepted tomorrow.

References

[BFSS01] C. Banderier, P. Flajolet, G. Schaeffer, and M. Soria. Random maps, coalescing saddles, singularity analysis, and airy phenomena. Random Structures and Algorithms 19(3-4), 194246,2001.

[BH86] N. Bleistein and R. Handelsman. Asymptotic expansion of integrals. Dover Publications, 1986.

[CFU57] C. Chester, B. Friedman, and F. Ursell. An extension of the method of steepest descents. Proc. Camb. Phil. Soc. 53, 599-611, 1957.

[Drm94] M. Drmota. A bivariate asymptotic expansion of coefficients of powers of generating functions. Europ. J. Combinatorics 15, 139-152, 1994.

[Gar95] D. Gardy. Some results on the asymptotic behavior of coefficients of large powers of functions. Discrete Mathematics, vol 139, 189-217, 1995.

[GJ04] I. P. Goulden and D. M. Jackson. Combinatorial enumeration. Dover Publications, 2004.

[Lev60a] N. Levinson. A canonical form for an analytic function of several variables at a critical point. Bulletin of the American Mathematical Society, vol 66, 68-69, 1960.

[Lev60b] N. Levinson. A polynomial canonical form for certain analytic functions of two variables at a critical point. Bulletin of the American Mathematical Society, vol 66, 366-368, 1960.

[L1a03] M. Lladser. Asymptotic enumeration via singularity analysis. Doctoral dissertation, Ohio State University, 2003.

[L1a06a] M. Lladser. Mixed powers of generating functions. In Proceedings of the fourth colloquium on mathematics and computer science, pages 171-182, Nancy, France, 2006. DMTCS.

[L1a06b] M. Lladser. Uniform formulae for coefficients of meromorphic functions in two variables. Part I. SIAM J. Discrete Math. 20, 811-828, 2006.

[PW02] R. Pemantle and M. Wilson. Asymptotics of multivariate sequences, part I: smooth points of the singular variety. J. Comb. Theory, Series A, vol. 97, 129-161, 2002.

[PW04] R. Pemantle and M Wilson. Asymptotics of multivariate sequences, part II: multiple points of the singular variety. Combinatorics, Probability and Computing 13, 735-761, 2004.

[PW05] R. Pemantle and M. Wilson. Twenty combinatorial examples of asymptotics derived from multivariate generating functions. Preprint, 2005.

[Rud87] W. Rudin. Real and complex analysis. McGraw-Hill series in Higher Mathematics, third edition, 1987.

[Tay02] J. Taylor. Several Complex variables with Connections to Algebraic Geometry and Lie Groups. Graduate Studies in Mathematics 46, 2002.

[Wi190] Herbert S. Wilf. Generatingfunctionology. Academic Press, 1990.

Manuel Lladser

University of Colorado, Department of Applied Mathematics, SCOT Room #232 /or PO Box 526 UCB, Boulder, CO 80309-0526, The United States

Printer friendly Cite/link Email Feedback | |

Author: | Lladser, Manuel |
---|---|

Publication: | DMTCS Proceedings |

Date: | Jan 1, 2007 |

Words: | 3480 |

Previous Article: | Distributional asymptotics in the analysis of algorithms: periodicities and discretization. |

Next Article: | Online bandwidth packing with symmetric distribution. |