Printer Friendly

Coefficients of algebraic functions: formulae and asymptotics.

1 Introduction

The theory of context-free grammars and its relationship with combinatorics was initiated by the article of Noam Chomsky and Marcel-Paul Schutzenberger in 1963 [CS63], where it is shown that the generating function of the number of words generated by a non ambiguous context-free grammar is algebraic. Since then, there has been much use of algebraic functions in combinatorics, see e.g. [Sta99, BM06, FS09].

Quite often, they come from a tree-like structure (dissections of polygons: a result going back to Euler in 1751, one of the founding problems of analytic combinatorics!), or from a grammar description (polyominoes [DV84], lattice paths [Duc00]), or from the "diagonal" of rational functions [BH12], or as solution of functional equations (solvable by the kernel method and its variants, e.g. for avoiding-pattern permutations [Knu98]). Their asymptotics is crucial for establishing (inherent) ambiguity of context-free languages [Fla87], for the analysis of lattice paths [BF02], walks with an infinite set of jumps [Ban02] (which are thus not coded by a grammar on a finite alphabet), or planar maps [BFSS01].

Plan of this article:

* In Section 2, we give a few definitions, mostly illustrating the link between context-free grammars, solutions of positive algebraic systems and N-algebraic functions.

* In Section 3, we survey some closure properties of algebraic functions and give a closed form for their coefficients.

* In Section 4, we state and sketch a proof of our main theorem on the possible asymptotics of algebraic functions (associated to a context-free grammar with positive weights).

* We end with a conclusion pinpointing some extensions (limit laws, algorithmic considerations, extension to infinite systems, or systems involving entire functions).

2 Definitions: N-algebraic functions, context-free grammars and pushdown automata

For the notions of automata, pushdown automata, context-free grammars, we refer to the survey [PS09]. Another excellent compendium on the subject is the handbook of formal languages [RS97] and the Lothaire trilogy. We now consider S-algebraic functions, that is, a function [y.sub.1](z) that is solution of a System (i):

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

where each polynomial [P.sub.i] has coefficients in any set S (in this article, we consider S = N, Z, [Q.sub.+], or [R.sub.+]). We restrict (with only minor loss of generality) to systems satisfying: [P.sub.i](0, ..., 0) = 0, each [P.sub.i] is involving at least one [y.sub.j], the coefficient of [y.sub.j] in [P.sub.i](0, ..., 0, [y.sub.j], 0 ..., 0) is 0, and there is at least one [P.sub.i](z, 0, ..., 0) which is not 0. Such systems are called "well defined" (or "proper" or "well founded" or "well posed", see [BD13]), and correspond to proper context-free grammars for which one has no "infinite chainrules". On the set of power series, d(F(z),G(z)): = [2.sup.-val(F(z)-G(z))] is an ultrametric distance, this distance extends to vectors of functions, and allows to apply the Banach fixed- point theorem: it implies existence and uniqueness of a solution of the system as a d-tuple of power series ([y.sub.1,] ..., [y.sub.d]) (and they are analytic functions in 0, as we already know that they are algebraic by nature). A common mistake is to forget that there exist situations for which the system (1) can admit several solutions as power series for [y.sub.1] (nota bene: there is no contradiction with our previous claim, which is considering tuples). By elimination theory (resultant or Grobner bases), S-algebraic functions are algebraic functions.

We give now few trivial/folklore results: N-algebraic functions correspond to generating functions of context-free grammars (this is often called the Chomsky-Schutzenberger theorem), or, equivalently, pushdown automata (via e.g. a Greibach normal form). Z-algebraic functions have no natural simple combinatorial structures associated to them, but they are the difference of two N-algebraic functions (as can be seen by introducing new unknowns splitting in two the previous ones, and writing the system involving positive coefficients on one side, and negative coefficients on the other side). They also play an important role as any algebraic generating with integer coefficients can be considered as a Z-algebraic function. An N-rational function is a function solution of a system (1) where each polynomial [P.sub.i] has coefficients in N and only linear terms in [y.sub.j]. Such functions correspond to generating functions of regular expressions or, equivalently, automata (a result essentially due to Kleene), and formula for their coefficients and their asymptotics are well-known, so we restrict from now on our attention to N- algebraic functions which are not rational.

3 Closed form for coefficient of algebraic function

A first natural question is how can we compute the n-th coefficient [f.sub.n] of an algebraic power series? An old theorem due to Abel states that algebraic functions are D-finite functions. A function F(z) is D-finite if it satisfies a differential equation with coefficients which are polynomials in z; equivalently, its coefficients [f.sub.n] satisfy a linear recurrence with coefficients which are polynomials in n. They are numerous algorithms to deal with this important class of functions, which includes a lot of special functions from physics, number theory and also combinatorics [Sta99]. The linear recurrence satisfied by [f.sub.n] allows to compute in linear time all the coefficients [f.sub.0], ..., [f.sub.n].

A less known fact is that these coefficients admit a closed form expression as a finite linear combination of weighted multinomial numbers. More precisely, one has the following theorem:

Theorem 1 (The Flajolet-Soria formula for coefficients of algebraic function) Let P(z, y) be a bivariate polynomial such that P(0,0) = 0, [P.sub.y](0,0) = 0 and P(z, 0) [not equal to] 0. Consider the algebraic function implicitly defined (ii) by f(z) = P(z, f(z)) and f(0) = 0. Then, the Taylor coefficients of f(z) are given by the following finite sum

[f.sub.n] = [summation over m [greater than or equal to] 1] [1/m] [[z.sup.n][y.sup.m-1]][P.sup.m](z,y). (2)

Accordingly, applying the multinomial theorem on [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] leads to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (3)

Proof: Consider y = P(z,y) as the perturbation at u =1 of the equation y = uP(z, y). Then, applying the Lagrange inversion formula (considering u as the main variable, and z as a fixed parameter) leads to the theorem. The second formula comes from the definition of the multinomial number, which is the number of ways to divide m objects into d groups, of cardinality [m.sub.1], ..., [m.sub.d] (with [m.sub.1] + ... + [m.sub.d] = m): [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. []

This Flajolet-Soria formula was first published in the habilitation thesis of Michele Soria in 1990 (and was later rediscovered independently by Gessel and Sokal).

As it is an alternating sign nested sum (indeed, as one reduces the set of positive equations describing our N-algebraic function to a single equation, the elimination process will lead to some non positive [a.sub.i]'s), it is not suitable to get general asymptotics from this formula, so we now proceed with another approach, which leads to a nice universal result for the critical exponents, but to the price of a rather technical proof.

4 Asymptotics for coefficients of algebraic function

A Puiseux series f = f(z) is a series of the form [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [k.sub.0] is an integer, N a positive integer. Let [k.sub.c]: = min{k [member of] Z - {0}|[a.sub.k] [not equal to] 0}, then [alpha] = [k.sub.c]/N is called the critical exponent (loosely speaking, [alpha] is the "first non zero exponent" appearing in the series, and if [z.sub.0] is not precised, it is by default the radius of convergence of f(z)). The theory of Puiseux expansions (or the theory of G-functions) implies that every algebraic function has a Puiseux series expansion and, thus, the critical exponents are rational numbers. The following proposition shows that all rational numbers are reached.

Theorem 2 (Q is the set of critical exponents) For every rational number [alpha] that is not a positive integer there exists an algebraic power series with positive integer coefficients for which its Puiseux expansion at the radius ofconvergence has exactly the critical exponent [alpha].

Proof: First consider F(z): = 1 - [(1 - [a.sup.2]z).sup.1/a], where a is any positive or negative integer. Accordingly, its coefficients are given by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The proof that the [f.sub.n] are positive integers was proven in [Lan00], via a link with a variant of Stirling numbers. We give here a simpler proof: first, via the Newton binomial theorem, the algebraic equation for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then, if one sees this equation as a fixed point equation (as a rewriting rule in the style of context-free grammars), it is obvious that the [f.sub.n]'s belong to Z. But as [f.sub.n+1] = a[an + (a - 1))[f.sub.n][f.sub.n] + 2], it is clear that the [f.sub.n]'s are finally positive integers. Finally, if b is any positive integer (such that b is not a multiple of a), considering G(z) = e[(zF(z) - 1).sup.b] (where e = 1 if a > b mod (2a) and e = - 1 elsewhere) leads to a series with integer coefficients (because of the integrality of the coefficients of F), positive coefficients (excepted a few of its first coefficients, for some monomials of degree less than b, as it comes from the Newton binomial expansion). Removing these negative coefficients gives a power series with only positive integer coefficients, with a Puiseux expansion of the form [(1 - [a.sup.2]z).sup.b/a]. []

One may then wonder if there is something stronger. For example, is it the case that for any radius of convergence, any critical exponent is possible? It happens not to be the case, as can be seen via a result of Fatou: a power series with integer coefficients and radius of convergence 1 is either rational or transcendental. However, one has the following neat generic behavior:

Theorem 3 (First main result: dyadic critical exponents for N-algebraic function) The critical exponent of an N-algebraic (or even [R.sub.+]-algebraic) function is either [2.sup.-k] for some k [greater than or equal to] 1 or -[m2.sup.-k] for some m [greater than or equal to] 1 and some k [greater than or equal to] 0.

If [f.sub.1](z) is aperiodic, that is, the radius of convergence [rho] is the only singularity on the circle of convergence [absolute value of z] = [rho] then the transfer principle of Flajolet and Odlyzko [FO90] implies that the coefficients [f.sub.n] = [[z.sup.n]] [f.sub.1](z) are asymptotically given by [f.sub.n] ~ A[[rho].sup.- n][n.sup.-1-[alpha]], when a is the critical exponent. In the general (non-aperiodic) case, we have to distinguish between residue classes but the asymptotics are still of the same form (when we restrict to these residue classes).

Theorem 4 (Second main result: asymptotics for coefficients of N-algebraic function) Let [f.sub.1](z) be the power series expansion of a well defined N-algebraic (or even [R.sub.+]- algebraic) system y = P(z, y). Then there is an integer M [greater than or equal to] 1 such that for every j [member of] {0,1, ..., M - 1} we either have [f.sub.n] = 0 for all (but finitely many) n with n [equivalent to] j mod M or there exist positive numbers [A.sub.j], [[rho].sub.j] and [[beta].sub.j] that is either -1 - [2.sup.-k] for some k [greater than or equal to] 1 or -1 + [m2.sup.-k] for some m [greater than or equal to] 1 and some k [greater than or equal to] 0 such

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

It is easy to see that all possible exponents actually appear.

Proposition 1 All the dyadic numbers of Theorem 3 appear as critical exponents of N-algebraic functions.

Proof: Let us first consider the system of equations [y.sub.1] = z([y.sub.2] + [y.sup.2.sub.1]), [y.sub.2] = z([y.sub.3] + [y.sup.2.sub.2]), [y.sub.3] = z(1 + [y.sup.2.sub.3]) has the following (explicit) solution

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Here [f.sub.1](z) has dominant singularity [(1 - 2z).sup.1/8] and it is clear that this example can be generalized: indeed, consider the system [y.sub.i] = z([y.sub.i+1] + [y.sup.2.sub.i]) for i = 1, ..., k - 1, and [y.sub.k] = z(1 + [y.sup.2.sub.k]), it leads to behavior [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for each k [greater than or equal to] 1. Now, taking the system of equations y = z([y.sup.m.sub.0] + y), [y.sub.0] = z(1 + 2[y.sub.0][y.sub.1]) leads to a behavior [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for each m [greater than or equal to] 1 and k [greater than or equal to] 0. See also [TB12] for another explicit combinatorial structure (a family of colored tree related to a critical composition) exhibiting all these critical exponents. []

On the other hand, we can use the result of Theorems 3 and 4 to identify classes that cannot be counted with the help of an N- (or [R.sub.+]-)algebraic system.

Proposition 2 Planar maps and several families of lattice paths (like Gessel walks) are not N-algebraic (i.e., they can not be generated by an unambiguous context-free grammar).

Proof: This comes as a nice consequence of our Theorem 3: all the families of planar maps of [BFSS01] cannot be generated by an unambiguous context-free grammar, because of their critical exponent 3/2. Also, the tables [BK09] of lattice paths in the quarter plane and their asymptotics (where some of the connection constants are guessed, but all the critical exponents are proved, and this is enough for our point) allow to prove that many sets of jumps are giving a non algebraic generating function, as they lead to a critical exponent which is a non-negative integer or involving 1/3. One very neat example are Gessel walks (their algebraicity were a nice surprise [BK10]), where the hypergeometric formula for their coefficients leads to an asymptotic in [4.sup.n]/[n.sup.2/3] not compatible with N-algebraicity. (iii) []

The critical exponents -1/4, -3/4, -5/4 which appear for walks on the slit plane [BMS02] and other lattice paths questions [BK10] are compatible with N-algebraicity, but these lattice paths are in fact not N-algebraic (it is possible to use Ogden's pumping lemma, to prove that these walks can be not generated by a context-free grammar). To get a constructive method to decide N- algebraicity (input: a polynomial equation, output: a context-free specification, whenever it exists) is a challenging task.

We now dedicate the two next subsections to the proof of Theorem 3. The proof of Theorem 4 is a considerable extension, where (at least) all singularities on the circle of convergence have to identified (see [BD13]). Due to space limitation we do not work out the latter proof in this extended abstract.

4.1 Dependency graph and auxiliary results

A main ingredient of the proof of Theorem 3 is the analysis of the dependency graph G of the system [y.sub.j] = [P.sub.j](z, [y.sub.1], ..., [y.sub.K]), 1 [less than or equal to] j [less than or equal to] K. The vertex set is {1, ..., K} and there is a directed edge from i to j if [P.sub.j] depends on [y.sub.i] (see Figure 1). If the dependency graph is strongly connected then we are in very special case of Theorem 3, for which one has one the following two situations (see [Drm97]):

Lemma 1 (rational singular behavior) Let y = A(z)y + B(z) a positive and well defined linear system of equations, where the dependency graph is strongly connected. Then the functions [f.sub.j](z) have a joint polar singularity p or order one as the dominant singularity, that is, the critical exponent is -1:

[f.sub.j](z)= [c.sub.j](z)/1 - z/[rho],

where [c.sub.j](z) is non-zero and analytic at z = [rho].

Lemma 2 (algebraic singular behavior) Let y = P(z, y) a positive and well defined polynomial system of equations that is not affine and where the dependency graph is strongly connected. Then the functions [f.sub.j](z) have a joint square-root singularity [rho] as the dominant singularity, that is, the critical exponent is 1/2:

[f.sub.j](z) = [g.sub.j](z) - [h.sub.j](z) [square root of (1 - [z/[rho]])],

where [c.sub.j](z) and [h.sub.j](z) are non-zero and analytic at z = [rho].

In the proof of Theorem 3 we will use in fact extended version of Lemma 1 and 2, where we introduce additional (polynomial) parameters, that is, we consider systems of functional equations of the form y = P(z, y, u), where P is now a polynomial in z, y, u with non-negative coefficients and where the dependency graph (with respect to y) is strongly connected. We also assume that u is strictly positive such that the spectral radius of the Jacobian [P.sub.y](0, f(0, u), u) is smaller than 1. (iv) Hence, we can consider the solution that we denote by f(z, u).

If we are in the affine setting (y = A(z, u)y + B(z, u)) it follows that y(z, u) has a polar singularity:

[f.sub.j](z, u) = [c.sub.j](z,u)/1 - z/[rho](u), (4)

where the functions [rho](u) and [c.sub.j](z, u) are non-zero and analytic. We have to distinguish two cases. If A(z, u) = A(z) does not depend on u then [rho](u) = [rho] is constant and the dependence from u just comes from B(z, u). Of course, if A(z, u) depends on u then [rho](u) is not constant. More precisely it depends exactly on those parameters that appear in A(z, u).

Similarly in the non-affine setting we obtain representations of the form

[f.sub.j](z, u)= [g.sub.j](z, u) - [h.sub.j](z, u) [square root of (1 - [z/[rho](u))], (5)

where the functions [rho](u), [g.sub.j](z, u), and [h.sub.j](z, u) are non-zero and analytic. In this case [rho](u) is always non-constant and depends on all parameters.

We denote by [D.sub.0] the set of positive real vectors u, for which r([P.sub.y] (0, f(z, 0), u)) < 1. It is easy to show that [rho](u) tends to 0 when u approaches the boundary of [D.sub.0].

4.2 Proof of our Theorem 3 on dyadic critical exponents

We fix some notation. Let G denote the dependency graph of the system and [??] the reduced dependency graph. Its vertices are the strongly connected components [C.sub.1], ... [C.sub.L] of G. We can then reduce the dependency graph to its components (see Figure 1).

Let [y.sub.1], ..., [y.sub.L] denote the system of vectors corresponding to the components [C.sub.1], ... [C.sub.L] and let [u.sub.1], ..., [u.sub.L] denote the input vectors related to these components. In the above example, we have [C.sub.1] = {1}, [C.sub.2] = {2}, [C.sub.3] = {3,4}, [C.sub.4] = {5, 6}, [y.sub.1] = [y.sub.1], [y.sub.2] = [y.sub.2], [y.sub.3] = ([y.sub.3], [y.sub.4]), [y.sub.4] = ([y.sub.5], [y.sub.6]), and [u.sub.1] = ([y.sub.2], [y.sub.5]), [u.sub.2] = ([y.sub.3], [y.sub.5]), [u.sub.3] = 0, [u.sub.4] = 0.

Finally, for each component [C.sub.l] we define the set [D.sub.l] of real vectors [u.sub.l] for which the spectral radius of the Jacobian of l-th subsystem evaluated at z = 0, [y.sub.l] = 0 is smaller than 1.

The first step we for each strongly connected component [C.sub.l] we solve the corresponding subsystem in the variables z and [u.sub.l] and obtain solutions f(z, [u.sub.l]), 1 [less than or equal to] l [less than or equal to] L. In our example these are the functions [f.sub.1](z, = [f.sub.1](z, [y.sub.2], [y.sub.5]), [f.sub.2](z, [u.sub.2]) = [f.sub.2](z, [y.sub.3], [y.sub.5]), [f.sub.3](z, [u.sub.3]) = ([f.sub.3](z), [f.sub.4](z)), [f.sub.4](z, [u.sub.4]) = ([f.sub.5](z), [f.sub.6](z)).

Since the dependency graph [??] is acyclic, there are components [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] with no input, that is, they corresponding functions [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] can be computed without any further information. By Lemma 1 and 2 they either have a polar singularity or a square-root singularity, that is, they are precisely of the types that are stated in Theorem 3.

Now we proceed inductively. We consider a strongly connected component [C.sub.l] with the function [F.sub.l](z, [u.sub.l]) and assume that all the functions [f.sub.j](z) that are contained in [u.sub.l] are already known and that their leading singularities of the two types stated in Theorem 3: the solutions [f.sub.j](z) have positive and finite radii of convergence [[rho].sub.j]. Furthermore, the singular behavior of [f.sub.j](z) around [[rho].sub.j] is either of algebraic type

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (6)

where [c.sub.j] [not equal to] 0 and where [k.sub.j] is a positive integer or of type

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (7)

where [d.sub.j] [not equal to] 0, [m.sub.j] are positive integers and [k.sub.j] are non-negative integers.

By the discussion following Lemma 1 and 2 it follows that functions contained in [f.sub.l](z, [u.sub.l]) have either a common polar singularity or a common square-root singularity [rho]([u.sub.l]).

We distinguish between three cases:

1. [f.sub.l](z, [u.sub.l]) comes from an affine system and is, thus, of the form (4) but the function [rho]([u.sub.l]) is constant.

2. [f.sub.l](z, [u.sub.l]) comes from an affine system and the function [rho]([u.sub.l]) is not constant.

3. [f.sub.l](z, [u.sub.l]) comes from an non-affine system and is, thus, of the form (5).

ad 1. The first case is very easy to handle. We just have to observe that c(z, [u.sub.l]) is a polynomial with non-negative coefficients in [u.sub.l] and that the class of admissible functions (that is, functions, where the critical exponent at the radius of convergence is either [2.sup.-k] for some k [greater than or equal to] 1 or -[m2.sup.-k] for some m [greater than or equal to] 1 and some k [greater than or equal to] 0) is closed under addition and multiplication. Hence the resulting function [f.sub.l](z) is of admissible form.

ad 2. In the second, we have to be more careful. Let [J'.sub.l] denote the set of j for which the function [rho]([u.sub.l]) really depends on.

First we discuss the denominator. For the sake of simplicity we will work with the difference [rho]([u.sub.j]) - z. Let [rho]' denote the smallest radius of convergence of the functions [f.sub.j](z), j [member of] [J'.sub.l]. Then we consider the difference [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. We have to consider the following cases for the denominator:

2.1. [delta]([rho]") = 0 for some [rho]" < [rho]' such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]:

First we note that [delta](z) has at most one positive zero since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is decreasing and z is increasing. Furthermore, the derivative satisfies [delta]'([rho]") > 0. Consequently, we have a simple zero [rho]" in the denominator.

2.2. We have [delta]([rho]') = 0 such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]:

In this case all functions [f.sub.j](z), j [member of] [J'.sub.l], with [[rho].sub.j] = [rho]' have to be of type (6). Consequently [delta](z) behaves like [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where c > 0 and [??] is the largest appearing [k.sub.j] (among those functions [f.sub.j](z) with [[rho].sub.j] = [rho]').

2.3. We have [delta]([rho]') > 0 such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]:

In this case, all functions [f.sub.j](z), j [member of] [J'.sub.l], with [[rho].sub.j] = [rho]' have to be (again) of type (6). Consequently [delta](z) behaves like [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [c.sub.0] > 0 and [c.sub.1] > 0 and [??] is the largest appearing [k.sub.j] (among those functions [f.sub.j](z) with [[rho].sub.j] = [rho]').

Finally, we have to discuss the numerator. Since the numerator c(z, [u.sub.j]) is just a polynomial in those [u.sub.j] for which j [not member of] [J'.sub.l], we can handle them as in the first case.

Summing up leads to a function [f.sub.j](z) that is either of type (6) or type (7).

ad 3. In the last case the function [f.sub.l](z, [u.sub.l]) has an representation of the form (5), where In this case [rho]([u.sub.l]) depends on all components of [u.sub.l]. As above we will study the behavior of the square-root [square root of ([rho]([u.sub.l]) - z)] instead of [square root of (1 - z/[rho]([u.sub.l]))] since the non-zero factor [square root of ([rho]([u.sub.l]))] can be put to h(z, [u.sub.l]).

Let [rho]' denote the smallest radius of convergence of the functions [f.sub.j](z) that correspond to [u.sub.l]. Here, we have to consider the following cases:

(3.1) [delta]([rho]") = 0 for some [rho]" < [rho]' such that ([f.sub.j]([rho]")) [member of] [D.sub.l]:

This means that [rho](([f.sub.j](z)) - z has a simple zero. By the Weierstrass preparation theorem we can, thus, represent this function as [rho](([f.sub.j](z)) - z = ([rho]" - z)H(z), where H(z) is non-zero and analytic at [rho]". Consequently, we observe that f(z) has a (simple) square-root singularity.

(3.2) We have [delta]([rho]') = 0 such that ([f.sub.j]([rho]")) [member of] [D.sub.l]:

In this case all functions [f.sub.j](z) with [[rho].sub.j] = [rho]' have to be of type (6). Hence the square-root of [delta](z) behaves as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where the corresponding k equals the largest appearing [k.sub.j] plus 1. Thus, f(z) is of type (6).

(3.3) We have [delta]([rho]') > 0 such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]:

In this case all functions [f.sub.j](z), with [[rho].sub.j] = [rho]' have to be (again) of type (6). Consequently the square-root of [delta](z) behaves like

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where [c.sub.0] > 0 and [c.sub.1] > 0 and [??] is the largest appearing [k.sub.j] (among those functions [f.sub.j](z) with [[rho].sub.j] = [rho]'). Hence, f(z) is of type (6).

This completes the induction proof of Theorem 3.

5 Conclusion

Now that we have a better picture of the behavior of algebraic coefficients, several extensions are possible and in the full version of this article [BD13], we say more on

* Algorithmic aspects: In order to automatize the asymptotics, one has to follow the right branch of the algebraic equations, this is doable by a disjunction of cases following the proof of our main theorem, coupled with an inspection of the associated spectral radii, this leads to a more "algebraic" approach suitable for computer algebra, shortcutting some numerical methods like e.g. the Flajolet-Salvy ACA (analytic continuation of algebraic) algorithm [FS09]. Giving an algorithm to decide in a constructive way if a function is N-algebraic would be nice. (This is doable for N-rational functions). With respect to the Pisot problem (i.e., deciding if one, or an infinite number of [f.sub.n] are zeroes), finding the best equivalent for N-algebraic functions of the Skolem- Lerch-Mahler theorem for N-rational functions is also a nice question. The binomial formula of Section 3 leads to many identities, simplifications of the corresponding nested sums are related to fascinating aspects of computer algebra.

* Extension to entire functions system: Most parts of the analysis of positive polynomial systems of equations also works for positive entire systems, however, one quickly gets "any possible asymptotic behavior" as illustrated by the system of equations [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], as it has the following explicit solution [f.sub.1](z) = exp (z/[square root of (1 - 4[z.sup.2])], which exhibits a non-algebraic behavior. However, adding the constraints [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] or if [P.sub.j] is affine in [y.sub.j] leads to the same conclusion as Theorem 3, with a smaller set of possible critical exponents (now, all [m.sub.j] = 1).

* Extension to infinite systems: If one considers systems having an infinite (but countable) number of unknowns [y.sub.i](z), it is proved in [Mor10] that strongly connected systems also lead to a square-root behavior. The fact that the limit law is Gaussian (as soon as a Jacobian operator associated to the system is compact) is proved in [DGM12]. When the conditions of strong connectivity or of compactness are dropped, a huge diversity of behavior appears, but it is however possible to give interesting subclasses having a regular behaviors.

* Extension to attributed grammars: Attribute grammars were introduced by Knuth. Many interesting parameters (like internal paths length in trees or area below lattice paths [BG06, Duc99, Ric09]) are well captured by such grammars. They lead to statistics with a mean which is no more linear. For a large class of strongly connected positive systems, it leads to the Airy function, and it is expected that it is also the case for a class of functional equations with non positive coefficients.

* Extension to limit laws: Philippe Flajolet called Borges' theorem the principle that motif statistics follow a Gaussian limit law [FS09]. They are however some technical conditions to ensure such a Gaussian behavior, like a strong connectivity of the associated system of equations; indeed, in the non strongly connected case, even very simple motifs in rational languages can then follow any limit law [BBPT12]. For algebraic systems, the strongly connected case leads to a Gaussian distribution, as illustrated by the limit law version of the Drmota-Lalley-Woods theorem [Drm97, BKP09]. In the full version of our article, we give an extension of this result to non strongly connected cases.

Acknowledgements

The authors acknowledge the financial support of the PHC Amadeus project, the ANR Magnum (ANR2010-BLAN-0204), and the FWF project SFB Algorithmic and Enumerative Combinatorics (F50).

References

[Ban02] Cyril Banderier. Limit laws for basic parameters of lattice paths with unbounded jumps.

In Mathematics and computer science, II (Versailles, 2002), Trends Math., pages 33-47. Birkhauser, Basel, 2002.

[BBPT12] Cyril Banderier, Olivier Bodini, Yann Ponty, and Hanane Tafat. On the diversity of pattern distributions in combinatorial systems. In proceedings of Analytic Algorithmics and Combinatorics (ANALCO'12), Kyoto, pages 107-116. SIAM, 2012.

[BD13] Cyril Banderier and Michael Drmota. Coefficients of algebraic functions: asymptotics and limit laws. 2013. Submitted.

[BF02] Cyril Banderier and Philippe Flajolet. Basic analytic combinatorics of directed lattice paths. Theoret. Comput. Sci., 281(1-2):37-80, 2002. Selected papers in honour of Maurice Nivat.

[BFSS01] Cyril Banderier, Philippe Flajolet, Gilles Schaeffer, and Michele Soria. Random maps, coalescing saddles, singularity analysis, and Airy phenomena. Random Structures Algorithms, 19(3-4):194-246, 2001.

[BG06] Cyril Banderier and Bernhard Gittenberger. Analytic combinatorics of lattice paths: enumeration and asymptotics for the area. In Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, pages 345-355. Assoc. Discrete Math. Theor. Comput. Sci., AG, 2006.

[BH12] Cyril Banderier and Pawel Hitczenko. Enumeration and asymptotics of restricted compositions having the same number of parts. Discrete Appl. Math., 160(18):2542-2554, 2012.

[BK09] Alin Bostan and Manuel Kauers. Automatic Classification of Restricted Lattice Walks. In proceedings of FPSAC'09, pages 201-215, 2009.

[BK10] Alin Bostan and Manuel Kauers. The complete generating function for Gessel walks is algebraic. Proc. Amer. Math. Soc., 138(9):3063-3078, 2010.

[BKP09] Cyril Banderier, Markus Kuba, and Alois Panholzer. Analysis of three graph parameters for random trees. Random Structures Algorithms, 35(1):42-69, 2009.

[BM06] Mireille Bousquet-Melou. Rational and algebraic series in combinatorial enumeration. In International Congress of Mathematicians. Vol. III, pages 789-826. Eur. Math. Soc., 2006.

[BMS02] Mireille Bousquet-Melou and Gilles Schaeffer. Walks on the slit plane. Probab. Theory Related Fields, 124(3):305-344, 2002.

[CS63] Noam Chomsky and Marcel-Paul Schutzenberger. The algebraic theory of context-free languages. In Computer programming and formal systems, pages 118-161. North-Holland, 1963.

[DGM12] Michael Drmota, Bernhard Gittenberger, and Johannes F. Morgenbesser. Infinite systems of functional equations and gaussian limiting distributions. In proceedings of AofA 12, pages 453-478. Discrete Math. Theor. Comput. Sci. Proc., AQ, 2012.

[Drm97] Michael Drmota. Systems of functional equations. Random Structures Algorithms, 10(1-2):103-124, 1997. Average-case analysis of algorithms (Dagstuhl, 1995).

[Duc99] Philippe Duchon. q-grammars and wall polyominoes. Ann. Comb., 3(2- 4):311-321, 1999. On combinatorics and statistical mechanics.

[Duc00] Philippe Duchon. On the enumeration and generation of generalized Dyck words. Discrete Math., 225(1-3):121-135, 2000. FPSAC'1998 (Toronto).

[DV84] Marie-Pierre Delest and Gerard Viennot. Algebraic languages and polyominoes enumeration. Theoret. Comput. Sci., 34(1-2):169-206, 1984.

[Fla87] Philippe Flajolet. Analytic models and ambiguity of context-free languages. Theoret. Comput. Sci., 49(2-3):283-309, 1987. ICALP'1985 (Nafplion).

[FO90] Philippe Flajolet and Andrew Odlyzko. Singularity analysis of generating functions. SIAM J. Discrete Math., 3(2):216-240, 1990.

[FS09] Philippe Flajolet and Robert Sedgewick. Analytic combinatorics. Cambridge University Press, 2009.

[Knu98] Donald E. Knuth. The art of computer programming. Vol. 2: Seminumerical algorithms. Addison-Wesley, 1998. (3rd edition, 2nd ed.: 1981, 1st ed.:1969).

[Lan00] Wolfdieter Lang. On generalizations of the Stirling number triangles. J. Integer Seq., 3(2):Ar ticle 00.2.4, 2000.

[Mor10] Johannes F. Morgenbesser. Square root singularities of infinite systems of functional equations. In proceedings of AofA'10, pages 513-525. Discrete Math. Theor. Comput. Sci. Proc., AM, 2010.

[PS09] Ion Petre and Arto Salomaa. Chapter 7: Algebraic systems and pushdown automata. In Handbook of weighted automata. Springer, 2009.

[Ric09] Christoph Richard. Limit distributions and scaling functions. In Polygons, polyominoes and polycubes, volume 775 of Lecture Notes in Phys., pages 247-299. Springer, Dordrecht, 2009.

[RS97] G. Rozenberg and A. Salomaa, editors. Handbook of formal languages. Springer, 1997.

[Sta99] Richard P. Stanley. Enumerative combinatorics. Vol. 2. Cambridge University Press, 1999.

[TB12] Hanane Tafat Bouzid. Combinatoire analytique des langages reguliers et algebriques. Phd thesis, Universite Paris-XIII, Dec 2012.

(i) In this article, we will often summarize the system (1) via the convenient short notation y = P(z, y), where bold fonts are used for vectors.

(ii) If an algebraic function f(z) with f(0) = 0 satisfies Q(z, f(z)) = 0, where Q(z, y) is a polynomial with Q(0,0) = 0 and [Q.sub.y](0, 0) [not equal to] 0 then f(z) satisfies the equation f(z) = P(z,f(z)), where P(z,y) = y - Q(y, z)/Qy (0, 0) satisfies P(0, 0) = 0 and [P.sub.y](0, 0) = 0.

(iii) The fact that critical exponents involving 1/3 were not possible was an informal conjecture in the community for years. We thank Philippe Flajolet, Mireille Bousquet-Melou and Gilles Schaeffer, who encouraged us to work on this question.

(iv) This condition assures that we have a unique analytic solution z [??] f(z, u) locally around z = 0.

Cyril Banderier (1) ([dagger]) Michael Drmota (2) ([double dagger])

(1) LIPN(UMR CNRS 7030), University Paris 13, France

(2) Institut fur Diskrete Mathematik und Geometrie, Technische Universitat Wien, Austria

We dedicate this article to the memory of Philippe Flajolet

([dagger]) http://lipn.univ-paris13.fr/~banderier

([double dagger]) http://www.dmg.tuwien.ac.at/drmota/
COPYRIGHT 2013 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2013 Gale, Cengage Learning. All rights reserved.

 
Article Details
Printer friendly Cite/link Email Feedback
Author:Banderier, Cyril; Drmota, Michael
Publication:DMTCS Proceedings
Article Type:Report
Geographic Code:4EUFR
Date:Jan 1, 2013
Words:6145
Previous Article:Antipode and convolution powers of the identity in graded connected Hopf algebras.
Next Article:Long cycle factorizations: bijective computation in the general case.
Topics:

Terms of use | Privacy policy | Copyright © 2018 Farlex, Inc. | Feedback | For webmasters