To appear in Discrete Mathematics.

Symbolic Integration of Meromorphic Differential Systems via Dirichlet Functions

Hoang Ngoc Minh, Université Lille II, 59024 Lille Cedex, France, and Gérard Jacob, Université Lille I, 59655 Villeneuve d’Ascq, France.

Abstract

We present a symbolic technique for computing the exact or approximate solutions of linear differential systems with meromorphic coefficients. To any system of that form, we attach a non commutative generating series F. The combinatorial decomposition of F allows to get the solution as a polynomial in Dirichlet functions, or hypergeometric functions, that are built from the coefficients of the system.

0 Introduction

In this paper, we propose the Dirichlet functions [20] as basic elements for expressing the solutions of the differential systems with meromorphic coefficients. Our method for investigating differential systems is based on the combinatorial properties of the rational series in non commutative variables [2, 22, 35, 36] and on the symbolic computation [15, 19]. Then we interpret this encoding via iterated integrals on meromorphic differential forms, and we exploit systematically the intrinsic structures of their symbolic encoding via non commutative rational identities. Just as the Laplace symbolic technique allows to treat ordinary differential equations systems with constant coefficients, the evaluation transform also allows to treat the case of non constant coefficients. A partial implementation of this transform can be found in [3, 16] and the proof is given in [19].

0.1 Position of the problem

To simplify our statement, we consider here the following linear differential equations system:

(DS) \{ \begin{matrix}dq(z) & = & A(z)q(z)dz, \\ q(z_{0}) & = & γ, \\ y(z) & = & λq(z), \end{matrix}

where the matrix A = (A_{ij})_{i,j=1..n} is a square matrix of order n of rational functions of z, and where γ and λ are respectively a column vector and a row vector of dimension n. We also suppose that zero is a singularity of A. Thanks to a Barkatou’s algorithm (implemented in Maple [1]), we can suppose, after a coordinate change, that we are in the Fuchs regular case with only simple regular singularities. Following Fuchs [14], the singularities of the output y are among the singularities of the matrix A. Therefore, it is natural to determine the exact or approximate solutions in the class of functions admitting the same singularities as A.

We start with a Picard procedure consisting in the transcription of these differential equations into integral equations and in the computation of q as the limit of the recurrent sequence {q_{k}}_{k≥0} defined as:

q_{k}(z) = q(z_{0}) + ∫_{z_{0}}^{z} A(s)q_{k−1}(s)ds

with the starting point q_{0}(z) = γ. The output y takes the following form:

y(z) = λU(z_{0}; z)γ

where the matrix U(z_{0}; z) is the following Dyson series [7]:

U(z_{0}; z) = ∑_{k≥0} ∫_{z_{0}}^{z} ∫_{z_{0}}^{s_{k}} … ∫_{z_{0}}^{s_{2}} A(s_{k}) … A(s_{1})ds_{1} … ds_{k}.

By a result of Chen [5, 34, 35], the matrix U(z_{0}; z) is the exponential of some Lie element and the problem is then to determine the matrix Ω(z_{0}; z) such that

U(z_{0}; z) = exp[Ω(z_{0}; z)].

Following Magnus [30], the computation of Ω(z_{0}; z) can be obtained as the limit of the recurrent sequence of matrices {Ω_{k}(z_{0}; z)}_{k≥0} defined as

Ω_{k}(z_{0}; z) = ∫_{z_{0}}^{z}(A(s) + \frac{1}{2}[A(s), Ω_{k−1}(z_{0}; s)] + \frac{1}{12}[[A(s), Ω_{k−1}(z_{0}; s)], Ω_{k−1}(z_{0}; s)] + …)ds.

with the starting point Ω_{0}(z_{0}; z) = 0. For the system (DS), Magnus work gives m constant matrices {N_{i}}_{i=1..m} and m scalar functions {f_{i}}_{i=1..m} verifying nonlinear differential equations such that locally U(z_{0}; z) is finitely represented

U(z_{0}; z) = exp[f_{1}(z)N_{1} + … + f_{m}(z)N_{m}].

Using the Zassenhaus formula, Magnus [30] also gave an infinite product representation of U(z_{0}; z). Based on this work, Wei and Norman [37, 38] proved the existence of l constant matrices {M_{i}}_{i=1..l} and l scalar functions {g_{i}}_{i=1..l} satisfying a set of nonlinear differential equations such that locally (sometimes globally), U(z_{0}; z) is finitely represented as :

U(z_{0}; z) = exp[g_{1}(z)M_{1}] … exp[g_{l}(z)M_{l}].

How to compute these local coordinate functions {g_{i}}_{i=1..l}? What kind of functions are they? The answers to these questions need, of course, the study of the structure of the abstract Lie

algebra generated by the matrices {M_{i}}_{i=1..l} as in [30, 37, 38] and lead naturally to the construction, in the dual structure [35], of the associated special functions obtained as the successive integrals of the coefficients of the matrix A (see [19, 20]).

0.2 Bilinear systems and generating series

Actually, as explained by Cartier [4], the unipotent case is such the previous Dyson series is finite and in this case, the coefficients of the matrix U(z_{0}; z) are finite sums of Chen iterated integrals on rational differential forms.

Now, for the non finite case, we introduce the linearly independant constant matrices M_{i} and the scalar functions v_{i}(z) on z, for i = 1..m, such that

A(z) = ∑_{i=1}^{m} M_{i}v_{i}(z)

and we write, as in [37, 38], the system (DS) in the form of a bilinear system

(BL) \{ \begin{matrix}dq(z) & = & ∑_{i=1}^{m} M_{i}q(z) v_{i}(z)dz, \\ q(z_{0}) & = & γ, \\ y(z) & = & λq(z). \end{matrix}

This form has several advantages • The singularities of the matrix A are placed in the prominent position. The input functions v_{i}

indicate what kind of iterated integrals we need. In particular, we organize the computation with a minimum number of useful iterated integrals.

• Symbolic manipulation of Lie bracket is easier in the case of constant matrices than in the case of meromorphic matrices (the matricial polylogarithms introduced by Dupont [6]) leading often to decision procedures on functional equations on special functions (it is a real difficulty even in the polylogarithm case [39, 40]).

• Following Fliess [13] and Jacob [23], the generating series of the bilinear system (BL) is rational over the alphabet X = {x_{1}, …, x_{m}}, in bijection with the inputs {v_{1}, …, v_{m}}, and admits (λ, μ, γ) as linear representation [2, 22]. The Peano-Baker formula gives the output y as the evaluation, for the differential forms dα_{x_{i}}(z) = v_{i}(z)dz, of the mirror of F^{1}

F = ∑_{w∈X^{∗}}[λμ(w)γ]w and y = ∑_{w∈X^{∗}}[λμ(w)γ]α(w̃).

Therefore, the description of solutions can be done in the context of formal power series.

0.3 The scope of the symbolic point of view

The essential benefits of this approach by generating series are its positive results on decidable properties and its non commutative rational identities interpreted here as functional equations on special functions. For example, it is decidable if a generating rational series is finite (see [2, 22]). Hence, in the positive case, the associated output is a finite sum of iterated integrals and it can be then expressed as a polynomial of some basic elements, obtained as the evaluation of the Lyndon-Širšov words, or any other transcendance basis of the shuffle algebra [33, 35, 36]. Generalizing the previous process for the non finite case, it is useful to give some necessary (and sufficient) conditions allowing to entirely explicit the output. For that, we explicit the various syntactic descriptions of generating series as the basic decompositions and after that, we use the evaluation transform to obtain their outputs as the basic solutions.

More precisely, by examination of the minimal linear representation (λ, μ, γ) of the generating series F [2, 22], we have obtained, via several symbolic techniques, the following computation of the exact or approximate solutions of the associated differential system [20]

• If F is exchangeable then it can be expressed as a function of elementary functions (theorem 3.1).

• If F is finite then by Radford theorem [33] the solutions can be expressed as a polynomial on elementary functions and on Dirichlet functions (theorem 3.2).

• If F is a linear combination of rational series in the form (c_{0}x_{0})^{∗}x_{i_{1}}(c_{1}x_{0})^{∗} … x_{i_{p}}(c_{p}x_{0})^{∗} then the solution can be expressed as a finite sum of hypergeometric functions (theorem 3.3).

• If the Lie algebra generated by the matrices {μ(x)}_{x∈X} is nilpotent then the solution can be expressed as a polynomial on elementary functions and on Dirichlet functions (theorem 3.4).

The last case will be extended, due to Wei-Norman theorem [37, 38], to the case of solvable Lie algebra (theorem 3.5).

These techniques confirm that, to express the solutions of differential systems with rational coefficients, one needs to introduce a new class of functions containing, especially, the hypergeometric functions and Dirichlet functions constructed from the coefficients of these systems, as already pointed out by Poincaré and done by Lappo-Danilevsky [27] and Dupont [6], introducing respectively the hyperlogarithms and the matricial polylogarithms.

1The mirror of the word w = x_{i_{1}}x_{i_{2}} … x_{i_{n}} is the word w̃ = x_{i_{n}} … x_{i_{2}}x_{i_{1}}.

0.4 Summary

The organization of this paper in the following sections is respectively as follows

1. We expose some useful algebraic properties of formal power series on non commutative variables, particularly the polynomials and the rational series [2, 22, 35, 36], for an application on symbolic computation [15, 19].

2. We give some combinatorial properties and some possible decompositions of the Dirichlet functions, in terms of polylogarithms and their derivatives [28, 29]. We show then how to extract some relations between these functions, from the algebraic relations on Lyndon-Širšov words, extending the class of Nielsen polylogarithms [31, 32]. We also construct their generating function, which is of hypergeometric type, as the evaluation of the rational series x_{1}(ax_{0})^{∗}.

3. We show, via the evaluation of non commutative rational series, that the solutions of meromorphic differential equations systems are intimately related to the special functions and their exponentials, according to the basic decompositions of their syntactic descriptions.

4. These tools are applied to explore the syntactic structure of the integral equation issued from the study of search costs in quadtrees, and to explain the relations of this equation with special functions, as already pointed out in [11, 12, 25, 26].

1 Formal power series and symbolic calculus

1.1 Combinatoric aspects

Here, we refer to [2, 35, 36] for the basic notations and we expose some useful algebraic properties of polynomials and formal power series on non commutative variables.

1.1.1 Words and rational series on non commutative variables

Let X = {x_{0}, …, x_{m}} be a finite alphabet. The free monoid generated by X is denoted by X^{∗}. The “empty word” is noted ε. The set of non commutative polynomials and formal power series over X with coefficients in C I are respectively noted C I ⟨X⟩ and C I ⟨⟨X⟩⟩.

A formal power series S is said to be proper if the coefficient of the empty word is equal to zero. The star of a proper series S is the infinite sum S^{∗} = ∑_{n≥0} S^{n}. The rational operations in C I ⟨⟨X⟩⟩ are the sum, the Cauchy product, the external product of C I on C I ⟨⟨X⟩⟩, and the star operation.

A formal power series is rational if it belongs to the closure of C I ⟨X⟩ under the rational operations. According to a theorem of Schützenberger (see [2, 22]), S is rational if and only if there exists an integer n ≥ 1, a morphism of monoids μ from X^{∗} to M_{n,n}(C I ) and two matrices λ ∈ M_{1,n}(C I ⟨⟨X⟩⟩), γ ∈ M_{n,1}(C I ⟨⟨X⟩⟩) such that

S = ∑_{w∈X^{∗}}[λμ(w)γ]w.

The triplet (λ, μ, γ) is called a linear representation of S and n is its dimension [2, 22]. By a theorem of Schützenberger (see [2, 22]), any rational power series S admits a linear representation of minimal dimension, which is unique up to some isomorphism. It is called the minimal representation of S. It will also be convenient to denote by ρ the morphism of monoids from X^{∗} to M_{n,n}(C I ⟨⟨X⟩⟩) defined by

∀x ∈ X, ρ(x) = μ(x)x.

Let (λ, μ, γ) be the minimal linear representation of the rational series S over X. Let L be the Lie algebra generated by the matrices {μ(x)}_{x∈X}. The lower central series, {L^{k}}_{k≥1}, and the derived series, {L^{(k)}}_{k≥1}, of L are defined recursively as follows

L^{1} = L, L^{n+1} = [L, L^{n}] and L^{(1)} = L, L^{(n+1)} = [L^{(n)}, L^{(n)}].

The Lie algebra L is nilpotent (resp. solvable) at order h if and only if L^{h+1} = {0} (resp. L^{(h+1)} = {0}). In this case, S also is said to be nilpotent (resp. solvable) at order h.

1.1.2 Lyndon-Širšov words and bases of the shuffle algebra

Let “<” be a total order over the alphabet X. The reverse lexicographical order, also denoted by “<” is defined as follows [36]

u < v ⟺ \{ \begin{matrix}either & ∃w ∈ X^{∗}, w ≠ ε & such that wu = v, \\ or & ∃f, g, h ∈ X^{∗}, x, y ∈ X, x < y & such that u = fxh and v = gyh. \end{matrix}

We denote by S the set of the Lyndon-Širšov words. Recall that a word w is an element of S if and only if it is strictly less than all its proper left factors, for the reverse lexicographical order.

Lemma 1.1 (Standard factorization, [36]) Any Lyndon-Širšov word b either is a letter of X, or admits a standard factorization st(b) = (m, l) that satisfies b = ml, with l, m ∈ S and l < m.

Theorem 1.1 (Radford theorem, [33, 35])

1. The Lyndon-Širšov words form a transcendance basis of the shuffle algebra C I ⟨X⟩.

2. Any word w admits a unique increasing factorization on Lyndon-Širšov words l_{1}, …, l_{k} veri-

fying l_{1} < … < l_{k}

w = l_{1}^{i_{1}}l_{2}^{i_{2}} … l_{k}^{i_{k}}.

3. Let l_{1}^{i_{1}}l_{2}^{i_{2}} … l_{k}^{i_{k}} be the increasing factorization of w on Lyndon-Širšov words. Then for some constant integers c_{u}^{2}

\frac{l_{1}^{_{⊔⊔} i_{1}} ^{⊔⊔} …^{⊔⊔} l_{k}^{_{⊔⊔} i_{k}}}{i_{1}! … i_{k}!} = w + ∑_{u∈X^{|w|},u<w} c_{u}u.

Definition 1.1 [36] For any Lyndon-Širšov word b, one defines recursively a Lie polynomial Q_{b} as follows

\{ \begin{matrix}if & b ∈ X & then & Q_{b} = b, \\ if & st(b) = (m, l) & then & Q_{b} = [Q_{m}, Q_{l}]. \end{matrix}

Theorem 1.2 [36] The family {Q_{b}}_{b∈S} is a basis of the free Lie algebra Lie⟨X⟩. It is called the Lyndon-Širšov basis.

Theorem 1.3 (Poincaré-Birkhoff-Witt Theorem, [36]) Let l_{1}^{i_{1}}l_{2}^{i_{2}} … l_{k}^{i_{k}} be the factorization of w by the Lyndon-Širšov words. The family {Q_{w}}_{w∈X^{∗}}, defined by

Q_{w} = Q_{l_{1}}^{i_{1}}Q_{l_{2}}^{i_{2}} … Q_{l_{k}}^{i_{k}},

is a basis of the associative algebra C I ⟨X⟩ of polynomials. It is called the PBW-Lyndon-Širšov basis.

Theorem 1.4 (Dual basis, see [35]) Let us denote by {R_{w}}_{w∈X^{∗}} the “dual basis” of the PBW-Lyndon-Širšov basis. Then these polynomials can be recursively computed as follows

R_{w} = \{ \begin{matrix}ε & if & w = ε, \\ R_{v}x & if & w = vx ∈ S, & (v ∈ X^{∗}, x ∈ X), \\ \frac{1}{i_{1}! … i_{k}!}R_{l_{1}}^{_{⊔⊔} i_{1}} ^{⊔⊔} …^{⊔⊔} R_{l_{k}}^{_{⊔⊔} i_{k}} & if & w = l_{1}^{i_{1}} … l_{k}^{i_{k}}, & (l_{i} ∈ S and l_{1} < … < l_{k}). \end{matrix}

Each polynomial R_{w} is homogenous of degree |w|.

\begin{matrix}∀u ∈ X^{∗}, & u^{⊔⊔} ε = ε^{⊔⊔} u = u, \\ ∀u, v ∈ X^{∗}, ∀x, y ∈ X, & ux^{⊔⊔} vy = (ux^{⊔⊔} v)y + (u^{⊔⊔} vy)x. \end{matrix}

2“^{⊔⊔}” denotes the shuffle product and it is defined as follows (see [2, 22])

The role of the polynomials R_{b} (for the Lyndon-Širšov words b) with respect to the shuffle product is clarified by the following theorem

Theorem 1.5 [35] The non commutative polynomial algebra C I ⟨X⟩ also is, with respect to the shuffle product, the commutative algebra freely generated by the family {R_{b}}_{b∈S}.

In other words, any non commutative polynomial is, with respect to the shuffle, a polynomial on the R_{b}’s.

Example 1.1 Let X = {x_{0}, x_{1}} with x_{0} < x_{1}. From the definitions 1.1 and 1.4, we have

\begin{matrix}b & Q_{b} & R_{b} \\ x_{0} & x_{0} & x_{0} \\ x_{1}x_{0}^{4} & [[[[x_{1}, x_{0}], x_{0}], x_{0}], x_{0}] & x_{1}x_{0}^{4} \\ x_{1}x_{0}^{3} & [[[x_{1}, x_{0}], x_{0}], x_{0}] & x_{1}x_{0}^{3} \\ x_{1}^{2}x_{0}^{3} & [[[x_{1}, [x_{1}, x_{0}]], x_{0}], x_{0}] & x_{1}^{2}x_{0}^{3} \\ x_{1}x_{0}^{2} & [[x_{1}, x_{0}], x_{0}] & x_{1}x_{0}^{2} \\ x_{1}x_{0}x_{1}x_{0}^{2} & [[x_{1}, x_{0}], [[x_{1}, x_{0}], x_{0}]] & x_{1}x_{0}x_{1}x_{0}^{2} + 2x_{1}^{2}x_{0}^{3} \\ x_{1}^{2}x_{0}^{2} & [[x_{1}, [x_{1}, x_{0}]], x_{0}] & x_{1}^{2}x_{0}^{2} \\ x_{1}^{3}x_{0}^{2} & [x_{1}, [[x_{1}, x_{0}], x_{0}]] & x_{1}^{3}x_{0}^{2} \\ x_{1}x_{0} & [x_{1}, x_{0}] & x_{1}x_{0} \\ x_{1}^{2}x_{0}x_{1}x_{0} & [[x_{1}, [x_{1}, x_{0}]], [x_{1}, x_{0}]] & x_{1}^{2}x_{0}x_{1}x_{0} + 3x_{1}^{3}x_{0}^{2} \\ x_{1}^{2}x_{0} & [x_{1}, [x_{1}, x_{0}]] & x_{1}^{2}x_{0} \\ x_{1}^{3}x_{0} & [x_{1}, [x_{1}, [x_{1}, x_{0}]]] & x_{1}^{3}x_{0} \\ x_{1}^{4}x_{0} & [x_{1}, [x_{1}, [x_{1}, [x_{1}, x_{0}]]]] & x_{1}^{4}x_{0} \\ x_{1} & x_{1} & x_{1} \end{matrix}

So we verify that for n, p ≥ 0, we have x_{1}^{p}x_{0}^{n} = R_{x_{1}^{p}x_{0}^{n}}. The other Širšov words can be expressed in terms of R_{b}’s. For example x_{1}x_{0}x_{1}x_{0}^{2} = R_{x_{1}x_{0}x_{1}x_{0}^{2}} −2R_{x_{1}^{2}x_{0}^{3}}, x_{1}^{2}x_{0}x_{1}x_{0} = R_{x_{1}^{2}x_{0}x_{1}x_{0}} −3R_{x_{1}^{3}x_{0}^{2}}, . . ..

1.2 Symbolic computational aspects

Here, we suppose given a meromorphic differential form dα_{x}, for each letter x ∈ X.

1.2.1 Evaluation without kernel

To any word w we associate the iterated integral α_{ς}^{z}(w) by the following recursive definition

α_{ς}^{z}(w) = \{ \begin{matrix}1 & if & w = ε, \\ ∫_{ς}^{z} α_{ς}^{s}(v)dα_{x}(s) & if & w = vx, & (v ∈ X^{∗}, x ∈ X). \end{matrix}

The iterated integral α_{ς}^{z}(w) also is called the evaluation transform [19] of the word w with respect to the meromorphic differential forms {dα_{x}}_{x∈X}. A straightforward interpretation can be done in form of differential equations as follows. By setting dα_{x_{i}} = dz/f_{i}(z), the iterated integral α_{ς}^{z}(x_{i_{1}} … x_{i_{k}}) is nothing else as the function g(z) that satisfies the following differential equation, (for clear vanishing conditions at ς)

(f_{i_{1}}(z)\frac{d}{dz} ) ∘ … ∘ (f_{i_{k}}(z)\frac{d}{dz} )g(z) = 1.

This evaluation transform is extended to the formal power series, up to convergence, by [19]

α_{ς}^{z}(S) = ∑_{w∈X^{∗}}⟨S|w⟩α_{ς}^{z}(w).

The evaluation transform of the words verifies the two following properties [5, 19] • The integration by part rule : for any word u and v, one has

α_{ς}^{z}(u^{⊔⊔} v) = α_{ς}^{z}(u)α_{ς}^{z}(v).

• The additivity property : for any w, one get

α_{ρ}^{z}(w) = ∑_{u,v∈X^{∗},uv=w} α_{ρ}^{ς}(u)α_{ς}^{z}(v).

From the integration by part rule, for any letters x and for any integers n, one deduce

α_{ς}^{z}(x^{n}) = \frac{[α_{ς}^{z}(x)]^{n}}{n!} .

The evaluation transform can be then considered as the generalization of the inverse Laplace-Borel transform and it explains that the exchangeable power series^{3} are exactly the symbolic encoding of the analytic functionals (see [13])

\begin{matrix}∑_{n≥0} c_{n}x^{n} & ⟼ & ∑_{n≥0} c_{n} \frac{[α_{ς}^{z}(x)]^{n}}{n!} , \\ ∑_{n_{1},...,n_{m}≥0} c_{n_{1},...,n_{m}}x_{1}^{n_{1}} ^{⊔⊔} …^{⊔⊔} x_{m}^{n_{m}} & ⟼ & ∑_{n_{1},...,n_{m}≥0} c_{n_{1},...,n_{m}} \frac{[α_{ς}^{z}(x_{1})]^{n_{1}} … [α_{ς}^{z}(x_{m})]^{n_{m}}}{n_{1}! … n_{m}!} . \end{matrix}

In particular

\begin{matrix}(cx)^{∗} & ⟼ & exp[cα_{ς}^{z}(x)], \\ (c_{1}x_{1} + … + c_{m}x_{m})^{∗} & ⟼ & exp[c_{1}α_{ς}^{z}(x_{1}) + … + c_{m}α_{ς}^{z}(x_{m})]. \end{matrix}

More generally, any non commutative power series that verifies the growth condition encodes a functional of the inputs, that can be obtained by using the evaluation without kernel [15] or even better, by using the evaluation with kernel function [19]

1.2.2 Evaluation with kernel

Let us note κ_{ς} a function vanishing in ς ∈ C I . The evaluation transform of the formal power series S = ∑_{w∈X^{∗}}⟨S|w⟩w with respect to the meromorphic differential forms {dα_{x}}_{x∈X} and to the kernel function κ_{ς} is defined as follows [19]

\begin{matrix}α_{ς}^{z}(κ_{ς}; S) = ∑_{w∈X^{∗}}⟨S|w⟩α_{ς}^{z}(κ_{ς}; w), \\ α_{ς}^{z}(κ_{ς}; w) = \{ \begin{matrix}κ_{ς}(z) & if & w = ε, \\ ∫_{ς}^{z} α_{ς}^{s}(κ_{ς}; v)dα_{x}(s) & if & w = vx, & (x ∈ X, v ∈ X^{∗}). \end{matrix} \end{matrix}

A straightforward interpretation can be done in terms of differential equations as follows by setting dα_{x_{i}} = dz/f_{i}(z), the iterated integral α_{ς}^{z}(κ_{ς}; x_{i_{1}} … x_{i_{k}}) is nothing else as the function g(z) that satisfies the following differential equation, (for clear vanishing conditions at z = ς)

(f_{i_{1}}(z)\frac{d}{dz} ) ∘ … ∘ (f_{i_{k}}(z)\frac{d}{dz} )g(z) = κ_{ς}(z).

3A formal power series R is exchangeable if and only if two words have the same coefficient in R, each time they have the same commutative image (see [13])

(∀x ∈ X, |u|_{x} = |v|_{x}) ⇒ (⟨R|u⟩ = ⟨R|v⟩).

It follows that R is exchangeable if and only if it takes the form R = ∑_{n_{0},...,n_{m}≥0} r_{n_{0},...,n_{m}}x_{0}^{n_{0}} ^{⊔⊔} …^{⊔⊔} x_{m}^{n_{m}}.

The evaluation transform with respect to the kernel function κ_{ς} is no longer a morphism for the shuffle because, in general, we have

α_{ς}^{z}(κ_{ς}; u^{⊔⊔} v) ≠ α_{ς}^{z}(κ_{ς}; u)α_{ς}^{z}(κ_{ς}; v).

But we get the following result [19] (for any letter y_{1}, …, y_{n} and for any integer i_{1}, …, i_{n})

α_{ς}^{z}(κ^{ς}; y_{1}^{i_{1}} ^{⊔⊔} …^{⊔⊔} y_{n}^{i_{n}}) = ∫_{ς}^{z} \frac{[α_{ς}^{z}(y_{1}) − α_{ς}^{s}(y_{1})]^{i_{1}}}{i_{1}!} … \frac{[α_{ς}^{z}(y_{n}) − α_{ς}^{s}(y_{n})]^{i_{n}}}{i_{n}!} dκ_{ς}(s).

This yields a correspondence between some convolutions of signals and the corresponding Cauchy products of generating power series

Theorem 1.6 (Convolution theorem, [19]) Let H be an exchangeable formal power series and let h[α_{ς}^{z}(x_{1}), …, α_{ς}^{z}(x_{m})] be its evaluation without kernel. We have

α_{ς}^{z}(κ_{ς}; H) = ∫_{ς}^{z} h[α_{ς}^{z}(x_{1}) − α_{ς}^{s}(x_{1}), …, α_{ς}^{z}(x_{m}) − α_{ς}^{s}(x_{m})]dκ_{ς}(s).

Finally, the evaluation transform with respect to kernel functions vanishing at ς verifies the following properties (S, R are formal power series and κ_{ς}, λ_{ς} are kernel functions) [19]

1. If ⟨S|ε⟩ = 0 then α_{ς}^{ς}(κ_{ς}; S) = 0.

2. If ⟨S|ε⟩ = 0 then α_{ς}(κ_{ς} + λ_{ς}; S) = α_{ς}(κ_{ς}; S) + α_{ς}(λ_{ς}; S).

3. If ⟨S|ε⟩ = ⟨R|ε⟩ = 0 then α_{ς}(κ_{ς}; S + R) = α_{ς}(κ_{ς}; S) + α_{ς}(κ_{ς}; R).

4. α_{ς}(κ_{ς}; SR) = α_{ς}[α_{ς}(κ_{ς}; S); R].

5. α_{ς}(S^{⊔⊔} R) = α_{ς}(S)α_{ς}(R).

6. If R is exchangeable and if r[α_{ς}^{z}(x_{1}), …, α_{ς}^{z}(x_{m})] is its evaluation without kernel, then

α_{ς}^{z}(SR) = ⟨S|ε⟩r[α_{ς}^{z}(x_{1}), …, α_{ς}^{z}(x_{m})] + ∫_{ς}^{z} r[α_{ς}^{z}(x_{1}) − α_{ς}^{s}(x_{1}), …, α_{ς}^{z}(x_{m}) − α_{ς}^{s}(x_{m})]dα_{ς}^{s}(S).

2 The Dirichlet functions

In this section, as an application of the evaluation transform, we give some combinatorial properties of the Dirichlet functions and their possible decompositions in terms of polylogarithms. We also construct their generating functions, which are hypergeometric type functions.

2.1 Notations and definitions

Let {f_{k}}_{k≥1} be a sequence of complex numbers, with generating series

F (z) = ∑_{k≥1} f_{k}z^{k}

and suppose that F (z)/z is meromorphic. We cut the complex plane C I from 0 and from each singularity of F to ∞ without crossings. The remaining domain is denoted by Ω_{F} and the unit open disc is denoted by U.

Let g be an injective meromorphic function with values in the domain Ω_{F} and we consider the two following differential forms

dα_{x_{0}} = \frac{dg}{g} and dα_{x_{1}} = F (g)\frac{dg}{g} .

Definition 2.1 Let γ ∈ Ω_{F}. For any positive integer n, we define the Dirichlet function associated to F and g as the evaluation of the word x_{1}x_{0}^{n−1}

Di_{n}^{γ}(F |g) = α_{g^{−1}(γ)}(x_{1}x_{0}^{n−1}).

If lim_{γ→0} Di_{n}^{γ}(F |g) exists then we note this limit Di_{n}(F |g).

Here, note that the evaluation of the word x_{1}x_{0}^{n−1}, for the differential forms dα_{x_{0}} and dα_{x_{1}} is the Chen iterated integral associated to x_{1}x_{0}^{n−1} [5]

α_{g^{−1}(γ)}^{z}(x_{1}x_{0}^{n−1}) = ∫_{g^{−1}(γ)}^{z} ∫_{g^{−1}(γ)}^{s_{n}} … ∫_{g^{−1}(γ)}^{s_{2}} F (s_{1})\frac{ds_{1}}{s_{1}} \frac{ds_{2}}{s_{2}} … \frac{ds_{n}}{s_{n}}

and it verifies the following algebraic differential equation [20]

(g \frac{d}{dg} )^{n}(f) = F (g).

Definition 2.2 Let γ ∈ Ω_{F}. For any positive integer n, let us define the following integral

Λ_{n}^{γ}(F |g(z)) = ∫_{g^{−1}(γ)}^{z} \frac{[− log(g(s))]^{n}}{n!} dα_{x_{1}}(s).

If lim_{γ→0} Λ_{n}^{γ}(F |g) exists then we note this limit Λ_{n}(F |g).

If F (z) = ∑_{k≥1}(−z)^{k} then Λ_{n}(F |z) = (−1)^{n}/n! ∫_{0}^{z}[log(s)]^{n}ds/(1 + s). The last integral is the (n + 1)-th Kummer’s function (see [28]).

2.2 Series expansions of Dirichlet fonctions

Proposition 2.1 If there exists an integration arc Γ_{g^{−1}(γ)}^{z} such that its image by g is included in Ω_{F} then

Di_{n}(F |g) = ∑_{k≥1} f_{k} \frac{g^{k}}{k^{n}} .

Therefore, if the coefficients {f_{k}/k^{n}}_{k≥1} (resp. {f_{k}/k^{n−1}}_{k≥1}) verify a linear recurrence equation then Di_{n}(F |g) (resp. exp[Di_{n}(F |g)]) is a rational function on g.

\underline{Proof} : To simplify, let us consider the case g(z) = z. By induction, we prove that

α_{γ}^{z}(x_{1}x_{0}^{n−1}) = ∑_{k≥1} f_{k} \frac{z^{k}}{k^{n}} − ∑_{j=0}^{n−1}[∑_{k≥1} f_{k} \frac{γ^{k}}{k^{j+1}} ]\frac{1}{(n − 1 − j)!}[log(\frac{z}{γ})]^{n−1−j}.

Since lim_{γ→0} γ^{k}[log(z/γ)]^{n−1−j} = 0 then it yields α_{0}^{z}(x_{1}x_{0}^{n−1}) = ∑_{k≥1} f_{k}z^{k}/k^{n}. So we can easily deduce the desired result •

Example 2.1 For g(z) = z, let us consider the following Nielsen polylogarithms [31, 32] (the S_{k}^{(p)}’s are the Stirling numbers of first kind and the H_{k}^{(n)}’s are the harmonic numbers)

s_{n,p}(z) = ∑_{k≥p} \frac{S_{k}^{(k−p)}}{(k − 1)!} \frac{z^{k}}{k^{n}} and c_{n,p}(z) = ∑_{k≥2} H_{k−1}^{(n)} \frac{z^{k}}{k^{p}} .

These Nielsen polylogarithms are the Dirichlet functions Di_{n}^{γ}(L_{p}|z) and Di_{n}^{γ}(H^{(n)}|z) associated to L_{p}(z) and H^{(n)}(z) respectively

L_{p}(z) = \frac{z}{1 − z} \frac{[− log(1 − z)]^{p−1}}{(p − 1)!} and H^{(n)}(z) = \frac{z}{1 − z} Li_{n}(z),

where Li_{n}(z) is the classical polylogarithm [28, 29] and can be viewed as the Dirichlet function Di_{n}^{γ}(L_{1}|z) associated to L_{1}(z) = z(1 − z)^{−1}, i.e. s_{n,1}(z).

Proposition 2.2 For any positive integer n, we get

Λ_{n}^{γ}(F |g) = ∑_{l=0}^{n} \frac{(−1)^{l}}{l!} ([log(g)]^{l} Di_{n−l+1}(F |g) − [log(γ)]^{l} Di_{n−l+1}(F |γ)).

\underline{Proof} : To simplify, let us consider the case g(z) = z. We easily verify that

Λ_{j}^{γ}(F |z) = \frac{(−1)^{j}}{j!} ∑_{k≥1} f_{k}Λ_{j,k}^{γ}(z),

where, for any integer j and k, we set Λ_{j,k}^{γ}(z) = ∫_{γ}^{z} s^{k−1} log^{j}(s)ds. Integrating by part, we get Λ_{j,k}^{γ}(z) = [z^{k} log^{j}(z) − γ^{k} log^{j}(γ) − jΛ_{j−1,k}^{γ}(z)]/k. Since Λ_{0,k}^{γ}(z) = (z^{k} − γ^{k})/k we can prove (by induction on j) that

Λ_{j,k}^{γ}(z) = \frac{j!}{(−1)^{j}} ∑_{l=0}^{j} \frac{(−1)^{l}}{l!} \frac{z^{k} log^{l}(z) − γ^{k} log^{l}(γ)}{k^{j−l+1}}.

By the proposition 2.1, it yields the expected result •

2.3 Some combinatorial properties of Dirichlet functions

Dirichlet functions satisfy a lot of combinatorial properties. Their proofs can be done in the context of the combinatorics on words and the symbolic computation as we already did for the polylogarithms and their derivatives [19, 20]

Proposition 2.3 If there exists an integration arc Γ_{g^{−1}(γ)}^{z} such that its image by g is included in Ω_{F} then

Di_{n}^{γ}(F |g) = ∑_{k=1}^{n−1} \frac{[log(g)]^{n−k}}{(n − k)!} Λ_{k−1}^{γ}(F |g),

Di_{n}^{γ}(F |g) = ∑_{i=1}^{n−1} \frac{(−1)^{i−1}}{i!} [log(\frac{g}{γ})]^{i} Di_{n−i}^{γ}(F |g) + Λ_{k−1}^{γ}(F |g),

Di_{n}^{γ}(F |g) = Di_{n}^{g(0)}(F |g) − ∑_{j=1}^{n} Di_{j}^{g(0)}(F |γ)\frac{1}{(n − j)!}[log(\frac{g}{γ})]^{n−j}.

\underline{Proof} : The first expression follows immediately from theorem 1.6 and the binomial formula. Using the recursive definition of the shuffle product [2], we successively have

x_{1}x_{0}^{n−1} = x_{0} ^{⊔⊔} x_{1}x_{0}^{n−2} − (x_{0} ^{⊔⊔} x_{1}x_{0}^{n−3})x_{0}
= x_{0} ^{⊔⊔} x_{1}x_{0}^{n−2} − x_{0}^{2} ^{⊔⊔} x_{1}x_{0}^{n−3} + (x_{0}^{2} ^{⊔⊔} x_{1}x_{0}^{n−4})x_{0}
⋮
= ∑_{i=1}^{n−1}(−1)^{i−1}x_{0}^{i} ^{⊔⊔}(x_{1}x_{0}^{n−1−i}) + (−1)^{n−1}x_{0}^{n−1}x_{1}.

Hence, using the integration by part rule for iterated integrals (see 1.2.1), it leads to the second expression. The last expression is a direct consequence of the additivity property of the iterated integrals (see 1.2.1) •

Proposition 2.4 If there exists an integration arc Γ_{g^{−1}(γ)}^{z} such that its image by g is included in Ω_{F} then

Di_{n}(F |g) = ∑_{k=1}^{n} \frac{[log(g)]^{n−k}}{(n − k)!} Λ_{k−1}(F |g),

Di_{n}(F |g) = Λ_{n−1}(F |g) − ∑_{i=1}^{n−1} \frac{[− log(g)]^{i}}{i!} Di_{n−i}(F |g).

\underline{Proof} : The first expression can be deduced from the proposition 2.2. The last one follows by successive integrations by part •

2.4 Some decompositions of Dirichlet functions

Next, we give some possible decompositions of Dirichlet functions in terms of polylogarithms and their derivatives making it possible to specify the values of iterated integral at the singularities.

Theorem 2.1 Let {ν_{i}}_{j∈I} be a finite set of pairwise distinct complex numbers

1. Let {μ_{i}}_{i∈I} be another finite set of complex numbers. Then we have

\begin{aligned}& ∀k ≥ 1, & f_{k} & = & ∑_{i∈I} μ_{i}ν_{i}^{k} \\ ⟺ & ∀n ≥ 1, & Di_{n}^{γ}(F |g) & = & ∑_{i∈I} μ_{i} Li_{j}^{γ}(ν_{i}g). \end{aligned}

2. Let μ_{0}, …, μ_{n−1} be n complex numbers. Then we have

\begin{aligned}& ∀k ≥ 1, & f_{k} & = & ∑_{i=0}^{n−1} μ_{i}k^{i} + ∑_{i∈I} \frac{ν_{i}}{k^{i}} \\ ⟺ & ∀j = 1..n, & Di_{j}(F |g) & = & ∑_{i=0}^{n−1} μ_{i} Li_{j−i}(g) + ∑_{i∈I} ν_{i} Li_{j+i}(g). \end{aligned}

3. Let μ_{0}, …, μ_{n−1} be n complex numbers. If γ ≠ 0 and g(0) = 0 then

\begin{aligned}& ∀k ≥ 1, & f_{k} & = & ∑_{i=0}^{n−1} μ_{i}k^{i} + ∑_{i∈I} \frac{ν_{i}}{k^{i}} \\ ⟺ & ∀j = 1..n, & Di_{j}^{γ}(F |g) & = & ∑_{i=0}^{n−1} μ_{i} Li_{j−i}^{γ}(g) + ∑_{i∈I} ν_{i} Li_{j+i}^{γ}(g). \end{aligned}

\underline{Proof} :

1. In fact, we get the following equivalences

∀k ≥ 1, f_{k} = ∑_{i∈I} μ_{i}ν_{i}^{k} ⟺  F (g) = ∑_{i∈I} μ_{i} \frac{ν_{i}g}{1 − ν_{i}g} ,
⟺  Di_{1}^{γ}(F |g) = ∑_{i∈I} μ_{i} Li_{1}^{γ}(ν_{i}g),
⟺ ∀n ≥ 1, Di_{j}^{γ}(F |g) = ∑_{i∈I} μ_{i} Li_{n}^{γ}(ν_{i}g).

2. The proof can be obtained by using the expansions of Di_{j}(F |g) and Li_{j}(g) given in proposition 2.1, and by substituting the expression of f_{k}.

3. Here, we also use the expansions of Di_{j}^{γ}(F |g) and of Li_{j}^{γ}(g) given in the third expression of proposition 2.3, and we conclude with point 2 •

Example 2.2 Let {l_{k}}_{k≥1} and {h_{k}}_{k≥1} be two sequences defined by l_{2k} = h_{2k} = 0, l_{2k−1} = 1 and h_{2k−1} = (−1)^{k}. Therefore

L(z) = \frac{z}{2}(\frac{1}{1 − z} + \frac{1}{1 + z} ) and  H(z) = \frac{z}{2}(\frac{1}{1 − iz} + \frac{1}{1 + iz} ),
Di_{n}^{γ}(L|g) = \frac{Li_{n}^{γ}(g) − Li_{n}^{γ}(−g)}{2} and Di_{n}^{γ}(H|g) = \frac{Li_{n}^{γ}(ig) − Li_{n}^{γ}(−ig)}{2i}.

If g(z) = z then we obtain

Di_{n}(L|1) = \frac{ζ(n) + η(n)}{2} and Di_{n}(H|i) = i \frac{ζ(n) + η(n)}{2},

where ζ(n) = Li_{n}(1) and η(n) = − Li_{n}(−1), leading to some special values

Di_{2}(L|1) = \frac{π^{2}}{8} , Di_{4}(L|1) = \frac{π^{4}}{96} , Di_{6}(L|1) = \frac{π^{6}}{960}, ….

In particular, if n = 2 then these correspond to the so-called Legendre chi-function and inverse tangent integral respectively (see [28])

Di_{2}(L|z) = \frac{1}{2} ∫_{0}^{z} log(\frac{1 + s}{1 − s})\frac{ds}{s} = χ_{2}(z) and Di_{2}(H|z) = ∫_{0}^{z} arctan(s)\frac{ds}{s} = Ti_{2}(z).

2.5 Generating function of Dirichlet functions

Theorem 2.2 The generating function of Dirichlet functions is given by

∑_{n≥0} a^{n} Di_{n+1}^{γ}(F |g(z)) = ∫_{g^{−1}(γ)}^{z} ∑_{n≥0} \frac{a^{n}}{n!} [log(\frac{g(z)}{g(s)})]^{n}F (g(s))\frac{dg(s)}{g(s)}.

Therefore, if F (z) = z(1 − z)^{−b} then we obtain in particular

∑_{n≥0} a^{n} Di_{n+1}^{γ}(F |g(z)) = g^{a}(z) ∫_{g^{−1}(γ)}^{z} \frac{dg(s)}{[1 − g(s)]^{b}g^{a}(s)}.

\underline{Proof} : The sum ∑_{n≥0} a^{n} Di_{n+1}^{γ}(F |g) is the evaluation of the formal series x_{1} ∑_{n≥0}(ax_{0})^{n}. As in [19], the power series ∑_{n≥0} a^{n}/n![log(g/γ)]^{n} is supposed uniformly convergent along the integration arc Γ_{g^{−1}(γ)}^{z}. By theorem 1.6, we get the expected result leading to the generating function of Dirichlet functions which is the evaluation of the formal series x_{1}(ax_{0})^{∗} •

Note that, from theorem 2.2, we can also deduce some following summations of polylogarithms which are the special case of theorem 2.2 (b = 1), as already traited in [19]

(1) ∑_{n≥0}(−1)^{n} Li_{n+1}(z)  = \frac{1}{z} log(\frac{1}{1 − z} ) − 1,
(2) ∑_{p≥1}(−1)^{p−1} Li_{2p}(z)  = ∑_{k≥1} \frac{z^{k}}{1 + k^{2}} ,
(3) ∑_{p≥0}(−1)^{p} Li_{2p+1}(z)  = ∑_{k≥1} \frac{kz^{k}}{1 + k^{2}} ,
(4) ∑_{n≥0}(−1)^{n}n Li_{n+1}(z)  = 1 − \frac{1}{z} Li_{2}(z),
(5) ∑_{n≥1}(1 − \frac{1}{k} )^{n} Li_{n}(−z^{k}) = −\frac{k^{2}z^{k−1}}{k − 1} ∫_{0}^{z} \frac{ds}{1 + s^{k}} , (k > 1).

Therfore, for ζ(n) = Li_{n}(1) and η(n) = − Li_{n}(−1), we have

(1′) ∑_{n≥1}(−1)^{n}η(n)  = log 2 − 1,
(2′) ∑_{p≥1}(−1)^{p}η(2p)  = ∑_{k≥1} \frac{(−1)^{k}}{1 + k^{2}}  = \frac{π}{e^{π} − 1} − \frac{π}{e^{2π} − 1} − \frac{1}{2},
(2′′) ∑_{p≥1}(−1)^{p−1}ζ(2p)  = ∑_{k≥1} \frac{1}{1 + k^{2}}  = \frac{π}{e^{2π} − 1} + \frac{π}{2} − \frac{1}{2},
(3′) ∑_{p≥1}(−1)^{p}η(2p − 1) = ∑_{k≥1} \frac{(−1)^{k}k}{1 + k^{2}} ,
(4′) ∑_{n≥2}(−1)^{n}nη(n + 1) = \frac{π^{2}}{6} − 1,
(4′′) ∑_{n≥2}(−1)^{n}nζ(n + 1) = 1,
(5′) ∑_{n≥1}(\frac{k − 1}{k})^{n}η(n) = \frac{k^{2}}{k − 1} ∫_{0}^{1} \frac{ds}{1 + s^{k}} ,  (k > 1).

From (5), we can also extract the following summations of polylogarithms

∑_{n≥1}(\frac{1}{2})^{n} Li_{n}(z^{2}) = 4z argth z,
∑_{n≥1}(\frac{1}{2})^{n} Li_{n}(−z^{2}) = −4z arctan z,
∑_{n≥1}(\frac{2}{3})^{n} Li_{n}(z^{3}) = \frac{3z^{2}}{2} [log (\frac{\sqrt{z + 1 + z^{2}}}{z − 1} ) + \sqrt{3} arctan (\frac{\sqrt{3}}{3}(2z + 1)) − \frac{\sqrt{3}}{6}π + iπ],
∑_{n≥1}(\frac{2}{3})^{n} Li_{n}(−z^{3}) = \frac{3z^{2}}{2} [log(\frac{\sqrt{1 − z + z^{2}}}{z + 1} ) − \sqrt{3} arctan(\frac{\sqrt{3}}{3}(2z + 1)) − \frac{\sqrt{3}}{6}π],
∑_{n≥1}(\frac{3}{4})^{n} Li_{n}(z^{4}) = \frac{8z^{3}}{3} (argth z + arctan z),
∑_{n≥1}(\frac{3}{4})^{n} Li_{n}(−z^{4}) = \frac{4\sqrt{2}z^{2}}{3} [\frac{1}{2} log(\frac{z^{2} − \sqrt{2}z + 1}{z^{2} + \sqrt{2}z + 1}) − arctan(\sqrt{2}z + 1) − arctan(\sqrt{2}z − 1)],
⋮

yielding the following summations of series (see also (5′))

∑_{n≥1}(\frac{1}{2})^{n}η(n) = π, ∑_{n≥1}(\frac{2}{3})^{n}η(n) = \frac{3}{2} log 2 + \frac{\sqrt{3}}{2}π, ∑_{n≥1}(\frac{3}{4})^{n}η(n) = \frac{2\sqrt{2}}{3}[log(3 + \sqrt{2}) + π].

2.6 Nielsen functions

In this section, we are interested in the Dirichlet functions obtained from higher level Lyndon-Širšov words.

2.6.1 Lyndon-Širšov words and Nielsen polylogarithms

We can also obtain Nielsen polylogarithms in example 2.1 as the evaluation of the words x_{1}^{p}x_{0}^{n−1} and x_{1}x_{0}^{n−1}x_{1}x_{0}^{p−1} with respect to dβ_{x_{0}} = dz/z and dβ_{x_{1}} = dz/(1 − z) [20]

s_{n,p}(z) = β_{0}^{z}(x_{1}^{p}x_{0}^{n−1}) and c_{n,p}(z) = β_{0}^{z}(x_{1}x_{0}^{n−1}x_{1}x_{0}^{p−1}).

Now, the algebraic relations between the Lyndon-Širšov words for the shuffle structure find a natural interpretation as algebraic relations between Nielsen polylogarithms. For example, for the reverse lexicographical order over X induced by x_{0} < x_{1}, we obtain

• x_{1}x_{0}x_{1}x_{0} = −1/2(x_{1}x_{0})^{_{⊔⊔} 2} − 2x_{1}^{2}x_{0}^{2} and x_{1}x_{0}^{2}x_{1}x_{0}^{2} = 1/2(x_{1}x_{0}^{2})^{_{⊔⊔} 2} − 3x_{1}x_{0}x_{1}x_{0}^{3} − 6x_{1}^{2}x_{0}^{4},

thus

c_{2,2}(z) = −1/2[Li_{2}(z)]^{2} − 2s_{3,2}(z) and c_{3,3}(z) = 1/2[Li_{3}(z)]^{2} − 3c_{2,4}(z) − 6s_{5,2}(z).

In the same way, we also get

• (x_{1}x_{0})^{_{⊔⊔} 2}x_{0} = 4x_{1}^{2}x_{0}^{3} + 2x_{1}x_{0}x_{1}x_{0}^{2} and (x_{1}x_{0}^{2})^{_{⊔⊔} 2}x_{0} = 12x_{1}^{2}x_{0}^{5} + 6x_{1}x_{0}x_{1}x_{0}^{4} + 2x_{1}x_{0}^{2}x_{1}x_{0}^{3}.

We can then deduce the following relations

∫_{0}^{z}[Li_{2}(s)]^{2} \frac{ds}{s} = 4s_{4,2}(z) + 2c_{2,3}(z) and ∫_{0}^{z}[Li_{3}(s)]^{2} \frac{ds}{s} = 12s_{6,2}(z) + 6c_{2,5}(z) + 2c_{3,4}(z),

and their values at the singularities via the special values, s_{n,p}(1) and c_{n,p}(1), already obtained by Nielsen in [31, 32] (see also [20, 21]).

2.6.2 Nielsen functions

More generally, by evaluating the family of all the Lyndon-Širšov words with respect to

dα_{x_{0}} = \frac{dg}{g} and dα_{x_{1}} = F (g)\frac{dg}{g} ,

we obtain the family of Nielsen functions, as an extension of the family of Nielsen polylogarithms.

Definition 2.3 We define the Nielsen function associated to the Lyndon-Širšov word b as the function

Ni_{b}(F |g) = α(R_{b}).

Thus Nielsen functions Ni_{b}(F |g) can be recursively computed as follows

dα(R_{b}) = \frac{[α(R_{l_{1}})]^{i_{1}} … [α(R_{l_{k}})]^{i_{k}}}{i_{1}! … i_{k}!} dα_{x} for b = l_{1}^{i_{1}} … l_{k}^{i_{k}}x, x ∈ X, l_{i} ∈ S and l_{1} < … < l_{k}.

Since, in the Lyndon-Širšov basis, for any n and p ≥ 1, one has (see the example 1.1)

R_{x_{1}^{p}x_{0}^{n}} = x_{1}^{p}x_{0}^{n} and R_{x_{1}^{2}x_{0}^{n−1}x_{1}x_{0}^{p−1}} = x_{1}^{2}x_{0}^{n−1}x_{1}x_{0}^{p−1}

and as in example 2.1, suppose now dβ_{x_{0}} = dz/z and dβ_{x_{1}} = dz/(1 − z). We get the following Nielsen functions

β_{0}^{z}(R_{x_{1}^{p}x_{0}^{n−1}}) = ∑_{k≥p} \frac{S_{k}^{(k−p)}}{(k − 1)!} \frac{z^{k}}{k^{n}} and β_{0}^{z}(R_{x_{1}^{2}x_{0}^{n−1}x_{1}x_{0}^{p−1}}) = ∑_{k≥2}[∑_{l=2}^{k−1} \frac{S_{l}^{(l−2)}}{l^{n}(l − 1)!}]\frac{z^{k}}{k^{p}} .

But one has (see the example 1.1)

R_{x_{1}x_{0}x_{1}x_{0}^{2}} = x_{1}x_{0}x_{1}x_{0}^{2} + 2x_{1}^{2}x_{0}^{3}, R_{x_{1}^{2}x_{0}x_{1}x_{0}} = x_{1}^{2}x_{0}x_{1}x_{0} + 3x_{1}^{3}x_{0}^{2}, ….

Therefore, we also obtain the following Nielsen functions (see example 2.1)

\begin{aligned}β_{0}^{z}(R_{x_{1}x_{0}x_{1}x_{0}^{2}}) & = & ∑_{k≥2} H_{k−1}^{(2)} \frac{z^{k}}{k^{3}} + 2 ∑_{k≥2} \frac{S_{k}^{(k−2)}}{(k − 1)!} \frac{z^{k}}{k^{4}} , \\ β_{0}^{z}(R_{x_{1}^{2}x_{0}x_{1}x_{0}}) & = & ∑_{k≥2}[∑_{l=2}^{k−1} \frac{S_{l}^{(l−2)}}{l^{2}(l − 1)!}]\frac{z^{k}}{k^{2}} + 3 ∑_{k≥3} \frac{S_{k}^{(k−3)}}{(k − 1)!} \frac{z^{k}}{k^{3}} , …. \end{aligned}

3 The symbolic integration of the ordinary differential systems with elementary and special functions

In this section, we point out that the evaluation of rational series are the solutions of some meromorphic differential equations systems. These solutions are intimately related to the special functions and their exponentials, following their syntactic descriptions.

Let us present two small examples.

Example 3.1 [4] Let us consider the following linear differential system

dq(z) = [( \begin{matrix}0 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix} ) \frac{dz}{z} + ( \begin{matrix}0 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{matrix} ) \frac{dz}{1 − z} ] q(z)

with q(0) = ( \begin{matrix}0 \\ 0 \\ 1 \end{matrix} ) and y = q_{3}. Then its generating series F_{1} has the following representation

λ = ( 1 0 0 ) , μ(x_{0}) = ( \begin{matrix}0 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix} ) , μ(x_{1}) = ( \begin{matrix}0 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{matrix} ) , γ = ( \begin{matrix}0 \\ 0 \\ 1 \end{matrix} ) .

Thus, we have F_{1} = x_{0}x_{1}. For dα_{x_{0}} = dz/z and dα_{x_{1}} = dz/(1 − z), we obtain

y(z) = α_{0}^{z}(F_{1}) = Li_{2}(z).

Example 3.2 [20] Let us consider the following linear differential system

dq(z) = [( \begin{matrix}1 & 1 \\ 0 & 1 \end{matrix} ) \frac{dz}{z} + ( \begin{matrix}1 & −1 \\ 0 & 1 \end{matrix} ) \frac{dz}{1 − z} ] q(z)

with q(z_{0}) = ( \begin{matrix}0 \\ 1 \end{matrix} ) and y = q_{2}. Then its generating series F_{2} has the following representation

λ = ( 1 0 ) , μ(x_{0}) = ( \begin{matrix}1 & 1 \\ 0 & 1 \end{matrix} ) , μ(x_{1}) = ( \begin{matrix}1 & −1 \\ 0 & 1 \end{matrix} ) , γ = ( \begin{matrix}0 \\ 1 \end{matrix} ) .

Because the two matrices μ(x_{0}) and μ(x_{1}) commute, the generating series is exchangeable and we have (see [20])

F_{2} = ( 1 0 ) [[x_{0}μ(x_{0})]^{∗} ^{⊔⊔}[x_{1}μ(x_{1})]^{∗}] ( \begin{matrix}0 \\ 1 \end{matrix} )
= ( 1 0 ) [( \begin{matrix}x_{0}^{∗} & x_{0}^{∗}x_{0}x_{0}^{∗} \\ 0 & x_{0}^{∗} \end{matrix} )^{⊔⊔} ( \begin{matrix}x_{1}^{∗} & −x_{1}^{∗}x_{1}x_{1}^{∗} \\ 0 & x_{1}^{∗} \end{matrix} )] ( \begin{matrix}0 \\ 1 \end{matrix} )
= x_{0}^{∗} ^{⊔⊔}(−x_{1}^{∗}x_{1}x_{1}^{∗}) + (x_{0}^{∗}x_{0}x_{0}^{∗})^{⊔⊔} x_{1}^{∗}
= −x_{0}^{∗} ^{⊔⊔}(−x_{1}^{∗} ^{⊔⊔} x_{1}) + (x_{0}^{∗} ^{⊔⊔} x_{0})^{⊔⊔} x_{1}^{∗}
= x_{0}^{∗} ^{⊔⊔} x_{1}^{∗} ^{⊔⊔}(x_{0} − x_{1}).

Thus, for dα_{x_{0}} = dz/z and dα_{x_{1}} = dz/(1 − z), we obtain

y(z) = α_{z_{0}}^{z}(F_{2}) = \frac{z}{z_{0}} \frac{1 − z_{0}}{1 − z} log(\frac{z}{z_{0}} \frac{1 − z}{1 − z_{0}} ).

Lemma 3.1 Let Q be a rational series on the letter x. The evaluation of Q is a finite sum of polynomial exponentials on the primitive of the input associated to x

α(Q) = ∑_{finite} R_{j}[α(x)] exp[c_{j}α(x)],

where the c_{j}’s are algebraic numbers and the R_{j}’s are polynomials.

In case dα(x) = dz/z then

α_{z_{0}}^{z}(Q) = ∑_{finite} R_{j}[log(\frac{z}{z_{0}} )](\frac{z}{z_{0}} )^{c_{j}}.

In case dα(x) = dz/(1 − z) then

α_{z_{0}}^{z}(Q) = ∑_{finite} R_{j}[log(\frac{1 − z_{0}}{1 − z} )](\frac{1 − z}{1 − z_{0}} )^{c_{j}}.

Theorem 3.1 For any linear system of differential equations with rational coefficients, if its generating series is exchangeable then its output can be expressed as a finite sum of products of polynomial exponentials on the primitive of the inputs.

\underline{Proof} : It is the direct consequence of the fact that if the rational series S is exchangeable over X then it can be decomposed on partial elements, i.e. it can be written as a finite sum of shuffles of rational series on one letter [20]. We conclude with lemma 3.1 •

Theorem 3.2 [20] For any linear system of differential equations with rational coefficients, if its generating series is finite then its output can be expressed as a polynomial on Nielsen functions.

\underline{Proof} : It is the direct consequence of theorem 1.5 and of definition 2.3 •

Theorem 3.3 For any linear system of differential equations with rational coefficients, if its generating series is a finite sum of rational series in the following form (the c_{0}, c_{1}, …, c_{p} are complex numbers)

(c_{0}x_{0})^{∗}x_{i_{1}}(c_{1}x_{0})^{∗} … x_{i_{p}}(c_{p}x_{0})^{∗}

then its output can be expressed as a finite sum of hypergeometric type functions constructed from the inputs of this system.

\underline{Proof} : It is the direct consequence of the fact that the evaluations, with rational differential forms, of rational series (c_{0}x_{0})^{∗}x_{i_{1}}(c_{1}x_{0})^{∗} … x_{i_{p}}(c_{p}x_{0})^{∗} are hypergeometric type functions [20] •

Theorem 3.4 [20] If the rational series F is nilpotent at order K +1 then its output is polynomial on Nielsen functions indexed by the Lyndon-Širšov words of length at most K.

\underline{Proof} : Let (λ, μ, γ) be the minimal representation of the rational series F. Let us consider the diagonal series ∑_{w∈X^{∗}} w ⊗ w in C I ⟨⟨X⟩⟩ˆ⊗C I ⟨⟨X⟩⟩ ^{4} (here, we equip the left and the right member of “⊗”, with Cauchy product and shuffle product respectively). Since the series S can be obtained as the image of the diagonal series by the morphism μ ⊗ Id_{⊔⊔}, from C I ⟨⟨X⟩⟩ˆ⊗C I ⟨⟨X⟩⟩ to Mn,n^{⊔⊔}(C I ⟨X⟩), in the following way

F = λ[ ∑_{w∈X^{∗}} μ(w)w]γ = λ[(μ ⊗ Id_{⊔⊔})( ∑_{w∈X^{∗}} w ⊗ w)]γ,

then the factorization of this diagonal series [35] allows us to deduce the factorization of F

∑_{w∈X^{∗}} w ⊗ w = ∏_{l∈S reverse lexicographical decreasing} exp_{.⊗_{⊔⊔}} (Q_{l} ⊗ R_{l}),

α(F) = λ[  ∏_{l∈S reverse lexicographical decreasing} exp[μ(Q_{l})α(R_{l})]]γ.

Now, if F is nilpotent at order K + 1 then the previous product is finite. We can suppose, up to some change of basis, that the nilpotent matrices μ(Q_{l})’s are in upper triangular form. Hence each exponential in the product expansion is a polynomial on its entries. So we obtain the expected result •

4C I ⟨⟨X⟩⟩ˆ⊗C I ⟨⟨X⟩⟩ is the completion of C I ⟨⟨X⟩⟩⊗C I ⟨⟨X⟩⟩ for the topology defined by the degree.

The proof of theorem 3.4 also gives a way to write any polynomial in the {R_{l}}_{l∈S} basis and then with the Lyndon-Širšov words. Thus, by comparison with the third item of theorem 1.1, Radford theorem becomes concretely effective.

Theorem 3.5 (Wei-Norman theorem [37, 38]) Let us consider the linear differential equations system with rational coefficients in the following form

\{ \begin{matrix}dq(z) & = & ∑_{i=1}^{m} M_{i}q(z) u_{i}(z)dz, \\ q(z_{0}) & = & γ, \\ y(z) & = & λq(z), \end{matrix}

admitting F as the generating series. If the Lie algebra L generated by the matrices M_{i}’s is solvable then there exists l − m matrices M_{m+1}, …, M_{l} (obtained by bracketing iteratively the matrices M_{1}, …, M_{m}) such that {M_{i}}_{i=1..l} form a basis of L.

There also exists l functions g_{1}, …, g_{l} on the primitives of the inputs such that the output y is a polynomial on g_{1}, …, g_{l} and their exponentials

y = α(F) = λ(e^{g_{1}M_{1}} … e^{g_{l}M_{l}})γ.

Approximative recursive formulas for the g_{1}, …, g_{l} can be obtained by a symbolic translation of the differential equations system sastisfied by the g_{i}. It will be better explained on the following example. This example also shows that the solvability condition for the existence of g_{1}, …, g_{l} is necessary but not sufficient

Example 3.3 Let us consider the differential system of generating series (x_{2}x_{1}^{∗}x_{3} − x_{1})^{∗}, which admits the following linear representation

λ = ( 1 0 ) , μ(x_{1}) = ( \begin{matrix}−1 & 0 \\ 0 & 1 \end{matrix} ) , μ(x_{2}) = ( \begin{matrix}0 & 1 \\ 0 & 0 \end{matrix} ) , μ(x_{3}) = ( \begin{matrix}0 & 0 \\ 1 & 0 \end{matrix} ) , γ = ( \begin{matrix}1 \\ 0 \end{matrix} ) .

One easily verifies that μ([x_{2}, x_{1}]) = 2μ(x_{2}), μ([x_{3}, x_{1}]) = −2μ(x_{3}) and μ([x_{3}, x_{2}]) = μ(x_{1}). The Lie algebra generated by the μ(x_{i}) is of dimension 3 and it is not solvable. Since

\begin{aligned}e^{g_{1}ad_{μ(x_{1})}} μ(x_{2}) & = & e^{−2g_{1}} μ(x_{2}), \\ e^{g_{2}ad_{μ(x_{2})}} μ(x_{3}) & = & μ(x_{3}) + g_{2}μ(x_{1}) + g_{2}^{2}μ(x_{2}), \\ e^{g_{1}ad_{μ(x_{1})}} e^{g_{2}ad_{μ(x_{2})}} μ(x_{3}) & = & e^{2g_{1}} μ(x_{3}) + g_{2}μ(x_{1}) + g_{2}^{2} e^{−2g_{1}} μ(x_{2}), \end{aligned}

one has

\begin{aligned}∑_{i=1}^{3} u_{i}μ(x_{i}) & = & ġ_{1}μ(x_{1}) + ġ_{2} e^{g_{1}ad_{μ(x_{1})}} μ(x_{2}) + ġ_{3} e^{g_{1}ad_{μ(x_{1})}} e^{g_{2}ad_{μ(x_{2})}} μ(x_{3}) \\ & = & [ġ_{1} + ġ_{3}g_{2}]μ(x_{1}) + [ġ_{2} e^{−2g_{1}} +ġ_{3}g_{2}^{2} e^{−2g_{1}}]μ(x_{2}) + ġ_{3} e^{2g_{1}} μ(x_{3}). \end{aligned}

Consequently, g_{1}, g_{2} and g_{3} satisfy the following triangular differential system [37, 38]

( ġ_{1} ; ġ_{2} ; ġ_{3} ) = ( \begin{matrix}1 & 0 & −g_{2} e^{−2g_{1}} \\ 0 & e^{2g_{1}} & −g_{2}^{2} e^{−2g_{1}} \\ 0 & 0 & e^{−2g_{1}} \end{matrix} ) ( \begin{matrix}u_{1} \\ u_{2} \\ u_{3} \end{matrix} )

and one has

α[(x_{2}x_{1}^{∗}x_{3} − x_{1})^{∗}] = λ e^{g_{1}μ(x_{1})} e^{g_{2}μ(x_{2})} e^{g_{3}μ(x_{3})} γ = (1 + g_{2}g_{3}) e^{−g_{1}} .

With the change of variables u_{1} = \underline{u}_{1}, u_{2} = \underline{u}_{2} e^{−2g_{1}} and u_{3} = \underline{u}_{3} e^{2g_{1}}, we obtain the simpler triangular differential system for g_{1}, g_{2}, g_{3} and the associated symbolic system of the generating series θ_{1}, θ_{2}, θ_{3}

\{ \begin{matrix}ġ_{1} = \underline{u}_{1} − g_{2}\underline{u}_{3}, \\ ġ_{2} = \underline{u}_{2} − g_{2}^{2}\underline{u}_{3}, \\ ġ_{3} = \underline{u}_{3}. \end{matrix}  \{ \begin{matrix}θ_{1} = \underline{x}_{1} − θ_{2}\underline{x}_{3}, \\ θ_{2} = \underline{x}_{2} − θ_{2}^{_{⊔⊔} 2}\underline{x}_{3}, \\ θ_{3} = \underline{x}_{3}. \end{matrix}

Note that the solution of g_{2} can be obtained by solving the following Riccati equation

(R)  ḟ + \underline{u}_{2}f^{2} − \underline{u}_{3} = 0.

If f_{1} is one particular solution already known of (R) then by substituting f by f_{1} + h in (R), we obtain the following Bernoulli equation (that is the linear equation with respect to 1/h)

(B)  ḣ + 2\underline{u}_{2}f_{1}h + \underline{u}_{2}h^{2} = 0.

The symbolic non linear equation on θ_{2}

θ_{2} = \underline{x}_{2} − θ_{2}^{_{⊔⊔} 2}\underline{x}_{3}

can also be solved iteratively.

4 Application in the study of an integral equation

4.1 Introduction

In the study of the multidimensional quadtrees, many authors have considered the integral equation that can be encoded as follows (d ≥ 1) [8, 9, 11, 12, 24, 25, 26]

(IE) e = p + 2^{d}α(e; x_{1}x_{0}^{d−1}),

with the rational differential forms dα_{x_{1}} = dz/(1 − z) and dα_{x_{0}} = dz/[z(1 − z)]. The solution of this integral equation is then the evaluation of the rational series (2^{d}x_{1}x_{0}^{d−1})^{∗}

e = α[p; (2^{d}x_{1}x_{0}^{d−1})^{∗}].

For d > 0, by Picard iterative method, we can approximate the series (2^{d}x_{1}x_{0}^{d−1})^{∗} by linear combinations of monomials (x_{1}x_{0}^{d−1})^{j}. The evaluation, with the kernel p, of each one gives a Dirichlet function. Actually, by putting g(z) = z/(z − 1) and we get dα_{x_{1}} = −dg/(1 − g) and dα_{x_{0}} = dg/g. Hence, for any ν ≥ 1, we get for example (see [20] for more precision on computations)

\begin{matrix}p & α(p; x_{1}x_{0}^{d−1}) & α(p; x_{1}x_{0}^{d−1}x_{1}x_{0}^{d−1}) \\ 1 & − ∑_{k≥1} \frac{g^{k}}{k^{d}} & ∑_{k≥2} H_{k−1}^{(d)} \frac{g^{k}}{k^{d}} \\ (\frac{z}{z − 1})^{ν} & − ∑_{k≥1} \frac{g^{k+ν}}{(k + ν)^{d}} & ∑_{k≥2}[∑_{l=1}^{k−1} \frac{1}{(l + ν)^{d}} ]\frac{g^{k+ν}}{(k + ν)^{d}} \\ \frac{z^{ν−1}}{(z − 1)^{ν}} & −\frac{d!}{(n + d)!}g^{n+d} & \frac{d!}{(n + d)!} ∑_{k≥2} \frac{g^{k+ν+d}}{(k + ν + d)^{d}} \\ \frac{z^{ν+1}}{(z − 1)^{ν}} & ∑_{k≥2}(k − 1)\frac{g^{k+ν}}{(k + ν)^{d}} & − ∑_{k≥2}[∑_{l=1}^{k−1} \frac{l − 1}{(l + ν)^{d}} ]\frac{g^{k+ν}}{(k + ν)^{d}} \\ \frac{1}{ν!}[log(\frac{1}{1 − z})]^{ν} & − ∑_{k≥ν} \frac{S_{k}^{(k−ν)}}{(k − 1)!} \frac{g^{k}}{k^{d}} & ∑_{k≥ν}[∑_{l=2}^{k−1} \frac{S_{l}^{(l−ν)}}{l^{d}(l − 1)!}]\frac{g^{k}}{k^{d}} \end{matrix}

4.2 Some experimentations with Maple

Differentiating d times, the evaluation of the rational series (2^{d}x_{1}x_{0}^{d−1})^{∗} is equivalent to the integration of the following differential equation (with initial conditions not mentioned here)

((1 − z)\frac{d}{dz} )(z(1 − z)\frac{d}{dz} )^{d−1}e(z) = ((1 − z)\frac{d}{dz} )(z(1 − z)\frac{d}{dz} )^{d−1}p(z) + 2^{d}e(z).

The direct use of Maple does not give a simple solution, except in the case d = 1, where the exact evaluation can be done, for example, via theorem 1.6

e(z) = α[p; (2x_{1})^{∗}] = \frac{1}{(1 − z)^{2}} ∫_{0}^{z}(1 − s)^{2}dp(s)

and in the case d = 2, where the solution can be obtained, as done by Gonnet and Baeza-Yates [8] and by Hoshi and Flajolet [9], by subtitution of the following expressions of K(z, t) and e(z)

\begin{aligned}K(z, t) & = & −\frac{z(1 − t)(14 + (t + 1)z + 2tz^{2}) + 2(1 + 2z)(1 + 2tz) log(t)}{(1 − tz)^{3}}, \\ e(z) & = & p(z) + \frac{2z}{(1 − z)^{2}} ∫_{0}^{1} K(z, t)p(tz)dt, \end{aligned}

in the following differential equation

(z(1 − z)\frac{d}{dz} )^{2}w(z) − 4zw(z) = 4zp(z),

where w(z) = e(z) − p(z). Independently, experimenting with Maple, Labelle and Laforest found the same result [24, 25].

The first author of this paper has verified previous experiences in Maple with Labelle and after applying the variable change u = z/(z−1) (which is involutive!), he also has integrated the following equation (for d = 2)

((1 − u)\frac{d}{du})(u\frac{d}{du})f(u) = ((1 − u)\frac{d}{du})(u\frac{d}{du})π(u) + 4f(u)

on two steps

1. By use of the Maple function dsolve with π(u) as the constant function equal to 1, the following solution is obtained (c_{1} and c_{2} are the integration constants)

f(u) = c_{1}(1 − 4u + 3u^{2}) + c_{2}[−3u + \frac{5}{2} + (1 − 4u + 3u^{2}) log(\frac{u}{u − 1})].

So with a good choose of initial conditions, we can have c_{1} = 1 and c_{2} = 0. After applying the variable change z = u/(u − 1), we get the rational solution conforming to the solution obtained by Labelle and Laforest in [25]

e(z) = \frac{1 + 2z}{(z − 1)^{2}} .

2. By use of the Maple function dsolve with p(u) as the function Dirac(u − t), we obtained the corresponding kernel K(u, t).

For d > 3, we do not obtain interesting expressions with Maple.

4.3 Some other exact computations

For some particular expressions of p(z), Flajolet, Labelle Laforest and Salvy [12] gave the coefficients {e_{n}}_{n≥0} of e(z) via the Euler transform

\begin{matrix}p(z) & e_{n} \\ 1 & \frac{1}{2}n − \frac{1}{4} ∑_{k=2}^{n} \binom{n}{k}(−1)^{k}[k; \frac{1}{2}]! \\ z & n − ∑_{k=2}^{n} \binom{n}{k}(−1)^{k}[∑_{j=2}^{k} \frac{[k]!}{[j]!}] \\ \frac{z}{(1 − z)^{2}} & n + ∑_{k=2}^{n} \binom{n}{k}(−1)^{k}[k]! \\ \frac{z^{b+1}}{1 − z} & 1 + (2^{d} − 1) ∑_{k=b}^{n} \binom{n}{k}(−1)^{k+b+1}[ ∑_{j=b+1}^{k} \binom{j − 2}{b − 1}\frac{[k]!}{[j]!}] \end{matrix}

In particular, for p(z) = z/(1 − z)^{2}, these authors indicate that the generation of the corresponding sequence {e_{n}}_{n≥0} is of hypergeometric type [12]

e(z) = \frac{z}{(1 − z)^{2}} + \frac{z^{2}}{(1 − z)^{3}}_{d+1}F_{d} ({3 − e^{2iπ/d}, …, 3 − e^{2iπ}, 1 \atop 3, …, 3}|\frac{z}{1 − z} ).

4.4 Our goal

For the general case, Labelle and Laforest [25, 26] proved the existence of d formal power series w_{0}(z, t), w_{1}(z, t), …, w_{d−1}(z, t) and a kernel K_{d}(z, t) such that

\begin{aligned}K_{d}(z, t) & = & w_{0}(z, t) + w_{1}(z, t)(− log t) + … + w_{d−1}(z, t)(− log t)^{d−1}, \\ e(z) & = & p(z) + ∫_{0}^{1} K_{d}(z, t)p(tz)dt. \end{aligned}

But these authors do not give an explicit way for computing these kernels {w_{i}(z, t)}_{i=0..d−1}. Therefore, our goal is to find the Volterra equation that satisfies e(z) (see Section 4.4.1) and to construct the class of special functions to express the kernel K_{d}(z, t) after obtaining an associated integral equations system (see Section 4.4.2) and a symbolic equations system (see Section 4.4.3). This work is not yet achieved but it helps us to understand this integral equation and to explain the relations of this equation with special functions by exploiting its syntactic structure.

4.4.1 Convolution equation

Since (2^{d}x_{1}x_{0}^{d−1})^{∗} = 1 + 2^{d}(2^{d}x_{1}x_{0}^{d−1})^{∗}x_{1}x_{0}^{d−1} then

α[p; (2^{d}x_{1}x_{0}^{d−1})^{∗}] = p + 2^{d}α[α[p; (2^{d}x_{1}x_{0}^{d−1})^{∗}x_{1}]; x_{0}^{d−1}].

By theorem 1.6, we can write the equation (IE) in the form of the Volterra equation with separated kernels :

K_{d}(z, s) = \frac{[log(g(z)) − log(g(s))]^{d−1}}{(d − 1)!} = ∑_{j=0}^{d−1} a_{j}(z)b_{j}(s),

where a_{j} = 2^{d}[log(g)]^{j}/j! and b_{j} = [− log(g)]^{d−1−j}/(d − 1 − j)! for any j verifying 0 ≤ j ≤ d − 1. Hence

e(z) = p(z) + ∫_{0}^{z} e(s)K_{d}(z, s)\frac{ds}{1 − s}
= p(z) + ∑_{j=0}^{d−1} a_{j}(z) ∫_{0}^{z} e(s)b_{j}(s)\frac{ds}{1 − s}

= p(z) + ∑_{j=0}^{d−1} a_{j}(z)e_{j}(z),

where, for j = 0, …, d − 1, we set

e_{j}(z) = ∫_{0}^{z} e(s)b_{j}(s)\frac{ds}{1 − s}.

4.4.2 Integral equations system

Multiplying the Volterra equation of 4.4.1 by b_{i}, we obtain then

b_{i}e = b_{i}p + ∑_{j=0}^{d−1} q_{i,j}e_{j},

where, for any i and j = 0, …, d − 1, we set q_{i,j} = b_{i}a_{j}. These new equations give a system of integral equations on the unknowns e_{i}, with the same existence and uniqueness conditions as the equation (IE)

e_{i}(z) = ∫_{0}^{z} p(s)b_{i}(s)\frac{ds}{1 − s} + ∑_{j=0}^{d−1} ∫_{0}^{z} e_{j}(s)q_{i,j}(s)\frac{ds}{1 − s}.

4.4.3 Symbolic equations system

Now, let P be such that β(P) = p/2^{d} and for any i = 0, …, d − 1, let E_{i} be such that β(E_{i}) = e_{i}. Let us also introduce the following integration operators (i, j = 0, …, d − 1)

Q_{i,j} : f ⟼ ∫ f(s)q_{i,j}(s)\frac{ds}{1 − s}.

Note that Q_{i,i}(z) = (−1)^{d−1−i}\binom{d−1}{i}Q_{d−1,d−1} since q_{i,i} = (−1)^{d−1−i}\binom{d−1}{i}q_{d−1,d−1}.

We then obtain the associated symbolic equations system (i = 0, …, d − 1)

E_{i} = P Q_{i,0} + ∑_{j=0}^{d−1} E_{j}Q_{i,j}

that can be solved symbolically using the star lemma, and non commutative continued fractions [10]

E_{d−1} = [P Q_{d−1,0} + ∑_{j=0}^{d−2} E_{j}Q_{1,j}]Q_{d−1,d−1}^{∗}
E_{d−2} = [P [Q_{d−1,0}Q_{d−1,d−1}^{∗}Q_{d−2,d−1} + Q_{d−2,0}]
+ ∑_{j=0}^{d−3} E_{j}[Q_{d−1,j}Q_{d−1,d−1}^{∗}Q_{d−2,d−1} + Q_{d−2,j}]][Q_{d−1,d−2}Q_{d−1,d−1}^{∗}Q_{d−2,d−1} − Q_{d−1,d−1}]^{∗}
⋮ .

Consequently, the resolution of the integral equation issued from the study of search costs in quadtrees, also consists in computing the evaluation of the rational series E_{i} with respect to the differential forms

dβ_{P} = \frac{dp}{2^{d}} and dβ_{Q_{i,j}} = (−1)^{d−1−i}2^{d} \frac{[log(g(z))]^{d−1−i+j}}{(d − 1 − i)!j!} \frac{dz}{1 − z} ,

and the solution is the following sum (to compare with [26])

e(z) = p(z) + 2^{d} ∑_{j=0}^{d−1} \frac{[log(g(z))]^{j}}{j!} β_{0}^{z}(E_{j}).

Note that each rational series E_{j} is of the form P F_{j}, for j = 0, …, d − 1. Therefore, the evaluation of these series can be done in two steps. The first one is the evaluation of the rational series F_{j} over the non commutative variables {Q_{i,j}}_{1≤i,j≤d−1}. From the theorem 3.5, this evaluation is a function on g_{1}, … g_{l}. The second one consists in the “convolution with P ” (see theorem 1.6) leading to the kernels w_{j}(z, t) of [25].

4.4.4 Case d = 2

In the case d = 2, the associated symbolic equations system is the following

\{ \begin{matrix}E_{0} & = & −(P + E_{0})Q_{1,1} + E_{1}Q_{0,1}, \\ E_{1} & = & (P + E_{0})Q_{1,0} + E_{1}Q_{1,1}. \end{matrix}

Applying the star lemma on the second equation, we get E_{1} = (P + E_{0})Q_{1,0}Q_{1,1}^{∗}. Subtituting E_{1} in the first equation, we obtain E_{0} = P [Q_{1,0}Q_{1,1}^{∗}Q_{0,1} − Q_{1,1})^{∗} − 1] and we deduce that E_{1} = P (Q_{1,0}Q_{1,1}^{∗}Q_{0,1} − Q_{1,1})^{∗}. Hence

\begin{aligned}e(z) & = & 4β_{0}^{z}(P) + 4β_{0}^{z}(E_{0}) + 4 log(g(z))β_{0}^{z}(E_{1}) \\ & = & [1 + log(g(z))]β_{0}^{z}[P (Q_{1,0}Q_{1,1}^{∗}Q_{0,1} − Q_{1,1})^{∗}]. \end{aligned}

Therefore, the resolution of the initial equation also consists in computing the evaluation of the rational series P (Q_{1,0}Q_{1,1}^{∗}Q_{0,1} − Q_{1,1})^{∗} with respect to the following differential forms

dβ_{P} = \frac{dp}{4}, dβ_{Q_{1,0}} = 4\frac{dz}{1 − z} , dβ_{Q_{1,1}} = 4 log (\frac{z}{z − 1})\frac{dz}{1 − z} , dβ_{Q_{0,1}} = −4 log^{2} (\frac{z}{z − 1})\frac{dz}{1 − z} .

This evaluation can be done via the evaluation of the rational series (Q_{1,0}Q_{1,1}^{∗}Q_{0,1} − Q_{1,1})^{∗}, as done in example 3.3 (i.e. via integration of the autonomous differential system associated to the generating series (x_{2}x_{1}^{∗}x_{3} − x_{1})^{∗}), followed by a convolution with the “second member”.

5 Syntactic Description ≃ Symbolic Integration

In this work, we have presented a method to investigate the differential systems with meromorphic coefficients, in order to identify the functional equations on special functions, to evaluate the special values of iterated integrals, and to perform some summations of series. This method is based on the encoding of iterated integrals by non commutative words, and then exploits the algebraic properties of formal power series on non commutative variables. We specifically underline the combinatorial properties of special functions established in this context. We have applied them in order to explore the syntactic structure of the integral equation issued from the study of search costs in quadtrees, and we have explained the relations of this equation with special functions.

This also shows that, in order to express the solutions of the differential systems with rational coefficients, a new class of functions is needed, strictly extending the class of hypergeometric functions and Dirichlet functions constructed from the coefficients of these systems.

The correspondence between these syntactic tools and these special functions is possible by use of the various symbolic descriptions of the functional equations and by use of the evaluation transform, considered as a generalization of the inverse Laplace-Borel transform.

References

[1] A. Barkatou.– A rational version of Moser’s algorithm, ISSAC’95, Montréal, Canada, Juillet 1995.

[2] J. Berstel & C. Reutenauer.– Rational series and their languages, Springer-Verlag, 1988.

[3] F. Boussemart.– La simulation graphique interactive des systèmes dynamiques non linéaires conception et réalisation en Scratchpad, Thèse, Université Lille I, Lille 1992.

[4] P. Cartier.– Jacobiennes généralisées, monodromie unipotente et intégrales itérées, séminaire Bourbaki, 40^{ème} année, 1987-1988, N^{∘}687, pp. 31-52.

[5] K.T. Chen.– Iterated path integrals, Bull. Amer. Math., Soc., vol 83, 1977, pp. 831-879.

[6] J.L. Dupont.– On Polylogarithms, Nagoya Math. J., Vol 114, 1989, pp. 1-20.

[7] F.J. Dyson.– The radiation theories of Tomonaga, Schwinger and Feynman, Physical Rev, vol 75, 1949, pp. 486-502.

[8] G. Gonnet & R. Baeza-Yates.– Handbook of Algorithms and Data Structure In Pascal and in C, Addison-Willey, 1991.

[9] M. Hoshi & Ph. Flajolet.– Page usage in quadtree index, BIT, 32, 1992, pp 384-402.

[10] Ph. Flajolet.– Combinatorial Aspects of Continued Fractions, Discrete Mathematics, 32, pp 125-161, 1980.

[11] Ph. Flajolet.– Arbres de recherche, équations différentielles, fonctions hypergéométriques et dilogarithmes, “Fonctions spéciales et Calcul Formel”, Limoges, 1993.

[12] Ph. Flajolet, G. Labelle, L. Laforest & B. Salvy.– Hypergeometrics and the Cost Structure of Quadtrees, in Random Structures and Algorithms, 7, 1995, pp. 117-144.

[13] M. Fliess.– Fonctionnelles causales non linéaires et indéterminées non commutatives, Bull. Soc. Math. France, N^{∘}109, 1981, pp. 3-40.

[14] L. Fuchs.– Zur Theorie der linear Differentialeichungen mit veränderlichen Coefficienten, J. de Crelle, t. LXVI, 1866, pp. 121-160.

[15] Hoang Ngoc Minh.– Evaluation Transform, Theoret. Computer. Sciences, 79, 1991, pp. 163-177.

[16] Hoang Ngoc Minh & G. Jacob.– Evaluation transform and its implementation in MACSYMA, in “New Trends in Systems Theory”, Birkhaüser, Boston, 1991.

[17] Hoang Ngoc Minh.– Chained System Steering With Singular Inputs, “New Computer Technologies in Control Systems”, Pereslavl-Zalessky, Russie, Juillet 1994.

[18] Hoang Ngoc Minh.– Bilinear System Steering With Singular Inputs, “New Computer Technologies in Control Systems”, Pereslavl-Zalessky, Russie, August 1995.

[19] Hoang Ngoc Minh.– Summations of Polylogarithms via Evaluation Transform, in Mathematics and Computers in Simulations, 42, 4-6, 1996, pp. 707-728.

[20] Hoang Ngoc Minh.– Fonction de Dirichlet d’ordre n et de paramètre t, Discrete Math., 180, 1998, pp. 221-241.

[21] Hoang Ngoc Minh & M. Petitot.– Mots de Lyndon : générateurs de relations entre les polylogarithmes de Nielsen, FPSCA’97, Vienne, 14-18 Juillet 1997.

[22] G. Jacob.– Représentation et substitutions matricielles dans la théorie algébrique des transductions, thèse d’Etat, Univ. Paris 7 (1975). “New Computer Technologies in Control Systems”

[23] G. Jacob.– Réalisation des systèmes réguliers (ou bilinéaires) et les séries génératrices non commutatives, Séminaire d’Aussois, RCP 567, dans “Outils et Modèles Mathématiques pour l’Automatique, l’Analyse des Systèmes, et le traitement de Signal”, CNRS, Landau, 1980.

[24] G. Labelle.– Some Combinatorial Results first Found Using Computer Algebra, J. Symbolic Computation, 20, 1995, pp. 567-594.

[25] G. Labelle & L. Laforest.– Etude de constantes universelles pour les arborescences hyperquaternaires de recherche, FPSAC’93, Discrete Math., 153, 1996, pp. 199-211.

[26] G. Labelle & L. Laforest.– Combinatorial variations on multidimensional quadtrees, Journal of Combinatorial Theory - Series A, Academic Press, New York, 69, 1995, pp. 1-16.

[27] J.A. Lappo-Danilevsky.– Théorie des systèmes des équations différentielles linéaires, Chelsea, New York, 1953.

[28] L. Lewin.– Polylogarithms and associated functions, North Holland, New York and Oxford, 1981.

[29] L. Lewin.– Structural properties of polylogarithms, Mathematical survey and monographs, Amer. Math. Soc., vol 37, 1992.

[30] W. Magnus.– On the Exponential Solution of Differential Equation for a Linear Operator, Comm. Pure Appl. Math. 7, 1954, pp. 649-673.

[31] N. Nielsen.– Recherches sur le carré de la dérivée logarithmique de la fonction gamma et sur quelques fonctions analogues, Annali di Matematica, vol 9, 1904, pp. 190-210.

[32] N. Nielsen.– Recherches sur des généralisations d’une fonction de Legendre et d’Abel, Annali di Matematica, vol 9, 1904, pp. 219-235.

[33] D.E. Radford.– A natural ring basis for shuffle algebra and an application to group schemes, Journal of Algebra, 58, pp. 432-454, 1979.

[34] R. Ree.– Lie elements and an associated with shuffles, Ann of Math., 68, 1958, pp. 210-220.

[35] C. Reutenauer.– Free Lie Algebras, London Math. Soc. Monog. 7 (new series), Clarendon Press-Oxford Sciences Publications, 1993.

[36] G. Viennot.– Algèbres de Lie libres et monoïdes libres, Lecture Notes in Mathematics, Springer-Verlag, 691, 1978.

[37] J. Wei & E. Norman.– Lie algebraic solution of linear differentiel equations, J. Math. Phys., 4, 1963, 575-581.

[38] J. Wei & E. Norman.– On global representation of the solution of linear differentiel equations as product of exponentials, Proc. A.M.S., 15, 1964, pp. 327-334.

[39] Z. Wojtkowiak.– A note on functional equations of the p-adic polylogarithms, Bull. Soc. Math. France, N^{∘}119, 1991, pp. 343-370.

[40] Z. Wojtkowiak.– The basic structure of polylogarithmic functional equations, in [29], pp. 205-231.