Algorithms yield upper bounds
in differential algebra

Wei Li KLMM, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, No.55 Zhongguancun East Road, 100190, Beijing, China [email protected] , Alexey Ovchinnikov CUNY Queens College, Department of Mathematics, 65-30 Kissena Blvd, Queens, NY 11367, USA and CUNY Graduate Center, Mathematics and Computer Science, 365 Fifth Avenue, New York, NY 10016, USA [email protected] , Gleb Pogudin LIX, CNRS, École Polytechnique, Institut Polytechnique de Paris, 1 rue Honoré d’Estienne d’Orves, 91120, Palaiseau, France and National Research University Higher School of Economics, Moscow, Russia [email protected] and Thomas Scanlon University of California, Berkeley, Department of Mathematics, Berkeley, CA 94720-3840, USA [email protected]

Abstract.

Consider an algorithm computing in a differential field with several commuting derivations such that the only operations it performs with the elements of the field are arithmetic operations, differentiation, and zero testing. We show that, if the algorithm is guaranteed to terminate on every input, then there is a computable upper bound for the size of the output of the algorithm in terms of the size of the input. We also generalize this to algorithms working with models of good enough theories (including for example, difference fields).

We then apply this to differential algebraic geometry to show that there exists a computable uniform upper bound for the number of components of any variety defined by a system of polynomial PDEs. We then use this bound to show the existence of a computable uniform upper bound for the elimination problem in systems of polynomial PDEs with delays.

2010 Mathematics Subject Classification:

Primary 12H05, 12H10, 03C10; Secondary 03C60, 03D15

1. Introduction

Finding uniform bounds for problems and quantities (e.g., consistency testing or counting of solutions) is one of the central questions in differential algebra. In [27], it was demonstrated that, in commutative algebra, one can show the existence of such bounds as a consequence of theorems about nonstandard extensions of standard algebraic objects. This approach was successfully applied in the differential algebra context in [11] and [8, Section 6] for establishing, for example, the existence of a uniform bound in the differential Nullstellensatz. Furthermore, in [26], the authors used methods of proof theory to extract explicit bounds based on nonstandard existence proofs.

The present paper can be viewed as an alternative approach, in which we derive the existence of a computable uniform bound for an object from the existence of an algorithm for computing the object. More precisely, let $T$ be a complete decidable theory. The most relevant examples for us would be the theory of differentially closed fields in zero characteristic with $m$ commuting derivations and the theory of existentially closed difference fields, others include algebraically closed and real closed fields. Consider an algorithm $A$ performing computations in a model of $T$ that is restricted to using only definable functions when working with elements of the model (for formal definition, we refer to Section 4.1) and required to terminate for every input.

We show that there is a computable upper bound for the size of the output of $A$ in terms of the input size of $A$ . We apply this to the Rosenfeld-Gröbner algorithm [3] that decomposes a solution set of a system of polynomial PDEs into components and is such an algorithm. This allows us to show that there is a uniform upper bound for the number of components of any differential-algebraic variety defined by a system of polynomial PDEs. We also show how this bound for the number of components leads to a uniform upper bound for the elimination problem in systems of polynomial PDEs with delays.

A bound for the number of components of varieties defined by polynomial ODEs appeared in [18], as did a bound for the elimination problem for polynomial ODEs with delays. These bounds are based on the application of the Rosenfeld-Gröbner algorithm, which, if applied in this situation to ODEs, outputs equations whose order does not exceed the order of the input. This allowed to restrict to a finitely generated subring of the ring of differential polynomials and use tools from algebraic geometry. It is non-trivial to generalize this to polynomial PDEs because the orders in the output of the Rosenfeld-Gröbner can be greater than the orders of the input. Another key ingredient in the ODE case to obtain the bound in [18] was an analysis of differential dimension polynomials. A significant difference of our present PDE context with the ordinary case that these polynomials behave less predictably under projections of varieties (compare [18, Lemma 6.16] and Lemma 6.6). To overcome this difficulty, we use again our bound for the Rosenfeld-Gröbner algorithm.

We believe that our method can also be applied to obtain bounds for other algorithms in differential algebra such as [1, Algorithm 3.6] and for algorithms from other theories, e.g. [7, Algorithm 3] for systems of difference equations. Since the reducibility of a polynomial can be expressed as a first-order existential formula, it seems plausible that the same methods could be applied to other algorithms dealing with difference [5] and differential-difference [6] equations that use factorization because the corresponding theories satisfy the requirements of our approach [14, 16, 23]. However, we leave these for future research.

The paper is organized as follows. Section 2 contains definitions and notation used in Section 3 to state the main results. Bounds for an algorithm working with a model of a theory $T$ are established in Section 4. These results are applied to differential algebra in Section 5. Further applications to delay PDEs are given in Section 6.

2. Basic notions and notaiton

Definition 2.1 (Differential-difference rings).

•

A $\Delta$ - $\sigma$ -ring $(\mathcal{R},\Delta,\sigma)$ is a commutative ring $\mathcal{R}$ endowed with a finite set $\Delta=\{\partial_{1},\ldots,\partial_{m}\}$ of commuting derivations of $\mathcal{R}$ and an endomorphism $\sigma$ of $\mathcal{R}$ such that, for all $i$ , $\partial_{i}\sigma=\sigma\partial_{i}$ .
•

When $\mathcal{R}$ is additionally a field, it is called a $\Delta$ - $\sigma$ -field.
•

If $\sigma$ is an automorphism of $\mathcal{R}$ , $\mathcal{R}$ is called a $\Delta$ - $\sigma^{\ast}$ -ring.
•

If $\sigma=\operatorname{id}$ , $\mathcal{R}$ is called a $\Delta$ -ring or differential ring.
•

For a commutative ring $\mathcal{R}$ , $\langle F\rangle$ denotes the ideal generated by $F\subset\mathcal{R}$ in $\mathcal{R}$ .
•

For $\Delta=\{\partial_{1},\ldots,\partial_{m}\}$ , let $\Theta_{\Delta}=\{\partial_{1}^{i_{1}}\cdot\ldots\cdot\partial_{m}^{i_{m}}\mid i_{j}\geqslant 0,\,1\leqslant j\leqslant m\}$ .
•

For $\theta=\partial_{1}^{i_{1}}\cdot\ldots\cdot\partial_{m}^{i_{m}}\in\Theta_{\Delta}$ , we let $\operatorname{ord}\theta=i_{1}+\ldots+i_{m}$ . For a non-negative integer $B$ , we denote $\Theta_{\Delta}(B):=\{\theta\in\Theta_{\Delta}\mid\,\operatorname{ord}\theta\leqslant B\}$ .
•

For a $\Delta$ -ring $\mathcal{R}$ , the differential ideal generated by $F\subset\mathcal{R}$ in $\mathcal{R}$ is denoted by $\langle F\rangle^{(\infty)}$ ; for a non-negative integer $B$ , we introduce the following ideal of $\mathcal{R}$ :

$\langle F\rangle^{(B)}:=\langle\theta(F)\mid\,\theta\in\Theta_{\Delta}(B)\rangle.$

Definition 2.2 (Differential polynomials).

Let $\mathcal{R}$ be a $\Delta$ -ring. The differential polynomial ring over $\mathcal{R}$ in $\bm{y}=y_{1},\ldots,y_{n}$ is defined as

\mathcal{R}\{\bm{y}\}_{\Delta}:=\mathcal{R}[\theta y_{s}\mid\theta\in\Theta_{\Delta};\,1\leqslant s\leqslant n].

The structure of a $\Delta$ -ring is defined by $\partial_{i}(\theta y_{s}):=(\partial_{i}\theta)y_{s}$ for every $\theta\in\Theta_{\Delta}$ .

Definition 2.3 (Differential-difference polynomials).

Let $\mathcal{R}$ be a $\Delta$ - $\sigma$ -ring. The differential-difference polynomial ring over $\mathcal{R}$ in $\bm{y}=y_{1},\ldots,y_{n}$ is defined as

\mathcal{R}[\bm{y}_{\infty}]:=\mathcal{R}[\theta\sigma^{i}y_{s}\mid\theta\in\Theta_{\Delta};\,i\geqslant 0;\,1\leqslant s\leqslant n].

The structure of $\Delta$ - $\sigma$ ring is defined by $\sigma(\theta\sigma^{j}y_{s}):=\theta\sigma^{j+1}y_{s}$ and $\partial_{i}(\theta\sigma^{j}y_{s}):=(\partial_{i}\theta)\sigma^{j}y_{s}$ for every $\theta\in\Theta_{\Delta}$ and $j\geqslant 0$ .

A $\Delta$ - $\sigma$ -polynomial is an element of $\mathcal{R}[\bm{y}_{\infty}]$ . Given $B\in\mathbb{N}$ , let $\mathcal{R}[\bm{y}_{B}]$ denote the polynomial ring

\mathcal{R}[\theta\sigma^{j}y_{s}\mid\theta\in\Theta_{\Delta}(B);0\leqslant j\leqslant B;1\leqslant s\leqslant n].

The notions from logic that we use are described in detail in [19]. In particular, we will use the notions of a first-order language [19, Definition 1.1.1], structure [19, Definition 1.1.2], formula [19, Definition 1.1.5], theory [19, Section 1.2, page 14], model [19, Section 1.2, page 14], compactness [19, Section 2.1], complete theory [19, Definition 2.2.1], decidable theory [19, Definition 2.2.7], quantifier elimination [19, Definition 3.1.1], and $\aleph_{0}$ -saturation [19, Definition 4.3.1].

3. Main results

For clarity, we gather our main results in one section.

Theorem 3.1 (Upper bound for irreducible components for PDEs).

There exists a computable function $\operatorname{Components}(m,n)$ such that, for every differential field $k$ of zero characteristic with a set of $m$ commuting derivations $\Delta$ and finite $F\subset k\{y_{1},\ldots,y_{n}\}_{\Delta}$ with $\max\{\operatorname{ord}F,\deg F\}\leqslant s$ , the number of components in the variety defined by $F=0$ does not exceed $\operatorname{Components}(m,\max\{n,s\})$ .

Additional details and proof are given in Theorem 5.13.

Theorem 3.2 (Upper bound for elimination in delay PDEs).

For all non-negative integers $r$ , $m$ and $s$ , there exists a computable $B=B(r,m,s)$ such that, for all:

•

non-negative integers $q$ and $t$ ,
•

a $\Delta$ - $\sigma$ -field $k$ with $\operatorname{char}k=0$ and $|\Delta|=m$ ,
•

sets of $\Delta$ - $\sigma$ -polynomials $F\subset k[\bm{x}_{t},\bm{y}_{s}]$ , where $\bm{x}=x_{1},\ldots,x_{q}$ , $\bm{y}=y_{1},\ldots,y_{r}$ , and $\deg_{\bm{y}}F\leqslant s$ ,

we have

\big{\langle}\sigma^{i}(F)\mid i\in\mathbb{Z}_{\geqslant 0}\big{\rangle}^{(\infty)}\cap k[\bm{x}_{\infty}]\neq\{0\}\\ \iff\langle\sigma^{i}(F)\mid i\in[0,B]\big{\rangle}^{(B)}\cap k[\bm{x}_{B+t}]\neq\{0\}.

Corollary 3.3 (Effective Nullstellensatz for delay PDEs).

For all non-negative integers $r$ , $m$ and $s$ , there exists a computable $B=B(r,m,s)$ such that, for all:

•

$\Delta$ - $\sigma$ -fields $k$ with $\operatorname{char}k=0$ and $|\Delta|=m$ ,
•

sets of $\Delta$ - $\sigma$ -polynomials $F\subset k[\bm{y}_{s}]$ , where $\bm{y}=y_{1},\ldots,y_{r}$ , and $\deg F\leqslant s$ ,

the following statements are equivalent:

(1)

There exists a $\Delta$ - $\sigma^{*}$ field $L$ extending $k$ such that $F=0$ has a sequence solution in $L$ .
(2)

$1\notin\langle\sigma^{i}(F)\mid i\in[0,B]\big{\rangle}^{(B)}$ .
(3)

There exists a field extension $L$ of $k$ such that the polynomial system $\big{\{}\sigma^{i}(F)^{(j)}=0\mid i,j\in[0,B]\big{\}}$ in the finitely many unknowns $\bm{y}_{B+s}$ has a solution in $L$ .

The two preceding theorems are proved using our main technical result about algorithms performing computations in complete decidable theories. Stating it precisely requires defining admissible algorithms carefully, so we postpone it until Section 4 and give here a simplified and informal version of the statement.

Theorem 3.4 (Algorithm yields a bound, stated precisely as Theorem 4.5).

There exists a computable function with input

•

a complete decidable theory $T$ ;
•

an algorithm $\mathcal{A}$ performing computations in a model of $T$ restricted to using only definable functions when working with elements of the model;
•

positive integer $\ell$

that computes a number $N$ such that for every model $M$ of $T$ and every $\mathbf{a}\in M^{\ell}$ the size of the output of $\mathcal{A}$ with input $\mathbf{a}$ does not exceed $N$ .

For the application of this to the Rosenfeld-Gröbner algorithm, see Theorem 5.10.

4. Bounds for the output size of algorithms over complete theories

In this section, we will use the formalism of oracle Turing machines [24, § 14.3]. Roughly speaking, an oracle Turing machine is a Turing machine with an extra tape for performing queries to an external oracle. An oracle is not considered to be a part of the machine.

4.1. Setup

To consider an algorithm dealing with elements of a (not necessarily computable) model of a theory $T$ , we will “encapsulate” the elements of the model given to the algorithm into an oracle that allows to perform only first-order operations with them as defined below. Alternatively, one could adapt other approaches used to formalize computations in real numbers [2, Section 3] or in arbitrary structures (see [9, §1] and [4, §2.2]).

Definition 4.1 ( $T$ -oracle).

Let $\mathcal{L}$ be a language and $T$ be a theory in $\mathcal{L}$ . For elements $a_{1},\ldots,a_{\ell}$ of a model $M$ of $T$ , any oracle that supports the following queries: given a formula $\varphi(x_{1},\ldots,x_{\ell})$ , the oracle returns the value $\varphi(a_{1},\ldots,a_{\ell})$ in $M$ (can be true or false), will be denoted by $\mathcal{O}_{M}(a_{1},\ldots,a_{\ell})$ and called an evaluation oracle.

Definition 4.2 (Total algorithm over $T$ ).

An oracle Turing machine $\mathcal{A}$ will be called a total algorithm over $T$ if, for all positive integers $\ell$ , every model $M$ of $T$ and every $a_{1},\ldots,a_{\ell}\in M$ , the machine with every input and oracle $\mathcal{O}_{M}(a_{1},\ldots,a_{\ell})$ is guaranteed to terminate.

4.2. Auxiliary bound and result

Lemma 4.3.

There is an algorithm that takes as input:

•

language $\mathcal{L}$ ;
•

a complete decidable theory $T$ given by a Turing machine checking correctness of sentences in the theory;
•

a total algorithm $\mathcal{A}$ over $T$ ;
•

positive integers $\ell$ and $N$ ;
•

a string $\mathcal{S}$ in the input alphabet of $\mathcal{A}$ ;

and computes

•

a first-order formula $\varphi=\varphi_{T,\mathcal{A}}(\ell,\mathcal{S},N)$ in $\mathcal{L}$ in $\ell$ variables and
•

a number $\mathcal{N}:=\mathcal{N}_{T,\mathcal{A}}(\ell,\mathcal{S},N)$

such that, for any model $M$ of $T$ and tuple $\mathbf{a}\in M^{\ell}$ , the following are equivalent:

(1)

the sentence $\varphi(\mathbf{a})$ is true in $M$ ;
(2)

algorithm $\mathcal{A}$ with input $\mathcal{S}$ and oracle $\mathcal{O}_{M}(\mathbf{a})$ terminates after performing at most $N$ queries to the oracle

and if these statements are true, then the number of steps performed by $\mathcal{A}$ with input $\mathcal{S}$ and oracle $\mathcal{O}_{M}(\mathbf{a})$ does not exceed $\mathcal{N}$ .

Proof.

We describe an algorithm for computing $\varphi_{T,\mathcal{A}}(\ell,\mathcal{S},N)$ and $\mathcal{N}_{T,\mathcal{A}}(\ell,\mathcal{S},N)$ . Fix some $\mathcal{L},T,\mathcal{A},$ $\ell$ , and $\mathcal{S}$ .

We will describe an algorithm that, for a given positive integer $s$ , computes first-order formulas $\psi_{s}$ and $q_{s}$ in $\mathcal{L}$ in the variables $\mathbf{x}=(x_{1},\ldots,x_{\ell})$ and a positive integer $\mathcal{N}_{s}$ such that, for every model $M$ of $T$ and every $\mathbf{a}\in T^{\ell}$

•

$\psi_{s}(\mathbf{a})$ is true in $M$ iff algorithm $\mathcal{A}$ with input $\mathcal{S}$ and oracle $\mathcal{O}_{M}(\mathbf{a})$ will perform at least $s$ queries;
•

if $\psi_{s}(\mathbf{a})$ is true in $M$ , then the result of the $s$ -th query will be $q_{s}(\mathbf{a})$ ;
•

if algorithm $\mathcal{A}$ with input $\mathcal{S}$ and oracle $\mathcal{O}_{M}(\mathbf{a})$ performs at most $s$ queries, then the number of steps performed does not exceed $\mathcal{N}_{s}$ .

Fix some $s\geqslant 1$ and assume that the algorithm have computed $\psi_{1},\ldots,\psi_{s-1}$ , $q_{1},\ldots,q_{s-1}$ , and $\mathcal{N}_{0},\ldots,\mathcal{N}_{s-2}$ . Assume that $\mathcal{A}$ with input $\mathcal{S}$ has performed $s-1$ queries. Then whether or not an $s$ -th query will be performed is determined by the results of the first $s-1$ queries. Fix some $\mathbf{r}\in\{\mathrm{True},\mathrm{False}\}^{s-1}$ . It will represent possible results of the first $s-1$ queries. Consider the following formula in $\mathcal{L}$ :

\psi_{\mathbf{r}}(\mathbf{x}):=\psi_{s-1}(\mathbf{x})\wedge\bigwedge\limits_{i=1}^{s-1}\left(q_{i}(\mathbf{x})\iff r_{i}\right),

where we assume $\psi_{0}=\mathrm{True}$ . The algorithm uses the algorithm for checking correctness of sentences in $T$ to check whether the sentence $\exists\mathbf{x}\;\psi_{\mathbf{r}}(\mathbf{x})$ is false in $T$ . If it is, then there is no oracle of the form $\mathcal{O}_{M}(\mathbf{a})$ such that $\mathcal{A}$ will perform at least $s-1$ queries on it with the results being $r_{1},\ldots,r_{s-1}$ .

In the case of $\exists\mathbf{x}\;\psi_{\mathbf{r}}(\mathbf{x})$ is true in $T$ , the algorithm will run $\mathcal{A}$ with input $\mathcal{S}$ and an oracle $\mathcal{O}_{\mathbf{r}}$ that works as follows. For the first $s-1$ queries, $\mathcal{O}_{\mathbf{r}}$ will return $r_{1},\ldots,r_{s-1}$ . For all subsequent queries, it always returns True. The algorithm will stop the execution of $\mathcal{A}$ if $\mathcal{A}$ makes an $s$ -th query to the oracle, and denote the formula in the query by $q_{\mathbf{r}}$ .

Since $\exists\mathbf{x}\;\psi_{\mathbf{r}}(\mathbf{x})$ is true in $T$ , $\mathcal{O}_{\mathbf{r}}$ gives the same responses to the first $s-1$ queries as some oracle of the form $\mathcal{O}_{M}(\mathbf{a})$ . Since $\mathcal{A}$ must terminate in finite time for every such oracle, one of the following must happen:

(1)

$\mathcal{A}$ will perform an $s$ -th query.
(2)

$\mathcal{A}$ will terminate after performing only $s-1$ queries.

In the former case, as described above, the algorithm will define a formula $q_{\mathbf{r}}$ to be the $s$ -th query. In the latter case, the algorithm will define $\mathcal{N}_{\mathbf{r}}$ to be the number of steps performed by $\mathcal{A}$ . Then the algorithm computes

	$\displaystyle\psi_{s}(\mathbf{x}):=\bigvee\limits_{q_{\mathbf{r}}\text{ is defined}}\psi_{\mathbf{r}}(\mathbf{x}),\quad q_{s}(\mathbf{x}):=\bigwedge\limits_{q_{\mathbf{r}}\text{ is defined}}(\psi_{\mathbf{r}}(\mathbf{x})\implies q_{\mathbf{r}}(\mathbf{x})),$
	$\displaystyle\mathcal{N}_{s-1}:=\max\left(\mathcal{N}_{s-2},\sum\limits_{\mathcal{N}_{\mathbf{r}}\text{ is defined}}\mathcal{N}_{\mathbf{r}}\right),$

where we assume $\mathcal{N}_{-1}=-\infty$ . If the set $\{\mathbf{r}\mid q_{\mathbf{r}}\text{ is defined}\}$ is empty, the algorithm sets $\psi_{s}(\mathbf{x})=\operatorname{False}$ and $q_{s}(\mathbf{x})=\operatorname{True}$ . Finally, the algorithm returns $\varphi_{T,\mathcal{A}}(\ell,\mathcal{S},N):=\lnot\psi_{N+1}$ and $\mathcal{N}_{T,\mathcal{A}}(\ell,\mathcal{S},N):=\mathcal{N}_{N}$ . ∎

Lemma 4.4.

Let $T$ be a theory and $M$ an $\aleph_{0}$ -saturated model. Let $U_{1}\supset U_{2}\supset U_{3}\supset\ldots$ be a sequence of definable sets in $M^{n}$ such that $\bigcap\limits_{i=1}^{\infty}U_{i}=\varnothing$ . Then there exists $N$ such that $U_{N}=\varnothing$ .

Proof.

Assume the contrary, that is, that $U_{i}\neq\varnothing$ for every $i\geqslant 1$ . We will show that $\bigcap\limits_{i=1}^{\infty}U_{i}\neq\varnothing$ .

We show that a collection of formulas $\{x\in U_{i}\}_{i=1}^{\infty}$ is finitely satisfiable. Indeed, let $S\subset\mathbb{Z}_{>0}$ be a finite set and $N=\max S$ . Then $\bigcap_{i\in S}U_{i}=U_{N}\neq\varnothing$ . Due to compactness, the countable collection $\{x\in U_{i}\}_{i=1}^{\infty}$ is satisfiable in some elementary extension of $M$ . Since $M$ is $\aleph_{0}$ -saturated, this collection is satisfiable in $M$ . Therefore, $\bigcap\limits_{i=1}^{\infty}U_{i}\neq\varnothing$ . ∎

4.3. Main result

Theorem 4.5.

There exists a computable function $\operatorname{Steps}_{T,\mathcal{A}}(\ell,r)$ with input

•

a complete decidable theory $T$ (given by an algorithm for checking correctness of sentences);
•

a total algorithm $\mathcal{A}$ over $T$ ;
•

positive integers $\ell$ and $r$

that computes a number $N$ such that for every model $M$ of $T$ , every $\mathbf{a}\in M^{\ell}$ , and every string $\mathcal{S}$ in the alphabet of $\mathcal{A}$ of size at most $r$ , the number of steps performed by $\mathcal{A}$ with input $\mathcal{S}$ and oracle $\mathcal{O}_{M}(\mathbf{a})$ does not exceed $N$ .

Remark 4.6.

Let the intermediate result at step $n$ for a total algorithm $\mathcal{A}$ with given input and oracle be the content of all the cells of the tape that have been read by the Turing machine. Since a Turing machine can read at most one cell at each step, the number of these cells cannot exceed $n$ . Therefore, the intermediate result at step $n$ can be encoded using $n\log\ell$ bits, where $\ell$ is the cardinality of the alphabet of $\mathcal{A}$ . In particular, if a binary alphabet is used, the bitsize of the intermediate result never exceeds the total number of steps in the algorithm.

Proof.

We will describe an algorithm for computing $\operatorname{Steps}_{T,\mathcal{A}}(\ell,r)$ . We fix $T$ , $\mathcal{A}$ , $\ell$ , and $r$ . We will consider $\mathcal{S}$ of length at most $r$ and describe how to compute a bound for the number of steps given that the input is $\mathcal{S}$ . Taking the maximum over all $\mathcal{S}$ of length at most $r$ (there are finitely many of them), we obtain $\operatorname{Steps}_{\mathcal{A},T}(\ell,r)$ .

The algorithm will compute $\varphi_{i}:=\varphi_{T,\mathcal{A}}(\ell,\mathcal{S},i)$ for $i=1,2,\ldots$ using the algorithm from Lemma 4.3. For each $\varphi_{i}$ , the algorithm will check whether the formula is equivalent to $\mathrm{True}$ in $T$ using the decidability of $T$ .

If this is true, the algorithm stops and returns $\mathcal{N}_{T,\mathcal{A}}(\ell,\mathcal{S},i)$ (see Lemma 4.3). It remains to show that the described procedure terminates in finitely many steps. Let $M$ be an $\aleph_{0}$ -saturated model of $T$ (it exists, for example, due to [19, Theorem 4.3.12]). For every $i=1,2,\ldots$ , we introduce a definable set

U_{i}:=\{\mathbf{a}\in M^{\ell}\mid\varphi_{i}(\mathbf{a})=\mathrm{False}\}.

Notice that $U_{i}=\varnothing$ if and only if $(\varphi_{i}\iff\mathrm{True})$ in $T$ . Then the definition of $\varphi_{i}$ ’s implies that $U_{1}\supset U_{2}\supset\ldots$ . Assume that $\bigcap_{i=1}^{\infty}U_{i}$ is not empty and choose an element $\mathbf{a}$ in it. Then $\mathcal{A}$ will not terminate in finitely many steps with input $\mathcal{S}$ and oracle $\mathcal{O}_{M}(\mathbf{a})$ . Thus, $\bigcap_{i=1}^{\infty}U_{i}=\varnothing$ . Lemma 4.4 implies that there exists $N$ such that $U_{N}=\varnothing$ . Then our algorithm will terminate after checking whether $\varphi_{N}$ is equivalent to True. ∎

5. Applications to differential algebra

In this section, we will apply the results of Section 4 to the theory of differentially closed fields with several commuting derivations.

5.1. Preparation

Notation 5.1.

Let $m$ be a positive integer.

•

The language of partial differential rings with $m$ commuting derivation is denoted by $\mathcal{L}_{m}:=\{+,-,\cdot,0,1,\partial_{1},\ldots,\partial_{m}\}$ . We add a separate functional symbol for subtraction for convenience.
•

The theory of partial differentially closed fields with $m$ commuting derivations of characteristic zero is denoted by $\operatorname{DCF}_{m}$ . Recall that $\operatorname{DCF}_{m}$ is complete [21, Corollary 3.1.9 ] and, with this, is decidable by [19, Lemma 2.2.8] and [21, Lemma 3.1.2 and page 890].

Notation 5.2.

Let $m,n,h$ be positive integers and $k$ a differential field with a set of $m$ commuting derivations $\Delta=\{\partial_{1},\ldots,\partial_{m}\}$ .

•

$\operatorname{Pol}_{k}(m,n,h)$ denotes the space of all differential polynomials over $k$ in $n$ variables of order at most $h$ and degree at most $h$ .
•

The dimension of $\operatorname{Pol}_{k}(m,n,h)$ (which does not depend on $k$ ) will be denoted by $\operatorname{PolDim}(m,n,h)$ .

Notation 5.3.

Let $m$ , $\ell$ and $n$ be positive integers.

•

Let $\mathcal{L}_{m}(x_{1},\ldots,x_{\ell})\{y_{1},\ldots,y_{n}\}_{\Delta}$ denote the ring of differential polynomials in differential variables $y_{1},\ldots,y_{n}$ with respect to $m$ derivations with the coefficients being terms in the language $\mathcal{L}_{m}$ in $x_{1},\ldots,x_{\ell}$ (that is, elements of $\mathbb{Z}\{x_{1},\ldots,x_{\ell}\}_{\Delta})$ .

This is a computable differential ring with $m$ commuting derivations. In what follows, we will assume that the algorithms use dense representation to store these polynomials (that is, store all the coefficients up to certain order and certain degree).
•

Let $k$ be a differential field with $m$ derivations and $\mathbf{a}\in k^{\ell}$ . Then, for $T\in\mathcal{L}_{m}(x_{1},\ldots,x_{\ell})\{y_{1},\ldots,y_{n}\}_{\Delta}$ , we define $T(\mathbf{a})\in k\{y_{1},\ldots,y_{n}\}_{\Delta}$ to be the result of evaluating the coefficients of $T$ at $\mathbf{a}$ .

Definition 5.4.

A differential ranking for $k\{z_{1},\ldots,z_{n}\}_{\Delta}$ is a total order $>$ on $Z:=\{\theta z_{i}\mid\theta\in\Theta_{\Delta},\,1\leqslant i\leqslant n\}$ satisfying, for all $i$ , $1\leqslant i\leqslant m$ :

•

for all $x\in Z$ , $\partial_{i}(x)>x$ and
•

for all $x,y\in Z$ , if $x>y$ , then $\partial_{i}(x)>\partial_{i}(y)$ .

Notation 5.5.

For a $\Delta$ -field $k$ and $f\in k\{z_{1},\ldots,z_{n}\}_{\Delta}\backslash k$ and differential ranking $>$ ,

•

$\operatorname{lead}(f)$ is the element of $Z$ of the highest rank appearing in $f$ .
•

The leading coefficient of $f$ considered as a polynomial in $\operatorname{lead}(f)$ is denoted by $\operatorname{in}(f)$ and called the initial of $f$ .
•

The separant of $f$ is $\frac{\partial f}{\partial\operatorname{lead}(f)}$ .
•

The rank of $f$ is $\operatorname{rank}(f)=\operatorname{lead}(f)^{\deg_{\operatorname{lead}(f)}f}$ . The ranks are compared first with respect to $\operatorname{lead}$ , and in the case of equality with respect to $\deg$ .
•

For $S\subset k\{z_{1},\ldots,z_{n}\}_{\Delta}\backslash k$ , the set of initials and separants of $S$ is denoted by $H_{S}$ .

Remark 5.6 (Defining a ranking).

In general, there are uncountable many differential rankings already for $m=2$ and $n=1$ . However, [25, Theorem 29] implies that any differential ranking can be defined by $m(m+1)n$ real numbers together with $n^{2}$ integers not exceeding $m$ and one permutation on $n$ elements. We define a function $\operatorname{RK}_{m,n}(\bm{\alpha},\mathcal{S})$ taking as input a tuple $\bm{\alpha}$ of $m(m+1)n$ real numbers and a binary string $\mathcal{S}$ (of length at most $(n^{2}+n)\log_{2}(\max(n,m))$ ) encoding the integers and the permutation and returning the corresponding binary predicate on the derivatives as in [25, Definition 28]. The relevant properties of this encoding for us will be that, for fixed $\mathcal{S}$ :

(1)

the statement that $\operatorname{RK}_{m,n}(\bm{\alpha},\mathcal{S})$ defines a ranking is a first-order formula in $\bm{\alpha}$ in the language of ordered fields;
(2)

for every two derivatives $\theta_{1}z_{i}$ and $\theta_{2}z_{j}$ , the fact that $\theta_{1}z_{i}<\theta_{2}z_{j}$ with respect to $\operatorname{RK}_{m,n}(\bm{\alpha},\mathcal{S})$ is also a first-order formula in $\bm{\alpha}$ in the language of ordered fields.

Definition 5.7 (Characteristic sets).

•

For $f,g\in k\{z_{1},\ldots,z_{n}\}_{\Delta}\backslash k$ , $f$ is said to be reduced w.r.t. $g$ if no proper derivative of $\operatorname{lead}(g)$ appears in $f$ and $\deg_{\operatorname{lead}(g)}f<\deg_{\operatorname{lead}(g)}g$ .
•

A subset $\mathcal{A}\subset k\{z_{1},\ldots,z_{n}\}_{\Delta}\backslash k$ is called autoreduced if, for all $p\in\mathcal{A}$ , $p$ is reduced w.r.t. every element of $\mathcal{A}\setminus\{p\}$ . One can show that every autoreduced set is finite [13, Section I.9].
•
Let $\mathcal{A}=A_{1}<\ldots<A_{r}$ and $\mathcal{B}=B_{1}<\ldots<B_{s}$ be autoreduced sets ordered by their ranks (see Notation 5.5). We say that $\mathcal{A}<\mathcal{B}$ if
- –
  
  $r>s$ and $\operatorname{rank}(A_{i})=\operatorname{rank}(B_{i})$ , $1\leqslant i\leqslant s$ , or
- –
  
  there exists $q$ such that $\operatorname{rank}(A_{q})<\operatorname{rank}(B_{q})$ and, for all $i$ , $1\leqslant i<q$ , $\operatorname{rank}(A_{i})=\operatorname{rank}(B_{i})$ .
•

An autoreduced subset of the smallest rank of a differential ideal $I\subset k\{z_{1},\ldots,z_{n}\}_{\Delta}$ is called a characteristic set of $I$ . One can show that every non-zero differential ideal in $k\{z_{1},\ldots,z_{n}\}_{\Delta}$ has a characteristic set.
•

A radical differential ideal $I$ of $k\{z_{1},\ldots,z_{n}\}_{\Delta}$ is said to be characterizable if $I$ has a characteristic set $C$ such that $I=\langle C\rangle^{(\infty)}:H_{C}^{\infty}$ .

The Rosenfeld-Gröbner algorithm [3, Theorem 9] takes as input a finite set $F$ of differential polynomials and a differential ranking and outputs autoreduced sets $\mathcal{C}_{1},\ldots,\mathcal{C}_{N}$ such that

(1)

\sqrt{\langle F\rangle^{(\infty)}}=\bigcap_{i=1}^{N}\langle\mathcal{C}_{i}\rangle^{(\infty)}:H_{\mathcal{C}_{i}}^{\infty}

and that, for each $i$ , $1\leqslant i\leqslant N$ , $\mathcal{C}_{i}$ is a characteristic set of $\langle\mathcal{C}_{i}\rangle^{(\infty)}:H_{\mathcal{C}_{i}}^{\infty}$ . The representation (1) can be used, for example, for membership testing, estimating the number of irreducible components (used in Theorem 5.13) or the Kolchin polynomial (used in Section 6) of a differential-algebraic variety.

With the next Proposition 5.9 we express how we will call the Rosenfeld-Gröbner algorithm. This algorithm depends on the choice of a differential ranking. The reader may wish to make one such choice once and for all, thereby ignoring the potential ambiguity. However, since such a choice may affect the size of the output and the efficiency of any given implementation of the algorithm, one may prefer to allow for these other orderings.

We will express this dependence by seeing the algorithm as a total algorithm relative to the two-sorted theory $\operatorname{DCF}_{m}\oplus\operatorname{RCF}$ which is a disjoint union of $\operatorname{DCF}_{m}$ and the complete decidable theory with quantifier elimination of real closed fields $\operatorname{RCF}$ [19, Theorem 3.3.15 and Corollary 3.3.16]. Then we will use the characterization of differential rankings via real numbers from Remark 5.6.

Lemma 5.8.

Theory $\operatorname{DCF}_{m}\oplus\operatorname{RCF}$ is decidable and complete.

Proof.

In order to prove the completeness and decidability, we will prove that there is an algorithm for quantifier elimination in $\operatorname{DCF}_{m}\oplus\operatorname{RCF}$ based on the existence of such algorithms for $\operatorname{DCF}_{m}$ (follows from decidability, see Notation 5.1, and quantifier elimination [21, Theorem 3.1.7]) and $\operatorname{RCF}$ . It is sufficient to perform quantifier elimination for a formula of the form

\exists x\in S\colon L_{1}\wedge\ldots\wedge L_{N},

where $S$ is one of the sorts (corresponding to $\operatorname{DCF}_{m}$ or $\operatorname{RCF}$ ) and $L_{1},\ldots,L_{N}$ are literals. (See [19, Lemma 3.1.5].) By reordering $L_{1},\ldots,L_{N}$ if necessary, we will further assume that there exists $N_{0}$ such that $L_{1},\ldots,L_{N_{0}}$ are in the signature of the sort $S$ and $L_{N_{0}+1},\ldots,L_{N}$ are in the signature of the other sort. Then

\left(\exists x\in S\colon L_{1}\wedge\ldots L_{N}\right)\iff\left(\exists x\in S\colon L_{1}\wedge\ldots\wedge L_{N_{0}}\right)\wedge\left(L_{N_{0}+1}\wedge\ldots\wedge L_{N}\right),

and, for $\exists x\in S\colon L_{1}\wedge\ldots\wedge L_{N_{0}}$ , the algorithm for the corresponding sort $S$ can compute an equivalent quantifier-free formula.

The resulting theory is decidable because the correctness of each sentence can be checked by performing quantifier elimination after which the formula will become just true/false. ∎

Proposition 5.9.

There is a computable function that, for a given positive integer $m$ , computes a total algorithm $\mathcal{RG}_{m,}$ over $\operatorname{DCF}_{m}\oplus\operatorname{RCF}$ such that, for every differential field $k$ with $m$ derivations and $\mathbf{a}\in k^{\ell}$ and any $\mathbf{b}\in\mathbb{R}^{s}$ , the input-output specification of $\mathcal{RG}_{m}$ with oracle $\mathcal{O}_{k\oplus\mathbb{R}}(\mathbf{a},\mathbf{b})$ is the following:

Input:

finite subsets $A$ and $S$ of $\mathcal{L}_{m}(x_{1},\ldots,x_{\ell})\{y_{1},\ldots,y_{n}\}_{\Delta}$ and a binary string $\mathcal{S}$ ;

Output:

if $\operatorname{RK}_{m,n}(\mathbf{b},\mathcal{S})$ (see Remark 5.6) defines a differential ranking, return a list of tuples $C_{1},\ldots,C_{N}$ from $\mathcal{L}_{m}(x_{1},\ldots,x_{\ell})\{y_{1},\ldots,y_{n}\}_{\Delta}$ such that

C_{1}(\mathbf{a}),\ldots,C_{N}(\mathbf{a})

is the output of the Rosenfeld-Gröbner algorithm [3, Theorem 9] with input $(A(\mathbf{a}),S(\mathbf{a}))$ with respect to the ranking $\operatorname{RK}_{m,n}(\mathbf{b},\mathcal{S})$ . Otherwise, return $\varnothing$ .

Proof.

[3, Theorem 9] states that the only operations performed by the Rosenfeld-Gröbner algorithm with the elements of the ground differential field are arithmetic operations, differentiation, and zero testing. Algorithm $\mathcal{RG}_{m}$ is constructed to work exactly in the same way as the Rosenfeld-Gröbner algorithm with the only difference that the elements of the ground differential field will be represented as $L(\mathbf{a})$ , where $L\in\mathcal{L}_{m}(x_{1},\ldots,x_{\ell})\{y_{1},\ldots,y_{n}\}_{\Delta}$ . The arithmetic operations and differentiations can be performed with $L$ , zero testing can be performed using the $k$ -component of the oracle, and the queries to the ranking can be performed using the $\mathbb{R}$ -component of the oracle, so $\mathcal{RG}$ will be able to perform the same computations as the Rosenfeld-Gröbner algorithm.

Due to [3, Theorem 5], the Rosenfeld-Gröbner algorithm is guaranteed to terminate on every input. Hence, the same is true for $\mathcal{RG}_{m}$ . ∎

5.2. Bounds

Theorem 5.10 (Upper bound for Rosenfeld-Gröbner algorithm).

There exists a computable function $\operatorname{RG}(m,n,\ell)$ such that, for every differential field $k$ with $m$ derivations and subsets $A,S\subset\operatorname{Pol}_{k}(m,n,n)$ with $|A|,|S|\leqslant\ell$ , and every differential ranking, the Rosenfeld-Gröbner algorithm [3, Theorem 9] on $A$ and $S$ will produce at most $\operatorname{RG}(m,n,\ell)$ components with all the orders and degrees of the differential polynomials occurring in the algorithm not exceeding $\operatorname{RG}(m,n,\ell)$ .

Proof.

We fix integers $m$ , $n$ , and $\ell$ and compute the total algorithm $\mathcal{RG}_{m}$ over $\operatorname{DCF}_{m}\oplus\operatorname{RCF}$ from Proposition 5.9. Let $\mathbf{a}$ be the set of all the coefficients of $A$ and $S$ . Then $|\mathbf{a}|\leqslant N:=2\ell\operatorname{PolDim}(m,n,n)$ . The sets $A$ and $S$ can be presented as evaluations of subsets $\widetilde{A},\widetilde{S}\subset\mathcal{L}_{m}(x_{1},\ldots,x_{N})\{y_{1},\ldots,y_{n}\}_{\Delta}$ at $\mathbf{a}$ such that the orders and degrees of $\widetilde{A},\widetilde{S}$ in $y_{1},\ldots,y_{n}$ do not exceed $n$ and every coefficient is a single variable $x_{i}$ . Let the ranking be defined as $\operatorname{RK}(\mathbf{b},\mathcal{S})$ (see Remark 5.6), where $\mathbf{b}$ is a tuple of $m(m+1)n$ real numbers and $\mathcal{S}$ is a binary string of length at most $(n^{2}+n)\log_{2}\max(n,m)$ . Then the the tuple $(\widetilde{A},\widetilde{S},\mathcal{S})$ can be encoded as a binary string of the length bounded by a computable function $S(m,n,N)$ .

We run $\mathcal{RG}_{m}$ with the input $\mathcal{I}=(\widetilde{A},\widetilde{S},\mathcal{S})$ and oracle $\mathcal{O}(\mathbf{a},\mathbf{b})$ . Theorem 4.5 implies that the number of steps and, consequently, the bitsize of of all the intermediate results (see Remark 4.6) will not exceed $\operatorname{Steps}_{\mathcal{RG}_{m},\operatorname{DCF}_{m}\oplus\operatorname{RCF}}(N,S(m,n,N))$ .

Since each component takes at least one bit, a polynomial of degree $d$ or order $d$ has at least $d$ coefficients (due to the dense representation of the polynomials, see Notation 5.2) requiring at least one bit each, the number of components, the degrees and orders do not exceed the bitsize of the intermediate results. Therefore, we can set $\operatorname{RG}(m,n,\ell)=\operatorname{Steps}_{\mathcal{RG}_{m},\operatorname{DCF}_{m}\oplus\operatorname{RCF}}(N,S(m,n,N))$ . ∎

Corollary 5.11.

There exists a computable function $\operatorname{CharSet}(m,n,\ell)$ such that, for every computable differential field $k$ with $m$ derivations and subsets $A,S\subset\operatorname{Pol}_{k}(m,n,n)$ with $|A|,|S|\leqslant\ell$ , and every differential ranking, the ideal $\sqrt{\langle A\rangle^{(\infty)}\colon S^{\infty}}$ can be written as an intersection of at most $\operatorname{CharSet}(m,n,\ell)$ characterizable differential ideals defined by their characteristic sets with respect to the ranking of order and degree not exceeding $\operatorname{CharSet}(m,n,\ell)$ .

Proof.

Theorem 5.10 implies that there exists a representation

\sqrt{\langle A\rangle^{(\infty)}\colon S^{\infty}}=(\langle C_{1}\rangle^{(\infty)}\colon H_{C_{1}})\cap\ldots\cap(\langle C_{N}\rangle^{(\infty)}\colon H_{C_{N}}),

where $H_{C_{i}}$ is the product of the initials and separants of $C_{i}$ , and $C_{i}$ is the characteristic presentation [3, Definition 8] of $\langle C_{i}\rangle^{(\infty)}\colon H_{C_{i}}^{\infty}$ for every $1\leqslant i\leqslant N$ . As noted in [3, p. 108] a characteristic set of $\langle C_{i}\rangle^{(\infty)}\colon H_{C_{i}}^{\infty}$ can be obtained from $C_{i}$ by performing reductions until it will become autoreduced. Since differential reduction is a part of the Rosenfeld-Gröbner algorithm, it can also be performed by a total algorithm over $\operatorname{DCF}_{m}\oplus\operatorname{RCF}$ . Therefore, as in the proof of Theorem 5.10, Lemma 4.5 implies that $\langle C_{i}\rangle^{(\infty)}\colon H_{C_{i}}^{\infty}$ has a characteristic set with degrees and order bounded by a computable function of the degrees and orders of $C_{i}$ . The latter are bounded by a computable function $\operatorname{RG}$ due to Theorem 5.10. Composing these two bounds, we obtain a desired function $\operatorname{CharSet}(m,n,\ell)$ . ∎

Lemma 5.12.

There exists a computable function $\operatorname{PrimeComp}(m,n)$ such that for every partial differential field $k$ with $m$ derivations, every ranking, and every characterizable differential ideal $I$ defined by a characteristic set $C\subset\operatorname{Pol}_{k}(m,n,n)$ with respect to this ranking, we have

(1)

the number of prime components of $I$ does not exceed $\operatorname{PrimeComp}(m,n)$ ;
(2)

every prime component of $I$ has a characteristic set with respect to the ranking with orders and degrees bounded by $\operatorname{PrimeComp}(m,n)$ .

Proof.

Let $H$ be the product of the initials and separants of $C$ . [3, Theorem 4] implies that the number of prime components of $\langle C\rangle^{(\infty)}\colon H^{\infty}$ is equal to the number of prime components of the algebraic ideal $(\langle C\rangle^{(\infty)}\colon H^{\infty})\cap R_{n}$ , where $R_{n}$ is the ring of differential polynomials of order at most $n$ . Since the degrees of elements of $C$ are bounded by $n$ , the Bézout inequality implies that there is a computable bound $D$ for the degree of the radical ideal $I\cap R_{n}$ (defined, e.g., as the degree of the corresponding affine variety [12, page 246]) in terms of $m$ and $n$ , so this gives a bound for the number of components.

Let $P_{1},\ldots,P_{\ell}$ be the prime components of $I$ . For every $1\leqslant i\leqslant\ell$ , $P_{i}\cap R_{n}$ is a prime algebraic ideal, and its zero set can be defined by equations of degree at most $\deg(P_{i}\cap R_{n})$ due to [12, Proposition 3]. Therefore, for each $2\leqslant i\leqslant\ell$ , we can choose a polynomial in $(P_{1}\setminus P_{i})\cap R_{n}$ of degree at most $\deg(P_{i}\cap R_{n})$ . Their product $Q$ has degree at most $\deg(I\cap R_{n})\leqslant D$ . Observe that

P_{1}=P_{1}\colon Q^{\infty}\subset I\colon Q^{\infty}=(P_{1}\colon Q^{\infty})\cap\ldots\cap(P_{\ell}\colon Q^{\infty})=P_{1}.

Thus, applying Corollary 5.11 to a pair $(C,HQ)$ and using that $|C|\leqslant\operatorname{PolDim}(m,n)$ , we show that $P_{1}$ has a characteristic set with orders and degrees bounded by $\operatorname{CharSet}(m,D+n,\operatorname{PolDim}(m,n))$ . ∎

Theorem 5.13 (Upper bound for the components of a differential variety and their number).

There exists a computable function $\operatorname{Components}(m,n)$ such that, for all non-negative integers $m$ , $n$ and $h$ and a partial differential field $k$ with $m$ derivations and finite set $F\subset\operatorname{Pol}_{k}(m,n,h)$ :

(1)

the number of components in the variety defined by $F=0$ does not exceed $\operatorname{Components}(m,\max\{n,h\})$ ;
(2)

for every differential ranking and every component $X$ of the variety $F=0$ , $X$ has a characteristic set with respect to the ranking with orders and degrees bounded by $\operatorname{Components}(m,\max\{n,h\})$ .

Proof.

Consider any differential ranking. By replacing $F$ with the basis of its linear span, we will further assume that $|F|\leqslant\operatorname{PolDim}(m,n,h)$ (see Notation 5.2). Corollary 5.11 implies that $\sqrt{\langle F\rangle^{(\infty)}}$ can be represented as an intersection of at most $N$ characterizable ideals with characteristic sets $C_{1},\ldots,C_{N}$ of order and degree at most $N$ , where

N:=\operatorname{CharSet}(m,\max\{n,h\},\operatorname{PolDim}(m,n,h)).

Lemma 5.12 applied to each of $C_{1},\ldots,C_{N}$ implies that the number of components of the variety defined by $F=0$ does not exceed $N\cdot\operatorname{PrimeComp}(m,N)$ , and each of them has a characteristic set with orders and degrees not exceeding $\operatorname{PrimeComp}(m,N)$ . ∎

Remark 5.14.

It was shown in [11, Theorem 6.1] that there exists a (not necessarily computable) bound for the degrees and orders a characteristic set of a prime differential ideal. The second part of Theorem 5.13 implies that there is a computable bound.

6. Application to delay PDEs

In this section, we will show how Theorem 5.13 applies to the problem of elimination of unknowns in delay PDEs.

The proof of the main result of this section, Theorem 6.23 (Effective elimination theorem for delay PDEs) inherited from [18] had only two missing ingredients closely related to each other: the bound on the number of components of the variety defined by a system of differential algebraic PDEs and bounds on the coefficients of Kolchin polynomials under projection in the PDE case. Now that we have obtained the former in Theorem 5.13 together with a bound for characteristic sets, it is possible to obtain the latter in Lemma 6.6 and finish the proof. Therefore, Section 6 can be thought of as a motivation for the rest of the paper and is an interesting example of a problem from differential-difference algebra that motivated a purely differential algebraic result.

6.1. Bounds for Kolchin polynomials for algebraic PDEs

Definition 6.1.

Let $K$ be a differentially closed $\Delta$ -field containing a $\Delta$ -field $k$ . We say that $X\subset K^{n}$ is a $\Delta$ -variety over $k$ if there exists $F\subset k\{y_{1},\ldots,y_{n}\}_{\Delta}$ such that

X=\{\bm{a}\in K^{n}\mid\forall\,f\in F\ f(\bm{a})=0\}.

We write $X=\mathbb{V}(F)$ . The $\Delta$ -variety $K^{n}$ is denoted by $\mathbb{A}^{n}$ . A $\Delta$ -variety $\mathbb{V}(F)$ is called irreducible if the differential ideal $\sqrt{\langle F\rangle^{(\infty)}}$ is prime.

For a subset $Y\subset K^{n}$ , the smallest $\Delta$ -variety $X\subset K^{n}$ containing $Y$ is called the Kolchin closure of $Y$ and denoted by $\overline{Y}^{\operatorname{Kol}}$ .

Definition 6.2.

We will say that a $\Delta$ -variety $X\subset\mathbb{A}^{n}$ is bounded by $N$ if $N\geqslant\max(n,m)$ ( $m=|\Delta|$ ) and $X$ can be defined by equations of order and degree at most $N$ .

Notation 6.3.

For a numeric polynomial $\omega(t)=\sum\limits_{i=0}^{m}a_{i}\binom{t+i}{i}$ , we set

|\omega|:=\sum\limits_{i=0}^{m}|a_{i}|.

Definition 6.4.

The generic point $(a_{1},\ldots,a_{n})$ of an irreducible $\Delta$ -variety $X=\mathbb{V}(F)$ , where $F\subset k\{\bm{y}\}_{\Delta}$ , is the image of $\bm{y}$ under the homomorphism $K\{\bm{y}\}_{\Delta}\to K\{\bm{y}\}_{\Delta}\big{/}\sqrt{\langle F\rangle^{(\infty)}}$ .

Definition 6.5.

The Kolchin polynomial of an irreducible $\Delta$ -variety $V=\mathbb{V}(F)$ , where $F\subset k\{\bm{y}\}_{\Delta}$ , is the unique numerical polynomial $\omega_{V}(t)$ such that there exists $t_{0}\geqslant 0$ such that, for all $t\geqslant t_{0}$ and the generic point $\bm{a}$ of $V$ , $\omega_{V}(t)=\operatorname{trdeg}k(\bm{a}_{t})/k$ , where $\bm{a}_{t}=\big{(}\theta(\bm{a}):\theta\in\Theta_{\Delta}(t)\big{)}$ . For the proof of the existence, see [22, Theorem 5.4.1].

Lemma 6.6.

There exists a computable function $\operatorname{KolchinProj}(N)$ such that for every

•

differential variety $X\subset\mathbb{A}^{n}$ bounded by $N$ ,
•

irreducible component $X_{0}\subset X$ ,
•

and linear projection $\pi\colon\mathbb{A}^{n}\to\mathbb{A}^{\ell}$ ,

we have $|\omega_{Y}|\leqslant\operatorname{KolchinProj}(N)$ , where $Y:=\overline{\pi(X_{0})}^{\operatorname{Kol}}$ .

Proof.

By performing a linear change of variables, we reduce the problem to the case in which $\pi$ is the projection to the first $\ell$ coordinates. Consider a ranking such that

•

$y_{\ell+i}$ is greater than every derivative of $y_{j}$ for every $i>0$ and $1\leqslant j\leqslant\ell$ ;
•

the restriction of the ranking on $y_{1},\ldots,y_{\ell}$ is an orderly ranking (that is, a ranking such that $\operatorname{ord}\theta_{1}>\operatorname{ord}\theta_{2}$ implies, for all $i$ and $j$ , $\theta_{1}y_{i}>\theta_{2}y_{j}$ ).

Theorem 5.13 implies that $X_{0}$ has a characteristic set $\mathcal{C}$ with respect to this ranking with the order bounded by a computable function of $N$ . Since a characteristic set of $Y$ can be obtained from $\mathcal{C}$ by selecting the polynomials only in the first $\ell$ variables, there is a charactersitic set of $Y$ with respect to the orderly ranking with the order bounded by a computable function of $N$ . Then [15, Proposition 3.1] and [15, Fact 2.1] imply that $|\omega_{Y}|$ is bounded by a computable function of $N$ . ∎

Proposition 6.7.

There exists an algorithm that, for every computable function $g(n)\colon\mathbb{Z}_{\geqslant 0}\to\mathbb{Z}_{\geqslant 0}$ , produces a number $\operatorname{Len}_{g}$ such that, for every sequence of Kolchin polynomials

\omega_{0}>\omega_{1}>\ldots>\omega_{\ell}

such that $|\omega_{i}|<g(i)$ for every $0\leqslant i\leqslant\ell$ , we have $\ell<\operatorname{Len}_{g}$ .

Proof.

By replacing $g(n)$ with $n+\max\limits_{0\leqslant s\leqslant n}g(s)$ , we can further assume that $g(n)$ is increasing and $g(n)\geqslant n$ . [22, Definition 2.4.9 and Lemma 2.4.12] define a computable order-preserving map $c$ from the set of all Kolchin polynomials $\mathcal{K}$ to $\mathbb{Z}_{\geqslant 0}^{m+1}$ (considered with respect to the lexicographic ordering). For $v=(v_{0},\ldots,v_{m})\in\mathbb{Z}_{\geqslant 0}^{m+1}$ , we define $|v|=v_{0}+\ldots+v_{m}$ . For every function $g\colon\mathbb{Z}_{\geqslant 0}\to\mathbb{Z}_{\geqslant 0}$ , we define

\widetilde{g}(n):=\max\limits_{\omega\in\mathcal{K},\;|\omega|\leqslant g(n)}|c(\omega)|.

Note that if $g(n)$ was computable, then $\widetilde{g}(n)$ is also computable.

The sequence $\omega_{0}>\omega_{1}>\ldots$ gives rise to a sequence $c(\omega_{0})>_{\operatorname{lex}}c(\omega_{1})>_{\operatorname{lex}}\ldots$ in $\mathbb{Z}_{\geqslant 0}^{m+1}$ with $|c(\omega_{i})|\leqslant\widetilde{g}(i)$ for every $i$ . [20, Main Lemma] implies that there is an algorithm to compute the maximal length of such a sequence, so there is an algorithm to compute a bound on $\ell$ from $g$ . ∎

6.2. Trains of varieties, partial solutions, and their upper bounds

Lemma 6.8.

For every $\Delta$ - $\sigma$ -field $k$ of characteristic zero, there exists an extension $k\subset K$ of $\Delta$ - $\sigma$ -fields, where $K$ is a differentially closed $\Delta$ - $\sigma^{*}$ -field.

Proof.

The proof follows [18, Lemma 6.1] mutatis mutandis as follows. We will show that there exists a $\Delta$ - $\sigma^{\ast}$ -field $K_{0}$ containing $k$ . The proof of [17, Proposition 2.1.7] implies that one can build an ascending chain of $\sigma$ -fields

(2)

k_{0}\subset k_{1}\subset k_{2}\subset\ldots

such that, for every $i\in\mathbb{N}$ , there exists an isomorphism $\varphi_{i}\colon k\to k_{i}$ of $\sigma$ -fields, $\sigma(k_{i+1})=k_{i}$ , and $\varphi_{i}=\sigma\circ\varphi_{i+1}$ for every $i\in\mathbb{N}$ . We transfer the $\Delta$ - $\sigma$ -structure from $k$ to $k_{i}$ ’s via $\varphi_{i}$ ’s. Then $\varphi_{i}=\sigma\circ\varphi_{i+1}$ implies that the restriction of $\Delta$ on $k_{i+1}$ to $k_{i}$ coincides with the action of $\Delta$ on $k_{i}$ . We set $K_{0}:=\bigcup\limits_{i\in\mathbb{N}}k_{i}$ . Since the action $\Delta$ and $\sigma$ is consistent with the ascending chain (2), $K_{0}$ is a $\Delta$ - $\sigma$ -extension of $k_{0}\cong k$ . It is shown in [17, Proposition 2.1.7] that the action of $\sigma$ on $K_{0}$ is surjective. [14, Corollary 2.4] implies that $K_{0}$ can be embedded in a differentially closed $\Delta$ - $\sigma^{\ast}$ -field $K$ . ∎

Notation 6.9.

Within Sections 6.2 and 6.3, we fix a ground $\Delta$ - $\sigma$ field $k$ and a differentially closed $\Delta$ - $\sigma^{\ast}$ -field $K$ given by Lemma 6.8 applied to $k$ . All varieties in Sections 6.2 and 6.3 are considered over $K$ .

Definition 6.10 (Partial solutions).

•

For $\Delta$ - $\sigma$ -rings $\mathcal{R}_{1}$ and $\mathcal{R}_{2}$ , a homomorphism $\phi:\mathcal{R}_{1}\longrightarrow\mathcal{R}_{2}$ is called a $\Delta$ - $\sigma$ -homomorphism if, for all $i$ , $\phi\partial_{i}=\partial_{i}\phi$ and $\phi\sigma=\sigma\phi$ .

•

Let $\mathcal{R}$ be a $\Delta$ - $\sigma$ -ring containing a $\Delta$ - $\sigma$ -field $k$ . Let $k[\bm{y}_{\infty}]$ be the $\Delta$ - $\sigma$ -polynomial ring over $k$ in $\bm{y}=y_{1},\ldots,y_{r}$ . Given a point $\bm{a}=(a_{1},\dots,a_{r})\in\mathcal{R}^{r}$ , there exists a unique $\Delta$ - $\sigma$ -homomorphism over $k$ ,

\phi_{\bm{a}}:k[\bm{y}_{\infty}]\longrightarrow\mathcal{R}\quad\text{with}\ \ \phi_{\bm{a}}(y_{i})=a_{i}\ \text{and}\ \phi_{\bm{a}}|_{k}=\operatorname{id}.

Given $f\in k[\bm{y}_{\infty}]$ , $\bm{a}$ is called a solution of $f$ in $\mathcal{R}$ if $f\in\operatorname{Ker}(\phi_{\bm{a}})$ .

•

For a $\Delta$ - $\sigma$ - $k$ -algebra $\mathcal{R}$ and $I=\mathbb{N}$ or $\mathbb{Z}$ , the sequence ring $\mathcal{R}^{I}$ has the following structure of a $\Delta$ - $\sigma$ -ring ( $\Delta$ - $\sigma^{\ast}$ -ring for $I=\mathbb{Z}$ ) with $\sigma$ and $\Delta$ defined by

\sigma\big{(}(x_{i})_{i\in I}\big{)}:=(x_{i+1})_{i\in I}\quad\text{and}\quad\partial_{j}\big{(}(x_{i})_{i\in I}\big{)}:=(\partial_{j}(x_{i}))_{i\in I}.

For a $k$ - $\Delta$ - $\sigma$ -algebra $\mathcal{R}$ , $\mathcal{R}^{I}$ can be considered a $k$ - $\Delta$ - $\sigma$ -algebra by embedding $k$ into $\mathcal{R}^{I}$ in the following way:

a\mapsto(\sigma^{i}(a))_{i\in I},\ \ a\in k.

For $f\in k[\bm{y}_{\infty}]$ , a solution of $f$ with components in $\mathcal{R}^{I}$ is called a sequence solution of $f$ in $\mathcal{R}$ .

•

Given $f\in\mathcal{R}[\bm{y}_{\infty}]$ , the order of $f$ is defined to be the maximal $\operatorname{ord}\theta+j$ such that $\theta\sigma^{j}y_{s}$ effectively appears in $f$ for some $s$ , denoted by $\operatorname{ord}(f)$ .
•

The relative order of $f$ with respect to $\Delta$ (resp. $\sigma$ ), denoted by $\operatorname{ord}_{\Delta}(f)$ (resp. $\operatorname{ord}_{\sigma}(f)$ ), is defined as the maximal $\operatorname{ord}\theta$ (resp. $j$ ) such that $\theta\sigma^{j}y_{s}$ effectively appears in $f$ for some $s$ .
•

Let $F=\{f_{1},\ldots,f_{N}\}\subset k[\bm{y}_{\infty}]$ , where $\bm{y}=y_{1},\ldots,y_{r}$ , be a set of $\Delta$ - $\sigma$ -polynomials. Suppose $h=\max\{\operatorname{ord}_{\sigma}(f)\mid f\in F\}$ . A sequence of tuples $(\overline{a}_{1},\ldots,\overline{a}_{r})\in K^{\ell+h}\times\cdots\times K^{\ell+h}$ is called a partial solution of $F$ of length $\ell$ if $(\overline{a}_{1},\ldots,\overline{a}_{r})$ is a $\Delta$ -solution of the system in $\bm{y}_{\infty,\ell+h-1}$ :

$\{\sigma^{i}(F)=0\;|\;0\leqslant i\leqslant\ell-1\},$

where $\bm{y}_{\infty,\ell+h-1}=\{\theta\sigma^{i}y_{s}\mid\theta\in\Theta_{\Delta};\,0\leqslant i\leqslant\ell+h-1;\,1\leqslant s\leqslant r\}$ .

We associate the following geometric data with the above set $F$ of $\Delta$ - $\sigma$ -polynomials:

•

the $\Delta$ -variety $X\subset\mathbb{A}^{H}$ defined by $f_{1}=0,\ldots,f_{N}=0$ regarded as $\Delta$ -equations in $k[\bm{y}_{\infty,h}]$ with $H={r}(h+1)$ , and

•

two projections $\pi_{1},\pi_{2}:\mathbb{A}^{H}\longrightarrow\mathbb{A}^{H-r}$ defined by

	$\displaystyle\pi_{1}(a_{1},\ldots,\sigma^{h}(a_{1});\ldots;$	$\displaystyle a_{r},\ldots,\sigma^{h}(a_{r}))$
		$\displaystyle:=(a_{1},\sigma(a_{1}),\ldots,\sigma^{h-1}(a_{1});\ldots;a_{r},\ldots,\sigma^{h-1}(a_{r})),$
	$\displaystyle\pi_{2}(a_{1},\ldots,\sigma^{h}(a_{1});\ldots;$	$\displaystyle a_{r},\ldots,\sigma^{h}(a_{r}))$
		$\displaystyle:=(\sigma(a_{1}),\ldots,\sigma^{h}(a_{1});\ldots;\sigma(a_{r}),\ldots,\sigma^{h}(a_{r})).$

Let $\sigma(X)$ denote the $\Delta$ -variety in $\mathbb{A}^{H}$ defined by $f_{1}^{\sigma},\ldots,f_{N}^{\sigma}$ , where $f_{i}^{\sigma}$ is the result by applying $\sigma$ to the coefficients of $f_{i}$ .

Definition 6.11.

A sequence $p_{1},\ldots,p_{\ell}\in\mathbb{A}^{H}$ is a partial solution of the triple $(X,\pi_{1},\pi_{2})$ if

(1)

for all $i$ , $1\leqslant i\leqslant\ell$ , we have $p_{i}\in\sigma^{i-1}(X)$ and
(2)

for all $i$ , $1\leqslant i<\ell$ , we have $\pi_{1}(p_{i+1})=\pi_{2}(p_{i})$ .

A two-sided infinite sequence with such a property is called a solution of the triple $(X,\pi_{1},\pi_{2})$ .

Lemma 6.12.

For every positive integer $\ell$ , $F$ has a partial solution of length $\ell$ if and only if the triple $(X,\pi_{1},\pi_{2})$ has a partial solution of length $\ell.$ The system $F$ has a sequence solution in $K^{\mathbb{Z}}$ if and only if the triple $(X,\pi_{1},\pi_{2})$ has a solution.

Proof.

As in [18, Lemma 6.5]. ∎

Definition 6.13.

For $\ell\in\mathbb{N}$ or $+\infty$ , a sequence of irreducible $\Delta$ -subvarieties $(Y_{1},\ldots,Y_{\ell})$ in $\mathbb{A}^{H}$ is said to be a train of length $\ell$ in $X$ if

(1)

for all $i$ , $1\leqslant i\leqslant\ell$ , we have $Y_{i}\subseteq\sigma^{i-1}(X)$ and
(2)

for all $i$ , $1\leqslant i<\ell$ , we have $\overline{\pi_{1}(Y_{i+1})}^{\operatorname{Kol}}=\overline{\pi_{2}(Y_{i})}^{\operatorname{Kol}}$ .

Lemma 6.14.

For every train $(Y_{1},\ldots,Y_{\ell})$ in $X$ , there exists a partial solution $p_{1},\ldots,p_{\ell}$ of $(X,\pi_{1},\pi_{2})$ such that for all $i$ , we have $p_{i}\in Y_{i}$ . In particular, if there is an infinite train in $X$ , then there is a solution of the triple $(X,\pi_{1},\pi_{2})$ .

Proof.

We prove it as in [18, Lemma 6.7], as follows. To prove the existence of a partial solution of $(X,\pi_{1},\pi_{2})$ with the desired property, it suffices to prove the following:

Claim.

There exists a nonempty open (in the sense of the Kolchin topology) subset $U\subseteq Y_{\ell}$ such that for each $p_{\ell}\in U$ , $p_{\ell}$ can be extended to a partial solution $p_{1},\ldots,p_{\ell}$ of $(X,\pi_{1},\pi_{2})$ with $p_{i}\in Y_{i}$ for every $1\leqslant i\leqslant\ell$ .

We will prove the Claim by induction on $\ell$ . For $\ell=1$ , take $U=Y_{1}$ . Since each point in $Y_{1}$ is a partial solution of $(X,\pi_{1},\pi_{2})$ of length 1, the Claim holds for $\ell=1$ . Now suppose we have proved the Claim for $\ell-1$ . So there exists a nonempty open subset $U_{0}\subseteq Y_{\ell-1}$ satisfying the desired property. Since $Y_{\ell-1}$ is irreducible, $U_{0}$ is dense in $Y_{\ell-1}.$ So, $\pi_{2}(U_{0})$ is dense in $\overline{\pi_{2}(Y_{\ell-1})}^{\operatorname{Kol}}=\overline{\pi_{1}(Y_{\ell})}^{\operatorname{Kol}}$ . Since $U_{0}$ is $\Delta$ -constructible (that is, solution set of a quantifier-free formula with parameters in $K$ or, equivalently, a finite union of $\Delta$ -closed and $\Delta$ -open sets), $\pi_{2}(U_{0})$ is $\Delta$ -constructible too. So, $\pi_{2}(U_{0})$ contains a nonempty open subset of $\overline{\pi_{1}(Y_{\ell})}^{\operatorname{Kol}}$ .

Since $\pi_{1}(Y_{\ell})$ is $\Delta$ -constructible and dense in $\overline{\pi_{1}(Y_{\ell})}^{\operatorname{Kol}}$ , $\pi_{2}(U_{0})\cap\pi_{1}(Y_{\ell})\neq\varnothing$ is $\Delta$ -constructible and dense in $\overline{\pi_{1}(Y_{\ell})}^{\operatorname{Kol}}$ . Let $U_{1}$ be a nonempty open subset of $\overline{\pi_{1}(Y_{\ell})}^{\operatorname{Kol}}$ contained in $\pi_{2}(U_{0})\cap\pi_{1}(Y_{\ell})$ and

U_{2}=\pi_{1}^{-1}(U_{1})\cap Y_{\ell}.

Then $U_{2}$ is a nonempty open subset of $Y_{\ell}$ . We will show that for each $p_{\ell}\in U_{2}$ , there exists $p_{i}\in Y_{i}$ for $i=1,\ldots,\ell-1$ such that $p_{1},\ldots,p_{\ell}$ is a partial solution of $(X,\pi_{1},\pi_{2}).$

Since $\pi_{1}(p_{\ell})\in U_{1}\subset\pi_{2}(U_{0})$ , there exists $p_{\ell-1}\in U_{0}$ such that $\pi_{1}(p_{\ell})=\pi_{2}(p_{\ell-1}).$ Since $p_{\ell-1}\in U_{0}$ , by the inductive hypothesis, there exists $p_{i}\in Y_{i}$ for $i=1,\ldots,\ell-1$ such that $p_{1},\ldots,p_{\ell-1}$ is a partial solution of $(X,\pi_{1},\pi_{2})$ of length $\ell-1$ . So $p_{1},\ldots,p_{\ell}$ is a partial solution of $(X,\pi_{1},\pi_{2})$ of length $\ell$ . ∎

For two trains $Y=(Y_{1},\ldots,Y_{\ell})$ and $Y^{\prime}=(Y^{\prime}_{1},\ldots,Y^{\prime}_{\ell})$ , denote $Y\subseteq Y^{\prime}$ if $Y_{i}\subseteq Y^{\prime}_{i}$ for each $i$ . Given an increasing chain of trains $Y_{i}=(Y_{i,1},\ldots,Y_{i,\ell})$ ,

\big{(}\overline{\cup_{i}Y_{i,1}}^{\operatorname{Kol}},\ldots,\overline{\cup_{i}Y_{i,\ell}}^{\operatorname{Kol}}\big{)}

is a train in $X$ that is an upper bound for this chain. (For each $j$ , $\overline{\cup_{i}Y_{i,j}}^{\operatorname{Kol}}$ is an irreducible $\Delta$ -variety in $\sigma^{j-1}$ (X).) So by Zorn’s lemma, maximal trains of length $\ell$ always exist in $X$ .

For $\ell\in\mathbb{N}$ , consider the product

\textbf{X}_{\ell}:=X\times\sigma(X)\times\ldots\times\sigma^{\ell-1}(X)

and denote the projection of $\textbf{X}_{\ell}$ onto $\sigma^{i-1}(X)$ by $\varphi_{\ell,i}$ . Let

\mathbf{W}_{\ell}(X,\pi_{1},\pi_{2}):=\{p\in\textbf{X}_{\ell}:\pi_{2}(\varphi_{\ell,i}(p))=\pi_{1}(\varphi_{\ell,i+1}(p)),i=1,\ldots,\ell-1\}.

Lemma 6.15.

For every irreducible $\Delta$ -subvariety $W\subset\mathbf{W}_{\ell}$ ,

\big{(}\overline{\varphi_{\ell,1}(W)}^{\operatorname{Kol}},\ldots,\overline{\varphi_{\ell,\ell}(W)}^{\operatorname{Kol}}\big{)}

is a train in $X$ of length $\ell$ . Conversely, for each train $(Y_{1},\ldots,Y_{\ell})$ in $X$ , there exists an irreducible $\Delta$ -subvariety $W\subseteq\mathbf{W}_{\ell}$ such that $Y_{i}=\overline{\varphi_{\ell,i}(W)}^{\operatorname{Kol}}$ for each $i=1,\ldots,\ell$ .

Proof.

The proof follows [18, Lemma 6.8]. The first assertion is straightforward. We will prove the second assertion by induction on $\ell$ . For $\ell=1$ , $\mathbf{W}_{1}=X$ , and we can set $W=Y_{1}$ .

Let $\ell>1$ . Apply the inductive hypothesis to the train $(Y_{1},\ldots,Y_{\ell-1})$ and obtain an irreducible subvariety $Y^{\prime}\subset\mathbf{W}_{\ell-1}\subset\mathbf{X}_{\ell-1}$ . Then there is a natural embedding of $Y^{\prime}\times Y_{\ell}$ into $\mathbf{X}_{\ell}$ . Denote $(Y^{\prime}\times Y_{\ell})\cap\mathbf{W}_{\ell}$ by $\widetilde{Y}$ . Since $Y^{\prime}\subset\mathbf{W}_{\ell-1}$ ,

\widetilde{Y}=\{p\in Y^{\prime}\times Y_{\ell}\>|\>\pi_{2}\left(\varphi_{\ell,\ell-1}(p)\right)=\pi_{1}\left(\varphi_{\ell,\ell}(p)\right)\}.

Let

(3)

Z:=\overline{\pi_{2}\left(\varphi_{\ell-1,\ell-1}(Y^{\prime})\right)}=\overline{\pi_{1}(Y_{\ell})}.

Then we have a $(k,\Delta)$ -isomorphism

R_{Y^{\prime}}\otimes_{R_{Z}}R_{Y_{\ell}}\to R_{\widetilde{Y}}

under the $(k,\Delta)$ -algebra homomorphisms $i_{1}:R_{Z}\to R_{Y^{\prime}}$ and $i_{2}:R_{Z}\to R_{Y_{\ell}}$ induced by $\pi_{2}\circ\varphi_{\ell-1,\ell-1}$ and $\pi_{1}$ , respectively. Equality (3) implies that $i_{1}$ and $i_{2}$ are injective. Denote the fields of fractions of $R_{Y^{\prime}}$ , $R_{Y_{\ell}}$ , and $R_{Z}$ by $E$ , $F$ , and $L$ , respectively. Let $\mathfrak{p}$ be any prime differential ideal in $E\otimes_{L}F$ ,

R:=(E\otimes_{L}F)/\mathfrak{p},

and $\pi\colon E\otimes_{L}F\to R$ be the canonical homomorphism. Consider the natural homomorphism $i\colon R_{Y^{\prime}}\otimes_{R_{Z}}R_{Y_{\ell}}\to E\otimes_{L}F$ . Since $1\in i(R_{Y^{\prime}}\otimes_{R_{Z}}R_{Y_{\ell}})$ , the composition $\pi\circ i$ is a nonzero homomorphism. Since $i_{1}$ and $i_{2}$ are injective, the natural homomorphisms $i_{Y^{\prime}}\colon R_{Y^{\prime}}\to R_{Y^{\prime}}\otimes_{R_{Z}}R_{Y_{\ell}}$ and $i_{Y_{\ell}}\colon R_{Y_{\ell}}\to R_{Y^{\prime}}\otimes_{R_{Z}}R_{Y_{\ell}}$ are injective as well. We will show that the compositions

\pi\circ i\circ i_{Y^{\prime}}\colon R_{Y^{\prime}}\to R\quad\text{and}\quad\pi\circ i\circ i_{Y_{\ell}}\colon R_{Y_{\ell}}\to R

are injective. Introducing the natural embeddings $i_{E}\colon E\to E\otimes_{L}F$ and $j_{Y^{\prime}}\colon R_{Y^{\prime}}\to E$ , we can rewrite

\pi\circ i\circ i_{Y^{\prime}}=\pi\circ i_{E}\circ j_{Y^{\prime}}.

The homomorphisms $i_{E}$ and $j_{Y^{\prime}}$ are injective. The restriction of $\pi$ to $i_{E}(E)$ is also injective since $E$ is a field. Hence, the whole composition $\pi\circ i_{E}\circ j_{Y^{\prime}}$ is injective. The argument for $\pi\circ i\circ i_{Y_{\ell}}$ is analogous. Let

S:=\big{(}R_{Y^{\prime}}\otimes_{R_{Z}}R_{Y_{\ell}}\big{)}\big{/}\bigl{(}\mathfrak{p}\cap\big{(}R_{Y^{\prime}}\otimes_{R_{Z}}R_{Y_{\ell}}\big{)}\bigr{)},

which is a domain, and the homomorphisms $\pi\circ i\circ i_{Y^{\prime}}:R_{Y^{\prime}}\to S$ and $\pi\circ i\circ i_{Y_{\ell}}:R_{Y_{\ell}}\to S$ are injective. Let $F\subset k\{\textbf{W}_{\ell}\}$ be such that $S=k\{\textbf{W}_{\ell}\}/\sqrt{\langle F\rangle}^{(\infty)}$ . We now let $W$ be the $\Delta$ -subvariety of $\textbf{W}_{\ell}$ defined by $F=0$ . For every $i$ , $1\leqslant i<\ell$ , the homomorphism

\varphi_{\ell,i}^{\sharp}=(\pi\circ i\circ i_{Y^{\prime}})\circ\varphi_{\ell-1,i}^{\sharp}:R_{Y_{i}}\to R_{Y^{\prime}}\to S

is injective as a composition of two injective homomorphisms. Hence, the restriction $\varphi_{\ell,i}\colon W\to Y_{i}$ is dominant. ∎

Lemma 6.16.

Let $(X,\pi_{1},\pi_{2})$ be a triple with $X$ bounded by $n$ . Then, for every $\ell$ , the number of maximal trains of length $\ell$ in $X$ does not exceed $\operatorname{Components}(m,\ell n)$ .

Proof.

By Lemma 6.15, the number of maximal trains of length $\ell$ in $X$ is equal to the number of irreducible components of $\textbf{W}_{\ell}$ . By Theorem 5.13, this number does not exceed $\operatorname{Components}(m,\ell n)$ . ∎

Definition 6.17.

Let $(X,\pi_{1},\pi_{2})$ be a triple and $\omega(t)$ be a numeric polynomial. We define $B(X,\omega)\in\mathbb{Z}\cup\{\infty\}$ as the smallest value that is greater than the length of any train in $X$ with Kolchin polynomials at least $\omega$ .

Lemma 6.18.

Let $X$ be a differential variety bounded by $n$ such that $B(X,0)<\infty$ . Then $B(X,\omega_{X})$ does not exceed the number of components of $X$ plus one.

Proof.

Denote the number of components in $X$ by $N$ and assume that there is a train $(Y_{1},\ldots,Y_{N+1})$ with the Kolchin polynomial at least $\omega_{X}$ . Then each of $Y_{1},\sigma^{-1}(Y_{2}),\ldots,\sigma^{-N}(Y_{N+1})$ must be a component of $X$ , so there exist $1\leqslant i<j\leqslant N+1$ such that $Y_{j}=\sigma^{j-i}Y_{i}$ . Thus, there exists an infinite train $(Y_{1},\ldots,Y_{i},Y_{i+1},\ldots,Y_{j-1},\sigma^{j-i}(Y_{i}),\sigma^{j-i}(Y_{i+1}),\ldots)$ in $X$ . This contradicts to $B(X,0)<\infty$ . ∎

Lemma 6.19.

There exists a computable function $\operatorname{Iter}(n,D)$ such that, for every triple $(X,\pi_{1},\pi_{2})$ such that

•

$B(X,0)<\infty$
•

$X$ is bounded by $n$

and every numeric polynomial $\omega_{1}(t)>0$ , there exists a numeric polynomial $\omega_{2}(t)\geqslant 0$ such that

•

$\omega_{2}(t)<\omega_{1}(t)$ ;
•

$|\omega_{2}|\leqslant\operatorname{Iter}(n,B(X,\omega_{1}))$ ;
•

$B(X,\omega_{2})\leqslant\operatorname{Iter}(n,B(X,\omega_{1}))$ .

Proof.

The proof follows [18, Lemma 6.20]. Let $B_{1}:=B(X,\omega_{1})$ , and let $T$ be the number of maximal trains of length $B_{1}$ in $X$ . We set $B_{2}:=B_{1}+T$ . Lemma 6.16 implies that $T$ is bounded by $\operatorname{Components}(m,nB_{1})$ . Consider the fibered product $\mathbf{W}_{B_{1}}(X,\pi_{1},\pi_{2})$ , and, for each irreducible component $W$ in it, denote the corresponding train by $Y_{W}$ . We set (assuming $\max\varnothing=0$ )

\omega_{2}:=\max\bigl{\{}\omega_{Y_{W}}\mid\omega_{Y_{W}}<\omega_{1},W\text{ is a component of }\mathbf{W}_{B_{1}}\bigr{\}}.

We will show that $B(X,\omega_{2})\leqslant B_{1}+T$ . Assume that there is a maximal train $(Y_{1},\ldots,Y_{B_{2}})$ in $X$ with the Kolchin polynomial at least $\omega_{2}$ . Introduce $T+1$ trains $Z^{(1)},\ldots,Z^{(T+1)}$ of length $B_{1}$ in $X,\sigma(X),\ldots,\sigma^{T}(X)$ , respectively, such that for each $j$ ,

Z^{(j)}=\big{(}Z^{(j)}_{1},\ldots,Z^{(j)}_{T}\big{)}:=(Y_{j},\ldots,Y_{j+B_{1}-1}).

Then for each $j$ , consider a maximal train $\tilde{Z}^{(j)}$ of length $B_{1}$ containing $Z^{(j)}$ . So $\sigma^{-j+1}(\tilde{Z}^{(j)})$ is a maximal train of length $B_{1}$ in $X$ . There are two cases to consider:

(Case 1)

\big{\{}\omega_{Y_{W}}(t)\>\big{|}\>\omega_{Y_{W}}(t)<\omega_{1}(t),\;W\text{ is a component of }\mathbf{W}_{B_{1}}\big{\}}=\varnothing.

In this case, $\tilde{Z}^{(1)}$ is a train in $X$ with Kolchin polynomial at least $\omega_{1}$ . This contradicts the definition of $B(X,\omega_{1})$ .

(Case 2)

\big{\{}\omega_{Y_{W}}(t)\>\big{|}\>\omega_{Y_{W}}(t)<\omega_{1}(t),\;W\text{ is a component of }\mathbf{W}_{B_{1}}\big{\}}\neq\varnothing.

By the definition of $B(X,\omega_{1})$ , for every $j$ , $\omega_{\sigma^{-j+1}(\tilde{Z}^{(j)})}(t)<\omega_{1}(t)$ . This implies that, for each $j$ ,

\omega_{\sigma^{-j+1}(\tilde{Z}^{(j)})}(t)=\omega_{2}(t).

Since there are only $T$ maximal trains in $X$ of length $B_{1}$ , there exist $a<b$ such that

\sigma^{-a+1}(\tilde{Z}^{(a)})=\sigma^{-b+1}(\tilde{Z}^{(b)})=:Z.

Since $\omega_{Z}=\omega_{2}$ , there exists $\ell$ such that $\omega_{Z_{\ell}}=\omega_{2}$ . Since

\omega_{\sigma^{-a+1}({Z}^{(a)}_{\ell})}=\omega_{2}\quad\text{ and }\quad\sigma^{-a+1}({Z}^{(a)}_{\ell})\subseteq Z_{\ell}

we have $\sigma^{-a+1}({Z}^{(a)}_{\ell})=Z_{\ell}$ . Similarly, we can show $\sigma^{-b+1}({Z}^{(b)}_{\ell})=Z_{\ell}$ . Hence,

\sigma^{-a+1}(Y_{a+\ell-1})=\sigma^{-a+1}({Z}^{(a)}_{\ell})=\sigma^{-b+1}({Z}^{(b)}_{\ell})=\sigma^{-b+1}(Y_{b+\ell-1}).

Thus, we have $Y_{b+\ell-1}=\sigma^{b-a}(Y_{a+\ell-1})$ . This contradicts the fact that $B(X,0)<\infty$ .

It remains to show that $|\omega_{2}|$ is bounded by a computable function of $n$ and $B_{1}$ . Let $W$ be a component of $\mathbf{W}_{B_{1}}$ such that $\omega_{Y_{W}}=\omega_{2}$ . Let $Y_{W}=(Y_{W,1},\ldots,Y_{W,B_{1}})$ . There exists $1\leqslant i\leqslant B_{1}$ such that $\omega_{Y_{i}}=\omega_{2}$ . Since $Y_{i}$ is the Kolchin closure of a linear projection of a component of $\mathbf{W}_{B_{1}}$ and $\mathbf{W}_{B_{1}}$ is bounded by $B_{1}n$ , Lemma 6.6 implies that $|\omega_{2}|$ is bounded by a computable function of $n$ and $B_{1}$ .

Taking $\operatorname{Iter}(n,D)$ to be the maximum of the computable bounds for $B(X,\omega_{2})$ and $|\omega_{2}|$ , we conclude the proof. ∎

Definition 6.20.

Let $n$ be a positive integer and $\omega(t)$ be a numeric polynomial such that $\omega>0$ . We define $B(n,\omega)\in\mathbb{Z}\cup\{\infty\}$ as the smallest value such that, for every affine differential variety $X$ bounded by $n$ , if there exists a train in $X$ with Kolchin polynomial at least $\omega$ of length at least $B(n,\omega)$ , then there exists an infinite train in $X$ .

Proposition 6.21.

$B(n,0)$ is bounded by a computable function $A(n)$ .

Proof.

We recursively define the following function $G(n)$ on nonnegative integers

	$\displaystyle G(0):=\max\bigl{(}\operatorname{Components}(n,n)+1,\operatorname{KolchinProj}(n)\bigr{)},$
	$\displaystyle G(j+1):=\operatorname{Iter}(n,G(j)),\ \ j\geqslant 0.$

Consider a variety $X$ bounded by $n$ such that there is no infinite train in $X$ , that is $B(X,0)<\infty$ . Lemma 6.18 implies that $B(X,\omega_{X})-1$ does not exceed the number of components of $X$ . Hence, Theorem 5.13 implies that $B(X,\omega_{X})\leqslant\operatorname{Components}(n,n)+1$ . Lemma 6.6 implies that $|\omega_{X}|\leqslant\operatorname{KolchinProj}(n)$ . Repeatedly applying Lemma 6.19, we obtain a sequence of numeric polynomials

\omega_{0}:=\omega_{X}>\omega_{1}>\omega_{2}>\ldots

such that, for every $1\leqslant i\leqslant L$ , we have $B(X,\omega_{i})\leqslant G(i)$ and $|\omega_{i}|\leqslant G(i)$ . Since the Kolchin polynomial are well-ordered, there exists $L$ such that $\omega_{L}=0$ . Proposition 6.7 implies that $L\leqslant\operatorname{Len}_{G}$ . Hence, $B(X,0)\leqslant G(\operatorname{Len}_{G})$ , where the right-hand side is a computable function of $n$ . Set $A(n):=G(\operatorname{Len}_{G})$ , then $B(n,0)\leqslant A(n)$ . ∎

Corollary 6.22.

For all $r$ , $m$ and $s\in\mathbb{Z}_{\geqslant 0}$ , and a set of $\Delta$ - $\sigma$ polynomials $F\subset k[\bm{y}_{s}]$ with $|\Delta|=m$ , $\deg F\leqslant s$ and $|\bm{y}|=r$ , $F=0$ has a sequence solution in $K^{\mathbb{Z}}$ if and only if $F=0$ has a partial solution of computable length $A(\max\{r,m,s\})$ .

Proof.

The proof is as in [18, Corollary 6.21], as follows. Let $X\subset\mathbb{A}^{H}$ be the $\Delta$ -variety defined by $F=0$ regarded as a system of $\Delta$ -equations in $\bm{y},\sigma(\bm{y}),\ldots,\sigma^{h}(\bm{y})$ , where $H=n(h+1)$ . By Lemmas 6.12 and 6.14, $F=0$ has a partial solution of length $D$ (resp. $F=0$ has a solution in $K^{\mathbb{Z}}$ ) if and only if there exists a train of length $D$ in $X$ (resp., there exists an infinite train in $X$ ). By Proposition 6.21, if there exists a train of length $D:=A(\max\{r,m,s\})$ in $X$ , then there exists a infinite train in $X$ . So the assertion holds. ∎

6.3. Upper bound for delay PDEs

We now state and prove the main result of this section which generalizes [18, Theorem 3.1] to delay PDEs.

Theorem 6.23 (Effective elimination for delay PDEs).

For all non-negative integers $r$ , $m$ , and $s$ , there exists a computable $B=B(r,m,s)$ such that, for all:

•

non-negative integers $q$ and $t$ ,
•

$\Delta$ - $\sigma$ -fields $k$ with $\operatorname{char}k=0$ and $|\Delta|=m$ ,
•

sets of $\Delta$ - $\sigma$ -polynomials $F\subset k[\bm{x}_{t},\bm{y}_{s}]$ , where $\bm{x}=x_{1},\ldots,x_{q}$ , $\bm{y}=y_{1},\ldots,y_{r}$ , and $\deg_{\bm{y}}F\leqslant s$ ,

we have

\big{\langle}\sigma^{i}(F)\mid i\in\mathbb{Z}_{\geqslant 0}\big{\rangle}^{(\infty)}\cap k[\bm{x}_{\infty}]\neq\{0\}\iff\langle\sigma^{i}(F)\mid i\in[0,B]\big{\rangle}^{(B)}\cap k[\bm{x}_{B+t}]\neq\{0\}.

Proof.

The proof closely follows [18, Theorem 6.22]. The “ $\impliedby$ ” implication is straightforward. We will prove the “ $\implies$ ” implication. For this, let $A:=A(\max\{r,m,s\})$ from Corollary 6.22, and let $B$ be a computable bound obtained from [10, Theorem 3.4] with

m\leftarrow m,\ \ n\leftarrow r(A+s+1),\ \ h\leftarrow s,\ \ \text{and}\ \ D\leftarrow s.

By assumption,

(4)

1\in\big{\langle}\sigma^{i}(F)\mid i\in\mathbb{Z}_{\geqslant 0}\big{\rangle}^{(\infty)}\cdot k(\bm{x}_{\infty})[\bm{y}_{\infty}].

Suppose that

(5)

\langle\sigma^{i}(F)\mid i\in[0,A]\big{\rangle}^{(B)}\cap k[\bm{x}_{B+t}]=\{0\}.

1\in\big{\langle}\sigma^{i}(F)\mid i\in[0,A]\big{\rangle}^{({B})}\cdot k(\bm{x}_{B+t})[\bm{y}_{\infty,A+s}],

then there would exist $c_{i,j}\in k(\bm{x}_{B+t})[\bm{y}_{\infty,A+s}]$ such that

(6)

1=\sum\limits_{\theta\in\Theta_{\Delta}(B)}\sum\limits_{j=0}^{A}\sum\limits_{f\in F}c_{i,j}\theta(\sigma^{j}(f)).

Multiplying equation (6) by the common denominator in the variables $\bm{x}_{B+t}$ , we obtain a contradiction with (5). Hence, by [10, Theorem 3.4],

1\notin\big{\langle}\sigma^{i}(F)\mid i\in[0,A]\big{\rangle}^{(\infty)}\cdot k(\bm{x}_{B+t})[\bm{y}_{\infty,A+s}].

By Lemma 6.8, there exists a differentially closed $\Delta$ - $\sigma^{*}$ -field extension $L\supset k(\bm{x}_{\infty})\supset k(\bm{x}_{B+t})$ . Then differential Nullstellensatz implies that the system of differential equations

\{\sigma^{i}(F)=0\mid i\in[0,A]\}

in the unknowns $\bm{y}_{\infty,A+s}$ has a solution in $L$ . Then the system $F=0$ has a partial solution of length $A+1$ in $L$ . Now from (4), we see that the system $F=0$ has no solutions in $L^{\mathbb{Z}}$ . Together with the existence of a partial solution of length $A+1$ , this contradicts to Corollary 6.22. ∎

Acknowledgments

This work was partially supported by the NSF grants CCF-1564132, CCF-1563942, DMS-1760448, DMS-1760413, DMS-1853650, DMS-1853482, and DMS-1800492; the NSFC grants (11971029, 11688101) and the fund of Youth Innovation Promotion Association of CAS. We are grateful to the referees for numerous insightful comments, which helped us substantially improve the paper.

References

Bächler et al. [2012] T. Bächler, V. Gerdt, M. Lange-Hegermann, and D. Robertz. Algorithmic Thomas decomposition of algebraic and differential systems. Journal of Symbolic Computation, 47(10):1233–1266, 2012. URL https://doi.org/10.1016/j.jsc.2011.12.043.
Blum et al. [1998] L. Blum, F. Cucker, M. Shub, and S. Smale. Complexity and Real Computation. Springer, 1998. URL https://doi.org/10.1007/978-1-4612-0701-6.
Boulier et al. [2009] F. Boulier, D. Lazard, F. Ollivier, and M. Petitot. Computing representations for radicals of finitely generated differential ideals. Applicable Algebra in Engineering, Communication and Computing, 20:73–121, 2009. URL https://doi.org/10.1007/s00200-009-0091-7.
Chapuis and Koiran [1999] O. Chapuis and P. Koiran. Saturation and stability in the theory of computation over the reals. Annals of Pure and Applied Logic, 99(1):1–49, 1999. URL https://doi.org/10.1016/S0168-0072(98)00060-8.
Gao et al. [2009a] X.-S. Gao, Y. Luo, and C. Yuan. A characteristic set method for ordinary difference polynomial systems. Journal of Symbolic Computation, 44(3):242–260, 2009a. URL https://doi.org/10.1016/j.jsc.2007.05.005.
Gao et al. [2009b] X.-S. Gao, J. Van der Hoeven, C.-M. Yuan, and G.-L. Zhang. Characteristic set method for differential-difference polynomial systems. Journal of Symbolic Computation, 44(9):1137–1163, 2009b. URL https://doi.org/10.1016/j.jsc.2008.02.010.
Gerdt and Robertz [2019] V. Gerdt and D. Robertz. Algorithmic approach to strong consistency analysis of finite difference approximations to PDE systems. In ISSAC ’19: Proceedings of the 2019 on International Symposium on Symbolic and Algebraic Computation, pages 163–170. ACM Press, 2019. URL https://doi.org/10.1145/3326229.3326255.
Golubitsky et al. [2009] O. Golubitsky, M. Kondratieva, A. Ovchinnikov, and A. Szanto. A bound for orders in differential Nullstellensatz. Journal of Algebra, 322(11):3852–3877, 2009. URL https://doi.org/10.1016/j.jalgebra.2009.05.032.
Goode [1994] J. B. Goode. Accessible telephone directories. The Journal of Symbolic Logic, 59:92–105, 1994. URL https://www.jstor.org/stable/2275252.
Gustavson et al. [2016] R. Gustavson, M. Kondratieva, and A. Ovchinnikov. New effective differential Nullstellensatz. Advances in Mathematics, 290:1138–1158, 2016. URL http://dx.doi.org/10.1016/j.aim.2015.12.021.
Harrison-Trainor et al. [2012] M. Harrison-Trainor, J. Klys, and R. Moosa. Nonstandard methods for bounds in differential polynomial rings. Journal of Algebra, 360:71–86, 2012. URL https://doi.org/10.1016/j.jalgebra.2012.03.013.
Heintz [1983] J. Heintz. Definability and fast quantifier elimination in algebraically closed fields. Theoretical Computer Science, 24(3):239–277, 1983. URL http://dx.doi.org/10.1016/0304-3975(83)90002-6.
Kolchin [1973] E. Kolchin. Differential Algebra and Algebraic Groups. Academic Press, New York, 1973.
Léon Sánchez [2016] O. Léon Sánchez. On the model companion of partial differential fields with an automorphism. Israel Journal of Mathematics, 212:419–442, 2016. URL https://doi.org/10.1007/s11856-016-1292-y.
León Sánchez [2019] O. León Sánchez. Estimates for the coefficients of differential dimension polynomials. Mathematics of Computation, 88:2959–2985, 2019. URL https://doi.org/10.1090/mcom/3429.
Léon Sánchez and Moosa [2016] O. Léon Sánchez and R. Moosa. The model companion of differential fields with free operators. Journal of Symbolic Logic, 81(2):493–509, 2016. URL https://doi.org/10.1017/jsl.2015.76.
Levin [2008] A. Levin. Difference algebra, volume 8 of Algebra and Applications. Springer, New York, 2008. URL http://dx.doi.org/10.1007/978-1-4020-6947-5.
Li et al. [2018] W. Li, A. Ovchinnikov, G. Pogudin, and T. Scanlon. Elimination of unknowns for systems of algebraic differential-difference equations, 2018. URL https://arxiv.org/abs/1812.11390.
Marker [2002] D. Marker. Model theory: An introduction. Springer-Verlag New York, 2002. URL https://doi.org/10.1007/b98860.
McAloon [1984] K. McAloon. Petri nets and large finite sets. Theoretical Computer Science, 32(1-2):173–183, 1984. URL https://doi.org/10.1016/0304-3975(84)90029-X.
McGrail [2000] T. McGrail. The model theory of differential fields with finitely many commuting derivations. Journal of Symbolic Logic, 65(2):885–913, 2000. URL https://doi.org/10.2307/2586576.
Mikhalev et al. [1999] A. V. Mikhalev, A. Levin, E. Pankratiev, and M. Kondratieva. Differential and Difference Dimension Polynomials, volume 461 of Mathematics and Its Applications. Springer Netherlands, 1999. URL https://doi.org/10.1007/978-94-017-1257-6.
Moosa and Scanlon [2014] R. Moosa and T. Scanlon. Model theory of fields with free operators in characteristic zero. Journal of Mathematical Logic, 14(2):1450009, 2014. URL https://doi.org/10.1142/s0219061314500093.
Papadimitriou [1993] C. H. Papadimitriou. Computational Complexity. Pearson, 1993.
Rust and Reid [1997] C. J. Rust and G. J. Reid. Rankings of partial derivatives. In Proceedings of the 1997 international symposium on Symbolic and algebraic computation - ISSAC’97, 1997. URL https://doi.org/10.1145/258726.258737.
Simmons and Towsner [2019] W. Simmons and H. Towsner. Proof mining and effective bounds in differential polynomial rings. Advances in Mathematics, 343:567–623, 2019. URL https://doi.org/10.1016/j.aim.2018.11.026.
van den Dries and Shmidt [1984] L. van den Dries and K. Shmidt. Bounds in the theory of polynomial rings over fields. a nonstandard approach. Inventiones mathematicae, 76:77–91, 1984. URL https://doi.org/10.1007/BF01388493.

Algorithms yield upper bounds in differential algebra

Abstract.

2010 Mathematics Subject Classification:

1. Introduction

2. Basic notions and notaiton

Definition 2.1 (Differential-difference rings).

Definition 2.2 (Differential polynomials).

Definition 2.3 (Differential-difference polynomials).

3. Main results

Theorem 3.1 (Upper bound for irreducible components for PDEs).

Theorem 3.2 (Upper bound for elimination in delay PDEs).

Corollary 3.3 (Effective Nullstellensatz for delay PDEs).

Theorem 3.4 (Algorithm yields a bound, stated precisely as Theorem 4.5).

4. Bounds for the output size of algorithms over complete theories

4.1. Setup

Definition 4.1 (TT-oracle).

Definition 4.2 (Total algorithm over TT).

4.2. Auxiliary bound and result

Lemma 4.3.

Proof.

Lemma 4.4.

Proof.

4.3. Main result

Theorem 4.5.

Remark 4.6.

Proof.

5. Applications to differential algebra

5.1. Preparation

Notation 5.1.

Notation 5.2.

Notation 5.3.

Definition 5.4.

Notation 5.5.

Remark 5.6 (Defining a ranking).

Definition 5.7 (Characteristic sets).

Lemma 5.8.

Proof.

Proposition 5.9.

Proof.

5.2. Bounds

Theorem 5.10 (Upper bound for Rosenfeld-Gröbner algorithm).

Proof.

Corollary 5.11.

Proof.

Lemma 5.12.

Proof.

Theorem 5.13 (Upper bound for the components of a differential variety and their number).

Proof.

Remark 5.14.

6. Application to delay PDEs

6.1. Bounds for Kolchin polynomials for algebraic PDEs

Definition 6.1.

Definition 6.2.

Notation 6.3.

Definition 6.4.

Definition 6.5.

Lemma 6.6.

Proof.

Proposition 6.7.

Proof.

6.2. Trains of varieties, partial solutions, and their upper bounds

Lemma 6.8.

Proof.

Notation 6.9.

Definition 6.10 (Partial solutions).

Definition 6.11.

Lemma 6.12.

Proof.

Definition 6.13.

Lemma 6.14.

Proof.

Claim.

Lemma 6.15.

Proof.

Lemma 6.16.

Proof.

Definition 6.17.

Lemma 6.18.

Proof.

Lemma 6.19.

Algorithms yield upper bounds
in differential algebra

Definition 4.1 ( $T$ -oracle).

Definition 4.2 (Total algorithm over $T$ ).