D-finite Power Series and the Diagonal Theorem

Bruno Haible Mathematisches Institut II Universität Karlsruhe Kaiserstraße 12 D – 76131 Karlsruhe

                     Email: <haible@ma2s2.mathematik.uni-karlsruhe.de>

Michael Stoll Mathematisches Institut der Universität Universität Bonn Beringstraße 4 D – 53115 Bonn

                           Email: <stoll@rhein.iam.uni-bonn.de>

Started: 9 May 1993 Last change: 9 March 1994

Mathematics Subject Classification: 13N10; 11B37, 05A15, 05A19.

This paper gives an introduction into differentiably finite power series and presents a proof and an application of the diagonal theorem.

1. Definitions

Definition 1: An X-differential ring R is an integral domain R of characteristic zero, together with a finite set X = {∂_{1}, …, ∂_{d}} of pairwise commuting derivations ∂_{i} on R. See [Hai], section 2.1. Definition 2: Let R be an X-differential ring. An X-differential R-module M is an R-module M, together with a rule how the derivations of X operate on M: For every ∂ ∈ X there is a map ∂_{M} : M → M (which we denote by the same symbol ∂) such that ∂(f + g) = ∂(f) + ∂(g) for every f, g ∈ M and ∂(af) = ∂(a) · f + a · ∂(f) for every a ∈ R and f ∈ M, and these maps ∂ ∈ Der_{R} (M) must be pairwise commuting. See [Hai], section 2.2. The definitions 1 and 2 can also be found in [Ko], p. 66. Definition 3: Let R be an X-differential ring. An X-differential R-algebra M is an X-differential R-module M together with a (not necessarily commutative) multiplication on M such that (M, ·) is an R-algebra and for every ∂ ∈ X, f, g ∈ M we have ∂(f · g) = ∂(f) · g + f · ∂(g). See [Hai], section 2.3. Proposition 1:

(a) If R is an X-differential ring, then R[z] is an (X ∪ {∂_{z}})-differential ring, where ∂_{z} denotes the usual partial derivative with respect to z, uniquely determined by ∂_{z}| R = 0 and ∂_{z}(z) = 1.

(b) If M is an X-differential R-module, then M[ ; [z] ; ] is an (X ∪ {∂_{z}})-differential R[z]-module, where the operation of ∂_{z} on M[ ; [z] ; ] is defined by ∂_{z}(∑_{i=0}^{∞} f_{i}z^{i}) = ∑_{i=1}^{∞} if_{i}z^{i−1}. Furthermore, if M is a torsion-free R-module, then M[ ; [z] ; ] is a torsion-free R[z]-module.

Proof: See [Hai], section 2.5. Proposition 2:

(a) If R is an X-differential ring, then the quotient field Quot (R) is an X-differential ring.

(b) If M is an X-differential R-module, then M̃ := (R \ {0})^{−1}M = Quot (R) ⊗_{R} M is an X-differential Quot (R)-module, especially a Quot (R) vector space.

(c) If M is an X-differential R-algebra, then M̃, defined as in (b), is an X-differential Quot (R)-algebra. Proof: See [Hai], sections 2.6, 2.7, 2.8.

2. D-finiteness in general

Definition 4: Let M be an X-differential R-module. Put R̃ := Quot (R) and M̃:= (R \ {0})^{−1}M; then M̃ is an X-differential R̃-module as in Prop. 2. Let λ : M → M̃ be the canonical map. For f ∈ M let f̃:= λ(f) ∈ M̃ be its image and A(f) := ∑_{n∈IN^{d}} R̃ · ∂^{n}f̃ (with ∂^{n}f̃ meaning ∂_{1}^{n_{1}} ⋯ ∂_{d}^{n_{d}} f̃) the span of all its derivatives, a subspace of the

R̃-vector space M̃. f is called differentiably finite – or D-finite for short –, and we then write f ∈ D(R, M, X),

if dim_{R} A(f) < ∞.

See [Hai], section 2.9. Proposition 3: Let M be an X-differential R-module. Then

(a) 0 ∈ D(R, M, X).

(b) If f ∈ D(R, M, X), then −f ∈ D(R, M, X).

(c) If f, g ∈ D(R, M, X), then f + g ∈ D(R, M, X).

(d) If f ∈ D(R, M, X) and a ∈ R, then a · f ∈ D(R, M, X).

(e) If M is an X-differential R-algebra and f, g ∈ D(R, M, X), then f · g ∈ D(R, M, X).

(f) If R ⊂ M, then R ⊂ D(R, M, X) ⊂ M.

(g) D(R, M, X) is an X-differential R-module.

Furthermore, if M is an X-differential R-algebra, then D(R, M, X) is, too. Proof: (See [Hai], section 2.10.)

(a) dim A(0) = 0.

(b) A(−f) = A(f).

(c) A(f + g) ⊂ A(f) + A(g).

(d) A(a · f) ⊂ A(f).

(e) A(f · g) ⊂ A(f) · A(g) by the Leibniz rule, so dim A(f · g) ≤ dim A(f) · A(g) ≤ dim A(f) ⊗ ; _{R} A(g) = dim A(f) · dim A(g).

(f) For a ∈ R, we have dim A(a) ≤ 1.

(g) Follows from (a) to (e) and the fact that D(R, M, X) is closed w.r.t. taking derivatives because A(∂_{i}f) ⊂

A(f).

q.e.d.

Proposition 4: Let M be a commutative X-differential R-algebra with 1 ∈ M, and f ∈ M.

(a) If f is algebraic over R, then f ∈ D(R, M, X).

(b) If for every i ∈ {1, …, d} there is an element g_{i} ∈ M algebraic over R such that ∂_{i}f = g_{i}f, then f ∈ D(R, M, X).

Proof: Denote by \left⟨{ \atop f}\right⟩ the subalgebra of M̃ generated by f̃, i.e. the R̃-vector space generated by 1, f̃, f̃^{2}, . . ..

(a) N := \left⟨{ \atop f}\right⟩ is a field, a finite extension of R̃. We have an equation P \binom{}{f} = 0 with a polynomial P ∈ R̃[T]

of minimum degree. For i ∈ \{1, …, d\} we then have 0 = ∂_{i}(P \binom{}{f}) = P′\binom{}{f} · ∂_{i}f̃+ (∂_{i}P)\binom{}{f}. Because

of characteristic zero P′\binom{}{f} ≠ 0, and it follows that ∂_{i}f̃ ∈ N. Thus A(f) ⊂ N, and dim_{R} A(f) ≤

dim_{R} N < ∞.

(b) Put N := ⟨g̃_{1}, …, g̃_{d}⟩. Then A(f) ⊂ Nf, and it follows dim_{R} A(f) ≤ dim_{R} N ≤ ∏_{i=1}^{d} deg g̃_{i} < ∞.

q.e.d.

Proposition 5:

(a) D-finiteness w.r.t. to X is equivalent to simultaneous D-finiteness w.r.t. every single derivation in X:

D(R, M, X) = ⋂_{i=1}^{d} D(R, M, {∂_{i}})

(b) For a single derivation ∂:

D(R, M, {∂}) = {f ∈ M : there is a linear differential operator L ∈ R[∂] \ {0} with Lf = 0}

Proof:

(b) Trivial; see [Hai], section 2.9.

(a) (See [Hai], section 2.11.) Let f ∈ D(R, M, X). Then for any i, A_{{∂_{i}}}(f) ⊂ A_{X}(f), which is finite-

dimensional, so f ∈ D(R, M, {∂_{i}}). On the other hand, let f ∈ ⋂_{i=1}^{d} D(R, M, {∂_{i}}). For i ∈ {1, …, d}

find a nonzero differential operator L_{i} ∈ R[∂_{i}] with L_{i}f = 0. Put n_{i} := max (deg L_{i}, 1). Then

A(f) = ∑_{0≤m_{1}<n_{1} ; {... \atop 0≤m_{d}<n_{d}}} R̃ · ∂_{1}^{m_{1}} ⋯ ∂_{d}^{m_{d}}f

and so dim A(f) ≤ n_{1} ⋯ n_{d} < ∞.

q.e.d.

3. D-finiteness over polynomial rings

We now specialize in the situation where R is a polynomial ring. Let G, the ground ring, be a Y -differential ring. Then the polynomial ring R := G[z_{1}, …, z_{d}] is an X-differential ring with X = Y ∪ Z and Z = {∂_{z_{1}}, …, ∂_{z_{d}}}, by Prop. 1(a). We will write Z = {∂_{1}, …, ∂_{d}}. Definition 5: The ring of differential operators with polynomial coefficients A := G[z_{1}, …, z_{d}, Y, Z] is the free noncommutative G[Y]-algebra with the generators z_{1}, …, z_{d}, ∂_{1}, …, ∂_{d} modulo the relations

z_{i}z_{j} = z_{j}z_{i} ∀i, j
∂_{i}∂_{j} = ∂_{j}∂_{i} ∀i, j
∂_{i}z_{j} = z_{j}∂_{i} + δ_{i,j} ∀i, j,

and G[Y] is a non-commutative ring (∂a = a∂ + ∂(a) for a ∈ G and ∂ ∈ Y). A is called the d-th Weyl algebra over G[Y]. Some notation: We will enumerate Y as Y = {∂_{−1}, …, ∂_{−e}}. For α ∈ IN^{d} we write z^{α} = z_{1}^{α_{1}} ⋯ z_{d}^{α_{d}} and |α| = α_{1} + ⋯ + α_{d}. For (β, γ) ∈ IN^{d} × IN^{e} we write ∂^{(β,γ)} = ∂_{Z}^{β}∂_{Y} ^{γ} = ∂_{1}^{β_{1}} ⋯ ∂_{d}^{β_{d}}∂_{−1}^{γ_{1}} ⋯ ∂_{−e}^{γ_{e}}. We have

A = ⨁_{{α∈IN^{d} \atop β∈IN^{d+e}}} G · z^{α}∂^{β}

Definition 6: A filtration of a non-commutative G-algebra A is a sequence (A_{n}) of finite-dimensional G-modules A_{n} such that

A = ⋃_{n=0}^{∞} A_{n}, A_{n} ⊂ A_{n+1} for every n and A_{n} · A_{m} ⊂ A_{n+m} for every n, m. Here and henceforth we define the

dimension of a G-module V by dim_{G} V := dim_{Quot (G)} (G \ {0})^{−1}V = dim_{Quot (G)} Quot (G) ⊗_{G} V.

The Weyl algebra A has the filtration (A_{n}), with

A_{n} = ⨁_{{α∈IN^{d} \atop β∈IN^{d+e}} ; |α|+|β|≤n} G · z^{α}∂^{β}

This is because the multiplication on A is defined in such a way that

∂^{β}z^{α} = ∏_{i=1}^{d} (∑_{ν≥0} ν!\binom{α_{i}}{ν}\binom{β_{i}}{ν}z_{i}^{α_{i}−ν}∂_{i}^{β_{i}−ν} ) · ∏_{i=−e}^{−1} ∂_{i}^{β_{i}}

Let now M be an X-differential R-module. We then define an operation of A on M by putting

(∑_{α,β} c_{α,β}z^{α}∂^{β}) · f := ∑_{α,β} c_{α,β} · z^{α} · ∂^{β}(f)

for c_{α,β} ∈ R (α ∈ IN^{d}, β ∈ IN^{d+e}) and f ∈ M. Lemma 6: Let f ∈ M. If there is a subalgebra A′ of A such that

dim_{G} (A′ ∩ A_{n}) ≥ c · n^{d+1} for n >> 0 and some c > 0

but

dim_{G} (A′ ∩ A_{n})f = O(n^{d}) for n >> 0,

then there is a differential operator L ∈ A′ \ {0} with Lf = 0. Proof: The map

\{ \begin{matrix}A′ ∩ A_{n} & → & (A′ ∩ A_{n})f \\ L & ↦ & Lf \end{matrix}\}

is G-linear. For n sufficiently large it can’t be injective because we have dim_{G} (A′ ∩ A_{n})f < dim_{G} (A′ ∩ A_{n}). q.e.d.

In the following, we will also make use of the standard filtration of R = G[z_{1}, …, z_{d}] itself: R = ⋃_{n=0}^{∞} R_{n} with

R_{n} = ⨁_{{α∈IN^{d} \atop |α|≤n}} G · z^{α} = \{h ∈ R : deg_{z_{1},...,z_{d}} h ≤ n\}.

Lemma 7: If f ∈ D(R, M, X), then there exists an r ∈ IN, an s ∈ R_{r} \ {0} and a finite set J ⊂ IN^{d+e} such that for every β ∈ IN^{d+e}:

s^{|β|} · ∂^{β}f ∈ ∑_{α∈J} R_{r|β|} · ∂^{α}f

Proof: (This is a generalization of [Hai], 2.15.) The assumption is equivalent to dim_{R} A(f) < ∞. So a finite set of derivatives of f̃ suffices to generate A(f):

A(f) = ∑_{α∈J} R̃ · ∂^{α}f̃

with J finite. We may assume 0 ∈ J (otherwise extend J). Put t := 1 + max_{α∈J} |α|. For every β ∈ IN^{d+e} with |β| ≤ t there is an equation

∂^{β}f̃ = ∑_{α∈J} c̃_{β,α}∂^{α}f̃

with c̃_{β,α} ∈ R̃ for every β and α. Considering common denominators, we can bring every such equation to the form

c_{β} · ∂^{β}f = ∑_{α∈J} (c_{β}c̃_{β,α})∂^{α}f

with c_{β} ∈ R \ {0} and c_{β}c̃_{β,α} ∈ R for every α. Let s be a common nonzero multiple of all the c_{β}. Then for every β with |β| ≤ t we have an equation

s · ∂^{β}f = ∑_{α∈J} c_{β,α}∂^{α}f

with c_{β,α} ∈ R for every α. Put r := max ({deg s} ∪ {deg c_{β,α} : α ∈ J, |β| ≤ t}). We now prove the claim by induction on |β|. The case β = 0 is clear because of 0 ∈ J. Now the induction step. Assume the claim for ∂^{β}:

s^{|β|} · ∂^{β}f = ∑_{α∈J} h_{β,α} · ∂^{α}f with h_{β,α} ∈ R_{r|β|}

and apply any fixed ∂_{0} ∈ X:

s^{|β|} · ∂_{0}∂^{β}f + |β|∂_{0}(s)s^{|β|−1} · ∂^{β}f = ∂_{0}(s^{|β|} · ∂^{β}f) = ∑_{α∈J} ∂_{0}(h_{β,α} · ∂^{α}f)

We have ∂_{0}(R_{n}) ⊂ R_{n} (this is clear if ∂_{0} ∈ Y because then ∂_{0} operates separately on every coefficient, and for ∂_{0} ∈ Z we even have ∂_{0}(R_{n}) ⊂ R_{n−1}). This implies deg ∂_{0}(s) ≤ deg s ≤ r. We thus get (after multiplication by s)

s^{|β|+1} · ∂_{0}∂^{β}f = −|β|∂_{0}(s)s^{|β|} · ∂^{β}f + ∑_{α∈J} s∂_{0}(h_{β,α})∂^{α}f + ∑_{α∈J} sh_{β,α}∂_{0}∂^{α}f

= ∑_{α∈J} (−|β|∂_{0}(s)h_{β,α} + s∂_{0}(h_{β,α}))∂^{α}f + ∑_{α∈J} h_{β,α} · s∂_{0}∂^{α}f

∈ ∑_{α∈J} R_{r+r|β|}∂^{α}f + ∑_{α∈J} R_{r|β|}(∑_{γ∈J} R_{r}∂^{γ}f)

⊂ ∑_{α∈J} R_{r(1+|β|)}∂^{α}f

This proves the claim for ∂_{0}∂^{β}. q.e.d.

Theorem 8: Let M be a torsion-free X-differential R-module. Then f ∈ D(R, M, X) if and only if dim_{G} A_{n}f = O(n^{d}) for n >> 0.

Proof:

“⇒” Invoking Lemma 7, we get r, s and J. Since the map \{ \begin{matrix}M & → & M \\ g & ↦ & s · g \end{matrix}\} is an injective G-module homo-

morphism, we have

dim_{G} (A_{n}f) = dim_{G} (s^{n}A_{n}f).

By Lemma 7,

s^{n}A_{n}f = ∑_{{k∈IN,β∈IN^{d+e} \atop k+|β|≤n}} s^{n} · R_{k} · ∂^{β}f

= ∑_{{k,β \atop k+|β|≤n}} R_{k} · s^{n−|β|} · s^{|β|}∂^{β}f

⊂ ∑_{{k,β \atop k+|β|≤n}} R_{k}R_{r(n−|β|)} · ∑_{α∈J} R_{r|β|}∂^{α}f

⊂ ∑_{α∈J} ( ∑_{{k,β \atop k+|β|≤n}} R_{k}R_{r(n−|β|)}R_{r|β|})∂^{α}f

⊂ ∑_{α∈J} (∑_{k≤n} R_{k+rn})∂^{α}f

= ∑_{α∈J} R_{(r+1)n}∂^{α}f

Thus dim_{G} (s^{n}A_{n}f) ≤ #J · dim_{G} R_{(r+1)n} = #J · \binom{(r+1)n+d}{d} = O(n^{d}). “⇐” For any ∂ ∈ X we can apply Lemma 6 to A′ := R[∂] since

dim_{G} (A′ ∩ A_{n}) = dim_{G} ⨁_{|α|+k≤n} G · z^{α}∂^{k} = \binom{n + d + 1}{d + 1} ∼ \frac{n^{d+1}}{(d + 1)!}

and dim_{G} (A′ ∩ A_{n})f ≤ dim_{G} A_{n}f = O(n^{d}) for n >> 0. We thus get a differential operator L ∈ R[∂] \ {0} with Lf = 0 and have verified that f ∈ D(R, M, {∂}). By Prop. 5 we have f ∈ D(R, M, X).

q.e.d.

4. Substitutions

Let M be a torsion-free X-differential R-module. By Prop. 1, M\begin{aligned}[ \\ [ & y_{1}, …, y_{r} & ] \\ & ] \end{aligned} is an (X ∪ Y)-differential R[y_{1}, …, y_{r}]-module, and M\begin{aligned}[ \\ [ & z_{1}, …, z_{s} & ] \\ & ] \end{aligned} is an (X ∪ Z)-differential R[z_{1}, …, z_{s}]-module. For short, we write R[Y] for R[y_{1}, …, y_{r}] etc. and put R(Z) := Quot (R[Z]). Let N ≤ M[ ; [Y] ; ] be an R[Y]-sub-differential-module. We call σ = (y_{1} ← σ_{1}, …, y_{r} ← σ_{r}) with all σ_{i} ∈ R[ ; [Z] ; ] a valid substitution on N if

σ^{∗} : \{ \begin{matrix}N & → & M[ ; [Z] ; ] \\ g(y_{1}, …, y_{r}) & ↦ & g(σ_{1}, …, σ_{r}) \end{matrix}\}

is well defined. (If N = M[Y], any σ is valid. If N = M[ ; [Y] ; ], σ is valid if σ_{i}(0, …, 0) = 0 for all i.) Theorem 9:

If σ_{1}, …, σ_{r} are algebraic over R(Z) and f ∈ D(R[Y], N, X ∪ Y), then σ^{∗}(f) ∈ D(R[Z], M[ ; [Z] ; ], X ∪ Z).

Proof: (Cf. [Hai] 2.13.) σ also induces a ring homomorphism

σ_{R}^{∗} : \{ \begin{matrix}R[Y] & → & R[σ_{1}, …, σ_{r}] ⊂ R[ ; [Z] ; ] \\ g(y_{1}, …, y_{r}) & ↦ & g(σ_{1}, …, σ_{r}) \end{matrix}\} .

1. Case 1: σ_{R}^{∗} is injective. Then it induces a field homomorphism σ_{R}^{∗} : R(Y) → K, where

K := R(Z)(σ_{1}, …, σ_{r})

is a finite field extension of R(Z) by the assumption. Because of characteristic 0, the derivations ∂ ∈ X ∪ Z can be extended from R(Z) to K, so that ∂(σ_{i}) ∈ K for all i. By the chain rule, we have for any ∂ ∈ X ∪ Z and any g ∈ (R[Y] \ {0})^{−1}N:

∂(σ^{∗}(g)) = ∑_{i=1}^{r} ∂(σ_{i}) · σ^{∗}(∂_{y_{i}}(g)) + \{ \begin{matrix}σ^{∗}(∂(g)) & if ∂ ∈ X \\ 0 & if ∂ ∈ Z \end{matrix} \}

(this equation being valid in (R[Z] \ {0})^{−1}M[ ; [Z] ; ]). This shows that ∑_{α∈IN^{#X+r}} K ·σ^{∗}(∂_{X∪Y} ^{α}(f)) is closed

with respect to taking a derivative ∂ ∈ X ∪ Z, giving

A_{X∪Z}(σ^{∗}(f)) ⊂ ∑_{α} K · σ^{∗}(∂_{X∪Y} ^{α}(f)).

A_{X∪Y} (f) is finitely generated over R(Y) by the assumption: A_{X∪Y} (f) = ∑_{α∈J} R(Y) · ∂_{X∪Y} ^{α}(f) with #J < ∞. Applying σ^{∗}, it follows that

∑_{α} K · σ^{∗}(∂_{X∪Y} ^{α}(f)) = ∑_{α∈J} K · σ^{∗}(∂_{X∪Y} ^{α}(f))

and therefore

dim_{R(Z)} A_{X∪Z}(σ^{∗}(f)) ≤ dim_{R(Z)} ∑_{α} K · σ^{∗}(∂_{X∪Y} ^{α}(f))
≤ dim_{R(Z)} K · #J < ∞

2. Case 2: s = r − 1 and σ_{1} = z_{1}, …, σ_{s} = z_{s}, σ_{r} = 0. Then σ^{∗} simply puts a zero in the last coordinate. For every ∂ ∈ X ∪ {∂_{y_{1}}, …, ∂_{y_{s}}} there is a nonzero differential operator L ∈ R[Y][∂] with Lf = 0. Write L as L = ∑_{j∈IN} y_{r}^{j}L_{j} with L_{j} ∈ R[y_{1}, …, y_{s}][∂]. Since M[ ; [Y] ; ] is a torsion-free R[Y]-module, we can replace L by \frac{1}{y_{r}} L until we reach L_{0} ≠ 0. Then L_{0}σ^{∗}(f) = σ^{∗}(L)σ^{∗}(f) = σ^{∗}(Lf) = 0.

3. Case 3: s ≤ r and σ_{1} = z_{1}, …, σ_{s} = z_{s}, σ_{s+1} = 0, …, σ_{r} = 0. This is done by applying case 2 r − s times.

4. Case 4: the general case. Split

g(y_{1}, …, y_{r})↦^{σ^{∗}}g(σ_{1}(Z), …, σ_{r}(Z))

into

g(y_{1}, …, y_{r})↦^{τ^{∗}}g(σ_{1}(Z) + w_{1}, …, σ_{r}(Z) + w_{r})↦^{ν^{∗}}g(σ_{1}(Z), …, σ_{r}(Z))

where

w_{1}, …, w_{r} are new variables,
τ = (y_{1} ← σ_{1}(Z) + w_{1}, …, y_{r} ← σ_{r}(Z) + w_{r}) and
ν = (z_{1} ← z_{1}, …, z_{r} ← z_{r}, w_{1} ← 0, …, w_{r} ← 0).

τ^{∗} is injective (the inverse substitution is (z_{1} ← 0, …, z_{r} ← 0, w_{1} ← y_{1} − σ_{1}(0), …, w_{r} ← y_{r} − σ_{r}(0))), and the result follows by applying the cases 1 and 3.

q.e.d.

5. The Diagonal Theorem

Theorem 10: The diagonal theorem. Let H be a torsion-free Y -differential G-module. Put R := G[z_{1}, …, z_{d}], M := H\begin{aligned}[ \\ [ & z_{1}, …, z_{d} & ] \\ & ] \end{aligned} and X := Y ∪ Z. By Prop. 1, M is an X-differential R-module. Given a_{1}, …, a_{d} ∈ ℤ and b ∈ ℤ we form the equation a_{1}α_{1} + ⋯ + a_{d}α_{d} = b, which we also write as a^{⊤}α = b, and the diagonal operator

∇ : \{ \begin{matrix}M & → & M \\ f = ∑_{α∈IN^{d}} f_{α}z^{α} & ↦ & ∇f = ∑_{{α∈IN^{d} \atop a^{⊤}α=b}} f_{α}z^{α} \end{matrix}\}

which cuts out a certain “diagonal” from f. The claim is: If f ∈ D(R, M, X), then ∇f ∈ D(R, M, X). The name “diagonal theorem” comes from the following Corollary 11: Let M be a torsion-free X-differential R-module and

f = ∑_{α,β∈IN} f_{α,β}y^{α}z^{β} ∈ D(R[y, z], M\begin{aligned}[ \\ [ & y, z & ] \\ & ] \end{aligned}, X ∪ \{∂_{y}, ∂_{z}\}).

Then

diagf := ∑_{α∈IN} f_{α,α}y^{α} ∈ D(R[y], M[ ; [y] ; ], X ∪ {∂_{y}}).

Proof of the Corollary: The equation for the exponents is α − β = 0. By Theorem 10, ∇_{α−β}(f) = ∑_{α∈IN} f_{α,α}y^{α}z^{α} is in D(R[y, z], N, X ∪ {∂_{y}, ∂_{z}}). where N denotes the sub- (X ∪ \{∂_{y}, ∂_{z}\})-differential R[y, z]-module M[y, z]\begin{aligned}[ \\ [ & yz & ] \\ & ] \end{aligned} of M\begin{aligned}[ \\ [ & y, z & ] \\ & ] \end{aligned}. Apply the substitution σ = (z ← 1) which is well-defined on N. The claim then follows from Theorem 9. Proof of the Theorem: (Our statement of the diagonal theorem is more general than the one proved in [Li1]. The following proof grew out of the proof given in [Hai] 2.18.) We may assume that ℚ ⊂ G, otherwise we replace G by (ℤ \ {0})^{−1}G and H by (ℤ \ {0})^{−1}H. If either all the a_{i} ≥ 0 or all the a_{i} ≤ 0, we may assume all the a_{i} ≥ 0. Renumbering the variables, we may assume a_{1}, …, a_{k} > 0 and a_{k+1} = ⋯ = a_{d} = 0. Then the solution set of the equation is {α ∈ IN^{d} : a^{⊤}α = b} = I × IN^{n−k} where I ⊂ IN^{k} is a finite set. Now

∇f = ∑_{(α_{1},...,α_{k})∈I} ∑_{α_{k+1},...,α_{d}∈IN} f_{α}z^{α} = ∑_{β∈I} (z_{1} ← 0, …, z_{k} ← 0)^{∗}(\frac{1}{β!}∂_{z_{1}}^{β_{1}} ⋯ ∂_{z_{k}}^{β_{k}}f)

is D-finite by Theorem 9. We can now assume that there is some a_{i} > 0 and some a_{i} < 0. Let A := R[Y, Z] = R[∂_{z_{1}}, …, ∂_{z_{d}}, ∂_{−1}, …, ∂_{−e}] = G[z_{1}, …, z_{d}, ∂_{z_{1}}, …, ∂_{z_{d}}, ∂_{−1}, …, ∂_{−e}] be the Weyl algebra. By Theorem 8 we know that

dim_{G} A_{n}f = O(n^{d}) for n >> 0  (1)

Put Δ := a_{1} · z_{1}∂_{z_{1}} + ⋯ + a_{d} · z_{d}∂_{z_{d}} − b ∈ A. For f = ∑_{α∈IN^{d}} f_{α}z^{α} we have

Δf = ∑_{α∈IN^{d}} (a^{⊤}α − b)f_{α}z^{α}  (2)

∇f = ∑_{{α∈IN^{d} \atop a^{⊤}α=b}} f_{α}z^{α}  (3)

Δ and ∇ are complementary in a certain sense:

∇Δf = 0  (4)
Δ∇f = 0  (5)
Δf = 0 ⇔ f = ∇f  (6)

By (5) and (6) we have

∇∇f = ∇f  (7)

Furthermore

ΔM = {f ∈ M : f_{α} = 0 if a^{⊤}α = b} = ker ∇  (8)
∇M = {f ∈ M : f_{α} = 0 if a^{⊤}α ≠ b} = ker Δ^{k} for every k ≥ 1  (9)

Our first important claim is:

For L ∈ A with ΔL = LΔ and f ∈ M: ∇Lf = L∇f  (10)

Proof: By (7) and (8), we can write f = ∇f + Δf̃ with f̃ ∈ M. Because of ΔL = LΔ and (4), ∇Lf = ∇L∇f + ∇LΔf̃ = ∇L∇f + ∇ΔLf̃ = ∇L∇f. Because of ΔL = LΔ and (5), ΔL∇f = LΔ∇f = 0, so (6) implies ∇L∇f = L∇f. Let A^{Δ} := {L ∈ A : ΔL = LΔ} be the set of those differential operators that commute with Δ. A^{Δ} is a subalgebra of A. We need an explicit description of A^{Δ}: Writing L = ∑_{{α∈IN^{d} \atop β∈IN^{d+e}}} c_{α,β}z^{α}∂^{β} with all c_{α,β} ∈ G,

we compute

ΔL − LΔ = ∑_{α,β} c_{α,β}(Δz^{α}∂^{β} − z^{α}∂^{β}Δ)

= ∑_{α,β} c_{α,β} ∑_{i=1}^{d} a_{i}(z_{i}∂_{z_{i}}z^{α}∂^{β} − z^{α}∂^{β}z_{i}∂_{z_{i}})

= ∑_{α,β} c_{α,β} ∑_{i=1}^{d} a_{i}((z_{i}z^{α}∂_{z_{i}} + α_{i}z^{α})∂^{β} − z^{α}(z_{i}∂^{β}∂_{z_{i}} + β_{i}∂^{β}))

= ∑_{α,β} c_{α,β} ∑_{i=1}^{d} a_{i}(α_{i} − β_{i})z^{α}∂^{β}

= ∑_{α,β} c_{α,β} · a^{⊤}(α − β) · z^{α}∂^{β}

Therefore

A^{Δ} = ⨁_{{α∈IN^{d} \atop (β,γ)∈IN^{d+e}} ; a^{⊤}(α−β)=0} G · z^{α}∂^{(β,γ)}  (11)

Fix a derivation ∂ ∈ X. Our aim is to find an equation L∇f = 0 with L ∈ R[∂] \ {0}. Let B := {L ∈ R[∂] : ΔL = LΔ} = R[∂] ∩ A^{Δ}, a subalgebra of A. We claim

(i) dim_{G} (B ∩ A_{n}) ≥ cn^{d} for n >> 0 and some c > 0.

(ii) B[Δ] = ⨁_{k∈IN} Δ^{k}B.

(iii) dim_{G} (B[Δ] ∩ A_{n}) ≥ cn^{d+1} for n >> 0 and some c > 0. (iv) dim_{G} (B[Δ] ∩ A_{n})f = O(n^{d}) for n >> 0. Proof:

(i) By (11) we have B = ⨁_{{α∈IN^{d} \atop β∈IN} ; a^{⊤}α=0} G · z^{α}∂^{β} if ∂ ∈ Y and B = ⨁_{{α∈IN^{d} \atop β∈IN} ; a^{⊤}α=a_{j}β} G · z^{α}∂^{β} if ∂ = ∂_{z_{j}} ∈ Z. There are

(d − 1) ℤ-linear independent solutions α^{(2)}, …, α^{(d)} ∈ IN^{d} of the equation a^{⊤}α = 0. (To see this: We may assume a_{1} > 0 and a_{2} < 0, else renumber variables. Put α^{(2)} := (−a_{2}, a_{1}, 0 … 0), and for i ∈

\{3, …, d\}: α^{(i)} := \{ \begin{matrix}(0, 0, 0 … 0, 1, 0 … 0) & if a_{i} = 0 \\ (−a_{i}, 0, 0 … 0, a_{1}, 0 … 0) & if a_{i} < 0 \\ (0, a_{i}, 0 … 0, −a_{2}, 0 … 0) & if a_{i} > 0 \end{matrix} \}, with non-zero entries only in the columns

1,2,i.) Now put β^{(2)} = ⋯ = β^{(d)} := 0, β^{(1)} := 1 and α^{(1)} := \{ \begin{matrix}(0 … 0) & if ∂ ∈ Y \\ (0 … 0, 1, 0 … 0) & if ∂ = ∂_{z_{j}} ∈ Z \end{matrix} \}. We

thus have d ℤ-linear independent solutions (α^{(1)}, β^{(1)}), …, (α^{(d)}, β^{(d)}) ∈ IN^{d+1} of the equation

\{ \begin{matrix}a^{⊤}α = 0 & if ∂ ∈ Y \\ a^{⊤}α = a_{j}β & if ∂ = ∂_{z_{j}} ∈ Z \end{matrix} \}  (12)

The map

φ : \{ \begin{matrix}IN^{d} & → & IN^{d+1} \\ (γ_{1}, …, γ_{d}) & ↦ & ∑_{i=1}^{d} γ_{i} · (α^{(i)}, β^{(i)}) \end{matrix}\}

is injective, and for |γ| ≤ m we have, putting h := max {|α^{(i)}| + β^{(i)} : i ∈ {1, …, d}} > 0 :

|φ(γ)| = |(∑_{i} γ_{i}α^{(i)}, ∑_{i} γ_{i}β^{(i)})| = ∑_{i} γ_{i}(|α^{(i)}| + β^{(i)}) ≤ ∑_{i} γ_{i} · h ≤ m · h

Thus φ({γ ∈ IN^{d} : |γ| ≤ m}) ⊂ {(α, β) ∈ IN^{d+1} : (12) holds, |α| + β ≤ mh}. For mh ≤ n < (m + 1)h we therefore have

dim_{G} (B ∩ A_{n}) = #{(α, β) ∈ IN^{d+1} : (12) holds, |α| + β ≤ mh}

≥ #φ({γ ∈ IN^{d} : |γ| ≤ m})

= \binom{m + d}{d} = \binom{⌊\frac{n}{h}⌋ + d}{d}

≥ c · n^{d} for n >> 0

(ii) There is an i ∈ {1, …, d} such that ∂ ≠ ∂_{z_{i}} and a_{i} ≠ 0. Let deg : A → IN ∪ {−∞} be the degree in ∂_{z_{i}} (well-defined on A!). Then deg Δ = 1, deg Δ^{k}L = k + deg L for L ∈ A, and deg Δ^{0}L_{0} + ⋯ Δ^{k}L_{k} = k for any L_{0}, …, L_{k} ∈ B with L_{k} ≠ 0.

(iii) By (ii) and since the multiplication by Δ^{k} is an injective G-linear map A_{n−k} → A_{n}

dim_{G} (B[Δ] ∩ A_{n}) ≥ dim_{G} (⨁_{k∈IN} (Δ^{k}B ∩ A_{n}))

= ∑_{k∈IN} dim_{G} (Δ^{k}B ∩ A_{n})

≥ ∑_{k=0}^{n} dim_{G} (B ∩ A_{n−k})

≥ ∑_{k=0}^{n−n_{0}} c(n − k)^{d} = ∑_{k=n_{0}}^{n} ck^{d}

∼ \frac{c}{d + 1}n^{d+1}

(iv) Follows from (1). Let π : B[Δ] → B be the G-algebra homomorphism defined by π| B = id_{B} and π(Δ) = 0. (That is,

π( ∑_{k∈IN} Δ^{k}L_{k}) = L_{0}.) We claim that

for L ∈ B[Δ] and f ∈ M: ∇Lf = π(L)∇f  (13)

Proof: Write L = π(L) + ΔL̃ with L̃ ∈ B[Δ]. By (4), ∇Lf = ∇π(L)f + ∇ΔL̃f = ∇π(L)f. Because of π(L) ∈ A^{Δ} and (10), ∇π(L)f = π(L)∇f. By (iii), (iv) and Lemma 6 we have a differential operator L ∈ B[Δ] \ {0} with Lf = 0. By (13), π(L)∇f = 0. If π(L) ≠ 0, we are done since B ⊂ R[∂]. Else write L uniquely as L = Δ^{k}L′ with k ≥ 1, L′ ∈ B[Δ] and π(L′) ≠ 0. By (9) and (6), L′f ∈ ker Δ^{k} = ker Δ, so ∇L′f = L′f. By Prop. 3(g), f ∈ D(R, M, X) implies L′f ∈ D(R, M, X), so there is an L′′ ∈ R[∂] \ {0} with L′′L′f = 0. Then L′′π(L′)∇f = L′′∇L′f = L′′L′f = 0 by (13), and we are done because L′′π(L′) ∈ R[∂] \ {0}. We have shown that for every ∂ ∈ X there is an L ∈ R[∂] \ {0} with L∇f = 0. Now ∇f is D-finite by Theorem 8. q.e.d.

6. Combinatorial Sums

Let R be a field of characteristic zero. Definition 7: An expression (depending on n_{1}, …, n_{e} ∈ IN) of the form

S(n_{1}, …, n_{e}) = ∑_{{n_{e+1},...,n_{d}∈IN \atop An {> \atop =} ; < b}} P_{1}(n_{1}) ⋯ P_{d}(n_{d}) · ∏_{k=1}^{n_{1}} Q_{1}(k) ⋯ ∏_{k=1}^{n_{d}} Q_{d}(k)

(n denotes the column vector ( n_{1} ; ⋮ ; n_{d} )) with

• A ∈ ℤ^{c×d}, b ∈ ℤ^{d}, and > = ; < a fixed set of c equality/inequality signs ∈ {=, ≤, ≥, <, >},

• P_{1}, …, P_{d} ∈ R(X) rational functions without poles in IN,

• Q_{1}, …, Q_{d} ∈ R(X) rational functions without poles in IN \ {0},

• such that for every (n_{1}, …, n_{e}) ∈ IN^{e} there are only finitely many solutions (n_{e+1}, …, n_{d}) ∈ IN^{d−e} of An > = ; < b is called a combinatorial sum over R. Theorem 12: The generating function

∑_{n_{1},...,n_{e}∈IN} S(n_{1}, …, n_{e})z_{1}^{n_{1}} ⋯ z_{e}^{n_{e}}

of a combinatorial sum is in D(R[z_{1}, …, z_{e}], R\begin{aligned}[ \\ [ & z_{1}, …, z_{e} & ] \\ & ] \end{aligned}, \{∂_{z_{1}}, …, ∂_{z_{e}}\}).

Corollary 13: Any combinatorial sum of one variable S(m) over R satisfies a non-trivial linear recurrence relation with polynomial coefficients: There are polynomials a_{r}, …, a_{0} ∈ R[m], not all zero, such that

a_{r}(m) · S(m + r) + ⋯ + a_{0}(m) · S(m) = 0 ∀m ∈ IN

For the proof, we recall the classical Proposition 14: Let R be an integral domain of characteristic zero, M an R-module, and f = ∑_{m=0}^{∞} a_{m}z^{m} ∈ M[ ; [z] ; ].

Then f ∈ D(R[z], M[ ; [z] ; ], {∂_{z}}) if and only if the sequence (a_{m}) satisfies a non-trivial linear recurrence relation with polynomial coefficients. Proof of the Proposition: See [Hai], section 1.14 or [Sta], Theorem 1.5. Proof of the Theorem: We may assume that we only have equality signs. (Introduce an auxiliary variable for every inequality.) The unrestricted sum

∑_{n_{1},...,n_{d}∈IN} ∏_{j=1}^{d} (P_{j}(n_{j}) · ∏_{k=1}^{n_{j}} Q_{j}(k)) · z^{n} = ∏_{j=1}^{d} ( ∑_{m=0}^{∞} P_{j}(m) · ∏_{k=1}^{m} Q_{j}(k) · z_{j}^{m})

is in D(R[z_{1}, …, z_{d}], R\begin{aligned}[ \\ [ & z_{1}, …, z_{d} & ] \\ & ] \end{aligned}, \{∂_{z_{1}}, …, ∂_{z_{d}}\}) by Prop. 14 and Prop. 5(a). Applying Theorem 10 c times, we get

∑_{{n_{1},...,n_{d}∈IN \atop An=b}} ∏_{j=1}^{d} (P_{j}(n_{j}) · ∏_{k=1}^{n_{j}} Q_{j}(k)) · z^{n} ∈ D(R[z_{1}, …, z_{d}], R\begin{aligned}[ \\ [ & z_{1}, …, z_{d} & ] \\ & ] \end{aligned}, \{∂_{z_{1}}, …, ∂_{z_{d}}\})

Then apply the substitution (z_{e+1} ← 1, …, z_{d} ← 1) which is well-defined on the sub-{∂_{z_{1}}, …, ∂_{z_{d}}}-differential R[z_{1}, …, z_{d}]-module

N := \{ ∑_{n∈IN^{d}} a_{n}z^{n} : there is an l ∈ IN such that a_{n} = 0 if \begin{matrix}| \\ | & An − b & | \\ | \end{matrix} > l\}

of R\begin{aligned}[ \\ [ & z_{1}, …, z_{d} & ] \\ & ] \end{aligned}. Theorem 9 now gives the desired result. q.e.d. Proof of the Corollary: Put e = 1 in Theorem 12 and use Prop. 14. q.e.d.

7. Notes

Section 1: The idea for the axiomatic approach comes from [Ko]. Section 2: Definition 4 was first formulated by [Sta] (for d = 1) and [Li1]. Prop. 3 and Prop. 4(a) are found in [Hai]; see also [Li2]. Prop. 4(b) comes from [Sto] and [HaSi]. Prop. 5 is mentioned in [Li1] and proved in [Li2].

[Ca] presents some more definitions of D-finiteness, based on Bernstein theory. Section 3: The importance of estimating the degrees of polynomials has first been recognized by Gessel [Ge], Zeilberger [Ze] and Lipshitz [Li1]. More on filtrations can be found in the books of J.-E. Björk [Bj] and A. Borel [Bo]. Theorem 8 is a generalization of previously known statements (see [Ca] or [Sto]): they handled only e = 0. Section 4: The determination of what substitutions are valid in the case N = M[ ; [Y] ; ] goes back to Gessel [Ge]. Theorem 9 is a generalization of [Hai] 2.13. (The proof in [Li2] is incomplete: it only treats case 1.) Section 5: Theorem 10 was first proved by Lipshitz [Li1] (case e = 0 only) and independently by Haible [Hai]. Both proofs involved much computation. A new proof was found by Stoll [Sto] (case e = 0 only). The present proof is a generalization of his proof to arbitrary e. Section 6: A similar but less explicit statement can be found in [Li1]. P-recursive sequences (i.e. sequences whose generating function is D-finite) are treated in more detail in [Li2].

8. References

Primary References:

[Ca] Pierre Cartier: Démonstration “automatique” d’identités et fonctions hypergéométriques. Astérisque 206 (1992), 41-91.

[Hai] Bruno Haible: D-finite Potenzreihen in mehreren Variablen. Diplomarbeit, Universität Karlsruhe, June 1989.

[Li1] Leonard Lipshitz: The diagonal of a D-finite power series is D-finite. J. Algebra 113 (1988), 373-378.

[Li2] Leonard Lipshitz: D-finite power series.

J. Algebra 122 (1989), 353-373. MR # 90g:13032.

[Sta] Richard Peter Stanley: Differentiably finite power series. European J. Combin. 1 (1980), 175-188. MR # 81m:05012.

[Sto] Michael Stoll: D-finite Potenzreihen.

Preprint, 1991.

Secondary References:

[Bj] J.-E. Björk: Rings of differential operators. North Holland, 1979.

[Bo] A. Borel et al.: Algebraic D-modules.

Perspectives in Math. 2, Academic Press, 1987.

[Ge] Ira M. Gessel: Two theorems on rational power series.

Utilitas Math. 19 (1981), 247-254. MR # 82h:05005.

[HaSi] W. A. Harris, Y. Sibuya: The reciprocal of solutions of linear ordinary differential equations.

Adv. Math. 58 (1985), 119-132.

[Ko] E. R. Kolchin: Differential algebra and algebraic groups. Academic Press, 1973.

[Ze] Doron Zeilberger: Sister Celine’s technique and its generalizations. J. Math. Anal. Appl 85 (1982), 114-145. MR # 83f:33001.