Solving Discrete Initial- and Boundary-Value Problems

Solving Discrete Initial- and Boundary-Value Problems

Marko Petkovsek

University of Ljubljana

Algorithms Seminar

October 4, 1999

[summary by Cyril Banderier]

A properly typeset version of this document is available in postscript and in pdf.

If some fonts do not look right on your screen, this might be fixed by configuring your browser (see the documentation here).

Abstract

Multivariate linear recurrences appear in such diverse fields of mathematics as combinatorics, probability theory, and numerical resolution of partial differential equations. Whereas in the univariate case the solution of a constant-coefficient recurrence always has a rational generating function, this is no longer true in the multivariate case where this generating function can be non-rational, non-algebraic, and even non-D-finite. Nevertheless, there are important cases where the solution can be computed exactly in terms of algebraic functions. Examples include many lattice-path problems such as the enumerations of Dyck, Motzkin, and Schroeder paths, determining the cardinality of various free algebras, and (in some cases) the enumeration of permutations with a forbidden pattern. This is joint work by Marko Petkovsek and Mireille Bousquet-Mélou (CNRS, Université de Bordeaux I).

1 Multivariate Linear Recurrences

Combinatorics are often synonymous of recurrences; whereas a quite impressive apparatus is available for univariate recurrences, multivariate recurrences are always a strange and mysterious world. Whereas a linear recurrence with constant coefficients necessarily leads to a rational generating function in one variable, this is no longer true in several variables (even with very regular boundary conditions). In fact, the set of multivariate generating functions with such a recurrence intersects almost all of the well-known classes of functions. Here are two examples leading to two kinds of generating functions.

A rational generating function: the chess king recurrence

On the square lattice, one performs a walk, beginning at (0,0), made of a sequence of jumps (1,0), (1,1) or (0,1). Let a_n,k be the number of ways to reach (n,k). Thus, one has the relation a_n,0=a_0,k=1 (for n,k³ 0) and the recurrence a_n,k=a_n-1,k+a_n,k-1+a_n-1,k-1 (for n,k³1). Then, the generating function is

F(x,y)=

n,k=0

a_n,k xⁿ y^k=

1-(x+y+xy)

Of course there is an explicit formula for the coefficients (often referred to as Delannoy numbers¹), namely a_n,k=å_i=0ⁿ (

) (

n+k-i

) which translates all the possible choices to perform i moves of the type (1,1), n-i moves of the type (1,0) and k-i moves of the type (0,1).

An irrational generating function: the chess knight recurrence

This time, one performs jumps (1,2) or (2,1) and the a_n,k's are known for n£ 1 or k£ 1. Petkovsek proved that F(x,y)=å a_n,kxⁿ y^k is irrational [10] and a forthcoming article by Bousquet-Mélou and Petkovsek should show that F is in fact non D-finite.

A first problem which can arise in several variables is that initial conditions have to be correctly set in order to establish the uniqueness of the solution to a linear recurrence with constant coefficients. The second problem is what the nature of the solutions is, and how to compute them.

2 Existence and Uniqueness of the Solution

Henceforth, we view all the indices (and variables) as tuples of Z^d or C^d, that is n=(n₁,...,n_d) and x=(x₁,...,x_d). Let H={h₁,...,h_k} be the set of allowed jumps. Let s be the ``true'' starting point of the walk, that is the point after which all jumps are possible and where one does not care about the side conditions anymore. The kind of recurrence under study is formalized by

ì
í
î

f(n)

for n³0 and n¬ ³s,

h₁

n+h₁

+...+c

h_k

n+h_k

for n³s.

(1)

The first part of the recurrence stands for the ``initial'' conditions (that is, the boundary values) and the second part reflects the different shifts (or jumps) allowed.

Definition 1 [Dependency relation] Define ® by p®qÜÞ(p-q Î H and q ³ s). Note ®⁺ the transitive closure of ®.

Thus, p®q simply means that there is a ``step'' from p to q, with q outside of the ``boundary value'' area, and p®⁺q means that there is a sequence of steps from p to q.

Theorem 1 The following are equivalent:

the transitive closure ®⁺ of the dependency relation ® is well-founded in N^d;
there exists u>0 such that u· h<0 for any ``jump vector'' hÎ H;
the convex hull of H does not intersect R₊^d.

The last point is the most efficient for proving uniqueness of the solution of recurrence (1) as it is easy to check. For example, for the chess king problem, one has a recurrence with starting point s=(1,1) and the set of allowed jumps is H={(-1,0),(-1,-1),(0,-1)}, the intersection of the convex hull of H (a triangle in the lower left quarter) and of R₊² is clearly the empty set; thus there is a unique solution to the recurrence. Considering now the recurrence a_n,k=a_n-1,k+2+a_n+2,k-1 (for n,k³ 1), where the a_n,k's are known (for n=0 or k=0), where the starting point is s=(1,1) and where the set of allowed jumps H={(-1,2),(2,-1)}, gives an example for which the convex hull intersects R₊²; thus uniqueness does not hold. As a last example, one shows that the chess knight problem has a unique solution: the starting point is s=(2,2) and the set of allowed jumps is H={(-2,1),(1,-2)}, whose convex hull does not intersect R₊².

3 Nature of the Solution

Let K be a field of characteristic zero. Consider F(x)=å_{n³ 0} a_n xⁿ with a_n Î K and xⁿ=x₁ⁿ··· x_dⁿ. A function F(x) is called rational if there exist two polynomials P and Q in K[x]\{0} such that QF-P=0. The function F is called algebraic if there exists PÎ K[x,t]\{0} such that P(x,F(x))=0. The function F is called D-finite if there exist polynomials P_i,j in K[x] such that

P_i,k(x)

¶^kF(x)

¶ x_i^k

+...+P_i,0(x)

¶^kF(x)

¶ x_i^k

with P_i,j¹0 for at least one j for each i=1,2,...,d. An equivalent definition states that the space spanned by all the derivatives of F is finite-dimensional over K(x). D-finite functions have nice closure properties and are related to a lot of combinatorial problems (see Stanley's article [12] and Lipshitz's article [7]).

Definition 2 [Apex] The apex of H is the componentwise maximum of H È {0}.

For example, for the chess knight problem, one has H={(-2,1),(1,-2)} so the apex is (1,1) (and the starting point is (2,2)). If H={(-2,-1),(-1,2)}, then the apex is (0,2).

An important ingredient in the proof of the two theorems stated hereafter is the kernel method. Let us detail this point: one wants to make explicit the solution F_s of the recurrence (1), which rewrites Q(x) F_s(x)=K(x)-U(x) where K stands for the known initial conditions and U stands for the unknown initial conditions. Q is called the kernel. The kernel method consists in cancelling the kernel Q(x) by a choice of algebraic values a of x, thus one gets a system of equations K(a)-U(a)=0. Solving this system generally allows to make U explicit. This provides F_s for generic x:

F_s(x)=

K(x)-U(x)

Q(x)

Typically, the function U(x) is the sum of m unknown multivariate functions F_i(x₁,...,x_d-1); thus cancelling the kernel with m different values for x_d (which then become functions of (x₁,...,x_d-1)) yields a system which allows to make explicit the F_i's. The kernel method has belonged to mathematical folklore since the 1970's; e.g., it has been used by combinatorialists [3][6, Sec. 2.2.1, Ex. 4 and 11] and probabilists [4]. There is also some recent work which makes a deep use of it [1, 2, 10, 11].

Theorem 2 Assume the apex of H is 0. Then the generating function F_s(x) of the unique solution of recurrence (1) is rational if and only if the known initial function K(x) itself is rational.

Theorem 3 Take K=C. Assume the apex of H has at most one positive coordinate. Then the generating function F_s(x) of the unique solution to the recurrence (1) is algebraic if and only if the known initial function K(x) itself is algebraic.

An algebraic example: Dyck paths

One performs steps (1,1) or (1,-1), the numbers a_i,j of paths from (0,0) to (i,j) satisfy the recurrence a_i,j=a_i-1,j-1+a_i-1,j+1 (for m,n³ 1), a_0,0=1 and a_i,j=0 elsewhere. This leads to the functional equation (y-x-xy²)F_s(x,y)=y-U(x). Applying the kernel method yields

F_s(x,y)=

1-(1-4x²)^1/2

y-x-xy²

A transcendental and D-finite example: Young tableaux

The generating function of Young tableaux of height at most d is related to the numbers

1,...,1,n+1

d-1

i=1

i^d-1

(dn)!

d-1

i=0

(n+i)!

d-1

i=1

i^d-1

(d)^1/2

(2p)^(d-1)/2

d^dn

(d²-1)/2

Algebraicity would imply asymptotics of the type C· Aⁿ/(G(1-r)n^r) with C and A algebraic numbers and r a rational number not in {1,2,3,...} (classical result from singularity analysis [5]). In our case, for odd d>1, r is an integer and for even d>2, G(1-(d²-1)/2) is in Q((p)^1/2 ) but not in Q(p^(d-1)/2). Thus, the generating function of Young tableaux of height at most d is transcendental (for d³ 3) and D-finite. Due to well-known one-to-one correspondences, this result extends from Young tableaux to ballot problems and involutions avoiding long increasing subsequences.

A non-D-finite and hypertranscendental example

The numbers a_m,n defined by

a_m,n=a_m+1,n-2+a_m-2,n+1-a_m-1,n-1, if m,n³ 2,

a_1,1=-1, and a_m,n=0 elsewhere, actually belong to {0,1,-1} and correspond to a nice ``fractal'' lozenge pattern (see the ``diamond figure'' in [11]). Let G(x)=å_m³
2 a_m,2 x^m+1; one then has

F_s(x,y)=

m,n³ 2

a_m,nx^m-2y^n-2=

xy-G(x)G(y)

(x-y²)(y-x²)

This equation gives x³-G(x)-G(x²)=0 which leads by iteration to G(x)=x³å_{i³ 0} (-i)ⁱ x²^ⁱ. This kind of lacunary series cannot be D-finite. A stronger result gives that G is in fact hypertranscendental [8], which means that there exists no algebraic differential equation P(z,G,G',...,G⁽ⁿ⁾)=0.

4 Conclusion

This talk gave a bestiary of solutions for linear multivariate recurrences with constant coefficients. In two dimensions, it covers the theory of Riordan arrays [9] (objects related to the Lagrange inversion formula). Even in two dimensions, it can be difficult to get the status of the generating function (algebraic?, D-finite?, ...). The main possible proofs are: in the algebraic case, the key point is the kernel method, note that this method also appears in two other summaries in these proceedings (see Schaeffer's and Banderier's talks); in the transcendental case, asymptotics allow to detect the nonalgebraicity, and for non D-finite functions, one generally tries bootstrapping and then obtaining an infinite number of singular points.

Marko Petkovsek has implemented some of the methods presented here in a Mathematica package multivar, available, as several author's articles, at http://www.fmf.uni-lj.si/~petkovsek/.

References

[1]: Banderier (C.), Bousquet-Mélou (M.), Denise (A.), Flajolet (P.), Gardy (D.), and Gouyou-Beauchamps (D.). -- Generating functions for generating trees. Discrete Mathematics. -- 25 pages. To appear.
[2]: Bousquet-Mélou (Mireille). -- Multi-statistic enumeration of two-stack sortable permutations. Electronic Journal of Combinatorics, vol. 5, n°1, 1998. -- Research Paper 21, 12 pp. (electronic).
[3]: Cori (Robert) and Richard (Jean). -- Énumération des graphes planaires à l'aide des séries formelles en variables non commutatives. Discrete Mathematics, vol. 2, 1972, pp. 115--162.
[4]: Fayolle (G.) and Iasnogorodski (R.). -- Solutions of functional equations arising in the analysis of two-server queueing models. In Performance of computer systems (Proc. Fourth Internat. Sympos. Modelling Performance Evaluation Comput. Systems, Vienna, 1979), pp. 289--303. -- North-Holland, Amsterdam, 1979.
[5]: Flajolet (Philippe). -- Analytic models and ambiguity of context-free languages. Theoretical Computer Science, vol. 49, n°2-3, 1987, pp. 283--309. -- Twelfth international colloquium on automata, languages and programming (Nafplion, 1985).
[6]: Knuth (Donald E.). -- The art of computer programming. Vol. 1: Fundamental algorithms. -- Addison-Wesley, 1968.
[7]: Lipshitz (L.). -- D-finite power series. Journal of Algebra, vol. 122, n°2, 1989, pp. 353--373.
[8]: Loxton (J. H.) and Van der Poorten (A. J.). -- A class of hypertranscendental functions. Aequationes Mathematicae, vol. 16, n°1-2, 1977, pp. 93--106.
[9]: Merlini (Donatella) and Verri (M. Cecilia). -- Generating trees and proper Riordan arrays. Discrete Mathematics, vol. 218, n°1-3, 2000, pp. 167--183.
[10]: Petkovsek (M.). -- The irrational chess knight. In Formal Power Series and Algebraic Combinatorics, pp. 513--522. -- 1998. Proceedings of FPSAC'98, June 1998, Toronto.
[11]: Petkovsek (Marko) and Bousquet-Mélou (Mireille). -- Linear recurrences with constant coefficients: the multivariate case. Discrete Mathematics, vol. 225, n°1-3, 2000, pp. 51--75.
[12]: Stanley (R. P.). -- Differentiably finite power series. European Journal of Combinatorics, vol. 1, n°2, 1980, pp. 175--188.

1: Henry Auguste Delannoy was born in 1833, graduated from the École polytechnique in 1853 and became a military intendant in the city of Orléans. He wrote a lot of contributions in recreative mathematics and combinatorics until 1898, the most remarkable being How to use a chessboard in order to solve some probability problems. After the death of his friend Lucas, he took in charge the publication of Lucas's last unachieved books.

This document was translated from L^AT_EX by H^EV^EA.