<figure><img src="image_1.png" /></figure>

HAL
open science

# Single-exponential bounds for diagonals of D-finite power series

Shaoshi Chen, Frédéric Chyzak, Pingchuan Ma, Chaochao Zhu

► To cite this version:

Shaoshi Chen, Frédéric Chyzak, Pingchuan Ma, Chaochao Zhu. Single-exponential bounds for diagonals of D-finite power series. 2025. hal-05132552

HAL Id: hal-05132552

https://inria.hal.science/hal-05132552v1

Preprint submitted on 27 Jun 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution - ShareAlike 4.0 International License
Single-exponential bounds for diagonals
of D-finite power series

Shaoshi Chen<sup>a,b</sup>, Frédéric Chyzak<sup>c</sup>, Pingchuan Ma<sup>d</sup>, Chaochao Zhu<sup>e</sup>

<sup>a</sup>KLMM, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China

<sup>b</sup>School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China

<sup>c</sup>Inria, 91120 Palaiseau, France

<sup>d</sup>Tsinghua University High School, Beijing 100084, China

<sup>e</sup>School of Finance and Mathematics, West Anhui University, Lu'an 237012, China

**Abstract**

D-finite power series appear ubiquitously in combinatorics, number theory, and mathematical physics. They satisfy systems of linear partial differential equations whose solution spaces are finite-dimensional, which makes them enjoy a lot of nice properties. After attempts by others in the 1980s, Lipshitz was the first to prove that the class they form in the multivariate case is closed under the operation of diagonal. In particular, an earlier work by Gessel had addressed the D-finiteness of the diagonals of multivariate rational power series. In this paper, we give another proof of Gessel's result that fixes a gap in his original proof, while extending it to the full class of D-finite power series. We also provide a single exponential bound on the degree and order of the defining differential equation satisfied by the diagonal of a D-finite power series in terms of the degree and order of the input differential system.

**Keywords:** D-finite power series, diagonal theorem, order bound, degree bound

**1. Introduction**

Diagonals of multivariate formal power series appear frequently in different areas: diagonals of rational power series play an important role in enumerative combinatorics, especially the lattice paths enumeration (see the books [21, 16, 18, 15] and the survey [17]); Christol's number-theoretic conjecture, which predicts that globally bounded D-finite power series are diagonals of rational power series [6], remains largely open (see the nice recent survey [7] by himself);

Email addresses: schen@amss.ac.cn (Shaoshi Chen), frederic.chyzak@inria.fr (Frédéric Chyzak), pcma@amss.ac.cn (Pingchuan Ma), zccjsbz@amss.ac.cn (Chaochao Zhu)
intensive studies on diagonals also appear in computer algebra with connection to mathematical physics [1, 4, 5, 3].

In these contexts, formal power series are commonly given implicitly as solutions to either algebraic or (linear) differential equations, and the corresponding diagonals also satisfy such equations. This is in particular the case for *D-finite power series*. Recall that these series are defined (Definition 1) as multivariate formal power series in variables $x_1, \dots, x_n$ whose infinite set of higher-order partial derivatives generates a finite-dimensional vector space over the field of rational functions in the variables. D-finite power series were first introduced and studied by Stanley in 1980 in the univariate case [20] and later systematically investigated by Lipshitz in the multivariate case [13, 14]. In the early 1980’s, Gessel, Stanley, Zeilberger, and many combinatorists conjectured that the diagonal of a rational power series in several variables is D-finite. Zeilberger [23] in 1980 and Gessel [11] in 1981 independently claimed to have proved this conjecture. Later in 1988, Lipshitz [13] pointed out that both proofs were not complete and he gave a proof by basing on a different idea, thus proving that D-finite power series are closed under taking diagonals. In 1990, Zeilberger [24] then completed his own proof with the theory of holonomic D-modules. Later, Wu and Chen [22] provided a similar result for the case of bivariate rational functions as a follow-up of Gessel’s work.

The problem we address in this paper is to bound the degrees and orders of linear differential equations satisfied by the diagonal of a given function in terms of degrees and orders of the differential systems that define the given function. We view this as a crucial preliminary step to the computational complexity analysis of algorithms for computing diagonals, and to the longer-term development of fast algorithms in a complexity-driven way.

Diagonals of multivariate series come in several flavors (see Definition 3): first, *primary diagonals* collapse just two variables; next, *complete diagonals* collapse all variables to a single one.

Starting with primary diagonals, we get a polynomial increase of the order and degree bounds (Corollary 22). A naive iteration of primary diagonals (Section 4.1.3) would thus lead to double-exponential bounds for complete diagonal (Section 4.1.3). Our first and main contribution is therefore to derive a *single-exponential* bound (Theorems 25 and 35). Note however that in the bivariate case ($n=2$), no iteration is necessary so that the double-exponential bound is in fact just polynomial, and the bounds of Corollary 22 are better than those of Theorems 25 and 35.

After Lipshitz’s work [13], the general belief was that the gaps in Gessel’s proof do not seem easy to fill. As a secondary contribution, we however fully fix and generalize Gessel’s proof [11] by elaborating on his original proof strategy (Theorems 5 and 6). Because Gessel’s approach does not need any change of variables, as opposed to Lipshitz’s, it leads more directly to explicit filtrations, from which we benefit in our bound estimates of the Lipshitz way.

It is worth comparing the bounds we obtained in this paper with the situation in positive characteristic. In that context, a result by Furstenberg [10] and Deligne [9] states that the diagonal of any algebraic function is algebraic. A
recent quantitative version of this theorem by Adamczewski and Bell [2] provides bounds on the algebraic degree of a diagonal and on the maximal degree (height) of a polynomial equation is satisfies, which, even in the case of the diagonal of a *rational* function, is doubly exponential of the form $O(p^{n^n})$, where $p$ is the characteristic and $n$ is the number of variables. As our bounds are singly exponential and might be useful also in characteristic $p$, this is another instance of the phenomenon [19] that representing an algebraic function by differential equations is more compact than by a polynomial equation.

The remainder of this paper is organized as follows. We recall some basic terminology about rings of differential operators and introduce D-finite power series and their diagonals in Section 2. In Section 3, we first prove the Diagonal Theorem (Theorem 5) on D-finite power series in the way suggested in Gessel’s work and we then derive an explicit polynomial bound for annihilators of diagonals in the bivariate case. Then, a single-exponential bound is given for the general multivariate situation in Section 4 by analyzing Lipshitz’s proof.

## 2. Differential operators, D-finiteness, and diagonals

Throughout this article, we assume that $K$ is a field of characteristic 0. Let $K[x]$ be the ring of polynomials in $x = x_1, \dots, x_n$ over $K$ and $K(x)$ be the field of rational functions in $x$ over $K$. Let $K[[x]]$ be the ring of formal power series in $x$ over $K$, which is a domain. Denote $S := K(x) \otimes_{K[x]} K[[x]]$. Let $D_{x_1}, \dots, D_{x_n}$ denote the usual partial derivations $\partial/\partial x_1, \dots, \partial/\partial x_n$ on $S$. Those are the basic notations that we will use in Sections 1 and 3, but they will need to be generalized in Section 4.

The Weyl algebra $W_n := K[x] \langle D_x \rangle$ is the non-commutative polynomial ring in the variables $x = x_1, \dots, x_n$ and $D_x = D_{x_1}, \dots, D_{x_n}$, in which the following multiplication rules hold: $x_i x_j = x_j x_i$, $D_{x_i} D_{x_j} = D_{x_j} D_{x_i}$ for all $i, j \in \{1, \dots, n\}$ and $D_{x_i} f = f D_{x_i} + \partial f/\partial x_i$ for all $i \in \{1, \dots, n\}$ and $f \in K[x]$. (Here and throughout, we use angled brackets $R\langle\dots\rangle$ to denote a twisted extension of a ring $R$, and the generators between brackets always commute with one another.) The Weyl algebra can be interpreted as the ring of linear partial differential operators with polynomial coefficients. Analogously, we define the *rational Ore algebra* $\mathbb{O}_n$ as the ring $K(x) \langle D_x \rangle$ of linear partial differential operators with rational function coefficients. The elements of $\mathbb{O}_n$ act on $S$ by interpreting $D_{x_i}$ as $\partial/\partial x_i$, which turns $S$ into a left $\mathbb{O}_n$-module. For a given $f \in S$, the *annihilating ideal* of $f$ in $\mathbb{O}_n$ is defined as the set $\text{Ann}_{\mathbb{O}_n}(f) = \{L \in \mathbb{O}_n \mid L \cdot f = 0\}$. Note that $\text{Ann}_{\mathbb{O}_n}(f)$ is in particular a (left) vector space over $K(x)$.

**Definition 1 (D-finiteness).** An element $f \in K[[x]]$ is *D-finite* over $K(x)$ if the $K(x)$-vector space generated by the derivatives of $f$ in $S$ is finite-dimensional.

Note that, $L(f)$ is also D-finite for any operator $L \in \mathbb{O}_n$.

**Definition 2 (Order and degree).** Assume that $f \in S$ is D-finite over $K(x)$. Then for each $i \in \{1, \dots, n\}$, there exists a non-zero operator $L_i$ in the
subalgebra $K[x]\langle D_{x_i} \rangle$ of $W_n$ such that $L_i(f) = 0$. Write

$$L_i = \ell_{i,0} + \ell_{i,1}D_{x_i} + \cdots + \ell_{i,r_i}D_{x_i}^{r_i}$$

with $\ell_{i,0}, \dots, \ell_{i,r_i} \in K[x]$ and $\ell_{i,r_i} \neq 0$. We call $r_i$ the order of the operator $L_i$, denoted by $\mathrm{ord}(L_i)$. The degree of $L_i$ is defined by the maximum total degree of its polynomial coefficients: $\mathrm{deg}(L_i) := \max_{j=0}^{r_i} \mathrm{tdeg}(\ell_{i,j})$, where $\mathrm{tdeg}$ means the total degree w.r.t. $x_1, \dots, x_n$. Let $r_f := \max_{i=1}^n r_i$ and $d_f := \max_{i=1}^n d_i$ where $d_i = \mathrm{deg}(L_i)$.

**Definition 3.** Let $f = \sum_{i_1, \dots, i_n \ge 0} a_{i_1, \dots, i_n} x_1^{i_1} \cdots x_n^{i_n} \in K[[x]]$. We call the power series

$$\Delta_{1,2}(f) := \sum_{i_1, i_3, \dots, i_n \ge 0} a_{i_1, i_3, \dots, i_n} x_1^{i_1} x_3^{i_3} \cdots x_n^{i_n} \in K[[x_1, x_3, \dots, x_n]]$$

a primary diagonal of $f$. Other primary diagonals $\Delta_{i,j}$ are defined similarly, so that $\Delta_{i,j}(f)$ and $\Delta_{j,i}(f)$ are the same series except for the variable names. A diagonal is defined by any composition of the $\Delta_{i,j}$. The complete diagonal of $f$, denoted by $\Delta(f)$, is defined as

$$\Delta(f) := \Delta_{n,n-1}\Delta_{n-1,n-2} \cdots \Delta_{2,1}(f) := \sum_{i \ge 0} a_{i, \dots, i} x_n^i \in K[[x_n]]. \quad (1)$$

By the diagonal of $f$, we mean its complete diagonal when no ambiguity arises.

For future reference, we recall here the following well-known consequence of Cramer's rules that will be used in the subsequent sections.

**Lemma 4.** Let $A = (a_{i,j}) \in K[x]^{n \times m}$ be a matrix with entries of total degree at most $d$. Assume the inequality $n < m$, so that the matrix has a non-trivial right nullspace. Then, there exists a non-zero vector $v = (v_1, \dots, v_m) \in K[x]^m$ that solves $Av = 0$ and has total degree at most $nd$.

*Proof.* Let $\rho$ denote the rank of $A$. Because $\rho \le n$, we can fix $\rho$ linearly independent rows of $A$ and form a $\rho \times m$ submatrix $B$ of $A$ of rank $\rho$. In turn, consider $\rho$ linearly independent columns of $B$, thus forming a $\rho \times \rho$ submatrix $C$, and an additional column $c$ of $B$. The system $Cw = -c$ admits a non-zero solution $w$ with $\mathrm{tdeg}(w) \le \rho d$ that can be expressed by Cramer's rules. Padding $w$ with zeros results in a non-zero $v$ satisfying $Av = 0$ and $\mathrm{tdeg}(v) \le \rho d \le nd$ as wanted. $\square$

### 3. Diagonal theorem in the multivariate case

In this section, we give a proof of the following “Diagonal theorem” in the spirit of Gessel [11].

**Theorem 5 (Diagonal Theorem).** Let $f \in K[[x]]$ be $D$-finite over $K(x)$. Then $\Delta(f) \in K[[x_n]]$ is $D$-finite over $K(x_n)$.
The proof of Theorem 5 is just an iteration of the following result for primary diagonals.

**Theorem 6.** Let $f \in K[[x]]$ be $D$-finite over $K(x)$. Then $\Delta_{1,2}(f)$ is $D$-finite over $K(x_1, x_3, \dots, x_n)$.

The rest of the present section is devoted to the proof of Theorem 6.

The following objects will serve as generators in relevant algebras:

$$ 
\begin{aligned}
D_{x_1,x_2} &:= D_{x_1}D_{x_2}, \\
\theta_{x_i} &:= x_iD_{x_i} \quad \text{for each } i \in \{1, \dots, n\}, \\
T_{x_1,x_2} &:= \theta_{x_1} - \theta_{x_2}.
\end{aligned}
$$

We use bold notation to abbreviate monomials: for example, $x^\alpha$ denotes $x_1^{\alpha_1} \dots x_n^{\alpha_n}$ and $D_x^\beta$ denotes $D_{x_1}^{\beta_1} \dots D_{x_n}^{\beta_n}$. By [8, Proposition 2.1], the set $\{x^\alpha D_x^\beta \mid \alpha, \beta \in \mathbb{N}^n\}$ is a basis of $W_n = K[x] \langle D_x \rangle$ as a vector space over $K$. Similarly, Lemmas 7, 8, and 9 are basis lemmas for several subalgebras of $W_n$: $K[x_1x_2, x_3, \dots, x_n] \langle T_{x_1,x_2}, D_{x_1,x_2} \rangle$, $K[x_1, x_3, \dots, x_n] \langle D_{x_1} \rangle$, and $K[x_1x_2, x_3, \dots, x_n] \langle T_{x_1,x_2}, D_{x_h} \rangle$ for $h \in \{3, \dots, n\}$.

**Lemma 7.** The set

$$ \{(x_1x_2)^i x_3^{k_3} \dots x_n^{k_n} T_{x_1,x_2}^j D_{x_1,x_2}^\ell \mid i, j, \ell, k_3, \dots, k_n \in \mathbb{N}\} $$

is a basis of $K[x_1x_2, x_3, \dots, x_n] \langle T_{x_1,x_2}, D_{x_1,x_2} \rangle$ as a vector space over $K$.

*Proof.* It suffices to show that the monomials $(x_1x_2)^i T_{x_1,x_2}^j D_{x_1,x_2}^\ell$ are linearly independent over $K$. Suppose that

$$ L = \sum_{(i,j,\ell) \in \Lambda} c_{i,j,\ell} \cdot (x_1x_2)^i T_{x_1,x_2}^j D_{x_1,x_2}^\ell = 0 $$

for some non-empty finite set $\Lambda$ and $c_{i,j,\ell} \in K \setminus \{0\}$. Let $\succ$ be the lexicographical order on the Weyl algebra $W_2 = K[x_1, x_2] \langle D_{x_1}, D_{x_2} \rangle$ with $D_{x_1} \succ D_{x_2} \succ x_2 \succ x_1$. It can be proved by induction that there exist $Q_1$ and $Q_2$ in $W_2$ such that

$$ T_{x_1,x_2}^j = \theta_{x_1}^j + Q_1 = x_1^j D_{x_1}^j + Q_2 \quad \text{and} \quad \mathrm{lm}(Q_1) < \mathrm{lm}(\theta_{x_1}^j), \mathrm{lm}(Q_2) < x_1^j D_{x_1}^j. $$

Then we have that there exists $Q_3$ in $W_2$ such that

$$ (x_1x_2)^i T_{x_1,x_2}^j D_{x_1,x_2}^\ell = x_1^{i+j} x_2^i D_{x_1}^{j+\ell} D_{x_2}^\ell + Q_3 \quad \text{and} \quad \mathrm{lm}(Q_3) < x_1^{i+j} x_2^i D_{x_1}^{j+\ell} D_{x_2}^\ell. $$

Note that the map $(i, j, \ell) \mapsto (i+j, i, j+\ell, \ell)$ is injective. Since the set $\{x^i D_x^j \mid i, j \in \mathbb{N}^n\}$ is a basis of $W_n = K[x] \langle D_x \rangle$ as a vector space over $K$, this forces all $c_{i,j,\ell} = 0$, which contradicts our assumption. $\square$

**Lemma 8.** The set

$$ \{x_1^k x_3^{k_3} \dots x_n^{k_n} D_{x_1}^\ell \mid k, k_3, \dots, k_n, \ell \in \mathbb{N}\} $$

is a basis of $K[x_1, x_3, \dots, x_n] \langle D_{x_1} \rangle$ as a vector space over $K$.
**Lemma 9.** For each $h \in \{3, \dots, n\}$, the set

$$ \{(x_1 x_2)^i x_3^{k_3} \cdots x_n^{k_n} T_{x_1, x_2}^j D_{x_h}^\ell \mid i, j, \ell, k_3, \dots, k_n \in \mathbb{N}\} $$

is a basis of $K[x_1x_2, x_3, \dots, x_n] \langle T_{x_1, x_2}, D_{x_h} \rangle$ as a vector space over $K$.

We omit the proofs of Lemma 8 and 9 those are very similar to the proof of Lemma 7. Next we present some commutation rules between the diagonal operator $\Delta_{1,2}$ and the operators $x_1x_2, D_{x_1, x_2}, \theta_{x_i}$ and $T_{x_1, x_2}$.

**Proposition 10.** For any power series $f(\mathbf{x}) \in K[[\mathbf{x}]]$, we have

$$ 1. \Delta_{1,2}(x_1 x_2 \cdot f) = x_1 \Delta_{1,2}(f); $$

$$ 2. \Delta_{1,2}(D_{x_1,x_2}(f)) = D_{x_1}\theta_{x_1}(\Delta_{12}(f)); $$

$$ 3. \Delta_{1,2}(\theta_{x_1}(f)) = \theta_{x_1}(\Delta_{1,2}(f)); $$

$$ 4. \Delta_{1,2}(\theta_{x_2}(f)) = \theta_{x_1}(\Delta_{1,2}(f)); $$

$$ 5. \Delta_{1,2}(T_{x_1,x_2}(f)) = 0; $$

$$ 6. D_{x_1,x_2}T_{x_1,x_2} = T_{x_1,x_2}D_{x_1,x_2}; $$

$$ 7. T_{x_1,x_2} \cdot x_1 x_2 = x_1 x_2 \cdot T_{x_1,x_2}. $$

*Proof.* Given $f = \sum_{i_1, \dots, i_n \ge 0} a_{i_1, \dots, i_n} x_1^{i_1} \cdots x_n^{i_n} \in K[[\mathbf{x}]]$, we have

$$ \begin{aligned} \Delta_{1,2}(x_1 x_2 \cdot f) &= \Delta_{1,2} \left( \sum_{i_1, \dots, i_n \ge 0} a_{i_1, \dots, i_n} x_1^{i_1+1} x_2^{i_2+1} x_3^{i_3} \cdots x_n^{i_n} \right) \\ &= \sum_{i_1, i_3, \dots, i_n \ge 0} a_{i_1, i_3, \dots, i_n} x_1^{i_1+1} x_3^{i_3} \cdots x_n^{i_n} = x_1 \Delta_{1,2}(f), \end{aligned} $$

which proves Point 1. Points 2, 3, and 4 are proved in [22, Lemma 4.3]. Point 5 immediately follows by linearity from Points 3 and 4. Taking the difference of the two identities

$$ D_{x_1, x_2}(x_1 D_{x_1}) = D_{x_1}(x_1 D_{x_1}) D_{x_2} = (x_1 D_{x_1} + 1) D_{x_1, x_2}, $$

$$ D_{x_1, x_2}(x_2 D_{x_2}) = D_{x_2}(x_2 D_{x_2}) D_{x_1} = (x_2 D_{x_2} + 1) D_{x_1, x_2}, $$

we obtain Point 6. Similarly, taking the difference of the two identities

$$ (x_1 D_{x_1}) x_1 x_2 = x_1 (x_1 D_{x_1} + 1) x_2 = x_1 x_2 \cdot (x_1 D_{x_1} + 1), $$

$$ (x_2 D_{x_2}) x_1 x_2 = x_2 (x_2 D_{x_2} + 1) x_1 = x_1 x_2 \cdot (x_2 D_{x_2} + 1), $$

proves Point 7. $\square$

**Lemma 11.** Let $f(\mathbf{x}) \in K[[\mathbf{x}]]$. Then, there exists $s \in \mathbb{N}$ such that $T_{x_1, x_2}^s(f) = 0$ if and only if there exists $g$ in $n-1$ variables such that $f(\mathbf{x}) = g(x_1 x_2, x_3, \dots, x_n)$.

*Proof.* If $f(\mathbf{x}) = g(x_1 x_2, x_3, \dots, x_n)$, write

$$ g(x_1, x_3, \dots, x_n) = \sum_{i_1, i_3, \dots, i_n \ge 0} b_{i_1, i_3, \dots, i_n} x_1^{i_1} x_3^{i_3} \cdots x_n^{i_n}. $$
Take $s = 1$, then

$$
\begin{align*}
T_{x_1,x_2}(f) &= T_{x_1,x_2}(g(x_1x_2, x_3, \dots, x_n)) \\
&= \sum_{i_1, i_3, \dots, i_n \ge 0} (i_1 - i_1) b_{i_1, i_3, \dots, i_n} x_1^{i_1} x_2^{i_2} x_3^{i_3} \cdots x_n^{i_n} = 0.
\end{align*}
$$

For the converse statement, assume there exists $s \in \mathbb{N}$ such that $T_{x_1,x_2}^s(f) = 0$. If $s=0$, then $f=0$. Take $g=0$. If $s>0$, write $f = \sum_{i_1,...,i_n \ge 0} a_{i_1,...,i_n} x_1^{i_1} \cdots x_n^{i_n}$.
Then

$$
T_{x_1, x_2}^{s}(f) = \sum_{i_1, \dots, i_n \ge 0} (i_1 - i_2)^s a_{i_1, \dots, i_n} x_1^{i_1} \cdots x_n^{i_n} = 0.
$$

Hence $(i_1 - i_2)^s a_{i_1, \dots, i_n} = 0$ for all integers $i_1, \dots, i_n \ge 0$, so that $a_{i_1, \dots, i_n} = 0$ for all $i_1 \ne i_2$. Take

$$
g(x_1, x_3, \dots, x_n) = \sum_{i_1, i_3, \dots, i_n \ge 0} a_{i_1, i_3, \dots, i_n} x_1^{i_1} x_3^{i_3} \cdots x_n^{i_n}.
$$

Then $f(\mathbf{x}) = g(x_1x_2, x_3, \dots, x_n)$. $\square$

**Lemma 12.** Let $f(\mathbf{x}) \in K[[\mathbf{x}]]$ be D-finite over $K(\mathbf{x})$. Let $\mathbf{y} = y_1, \dots, y_m$ and let power series

$$
g_1(\mathbf{y}), \dots, g_n(\mathbf{y}) \in K[[\mathbf{y}]]
$$

be algebraic over $K(\mathbf{y})$. Assume that the substitution $f(g_1(\mathbf{y}), \dots, g_n(\mathbf{y}))$ makes sense. Then $f(g_1(\mathbf{y}), \dots, g_n(\mathbf{y}))$ is D-finite over $K(\mathbf{y})$. In particular, let $f(\mathbf{x})$ be D-finite and suppose that the evaluation of $f(\mathbf{x})$ at $x_2 = 1$ makes sense, then $f(x_1, 1, x_3, \dots, x_n)$ is D-finite.

Proof. See [14, Proposition 2.3]. $\square$

From the definition of $\mathbb{O}_n$,

$$
D_{x_i} f = f D_{x_i} + D_{x_i}(f) \quad \text{for all } f \in K(\mathbf{x}).
$$

More generally, we have the formulae: for all $f \in K(\mathbf{x})$ and $i \in \{1, \dots, n\}$,

$$
D_{x_i}^k f = \sum_{\ell=0}^{k} \binom{k}{\ell} D_{x_i}^{\ell}(f) D_{x_i}^{k-\ell} \quad (2)
$$

and

$$
f D_{x_i}^k = \sum_{\ell=0}^{k} (-1)^\ell \binom{k}{\ell} D_{x_i}^{k-\ell} D_{x_i}^\ell(f). \quad (3)
$$

The relations (2) and (3) can be proved by a straightforward induction. In the sequel, we merely use the facts that, for all $f \in K[x]$ and $i \in \{1, \dots, n\}$,

$$
D_{x_i}^k f = f D_{x_i}^k + P \quad \text{and} \quad f D_{x_i}^k = D_{x_i}^k f - P, \qquad (4)
$$
where $P \in K[\mathbf{x}]\langle D_{x_i} \rangle$ with $\mathrm{ord}(P) < k$ and $\mathrm{deg}(P) \le \mathrm{deg}(f)$. Denote by $K[\mathbf{x}]_{\le d}$ the set of polynomials in $K[\mathbf{x}]$ with total degree no more than $d$.

A number of similar arguments in the rest of the article will differ only by a choice of variables. This is why we make a number of notations depend on a set $S$ in the following definition. The reader is invited to pay attention to this implicit dependency in what follows. We will indeed use $S = \{1, 2\}$ and $S = \{1, 2, h\}$ in the present Section 3, and we will additionally use $S = \{1, \dots, n\}$ in Section 4.

**Definition 13.** Fix a subset $S \subseteq \{1, 2, \dots, n\}$. Recall $L_i \in \mathbb{W}_n$ is fixed for each $i$. We give the following definitions and notations:

1. Given $\beta \in \mathbb{N}^S$, write $D_S^\beta$ for the product $\prod_{j \in S} D_{x_j}^{\beta_j}$,

2. $C := \mathrm{lcm}_{j \in S}(\mathrm{lcm}(L_j)) \in K[\mathbf{x}]$,

3. for each $j \in S$, $\tilde{L}_j := C/\mathrm{lcm}(L_j) \cdot L_j \in \mathbb{W}_n$,

4. $d_C := \sum_{j \in S} d_j$,

5. $B := \prod_{j \in S} \{0, 1, \dots, r_i - 1\} \subseteq \mathbb{N}^{\#S}$,

6. $\mathcal{F}_{d,r} := \bigoplus_{|\beta| \le r} K[\mathbf{x}]_{\le d} D_S^\beta$,

7. $\mathcal{H}_{d,r} := \bigoplus_{|\beta| \le r \text{ or } \beta \in B} K[\mathbf{x}]_{\le d} D_S^\beta$,

8. $J := \sum_{j \in S} \mathbb{W}_n \tilde{L}_j$,

where the dependency in $S$ is kept implicit in the notation.

Immediately we have

**Lemma 14.** For any non-empty set $S \subseteq \{1, 2, \dots, n\}$, consider the quantities in Definition 13. Then

1. $\mathrm{tdeg}(C) \le d_C$,

2. for each $i \in S$, $\tilde{L}_i(f) = 0$ and $\mathrm{deg} \tilde{L}_i \le d_C$,

3. for each $i \in S$, $CD_{x_i}^{r_i} = (CD_{x_i}^{r_i} - \tilde{L}_i) + \tilde{L}_i \in \mathcal{F}_{d_C, r_i - 1} + J$.

Continuing in analogy with [13, Lemma 3], we have the following lemmas:

**Lemma 15.** For all $\alpha \in \mathbb{N}^S$, $CD_S^\alpha$ is an element of $\mathcal{F}_{d_C, |\alpha|-1} + J$.

*Proof.* If $\alpha \in B$, nothing needs to be proven. So suppose, for instance, $n \in S$ and $\alpha_n \ge r_n$. Then multiply $D_S^{\alpha-r_n e_n}$ with $CD_{x_n}^{r_n}$, where $e_n := (0, 0, \dots, 1)$, which yields

$$ 
\begin{aligned}
D_S^{\alpha-r_n e_n} CD_{x_n}^{r_n} &\in \bigoplus_{j=0}^{r_n-1} D_S^{\alpha-r_n e_n} K[\mathbf{x}]_{\le d_C} D_{x_n}^j + J \\
&\subseteq \sum_{j=0}^{r_n-1} (K[\mathbf{x}]_{\le d_C} D_S^{\alpha-r_n e_n} + \mathcal{F}_{d_C, |\alpha|-r_n-1}) D_{x_n}^j + J \\
&\subseteq \mathcal{F}_{d_C, |\alpha|-1} + \mathcal{F}_{d_C, |\alpha|-2} + J = \mathcal{F}_{d_C, |\alpha|-1} + J.
\end{aligned}
$$

Hence

$$ 
\begin{aligned}
CD_S^\alpha &\in (D_S^{\alpha-r_n e_n} C + \mathcal{F}_{d_C, |\alpha|-r_n-1}) D_{x_n}^{r_n} \subseteq D_S^{\alpha-r_n e_n} CD_{x_n}^{r_n} + \mathcal{F}_{d_C, |\alpha|-1} \\
&\subseteq \mathcal{F}_{d_C, |\alpha|-1} + J.
\end{aligned}
$$

□
**Lemma 16.** For any $t \in \mathbb{N}$, $r \in \mathbb{Z}$, $CH_{t,r} \subseteq H_{d_C+t,r-1} + J$.

*Proof.* We have the chain of equalities and inclusions:

$$ 
\begin{aligned}
CH_{t,r} &= C \bigoplus_{|\beta| \le r \text{ or } \beta \in B} K[\mathbf{x}]_{\le t} D_S^\beta = \bigoplus_{|\beta| \le r \text{ or } \beta \in B} K[\mathbf{x}]_{\le t} CD_S^\beta \\
&\subseteq \sum_{\beta \in B} K[\mathbf{x}]_{\le d_C+t} D_S^\beta + \sum_{|\beta| \le r \text{ and } \beta \notin B} K[\mathbf{x}]_{\le t} \mathcal{F}_{d_C, |\beta|-1} + J \\
&\subseteq H_{d_C+t,r-1} + J,
\end{aligned}
$$

where the first inclusion is by Lemma 15. □

**Lemma 17.** For any $u, t \in \mathbb{N}$, $v \in \mathbb{Z}$, if $u \ge v$, then $C^u H_{t,v} \subseteq H_{t+ud_C,0} + J$. In particular, for all $\alpha \in \mathbb{N}^S$, $C^|\alpha| D_S^\alpha \in H_{|\alpha|d_C,0} + J$.

*Proof.* Note that for all $r' \le 0$, $H_{t,r'} = H_{t,0}$. The result is obtained by making $u$ repetitions of Lemma 16. □

Lemma 17 is specialized as follows.

**Lemma 18.** Set $u := v + 1 - \min_{i \in S} r_i$. Then $C^u H_{t,v} \subseteq H_{t+ud_C,0} + J$.

*Proof.* Observe that for any $\beta \in \mathbb{N}^S$, if $|\beta| < \min r_i$, then $\beta \in B$. Hence for any $r' < \min r_i$, $H_{t,r'} = H_{t,0}$. Again, the result is obtained by repeating the use of Lemma 16 $u$ times. □

**Observation 19.** For positive integers $D$ and $R$, define $N = 3D^2R$, then

$$ \binom{N+3}{3} - R \binom{DN+2}{2} > 0. $$

*Proof.* The result follows from the equality

$$ \binom{N+3}{3} - R \binom{DN+2}{2} = 9R^2 D^3 \left(D - \frac{1}{2}\right) + R \left(\frac{11}{2} D^2 - 1\right) + 1. $$

□

The following result provides structured annihilating operators of $f$ whose existence will be used in the proof of Theorem 6. It also provides degree bounds for all the announced annihilating operators, of which only those concerning $P$ will be used, in the specific situation of Corollary 22 ($n=2$).

**Theorem 20.** Let $f \in K[[\mathbf{x}]]$ be a $D$-finite power series over $K(\mathbf{x})$. Then, there exists a non-zero annihilating operator $P$ of $f$ that satisfies

* $P \in K[x_3, \dots, x_n][x_1x_2] \langle T_{x_1,x_2}, D_{x_1,x_2} \rangle,$

* $P$ is of degree $O(d_f^2 r_f^2)$ in $x_1x_2$, of total degree $O(d_f^9 r_f^8)$ in $x_3, \dots, x_n$, and of total degree $O(d_f^2 r_f^2)$ in $T_{x_1,x_2}, D_{x_1,x_2}$,
and for each $h \in \{3, \dots, n\}$, there exists a non-zero annihilating operator $Q_h$ of $f$ that satisfies

* $Q_h \in K[x_3, \dots, x_n][x_1x_2] \langle T_{x_1,x_2}, D_{x_h} \rangle,$

* $Q_h$ is of degree $O(d_f^2 r_f^3)$ in $x_1x_2$, of total degree $O(d_f^9 r_f^{12})$ in $x_3, \dots, x_n$, and of total degree $O(d_f^2 r_f^3)$ in $T_{x_1,x_2}, D_{x_h}$.

*Proof.* First we prove the existence of the operator $P$. We apply the counting argument used in [11, 13]. Use Definition 13 with $S = \{1, 2\}$. For any positive integer $N$, set

$$V_N = \operatorname{span}_{K(x_3, \dots, x_n)} \{C^{2N} (x_1 x_2)^i T_{x_1, x_2}^j D_{x_1, x_2}^\ell \mid i + j + \ell \le N\}$$

and

$$W_N = \operatorname{span}_{K(x_3, \dots, x_n)} \mathcal{H}_{2N(d_1+d_2+1),0}.$$

By degree considerations, for any integers $i, j, \ell$ satisfying $i + j + \ell \le N$ we have

$$(x_1 x_2)^i T_{x_1, x_2}^j D_{x_1, x_2}^\ell \in \mathcal{F}_{j+2i, j+2\ell} \subseteq \mathcal{H}_{j+2i, j+2\ell} \subseteq \mathcal{H}_{2N, 2N}.$$

Note that $\mathrm{tdeg}(C) \le d_C = d_1 + d_2$. Hence by Lemma 17,

$$C^{2N} (x_1 x_2)^i T_{x_1, x_2}^j D_{x_1, x_2}^\ell \in \mathcal{H}_{2N(d_1+d_2+1), 0} + J. \quad (5)$$

Consequently, we have the inclusion $V_N \subseteq W_N + K(x_3, \dots, x_n)J$ between $K(x_3, \dots, x_n)$-vector spaces. Note the asymptotic estimates

$$\dim_{K(x_3, \dots, x_n)} V_N = \binom{N+3}{3} = \Theta(N^3),$$

where the first equality is by Lemma 7, and

$$\dim_{K(x_3, \dots, x_n)} W_N = r_1 r_2 \binom{2N(d_1+d_2+1)+2}{2} = \Theta(N^2).$$

Choosing sufficient large $N$ results in $\dim(V_N) > \dim(W_N)$. So, some non-zero element of $V_N$ is in $K(x_3, \dots, x_n)J$ and without loss of generality we can choose it in $W_n \cap V_N$. Observe that this operator has $C^{2N}$ as a left factor. So, dividing by $C^{2N}$ yields a non-zero annihilating operator of $f$ in $K[x_1x_2, x_3, \dots, x_n] \langle D_{x_1}, D_{x_2} \rangle$.

To control the degree and order of such an annihilating operator, we now make a more specific choice that will lead to the announced operator $P$. To this end, we make (5) explicit in the form

$$C^{2N} (x_1 x_2)^i T_{x_1, x_2}^j D_{x_1, x_2}^\ell \in \sum_{\substack{i_1 < r_1, i_2 < r_2, \\ k_1 + k_2 \le 2N(d_1 + d_2 + 1)}} q_{i, j, \ell, i_1, i_2, k_1, k_2} x_1^{k_1} x_2^{k_2} D_{x_1}^{i_1} D_{x_2}^{i_2} + J,$$
for polynomials $q_{i,j,l,i_1,i_2,k_1,k_2}$ of $K[x_3, \dots, x_n]$ of total degree bounded by $2N(d_1 + d_2 + 1)$, and we set up an ansatz of the form

$$ C^{2N} P = \sum_{i+j+l \le N} p_{i,j,l} C^{2N} (x_1 x_2)^i T_{x_1, x_2}^j D_{x_1, x_2}^l \\ \in \sum_{\substack{i_1 < r_1, \ i_2 < r_2, \\ k_1 + k_2 \le 2N(d_1 + d_2 + 1)}} q_{i_1, i_2, k_1, k_2} x_1^{k_1} x_2^{k_2} D_{x_1}^{i_1} D_{x_2}^{i_2} + J, \qquad (6) $$

where the $p_{i,j,l}$ are undetermined polynomials from $K[x_3, \dots, x_n]$ and the resulting coefficients $q_{i_1,i_2,k_1,k_2}$ are polynomials of $K[x_3, \dots, x_n]$ given as linear combinations of the $p_{i,j,l}$ by

$$ q_{i_1, i_2, k_1, k_2} = \sum_{i+j+l \le N} p_{i,j,l} q_{i,j,l, i_1, i_2, k_1, k_2}. $$

After applying to $f$ to obtain

$$ C^{2N} P(f) = \sum_{\substack{i_1 < r_1, \ i_2 < r_2, \\ k_1 + k_2 \le 2N(d_1 + d_2 + 1)}} q_{i_1, i_2, k_1, k_2} x_1^{k_1} x_2^{k_2} D_{x_1}^{i_1} D_{x_2}^{i_2}(f), $$

we can enforce $P(f) = 0$ by forcing each $q_{i_1,i_2,k_1,k_2}$ to be zero. This gives a linear system over $K(x_3, \dots, x_n)$ with $\binom{N+3}{3}$ variables and a number $S$ of equations that is

$$ S := \dim_{K(x_3, \dots, x_n)} W_N = r_1 r_2 \binom{2N(d_1 + d_2 + 1) + 2}{2}. $$

Set $R := r_1 r_2$ and $D := 2(d_1 + d_2 + 1) \ge 2$. By Observation 19, we can choose $N := 3D^2 R$ so as to get a system with more variables than equations and thus a system with a non-trivial solution. Because the corresponding polynomial matrix is of size $S \times \binom{N+3}{3}$ with entries of total degree $2N(d_1 + d_2 + 1)$, by Lemma 4 we have, for a suitable non-zero solution $(p_{i,j,l})$,

$$ \mathrm{tdeg}(p_{i,j,l}) \le 2N(d_1 + d_2 + 1)r_1 r_2 \binom{2N(d_1 + d_2 + 1) + 2}{2} = O(d_f^9 r_f^8), $$

where the total degree is with respect to $x_3, \dots, x_n$. This non-trivial solution leads to a non-zero annihilator $P \in K[x_1 x_2, x_3, \dots, x_n] \langle T_{x_1, x_2}, D_{x_1, x_2} \rangle$ of $f$. From the ansatz form (6), $P$ has its degree in $x_1 x_2$ bounded by $N = O(d_f^2 r_f^2)$ and its total degree in $T_{x_1, x_2}, D_{x_1, x_2}$ not exceeding $N = O(d_f^2 r_f^2)$. This leads to the desired degree and order bounds for $P$.

For each $h \in \{3, \dots, n\}$, the proof of the existence of the operator $Q_h$ is similar. Using Definition 13 with $S = \{1, 2, h\}$, we set

$$ V_N = \mathrm{span}_{K(x_3, \dots, x_n)} \{C^N (x_1 x_2)^i T_{x_1, x_2}^j D_{x_h}^l \mid i + j + l \le N\}, $$

and

$$ W_N = \mathrm{span}_{K(x_3, \dots, x_n)} \mathcal{H}_{N(d_1+d_2+d_h+2), 0}. $$
This time we derive $V_N \subseteq \mathcal{H}_{2N, N}$ (not $\mathcal{H}_{2N, 2N}$) and we have the additional term $d_h$ in tdeg($C$) $\le d_C = d_1 + d_2 + d_h$, so that the analogue of (5) is

$$C^N(x_1 x_2)^i T_{x_1, x_2}^j D_{x_h}^\ell \in \mathcal{H}_{N(d_1+d_2+d_h+2), 0} + J.$$

Set $R := r_1 r_2 r_h$ and $D := d_1 + d_2 + d_h + 2 \ge 2$. We can still choose

$$N := 3D^2R = 3(d_1 + d_2 + d_h + 2)^2 r_1 r_2 r_h.$$

Then by Observation 19

$$\dim_{K(x_3, \dots, x_n)} V_N - \dim_{K(x_3, \dots, x_n)} W_N = \binom{N+3}{3} - R \binom{DN+2}{2} > 0.$$

Continuing as we did for $P$, we obtain that there exists a non-zero operator

$$Q_h \in K[x_1 x_2, x_3, \dots, x_n] \langle T_{x_1, x_2}, D_{x_h} \rangle$$

such that $Q_h(f) = 0$. By a similar argument, we have that $Q_h$ is of degree at most $N = O(d_f^2 r_f^3)$ in $x_1 x_2$, of total degree $O(d_f^9 r_f^{12})$ in $x_3, \dots, x_n$, and of total degree at most $N = O(d_f^2 r_f^3)$ in $T_{x_1, x_2}, D_{x_h}$. $\square$

After the preparation above, let us prove the diagonal theorem.

*Proof of Theorem 6.* Let $u_1, \dots, u_n$ be new variables. Write $K \langle\langle u_1, \dots, u_n \rangle\rangle$ for the associative $K$-algebra over the free non-commutative monoid generated by $\{u_1, \dots, u_n\}$. Assume that $f \in K([x])$ is D-finite over $K(x)$. By Theorem 20, there exists a non-zero operator $P \in K[x_1 x_2, x_3, \dots, x_n] \langle T_{x_1, x_2}, D_{x_1, x_2} \rangle$ and for each $h \in \{3, \dots, n\}$, a non-zero operator $Q_h \in K[x_1 x_2, x_3, \dots, x_n] \langle T_{x_1, x_2}, D_{x_h} \rangle$ such that $P(f) = 0$ and for each $h \in \{3, \dots, n\}$, $Q_h(f) = 0$.

We first show that there is a non-zero operator $\tilde{P} \in K(x_1, x_3, \dots, x_n) \langle D_{x_1} \rangle$ such that $\tilde{P}(\Delta_{1,2}(f)) = 0$. Recall that $T_{x_1, x_2}$ commutes with $x_1 x_2$ and $D_{x_1, x_2}$. Consider the maximal integer $s$ such that

$$P = T_{x_1, x_2}^s \cdot \tilde{P} \quad \text{with} \quad \tilde{P} = \sum_{i=0}^{m} T_{x_1, x_2}^i A_i(x_1 x_2, x_3, \dots, x_n, D_{x_1, x_2}) \quad (7)$$

for some $A_i \in K \langle\langle u_1, \dots, u_n \rangle\rangle$, where $A_i(\sigma_1, \dots, \sigma_n)$ denotes the evaluation at $u_1 = \sigma_1, \dots, u_n = \sigma_n$ of $A_i$ for elements $\sigma_1, \dots, \sigma_n \in W_n$. The maximality of $s$ implies $A_0 \ne 0$. By Lemma 11, we have

$$\tilde{P}(f) = \sum_{i=0}^{m} T_{x_1, x_2}^{i} A_i(f) = g(x_1 x_2, x_3, \dots, x_n) \quad (8)$$

for some power series $g$ in $n-1$ variables. Since $\Delta_{1,2} T_{x_1, x_2} = 0$ and by Proposition 10, taking the diagonal of the two sides of (8) yields

$$\Delta_{1,2} \tilde{P}(f) = A_0(x_1, x_3, \dots, x_n, D_{x_1} \theta_{x_1}) (\Delta_{1,2}(f)) = g(x_1, x_3, \dots, x_n).$$
The operator $H := A_0(x_1, x_3, \dots, x_n, D_{x_1} \theta_{x_1})$ is non-zero, since

$$x_1, x_3, \dots, x_n, D_{x_1} \theta_{x_1}$$

are linearly independent over $K$ by Lemma 8. Because $f$ is D-finite over $K(\boldsymbol{x})$, the series $\tilde{P}(f)$ is also D-finite over $K(\boldsymbol{x})$. Hence $g(x_1, x_3, \dots, x_n) = \tilde{P}(f)|_{x_2=1}$ is D-finite over $K(x_1, x_3, \dots, x_n)$ by Lemma 12. Therefore there exists a non-zero operator $G \in K(x_1, x_3, \dots, x_n) \langle D_{x_1} \rangle$ such that $G(g) = 0$. Then the operator $\tilde{P} := GH$ is non-zero and $\tilde{P}(\Delta_{1,2}(f)) = 0$.

The existence of a non-zero operator $\tilde{Q}_h \in K(x_1, x_3, \dots, x_n) \langle D_{x_h} \rangle$ such that $\tilde{Q}_h(\Delta_{1,2}(f)) = 0$ for each $h \in \{3, \dots, n\}$ is proved similarly. The only difference is the variation in the formula

$$\begin{aligned} \Delta_{1,2} A_0(x_1 x_2, x_3, \dots, x_n, D_{x_h})(f) &= A_0(x_1, x_3, \dots, x_n, D_{x_h}) \Delta_{1,2}(f) \\ &= g(x_1, x_3, \dots, x_n). \end{aligned}$$

Hence we conclude that $\Delta_{1,2}(f)$ is D-finite over $K(x_1, x_3, \dots, x_n)$. $\square$

<figure><img src="image_3.png" /></figure>

The following result is very much inspired by [12], which we merely generalize to the bivariate situation. The reader will pay attention that it combines bounds about a function $f$ provided by a system of equations, each in a single derivative like in Definition 2, with bounds on a (potentially) partial differential operator $L$, to derive bounds on equations in a single derivative for $L(f)$.

**Lemma 21.** Fix $n = 2$ and a bivariate D-finite function $f$. Given a system of linear differential equations with known order and degree bounds $r_f$ and $d_f$ exhibiting the D-finiteness of $f$, as well as an operator $L$ of order $r_L$ and degree $d_L$, there exists a system of linear differential equations exhibiting the D-finiteness of $g = L(f)$, whose order $r_g$ and degree $d_g$ are bounded by

$$d_g \le (d_L + 2d_f(r_f^2 + r_L))r_f^2 \quad \text{and} \quad r_g \le r_f^2. \qquad (9)$$

*Proof.* Use Definition 13 when $S = \{1, 2\}$. We look for non-zero operators $A \in K[x_1 x_2] \langle D_{x_1} \rangle$ annihilating $g$, that is, such that $(AL)(f) = 0$. Write $r_A$ and $d_A$ for the order and degree of a potential $A$. For $l \in K[x_1, x_2]$, if $\deg(l) \le d_L$, $0 \le k \le r_A$, and $0 \le i + j \le r_L$, then, by Lemma 17 we have

$$C^{r_A+r_L} D_{x_1}^k l(x_1, x_2) (D_{x_1}^i D_{x_2}^j) \in \mathcal{H}_{d_L+d_C(r_A+r_L),0} + J,$$

hence for a potential $A = \sum_{k=0}^{r_A} a_k(x_1, x_2) D_{x_1}^k$ we need to have

$$C^{r_A+r_L}(AL)(f) = \sum_{0 \le i < r_1} \sum_{0 \le j < r_2} a_k q_{i,j,k} D_{x_1}^i D_{x_2}^j(f)$$

for explicit polynomials $q_{i,j,k} \in K[x_1, x_2]$ of degree at most $d_L + d_C(r_A + r_L)$. Now, for this to be zero, the $r_A+1$ polynomial coefficients of $A$ need to cancel the $r_1 r_2 = O(r_f^2)$ equations obtained by equating the coefficients of the $K[x_1, x_2]$-linearly independent elements $D_{x_1}^i D_{x_2}^j(f)$ that appear in the sum. Setting $r_A =$
$r_1r_2$ ensures a non-zero solution exist, and Lemma 4 guarantees there exists a solution with degree $d_A$ at most $(d_L + d_C(r_A + r_L))r_A$. Looking for $A \in K[x_1x_2]\langle D_{x_2} \rangle$ leads to the same bounds, which leads to (9).

□

**Corollary 22.** Let $f \in K[[x_1, x_2]]$ be D-finite over $K(x_1, x_2)$. Then $\Delta_{1,2}(f)$ is D-finite over $K(x_1)$. In addition, there exists a non-zero operator $\bar{P}$ that satisfies $\bar{P}(\Delta_{1,2}(f)) = 0$ and

$$ \deg(\bar{P}) = O(d_f^3 r_f^4) \quad \text{and} \quad \text{ord}(\bar{P}) = O(d_f^2 r_f^2). $$

*Proof.* The first statement is just Theorem 6 in the case $n = 2$. For the degree bounds, we continue in the context of the proof of Theorem 6. Specifically, we have found:

* an operator $\tilde{P} = \tilde{P}(x_1x_2, T_{x_1,x_2}, D_{x_1,x_2})$ that is a factor of an operator $P$ that we obtained by Theorem 20 and therefore satisfies that its degree in $x_1x_2$ and its degree in $D_{x_1,x_2}$ are both $O(d_f^2 r_f^2)$,

* a univariate power series $g$ such that $\tilde{P}(f) = g(x_1x_2)$,

* a non-zero operator $H = H(x_1, D_{x_1}\theta_{x_1})$ such that $H(x_1x_2, D_{x_1,x_2})$ is the coefficient of $T_{x_1,x_2}^0$ in $\tilde{P}$ and $H(\Delta_{1,2}(f)) = g(x_1)$.

By construction, both $\tilde{P}$ and $H$ admit the same bounds on order and degree as $P$, in particular, both $\text{ord}(H)$ and $\text{deg}(H)$ are in $O(d_f^2 r_f^2)$. Now, Lemma 21 applies to the D-finite function $f$ and the operator $H$ to prove the existence of a non-zero annihilator $G \in K[x_1]\langle D_{x_1} \rangle$ of $g$ satisfying

$$ \deg(G) \le (\deg(H) + 2d_f(r_f^2 + \text{ord}(H)))r_f^2 = O(d_f^3 r_f^4) \quad \text{and} \quad \text{ord}(G) \le r_f^2 $$

as a consequence of (9). Setting $\bar{L} = GH$ and observing that $H$ has lower bounds than $g$ gives the announced result. □

**Remark 23.** It is unsatisfactory that we could not find and apply a one-stage variant of Gessel's approach, especially in view of the bivariate case in which it outperforms Lipshitz's approach that is developed in the next section. After this work, it would still be of interest to derive such a direct variant.

## 4. Lipshitz's method for bounds of diagonal

In this section, we analyze the method of Lipshitz [13] and we make specific choices in it so as to construct annihilating operators of a diagonal and to derive upper bounds on their order and degree.

Let us provide definitions that generalize those of Section 1. Given integers $n$ and $m$ satisfying $0 \le m \le n-1$, we use the notation $s$ for $s_1, \dots, s_m$ and $\hat{s}$ for $x_{m+1}, \dots, x_n$. In particular, the list $s$ is empty if $m = 0$, which was the setting in Section 1. The variable $x_{m+1}$ is denoted by $t$ if $m \ge 1$: in this new situation,
our goal is to take a diagonal with respect to $s, t = s_1, \dots, s_m, x_{m+1}$, keeping $\hat{x} = x_{m+2}, \dots, x_n$ as parameters. For primary diagonals there is a single $s_i$ ($m=1$), and we more simply denote $s_1$ by $s$. In other words, we have:

$$ \mathbf{s}, \hat{\mathbf{x}} = \begin{cases} x_1, \dots, x_n & \text{if } m=0, \\ s, t (= x_2), x_3, \dots, x_n & \text{if } m=1, \\ s_1, \dots, s_m, t (= x_{m+1}), x_{m+2}, \dots, x_n & \text{if } m \ge 2. \end{cases} $$

The definitions of $\tau$ that will be needed, (12) in the present section and (41) in Section 4.2, motivate that we accommodate series with negative exponents by defining

$$ M := \bigcup_{k \in \mathbb{N}} \bigoplus_{|\alpha|+|\beta| \ge -k} K s^{\alpha} \hat{x}^{\beta} \subseteq K^{\mathbb{Z}^m \times \mathbb{N}^{n-m}}, $$

where $\alpha := (\alpha_1, \dots, \alpha_m) \in \mathbb{Z}^m$ and $\beta := (\beta_{m+1}, \dots, \beta_n) \in \mathbb{N}^{n-m}$. This set $M$ is a module over $K[\mathbf{s}, \hat{\mathbf{x}}] \langle \mathbf{D}_s, \mathbf{D}_{\hat{\mathbf{x}}} \rangle$, but it is not a $K(\mathbf{s}, \hat{\mathbf{x}})$-vector space. If $m=0$, then $\mathbf{x} = \hat{\mathbf{x}}$ and $M$ is just the ring $K[[\mathbf{x}]]$ of formal power series.

**Definition 24 (D-finiteness).** An element $F \in M$ is D-finite over $K(\mathbf{s}, \hat{\mathbf{x}})$ if the $K(\mathbf{s}, \hat{\mathbf{x}})$-vector space generated by the derivatives of $F$ in $\mathcal{T} := K(\mathbf{s}, \hat{\mathbf{x}}) \otimes_{K[\mathbf{s}, \hat{\mathbf{x}}]} M$ is finite-dimensional, after identifying each element $m \in M$ with $1 \otimes m \in \mathcal{T}$.

The reader will pay attention to the redefinition of a number of quantities in Sections 4.1.1 and 4.1.2, including $M, S, B, C, d_C, R, N, G_N, V_N, W_N, \phi$.

### 4.1. Bounds for primary diagonal

We analyze the behavior of the primary diagonal operator $\Delta_{2,1}$ and derive the following theorem, which gives bounds on order and degree for linear differential operators that annihilate $\Delta_{2,1}(f)$. The rest of the section consists of the proof of this theorem, with the bounds (10) proven by Lemma 32 and the bounds (11) proven by Lemma 34.

**Theorem 25.** Let $f \in K[[\mathbf{x}]]$ be D-finite over $K(\mathbf{x})$ and let $d_i, f_i, d_f, r_f$ be as in Definition 2. Then, there exists a non-zero annihilating operator $P_\alpha$ of $\Delta_{2,1}(f)$ in $K[t, x_3, \dots, x_n] \langle D_i \rangle$ that satisfies

$$ \deg(P_{\alpha}) \le 8(d_1 + d_2 + 1)^2 (r_1 r_2)^2 (8(d_1 + d_2 + 1)^2 r_1 r_2 + 1) = O(d_f^4 r_f^6), \quad (10) $$

$$ \mathrm{ord}(P_{\alpha}) \le 4(d_1 + d_2 + 1) r_1 r_2 = O(d_f r_f^2), $$

and for each $h \in \{3, \dots, n\}$, there exists a non-zero annihilating operator $P_{h,\alpha_h}$ of $\Delta_{2,1}(f)$ in $K[t, x_3, \dots, x_n] \langle D_{x_h} \rangle$ that satisfies

$$ \begin{aligned} \deg(P_{h,\alpha_h}) &\le 8(d_1 + d_2 + d_h + 1)^2 (r_1 r_2 r_h)^2 (8(d_1 + d_2 + d_h + 1)^2 r_1 r_2 r_h + 1) \\ &= O(d_f^4 r_f^9), \\ \mathrm{ord}(P_{h,\alpha_h}) &\le 4(d_1 + d_2 + d_h + 1) r_1 r_2 r_h = O(d_f r_f^3). \end{aligned} \quad (11) $$
We specialize our setting by choosing $m = 1$, that is, we make $s, \hat{x} = s, t, x_3, \dots, x_n$. We aim to refine Lipshitz's proof [13, Lemma 3] of existence of annihilating operators in $K[\hat{x}]\langle D_s, D_{x_i} \rangle$ for $i = 2, \dots, n$. Recall the notation $S = K(\boldsymbol{x}) \otimes_{K[\hat{x}]} K[\boldsymbol{x}]$ from the introduction. We define two maps $\sigma$ and $\tau$ from $S$ to $M$ by

$$ \tau(h(\boldsymbol{x})) = h\left(s, \frac{t}{s}, x_3, \dots, x_n\right) \quad \text{and} \quad \sigma(h(\boldsymbol{x})) = \frac{\tau(h(\boldsymbol{x}))}{s}. \qquad (12) $$

Hence, $\tau$ is a ring morphism and we have

$$ \sigma(gh) = \tau(g)\sigma(h) \quad \text{for any } g, h \text{ in } S. \qquad (13) $$

**Lemma 26.** Let $P$ be any non-zero operator

$$ P = P(\hat{x}; D_t, D_s) = \sum_{j=\alpha}^{\beta} P_j(\hat{x}; D_t) D_s^j \in K[\hat{x}]\langle D_t, D_s \rangle \qquad (14) $$

for which $P_\alpha \neq 0$, and let $g \in \sum_{i \in \mathbb{Z}} g_i(\hat{x})s^i$ be any element of $M$. Then, the coefficient of $s^{-1-\alpha}$ in $P(g)$ is $P_\alpha(g_{-1})$.

Similarly, for any $h \in \{3, \dots, n\}$, if $P_h$ is a non-zero operator

$$ P_h = P_h(\hat{x}; D_{x_h}, D_s) = \sum_{j=\alpha_h}^{\beta_h} P_{h,j}(\hat{x}; D_{x_h}) D_s^j \in K[\hat{x}]\langle D_{x_h}, D_s \rangle, \qquad (15) $$

for which $P_{h,\alpha_h} \neq 0$, then the coefficient of $s^{-1-\alpha}$ in $P_h(g)$ is $P_{\alpha_h}(g_{-1})$.

*Proof.* Note that

$$ D_s^j(g) = D_s^j\left(\sum_{i \leq -2} g_i(\hat{x})s^i\right) + (-1)^j j! g_{-1}(\hat{x})s^{-1-j} + D_s^j\left(\sum_{i \geq 0} g_i(\hat{x})s^i\right), $$

where the first term has all exponents less than $-1-j$ and the last has all exponents at least 0: only the middle term contributes to the coefficient of $s^{-1-j}$. So, for $j \ge \alpha$, some contribution to the coefficient of $s^{-1-\alpha}$ is only possible if $j = \alpha$, proving the result for the case $P = P(\hat{x}; D_t, D_s)$. The proof for the other cases is the same. $\square$

Consider any non-necessarily D-finite series

$$ f = \sum_{i_1, \dots, i_n \ge 0} a_{i_1, \dots, i_n} x_1^{i_1} \cdots x_n^{i_n} \in K[\boldsymbol{x}] \qquad (16) $$

and the corresponding element $\sigma(f)$ of $M \subseteq \mathcal{T}$. By Definition 3 (diagonals) and because we write $t$ for $x_2$, the primary diagonal $\Delta_{2,1}(f)$ is

$$ \Delta_{2,1}(f) = \sum_{i_1, i_3, \dots, i_n \ge 0} a_{i_1, i_3, \dots, i_n} t^{i_1} x_3^{i_3} \cdots x_n^{i_n} \in K[\hat{x}]. $$

By the definition (12) of $\tau$ and $\sigma$, this diagonal is the coefficient of degree $s^{-1}$ in $\sigma(f)$. The following lemma immediately follows, as a consequence of Lemma 26.
**Lemma 27.** Let $f$ be as in (16). If $P(f) = 0$ for $P$ and $P_\alpha \neq 0$ as in (14), then $P_\alpha$ annihilates $\Delta_{2,1}(f)$. For any $h \in \{3, \dots, n\}$, if $P_h(f) = 0$ for $P_h$ and $P_{h,\alpha_h} \neq 0$ as in (15), then $P_{h,\alpha_h}$ annihilates $\Delta_{2,1}(f)$.

In the next two subsections, when $f$ is D-finite we will construct operators $P$ and $P_h$ to be used in the previous lemma.

#### 4.1.1. Controlling and combining the $D_s^i D_t^j(\sigma(f))$

We construct an operator $P \in K[\hat{x}]\langle D_t, D_s \rangle$ such that $P(\sigma(f)) = 0$. To this end, we introduce two vector spaces depending on $N \in \mathbb{N}$,

$$V_N = A_N \cdot \operatorname{span}_{K(\hat{x})} \{D_s^i D_t^j \mid i + j \le N\} \quad (17)$$

and

$$W_N = \operatorname{span}_{K(\hat{x})} \{s^\alpha \sigma(D_x^\beta f) \mid \alpha \le DN, \beta \in B\}, \quad (18)$$

where $B$ is a finite set and $A_N$ is a polynomial, both to be determined (see Lemma 31). We will prove that the map defined by $\phi(P) := P(\sigma(f))$ is $K(\hat{x})$-linear from $V_N$ to $W_N$, that it is non-injective for large enough $N$ (see Lemma 32). As a by-product, we will get an annihilator $P_\alpha$ of $\Delta_{2,1}(f)$ with controled degree and order (see again Lemma 32).

Denote $D_i := D_{x_i}$ for $i = 1, \dots, n$.

**Lemma 28.** We have for all $g \in S$:

$$ \begin{aligned} D_s(\sigma(g)) &= \sigma\left((-x_1^{-1} + D_1 - x_1^{-1}x_2D_2)(g)\right), \\ D_t(\sigma(g)) &= \sigma\left((x_1^{-1}D_2)(g)\right), \\ D_{x_h}(\sigma(g)) &= \sigma(D_h(g)), \quad h = 3, \dots, n. \end{aligned} $$

*Proof.* For the first two identities, write the following two equations by the chain rule, then use the formulas $\tau(x_1) = s$, $\tau(x_2) = t/s$, and (13):

$$ \begin{aligned} D_s(\sigma(g)) &= -\frac{1}{s}\sigma(g) + \sigma(D_1(g)) - \frac{t}{s^2}\sigma(D_2(g)), \\ D_t(\sigma(g)) &= \frac{1}{s}\sigma(D_2(g)). \end{aligned} $$

The third identity is obvious. $\square$

Define for any $N \in \mathbb{N}$:

$$\mathcal{G}_N := \bigoplus_{a+b \le N} x_1^{-N} K[x_1, x_2]_{\le N} D_1^a D_2^b. \quad (19)$$

**Lemma 29.** For all $g \in S$ and all non-negative integers $i$ and $j$, $D_t^j D_s^i(\sigma(g))$ is an element of $\sigma(\mathcal{G}_{i+j}(g))$.
*Proof.* It follows immediately from Lemma 28 that, for all $i, j \in \mathbb{N}$,

$$ 
\begin{aligned}
D_t^j D_s^i (\sigma(g)) &= D_t^j \sigma ((-x_1^{-1} + D_1 - x_1^{-1} x_2 D_2)^i(g)) \\
&= \sigma ((x_1^{-1} D_2)^j (-x_1^{-1} + D_1 - x_1^{-1} x_2 D_2)^i(g)).
\end{aligned} 
\quad (20) $$

Consider an element $x^{-ip} D_1^a D_2^b$ of $\mathcal{G}_i$, or equivalently, integers $a$ and $b$ and a polynomial $p \in K[x_1, x_2]$ satisfying $a+b \le i$ and $\mathrm{tdeg}(p) \le i$. We observe that

$$ 
\begin{aligned}
\left(-\frac{1}{x_1} + D_1 - \frac{x_2}{x_1} D_2\right) \left(\frac{p}{x_1^i} D_1^a D_2^b\right) &= \\
&\frac{1}{x_1^{i+1}} \left( -p D_1^a D_2^b - ip D_1^a D_2^b + x_1 D_1(p) D_1^a D_2^b + x_1 p D_1^{a+1} D_2^b \right. \\
&\qquad \left. - x_2 D_2(p) D_1^a D_2^b - x_2 p D_1^a D_2^{b+1} \right)
\end{aligned} 
$$

is in $\mathcal{G}_{i+1}$. Therefore, $(-\frac{1}{x_1} + D_1 - \frac{x_2}{x_1} D_2) \mathcal{G}_i \subseteq \mathcal{G}_{i+1}$, by linearity. We derive similarly

$$ \left(\frac{1}{x_1} D_2\right) \left(\frac{1}{x_1^i} p(x_1, x_2) D_1^a D_2^b\right) = \frac{1}{x_1^{i+1}} \left(D_2(p) D_1^a D_2^b + p D_1^a D_2^{b+1}\right) \in \mathcal{G}_{i+1}, $$

and $(\frac{1}{x_1} D_2) \mathcal{G}_i \subseteq \mathcal{G}_{i+1}$. Since $1 \in \mathcal{G}_0$, we get by induction that for all $i, j \in \mathbb{N}$,

$$ \left(\frac{1}{x_1} D_2\right)^j \left(-\frac{1}{x_1} + D_1 - \frac{x_2}{x_1} D_2\right)^i \in \mathcal{G}_{i+j}. $$

□

**Lemma 30.** For any integers $p$ and $q$, we have:

$$ \tau \left( \frac{1}{x_1^q} K[x_1, x_2]_{\le p} \right) \subseteq \frac{K[s, t]_{\le 2p}}{s^{p+q}} \quad \text{and} \quad \tau (K[\mathbf{x}]_{\le p}) \subseteq \frac{K[s, \hat{\mathbf{x}}]_{\le 2p}}{s^p}. $$

*Proof.* Both formulas follow by linearity from the action of $\tau$ on monomials:

$$ \tau(x_1^i x_2^j) = \frac{s^{i+(p-j)} t^j}{s^p} \in \frac{K[s, t]_{\le p+i}}{s^p} \quad \text{if } i+j \le p; $$

$$ \tau(\mathbf{x}^i) = \frac{s^{i_1+(p-i_2)} x_2^{i_2} \cdots x_n^{i_n}}{s^p} \in \frac{K[s, \hat{\mathbf{x}}]_{\le p+i_1}}{s^p} \quad \text{if } |\mathbf{i}| \le p. $$

□

**Lemma 31.** Consider $B := \{0, 1, \dots, r_1 - 1\} \times \{0, 1, \dots, r_2 - 1\}$, the polynomial $C$, and $d_C = d_1 + d_2 \le 2d_f$ as set by Definition 13 for $S := \{1, 2\}$. Fix $N \in \mathbb{N}$ and set $D := 2+2d_C \ge 2$ and $A_N(s, \hat{\mathbf{x}}) := s^{(d_C+2)N} \cdot \tau(C^N) \in K[s, \hat{\mathbf{x}}]$. Then, if $i+j \le N$, then

$$ D_s^i D_t^j (\sigma(f)) \in \sum_{\substack{\alpha \le DN \\ \beta \in B}} \frac{K[\hat{\mathbf{x}}]_{\le DN}}{A_N(s, \hat{\mathbf{x}})} s^\alpha \sigma(D_x^\beta f). \quad (21) $$
Proof. If $i + j \le N$, then Lemma 29, Equation (13) and Lemma 30 imply

$$
\begin{align}
D_s^i D_t^j (\sigma(f)) \in \sigma(\mathcal{G}_{i+j}(f)) &\subseteq \sigma(\mathcal{G}_N(f)) \nonumber \\
&= \sum_{a+b \le N} \tau(x_1^{-N} K[x_1, x_2]_{\le N}) \sigma(D_1^a D_2^b(f)) \tag{22} \\
&\subseteq \sum_{a+b \le N} \frac{K[s, t]_{\le 2N}}{s^{2N}} \sigma(D_1^a D_2^b(f)). \nonumber
\end{align}
$$

Next, by Definition 13 for $S := \{1, 2\}$ and by Lemma 17 with $u := N \ge v := a+b$ and $t := 0$, we have

$$
D_1^a D_2^b \in \mathcal{H}_{0,a+b} \subseteq \frac{1}{C^N} \mathcal{H}_{NdC,0} + \frac{1}{C^N} J.
$$

Applying to $f$, then applying $\sigma$, yields, appealing again to (13), next again to Lemma 30:

$$
\sigma(D_1^a D_2^b(f)) \in \frac{1}{\tau(C^N)} \sigma(\mathcal{H}_{NdC,0}(f)) \subseteq \sum_{\beta \in B} \frac{K[s, \hat{x}]_{\le 2d_C N}}{s^{d_C N} \cdot \tau(C^N)} \sigma(D_x^\beta f). \quad (23)
$$

Combining (22) and (23) and using $t = x_2$, we obtain (21) where $D$ and $A_N$ are set as in the lemma statement. $\square$

**Lemma 32.** There exists a non-zero annihilator $P_\alpha(\hat{x}; D_t)$ of $\Delta_{2,1}(f)$ satisfying (10).

Proof. Recall the definitions (17) and (18) of $V_N$ and $W_N$, where $A_N$ and $B$ are now fixed. Lemma 31 has proved that the $K(\hat{x})$-linear map defined by $\phi(P) := P(\sigma(f))$ is from $V_N$ to $W_N$. Note that

$$
\dim_{K(\hat{x})} V_N = \binom{N+2}{2}, \quad \dim_{K(\hat{x})} W_N \le R(DN+1), \quad (24)
$$

where $R := r_1 r_2 = O(r_f^2)$. Fix

$$
N = 2DR = 4(d_1 + d_2 + 1) r_1 r_2 = O(d_f r_f^2), \quad (25)
$$

so that

$$
\dim_{K(\hat{x})} V_N - \dim_{K(\hat{x})} W_N = (3D - 1)R + 1 > 0 \quad (26)
$$

and $\phi$ is non-injective. For all $i,j$ with $i+j \le N$, by Lemma 31 there exist polynomials $q_{\alpha,\beta}^{(i,j)} \in K[\hat{x}]$ satisfying $\text{tdeg}(q_{\alpha,\beta}^{(i,j)}) \le DN$ and

$$
A_N \cdot D_s^i D_t^j (\sigma(f)) = \sum_{\substack{\alpha \le DN \\ \beta \in B}} q_{\alpha, \beta}^{(i,j)} s^\alpha \sigma(D_x^\beta f) \in W_N.
$$

A witness of non-injectivity will be provided by polynomials $p_{i,j} \in K[\hat{x}]$ such that

$$
\sum_{i+j \le N} p_{i,j}(\hat{x}) \cdot A_N D_s^i D_t^j(\sigma(f)) = 0,
$$
that is, by coefficient extraction, such that for all $\alpha \le DN$ and $\beta \in B$,

$$ \sum_{i+j \le N} p_{i,j} q_{\alpha, \beta}^{(i,j)} = 0. $$

Hence we have a linear system

$$ \left( \dots \begin{array}{c} \dots \\ \dots q_{\alpha, \beta}^{(i,j)} \dots \\ \dots \end{array} \right) \cdot \left( \begin{array}{c} \vdots \\ \vdots p_{i,j} \\ \vdots \end{array} \right) = 0, $$

where the polynomials $q_{\alpha,\beta}^{(i,j)}$ have total degree at most $DN$. This system has $\dim_{K(\hat{x})} W_N$ rows and $\dim_{K(\hat{x})} V_N$ columns, where those dimensions are given by (24), and by the inequality (26) it has more columns than rows. So, Lemma 4 applies and leads to a non-zero solution $(p_{i,j})$ satisfying

$$ \mathrm{tdeg}(p_{i,j}) \le DN \cdot R(ND + 1) = O(D^4 R^3) = O(d_f^4 r_f^6), $$

where we used (25). The operator $P := \sum_{i+j \le N} p_{i,j} D_s^i D_t^j$ satisfies $P(\sigma(f)) = 0$ and can be written

$$ P = \sum_{i=\alpha}^{\beta} P_i(\hat{x}; D_t) D_s^i $$

with $P_{\alpha}(\hat{x}; D_t) \neq 0$. Then $P_{\alpha}$ annihilates $\Delta_{2,1}(f)$ and satisfies the announced bounds (10). $\square$

### 4.1.2. Controlling and combining the $D_s^i D_{x_h}^j$ ($\sigma(f)$)

For each $h \in \{3, \dots, n\}$, we proceed by an argument similar to the argument of Section 4.1.1 to construct an operator $P_h \in K[\hat{x}]\langle D_{x_h}, D_s \rangle$ such that $P_h(\sigma(f)) = 0$. The proof is a bit simpler, because the action of $D_{x_h}$ on $\sigma(f)$ is simpler that the action of $D_t$ on it. This time, we consider $B = \{0, 1, \dots, r_1\} \times \{0, 1, \dots, r_2\} \times \{0, 1, \dots, r_h\}$, the polynomial $C$, and $d_C = d_1 + d_2 + d_h \le 3d_f$ as set by Definition 13 for $S := \{1, 2, h\}$. In analogy with (10) and (11), for each $N \in \mathbb{N}$, we introduce

$$ V_N = A_N \cdot \mathrm{span}_{K(\hat{x})} \{D_s^i D_{x_h}^j \mid i + j \le N\}, \quad (27) $$

where $A_N = s^{(d_C+2)N} \cdot \tau(C^N) \in K[s, \hat{x}]$, and

$$ W_N = \mathrm{span}_{K(\hat{x})} \{s^{\alpha} \sigma(D_x^{\beta} f) \mid \alpha \le DN, \beta \in B\}, \quad (28) $$

where $D = 2 + 2d_C = O(d_f)$. We will again prove that the map defined by $\phi(P) := P(\sigma(f))$ is $K(\hat{x})$-linear from $V_N$ to $W_N$.

In analogy with (19), define for any $N \in \mathbb{N}$:

$$ \mathcal{G}_N := \bigoplus_{a+b+c \le N} x_1^{-N} K[x_1, x_2]_{\le N} D_1^a D_2^b D_{x_h}^c. \quad (29) $$
**Lemma 33.** Let B, C, and d_C be as defined at the beginning of Section 4.1.2, that is, as set by Definition 13 for S := {1, 2, h}. Then, if i + j ≤ N, then

$$D_s^i D_{x_h}^j (\sigma(f)) \in \sum_{\substack{\alpha \le DN \\ \beta \in B}} \frac{K[\hat{x}]_{\le DN}}{A_N(s, \hat{x})} s^\alpha \sigma(D_x^\beta f). \quad (30)$$

*Proof.* If i + j ≤ N, then Lemma 29, the definition (29), Equation (13) and Lemma 30 imply

$$\begin{align}
D_s^i D_{x_h}^j (\sigma(f)) &\in D_{x_h}^j \sigma(G_i(f)) \subseteq \sigma(G_{i+j}(f)) \subseteq \sigma(G_N(f)) \nonumber \\
&= \sum_{a+b+c \le N} \tau(x_1^{-N} K[x_1, x_2]_{\le N}) \sigma(D_1^a D_2^b D_{x_h}^c(f)) \tag{31} \\
&\subseteq \sum_{a+b+c \le N} \frac{K[s, t]_{\le 2N}}{s^{2N}} \sigma(D_1^a D_2^b D_{x_h}^c(f)). \nonumber
\end{align}$$

Next, by Lemma 17 with $u := N \ge v := a + b + c$ and $t := 0$, we have

$$D_1^a D_2^b D_{x_h}^c \in \mathcal{H}_{0,a+b+c} \subseteq \frac{1}{C^N} \mathcal{H}_{Nd_C,0} + \frac{1}{C^N} J.$$

Applying to $f$, then applying $\sigma$, yields, appealing again to (13), next again to Lemma 30:

$$\sigma(D_1^a D_2^b D_{x_h}^c(f)) \in \frac{1}{\tau(C^N)} \sigma(H_{Nd_C,0}(f)) \subseteq \sum_{\beta \in B} \frac{K[s, \hat{x}]_{\le 2d_C N}}{s^{d_C N} \cdot \tau(C^N)} \sigma(D_x^\beta f). \quad (32)$$

Combining (31) and (32) and using $t = x_2$, we obtain (30) where D and $A_N$ are set as in the lemma statement. □

**Lemma 34.** There exists a non-zero annihilator $P_\alpha(\hat{x}; D_{x_h})$ of $\Delta_{2,1}(f)$ satisfying (11).

*Proof.* Recall the definitions (27) and (28) of $V_N$ and $W_N$. Lemma 33 has proved that the $K(\hat{x})$-linear map defined by $\phi(P) := P(\sigma(f))$ is from $V_N$ to $W_N$. Note that

$$\dim_{K(\hat{x})} V_N = \binom{N+2}{2}, \quad \dim_{K(\hat{x})} W_N \le R(DN+1),$$

where $R := r_1 r_2 f_h = O(r_f^3)$, and fix

$$N = 2DR = 4(d_1 + d_2 + d_h + 1) r_1 r_2 r_h = O(d_f r_f^3). \quad (33)$$

The last three formulas in terms of R and D are the same as in Lemma 34, with only the values of R and D changed, so the inequality

$$\dim_{K(\hat{x})} V_N - \dim_{K(\hat{x})} W_N = (3D - 1)R + 1 > 0 \quad (34)$$
holds again, and $\phi$ is non-injective. The proof by linear algebra continues as in the proof of Lemma 32, recombining expressions $A_N D_s^i D_{x_h}^j(\sigma(f))$ instead of expressions $A_N D_s^i D_t^j(\sigma(f))$. It constructs a non-zero operator

$$P_h := \sum_{i+j \le N} p_{i,j} D_s^i D_{x_h}^j = \sum_{i=\alpha_h}^{\beta_h} P_{h,i}(\hat{x}; D_{x_h}) D_s^i \in K[\hat{x}]\langle D_s, D_{x_h} \rangle$$

satisfying $P_h(\sigma(f)) = 0$, $P_{h,\alpha_h} \ne 0$, and

$$\mathrm{tdeg}(p_{i,j}) \le ND \cdot R(ND + 1) = O(D^4 R^3) = O(d_f^4 r_f^9). \quad (35)$$

Then $P_{h,\alpha_h}$ annihilates $\Delta_{2,1}(f)$ and satisfies the announced bounds (11). $\square$

### 4.1.3. Iterating primary diagonals

We can now estimate bounds on the degree and order of an annihilating operator for the complete diagonal of $f$ obtained by successive primary diagonals. In analogy with the definition (1) of the complete diagonal, we consider the partial diagonal

$$g := \Delta_{k+1,k} \Delta_{k,k-1} \cdots \Delta_{2,1}(f) \in K[[x_{k+1}, \dots, x_n]].$$

obtained after $k$ iterations of a primary diagonal. Assume that there exists a non-zero annihilating operator for $g$ with respective degree and order bounds

$$O(d_f^{u(k)} r_f^{v(k)}) \quad \text{and} \quad O(d_f^{s(k)} r_f^{t(k)}). \quad (36)$$

By Theorem 25 applied to $f = g$, there exists a non-zero annihilating operator for $\Delta_{k+2,k+1}(g)$, with respective degree and order bounds analogous to (36) for exponents $u(k+1), v(k+1), s(k+1), t(k+1)$ given by

$$\begin{pmatrix} u(k+1) & v(k+1) \\ s(k+1) & t(k+1) \end{pmatrix} = \begin{pmatrix} 4 & 9 \\ 1 & 3 \end{pmatrix} \cdot \begin{pmatrix} u(k) & v(k) \\ s(k) & t(k) \end{pmatrix}.$$

Here, the entries of the constant matrix are obtained as the maximums of the exponents appearing in the big $O$ terms in (10) and (11). This sets up a recurrence that we proceed to analyze. The matrix $\begin{pmatrix} 4 & 9 \\ 1 & 3 \end{pmatrix}$ has two eigenvalues satisfying $\lambda^2 - 7\lambda + 3 = 0$, namely

$$\lambda_1 := \frac{7 + \sqrt{37}}{2} \approx 6.54\dots, \quad \lambda_2 := \frac{7 - \sqrt{37}}{2} \approx 0.46\dots \quad (37)$$
Taking initial values for $s, t, u, v$ in to account, we get

$$
\begin{align}
s(k) &= \frac{1}{\sqrt{37}} \lambda_1^k - \frac{1}{\sqrt{37}} \lambda_2^k &\approx (0.16 \dots) \lambda_1^k - (0.16 \dots) \lambda_2^k, \nonumber \\
t(k) &= \left(\frac{1}{2} - \frac{1}{2\sqrt{37}}\right) \lambda_1^k + \left(\frac{1}{2} + \frac{1}{2\sqrt{37}}\right) \lambda_2^k &\approx (0.42 \dots) \lambda_1^k + (0.58 \dots) \lambda_2^k, \nonumber \\
u(k) &= \left(\frac{1}{2} - \frac{5}{2\sqrt{37}}\right) \lambda_1^k + \left(\frac{1}{2} + \frac{5}{2\sqrt{37}}\right) \lambda_2^k &\approx (0.09 \dots) \lambda_1^k + (0.91 \dots) \lambda_2^k, \nonumber \\
v(k) &= \frac{9}{\sqrt{37}} \lambda_1^k - \frac{9}{\sqrt{37}} \lambda_2^k &\approx (1.48 \dots) \lambda_1^k - (1.48 \dots) \lambda_2^k. \tag{38}
\end{align}
$$

Degree and order bounds for an annihilating operator $P$ of $\Delta(f)$ are obtained for $k = n - 1$, and (38) leads to the respective asymptotic formulas

$$
\deg(P) = O \left( d_f^{u(n-1)} r_f^{v(n-1)} \right) = d_f^{O(\lambda_1^n)} r_f^{O(\lambda_1^n)},
$$

$$
\mathrm{ord}(P) = O \left( d_f^{s(n-1)} r_f^{t(n-1)} \right) = d_f^{O(\lambda_1^n)} r_f^{O(\lambda_1^n)}.
$$

when $n, d_f$, and $r_f$ tend independently to infinity, and where the constants in
the big $O$'s are small (at most 1).

4.2. Complete diagonal in a single step

Following [13, Remarks, item (3)], instead of iterating primary diagonal
transformations, we can get the operator that annihilates the complete diagonal
of $f$ in a single step. The goal of this subsection is indeed the construction of a
specific linear differential operator annihilating $\Delta(f)$ that satisfies the bounds
presented in the following theorem. These bounds are simply exponential in $n$,
and therefore asymptotically smaller than the bounds obtained by the method
by iteration, which are doubly exponential in $n$.

**Theorem 35.** Let $f \in K[[x]]$ be $D$-finite over $K(x)$ and let $d_i, f_i, d_f, r_f$ be as in Definition 2. Then, there exists an annihilating operator $\tilde{P}$ of $\Delta(f)$ in $K[t]\langle D_t \rangle$ that satisfies, for all $\varepsilon > 0$,

$$
\deg(\tilde{P}) \le N' = O((2+\varepsilon)^n n^{2n} d_f^{n-1} r_f^n), \quad \mathrm{ord}(\tilde{P}) \le N = O((2+\varepsilon)^n n^{2n-1} d_f^{n-1} r_f^n), \tag{39}
$$

when $n, d_f$, and $r_f$ tend independently to infinity, and where

$$
N' = (2D + 1)^n \prod_{j=1}^{n} r_j, \quad N = \frac{(2D + 1)^n}{D} \prod_{j=1}^{n} r_j, \quad \text{for } D = n \left(2 + \sum_{i=1}^{n} d_i\right). \quad (40)
$$

To prepare for the proof, we specialize the setting introduced at the
beginning of Section 4 by setting $m = n - 1$, so that $t = x_n$, and we define
two maps $\sigma$ and $\tau$ from $S$ to $M$ by

$$
\tau(h(\mathbf{x})) = h \left( s_1, \frac{s_2}{s_1}, \frac{s_3}{s_2}, \dots, \frac{s_{n-1}}{s_{n-2}}, \frac{t}{s_{n-1}} \right) \quad \text{and} \quad \sigma(h(\mathbf{x})) = \frac{\tau(h(\mathbf{x}))}{s_1 \cdots s_{n-1}}, \quad (41)
$$
which the reader will compare with (12). Hence, as in the previous subsection, $\tau$ is a ring morphism and the formula (13) holds again.

In order to generalize Lemmas 26 and 27, we introduce some convenient notation for coefficient extraction. For a series

$$g = \sum_{i,j} g_{i,j} s^i t^j \in M,$$

variables $v_1, \dots, v_\ell$ and exponents $e_1, \dots, e_\ell$, with $\{v_1, \dots, v_\ell\} \subset \{s, t\}$, we denote by

$$[v_1^{e_1} \cdots v_\ell^{e_\ell}]g$$

the sub-series of $g$ involving only the monomials $s^i t^j$ in which $v_1$ has exponent exactly $e_1$, $v_2$ has exponent exactly $e_2$, etc. Note that this is mere notation and that $[v_1^{e_1}]g$ need not be equal to $[v_1^{e_1} v_2^0]g$ although $v_1^{e_1} = v_1^{e_1} v_2^0$ in $M$. We do analogously with an operator $P \in (K[t] \langle D_t \rangle)[D_s]$ and a set of variables $\{v_1, \dots, v_\ell\} \subset \{D_s\}$, with the convention that coefficients are always written to the left of the monomials.

**Lemma 36.** Let $P \in (K[t] \langle D_t \rangle)[D_s]$ be a non-zero operator viewed with coefficients in $K[t] \langle D_t \rangle$. Consider any lexicographical order $>^>$ on the commutative monoid generated by $\{D_{s_1}, \dots, D_{s_{n-1}}\}$, e.g., the lexicographical order for which $D_{s_1} >^> D_{s_2} >^> \dots >^> D_{s_{n-1}}$. Let $D_{s_1}^{\alpha_1} \cdots D_{s_{n-1}}^{\alpha_{n-1}}$ be the minimal monomial in $P$ with respect to this order, so that

$$P = \tilde{P}(t; D_t) D_{s_1}^{\alpha_1} \cdots D_{s_{n-1}}^{\alpha_{n-1}} + \text{terms with higher monomials} \quad (42)$$

for some non-zero $\tilde{P} \in K[t] \langle D_t \rangle$. Additionally, let

$$g = \sum_{i,j} g_{i,j} s^i t^j$$

be any series in $M$. Then,

$$[s_1^{-(\alpha_1+1)} \cdots s_{n-1}^{-(\alpha_{n-1}+1)}]P(g) = (-1)^{|\alpha|} \alpha_1! \cdots \alpha_{n-1}! \tilde{P}([s_1^{-1} \cdots s_{n-1}^{-1}]g).$$

*Proof.* For the proof, we fix the lexicographical order $>^>$ to satisfy $D_{s_1} >^> D_{s_2} >^> \dots >^> D_{s_{n-1}}$. Any other lexicographical order would be dealt with by obvious modifications. We claim that, for any $i$, after writing

$$P = \bar{P}(t; D_t, D_{s_{i+1}}, \dots, D_{s_{n-1}}) D_{s_1}^{\alpha_1} \cdots D_{s_i}^{\alpha_i} + Q$$

for some non-zero $\bar{P} \in K[t] \langle D_t, D_{s_{i+1}}, \dots, D_{s_{n-1}} \rangle$ and some operator $Q$ whose monomials $D_s^\beta$ are all such that $(\beta_1, \dots, \beta_i)$ is lexicographically higher than $(\alpha_1, \dots, \alpha_i)$, we have

$$[s_1^{-(\alpha_1+1)} \cdots s_i^{-(\alpha_i+1)}]P(g) = (-1)^{\alpha_1+\cdots+\alpha_i} \alpha_1! \cdots \alpha_i! \bar{P}([s_1^{-1} \cdots s_i^{-1}]g). \quad (43)$$

The proof is by induction on $i \in \{0, \dots, n-1\}$. The base case $i=0$ corresponds to no coefficient extraction and $\bar{P}=P$, so that (43) is the tautology $P(g)=$
1 × $\bar{P}(g)$. Fix $i \ge 1$ and, in order to prove (43), assume the analog of (43) at $i-1$, that is,

$$ [s_1^{-(\alpha_1+1)} \cdots s_{i-1}^{-(\alpha_{i-1}+1)}]P(g) = (-1)^{\alpha_1+\cdots+\alpha_{i-1}} \alpha_1! \cdots \alpha_{i-1}! \hat{P}([s_1^{-1} \cdots s_{i-1}^{-1}]g), \quad (44) $$

for some non-zero

$$ \hat{P} = \sum_{j \ge \alpha_i} \hat{P}_j(t; D_t, D_{s_{i+1}}, \dots, D_{s_{n-1}}) D_{s_i}^j \in K[t] \langle D_t, D_{s_i}, \dots, D_{s_{n-1}} \rangle. $$

Consider a series $c \in M$ involving only $t, s_{i+1}, \dots, s_{n-1}$, as well as some integer $u \in \mathbb{Z}$, to compute

$$ [s_i^{-(\alpha_i+1)}] \hat{P}(cs_i^u) = \sum_{j \ge \alpha_i} \hat{P}_j(c) u(u-1) \cdots (u-j+1) [s_i^{-(\alpha_i+1)}] s_i^{u-j}. $$

The last term $[s_i^{-(\alpha_i+1)}]s_i^{u-j}$ makes the sum have at most one single non-zero contribution, for $j = u + \alpha_i + 1$, while it makes it zero if $u \le -2$. If not a priori zero, the sum reduces to $\hat{P}_{u+\alpha_i+1}(c) u(u-1) \cdots (-\alpha_i)$, hence it is zero if $u \ge 0$. The only possibly non-zero case is therefore for $u = -1$, making the sum equal to $(-1)^{\alpha_i} \alpha_i! \hat{P}_{\alpha_i}(c)$. By linearity, we obtain

$$ [s_i^{-(\alpha_i+1)}] \hat{P}([s_1^{-1} \cdots s_{i-1}^{-1}]g) = (-1)^{\alpha_i} \alpha_i! \hat{P}_{\alpha_i}([s_i^{-1}] [s_1^{-1} \cdots s_{i-1}^{-1}]g). \quad (45) $$

Applying $[s_i^{-(\alpha_i+1)}]$ to (44), combining with (45), and setting $\bar{P} = \hat{P}_{\alpha_i}$, we thus obtain (43). The case $i = n-1$ proves the lemma by providing $\tilde{P} = \bar{P}$. $\square$

Consider again a non-necessarily D-finite series $f$ as in (16). By the definition (1) of the complete diagonal $\Delta(f)$, and by the definition (41) of $\tau$ and $\sigma$, this complete diagonal $\Delta(f)$ is $[s_1^{-1} \cdots s_{n-1}^{-1}]\sigma(f)$. We will now derive the following analogue of Lemma 27.

**Lemma 37.** Let $f$ be as in (16). Fix any lexicographical order $>_{\sigma}$ on the commutative monoid generated by $\{D_{s_1}, \dots, D_{s_{n-1}}\}$. If $P(\sigma(f)) = 0$ for $P$ and $\tilde{P} \ne 0$ as in (42), then $\tilde{P}$ annihilates $\Delta(f)$.

*Proof.* Lemma 36 and the equality $[s_1^{-1} \cdots s_{n-1}^{-1}]\sigma(f) = \Delta(f)$ imply

$$ (-1)^{|\alpha|} \alpha_1! \cdots \alpha_{n-1}! \tilde{P}(\Delta(f)) = [s_1^{-(\alpha_1+1)} \cdots s_{n-1}^{-(\alpha_{n-1}+1)}] P(\sigma(f)) = 0. $$

Hence, $\tilde{P}(\Delta(f)) = 0$. $\square$

We will now construct an operator $P$. Henceforth, it will be convenient to write $w$ in place of $s_1 \cdots s_{n-1}$ and $D_i$ in place of $D_{x_i}$, for $i = 1, \dots, n$. Define

$$ G_m := \frac{K[\mathbf{s}, t]_{\le 2nm}}{w^{2m}} \sigma(\mathrm{span}_K \{\mathbf{D}_x^\alpha f \mid |\alpha| \le m\}). $$
For convenience, write $s_0 := 1, s_n := t$. By the chain rule, for all $g \in S$ and each $i = 1, 2, \dots, n-1$, we have

$$D_{s_i}(\sigma(g)) = -\frac{1}{s_i}\sigma(g) + \frac{1}{s_{i-1}}\sigma(D_i(g)) - \frac{s_{i+1}}{s_i^2}\sigma(D_{i+1}(g)), \quad (46)$$

and

$$D_t(\sigma(g)) = \frac{1}{s_{n-1}}\sigma(D_n(g)). \quad (47)$$

For all $|\alpha| \le m$, and all $p(s, t) \in K[s, t]_{\le 2nm}$, the chain rule implies that if $1 \le i \le n-1$, then

$$D_{s_i} \left( \frac{p(s, t)}{w^{2m}} \sigma(D_x^\alpha f) \right) = D_{s_i} \left( \frac{1}{w^{2m}} \right) p \sigma(D_x^\alpha f) + \frac{D_{s_i}(p)}{w^{2m}} \sigma(D_x^\alpha f) + \frac{p}{w^{2m}} D_{s_i}(\sigma(D_x^\alpha f)).$$

Rewriting the first two terms of the right-hand side over the denominator $w^{2(m+1)}$ shows that they are both in $G_{m+1}$. Similarly, making $g = D_x^\alpha f$ in (46) and rewriting over the denominator $w^{2(m+1)}$ shows that the third term is also in $G_{m+1}$. Therefore, $D_{s_i} G_m \subseteq G_{m+1}$. A similar proof, using (47), also shows $D_t G_m \subseteq G_{m+1}$. Since $1 \in G_0$, we get by induction that for all $i \in \mathbb{N}^{n-1}$ and $j \in \mathbb{N}$,

$$D_t^j D_s^i(\sigma(f)) \in G_{j+|i|}.$$

Also note that $G_m \subseteq G_{m'}$ if $m \le m'$. Now, if $k \le N'$, $j + |i| \le N$, then

$$t^k D_t^j D_s^i(\sigma(f)) \in \frac{K[s, t]_{\le 2nN+N'}}{w^{2N}} \sigma(\operatorname{span}_K \{D_x^\alpha f \mid |\alpha| \le N\}). \quad (48)$$

Using Definition 13 when $S = \{1, \dots, n\}$ fixes $B = \prod_{i=1}^n \{0, 1, \dots, r_i - 1\}$, the polynomial $C$, and $d_C = \sum_{j=1}^n d_j \le nd_f$. Then by Lemma 17, with $u = N, v = |\alpha|, t = 0$, we have

$$D_x^\alpha \in \frac{1}{C^N} \mathcal{H}_{Nd_C, 0} + \frac{1}{C^N} J.$$

Applying to $f$, then applying $\sigma$, yields:

$$\sigma(D_x^\alpha f) \in \frac{1}{\tau(C^N)} \sigma(\mathcal{H}_{Nd_C, 0}(f)) \subseteq \frac{K[s, t]_{\le nNd_C}}{w^{d_C N} \tau(C^N)} \bigoplus_{\beta \in B} K \sigma(D_x^\beta f). \quad (49)$$

Therefore, by (48) and (49), and for $D$ defined as in (40), we have

$$t^k D_t^j D_s^i \sigma(f) \in \frac{K[s, t]_{\le DN+N'}}{w^{(2+d_C)N} \tau(C^N)} \bigoplus_{\beta \in B} K \sigma(D_x^\beta f). \quad (50)$$

Denote $A_N(s, t) := w^{(2+d_C)N} \tau(C^N) \in K[s, t]$. For any given $N'$ and $N$, define

$$V_{N,N'} = A_N \cdot \operatorname{span}_K \{t^k D_t^j D_s^i \mid k \le N', j + |i| \le N\}$$
and

$$W_{N,N'} = \sum_{\beta \in B} K[s,t]_{\le DN+N'} \sigma(D_x^\beta f).$$

We have proved by (50) that there is a K-linear map $\phi$ from $V_{N,N'}$ to $W_{N,N'}$ defined by $\phi(P) := P(\sigma(f))$. Note that

$$\dim_K V_{N,N'} = (N' + 1) \binom{N+n}{n}, \quad \dim_K W_{N,N'} \le R \binom{DN + N' + n}{n}, \quad (51)$$

where $R := r_1 \cdots r_n = O(r_f^n)$. Fix $N$ and $N'$ as in (40) ($D$ has already been defined as there), so that $N' = DN$, $N > R \frac{1+2nD}{D} > 2n > n$, and

$$N^n N' = R(2ND + N)^n > R(2ND + n)^n = R(DN + N' + n)^n,$$

from which follows, with the help of (51),

$$\dim_K V_{N,N'} > N' \cdot \frac{N^n}{n!} \\ > R \cdot \frac{(DN + N' + n)^n}{n!} > R \binom{DN + N' + n}{n} \ge \dim_K W_{N,N'}.$$

We therefore obtain $\dim_K V_{N,N'} - \dim_K W_{N,N'} > 0$, so that $\phi$ is non-injective. Consider any non-zero kernel element $Z$, that is, any family of constants $c_{i,j,k} \in K$ indexed by $i, j, k$ with $|i| + j \le N$ and $k \le N'$, and such that $\phi(Z) = 0$ for

$$Z = \sum_{i+j \le N, k \le N'} c_{i,j,k} \cdot A_N t^k D_t^j D_s^i. \quad (52)$$

Then, the operator $P := A_N^{-1}Z = \sum c_{i,j,k} t^k D_t^j D_s^i$ satisfies $P(\sigma(f)) = 0$ as well. From (52) it follows that

$$\deg(P) \le N', \quad \mathrm{ord}(P) \le N. \quad (53)$$

Finally, $P$ can be written

$$P = \tilde{P}(t; D_t) D_{s_1}^{\alpha_1} \cdots D_{s_{n-1}}^{\alpha_{n-1}} + \text{higher terms}$$

with $\tilde{P}(t; D_t) \ne 0$, and the operator $\tilde{P}$ annihilates $\Delta(f)$ by Lemma 37 and satisfies the announced bounds (39) because of (53).

Finishing the proof of Theorem 35 only requires to validate the asymptotic estimates in (39). Set $S := \sum_{i=1}^n d_i$, which goes to infinity because $d_f \le S \le nd_f$. Fix $\varepsilon > 0$. From the value of $D$ in (40) follow, at least for $n \ge 1/(4\varepsilon)$,

$$D = nS \left(1 + \frac{2}{S}\right) \le nS \left(1 + \frac{2}{d_f}\right) = O(nS),$$

$$2D + 1 = 2nS \left(1 + \frac{2}{S} + \frac{1}{4nS}\right) \le 2nS \left(1 + \frac{2}{d_f} + \frac{1}{4nd_f}\right) \le 2nS \left(1 + \frac{2 + \varepsilon}{d_f}\right),$$
and then, at least for $n \ge 1/(4\epsilon)$ and $d_f \ge 2$,

$$ (2D+1)^n \le 2^n n^n S^n (1+\epsilon/2)^n \le (2+\epsilon)^n n^{2n} d_f^n, \\ \frac{(2D+1)^n}{D} \le \frac{(2+\epsilon)^n n^{2n} d_f^n}{n(2+S)} \le \frac{(2+\epsilon)^n n^{2n} d_f^n}{n(2+d_f)} \le (2+\epsilon)^n n^{2n-1} d_f^{n-1}. $$

Combining with (40) yields (39).

**Acknowledgement.** Shaoshi Chen and Pingchuan Ma were partially supported by the National Key R&D Programs of China (No. 2020YFA0712300 and No. 2023YFA1009401), the NSFC grants (No. 12271511 and No. 11688101), the CAS Funds of the Youth Innovation Promotion Association (No. Y2022001), and the Strategic Priority Research Program of the Chinese Academy of Sciences (No. XDB0510201). Frédéric Chyzak was supported in part by the French ANR grant De rerum natura (ANR-19-CE40-0018), by the French-Austrian ANR-FWF grant EAGLES (ANR-22-CE91-0007 & FWF-I-6130-N), and by the European Research Council under the European Union's Horizon Europe research and innovation programme, grant agreement 101040794 (10000 DIGITS). Part of Pingchuan Ma's work was done during a 6-month visit at Inria in 2023. Chaochao Zhu was partially supported by 2021 Research Start-up Fund for High-level Talents (Natural Sciences) (Project No. 00701092242). All authors were also supported by the International Partnership Program of Chinese Academy of Sciences (Grant No. 167GJHZ2023001FN).

## References

[1] Abdelaziz, Y., Koutschan, C., Maillard, J.M., 2020. On christol's conjecture. Journal of Physics A: Mathematical and Theoretical 53, 205201. doi:10.1088/1751-8121/ab82dc.

[2] Adamczewski, B., Bell, J.P., 2013. Diagonalization and rationalization of algebraic Laurent series. Ann. Sci. Éc. Norm. Supér. (4) 46, 963–1004. doi:10.24033/asens.2207.

[3] Bostan, A., Boukraa, S., Maillard, J.M., Weil, J.A., 2015. Diagonals of rational functions and selected differential Galois groups. J. Phys. A 48, 504001, 29. doi:10.1088/1751-8113/48/50/504001.

[4] Bostan, A., Chyzak, F., van Hoeij, M., Pech, L., 2011. Explicit formula for the generating series of diagonal 3D rook paths. Séminaire Lotharingien de Combinatoire 66, 1–27.

[5] Bostan, A., Dumont, L., Salvy, B., 2017. Algebraic diagonals and walks: Algorithms, bounds, complexity. Journal of Symbolic Computation 83, 68–92. doi:10.1016/j.jsc.2016.11.006. special issue on the conference ISSAC 2015: Symbolic computation and computer algebra.
[6] Christol, G., 1986–1987. Fonctions hypergéométriques bornées. Groupe de travail d'analyse ultramétrique 14, 1–16. URL: http://eudml.org/doc/91963.

[7] Christol, G., 2015. Diagonals of rational fractions. Eur. Math. Soc. Newsl. 37, 37–43.

[8] Coutinho, S.C., 1995. A primer of algebraic $D$-modules. volume 33 of *London Mathematical Society Student Texts*. Cambridge University Press, Cambridge. doi:10.1017/CB09780511623653.

[9] Deligne, P., 1984. Intégration sur un cycle évanescent. Inventiones Mathematicae 76, 129–144. URL: http://eudml.org/doc/143120.

[10] Furstenberg, H., 1967. Algebraic functions over finite fields. J. Algebra 7, 271–277.

[11] Gessel, I., 1981. Two theorems on rational power series. Utilitas Mathematica 19, 247–254.

[12] Kauers, M., 2014. Bounds for D-finite closure properties, in: ISSAC 2014—Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ACM, New York. pp. 288–295. URL: https://doi.org/10.1145/2608628.2608634, doi:10.1145/2608628.2608634.

[13] Lipshitz, L.M., 1988. The diagonal of a D-finite power series is D-finite. J. Algebra 113, 373–378. doi:10.1016/0021-8693(88)90166-4.

[14] Lipshitz, L.M., 1989. D-finite power series. J. Algebra 122, 353–373. doi:10.1016/0021-8693(89)90222-6.

[15] Melczer, S., 2021. An invitation to analytic combinatorics: from one to several variables. Texts and Monographs in Symbolic Computation, Springer. doi:10.1007/978-3-030-67080-1.

[16] Mishna, M., 2020. Analytic combinatorics: a multidimensional approach. Discrete Mathematics and its Applications, CRC Press, Boca Raton, FL.

[17] Pemantle, R., Wilson, M.C., 2008. Twenty combinatorial examples of asymptotics derived from multivariate generating functions. SIAM Rev. 50, 199–272. doi:10.1137/050643866.

[18] Pemantle, R., Wilson, M.C., Melczer, S., 2024. Analytic combinatorics in several variables. volume 212 of *Cambridge Studies in Advanced Mathematics*. Second ed., Cambridge University Press, Cambridge. doi:10.1017/9781108874144.

[19] Salvy, B., 2019. Linear differential equations as a data structure. Found. Comput. Math. 19, 1071–1112. doi:10.1007/s10208-018-09411-x.
[20] Stanley, R.P., 1980. Differentiably finite power series. European J. Combin. 1, 175-188. doi:10.1016/S0195-6698(80)80051-5.

[21] Stanley, R.P., 1999. Enumerative combinatorics. Vol. 2. volume 62 of *Cambridge Studies in Advanced Mathematics*. Cambridge University Press, Cambridge.

[22] Wu, X.L., Chen, S.S., 2013. A note on the diagonal theorem for bivariate rational formal power series. Acta Math. Sinica (Chinese Ser.) 56, 203-210.

[23] Zeilberger, D., 1982. Sister celine's technique and its generalization. Journal of Mathematical Analysis and its Applications 85, 114-145.

[24] Zeilberger, D., 1990. A holonomic systems approach to special functions identities. J. Comput. Appl. Math. 32, 321-368. doi:10.1016/0377-0427(90)90042-X.