# Systems of Discrete Differential Equations,
Constructive Algebraicity of the Solutions

Hadrien Notarantonio111Inria, Palaiseau (France).
<EMAIL_ADDRESS>Sergey Yurkevich222 University of Vienna
(Austria<EMAIL_ADDRESS>
###### Abstract

In this article, we study systems of $n\geq 1$, not necessarily linear,
discrete differential equations (DDEs) of order $k\geq 1$ with one catalytic
variable. We provide a constructive and elementary proof of algebraicity of
the solutions of such equations. This part of the present article can be seen
as a generalization of the pioneering work by Bousquet-Mélou and Jehanne
(2006) who settled down the case $n=1$. Moreover, we obtain effective bounds
for the algebraicity degrees of the solutions and provide an algorithm for
computing annihilating polynomials of the algebraic series. Finally, we carry
out a first analysis in the direction of effectivity for solving systems of
DDEs in view of practical applications.

##  1 Introduction

###  1.1 Context and motivation

The equations that lie in the interest of this work are so-called _discrete
differential equations with one catalytic variable_ of fixed-point type. They
take the form

$F(t,u)=f(u)+t\cdot
Q(F(t,u),\Delta_{a}F(t,u),\dots,\Delta_{a}^{k}F(t,u),t,u),$ (1)

where $k\in\mathbb{N}$ is called the _order_ of the DDE, $f$ and $Q$ are
polynomials, and (for some $a\in\mathbb{Q}$) $\Delta_{a}^{\ell}$ is the
$\ell$th iteration of the  _discrete derivative operator_
$\Delta_{a}:\mathbb{Q}[u][[t]]\rightarrow\mathbb{Q}[u][[t]]$ defined by

$\Delta_{a}F(t,u):=\frac{F(t,u)-F(t,a)}{u-a}.$

Discrete differential equations are ubiquitous in enumerative combinatorics
[25, 12, 13, 10, 5]. Indeed, enumerating discrete structures usually leads to
introducing the corresponding generating function, say $G(t)$. In some of such
cases, the combinatorial nature of the initial problem can be transformed
directly into an algebraic or analytic question on the equation satisfied by
$G(t)$. However for many practical counting problems, the initial
combinatorial structure is too coarse to be translated into any meaningful
equation. In these cases it is often helpful to try to solve a more refined
problem, introducing new structure into the initial question and consequently
a new variable $u$ in the generating function: one is then lead to study a DDE
satisfied by some bivariate series $F(t,u)\in\mathbb{Q}[u][[t]]$, even though
the interest only lies in the specialization, usually $G(t)=F(t,0)$ or
$G(t)=F(t,1)$. Although this idea is, of course, very classical and used since
decades [25, 12, 13], the name “catalytic” for such a variable $u$ was
introduced only relatively recently by Zeilberger [27] in the year 2000.

######  Example 1.

The so-called $2$-constellations are special bi-colored planar maps (see [10,
§$5.3$] for the definition). Let the sequence $(a_{n})_{n\geq 0}$ enumerate
the $2$-constellations with $n$ black faces; we wish to discover properties of
$G(t)=\sum_{n\geq 0}a_{n}t^{n}$ (e.g. a closed-form expression for $G(t)$ or
the numbers $a_{n}$, asymptotics of $(a_{n})_{n\geq 0}$, etc). This problem is
usually refined by considering the numbers $a_{n,d}$ enumerating
$2$-constellations with $n$ black faces and outer degree $2d$. With now more
constraints on the studied enumeration (black faces and outer-degree), it is
possible to show by a recursive analysis of the construction of a
$2$-constellation (see [10, Section $5.3$] for details) that the bivariate
generating function $F(t,u)\coloneqq\sum_{n,d\geq
0}{a_{n,d}u^{d}t^{n}}\in\mathbb{Q}[u][[t]]$ satisfies the DDE of order $1$

$\displaystyle F(t,u)=1+tuF(t,u)^{2}+tu\Delta_{1}F(t,u).$ (2)

Note that $G(t)=F(t,1)\in\mathbb{Q}[[t]]$ is the generating function we were
initially interested in. The classical way of studying the series $G(t)$ is by
considering Equation (2). For instance, by studying (2), it can be shown using
[14], [10, Section $2$] or [8, Proposition $2.4$] that $F(t,u)$ is an
algebraic function over $\mathbb{Q}(t,u)$ and consequently that $G(t)$ is
algebraic over $\mathbb{Q}(t)$. Explicitly,

$16t^{3}G(t)^{2}-(8t^{2}+12t-1)tG(t)+t(t^{2}+11t-1)=0.$

Knowing that
$R(t,z):=16t^{3}z^{2}-(8t^{2}+12t-1)tz+t(t^{2}+11t-1)\in\mathbb{Q}[t,z]$
annihilates $G(t)$, it is possible to show that for $n\geq 1$, one has the
closed-form expression

$a_{n}=3\frac{2^{n-1}}{(n+2)(n+1)}\binom{2n}{n}$

whose asymptotic behavior is $a_{n}\sim 3\cdot 8^{n}/\sqrt{4\pi n^{5}}$, by
Stirling’s formula.

The algebraicity of $F(t,u)$ over $\mathbb{Q}(t,u)$ in 1 is no coincidence. In
their pioneering work [10], Bousquet-Mélou and Jehanne proved (see [10,
Theorem $3$]) that the unique power series solution of a functional equation
of the form (1) is always an algebraic function.

In a variety of different contexts throughout combinatorics also appears their
natural extension _systems of DDEs_ of fixed-point type that are, systems of
the form

$\begin{cases}F_{1}=f_{1}(u)+t\cdot
Q_{1}(\nabla_{a}^{k}F_{1},\ldots,\nabla_{a}^{k}F_{n},t,u),\\\
\indent\vdots\hskip 56.9055pt\vdots\\\ F_{n}=f_{n}(u)+t\cdot
Q_{n}(\nabla_{a}^{k}F_{1},\ldots,\nabla_{a}^{k}F_{n},t,u),\end{cases}$ (3)

where for $i=1,\dots,n$ the polynomials
$f_{i}\in\mathbb{Q}[u],Q_{i}\in\mathbb{Q}[y_{1},\dots,y_{n(k+1)},t,u]$ are
given and we write
$\nabla_{a}^{k}F\coloneqq(F,\Delta_{a}F,\ldots,\Delta_{a}^{k}F)$ for
$\Delta_{a}$ as before, and the unknowns
$F_{i}=F_{i}(t,u)\in\mathbb{Q}[u][[t]]$. As previously, $k$ is called the
_order_ of (3). Such systems of functional equations appear, for instance, in
the enumeration of hard particles on planar maps [10, §5.4], inhomogeneous
lattice paths [15], certain orientations with $n$ edges [7, §5], or
parallelogram polyominoes [4, §7.1].

For any given functional equation or system of such, the results one typically
wishes to obtain are for instance: a closed-form expression for the number of
objects of a given size, a grasp on the asymptotic behavior, or a
classification of the nature of the generating function(s) (e.g. algebraic,
D-finite, etc.). It is often easier to obtain a closed-formula or an
asymptotic estimate by studying a _witness_ of the nature of the generating
function (e.g. an annihilating polynomial, a linear ODE, etc.), so a natural
aim is to _solve_ the system, i.e. to compute such a witness. These objectives
frequently yield arbitrarily difficult challenges at the intersection with
enumerative combinatorics, theoretical physics [11] and computational geometry
[16].

##### Main goals

We want to prove in an elementary way that the components of the unique
solution $(F_{1},\dots,F_{n})\in\mathbb{Q}[u][[t]]^{n}$ of (3) are always
algebraic power series over $\mathbb{Q}(t,u)$. Moreover in the setting $n>1$
in (3), we want to design, analyze and theoretically compare geometry-driven
algorithms that compute an annihilating polynomial of the specialized series
$F_{1}(t,a)$.

Before providing a state-of-the-art and stating our contributions, we
introduce a combinatorial example of systems of DDEs that we shall use
intensively for illustrating this paper.

######  Example 2.

The following system of DDEs for the generating function of certain planar
orientations was considered in [7, Eq.$(27)$]:

$\begin{cases}\textbf{(E${}_{\textbf{F}_{1}}$):}\;\;F_{1}(t,u)=1+t\cdot\big{(}u+2uF_{1}(t,u)^{2}+2uF_{2}(t,1)+u\frac{F_{1}(t,u)-uF_{1}(t,1)}{u-1}\big{)},\\\
\textbf{(E${}_{\textbf{F}_{2}}$):}\;\;F_{2}(t,u)=t\cdot\big{(}2uF_{1}(t,u)F_{2}(t,u)+uF_{1}(t,u)+uF_{2}(t,1)+u\frac{F_{2}(t,u)-uF_{2}(t,1)}{u-1}\big{)}.\end{cases}$
(4)

We show in section 2 that $F_{1}(t,1)=1+2t+10t^{2}+66t^{3}+\cdots$ is
algebraic over $\mathbb{Q}(t)$, and that its minimal polynomial
$64t^{3}z_{0}^{3}+(48t^{3}-72t^{2}+2t)z_{0}^{2}-(15t^{3}-9t^{2}-19t+1)z_{0}+t^{3}+27t^{2}-19t+1$
can be computed using tools coming from elimination theory.

###  1.2 Previous works

In the lines below, we present an overview of the main results regarding
algebraicity of solutions of systems of DDEs. We start with the study of a
single DDE for $k>1$ (the case $k=1$ is not of our interest since, as we shall
see later in this article, systems of DDEs of order $k\geq 1$ reduce to a
single functional equation that ”involves” at least $2$ univariate series).

In the seminal work [10], Bousquet-Mélou and Jehanne completely resolve
algebraicity of solutions of DDEs (1), equivalently the case $n=1$ in (3).
Moreover, Bousquet-Mélou and Jehanne provide systematic methods for computing
an annihilating polynomial of the specialized series $F(t,a)$. For proving
[10, Theorem $3$], the authors designed a “nonlinear kernel method” which
allows one to prove that the unique solution of (1) is always an algebraic
function over $\mathbb{Q}(t,u)$. Significantly in practice, this approach
yields an algorithm for finding an annihilating polynomial of the
specialization $F(t,a)$ and of the bivariate series $F(t,u)$. The idea of
their algebraicity proof is to reduce the resolution of the DDE to solving
some system of polynomial equations which has a solution whose coordinates
contains the involved specializations of $F$. Their proof involves a symbolic
deformation argument ensuring that the polynomial system which is constructed
contains enough independent equations. For efficiency considerations for the
resolution of a single DDE of the form (1), a recent algorithmic work [9] by
Bostan, Safey El Din and Notarantonio targeted the intensive use of effective
algebraic geometry in order to efficiently solve the underlying polynomial
systems.
Regarding systems of DDEs (i.e. the case $n>1$), the usual strategy (e.g. [10,
Section $11$]) is to reduce a given system to a single equation and to apply
the method from [10, Section $2$]. Nevertheless, since the reduced equation
may not be of the form (1) anymore, the ideas of [10, Section $2$] may not be
applicable. In the literature, there exist two methods to overcome these
theoretical issues. First, a deep theorem in commutative algebra by Popescu
[23], central in the so-called “nested Artin approximation” theory, guarantees
that equations of the form (5) always admit an algebraic solution (see also
[7, Theorem $16$] for a statement of this theorem). Note that the nested
condition is automatically satisfied in this case and that the uniqueness of
the solution is obvious. A drawback of using Popescu’s theorem, however, is
that its proof is a priori highly non-constructive and can only be applied as
a “black box”, whereas in practice one is often interested in the explicit
annihilating polynomials of the solutions. Secondly, the frequent case when
(5) is linear in the bivariate formal power series and their specializations
was effectively solved (i.e. their proof of algebraicity yields an algorithm)
in the more recent article [15] by Buchacher and Kauers by using a multi-
dimensional kernel method. However even if their proof yields an algorithm,
its efficiency was not discussed at all. Note that the now common multi-
dimensional kernel method appears as well in the article of the same year [1]
by Asinowski, Bacher, Banderier and Gittenberger.

Before the present work, however, there was no systematic approach for dealing
with systems of DDEs such as (4). It is in this context that the present paper
takes place.

###  1.3 Contributions

This paper is the full version of the extended abstract [22] that was
published in the proceedings of the conference _Formal Power Series and
Algebraic Combinatorics $2023$_.

The first contribution of this article is a generalization of the algebraicity
result [10, Theorem $3$] to systems of discrete differential equations of a
fixed-point type. Precisely, we prove the following theorem. Here and in the
following, we denote $\mathbb{K}$ a field of characteristic $0$.

######  Theorem 3.

Let $n,k\geq 1$ be integers and $f_{1},\ldots,f_{n}\in\mathbb{K}[u]$,
$Q_{1},\ldots,Q_{n}\in\mathbb{K}[y_{1},\ldots,y_{n(k+1)},t,u]$ be polynomials.
For $a\in\mathbb{K}$, set
$\nabla_{a}^{k}F:=(F,\Delta_{a}F,\ldots,\Delta_{a}^{k}F)$. Then the system of
equations

$\displaystyle\begin{cases}\textbf{{\text{(E}}}_{\textbf{{\text{F}}}_{\textbf{{\text{1}}}}}\textbf{{\text{):}}}\;\;\;F_{1}=f_{1}(u)+t\cdot
Q_{1}(\nabla_{a}^{k}F_{1},\ldots,\nabla_{a}^{k}F_{n},t,u),\\\
\quad\vdots\hskip 85.35826pt\vdots\\\
\textbf{{\text{(E}}}_{\textbf{{\text{F}}}_{\textbf{{\text{n}}}}}\textbf{{\text{):}}}\;\;\;F_{n}=f_{n}(u)+t\cdot
Q_{n}(\nabla_{a}^{k}F_{1},\ldots,\nabla_{a}^{k}F_{n},t,u)\end{cases}$ (5)

admits a unique vector of solutions
$(F_{1},\ldots,F_{n})\in\mathbb{K}[u][[t]]^{n}$, and all its components are
algebraic functions over $\mathbb{K}(t,u)$.

The key idea, analogous to the one in the proof of [10, Theorem $3$], for
proving this theorem is to define a deformation of (5) that ensures the
applicability of a multi-dimensional analog of the “nonlinear kernel method”.
Stated explicitly, we show in 6 that after deforming the equations as in (7),
the polynomial in $u$ defined by the determinant of the Jacobian matrix
associated to the equations in (5) (considered with respect to the $F_{i}$)
has exactly $nk$ solutions in an extension of the ring $\bigcup_{d\geq
1}\overline{\mathbb{K}}[[t^{1/d}]]$. After a process of “duplication of
variables”, we construct a zero-dimensional polynomial ideal, a non-trivial
element of which must be the desired annihilating polynomial. The most
technical step consists in proving the invertibility of a certain Jacobian
matrix (8 and 9) in order to justify the zero-dimensionality.

The second contribution is the analysis of the resulting algorithm for finding
annihilating polynomials of the power series $F_{i}(t,u)$ in 3. From our
constructive proof we deduce a theoretical upper bound on the algebraicity
degree of each $F_{i}$. Moreover using the radicality of the constructed
$0$-dimensional ideal, and when the field $\mathbb{K}$ is effective (e.g.
$\mathbb{K}=\mathbb{Q}$), we also bound the arithmetic complexity of our
algorithm, that is the number of operations $(+,-,\times,\div)$ performed in
$\mathbb{K}$. Denoting by $\textsf{totdeg}(P)$ the total degree of a
multivariate polynomial $P$, we obtain the following:

######  Theorem 4.

In the setting of 3, let $(F_{1},\ldots,F_{n})\in\mathbb{K}[u][[t]]^{n}$ be
the vector of solutions and
$\delta:=\max(\deg(f_{1}),\dots,\deg(f_{n}),\textsf{totdeg}(Q_{1}),\dots,\textsf{totdeg}(Q_{n}))$.
Then the algebraicity degree of each $F_{i}(t,u)$ over $\mathbb{K}(t,u)$ is
bounded by
${n^{2n^{2}k^{2}}(k+1)^{n^{2}k^{2}(n+2)+n}\delta^{n^{2}k^{2}(n+2)+n}}/{(nk)!^{nk}}$.
Moreover if $\mathbb{K}$ is effective, there exists an algorithm computing an
annihilating polynomial of any $F_{i}(t,a)$ in $O((nk\delta)^{40(n^{2}k+1)})$
arithmetic operations in $\mathbb{K}$.

Let us emphasize that despite the desperately looking exponent $40$ in 4, one
can still solve concrete examples from time to time as we shall see in section
2 and section 4.

The third contribution is the full algorithmic investigation of two natural
schemes for solving systems of DDEs. For each of them, we analyze the
conditions under which they might be applied, and the possible links between
their respective outputs. The first algorithm consists in the classical
duplication of variables argument, by following our proof of 3, and then
performing a brute force elimination of all irrelevant variables (11). The
second scheme consists in reducing the initial system of DDEs to a single
polynomial functional equation where the general method of [10, Section $2$]
and the recent algorithmic improvements made in [9, Section $5$] might apply.
In this direction, we identify in section 4.2 sufficient conditions under
which [10, Section $2$] and [9, Section $5$] can systematically be used. At
the end of section 4.2, we show that eq. 4 can not be solved by the state-of-
the-art based on reducing a system of DDEs to a single equation (and then in
applying any systematic method), while it can be solved by the systematic
method that we introduce in section 2.

##### Structure of the paper.

In section 2, we explain our method in the case of two equations of order one
under the assumption that no deformation is necessary. We summarize the method
in an algorithm and showcase it explicitly on 2. In section 3, we provide
proofs of 3 and 4 with more details than in the extended abstract [22]. In
section 4, we study and compare the output of two natural strategies for
solving systems of DDEs. Ultimately, we discuss some necessary future works in
section 5.

##### Notations.

Throughout this article, $\mathbb{K}$ denotes a field of characteristic $0$,
$\overline{\mathbb{K}}$ its algebraic closure, $\mathbb{K}[[t]]$ the ring of
formal power series in $t$ with coefficients in $\mathbb{K}$, and
$\overline{\mathbb{K}}[[t^{\frac{1}{\star}}]]$ the ring $\bigcup_{d\geq
1}\overline{\mathbb{K}}[[t^{\frac{1}{d}}]]$ of Puiseux series with rational
positive exponent in the variable $t$. Also for $n,k\geq 1$ and
$a\in\mathbb{K}$, we use the compact notation $A(u)$ for any given polynomial
expression of the form
$A(F_{1}(t,u),F_{1}(t,a),\ldots,\partial_{u}^{k-1}F_{1}(t,a),\ldots,F_{n}(t,u),F_{n}(t,a),\ldots,\partial_{u}^{k-1}F_{n}(t,a),t,u)$.
For an integer $N>1$, we denote by $\mathbb{K}[x_{1},\ldots,x_{N}]$ the ring
of polynomials in the variables $x_{1},\ldots,x_{N}$ with coefficients in
$\mathbb{K}$. For $P\in\mathbb{K}[x_{1},\ldots,x_{N}]$, we denote by
$\partial_{x_{i}}P$ the partial derivative of $P$ with respect to the variable
$x_{i}$ (for $i\in\\{1,\ldots,N\\}$) and by $V(P)$ its zero set in
$\overline{\mathbb{K}}^{N}$. For $\mathcal{I}$ an ideal of
$\mathbb{K}[x_{1},\ldots,x_{N}]$, we also denote by $V(\mathcal{I})$ the zero
set of $\mathcal{I}$ in $\overline{\mathbb{K}}^{N}$. Also, for $\mathcal{S}$ a
set of polynomials in $\mathbb{K}[x_{1},\ldots,x_{N}]$, we denote by
$V(\mathcal{S})$ the zero set of the ideal generated by $\mathcal{S}$ in
$\mathbb{K}[x_{1},\ldots,x_{N}]$. For $\mathbf{x},\mathbf{y}$ two sets of
variables, we denote
$\\{\mathbf{x}\\}\succ_{\operatorname{lex}}\\{\mathbf{y}\\}$ the monomial
order such that $\\{\mathbf{x}\\}$ (resp. $\\{\mathbf{y}\\}$) is the usual
degrevlex [18, Definition $5$, § $2$, Chapter $2$] order over $\mathbf{x}$
(resp. over $\mathbf{y}$), and such that any monomial in $\mathbf{y}$ is lower
than any monomial containing at least one variable in $\mathbf{x}$ (by default
$\\{\mathbf{x}\\}$ will always denote the usual degrevlex monomial order on
the variables $\mathbf{x}$). We use the soft-O notation $\tilde{O}(\cdot)$ for
hiding polylogarithmic factors in the argument.

##  2 General strategy and application to a first example

Before proving our main theorem in section 3, we introduce our general method
in the situation of two equations of order $1$. We illustrate each step with
the system (4) from 2.

Starting with (5) for $n=2$ and $k=1$, we first multiply
(E${}_{\textbf{F}_{1}}$) and (E${}_{\textbf{F}_{2}}$) by $(u-a)^{m_{1}}$ and
$(u-a)^{m_{2}}$ respectively (for $m_{1},m_{2}\in~{}\mathbb{N}$) in order to
obtain a system with polynomial coefficients in $u$. By a slight abuse of
notation, we shall still write (E${}_{\textbf{F}_{1}}$) and
(E${}_{\textbf{F}_{2}}$) for those equations. Note that this system induces
polynomials $E_{1},E_{2}$ in $\mathbb{K}(t)[x_{1},x_{2},z_{0},z_{1},u]$ whose
specializations to
$x_{1}=F_{1}(t,u),x_{2}=F_{2}(t,u),z_{0}=F_{1}(t,a),z_{1}=F_{2}(t,a)$, denoted
by $E_{1}(u),E_{2}(u)$, are zero.

######  Example 1 (cont.).

Multiplying (E${}_{\textbf{F}_{1}}$) and (E${}_{\textbf{F}_{2}}$) in 2 by
$u-1$ gives

$\begin{cases}E_{1}=(1-x_{1})\cdot(u-1)+t\cdot(2u^{2}x_{1}^{2}-u^{2}z_{0}+2u^{2}z_{1}-2ux_{1}^{2}+u^{2}+ux_{1}-2uz_{1}-u),\\\
E_{2}=x_{2}\cdot(1-u)+t\cdot(2u^{2}x_{1}x_{2}+u^{2}x_{1}-2ux_{1}x_{2}-ux_{1}+ux_{2}-uz_{1}).\end{cases}$

Note that applying the specializations
$x_{1}=F_{1}(t,u),x_{2}=F_{2}(t,u),z_{0}=F_{1}(t,1),z_{1}=F_{2}(t,1)$ to
$E_{1}$ and $E_{2}$ yields the vanishing of the induced polynomial functional
equations.

In the spirit of [10], we take the derivative of both equations with respect
to the variable $u$:

$\begin{pmatrix}(\partial_{x_{1}}E_{1})(u)&(\partial_{x_{2}}E_{1})(u)\\\
(\partial_{x_{1}}E_{2})(u)&(\partial_{x_{2}}E_{2})(u)\end{pmatrix}\cdot\begin{pmatrix}\partial_{u}F_{1}\\\
\partial_{u}F_{2}\end{pmatrix}+\begin{pmatrix}(\partial_{u}E_{1})(u)\\\
(\partial_{u}E_{2})(u)\end{pmatrix}=0,$ (6)

Define
$\operatorname{\mathsf{Det}}:=\partial_{x_{1}}E_{1}\cdot\partial_{x_{2}}E_{2}-\partial_{x_{1}}E_{2}\cdot\partial_{x_{2}}E_{1}\in\mathbb{K}(t)[x_{1},x_{2},z_{0},z_{1},u]$.
One can show that the specialization
$\operatorname{\mathsf{Det}}(F_{1}(t,u),F_{2}(t,u),F_{1}(t,a),F_{2}(t,a),t,u)\in\mathbb{K}[[t]][[u]]$
admits either $0,1$ or $2$ distinct non-constant solutions in $u$ in
$\overline{\mathbb{K}}[[t^{\frac{1}{\star}}]]$. We assume that there exist $2$
such solutions $U_{1},U_{2}\in\overline{\mathbb{K}}[[t^{\frac{1}{\star}}]]$;
we prove in section 3 that it is always the case up to the deformation (7).

Exploiting the common idea to [1, Proof of Theorem $3.2$] and [15, Section
$3$], we define the vector
$v:=(\partial_{x_{1}}E_{2},\;\;-\partial_{x_{1}}E_{1})\in\mathbb{K}(t)[x_{1},x_{2},z_{0},z_{1},u]^{2}$
and plug $U_{1}$ for $u$ into $v$ and (6). Note that $v$ is an element of the
left-kernel of the square matrix in (6) $\bmod$
$\operatorname{\mathsf{Det}}(x_{1},x_{2},z_{0},z_{1},u)$. After multiplication
of (6) by $v$ on the left, we find a new polynomial relation relating the
series $F_{1}(t,U_{i}),F_{2}(t,U_{i}),F_{1}(t,a),F_{2}(t,a),t$ and $U_{i}$,
namely
$\partial_{x_{1}}E_{1}\cdot\partial_{u}E_{2}-\partial_{x_{1}}E_{2}\cdot\partial_{u}E_{1}=0$
when evaluated at
$x_{1}=F_{1}(t,U_{i}),x_{2}=F_{2}(t,U_{i}),z_{0}=F_{1}(t,a),z_{1}=F_{2}(t,a),u=U_{i}$.
We denote
$P:=\partial_{x_{1}}E_{1}\cdot\partial_{u}E_{2}-\partial_{x_{1}}E_{2}\cdot\partial_{u}E_{1}\in\mathbb{K}(t)[x_{1},x_{2},z_{0},z_{1},u]$
this new polynomial.

######  Remark 5.

Note that $P$ is the determinant of the matrix
$\begin{pmatrix}\partial_{x_{1}}E_{1}&\partial_{x_{1}}E_{2}\\\
\partial_{u}E_{1}&\partial_{u}E_{2}\end{pmatrix}$, which is not a coincidence,
as we will see in the next section.

We define the polynomial system
$\mathcal{S}:=(E_{1},E_{2},\operatorname{\mathsf{Det}},P)\in\mathbb{K}(t)[x_{1},x_{2},z_{0},z_{1},u]^{4}$.
It admits the relevant solutions
$(F_{1}(t,U_{i}),F_{2}(t,U_{i}),F_{1}(t,a),F_{2}(t,a),U_{i})\in\overline{\mathbb{K}}[[t^{\frac{1}{\star}}]]^{5}$,
for $i\in\\{1,2\\}$.

######  Example 1 (cont.).

Continuing 2, we find

$\begin{cases}\operatorname{\mathsf{Det}}=(4tu^{2}x_{1}-4tux_{1}+tu-u+1)(2tu^{2}x_{1}-2tux_{1}+tu-u+1),\\\
P=-2tx_{1}x_{2}-tx_{1}+tx_{2}-tz_{1}-x_{2}+P_{1}\cdot u+P_{2}\cdot
u^{2}+P_{3}\cdot u^{3},\end{cases}$

where $P_{1},P_{2},P_{3}$ are explicit (but relatively big) polynomials in
$\mathbb{Q}[x_{1},x_{2},z_{0},z_{1},t]$.

Applying in spirit the steps of [10, Section $2$], we define for
$i\in\\{0,1\\}$ the polynomial systems
$\mathcal{S}_{i}:=\mathcal{S}(x_{2i+1},\;x_{2i+2},\;z_{0},\;z_{1},\;u_{i+1})$
by “duplicating” variables. In the case where the ideal
$\mathcal{S}_{\textsf{dup}}:=\langle\mathcal{S}_{0},\mathcal{S}_{1},m\cdot(u_{1}-u_{2})-1\rangle$
has dimension $0$ over $\mathbb{K}(t)$, finding an annihilating polynomial of
$F_{1}(t,a)$ is done by computing a nonzero element of
$\langle\mathcal{S}_{0},\mathcal{S}_{1},m\cdot(u_{1}-u_{2})-1\rangle\cap\mathbb{K}[z_{0},t]$.

######  Example 1 (cont.).

Continuing Example 2, we compute333All computations in this paper have been
performed in Maple using the C library msolve [6]. a generator of the
polynomial ideal
$\langle\mathcal{S}_{0},\mathcal{S}_{1},m\cdot(u_{1}-u_{2})-1\rangle\cap\mathbb{Q}[z_{0},t]$.
It has degree $13$ in $z_{0}$ and $14$ in $t$. In particular, it contains in
its factors the minimal polynomial of $F_{1}(t,1)$ given by
$64t^{3}z_{0}^{3}+(48t^{3}-72t^{2}+2t)z_{0}^{2}-(15t^{3}-9t^{2}-19t+1)z_{0}+t^{3}+27t^{2}-19t+1$.

We summarize the algorithm described above in the compact form given by
Algorithm 1.

Input: A system of two DDEs (E${}_{\textbf{F}_{1}}$), (E${}_{\textbf{F}_{2}}$)
of order $1$, with $\mathcal{S}_{\textsf{dup}}$ of dimension $0$ over
$\mathbb{K}(t)$.

Output: A nonzero $R\in\mathbb{K}[z_{0},t]$ annihilating $F_{1}(t,a)$.

1 Replace (E${}_{\textbf{F}_{1}}$) and (E${}_{\textbf{F}_{2}}$) by their
respective numerators and denote by $E_{1}$ and $E_{2}$ the associated
polynomials in $\mathbb{K}(t)[x_{1},x_{2},z_{0},z_{1},u]$.

2 Compute
$\operatorname{\mathsf{Det}}:=\partial_{x_{1}}E_{1}\cdot\partial_{x_{2}}E_{2}-\partial_{x_{1}}E_{2}\cdot\partial_{x_{2}}E_{1}$
and
$P:=\partial_{x_{1}}E_{1}\cdot\partial_{u}E_{2}-\partial_{x_{1}}E_{2}\cdot\partial_{u}E_{1}$.

3 Set
$\mathcal{S}:=(E_{1},E_{2},\operatorname{\mathsf{Det}},P)\subset\mathbb{K}(t)[x_{1},x_{2},z_{0},z_{1},u]$.

4 For $0\leq i\leq 1$, define
$\mathcal{S}_{i}:=\mathcal{S}(x_{2i+1},\;x_{2i+2},\;z_{0},\;z_{1},\;u_{i+1})$.

5 Define
$\operatorname{\mathcal{S}_{\mathsf{dup}}}:=\langle\mathcal{S}_{0},\mathcal{S}_{1},m\cdot(u_{1}-u_{2})-1\rangle\subset\mathbb{K}(t)[m,x_{1},x_{2},x_{3},x_{4},z_{0},z_{1},u_{1},u_{2}]$,

Return a nonzero element of
$\operatorname{\mathcal{S}_{\mathsf{dup}}}\cap\;\mathbb{K}[z_{0},t]$.

Algorithm 1 Solving systems of two discrete differential equations of order
$1$.

We remark that if the same strategy as above is applied in the case of a
single equation of first order of the form $F_{1}=f(u)+t\cdot
Q_{1}(F_{1},\Delta_{a}F_{1},t,u)$, the presented method simplifies to the
classical method in [10] of Bousquet-Mélou and Jehanne which relies on
studying the ideal $\langle
E_{1},\partial_{x_{1}}E_{1},\partial_{u}E_{1}\rangle$. Stated explicitly,
$\partial_{x_{1}}E_{1}$ plays the role of $\operatorname{\mathsf{Det}}$ and
$\partial_{u}E_{1}$ plays the role of $P$.

##  3 Proofs of 3 and 4

###  3.1 Proof of 3

As explained before, the statement and proof can be seen as a generalization
of [10, Theorem 3] and [15, Theorem 2], so several steps are done analogously.
Without loss of generality we assume that $a=0$ and set $\Delta:=\Delta_{0}$
and $\nabla:=\nabla_{0}$.

Denote by $m_{1},\ldots,m_{n}$ the least positive integers greater than or
equal to $k$ such that multiplying ($\textbf{E}_{\textbf{F}_{\textit{{i}}}}$)
in (5) by $u^{m_{i}}$ gives a polynomial equation; in other words, the
multiplication by $u^{m_{i}}$ clears the denominators introduced by the
application of $\Delta$. Set $\beta:=\lfloor 2M/k\rfloor$ and
$\alpha:=3n^{2}k\cdot(\beta+1)+3nM$, where $M:=m_{1}+\cdots+m_{n}$. Let
$\epsilon$ be a new variable, $\mathbb{L}:=\mathbb{K}(\epsilon)$, and let
$(\gamma_{i,j})_{1\leq i,j\leq n}$ be defined by $\gamma_{i,i}=i^{k}$ and
$\gamma_{i,j}=t^{\beta}$ for $i\neq j$. Then, consider the following system
which is a symbolic deformation of (5) with respect to the deformation
parameter $\epsilon$:

$\small\begin{cases}\textbf{{\text{(E}}}_{\textbf{{\text{G}}}_{\textbf{{\text{1}}}}}\textbf{{\text{):}}}\;\;\;G_{1}=f_{1}(u)+t^{\alpha}\cdot
Q_{1}(\nabla^{k}G_{1},\nabla^{k}G_{2},\ldots,\nabla^{k}G_{n},t^{\alpha},u)+t\cdot\epsilon^{k}\cdot\sum_{i=1}^{n}\gamma_{1,i}\cdot\Delta^{k}G_{i},\\\
\qquad\qquad\;\;\;\;\vdots\hfill\vdots\;\;\;\;\;\;\;\;\;\;\\\
\textbf{{\text{(E}}}_{\textbf{{\text{G}}}_{\textbf{{\text{{n}}}}}}\textbf{{\text{):}}}\;\;\;G_{n}=f_{n}(u)+t^{\alpha}\cdot
Q_{n}(\nabla^{k}G_{1},\nabla^{k}G_{2},\ldots,\nabla^{k}G_{n},t^{\alpha},u)+t\cdot\epsilon^{k}\cdot\sum_{i=1}^{n}\gamma_{n,i}\cdot\Delta^{k}G_{i}.\end{cases}$
(7)

The fixed point nature of the above equations still implies the existence of a
unique solution $(G_{1},\ldots,G_{n})\in\mathbb{L}[u][[t]]^{n}$ (it can be
seen by extracting the coefficient of $t^{m}$ of each $G_{1},\ldots,G_{n}$).
Remark that the equalities $F_{i}(t^{\alpha},u)=G_{i}(t,u,0)$ relate the
formal power series solutions of (5) and of (7). Hence, showing that each
$G_{i}$ is algebraic over $\mathbb{L}(t,u)$ is enough to prove 3. Moreover, as
we will see later, the algebraicity of each $G_{i}$ follows from the
algebraicity of the series
$G_{1}(0),\ldots,\partial_{u}^{k-1}G_{1}(0),\ldots,G_{n}(0),\ldots,\partial_{u}^{k-1}G_{n}(0)$.
Here, and in what follows, we shall use the short notations

$G_{i}(u)\equiv G_{i}(t,u,\epsilon),\partial_{0}G_{i}(u)\equiv
G_{i}(u),G_{i}(0),\partial_{u}G_{i}(0),\ldots,\partial_{u}^{k-1}G_{i}(0)$

and $A(u)\equiv A(\partial_{0}G_{1},\ldots,\partial_{0}G_{n},t,u)$ for any
polynomial $A\in\mathbb{L}[X_{1},\ldots,X_{n},t,u]$ with the notation
$X_{j}:=x_{j},z_{k(j-1)},z_{k(j-1)+1},\ldots,z_{kj-1}$. Note that in the case
$n=1$, this notation implies that for any $0\leq i\leq k-1$, the variable
$z_{i}$ stands for $\partial_{u}^{i}F_{1}(t,a)$.

Let us define $Y_{i,0}:=x_{i}$ and
$Y_{i,j}:=({x_{i}-z_{k(i-1)}-\cdots-\frac{u^{j-1}}{(j-1)!}z_{k(i-1)+j-1})/u^{j}}$
for $1\leq i\leq n$ and $1\leq j\leq k$. With these definitions, multiplying
each ($\textbf{E}_{\textbf{F}_{\textit{{i}}}}$) in (5) by $u^{m_{i}}$ and
substituting the series $G_{i}$’s and their specializations by their
associated variables yields the following system of polynomial equations

$\footnotesize\begin{cases}E_{1}:=u^{m_{1}}\cdot(f_{1}(u)-x_{1}+t^{\alpha}\cdot
Q_{1}(Y_{1,0},\ldots,Y_{1,k},Y_{2,0},\ldots,Y_{n,k},t^{\alpha},u)+t\cdot\epsilon^{k}\cdot\sum_{i=1}^{n}\gamma_{1,i}\cdot
Y_{i,k})=0,\\\ \indent\;\vdots\hfill\vdots\;\;\;\;\\\
E_{n}:=u^{m_{n}}\cdot(f_{n}(u)-x_{n}+t^{\alpha}\cdot
Q_{n}(Y_{1,0},\ldots,Y_{1,k},Y_{2,0},\ldots,Y_{n,k},t^{\alpha},u)+t\cdot\epsilon^{k}\cdot\sum_{i=1}^{n}\gamma_{n,i}\cdot
Y_{i,k})=0.\end{cases}$ (8)

Like in (6), we take the derivative with respect to the variable $u$ of these
equations and find

$\begin{pmatrix}(\partial_{x_{1}}E_{1})(u)&\dots&(\partial_{x_{n}}E_{1})(u)\\\
\vdots&\ddots&\vdots\\\
(\partial_{x_{1}}E_{n})(u)&\dots&(\partial_{x_{n}}E_{n})(u)\end{pmatrix}\cdot\begin{pmatrix}\partial_{u}G_{1}\\\
\vdots\\\
\partial_{u}G_{n}\end{pmatrix}+\begin{pmatrix}(\partial_{u}E_{1})(u)\\\
\vdots\\\ (\partial_{u}E_{n})(u)\end{pmatrix}=0.$ (9)

Let $\operatorname{\mathsf{Det}}\in\mathbb{L}[X_{1},\dots,X_{n},t][u]$ be the
determinant of the square matrix $(\partial_{x_{j}}E_{i})_{1\leq i,j\leq n}$.
The following lemma gives the number of distinct relevant solutions in $u$ to
the equation $\operatorname{\mathsf{Det}}(u)=0$.

######  Lemma 6.

$\operatorname{\mathsf{Det}}(u)=0$ admits exactly $nk$ distinct nonzero
solutions
$U_{1},\ldots,U_{nk}\in\overline{\mathbb{L}}[[t^{\frac{1}{\star}}]]$.

###### Proof.

Note that we have

$\operatorname{\mathsf{Det}}(u)=\det\begin{pmatrix}-u^{m_{1}}+t\epsilon^{k}\gamma_{1,1}u^{m_{1}-k}&\cdots&t\epsilon^{k}\gamma_{1,n}u^{m_{1}-k}\\\
\vdots&\ddots&\vdots\\\
t\epsilon^{k}\gamma_{n,1}u^{m_{n}-k}&\cdots&-u^{m_{n}}+t\epsilon^{k}\gamma_{n,n}u^{m_{n}-k}\end{pmatrix}+O(t^{\alpha}u^{M-nk}).$

For every $i$ we first divide the $i$th row by $u^{m_{i}-k}$. Then, using the
definition of $\gamma_{i,j}$ and $\alpha,\beta\geq n$, we see that the matrix
above becomes diagonal mod $t^{n+1}$ and its determinant mod $t^{n+1}$
simplifies to $u^{M-nk}\cdot\prod_{j=1}^{n}(-u^{k}+t\epsilon^{k}j^{k})\bmod
t^{n+1}$. Hence, computing the first terms of a solution in $u$ by using
Newton polygons, we find $nk$ distinct nonzero solutions in $u$ to the
equation $\operatorname{\mathsf{Det}}(u)=0$. We denote these solutions by
$U_{1},\ldots,U_{nk}\in\overline{\mathbb{L}}[[t^{\frac{1}{\star}}]]$. Their
first terms are given by $\zeta^{\ell}\cdot
t^{\frac{1}{k}}\cdot\epsilon,\ldots,\zeta^{\ell}\cdot n\cdot
t^{\frac{1}{k}}\cdot\epsilon\in\overline{\mathbb{L}}[[t^{\frac{1}{\star}}]]$,
for $\zeta$ a $k$-primitive root of unity and for all $1\leq\ell\leq k$.
Finally, note that the constant coefficient in $t$ of
$\prod_{j=1}^{n}(-u^{k}+t\epsilon^{k}j^{k})$ has degree $nk$ so by [10,
Theorem 2] there cannot be more than $nk$ solutions to
$\operatorname{\mathsf{Det}}(u)=0$ in
$\overline{\mathbb{L}}[[t^{\frac{1}{\star}}]]\setminus\\{0\\}$. ∎

Now, let $P$ be the determinant of the square matrix
$(\partial_{x_{j}}E_{i})_{1\leq i,j\leq n}$ where the last column
$(\partial_{x_{n}}E_{1},\dots,\partial_{x_{n}}E_{n})$ is replaced by
$(\partial_{u}E_{1},\dots,\partial_{u}E_{n})$, that is

$P:=\det\begin{pmatrix}\partial_{x_{1}}E_{1}&\dots&\partial_{x_{n-1}}E_{1}&\partial_{u}E_{1}\\\
\vdots&\ddots&\vdots&\vdots\\\
\partial_{x_{1}}E_{n}&\dots&\partial_{x_{n-1}}E_{n}&\partial_{u}E_{n}\\\
\end{pmatrix}.$

1Clearly, if $\operatorname{\mathsf{Det}}(u)=0$ then (9) implies $P(u)=0$,
thus $P(u)$ vanishes at the roots $U_{1},\dots,U_{nk}$ in 6. Hence, defining
the polynomial system $\mathcal{S}$ in $\mathbb{L}[t][X_{1},\ldots,X_{n},u]$
given by the vanishing of the set of polynomials
$(E_{1},\ldots,E_{n},\operatorname{\mathsf{Det}},P)$, we see that
$\mathcal{S}$ is a system with exactly $n+2$ equations in the $nk+n+1$
variables given by $z_{0},\ldots,z_{nk-1},x_{1},\ldots,x_{n},u$ (here $t$ and
$\epsilon$ are parameters). We introduce the _duplicated system_
$\mathcal{S}_{\textsf{dup}}^{\epsilon}:=(\mathcal{S}_{1},\ldots,\mathcal{S}_{nk})$
in
$\mathbb{L}(t)[x_{1},\ldots,x_{n^{2}k},z_{0},\dots,z_{nk-1},u_{1},\ldots,u_{nk}]$
after duplicating $nk$ times each of the variables $x_{i}$’s, $u_{i}$’s and
after duplicating $nk$ times the initial polynomial system $\mathcal{S}$: all
in all, we perform in spirit step $4$ of Algorithm 1. This system is built
from $nk(n+2)$ equations and $nk(n+2)$ variables.

The following lemma is proven in [8, Lemma 2.10] as a consequence of Hilbert’s
Nullstellensatz and of the Jacobian criterion [19, Theorem 16.19]. Recall that
for an integer $N>1$ and for some polynomial
$g\in\mathbb{K}[x_{1},\ldots,x_{N}]$ and an ideal
$\mathcal{I}\subset\mathbb{K}[x_{1},\ldots,x_{N}]$, the saturation of
$\mathcal{I}$ by $g$ (also called saturated ideal) is defined by
$\mathcal{I}:g^{\infty}:=\\{f\in\mathbb{K}[x_{1},\ldots,x_{N}]|\exists
s\in\mathbb{N}\text{ s.t. }g^{s}\cdot f\in\mathcal{I}\\}$444In practice, if
$\\{h_{1},\ldots,h_{r}\\}$ is a generating set of $\mathcal{I}$, then a
generating set of $\mathcal{I}:g^{\infty}$ is obtained by computing a
generating set of $\langle h_{1},\ldots,h_{r},m\cdot
g-1\rangle\cap\mathbb{K}[x_{1},\ldots,x_{N}]$, where $m$ is an extra
variable..

######  Lemma 7.

Assume that the Jacobian matrix
$\operatorname{\mathsf{Jac}}_{\mathcal{S}_{\textsf{dup}}^{\epsilon}}$ of
$\mathcal{S}_{\textsf{dup}}^{\epsilon}$, considered with respect to the
variables
$x_{1},\ldots,x_{n},u_{1},\ldots,x_{n^{2}k-n+1},\ldots,x_{n^{2}k},u_{nk},z_{0},\ldots,z_{nk-1}$,
is invertible at the point

$\displaystyle\mathcal{P}=(G_{1}$
$\displaystyle(U_{1}),\ldots,G_{n}(U_{1}),U_{1},\ldots,G_{1}(U_{nk}),\ldots,G_{n}(U_{nk}),U_{nk},{G}_{1}(0),\ldots,\partial_{u}^{k-1}{G}_{1}(0),\ldots,$
$\displaystyle{G}_{n}(0),\ldots,\partial_{u}^{k-1}{G}_{n}(0))\in\overline{\mathbb{L}}[[t^{\frac{1}{\star}}]]^{nk(n+1)}\times\mathbb{L}[[t]]^{nk}.$

Denote $\mathcal{I}_{\textsf{dup}}^{\epsilon}$ the ideal of
$\mathbb{L}(t)[x_{1},\ldots,x_{n},u_{1},\ldots,x_{n^{2}k-n+1},\ldots,x_{n^{2}k},u_{nk},z_{0},\ldots,z_{nk-1}]$
generated by $\mathcal{S}_{\textsf{dup}}^{\epsilon}$. Then the saturated ideal
$\mathcal{I}_{\textsf{dup}}^{\epsilon}:\det(\operatorname{\mathsf{Jac}}_{\mathcal{S}_{\textsf{dup}}^{\epsilon}})^{\infty}$
is zero-dimensional and radical over $\mathbb{L}(t)$. Moreover, $\mathcal{P}$
lies in the zero set of
$\mathcal{I}_{\textsf{dup}}^{\epsilon}:\det(\operatorname{\mathsf{Jac}}_{\mathcal{S}_{\textsf{dup}}^{\epsilon}})^{\infty}$.

Therefore, in order to conclude the algebraicity of
$G_{i}(0),\ldots,\partial_{u}^{k-1}G_{i}(0)$ over $\mathbb{L}(t)$ for all
$1\leq i\leq n$, it is enough to justify that
$\operatorname{\mathsf{Jac}}_{\mathcal{S}_{\textsf{dup}}^{\epsilon}}$ is
invertible at $\mathcal{P}$. The idea for proving
$\det(\operatorname{\mathsf{Jac}}_{\mathcal{S}_{\textsf{dup}}^{\epsilon}})(\mathcal{P})\neq
0$, analogous to the proof of [10, Theorem $3$], is to show first that
$\operatorname{\mathsf{Jac}}_{\mathcal{S}_{\textsf{dup}}^{\epsilon}}(\mathcal{P})$
can be rewritten as a block triangular matrix. We will then show that the
diagonal blocks are invertible by carefully analyzing the lowest valuation in
$t$ of their associated determinants.

If $A\in\mathbb{L}[t][X_{1},\ldots,X_{n},u]$, we shall define its “$i$th
duplicated polynomial” by

$A^{(i)}:=A(X_{n(i-1)+1},\ldots,X_{ni},u_{i}).$

Then the Jacobian matrix
$\operatorname{\mathsf{Jac}}_{\mathcal{S}_{\textsf{dup}}^{\epsilon}}(\mathcal{P})$
has the shape

$\displaystyle\operatorname{\mathsf{Jac}}_{\operatorname{\mathcal{S}_{\mathsf{dup}}}}(\mathcal{P})=\begin{pmatrix}A_{1}&&0&B_{1}\\\
&\ddots&&\vdots\\\ 0&&A_{nk}&B_{nk}\\\
\end{pmatrix}\in\overline{\mathbb{L}}[[t^{\frac{1}{\star}}]]^{nk(n+2)\times
nk(n+2)},$

where for $i=1,\dots,nk$ the matrices555In these matrices, we emphasize that
notations like $\partial_{x_{1}}E_{1}^{(i)}(U_{i})$ are compact forms for the
specializations of the duplicated polynomial $\partial_{x_{1}}E_{1}^{(i)}$ to
the values
$x_{(i-1)n+1}=F_{1}(t,U_{i}(t)),\ldots,x_{in}=F_{n}(t,U_{i}(t)),u_{i}=U_{i}(t),z_{(j-1)k+\ell}=(\partial_{u}^{\ell}F_{j})(t,a)$.
$A_{i}\in\overline{\mathbb{L}}[[t^{\frac{1}{\star}}]]^{(n+2)\times(n+1)}$ and
$B_{i}\in\overline{\mathbb{L}}[[t^{\frac{1}{\star}}]]^{(n+2)\times nk}$ are:

$A_{i}:=\begin{pmatrix}\partial_{x_{1}}E_{1}^{(i)}(U_{i})&\dots&\partial_{x_{n}}E_{1}^{(i)}(U_{i})&\partial_{u_{i}}E_{1}^{(i)}(U_{i})\\\
\vdots&\ddots&\vdots&\vdots\\\
\partial_{x_{1}}E_{n}^{(i)}(U_{i})&\dots&\partial_{x_{n}}E_{n}^{(i)}(U_{i})&\partial_{u_{i}}E_{n}^{(i)}(U_{i})\\\
\partial_{x_{1}}\operatorname{\mathsf{Det}}^{(i)}(U_{i})&\dots&\partial_{x_{n}}\operatorname{\mathsf{Det}}^{(i)}(U_{i})&\partial_{u_{i}}\operatorname{\mathsf{Det}}^{(i)}(U_{i})\\\
\partial_{x_{1}}P^{(i)}(U_{i})&\dots&\partial_{x_{n}}P^{(i)}(U_{i})&\partial_{u_{i}}P^{(i)}(U_{i})\end{pmatrix},$
$B_{i}:=\begin{pmatrix}\partial_{z_{0}}E_{1}^{(i)}(U_{i})&\dots&\partial_{z_{nk-1}}E_{1}^{(i)}(U_{i})\\\
\vdots&\ddots&\vdots\\\
\partial_{z_{0}}E_{n}^{(i)}(U_{i})&\dots&\partial_{z_{nk-1}}E_{n}^{(i)}(U_{i})\\\
\partial_{z_{0}}\operatorname{\mathsf{Det}}^{(i)}(U_{i})&\dots&\partial_{z_{nk-1}}\operatorname{\mathsf{Det}}^{(i)}(U_{i})\\\
\partial_{z_{0}}P^{(i)}(U_{i})&\dots&\partial_{z_{nk-1}}P^{(i)}(U_{i})\end{pmatrix}.$

Using $\operatorname{\mathsf{Det}}(U_{i})=0$ and (9), we see that the first
$n\times(n+1)$ minor of each $A_{i}$ has rank at most $n-1$. Hence, after
performing operations on the first $n$ rows, we can transform the $n$ th row
of $A_{i}$ into the zero vector. It follows that after the suitable
transformation and a permutation of rows,
$\operatorname{\mathsf{Jac}}_{\mathcal{S}_{\textsf{dup}}^{\epsilon}}(\mathcal{P})$
can be rewritten as a block triangular matrix. To give the precise form of the
determinant of
$\operatorname{\mathsf{Jac}}_{\mathcal{S}_{\textsf{dup}}^{\epsilon}}(\mathcal{P})$,
we first define

$\footnotesize
R:=\det\begin{pmatrix}\partial_{x_{1}}E_{1}^{(i)}(U_{i})&\dots&\partial_{x_{n-1}}E_{1}^{(i)}(U_{i})&y_{1}\\\
\vdots&\ddots&\vdots&\vdots\\\
\partial_{x_{1}}E_{n}^{(i)}(U_{i})&\dots&\partial_{x_{n-1}}E_{n}^{(i)}(U_{i})&y_{n}\end{pmatrix}\in\mathbb{K}[\\{\partial_{x_{\ell}}E_{j}^{(i)}(U_{i})\\}_{1\leq
j\leq n,1\leq\ell\leq n-1}][y_{1},\ldots,y_{n}].$ (10)

Then it follows that
$\det(\operatorname{\mathsf{Jac}}_{\mathcal{S}_{\textsf{dup}}^{\epsilon}})(\mathcal{P})=\pm\big{(}\prod\limits_{i=1}^{nk}\det(\operatorname{\mathsf{Jac}}_{i}(U_{i}))\big{)}\cdot\det(\Lambda)$,
where

$\small\operatorname{\mathsf{Jac}}_{i}(u):=\begin{pmatrix}\partial_{x_{1}}E_{1}^{(i)}(u)&\dots&\partial_{x_{n}}E_{1}^{(i)}(u)&\partial_{u_{i}}E_{1}^{(i)}(u)\\\
\vdots&\ddots&\vdots&\vdots\\\
\partial_{x_{1}}E_{n-1}^{(i)}(u)&\dots&\partial_{x_{n}}E_{n-1}^{(i)}(u)&\partial_{u_{i}}E_{n-1}^{(i)}(u)\\\
\partial_{x_{1}}\operatorname{\mathsf{Det}}^{(i)}(u)&\dots&\partial_{x_{n}}\operatorname{\mathsf{Det}}^{(i)}(u)&\partial_{u_{i}}\operatorname{\mathsf{Det}}^{(i)}(u)\\\
\partial_{x_{1}}P^{(i)}(u)&\dots&\partial_{x_{n}}P^{(i)}(u)&\partial_{u_{i}}P^{(i)}(u)\end{pmatrix}\in\mathbb{L}[u][[t]]^{(n+1)\times(n+1)},\text{
\normalsize{and}}$
$\small\Lambda:=\big{(}R(\partial_{z_{j}}E_{1}^{(i)}(U_{i}),\ldots,\partial_{z_{j}}E_{n}^{(i)}(U_{i}))\big{)}_{1\leq
i,j+1\leq nk}\in\overline{\mathbb{L}}[[t^{\frac{1}{\star}}]]^{nk\times nk}.$
(11)

The proof that this product is nonzero is the content of 8 and 9.

######  Lemma 8.

For each $i=1,\dots,nk$, the determinant of
$\operatorname{\mathsf{Jac}}_{i}(U_{i})$ is nonzero.

###### Proof.

To prove that $\det(\operatorname{\mathsf{Jac}}_{i}(U_{i}))\neq 0$ we will
show that
$\textsf{val}_{t}(\det(\operatorname{\mathsf{Jac}}_{i}(U_{i})))<\infty$, where
$\textsf{val}_{t}$ denotes the valuation in $t$. The main idea here is to
expand $\det(\operatorname{\mathsf{Jac}}_{i}(U_{i}))$ with respect to the last
column and show that the least valuation comes from the product of
$\partial_{u_{i}}\operatorname{\mathsf{Det}}^{(i)}(U_{i})$ by the determinant
of its associated submatrix666For $A=(a_{i,j})_{1\leq i,j\leq n}$ some matrix
of size $n\times n$, the submatrix associated to an element $a_{i_{0},j_{0}}$
is the $(n-1)\times(n-1)$ submatrix of $A$ obtained by deletion of the
$i_{0}$th row and $j_{0}$th column from $A$., denoted by $\mathcal{M}$. For
some matrix $\mathcal{A}$ whose entries are series in $t$, we shall denote by
$\textsf{val}_{t}(\mathcal{A})$ the matrix of the valuations in $t$ of the
entries of $\mathcal{A}$.

We shall justify that the term with lowest exponent in $t$ in
$\det(\operatorname{\mathsf{Jac}}_{i}(U_{i}))$ comes from the first term in
the product
$\det(\mathcal{M})\cdot\partial_{u_{i}}\operatorname{\mathsf{Det}}^{(i)}(U_{i})$.
By construction, the monomials in $\\{E_{i}\\}_{1\leq i\leq n}$ that are
quadratic in the variables $\\{x_{j}\\}_{1\leq j\leq n}$ all carry a
$t^{\alpha}$, so that
$\partial_{x_{j}}\operatorname{\mathsf{Det}}^{(i)}(U_{i})=O(t^{\alpha})$ for
all $1\leq j\leq n$ and all $1\leq i\leq nk$. Thus when expending
$\det(\operatorname{\mathsf{Jac}}_{i}(U_{i}))$ with respect to the last column
of $\operatorname{\mathsf{Jac}}_{i}(U_{i})$, the minors associated with
$\partial_{u_{i}}E_{j}^{(i)}(U_{i})$ and $\partial_{u_{i}}P^{(i)}(U_{i})$ are
in $O(t^{\alpha})$ (for $1\leq i\leq nk$).

Thus, it remains to prove that
$\textsf{val}_{t}(\partial_{u_{i}}\operatorname{\mathsf{Det}}^{(i)}(U_{i})\cdot\det(\mathcal{M}))<\alpha$;
this is done in the remaining part of the proof. Note that the expression of
$\operatorname{\mathsf{Det}}\bmod t^{n+1}$ in the proof of 6 implies that

$\textsf{val}_{t}(\partial_{u_{i}}\operatorname{\mathsf{Det}}^{(i)}(U_{i}))=(M-nk)/k+n-1+(k-1)/k=(M-1)/k.$
(12)

For $\det(\mathcal{M})$ there are two cases to treat separately: Either (Case
1) we have $U_{i}^{k}=n^{k}t\epsilon^{k}+(\text{higher powers of}~{}t)$, or
(Case 2) we have $U_{i}^{k}=m^{k}t\epsilon^{k}+(\text{higher powers of}~{}t)$
for some $m<n$. The reason for this distinction is that

$\partial_{x_{j}}E_{\ell}(u)=\begin{cases}-u^{m_{\ell}}+t\epsilon^{k}u^{m_{\ell}-k}\ell^{k},\text{
if }\ell=j,\\\ t^{\beta+1}\epsilon^{k}u^{m_{\ell}-k},\text{ else
},\end{cases}$ (13)

and, therefore, in Case 1 the $(\ell,\ell)$ entry of $\mathcal{M}$ always has
valuation in $t$ given by $m_{\ell}/k$ for each $\ell=1,\dots,n-1$, while in
Case 2 the entry of $\mathcal{M}$ on row and column $m$ has a valuation in $t$
that depends on $\beta$.

###### Case $\mathbf{1}$:

Assume that the $U_{i}$ of interest satisfies

$U_{i}^{k}=n^{k}t\epsilon^{k}+(\text{higher powers of}~{}t).$ (14)

By definition, $\mathcal{M}_{\ell,j}=\partial_{x_{j}}E_{\ell}(U_{i})$ for
$j=1,\dots,n$ and $\ell=1,\dots,n-1$ and thus from (13) we find

$\textsf{val}_{t}(\mathcal{M})_{\ell,j}=\begin{cases}\frac{m_{\ell}}{k}&\text{
if }\ell=j,\\\ \beta+\frac{m_{\ell}}{k}&\text{ else}.\end{cases}$ (15)

Moreover, we claim that the bottom right entry of $\mathcal{M}$ has valuation
$(M-1)/k$ in $t$. To prove this we compute

$\displaystyle\mathcal{M}_{n,n}=\partial_{x_{n}}P^{(i)}(U_{i})$
$\displaystyle=\partial_{x_{n}}\det\begin{pmatrix}\partial_{x_{1}}E_{1}&\dots&\partial_{x_{n-1}}E_{1}&\partial_{u}E_{1}\\\
\vdots&\ddots&\vdots&\vdots\\\
\partial_{x_{1}}E_{n}&\dots&\partial_{x_{n-1}}E_{n}&\partial_{u}E_{n}\\\
\end{pmatrix}^{(i)}(U_{i})$
$\displaystyle=\det\begin{pmatrix}\partial_{x_{1}}E_{1}&\dots&\partial_{x_{n-1}}E_{1}&\partial^{2}_{x_{n},u}E_{1}\\\
\vdots&\ddots&\vdots&\vdots\\\
\partial_{x_{1}}E_{n}&\dots&\partial_{x_{n-1}}E_{n}&\partial^{2}_{x_{n},u}E_{n}\\\
\end{pmatrix}^{(i)}(U_{i})\bmod t^{\alpha},$ (16)

since $\partial_{x_{n},x_{j}}^{2}E_{\ell}\in O(t^{\alpha})$ for each
$j=1,\dots,n$ and $\ell=1,\dots,n$. Regarding the last column of the above
matrix, a straightforward computations yields

$\partial^{2}_{x_{n},u}E_{n}(u)=-m_{n}u^{m_{n}-1}+t(m_{n}-k)n^{k}u^{m_{n}-k-1}+O(t^{\alpha}).$
(17)

From this and (14) it follows that
$\textsf{val}_{t}((\partial^{2}_{x_{n},u}E_{\ell})^{(i)}(U_{i}))=(m_{n}-1)/k$.
Moreover, using (13) and (15), we see that the only way to obtain in (16) a
term with exponent in $t$ independent of $\beta$ is to take the product of
entries of the main diagonal. The sufficiently large choice of $\beta=\lfloor
2{M}/{k}\rfloor$ implies that
$\textsf{val}_{t}(\mathcal{M}_{n,n})=\textsf{val}_{t}((\partial_{x_{n}}P)^{(i)}(U_{i}))=\frac{m_{1}}{k}+\cdots+\frac{m_{n-1}}{k}+\frac{m_{n}-1}{k}=(M-1)/k$,
where, as before, $M$ denotes $\sum_{j=1}^{n}m_{j}$.

Altogether, in this case we obtain that $\textsf{val}_{t}(\mathcal{M})$ has
the shape

$\small\textsf{val}_{t}(\mathcal{M})=\begin{pmatrix}\frac{m_{1}}{k}&\beta+\frac{m_{1}}{k}&\dots&\beta+\frac{m_{1}}{k}&\beta+\frac{m_{1}}{k}\\\
\beta+\frac{m_{2}}{k}&\frac{m_{2}}{k}&\dots&\beta+\frac{m_{2}}{k}&\beta+\frac{m_{2}}{k}\\\
\vdots&&\ddots&\vdots&\vdots\\\
\beta+\frac{m_{n-1}}{k}&\beta+\frac{m_{n-1}}{k}&\dots&\frac{m_{n-1}}{k}&\beta+\frac{m_{n-1}}{k}\\\
\star&\star&\dots&\star&(M-1)/k\end{pmatrix}.$

It follows that the only term in the determinant of $\mathcal{M}$ whose
exponent in $t$ has no dependency on $\beta$ comes from the product of the
entries located on the main diagonal of $\mathcal{M}$, and that the choice
$\beta=\lfloor 2{M}/{k}\rfloor$ ensures that
$\textsf{val}_{t}(\det(\mathcal{M}))<\beta$. Thus (12) implies
$\textsf{val}_{t}(\partial_{u_{i}}\operatorname{\mathsf{Det}}^{(i)}(U_{i})\cdot\det(\mathcal{M}))=(M-1)/k+(2M-m_{n}-1)/k$.
Finally, from $\alpha=3n^{2}k\cdot(\lfloor 2M/k\rfloor+1)+3nM$, it follows
that
$\textsf{val}_{t}(\partial_{u_{i}}\operatorname{\mathsf{Det}}^{(i)}(U_{i})\cdot\det(\mathcal{M}))<\alpha$,
as wanted.

###### Case $\mathbf{2}$:

The second case is similar in spirit to Case 1, but because of (13) when
$U_{i}$ is not of the form (14), computing the valuation in $t$ of
$\det(\mathcal{M})$ is slightly more delicate. In this case

$U_{i}^{k}=m^{k}t\epsilon^{k}+(\text{higher powers of}~{}t),$ (18)

for some $m<n$. For the sake of better readability, we shall assume without
loss of generality that $m=1$, since the argument works equally well in the
general case.

It follows from the definition of $\mathcal{M}$ and (13) that

$\mathcal{M}=\begin{pmatrix}-U_{i}^{m_{1}}+t\epsilon^{k}U_{i}^{m_{1}-k}&\dots&\epsilon^{k}t^{\beta+1}U_{i}^{m_{1}-k}&\epsilon^{k}t^{\beta+1}U_{i}^{m_{1}-k}\\\
\vdots&\ddots&\vdots&\vdots\\\
\epsilon^{k}t^{\beta+1}U_{i}^{m_{n-1}-k}&\dots&-U_{i}^{m_{n-1}}+(n-1)^{k}t\epsilon^{k}U_{i}^{m_{n-1}-k}&\epsilon^{k}t^{\beta+1}U_{i}^{m_{n-1}-k}\\\
\partial_{x_{1}}P^{(i)}(U_{i})&\dots&\partial_{x_{n-1}}P^{(i)}(U_{i})&\partial_{x_{n}}P^{(i)}(U_{i})\end{pmatrix}\operatorname{mod}t^{\alpha}.$

As before in (15), for $1\leq j\leq n$, we have
$\textsf{val}_{t}(\epsilon^{k}t^{\beta+1}U_{i}^{m_{j}-k})=\beta+\frac{m_{j}}{k}$.
Also, assuming that $m=1$, we have for all $2\leq j\leq n-1$ that

$-U_{i}^{m_{j}}+j^{k}t\epsilon^{k}U_{i}^{m_{j}-k}=\lambda_{i,j}\cdot
t^{\frac{m_{j}}{k}}+(\text{higher powers of}~{}t),$

for some nonzero $\lambda_{i,j}\in\overline{\mathbb{K}}(\epsilon)$. However,
for $j=1$ the term $\lambda_{i,j}$ vanishes and so we shall compute the
valuation in $t$ of $-U_{i}^{m_{1}}+t\epsilon^{k}U_{i}^{m_{1}-k}$ in this
case. From the expansion of $\operatorname{\mathsf{Det}}(u)$ to higher order
terms

$\displaystyle\operatorname{\mathsf{Det}}(u)=u^{M-nk}\cdot[\prod_{1\leq j\leq
n}{(-u^{k}+j^{k}t\epsilon^{k})}-t^{2(\beta+1)}\epsilon^{2k}\sum_{1\leq\ell<j\leq
n}\prod_{\begin{subarray}{c}b=1,\\\ b\neq\ell,b\neq
j\end{subarray}}^{n}{(-u^{k}+b^{k}t\epsilon^{k})}]+O(t^{3\beta}),$

we use Newton’s method to find the second lowest term of $U_{i}$ with respect
to the exponent in $t$:

$U_{i}=\zeta^{\ell_{i}}t^{\frac{1}{k}}\epsilon+\lambda_{i}t^{2\beta+\frac{1}{k}}+(\text{higher
powers of}~{}t),$

for some $1\leq\ell_{i}\leq k$ and $\lambda_{i}\neq 0$. This implies that

$\displaystyle\textsf{val}_{t}(\mathcal{M}_{1,1})=\operatorname{val}_{t}(-U_{i}^{m_{1}}+t\epsilon^{k}U_{i}^{m_{1}-k})$
$\displaystyle=\textsf{val}_{t}(U_{i}^{m_{1}-k})+\textsf{val}_{t}(-U_{i}^{k}+t\epsilon^{k})$
$\displaystyle=\frac{m_{1}-k}{k}+\frac{(k-1)}{k}+2\beta+\frac{1}{k}=2\beta+\frac{m_{1}}{k}.$

It remains to understand the valuation in $t$ of the last row of
$\mathcal{M}$, i.e. of $\\{\partial_{x_{j}}P^{(i)}(U_{i})\\}_{1\leq j\leq n}$.
The same argument as in (16) implies that for any $j=1,\dots,n$ we have

$(\partial_{x_{j}}P)^{(i)}(U_{i})=\det\begin{pmatrix}-U_{i}^{m_{1}}+t\epsilon^{k}U_{i}^{m_{1}-k}&\dots&\epsilon^{k}t^{\beta+1}U_{i}^{m_{1}-k}&\partial^{2}_{x_{j},u}E_{1}^{(i)}(U_{i})\\\
\vdots&\ddots&\vdots&\vdots\\\
\epsilon^{k}t^{\beta+1}U_{i}^{m_{n}-k}&\dots&\epsilon^{k}t^{\beta+1}U_{i}^{m_{n}-k}&\partial^{2}_{x_{j},u}E_{n}^{(i)}(U_{i})\\\
\end{pmatrix}\operatorname{mod}t^{\alpha}.$

Moreover, in spirit of (17) it holds because of (13) and (18) that

$\displaystyle\partial^{2}_{u,x_{j}}E_{\ell}(U_{i})=\begin{cases}(m_{\ell}-1)/k&\text{
if }j=\ell,\\\ O(t^{\beta+\frac{m_{\ell}-1}{k}})&\text{else.}\end{cases}$

Putting everything together, it follows that

$\textsf{val}_{t}(\partial_{x_{j}}P^{(i)}(U_{i}))=\textsf{val}_{t}\det\begin{pmatrix}t^{2\beta+\frac{m_{1}}{k}}&\cdots&\cdots&t^{\beta+\frac{m_{1}}{k}}&t^{\beta+\frac{m_{1}-1}{k}}\\\
t^{\beta+\frac{m_{2}}{k}}&t^{\frac{m_{2}}{k}}&t^{\beta+\frac{m_{1}}{k}}&\cdots&t^{\beta+\frac{m_{2}-1}{k}}\\\
\vdots&\ddots&\ddots&\ddots&\vdots\\\
t^{\beta+\frac{m_{j}}{k}}&\cdots&t^{\frac{m_{j}}{k}}&t^{\beta+\frac{m_{j}}{k}}&t^{(m_{j}-1)/k}\\\
\vdots&\ddots&\ddots&\ddots&\vdots\\\
t^{\beta+\frac{m_{n-1}}{k}}&\cdots&t^{\beta+\frac{m_{n-1}}{k}}&t^{\frac{m_{n-1}}{k}}&t^{\beta+\frac{m_{n-1}-1}{k}}\\\
t^{\beta+\frac{m_{n}}{k}}&\cdots&t^{\beta+\frac{m_{n}}{k}}&t^{\beta+\frac{m_{n}}{k}}&t^{\beta+\frac{m_{n}-1}{k}}\\\
\end{pmatrix},$

where in the matrix above the $(i_{0},j_{0})$ entry is $t^{\beta+m_{i_{0}}/k}$
if $1\leq j_{0}<n$ and $1\leq i_{0}\neq j_{0}\leq n$, $t^{m_{i_{0}}/k}$ if
$1<i_{0}=j_{0}<n$, $t^{2\beta+m_{1}/k}$ if $i_{0}=j_{0}=1$,
$t^{\beta+\frac{m_{i_{0}}-1}{k}}$ if $j_{0}=n,i_{0}\neq j$, and
$t^{(m_{j}-1)/k}$ if $j_{0}=n,i_{0}=j$. From this we obtain that
$\textsf{val}_{t}(\partial_{x_{j}}P^{(i)}(U_{i}))$ is at least
$2\beta+{(M-1)/k}$, except if $j=1$, since then it is given by the valuation
of the product of the lower left entry, the upper right entry and the
remaining entries on the diagonal of the matrix above. In other words:

$\displaystyle\textsf{val}_{t}(\partial_{x_{j}}P^{(i)}(U_{i}))=\begin{cases}\beta+(M-1)/k&\text{
if }j=1,\\\ \geq{2\beta+{(M-1)/k}}&\text{else.}\end{cases}$

This means that $\textsf{val}_{t}(\mathcal{M})$ has the shape

$\begin{pmatrix}2\beta+\frac{m_{1}}{k}&\beta+\frac{m_{1}}{k}&\cdots&\cdots&\beta+\frac{m_{1}}{k}\\\
\beta+\frac{m_{2}}{k}&\frac{m_{2}}{k}&\beta+\frac{m_{2}}{k}&\cdots&\beta+\frac{m_{2}}{k}\\\
\vdots&\ddots&\ddots&\ddots&\vdots\\\ \vdots&\ddots&\ddots&\ddots&\vdots\\\
\beta+\frac{m_{n-2}}{k}&\cdots&\frac{m_{n-2}}{k}&\beta+\frac{m_{n-2}}{k}&\beta+\frac{m_{n-2}}{k}\\\
\beta+\frac{m_{n-1}}{k}&\cdots&\beta+\frac{m_{n-1}}{k}&\frac{m_{n-1}}{k}&\beta+\frac{m_{n-1}}{k}\\\
\beta+\frac{M-1}{k}&\geq 2\beta+\frac{M-1}{k}&\cdots&\geq
2\beta+\frac{M-1}{k}&\geq 2\beta+\frac{M-1}{k}\\\ \end{pmatrix}.$

We see that the valuation of $\det(\mathcal{M})$ is $2\beta+(2M-m_{n}-1)/k$,
since it is given by the sum of the lower left entry, the upper right entry
and the remaining entries on the diagonal of the matrix above. Note that each
other combination will sum to at least $4\beta$ and the choice $\beta=\lfloor
2M/k\rfloor$ ensures that this term is strictly larger.

It remains to check that also in this case our choice for $\alpha$ was large
enough to guarantee that
$\textsf{val}_{t}(\partial_{u_{i}}\operatorname{\mathsf{Det}}^{(i)}(U_{i})\cdot\det(\mathcal{M}))<\alpha$.
Using that $\textsf{val}_{t}(\det(\mathcal{M}))=2\beta+(2M-m_{n}-1)/k$ and
(12), we obtain

$\textsf{val}_{t}(\partial_{u_{i}}\operatorname{\mathsf{Det}}^{(i)}(U_{i}))+\textsf{val}_{t}(\det(\mathcal{M}))=2\beta+\frac{3M-m_{n}-2}{k}<2\beta+\frac{3M}{k}.$

As $2\beta+\frac{3M}{k}<\alpha$, this concludes the proof of 8. ∎

######  Lemma 9.

The determinant of $\Lambda$ is nonzero.

Proving that $\det(\Lambda)\neq 0$ is again done by analyzing the first terms
in $t$ of $\det(\Lambda)$. More precisely, we are going to show that
$\det(\Lambda)$ factors modulo $t^{\alpha}$ as: a product of $U_{i}$, the
Vandermonde determinant $\prod_{i<j}(U_{i}-U_{j})$, and a nonzero polynomial
$H(t)\in\mathbb{K}[t]$.

Before starting with the proof we shall prove the following simple but useful
fact:

######  Lemma 10.

Let $\mathbb{F}$ be a field and $m\in\mathbb{N}$. Consider polynomials
$A_{1},\ldots,A_{m}\in~{}\mathbb{F}[x]$ and define
$M\coloneqq(A_{i}(x_{j}))_{1\leq j,i\leq m}$. Then $\det(M)=0$ if and only if
there exist $\lambda_{1},\ldots,\lambda_{m}\in\mathbb{F}$ not all equal to $0$
such that we have the linear combination $\sum_{i=1}^{m}{\lambda_{i}\cdot
A_{i}(x)=0}$.

###### Proof.

Clearly, if the linear combination $\sum_{i=1}^{m}{\lambda_{i}\cdot
A_{i}(x)=0}$ exists, $M$ is singular and its determinant vanishes. For the
other direction, we can assume without loss of generality that, up to
permutation of columns of $M$ and linear operations on them,
$\deg(A_{1}(x))>\cdots>\deg(A_{n}(x))$777Here $\deg(0)=-\infty$ and we allow
us to write $-\infty>-\infty$.. Then, since $\det(M)=0$, we must have that
$A_{i}(x)=0$ for some $i=1,\dots,n$, because the product of the diagonal
elements of $M$ cannot cancel otherwise. ∎

###### Proof of 9.

Recall from (10) and (11) that

$\small\Lambda\coloneqq\big{(}R(\partial_{z_{j}}E_{1}^{(i)}(U_{i}),\ldots,\partial_{z_{j}}E_{n}^{(i)}(U_{i}))\big{)}_{1\leq
i,j+1\leq nk}\in\overline{\mathbb{L}}[[t^{\frac{1}{\star}}]]^{nk\times nk},$

where

$\small
R\coloneqq\det\begin{pmatrix}\partial_{x_{1}}E_{1}^{(i)}(U_{i})&\dots&\partial_{x_{n-1}}E_{1}^{(i)}(U_{i})&y_{1}\\\
\vdots&\ddots&\vdots&\vdots\\\
\partial_{x_{1}}E_{n}^{(i)}(U_{i})&\dots&\partial_{x_{n-1}}E_{n}^{(i)}(U_{i})&y_{n}\end{pmatrix}\in\mathbb{K}[\\{\partial_{x_{\ell}}E_{j}^{(i)}(U_{i})\\}_{1\leq\ell\leq
n-1,1\leq j\leq n}][y_{1},\ldots,y_{n}].$

We shall first define and analyze the symbolic matrix $\tilde{\Lambda}$:

$\tilde{\Lambda}(u_{1},\dots,u_{n})=\tilde{\Lambda}\coloneqq(\tilde{R}_{j}^{(i)})_{1\leq
i,j+1\leq nk}\in\mathbb{L}[t][u_{1},\ldots,u_{nk}]^{nk\times nk},\text{
where}$ $\displaystyle\tilde{R}_{j}\;$
$\displaystyle:=\det\begin{pmatrix}\partial_{x_{1}}E_{1}&\dots&\partial_{x_{n-1}}E_{1}&\partial_{z_{j}}E_{1}\\\
\vdots&\ddots&\vdots&\vdots\\\
\partial_{x_{1}}E_{n}&\dots&\partial_{x_{n-1}}E_{n}&\partial_{z_{j}}E_{n}\end{pmatrix}\bmod
t^{\alpha}\in\mathbb{L}[t][u].$

Note that the polynomial matrix $\tilde{\Lambda}$ is symbolic and it holds
that

$\tilde{\Lambda}(U_{1},\dots,U_{nk})\equiv\Lambda\bmod t^{\alpha}.$ (19)

We will prove 9 in 3 steps corresponding to the 3 claims:

  * •

Claim 1: For the symbolic matrix $\tilde{\Lambda}$ it holds that
$\det(\tilde{\Lambda})\neq 0$.

  * •

Claim 2: We have that
$\det(\tilde{\Lambda})=\prod_{i=1}^{nk}{u_{i}^{M-nk}}\cdot\prod_{i<j}{(u_{i}-u_{j})}\cdot
H(t)$, for some nonzero polynomial $H(t)\in\mathbb{L}[t]$ of degree bounded by
$n^{2}k(\beta+1)$.

  * •

Claim 3: It holds that $\det(\tilde{\Lambda}(U_{1},\dots,U_{nk}))\bmod
t^{\alpha}\neq 0$, in particular, we have $\Lambda\neq 0$.

Before we start with the proofs of the three claims, we mention that it
follows from the definition of $E_{\ell}$ and our deformation that for $0\leq
j\leq nk-1$ and $1\leq\ell\leq n$ we have

$\partial_{z_{j}}E_{\ell}\mod
t^{\alpha}=\begin{cases}-\frac{t\epsilon^{k}\ell^{k}}{(j-k(\ell-1))!}u^{m_{\ell}+j-k(\ell-1)-k},\text{
if }j\in\\{k\ell-k,\ldots,k\ell-1\\},\\\
-\frac{t^{\beta+1}\epsilon^{k}}{h!}u^{m_{\ell}+h-k}\text{ else, with }h=j\bmod
k\text{ and }0\leq h<k.\end{cases}$ (20)

We will crucially use the fact that $\partial_{z_{j}}E_{\ell}\bmod t^{\alpha}$
is divisible by $u^{m_{\ell}-k}$ and that the quotient is a monomial in $u$ of
degree at most $k-1$.

Proof of Claim $\mathbf{1}$: Assume that $\det(\tilde{\Lambda})=0$. By 10
applied to $\tilde{\Lambda}$, there exist polynomials
$\lambda_{0},\ldots,\lambda_{nk-1}\in\mathbb{L}[t]$ not all equal to $0$ such
that $\sum_{i=0}^{nk-1}\lambda_{i}\cdot\tilde{R}_{i}=0$. For all $0\leq i\leq
nk-1$ the matrices associated to the $R_{i}$’s share the same $n-1$ first
columns, while the last column is equal to
$(\partial_{z_{i}}E_{\ell})_{1\leq\ell\leq n}$. From (20) it follows that for
all $1\leq i+1,\ell\leq n$ and for all $0\leq j\leq k-1$, we have
$\partial_{z_{ik+j}}E_{\ell}=\frac{u^{j}}{j!}\partial_{z_{{ik}}}E_{\ell}$.
Thus, using the multi-linearity of the determinant, it follows that for all
$0\leq i\leq n-1$ and $0\leq j\leq k-1$, we have
$\tilde{R}_{ik+j}=\frac{u^{j}}{j!}\cdot\tilde{R}_{ik}$. This implies that the
linear combination $\sum_{i=0}^{nk-1}\lambda_{i}\cdot\tilde{R}_{i}(u)=0$
rewrites into the form

$\sum_{i=0}^{n-1}\sum_{j=0}^{k-1}\lambda_{ik+j}\cdot\frac{u^{j}}{j!}\cdot\tilde{R}_{ik}=0.$
(21)

Moreover, the combination of (13) and (20) implies that all entries the $i$th
row of the matrix defining $\tilde{R}_{j}$ are divisible by $u^{m_{i}-k}$.
Define

$P_{\ell}(u)\coloneqq
u^{-m_{\ell}+k}\sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{k-1}\lambda_{ik+j}\cdot\frac{u^{j}}{j!}\cdot\partial_{z_{ik}}E_{\ell}\bmod
t^{\alpha}\quad\text{for }\ell=1,\dots,n,$

so that equations (13) and (21), as well as the multi-linearity of the
determinant imply that

$\mathcal{B}(u)\coloneqq\begin{pmatrix}-u^{k}+t\epsilon^{k}&\epsilon^{k}t^{\beta+1}&\cdots&\epsilon^{k}t^{\beta+1}&P_{1}\\\
\epsilon^{k}t^{\beta+1}&-u^{k}+t\epsilon^{k}2^{k}&\cdots&\epsilon^{k}t^{\beta+1}&P_{2}\\\
\vdots&\vdots&\ddots&\vdots&\vdots\\\
\epsilon^{k}t^{\beta+1}&\epsilon^{k}t^{\beta+1}&\cdots&-u^{k}+t\epsilon^{k}(n-1)^{k}&P_{n-1}\\\
\epsilon^{k}t^{\beta+1}&\epsilon^{k}t^{\beta+1}&\cdots&\epsilon^{k}t^{\beta+1}&P_{n}\end{pmatrix}$

is a singular polynomial matrix. Observe from (20) that $\deg_{u}P_{\ell}<k$
for $\ell=1,\dots,n$. Using this and $\det(\mathcal{B})=0$ we shall now show
that $P_{1}=\cdots=P_{n}=0$.

First note that when computing the determinant of $\mathcal{B}$ using the
Leibniz rule, we would get the product of all entries on the main diagonal and
products of other terms which will be polynomials in $u$ of degree at most
$(n-1)k-1$. The contribution of the main diagonal contains $u^{(n-1)k}P_{n}$.
Clearly, this term cannot cancel with others, unless $P_{n}$ vanishes.

Fix some $1\leq\ell\leq n-1$ and define
$\omega_{1},\dots,\omega_{k}\in\overline{\mathbb{K}}[\epsilon][[t^{1/\star}]]$
to be the distinct solutions of
$u^{k}=t\epsilon^{k}\ell^{k}-t^{\beta+1}\epsilon^{k}$. Clearly,
$\det(\mathcal{B}(\omega_{i}))=0$ for $i=1,\dots,k$, and by definition of
$\omega_{i}$, the first $n-1$ entries of the $\ell$th row of
$\mathcal{B}(\omega_{i})$ agree with the first $n-1$ entries of its last row.
Therefore, expanding along the last column, we find that

$0=\det(B(\omega_{i}))=\pm
P_{\ell}(\omega_{i})\cdot\det(\mathcal{B}_{\ell,n}(\omega_{i})),$

where $\mathcal{B}_{\ell,n}$ denotes the matrix $\mathcal{B}$ with the
$\ell$th row and last column removed. By subtracting the $\ell$th column from
all others one can easily compute $\det(\mathcal{B}_{\ell,n}(\omega_{i}))$, in
particular it follows that it is nonzero. So we conclude that
$P_{\ell}(\omega_{i})=0$ for $i=1,\dots,k$ and, then, since
$\deg_{u}P_{\ell}(u)<k$, it finally follows that $P_{\ell}$ vanishes
identically.

By (20) we have that $\deg_{u}\partial_{z_{ik}}E_{\ell}=m_{\ell}-k$,
therefore, looking at the coefficient of $u^{j}$ of $P_{\ell}(u)=0$ for
$j=0,\dots,k-1$, we obtain with (20) the following linear relations for the
$\lambda_{i}$’s:

$\begin{pmatrix}1&t^{\beta}&\cdots&t^{\beta}\\\
t^{\beta}&2^{k}&\cdots&t^{\beta}\\\ \vdots&\ddots&\ddots&\vdots\\\
t^{\beta}&\cdots&\cdots&n^{k}\end{pmatrix}\times\begin{pmatrix}\lambda_{j}\\\
\lambda_{k+j}\\\ \vdots\\\ \lambda_{(n-1)k+j}\end{pmatrix}=0,\;\text{ for all
$0\leq j\leq k-1$}.$ (22)

As the square matrix in (22) is invertible, we obtain that $\lambda_{i}=0$ for
all $i=0,\dots,nk-1$ which contradicts our assumption. Hence we have proved
that $\det(\tilde{\Lambda})\neq~{}0$.

Proof of Claim 2: We prove the following explicit factorization of
$\det(\tilde{\Lambda})$:

$\det(\tilde{\Lambda})=\prod_{i=1}^{nk}{u_{i}^{M-nk}}\cdot\prod_{i<j}{(u_{i}-u_{j})}\cdot
H(t),$ (23)

where $H(t)\in\mathbb{K}[\epsilon,t]$ is nonzero and of degree in $t$ at most
$n^{2}(\beta+1)$.

From (13) we know that for $0\leq j\leq nk-1$, the polynomial $\tilde{R}_{j}$
is given by

$\det\begin{pmatrix}u^{m_{1}}+t\epsilon^{k}u^{m_{1}-k}&t^{b+1}u^{m_{1}-k}&\cdots&\epsilon^{k}t^{b+1}u^{m_{1}-k}&\partial_{z_{j}}E_{1}\\\
\epsilon^{k}t^{b+1}u^{m_{2}-k}&u^{m_{2}}+t\epsilon^{k}2^{k}u^{m_{2}-k}&\cdots&\epsilon^{k}t^{b+1}u^{m_{2}-k}&\partial_{z_{j}}E_{2}\\\
\vdots&\vdots&\ddots&\vdots&\vdots\\\
\epsilon^{k}t^{b+1}u^{m_{n-1}-k}&\epsilon^{k}t^{b+1}u^{m_{n-1}-k}&\cdots&u^{m_{n-1}-k}(u^{k}+t\epsilon^{k}(n-1)^{k})&\partial_{z_{j}}E_{n-1}\\\
\epsilon^{k}t^{b+1}u^{m_{n}-k}&\epsilon^{k}t^{b+1}u^{m_{n}-k}&\cdots&\epsilon^{k}t^{b+1}u^{m_{n}-k}&\partial_{z_{j}}E_{n}\end{pmatrix}\bmod
t^{\alpha}.$

It follows from (20) that $u^{-m_{\ell}+k}\deg_{z_{j}}E_{\ell}$ is a monomial
of degree at most $k-1$ in $u$. Since all other terms in the $\ell$th row of
$\tilde{R}_{j}$ are trivially divisible by $u^{m_{\ell}-k}$, and
$\alpha>n(\beta+1)$, it follows that $\tilde{R}_{j}$ factors as $u^{M-nk}$
times the determinant of the polynomial matrix

$\begin{pmatrix}u^{k}+t\epsilon^{k}&\epsilon^{k}t^{b+1}&\cdots&\epsilon^{k}t^{b+1}&u^{-m_{1}+k}\partial_{z_{j}}E_{1}\\\
\epsilon^{k}t^{b+1}&u^{k}+t\epsilon^{k}2^{k}&\cdots&\epsilon^{k}t^{b+1}&u^{-m_{2}+k}\partial_{z_{j}}E_{2}\\\
\vdots&\vdots&\ddots&\vdots&\vdots\\\
\epsilon^{k}t^{b+1}&\epsilon^{k}t^{b+1}&\cdots&u^{k}+t\epsilon^{k}(n-1)^{k}&u^{-m_{n-1}+k}\partial_{z_{j}}E_{n-1}\\\
\epsilon^{k}t^{b+1}&\epsilon^{k}t^{b+1}&\cdots&\epsilon^{k}t^{b+1}&u^{-m_{n}+k}\partial_{z_{j}}E_{n}\end{pmatrix}\bmod
t^{\alpha},$ (24)

where, as before, $M\coloneqq\sum_{i=1}^{n}m_{i}$. Thus, $u^{M-nk}$ divides
$\tilde{R}_{j}$. Moreover, the degree in $u$ of the first $n-1$ columns of
(24) is upper-bounded by $k$ and the last column of this matrix has degree at
most $k-1$, so it follows that $\deg_{u}(\tilde{R}_{j})\leq M-1$.

Let us consider $\tilde{\Lambda}$ which is by definition the matrix
$(\tilde{R}_{j}^{(i)})_{1\leq i,j+1\leq
nk}\in\mathbb{L}[t][u_{1},\ldots,u_{nk}]^{nk\times nk}$. Since
$\deg_{u}(\tilde{R}_{j})\leq M-1$, we also have that
$\det_{u_{i}}(\tilde{\Lambda})\leq M-1$ for each $i=1,\dots,nk$. From the
considerations above it also follows that $\det(\tilde{\Lambda})$ is divisible
by $\prod_{i=1}^{nk}{u_{i}^{M-nk}}$. Moreover, it is obvious that if
$u_{i}=u_{j}$ for some $i\neq j$, the determinant of $\tilde{\Lambda}$
vanishes. Hence, we can also factor out the Vandermonde determinant
$\prod_{i<j}{(u_{i}-u_{j})}$ from $\det(\tilde{\Lambda})$. By comparing
degrees in each $u_{i}$ it follows that the remaining factor is a constant
with respect to $u_{i}$ and hence (23) holds. By Claim 1, $H(t)$ is nonzero,
so it remains to prove that $\deg_{t}H(t)\leq n^{2}k(\beta+1)$. This follows
directly from the fact that the degree in $t$ of the $\tilde{R}_{j}$’s is
bounded by $n(\beta+1)$ as determinants of $(n\times n)$ matrices whose
polynomial coefficients have degree in $t$ upper-bounded by $\beta+1$.

Finally for this step, using the definitions
$\alpha=3n^{2}k\cdot(\beta+1)+3nM$ and $\beta=\lfloor 2{M}/{k}\rfloor$, we
have that $\alpha>n^{2}k(\beta+1)$. So that
$\deg_{t}(\det(\tilde{\Lambda}))<\alpha$: by Claim $1$, we obtain
$\det(\tilde{\Lambda})\neq 0\bmod t^{\alpha}$.

Proof of Claim 3: Having established (23) it is now enough to show that

$\textsf{val}_{t}(\prod_{i=1}^{nk}{U_{i}^{M-nk}}\cdot\prod_{i<j}{(U_{i}-U_{j})}\cdot
H(t))<\alpha.$ (25)

Recall from 6 that $U_{i}=t^{1/k}\epsilon j\zeta^{\ell}+(\text{higher powers
of}~{}t)$ for $i=1,\dots,nk$, $j=1,\dots,n$ and $\zeta$ a primitive $k$th root
of unity. Thus, and because $\deg_{t}(H)\leq n^{2}k(\beta+1)$ by Claim 2, the
left-hand side of (25) is bounded by
$nk\cdot\frac{M-nk}{k}+nk(nk-1)\cdot\frac{1}{k}+n^{2}k(\beta+1)$, which is at
most $nM+n^{2}k(\beta+1)$. Since $\alpha=3n^{2}k\cdot(\beta+1)+3nM$, we
conclude that $\det(\tilde{\Lambda}(U_{1},\dots,U_{nk}))\bmod t^{\alpha}\neq
0$. Finally, together with (19) this implies that $\det(\Lambda)$ does not
vanish as well. ∎

Having now proved that
$\det(\operatorname{\mathsf{Jac}}_{\mathcal{S}_{\textsf{dup}}^{\epsilon}})\neq
0$ at $\mathcal{P}$, we can apply 7 and obtain that the specialized series
$G_{i}(0),\ldots,\partial_{u}^{k-1}G_{i}(0)$ are all algebraic over
$\mathbb{K}(t,\epsilon)$. The algebraicity of the complete formal power series
$G_{1},\ldots,G_{n}$ over $\mathbb{K}(t,u,\epsilon)$ then follows again by [8,
Lemma 2.10] from the invertibility of the Jacobian matrix of
$E_{1},\ldots,E_{n}$ considered with respect to the variables
$x_{1},\ldots,x_{n}$ (with $t,u,z_{0},\ldots,z_{nk-1}$ viewed as parameters).
The equalities $F_{i}(t^{\alpha},u)=G_{i}(t,u,0)$ finally imply that
$F_{1},\ldots,F_{n}$ are also algebraic over $\mathbb{K}(t,u)$.

###  3.2 Proof of 4

We prove the quantitative estimates announced in 4. The techniques of the
proof being standard in effective algebraic geometry, we will be quite brief
in the arguments. For more details on the upper bound on the algebraicity
degree, we refer the reader to [8, Prop. 2.8] in the case $n=k=1$, and to [9,
Prop. 3] for the more general case $n=1$ ($k$ arbitrary). For the complexity
proof, we refer the reader to [8, Prop. 2.9] and [9, Prop. $4$] in the two
respective cases. As in the proof of 3, we assume without loss of generality
that $a=0$.

Algebraicity degree bound: In order to bound the algebracity degree of
$F_{i}(t,u)$, we will provide an upper bound on the algebraicity degree of
$G_{i}(t,u,\epsilon)$ over $\mathbb{K}(t,u,\epsilon)$, where, as in the proof
of 3, $(G_{1},\dots,G_{n})$ denotes the solution of the deformed system (7).
Following the lines of the proof of Theorem 3, we shall first give explicit
bounds on the total degrees of all equations in
$\mathcal{S}_{\textsf{dup}}^{\epsilon}$. Note that in this part we are
interested in the algebraicity degree of $G_{i}(t,0)$ over
$\mathbb{K}(t,\epsilon)$, so in the computation of the total degree we take
into account all the variables
$u,u_{1},\ldots,u_{nk},x_{1},\dots,x_{n^{2}k},z_{0},\dots,z_{nk-1}$ but not
$t$ and $\epsilon$. In order to distinguish this restricted notion of total
degree from the usual total degree denoted by
$\operatorname{\mathsf{totdeg}}$, we will write it
$\operatorname{\mathsf{totdeg}}_{t,\epsilon}$.

Let $\delta$ be a bound on $\operatorname{\mathsf{totdeg}}_{t,\epsilon}$ of
$f_{1},\ldots,f_{n},Q_{1},\ldots,Q_{n}$; then the total degrees of
$E_{1},\ldots,E_{n}$ are bounded by $\delta(k+1)$. Moreover,
$\operatorname{\mathsf{totdeg}}_{t,\epsilon}(\operatorname{\mathsf{Det}}),\operatorname{\mathsf{totdeg}}_{t,\epsilon}(P)\leq
n\delta(k+1)$, since $\operatorname{\mathsf{Det}}$ and $P$ are determinants of
polynomial matrices of size $n\times n$ and degree at most $\delta(k+1)$.

Recall from 7 that the ideal
$\mathcal{I}_{\textsf{dup}}^{\epsilon}\subseteq\mathbb{K}(t,\epsilon)[x_{1},\ldots,x_{n^{2}k},u_{1},\ldots,u_{nk},z_{0},\ldots,z_{nk-1}]$
is defined by $nk$ duplications of the polynomials
$E_{1},\ldots,E_{n},\textsf{Det},P$. By 7 the saturated ideal
$\mathcal{I}_{\textsf{dup}}^{\epsilon}:\det(\textsf{Jac}_{\mathcal{S}_{\textsf{dup}}^{\epsilon}})^{\infty}$
is radical and of dimension $0$, and this yields bounds for the algebraicity
degrees of the specializations $\\{\partial_{u}^{i}G_{j}(0)\\}_{0\leq i\leq
k-1,1\leq j\leq n}$. More precisely, applying the Heintz-Bézout theorem [20,
Theorem $1$] in the same way as in [8, Prop. $3.1$], one obtains that the
algebraicity degree of any $\partial_{u}^{i}G_{j}(0)$ is bounded by

$\max_{i=1,\dots,n}(\operatorname{\mathsf{totdeg}}_{t,\epsilon}(E_{i}))^{n^{2}k}\cdot\textsf{totdeg}_{t,\epsilon}(\textsf{Det})^{nk}\cdot\operatorname{\mathsf{totdeg}}_{t,\epsilon}(P)^{nk}\leq
n^{2nk}\cdot(\delta(k+1))^{nk(n+2)}.$

We denote this bound by $\gamma(n,k,\delta)$.

As in [9, Prop. $4$] there is a group action of the symmetric group
$\mathfrak{S}_{nk}$ on the zero set associated to the ideal $\langle
E_{1}^{(1)},\ldots,E_{1}^{(nk)},\ldots,E_{n}^{(1)},\ldots,E_{n}^{(nk)},\textsf{Det}^{(1)},\ldots,\textsf{Det}^{(nk)},P^{(1)},\ldots,P^{(nk)}\rangle$
which permutes each of the $nk$ duplicated blocks of coordinates. As this
action preserves the $\\{t,z_{0},\ldots,z_{nk-1}\\}$-coordinate space, one
spares the cardinality of the orbits and deduces that an algebraicity upper
bound on any of the specialized series $\partial_{u}^{i}G_{j}(0)$ is also
given by ${\gamma(n,k,\delta)/(nk)!}$, that is we have

$\operatorname{\mathsf{algdeg}}_{\mathbb{K}(t,\epsilon)}(\partial_{u}^{i}G_{j}(0))\leq
n^{nk}\cdot(\delta(k+1))^{nk(n+2)}/(nk)!.$ (26)

Finally, it remains to give algebraicity bounds for the full series
$G_{1},\ldots,G_{n}$. This is done in the same fashion as above, this time
over the field extension

$\mathbb{K}(t,\epsilon,G_{1}(0),\ldots,\partial_{u}^{k-1}G_{1}(0),\ldots,G_{n}(0),\ldots,\partial_{u}^{k-1}G_{n}(0))/\mathbb{K}(t,\epsilon).$

Using (26) and the multiplicativity of the degrees in field extensions yields

$\operatorname{\mathsf{algdeg}}_{\mathbb{K}(t,u,\epsilon)}(G_{i}(u))\leq\delta^{n}(k+1)^{n}\cdot\left(\frac{n^{2nk}(\delta(k+1))^{nk(n+2)}}{(nk)!}\right)^{nk}\quad\text{
for }i=1,\dots,n,$

and, by specialization, the same bound then holds for
$\operatorname{\mathsf{algdeg}}_{\mathbb{K}(t,u)}(F_{i}(u))$ as well.

Complexity estimate: Let us recall that we fix $\mathbb{K}$ to be an effective
field of characteristic $0$ and we count the number of elementary operations
$(+,-,\times,\div)$ in $\mathbb{K}$. For proving the arithmetic complexity
estimate in 4, we rely on the use of the parametric geometric resolution (see
[24] for details). For this purpose we need:

  * •

the number of parameters and of variables of the input equations of interest,

  * •

and upper bound on the degree (with respect to all the variables and
parameters) of the saturated ideal
$\mathcal{I}_{\textsf{dup}}^{\epsilon}:\det(\operatorname{\mathsf{Jac}}_{\mathcal{S}_{\textsf{dup}}^{\epsilon}})^{\infty}$.

In our setting the parameters are $t$ and $\epsilon$ so we have two of them,
and the variables are

$x_{1},\ldots,x_{n^{2}k},z_{0},\ldots,z_{nk-1},u_{1},\ldots,u_{nk},$

so $nk(n+2)$ in total.

For computing an upper bound $\nu(n,k,\delta)$ on the degree of the ideal
$\mathcal{I}_{\textsf{dup}}^{\epsilon}:\det(\operatorname{\mathsf{Jac}}_{\mathcal{S}_{\textsf{dup}}^{\epsilon}})^{\infty}$,
we again apply the Heintz-Bézout theorem. Note that this time we must take
into account the total degree of the input system
$\mathcal{S}_{\textsf{dup}}^{\epsilon}$ with respect to both the variables and
the parameters. By the same arguments as in the first part of the proof and
using the definitions of $\alpha,\beta$, we find

${\nu(n,k,\delta)}=n^{2nk}(\delta\cdot(k+1)+3n^{2}k\cdot(2n\delta+1)+3nM)^{nk(n+2)}.$

Without loss of generality, we only address the computation of an annihilating
polynomial of $G_{1}(0)$ (and consequently of $F_{1}(0)$). The algorithm we
propose consists of two steps:

Step $1$: For $\lambda$ a new variable which is a random
$\mathbb{K}[t,\epsilon]$-linear combination of all the variables involved in
$\mathcal{S}_{\textsf{dup}}^{\epsilon}$, we compute two polynomials
$V(t,\epsilon,\lambda),W(t,\epsilon,\lambda)\in\mathbb{K}[t,\epsilon][\lambda]$,
such that: $G_{1}(0)$ is a solution888More precisely: the $z_{0}$th coordinate
of a solution of $\mathcal{S}_{\textsf{dup}}^{\epsilon}$ which is not a
solution of
$\det(\operatorname{\mathsf{Jac}}_{\mathcal{S}_{\textsf{dup}}^{\epsilon}})=0$.
of $\mathcal{S}_{\textsf{dup}}^{\epsilon}$ and not a solution of
$\det(\operatorname{\mathsf{Jac}}_{\mathcal{S}_{\textsf{dup}}^{\epsilon}})=0$
if and only if
$G_{1}(0)=V(t,\epsilon,\lambda_{0})/\partial_{\lambda}W(t,\epsilon,\lambda_{0})$
for $\lambda_{0}\in\overline{\mathbb{K}(t,\epsilon)}$ a solution of
$W(t,\epsilon,\lambda)=0$.

Step $2$: Compute the squarefree part $R\in\mathbb{K}[t,\epsilon,z_{0}]$ of
the resultant of
$z_{0}\cdot\partial_{\lambda}W(t,\epsilon,\lambda)-V(t,\epsilon,\lambda)$ and
$W(t,\epsilon,\lambda)$ with respect to $\lambda$.

By definition, $\lambda_{0}$ is a solution of
$\partial_{\lambda}W(t,\epsilon,\lambda)G_{1}(0)-V(t,\epsilon,\lambda)=0$ and
$W(t,\epsilon,\lambda)=0$, so $R(t,\epsilon,G_{1}(0))=0$ by the property of
the resultant. Moreover, it follows from the eigenvalue theorem [17, Theorem
$1$] and the fact that the dimension of the radical ideal
$\mathcal{I}_{\textsf{dup}}^{\epsilon}:\det(\operatorname{\mathsf{Jac}}_{\mathcal{S}_{\textsf{dup}}^{\epsilon}})^{\infty}$
is zero, that $R$ is a nonzero polynomial.

By [24, Theorem $2$], performing Step 1 can be done using
$\tilde{O}((Ln^{2}k+(n^{2}k)^{4})\cdot\nu(n,k,\delta)^{3})$ operations in
$\mathbb{K}$, where $L$ denotes the complexity of evaluating the duplicated
system $\mathcal{S}_{\textsf{dup}}^{\epsilon}$ at all variables and
parameters. Using the Bauer-Strassen theorem [3, Theorem $1$], the cost for
evaluating $\operatorname{\mathsf{Det}}$ and $P$ is in $O(nL^{\prime})$, where
$L^{\prime}$ is the cost for evaluating any of the $E_{1},\ldots,E_{n}$. The
total degrees of the $E_{i}$’s are bounded by
$d^{\prime}:=\delta\cdot(k+1)+3n^{2}k\cdot(2n\delta+1)+3nM$, so $L^{\prime}\in
O((d^{\prime})^{nk+n+3}))$, since $nk+n+3$ is the number of variables and
parameters. Duplicating $nk$ times the initial polynomials
$E_{1},\ldots,E_{n},\operatorname{\mathsf{Det}},P$, it follows that $L\in
O(n^{3}kL^{\prime})\subset O(n^{3}k(d^{\prime})^{nk+n+3})$. To do Step 2, we
perform evaluation-interpolation on $t$ and $\epsilon$. This requires to use
in total $O(\nu(n,k,\delta)^{2})$ distinct points from the base field
$\mathbb{K}$. For each specialization of
$z_{0}\cdot\partial_{\lambda}W(t,\epsilon,\lambda)-V(t,\epsilon,\lambda)$ and
$W(t,\epsilon,\lambda)$ to $t=\theta_{1}\in\mathbb{K}$ and
$\epsilon=\theta_{2}\in\mathbb{K}$, we compute the squarefree part of the
bivariate resultant of
$\partial_{\lambda}W(\theta_{1},\theta_{2},\lambda)\cdot
z_{\ell}-V(\theta_{1},\theta_{2},\lambda)$ and
$W(\theta_{1},\theta_{2},\lambda)$ with respect to $\lambda$. Using [26], this
requires $\tilde{O}((\nu(n,k,\delta)/(nk)!)^{3.63})$ operations in
$\mathbb{K}$.

In total we obtain that the arithmetic complexity is bounded by
$(2nk\delta)^{O(n^{2}k)}$ operations in $\mathbb{K}$. Deducing an annihilating
polynomial of $F_{1}(t,0)$ from the one annihilating $G_{1}(t,\epsilon=0,u=0)$
is included in the previous complexities. This proves 4. ∎

##  4 Elementary strategies for solving a system of DDEs

The present section aims at studying two strategies available at this time for
solving a system of DDEs in _practice_. Both approaches have the advantage to
be much more efficient than the algorithm resulting from 3, however they are
not guaranteed to always terminate. As before, the goal is, given a system of
DDEs of the form (5), to compute a nonzero polynomial
$R\in\mathbb{K}[t,z_{0}]$ such that $R(t,F_{1}(t,a))=~{}0$.

First, in section 4.1, we summarize the algorithm underlying the duplication
strategy that was used in the proof of 3 and we analyze its arithmetic
complexity _in the case where no symbolic deformation is necessary_ (the
arithmetic cost for solving a system of DDEs when such a symbolic deformation
is needed was the content of 4). In section 4.2, we study the practical
approach introduced and used in [10, Section $11$]: this approach consists in
_reducing_ the algorithmic study of a system of DDEs to the _study of a single
functional equation_ (which may not be of a fixed-point type). Once we are
left with this single equation, we apply the geometry-driven algorithm from
[9, Section $5$] which avoids the duplication of the variables.

###  4.1 The classical duplication of variables algorithm

####  4.1.1 General strategy

Consider the system of DDEs

$\begin{cases}\textbf{{\text{(E}}}_{\textbf{{\text{F}}}_{\textbf{{\text{1}}}}}\textbf{{\text{):}}}\;\;\;F_{1}=f_{1}(u)+t\cdot
Q_{1}(\nabla_{a}^{k}F_{1},\ldots,\nabla_{a}^{k}F_{n},t,u),\\\
\indent\vdots\hfill\vdots\;\;\;\;\;\\\
\textbf{{\text{(E}}}_{\textbf{{\text{F}}}_{\textbf{{\text{n}}}}}\textbf{{\text{):}}}\;\;F_{n}=f_{n}(u)+t\cdot
Q_{n}(\nabla_{a}^{k}F_{1},\ldots,\nabla_{a}^{k}F_{n},t,u),\end{cases}$ (27)

introduced in 3 and denote by $\operatorname{\mathcal{S}_{\mathsf{dup}}}$ the
duplicated polynomial system obtained by

  * •

considering the polynomials
$E_{1},\ldots,E_{n}\in\mathbb{K}(t)[x_{1},\ldots,x_{n},u,z_{0},\ldots,z_{nk-1}]$
associated to the “numerator equations”999For all $1\leq i\leq n$,
$E_{i}(u)\equiv
E_{i}(F_{1},\ldots,F_{n},u,F_{1}(t,a),\ldots,\partial_{u}^{k-1}F_{1}(t,a),\ldots,F_{n}(t,a),\ldots,\partial_{u}^{k-1}F_{n}(t,a))$.
of the system of DDEs (27), as well as the polynomials

$\operatorname{\mathsf{Det}}:=\det\begin{pmatrix}\partial_{x_{1}}E_{1}&\dots&\partial_{x_{n}}E_{1}\\\
\vdots&\ddots&\vdots\\\ \partial_{x_{1}}E_{n}&\dots&\partial_{x_{n}}E_{n}\\\
\end{pmatrix}\quad\text{ \normalsize{and} }\quad
P:=\det\begin{pmatrix}\partial_{x_{1}}E_{1}&\dots&\partial_{x_{n-1}}E_{1}&\partial_{u}E_{1}\\\
\vdots&\ddots&\vdots&\vdots\\\
\partial_{x_{1}}E_{n}&\dots&\partial_{x_{n-1}}E_{n}&\partial_{u}E_{n}\\\
\end{pmatrix},$

  * •

duplicating $nk$ times the variables $x_{1},\ldots,x_{n},u$ in the polynomials
$(E_{1},\ldots,E_{n},\operatorname{\mathsf{Det}},P)$ in order to obtain $nk$
duplications of the polynomials
$(E_{1},\ldots,E_{n},\operatorname{\mathsf{Det}},P)$ in the new variables
$x_{1},\ldots,x_{n^{2}k}$, $u_{1},\ldots,u_{nk}$ and (unchanged variables)
$z_{0},\ldots,z_{nk-1}$.

######  Example 2 (cont.).

We consider 2, where $k=1$ and $n=2$. We have the polynomials

$\begin{cases}E_{1}:=-(x_{1}-1)(u-1)+tu(2ux_{1}^{2}-uz_{0}+2uz_{2}-2x_{1}^{2}+u+x_{1}-2z_{2}-1),\\\
E_{2}:=-x_{2}(u-1)+tu(2ux_{1}x_{2}+ux_{1}-2x_{1}x_{2}-x_{1}+x_{2}-z_{2}).\end{cases}$

We compute

$\displaystyle\operatorname{\mathsf{Det}}$
$\displaystyle=\det\begin{pmatrix}\partial_{x_{1}}E_{1}&\partial_{x_{2}}E_{1}\\\
\partial_{x_{1}}E_{2}&\partial_{x_{2}}E_{2}\end{pmatrix}=(4tu^{2}x_{1}-4tux_{1}+tu-u+1)(2tu^{2}x_{1}-2tux_{1}+tu-u+1).$

and the rather large polynomial
$P=\det\begin{pmatrix}\partial_{x_{1}}E_{1}&\partial_{u}E_{1}\\\
\partial_{x_{1}}E_{2}&\partial_{u}E_{2}\end{pmatrix}$. We obtain by the
duplication strategy the set $\operatorname{\mathcal{S}_{\mathsf{dup}}}$ of
polynomials given by

$\displaystyle\operatorname{\mathcal{S}_{\mathsf{dup}}}:=\\{$
$\displaystyle(E_{1}(x_{1},x_{2},u_{1},z_{0},z_{1}),E_{2}(x_{1},x_{2},u_{1},z_{0},z_{1}),\operatorname{\mathsf{Det}}(x_{1},x_{2},u_{1},z_{0},z_{1}),P(x_{1},x_{2},u_{1},z_{0},z_{1}),$
$\displaystyle
E_{1}(x_{3},x_{4},u_{2},z_{0},z_{1}),E_{2}(x_{3},x_{4},u_{2},z_{0},z_{1}),\operatorname{\mathsf{Det}}(x_{3},x_{4},u_{2},z_{0},z_{1}),P(x_{3},x_{4},u_{2},z_{0},z_{1})\\}.$

Observe that $\operatorname{\mathcal{S}_{\mathsf{dup}}}$ is built from $8$
equations in the $8$ unknowns
$x_{1},x_{2},x_{3},x_{4},u_{1},u_{2},z_{0},z_{1}$ and the parameter $t$.

Assuming that we did not deform (27) using (7) (and thus that we did not
introduce any deformation parameter $\epsilon$), it follows by construction
that $\operatorname{\mathcal{S}_{\mathsf{dup}}}$ is defined in the polynomial
ring
$\mathbb{K}(t)[x_{1},\ldots,x_{n^{2}k},u_{1},\ldots,u_{nk},z_{0},\ldots,z_{nk-1}]$,
and is built from $nk(n+2)$ equations in $nk(n+2)$ unknowns ($t$ being
considered as a parameter). We introduce the polynomial
$\operatorname{sat}:=t\prod_{j=1}^{nk}(\prod_{i=1,i\neq
j}^{nk}(u_{i}-u_{j}))(u_{j}-a)\in\mathbb{K}(t)[u_{1},\ldots,u_{nk}]$ and
define the saturated ideal101010Recall that in practice, a generating set of
the ideal $\mathcal{I}_{\textsf{dup}}^{\infty}$ can be obtained by computing a
Gröbner basis of
$\langle\operatorname{\mathcal{S}_{\mathsf{dup}}},m\cdot\textsf{sat}-1\rangle\cap\mathbb{K}(t)[x_{1},\ldots,x_{n^{2}k},u_{1},\ldots,u_{nk},z_{0},\ldots,z_{nk-1}]$,
where $m$ is an extra variable introduced in order to remove the solution set
of the equation $\operatorname{sat}=0$.
$\mathcal{I}_{\textsf{dup}}^{\infty}:=\langle\operatorname{\mathcal{S}_{\mathsf{dup}}}\rangle:\operatorname{sat}^{\infty}$
in the ring
$\mathbb{K}(t)[x_{1},\ldots,x_{n^{2}k},u_{1},\ldots,u_{nk},z_{0},\ldots,z_{nk-1}]$.
In (4.1.1) below we shall assume that $\mathcal{I}_{\textsf{dup}}^{\infty}$
has expected dimension $0$ over $\mathbb{K}(t)$, without any multiplicity
points, and we also assume that there exist $nk$ distinct solutions to
$\operatorname{\mathsf{Det}}(u)=0$ in $u$, all of them lying in
$\overline{\mathbb{K}}[[t^{\frac{1}{\star}}]]\setminus\overline{\mathbb{K}}$.
All systems of DDEs that can be solved with the duplication approach satisfy
this assumption, up to removing the multiplicity points (which is harmless for
our objective of solving systems of DDEs).

$\displaystyle\underline{\text{Hypothesis}~{}\mathbf{1}:}$
$\displaystyle\bullet\;\operatorname{\mathsf{Det}}(u)=0\text{ admits }nk\text{
distinct solutions (in~{}$u$)}\text{ in
}\overline{\mathbb{K}}[[t^{\frac{1}{\star}}]]\setminus\overline{\mathbb{K}}.$
$\displaystyle\bullet\;\text{The
ideal~{}}\mathcal{I}_{\textsf{dup}}^{\infty}\text{ is radical of
dimension}~{}0\text{ over~{}}\mathbb{K}(t).$

Under (4.1.1), we denote by
$U_{1},\ldots,U_{nk}\in\overline{\mathbb{K}}[[t^{\frac{1}{\star}}]]\setminus\overline{\mathbb{K}}$
the distinct solutions to $\operatorname{\mathsf{Det}}(u)=0$.

Recall that after duplication of the variables $x_{1},\ldots,x_{n},u$ in the
initial set of polynomials
$(E_{1},\ldots,E_{n},\operatorname{\mathsf{Det}},P)$, we took the convention
in section 3 to have for all $1\leq i\leq n$, $1\leq j\leq nk$ and all
$0\leq\ell\leq k-1$, the correspondence “variables $\leftrightarrow$ values”
as follows:

$x_{(j-1)n+i}\leftrightarrow F_{i}(t,U_{j}(t))$, $u_{j}\leftrightarrow
U_{j}(t)$, $z_{(i-1)k+\ell}\leftrightarrow(\partial_{u}^{\ell}F_{i})(t,a)$.

It follows from the second part of (4.1.1) that the elimination ideal
$\mathcal{I}_{\textsf{dup}}^{\infty}\cap\mathbb{K}[t,z_{0}]$ is not reduced to
$\\{0\\}$. In spirit of [9, Proposition $2$] and [8, Proposition $2.1$], we
can show that any nonzero element of
$\mathcal{I}_{\textsf{dup}}^{\infty}\cap\mathbb{K}[t,z_{0}]$ annihilates the
series $F_{1}(t,a)$.

######  Lemma 11.

Under (4.1.1), any element
$R\in\mathcal{I}_{\textsf{dup}}^{\infty}\cap\mathbb{K}[t,z_{0}]\setminus\\{0\\}$
satisfies $R(t,F_{1}(t,a))=0$.

###### Proof.

Using $R\in\mathcal{I}_{\textsf{dup}}^{\infty}$ and the definition of the
saturation, it follows that there exists some $\ell\in\mathbb{N}$ such that
$R\cdot(\prod_{i\neq j}(u_{i}-u_{j})(u_{i}-a)t)^{\ell}$ can be written as a
sum of multiples of the duplicated polynomials obtained from
$E_{1},\ldots,E_{n},\operatorname{\mathsf{Det}},P$. Specializing the resulting
expression to the values $x_{(j-1)n+i}=F_{i}(t,U_{j}(t))$, $u_{j}=U_{j}(t)$,
$z_{(i-1)k+\ell}=(\partial_{u}^{\ell}F_{i})(t,a)$ and using (4.1.1) implies
that $U_{i}(t)\neq U_{j}(t)$ and $U_{i}(t)\neq a$ (whenever $i\neq j$). This
implies that $R(t,F_{1}(t,a))=~{}0$. ∎

######  Example 2 (cont.).

Consider $\operatorname{\mathcal{S}_{\mathsf{dup}}}$, and compute a nonzero
generator $R\in\mathbb{Q}[t,z_{0}]$ of
$\langle\operatorname{\mathcal{S}_{\mathsf{dup}}},m\cdot(u_{1}-u_{2})\cdot(u_{1}-1)\cdot(u_{2}-1)t-1\rangle\cap\mathbb{Q}[t,z_{0}]$.
For this computation, which is not easy to perform with a naive approach, we
rely on the recent work by the first author [21] which provides a Maple
package with efficient implementations of algorithms for solving DDEs: one of
these computes efficiently such an elimination polynomial. We obtain in a few
seconds on a regular laptop that

$\displaystyle R\;=\;$
$\displaystyle(64t^{3}z_{0}^{3}+2t(24t^{2}-36t+1)z_{0}^{2}+(-15t^{3}+9t^{2}+19t-1)z_{0}+t^{3}+27t^{2}-19t+1)$
$\displaystyle\cdot(z_{0}-1)\cdot(2tz_{0}+t-1)\cdot(36-60z_{0}+t\cdot\widetilde{R}(t,z_{0}))$

annihilates $F_{1}(t,1)$; here we write
$\widetilde{R}(t,z_{0})\in\mathbb{Q}[t,z_{0}]$ for an explicit but rather big
polynomial. Moreover, as $F_{1}=1+O(t)$ and $F_{1}$ is not a constant, we can
refine our conclusion and identify that the first factor of $R$ is the minimal
polynomial of $F_{1}(t,1)$.

####  4.1.2 Refined complexity and size estimates

We prove a version of 4 in the case where the symbolic deformation is not
needed. In this context, we provide an upper bound on the algebraicity degree
of $F_{1}(t,a)$ over $\mathbb{K}(t)$. Also, we estimate the arithmetic
complexity for the computation of a nonzero element of
$\mathcal{I}_{\textsf{dup}}^{\infty}\cap\mathbb{K}[t,z_{0}]$.

######  Proposition 12.

Let $\mathbb{K}$ be a field of characteristic $0$. Consider the system of DDEs
(27), assume that (4.1.1) holds and denote by $\delta$ an upper bound on the
total degrees of $f_{1},\ldots,f_{n},Q_{1},\ldots,Q_{n}$. Then the
algebraicity degree of $F_{1}(t,a)$ over $\mathbb{K}(t)$ is bounded by
$n^{2nk}(\delta(k+1)+1)^{nk(n+2)}/(nk)!$. Moreover when $\mathbb{K}$ is
effective, there exists an algorithm computing a nonzero polynomial
$R\in\mathbb{K}[t,z_{0}]$ such that $R(t,F_{1}(t,a))=0$, in
$\tilde{O}((nk\delta)^{5.26n(nk+k+1)})$ operations in $\mathbb{K}$.

###### Proof.

In spirit of the proof of 4:

  * •

Step 1: We compute an upper bound on the degree of the ideal
$\mathcal{I}_{\textsf{dup}}^{\infty}$ and then deduce an upper bound on the
algebraicity degree of $F_{1}(t,a)$.

  * •

Step 2: We make explicit the number of variables and parameters in
$\operatorname{\mathcal{S}_{\mathsf{dup}}}$.

  * •

Step 3: We describe and apply an algorithm which is itself based on the
algorithm of [24, Theorem $2$] in order to compute a nonzero annihilating
polynomial of $F_{1}(t,a)$.

  * •

Step 4: Finally, we use the arithmetic complexity of the algorithm on which
[24, Theorem $2$] relies in order to estimate the complexity of our algorithm.

In order to define the polynomials
$E_{1},\ldots,E_{n}\in\mathbb{K}(t)[x_{1},\ldots,x_{n},u,z_{0},\ldots,z_{nk-1}]$
associated to the numerator equations of (27), recall that it is necessary to
multiply the $i$th DDE in (27) by a power $m_{i}\in\mathbb{N}$ of $(u-a)$. The
polynomials $Q_{i}$ being of total degree upper-bounded by $\delta$, and the
DDEs considered being of order $k$, it results that each $m_{i}$ is upper-
bounded by $k\delta$. So each of the $E_{i}$’s has total degree upper-bounded
by $d:=\delta(k+1)+1$. Thus $\operatorname{\mathsf{Det}}$ and $P$ have their
respective total degrees bounded by $nd$ as determinants of $(n\times
n)$-matrices whose entries are polynomials of total degrees bounded by $d$. It
remains to see that because of the radicality assumption in (4.1.1), the
Heintz-Bézout theorem [20, Theorem $1$] applies and implies that the degree of
the ideal $\mathcal{I}_{\textsf{dup}}^{\infty}$ is bounded by the product of
the total degrees of the $nk(n+2)$ duplications
$E_{1}^{(1)},\ldots,E_{n}^{(1)},\operatorname{\mathsf{Det}}^{(1)},P^{(1)}$,
$\ldots,E_{1}^{(nk)},\ldots,E_{n}^{(nk)},\operatorname{\mathsf{Det}}^{(nk)},P^{(nk)}$.
Such a bound is given by $\gamma(n,k,\delta):=n^{2nk}d^{nk(n+2)}$. Similarly
to the proof of 4, there is a group action of the symmetric group
$\mathfrak{S}_{k}$ over the zero set of $\mathcal{I}_{\textsf{dup}}^{\infty}$
in $\overline{\mathbb{K}(t)}^{nk(n+2)}$, obtained by permuting the duplicated
blocks of coordinates, and which preserves the
$(z_{0},\ldots,z_{nk-1})$-coordinate space. This group action implies that the
algebraicity degree of $F_{1}(t,a)$ is upper-bounded by
$\gamma(n,k,\delta)/(nk)!=n^{2nk}(\delta(k+1)+1)^{nk(n+2)}/(nk)!$.

Recall that we have one parameter $t$, and $nk(n+2)$ variables for the
$x_{i}$’s, the $u_{i}$’s and the $z_{i}$’s. We will make explicit some
$R\in\mathbb{K}[t,z_{0}]\setminus\\{0\\}$ annihilating $F_{1}(t,a)$. To do so,
we first compute (here we use the second part of (4.1.1) again) two
polynomials $V,W\in\mathbb{K}[t,\lambda]$ such that: (i) $W$ is squarefree,
(ii) $\lambda$ is a new variable which is a $\mathbb{K}[t]$-linear combination
of the $nk(n+2)$ variables in Step $2$, (iii) for all the zeros
$\mathbf{\alpha}\in\overline{\mathbb{K}(t)}^{nk(n+2)}$ of
$\operatorname{\mathcal{S}_{\mathsf{dup}}}$ that are not solutions of
$\operatorname{sat}$, there exists
$\lambda_{0}\in\overline{\mathbb{K}(t,\epsilon)}$ solution in $\lambda$ of
$W(t,\lambda)=0$ such that
$V(t,\lambda_{0})/\partial_{\lambda}W(t,\lambda_{0})$ is the
$z_{0}$-coordinate of $\mathbf{\alpha}$. Using these polynomials, it is
straightforward to see by applying Stickelberger’s theorem [17, Theorem $1$],
using the radicality assumption in (4.1.1) and then applying 11 that the
squarefree part of the resultant of
$z_{0}\cdot\partial_{\lambda}W(t,\lambda)-V(t,\lambda)$ and $W(t,\lambda)$
with respect to $\lambda$ is a nonzero polynomial of $\mathbb{K}[t,z_{0}]$
annihilating the series $F_{1}(t,a)$.

It remains to estimate the complexity of Step $3$. Following the proof of 4,
the application of the algorithm underlying [24, Theorem $2$] allows us to
compute $V$ and $W$ in
$\tilde{O}((n^{2}kL+(n^{2}k)^{4})\gamma(n,k,\delta)^{2})$ operations in
$\mathbb{K}$, where $L$ is the length of a straight-line program which
evaluates the system $\mathcal{S}_{\textsf{dup}}$ and the polynomial
$\operatorname{sat}$. Since the cost for evaluating $E_{1},\ldots,E_{n}$ is
included in $O(d^{nk+n+2})$, then by the Baur-Strassen’s theorem [3, Theorem
$1$], the complexity of evaluating the polynomials
$\operatorname{\mathsf{Det}},P$ is included in $O(nd^{nk+n+2})$. Thus,
evaluating $E_{1},\ldots,E_{n},\operatorname{\mathsf{Det}},P$ has an
arithmetic cost which is in $O(n(\delta k)^{nk+n+2})$. As we considered $nk$
duplication of the polynomials
$(E_{1},\ldots,E_{n},\operatorname{\mathsf{Det}},P)$, we find $L\in
O(n^{3}kd^{nk+n+2})\subset O(n^{2}k(\delta k)^{nk+n+2})$. It remains to
compute the squarefree part $R\in\mathbb{K}[t,z_{0}]\setminus\\{0\\}$ of the
resultant of $z_{0}\cdot\partial_{\lambda}W(t,\lambda)-V(t,\lambda)$ and
$W(t,\lambda)$ with respect to $\lambda$. Note that under (4.1.1), the
quantity $\gamma(n,k,\delta)/(nk)!$ bounds the partial degrees of $R$. This
resultant computation can be done by applying evaluation-interpolation with
respect to $t$ with $O(n^{2nk}(\delta k)^{nk(n+2)}/(nk)!)$ points. For each
specialization at say $t=\theta\in\mathbb{K}$, we apply for instance [26] and
deduce that the bivariate resultant computation of
$z_{0}\cdot\partial_{\lambda}W(\theta,\lambda)-V(\theta,\lambda)$ and
$W(\theta,\lambda)$ with respect to $\lambda$ can be done in

$\tilde{O}(\gamma(n,k,\delta)^{2.63}/(nk)!^{2.63})\subset\tilde{O}(n^{5.26nk}(\delta
k)^{2.63nk(n+2)}/(nk)!^{2.63})$

operations in $\mathbb{K}$. Replacing $L$ and $\gamma(n,k,\delta)$ by their
values and summing up all arithmetic costs, one deduces that the arithmetic
cost for computing $R$ is included in $\tilde{O}((nk\delta)^{5.26n(nk+k+1)})$.
∎

######  Remark 13.

(i) Note that the complexity in 12 matches, as expected, the one that was
proven in [9, Proposition $4$] in the case $n=1$. One shall however see that
the total degree of $E_{1}$ is considered in [9, Proposition $4$], whereas
here we considered the total degree of $Q_{1}$ and $f_{1}$. Passing from the
complexity in 12 to the one in [9, Proposition $4$] is done by replacing
$\delta$ by $\delta/k$.

(ii) It follows from the inclusion
$\tilde{O}((nk\delta)^{5.26n(nk+k+1)})\subset\tilde{O}((nk\delta)^{40(n^{2}k+1)})$
that the arithmetic complexity stated in 12 refines the arithmetic complexity
stated in 4.

As shown in section 2 and section 4.1, a natural way of solving (27) is to
compute a nonzero element
$R\in\mathcal{I}_{\textsf{dup}}^{\infty}\cap\mathbb{K}[t,z_{0}]$. However, as
already pointed out in [9, Section $3$] in the case $n=1$, this process of
duplicating variables yields an exponential growth of the degree of the ideal
$\mathcal{I}_{\textsf{dup}}^{\infty}$ with respect to the number $nk$ of
duplications [20, Proposition $2$]. It is known that the degree of the ideal
generated by the polynomials in a given polynomial system is one of the main
parameters controlling the complexity of solving the system (see, for example,
[2] for a complexity analysis of Faugère’s $F_{5}$ algorithm in the context of
homogeneous polynomials). Thus, if one can avoid the strategy of variable
duplication one can potentially significantly reduce the exponent
$5.26n(nk+k+1)$ in the arithmetic complexity result of 12.

###  4.2 Reducing the system of DDEs to a single functional equation

####  4.2.1 Main strategy

In this subsection we elaborate on a strategy for solving systems of DDEs that
avoids duplication of variables: it reduces the initial system to a single
functional equation by eliminating the bivariate series $F_{2},\ldots,F_{n}$
from the system $(E_{1}(u)=0,\ldots,E_{n}(u)=0)$. In a favourable situation,
this reduction outputs a nonzero polynomial
$E\in\mathbb{K}(t)[x_{1},u,z_{0},\ldots,z_{nk}]$ such that

$E(u)\equiv
E(F_{1}(t,u),u,F_{1}(t,a),\ldots,(\partial_{u}^{k-1}F_{1})(t,a),\ldots,F_{n}(t,a),\ldots,(\partial_{u}^{k-1}F_{n})(t,a))=0.$

The following lemma ensures that this strategy works under the following
assumption: the saturated ideal $\langle
E_{1},\ldots,E_{n}\rangle:\operatorname{\mathsf{Det}}^{\infty}\cap\mathbb{K}(t)[x_{1},u,z_{0},\ldots,z_{nk-1}]$,
denoted by $\mathcal{J}$, is principal111111Recall that an ideal is called
principal if it is generated by only one element. – this natural assumption is
observable on all examples of systems of DDEs we encountered so far.

######  Lemma 14.

Consider (5) and denote
$E_{1},\ldots,E_{n}\in\mathbb{K}(t)[x_{1},\ldots,x_{n},u,z_{0},\ldots,z_{nk-1}]$
the polynomials obtained after taking the numerators of (5). Assume that the
ideal $\mathcal{J}$ is principal, generated by some
$E\in\mathbb{K}(t)[x_{1},u,z_{0},\ldots,z_{nk-1}]$. Then $E\neq 0$ and
$E(u)=0.$

###### Proof.

It results from the product of the diagonal elements in the matrix defining
$\operatorname{\mathsf{Det}}$ that $\operatorname{\mathsf{Det}}\neq 0\mod t$.
Also, the evaluation $\operatorname{\mathsf{Det}}(u)\in\mathbb{K}[[t]][[u]]$
is not equal to $0$ (recall that $\operatorname{\mathsf{Det}}(u)$ is the
specialization of $\operatorname{\mathsf{Det}}$ to the series $F_{i}(t,u)$ and
$(\partial_{u}^{\ell}F_{i})(t,a)$). It follows from the Jacobian criterion
that the ideal $\langle
E_{1},\ldots,E_{n}\rangle:\operatorname{\mathsf{Det}}^{\infty}$ is radical and
of dimension at most $0$ over $\mathbb{K}(t,z_{0},\ldots,z_{nk-1})$. Thus
$E\neq 0$. Moreover, as $E_{1}(u)=0,\ldots,E_{n}(u)=0$ and
$\operatorname{\mathsf{Det}}(u)\neq 0$, it follows $E(u)=0$. ∎

######  Example 2 (cont.).

We compute a Gröbner basis of $\langle
E_{1},E_{2},m\cdot\operatorname{\mathsf{Det}}-1\rangle\cap\mathbb{K}(t)[x_{1},u,z_{0},z_{1}]$
and observe that it is not reduced to $\\{0\\}$. Moreover, it is generated by
a unique element

$E:=-(x_{1}-1)(u-1)+tu(2ux_{1}^{2}-uz_{0}-2x_{1}^{2}+u+x_{1}-1)\in\mathbb{K}(t)[x_{1},u,z_{0},z_{1}].$

For the remaining part of section 4.2 we assume, as in 14, that the ideal
$\mathcal{J}$ is principal. Thus the polynomial $E$ obtained after eliminating
$x_{2},\ldots,x_{n}$ satisfies $E\neq 0$ and $E(u)~{}=~{}0$.

A natural idea now is to use Bousquet-Mélou and Jehanne’s method [10, Section
$2$]. This reduces our problem either to solving a polynomial system with now
$3nk+1$ unknowns and equations (where again the $+1$ comes from the saturation
polynomial $\operatorname{sat}$), or to applying the more recent algorithm
from [9, Section $5$]. Note that this method is not guaranteed to work in
general because the functional equation given by $E(u)=0$ may not be of a
fixed point type for $F_{1}$. As we will see, in order to make these
approaches work, one can require the following condition:

$\displaystyle\underline{\text{Hypothesis~{}$\mathbf{2}$:}}$
$\displaystyle\bullet\;\text{$\partial_{x_{1}}E(u)=0$ admits $nk$ distinct
solutions (in~{}$u$) in
$\overline{\mathbb{K}}[[t^{\frac{1}{\star}}]]\setminus\overline{\mathbb{K}}$,}$
(H2) $\displaystyle\bullet\;\text{The polynomial system obtained after
duplicating $nk$ times}$ the variables $x_{1},u$ in
$(E,\partial_{x_{1}}E,\partial_{u}E)$ and adding $\operatorname{sat}=0$
induces an ideal of dimension $0$ over $\mathbb{K}(t)$.

We emphasize that we are not aware of any system of DDEs inducing some $E$
that is not of a fixed-point type in $F_{1}$: when the system is generic (that
is, for generic choices of $f_{i}$’s and $Q_{i}$’s) we could observe by
generating lots of examples that this fixed-point nature is indeed satisfied.

This resolution strategy being different from the duplication of variables
approach from section 4.1, we investigate below how their outputs compare.

####  4.2.2 Theoretical comparison with the strategy from section 4.1

The following proposition ensures that the first part of (4.1.1) implies the
first part of (H2). Recall that $\mathcal{J}\coloneqq\langle
E_{1},\ldots,E_{n}\rangle:\operatorname{\mathsf{Det}}^{\infty}\cap\mathbb{K}(t)[x_{1},u,z_{0},\ldots,z_{nk-1}]$.

######  Proposition 15.

Let $U(t)\in\overline{\mathbb{K}}[[t^{\frac{1}{\star}}]]$ be a solution of
$\operatorname{\mathsf{Det}}(u)=0$ such that none of the $(n-1)\times(n-1)$
minors of $(\partial_{x_{j}}E_{i}(U(t)))_{1\leq i,j\leq n}$ is zero. Consider
$E\in\mathcal{J}$. Then $U(t)$ is also a solution in $u$ of the equation
$\partial_{x_{1}}E(u)=0$.

###### Proof.

Since $E\in\mathcal{J}$, there exist polynomials
$V_{1},\dots,V_{n}\in\mathbb{K}(t)[x_{1},\dots,x_{n},u,z_{0},\ldots,z_{nk-1}]$
such that $E(U)=\sum_{i=1}^{n}E_{i}(U)V_{i}(U)$. Differentiating with respect
to $x_{j}$ for $j=1,\dots,n$ and using that $E_{i}(U)=0$ and that $E$ does not
depend on $x_{j}$ for $j\geq 2$, we find

$\begin{pmatrix}\partial_{x_{1}}E(U)\\\ 0\\\ \vdots\\\
0\end{pmatrix}=\begin{pmatrix}\partial_{x_{1}}E_{1}(U)&\dots&\partial_{x_{1}}E_{n}(U)\\\
\vdots&\ddots&\vdots\\\
\partial_{x_{n}}E_{1}(U)&\dots&\partial_{x_{n}}E_{n}(U)\end{pmatrix}\begin{pmatrix}V_{1}(U)\\\
\vdots\\\ V_{n}(U)\end{pmatrix}.$ (28)

By definition of $U$, the matrix $(\partial_{x_{j}}E_{i}(U))_{i,j}$ is
singular and each of its $(n-1)\times(n-1)$ minors is nonzero. It follows that
we can express the first row of the matrix as a linear combination of the
other rows, then (28) implies that $\partial_{x_{1}}E(U)=0$. ∎

It remains to understand the second part of (H2). We reuse the notations from
the proof of 15 by writing $E=\sum_{i=1}^{n}{E_{i}\cdot V_{i}}$ for $E$ a
generator of $\mathcal{J}$ and for $V_{1},\ldots,V_{n}$ polynomials in
$\mathbb{K}(t)[x_{1},\dots,x_{n},u,z_{0},\ldots,z_{nk-1}]$. Also, we define
the new geometric assumption (P):

$\displaystyle\underline{\text{Hypothesis}~{}\mathbf{(P)}:}$ Every point
$\mathbf{\beta}\in\overline{\mathbb{K}(t)}^{nk+2}$ vanishing $E$ is the
projection onto (P) the $\\{x_{1},u,z_{0},\ldots,z_{nk-1}\\}$-coordinate space
of a point $\alpha\in\overline{\mathbb{K}(t)}^{nk+n+1}$ vanishing
simultaneously $E_{1},\ldots,E_{n-1}$ and $E_{n}$.

Observe that the zero set of $E$ in $\overline{\mathbb{K}(t)}^{nk+2}$ is, by
the closure theorem [18, Theorem $3$, Chap $3.2$], the Zariski closure in
$\overline{\mathbb{K}(t)}^{nk+2}$ of the projection of the solution set in
$\overline{\mathbb{K}(t)}^{nk+n+1}$ of $\langle
E_{1},\ldots,E_{n}\rangle:\operatorname{\mathsf{Det}}^{\infty}$ onto the
$\\{x_{1},u,z_{0},\ldots,z_{nk-1}\\}$-coordinate space. Assumption (P)
formulates that the boundary of the projection belongs to the projection
itself.

From now on we will denote by $\underline{x}$ (resp. $\underline{z}$) the
variables $x_{1},\ldots,x_{n}$ (resp. $z_{0},\ldots,z_{nk-1}$).

######  Remark 16.

Once a Gröbner basis $G$ of the ideal $\langle
E_{1},\ldots,E_{n}\rangle:\operatorname{\mathsf{Det}}^{\infty}$ is computed
for the block order
$\\{x_{2},\ldots,x_{n}\\}\succ_{lex}\\{x_{1},u,\underline{z}\\}$, the set of
points $\beta$ in (P) can be characterized by the extension theorem [18,
Theorem 3, Chap 3.1] as the solutions of explicit polynomial equations and
inequations built from $G$: namely $\beta$ are those solutions of
$G\cap\mathbb{K}(t)[x_{1},u,\underline{z}]$ that do not vanish simultaneously
all the leading terms of
$G\setminus(G\cap\mathbb{K}(t)[x_{1},u,\underline{z}])$ for the degrevlex
monomial order $\\{x_{2},\ldots,x_{n}\\}$ (the variables
$t,x_{1},u,\underline{z}$ shall be seen as parameters once $G$ is computed).
These leading coefficients are thus polynomials of
$\mathbb{K}(t)[x_{1},u,\underline{z}]$.

We formulate the below statement, whose purpose is to interpret geometrically
the link between the algebraic sets
$V(E,\partial_{x_{1}}E,\partial_{u}E)\subset\overline{\mathbb{K}(t)}^{nk+2}$
and
$V(E_{1},\ldots,E_{n},\operatorname{\mathsf{Det}},P)\subset\overline{\mathbb{K}(t)}^{nk+n+1}$.

######  Proposition 17.

Assume that $\mathcal{J}$ is principal and radical. Let
$E\in\mathbb{K}(t)[x_{1},u,z_{0},\ldots,z_{nk-1}]$ be its generator. Assume,
moreover, that (P) holds and denote by
$\pi_{x_{1},u,\underline{z}}:(\underline{x},u,\underline{z})\in\overline{\mathbb{K}(t)}^{nk+n+1}\mapsto(x_{1},u,\underline{z})\in\overline{\mathbb{K}(t)}^{nk+2}$
the canonical projection onto the $(x_{1},u,\underline{z})$-coordinate space.
Then we have the inclusion
$V(E,\partial_{x_{1}}E,\partial_{u}E)\subset\pi_{x_{1},u,\underline{z}}(V(E_{1},\ldots,E_{n},\operatorname{\mathsf{Det}},P))$.

###### Proof.

Writing $E=\sum_{i=1}^{n}E_{i}\cdot V_{i}$ for some
$V_{1},\ldots,V_{n}\in\mathbb{K}(t)[\underline{x},u,\underline{z}]$ and
considering the derivatives $\partial_{x_{i}}E$ for $i=1,\ldots,n$, we find by
the Leibniz rule

$\begin{pmatrix}\partial_{x_{1}}E\\\ 0\\\ \vdots\\\
0\end{pmatrix}=\begin{pmatrix}\partial_{x_{1}}E_{1}&\dots&\partial_{x_{1}}E_{n}\\\
\vdots&\ddots&\vdots\\\
\partial_{x_{n}}E_{1}&\dots&\partial_{x_{n}}E_{n}\end{pmatrix}\begin{pmatrix}V_{1}\\\
\vdots\\\
V_{n}\end{pmatrix}+\begin{pmatrix}\partial_{x_{1}}V_{1}&\dots&\partial_{x_{1}}V_{n}\\\
\vdots&\ddots&\vdots\\\
\partial_{x_{n}}V_{1}&\dots&\partial_{x_{n}}V_{n}\end{pmatrix}\begin{pmatrix}E_{1}\\\
\vdots\\\ E_{n}\end{pmatrix}.$ (29)

Now for any $\beta\in V(E,\partial_{x_{1}}E)$ and for all
$\alpha\in\pi_{x_{1},u,\underline{z}}^{-1}(\beta)\cap V(E_{1},\ldots,E_{n})$,
we obtain that

$\begin{pmatrix}0\\\ \vdots\\\
0\end{pmatrix}=\begin{pmatrix}\partial_{x_{1}}E_{1}(\alpha)&\dots&\partial_{x_{1}}E_{n}(\alpha)\\\
\vdots&\ddots&\vdots\\\
\partial_{x_{n}}E_{1}(\alpha)&\dots&\partial_{x_{n}}E_{n}(\alpha)\end{pmatrix}\begin{pmatrix}V_{1}(\alpha)\\\
\vdots\\\ V_{n}(\alpha)\end{pmatrix}.$

Thus it suffices to prove that $V_{i}(\alpha)\neq 0$ (for some
$i\in\\{1,\ldots,n\\}$) in order to to see that
$\operatorname{\mathsf{Det}}(\alpha)=0$. As $E$ generates the radical ideal
$\mathcal{J}$, we know that $E$ is squarefree. Hence the algebraic set
$V(E)\in\overline{\mathbb{K}(t)}^{nk+2}$ is smooth, hence the vector of
partial derivatives of $E$ w.r.t the variables $x_{1},u,z_{0},\ldots,z_{nk-1}$
does not vanish identically at $\beta$. As $E=\sum_{i=1}^{n}E_{i}\cdot V_{i}$,
this enforces one of the $V_{i}$ to be nonzero at $\alpha$: else by writing
all the partial derivatives of $E$ with the Leibniz rule applied to the sum
expression $E=\sum_{i=1}^{n}E_{i}\cdot V_{i}$ and using $\alpha\in
V(E_{1},\ldots,E_{n},V_{1},\ldots,V_{n})$ would imply that the vector of
partial derivatives of $E$ with respect to $x_{1},u,z_{0},\ldots,z_{nk-1}$
vanishes identically at $\beta$.

Now consider the vector of derivatives
$(\partial_{u}E,\partial_{x_{2}}E,\ldots,\partial_{x_{n}}E)$ and write it in
the form (29). This allows to reuse the above argument to show that
$P(\alpha)=0$, for any $\alpha\in\overline{\mathbb{K}(t)}^{nk+n+1}$ vanishing
simultaneously $\partial_{u}E,E_{1},\ldots,E_{n}$. It follows that under
assumption (P), we have the claimed inclusion
$V(E,\partial_{x_{1}}E,\partial_{u}E)\subset\pi_{x_{1},u,\underline{z}}(V(E_{1},\ldots,E_{n},\operatorname{\mathsf{Det}},P))$.
∎

Let us mention that under the technical assumptions introduced in 15 and 17:
if $\operatorname{\mathsf{Det}}(u)=0$ admits $\ell$ distinct solutions (in
$u$) in $\overline{\mathbb{K}}[[t^{\frac{1}{\star}}]]$ then so does
$\partial_{x_{1}}E(u)=0$.

Moreover still under the assumptions of 15 and 17, if the ideal
$\mathcal{I}_{\textsf{dup}}^{\infty}$ of section 4.1.1 has dimension $0$ over
$\mathbb{K}(t)$, then the aplication of [9, Section $5$] to the functional
equation $E(u)=0$ outputs a nonzero polynomial $R\in\mathbb{K}[t,z_{0}]$ such
that $R(t,F_{1}(t,a))=0$.

We gather below assumptions that we will use after. Also for any multivariate
polynomial $p$, we denote by $\operatorname{SqFreePart}(p)$ the squarefree
part of $p$.

$\displaystyle\underline{\text{Hypothesis $3$:}}$
$\displaystyle\bullet\text{\eqref{hyp1} and~{}\eqref{hypP} hold},$ (H3)
$\displaystyle\bullet\text{The ideal~{}$\mathcal{J}$ is radical and
principal},$ $\displaystyle\bullet\text{For
all~{}$U(t)\in\overline{\mathbb{K}}[[t^{\frac{1}{\star}}]]$ solution
of~{}$\operatorname{\mathsf{Det}}(u)=0$, the~{}$(n-1)\times(n-1)$ minors}$ of
$(\partial_{x_{j}}E_{i}(U(t)))_{1\leq i,j\leq n}$ are nonzero.

######  Proposition 18.

Assume that (H3) holds. Denote $R_{1}\in\mathbb{K}[t,z_{0}]$ a generator of
$\mathcal{I}_{\textsf{dup}}^{\infty}\cap\mathbb{K}[t,z_{0}]$ and
$R_{2}\in\mathbb{K}[t,z_{0}]$ the polynomial computed by the duplication
approach121212This duplication approach should in practice be replaced by the
more efficient algorithm from [9, Section $5$]. applied to the functional
equation $E(u)~{}=~{}0$. Then $\operatorname{SqFreePart}(R_{2})$ divides
$\operatorname{SqFreePart}(R_{1})$.

###### Proof.

The statement is a direct consequence of 15 and 17. ∎

In this section, so far, we compared two different strategies based for the
first one on a duplication of variables argument, and for the second one on
the reduction to a single equation. We showed that up to considering
squarefree parts, the output polynomial of the second strategy divides, under
technical assumptions, the output polynomial of the first strategy.

Even if we strongly believe that the introduced assumptions are reasonable for
practical considerations, we shall however underline that the literature
contains some degenerate examples that go against this believe. The following
example illustrates this degeneracy and thus strengthen the relevancy of the
strategy from section 4.1, even if the arithmetic complexity in 12 can seem
despairing.

######  Example 2 (cont.).

In this case 15 cannot be applied, since

$\displaystyle\operatorname{\mathsf{Det}}=\det\begin{pmatrix}4tu^{2}x_{1}-4tux_{1}+tu-u+1&0\\\
\star&2tu^{2}x_{1}-2tux_{1}+tu-u+1\end{pmatrix},$

so any of the two distinct solutions
$U_{1},U_{2}\in\overline{\mathbb{K}}[[t^{\frac{1}{\star}}]]$ to the equation
$\operatorname{\mathsf{Det}}(u)=0$ annihilates at least two coefficients of
the matrix $(\partial_{x_{j}}E_{i})_{1\leq i,j\leq 2}$. Moreover, it is
straightforward to see that for the polynomial
$E=-(x_{1}-1)(u-1)+tu(2ux_{1}^{2}-uz_{0}-2x_{1}^{2}+u+x_{1}-1)\in\mathbb{K}(t)[x_{1},u,z_{0},z_{1}]$
the equation $\partial_{x_{1}}E(u)=0$ has only one solution (in $u$) in the
ring $\overline{\mathbb{K}}[[t^{\frac{1}{\star}}]]$ while $E(u)=0$ involves
two univariate series $F_{1}(t,1)$ and $F_{2}(t,1)$. Thus, on this example,
the strategy described in the current section fails.

##  5 Conclusion and future works

We proved in 3 that solutions of systems of discrete differential equations
are algebraic functions. The proof uses the observation that, up to a symbolic
deformation pushing all degeneracy of a given system of the form (5) to some
higher powers of $t$, all the computations become explicit. In addition, we
obtained in 4 quantitative estimates for the size of an annihilating
polynomial for any solution $F_{i}$, together with arithmetic complexity
estimates.

We also refined the complexity estimate in 12 and also obtained an
algebraicity bound for all the $F_{i}(t,a)$. Moreover, we started an
algorithmic analysis of the problem of solving systems of DDEs. In this first
work we compared two natural strategies for solving systems of DDEs. We
identified rigorous assumptions ensuring their applicability illustrating them
on the Example 2, where the reduction to a single equation fails, while the
duplication approach works. Under these assumptions, the outputs of these two
strategies are linked via 18.

Our paper contains several research directions which we plan to investigate in
the future:

##### Algorithmic part

This article set the foundations of an algorithmic work that must be conducted
in order to understand better the many subtle and degenerate situations that
one can encounter with systems of DDEs from the literature. For instance, the
following points should be addressed:

  * •

Validity of the assumptions: It seems clear that up to deforming symbolically
as in (7), assumption (4.1.1) can be assumed to hold. Still, we do not know at
this stage if (P) holds once (5) is deformed as in (7). Also, we would like to
have results saying that the all introduced assumptions hold for generic
choices of system of DDEs.

  * •

New algorithms for solving systems of DDEs: In [9, Section $5$] an algorithm
was designed that computes in case of scalar DDEs the same output as the
algorithm described in section 4.1 and that avoids the duplication of
variables. This strategy can be naturally extended to the context of systems
of DDEs. Once this is done, a first task would be to compare this new strategy
with the ones described in section 4.2. Also, the case of systems of linear
DDEs contains many applications in which it is possible to use the linearity
in order to speed up the computations. All this should be clarified and
studied in depth.

##### Theoretical part:

In the case of more than one catalytic variables, the algebraicity of the
solutions remains guaranteed by Popescu’s theorem [23] under the additional
assumption that the variables are “nested”. It would be interesting to reprove
this result with elementary tools in the case of fixed-point equations and to
introduce new algorithms for solving these equations.

##### Acknowledgments

We would like to thank Mohab Safey El Din for many interesting discussions and
Alin Bostan for his great support and valuable comments on an early version of
this manuscript. We are also grateful to Mireille Bousquet-Mélou for exciting
and enlightening discussions, and to Eva-Maria Hainzl and Wenjie Fang for
pointing out to us the existence of the periodic Tamari intervals and their
associated systems of DDEs. Also, we are grateful to Mathilde Bouvel and
Nicholas Beaton for pointing us applications of our paper to [4].

Both authors were supported by the ANR-19-CE40-0018 De Rerum Natura project
and the French–Austrian ANR-22-CE91-0007 & FWF I6130-N project EAGLES; the
second author was funded by the DOC fellowship P-26101 of the ÖAW, the WTZ
collaboration project FR-09/2021 and the project P34765 of the  Austrian
science fund FWF.

## References

  * [1] Andrei Asinowski, Axel Bacher, Cyril Banderier and Bernhard Gittenberger  “Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata”  In _Algorithmica_ 82.3, 2020, pp. 386–428  DOI: 10.1007/s00453-019-00623-3
  * [2] Magali Bardet, Jean-Charles Faugère and Bruno Salvy  “On the complexity of the $F_{5}$ Gröbner basis algorithm”  In _J. Symbolic Comput._ 70, 2015, pp. 49–70  DOI: 10.1016/j.jsc.2014.09.025
  * [3] Walter Baur and Volker Strassen  “The complexity of partial derivatives”  In _Theoret. Comput. Sci._ 22.3, 1983, pp. 317–330  DOI: 10.1016/0304-3975(83)90110-X
  * [4] Nicholas R. Beaton, Mathilde Bouvel, Veronica Guerrini and Simone Rinaldi  “Slicing of parallelogram polyominoes: Catalan, Schröder, Baxter, and other sequences”  In _Electron. J. Combin._ 26.3, 2019, pp. Paper No. 3.1336  DOI: 10.37236/7375
  * [5] Olivier Bernardi and Mireille Bousquet-Mélou  “Counting colored planar maps: algebraicity results”  In _J. Combin. Theory Ser. B_ 101.5, 2011, pp. 315–377  DOI: 10.1016/j.jctb.2011.02.003
  * [6] Jérémy Berthomieu, Christian Eder and Mohab Safey El Din  “msolve: A Library for Solving Polynomial Systems”  In _2021 International Symposium on Symbolic and Algebraic Computation_ , ISSAC ’21  Saint Petersburg, Russia: ACM, 2021, pp. 51–58  DOI: 10.1145/3452143.3465545
  * [7] Nicolas Bonichon, Mireille Bousquet-Mélou, Paul Dorbec and Claire Pennarun  “On the number of planar Eulerian orientations”  In _European J. Combin._ 65, 2017, pp. 59–91  DOI: 10.1016/j.ejc.2017.04.009
  * [8] Alin Bostan, Frédéric Chyzak, Hadrien Notarantonio and Mohab Safey El Din  “Algorithms for Discrete Differential Equations of Order 1”  In _Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation_ , ISSAC ’22  Villeneuve-d’Ascq, France: ACM, 2022, pp. 101–110
  * [9] Alin Bostan, Hadrien Notarantonio and Mohab Safey El Din  “Fast algorithms for discrete differential equations”  In _Proceedings of the International Symposium on Symbolic & Algebraic Computation (ISSAC 2023)_ ACM, New York, [2023] ©2023, pp. 80–89  DOI: 10.1145/3597066.3597103
  * [10] Mireille Bousquet-Mélou and Arnaud Jehanne  “Polynomial equations with one catalytic variable, algebraic series and map enumeration”  In _J. Combin. Theory Ser. B_ 96.5, 2006, pp. 623–672
  * [11] E. Brézin, C. Itzykson, G. Parisi and J.. Zuber  “Planar diagrams”  In _Comm. Math. Phys._ 59.1, 1978, pp. 35–51  URL: http://projecteuclid.org/euclid.cmp/1103901558
  * [12] W.. Brown and W.. Tutte  “On the Enumeration of Rooted Non-Separable Planar Maps”  In _Canadian J. of Mathematics_ 16 Cambridge University Press, 1964, pp. 572–577  DOI: 10.4153/CJM-1964-058-7
  * [13] William G. Brown  “Enumeration of quadrangular dissections of the disk”  In _Canadian J. Math._ 17, 1965, pp. 302–317  DOI: 10.4153/CJM-1965-030-1
  * [14] William G. Brown  “On the existence of square roots in certain rings of power series”  In _Math. Ann._ 158, 1965, pp. 82–89  DOI: 10.1007/BF01370732
  * [15] Manfred Buchacher and Manuel Kauers  “Inhomogeneous restricted lattice walks”  In _Sém. Lothar. Combin._ 82B, 2020, pp. Art. 7512
  * [16] Luca Castelli Aleardi, Olivier Devillers and Gilles Schaeffer  “Optimal succinct representations of planar maps”  In _Computational geometry (SCG’06)_ ACM, New York, 2006, pp. 309–318  DOI: 10.1145/1137856.1137902
  * [17] David A. Cox  “Stickelberger and the eigenvalue theorem”  In _Commutative algebra_ Springer, Cham, [2021] ©2021, pp. 283–298  DOI: 10.1007/978-3-030-89694-28
  * [18] David A. Cox, John Little and Donal O’Shea  “Ideals, varieties, and algorithms” An introduction to computational algebraic geometry and commutative algebra, Undergraduate Texts in Mathematics  Springer, Cham, 2015, pp. xvi+646  DOI: 10.1007/978-3-319-16721-3
  * [19] David Eisenbud  “Commutative algebra” With a view toward algebraic geometry 150, Graduate Texts in Mathematics  Springer-Verlag, New York, 1995, pp. xvi+785
  * [20] Joos Heintz  “Definability and fast quantifier elimination in algebraically closed fields”  In _Theoret. Comput. Sci._ 24.3, 1983, pp. 239–277  DOI: 10.1016/0304-3975(83)90002-6
  * [21] Hadrien Notarantonio  “DDE-Solver: A Maple package for Discrete Differential Equations” Preprint
  * [22] Hadrien Notarantonio and Sergey Yurkevich  “Effective algebraicity for solutions of systems of functional equations with one catalytic variable”, In FPSAC’23, to appear (2023)
  * [23] Dorin Popescu  “General Néron desingularization and approximation”  In _Nagoya Math. J._ 104, 1986, pp. 85–115  DOI: 10.1017/S0027763000022698
  * [24] Éric Schost  “Computing parametric geometric resolutions”  In _Appl. Algebra Engrg. Comm. Comput._ 13.5, 2003, pp. 349–393  DOI: 10.1007/s00200-002-0109-x
  * [25] W.. Tutte  “A Census of Planar Triangulations”  In _Canadian J. Math._ 14 Cambridge University Press, 1962, pp. 21–38  DOI: 10.4153/CJM-1962-002-9
  * [26] Gilles Villard  “On computing the resultant of generic bivariate polynomials”  In _ISSAC’18—Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation_ ACM, New York, 2018, pp. 391–398  DOI: 10.1145/3208976.3209020
  * [27] Doron Zeilberger  “The umbral transfer-matrix method. I. Foundations” In memory of Gian-Carlo Rota  In _J. Combin. Theory Ser. A_ 91.1-2, 2000, pp. 451–463  DOI: 10.1006/jcta.2000.3110