A new algorithm for computing regular representations for radicals of parametric differential ideals

Abstract

The regular representation of the radical of a differential ideal has various applications such as solving the membership problem, computing Taylor expansion of solutions, finding the Lie symmetries, and solving dynamical systems. Presently, there is no algorithm giving all regular representations for all possible values of the parameters for a polynomial differential ideal with parametric coefficients. In this article, we propose a new algorithm that computes all different regular representations with respect to all possible states of the parameters. Also, we present an efficient criterion to reduce some ineffectual computations. Implementing the algorithm in Maple and several examples reported in this article demonstrate the high efficiency of the algorithm.

Keywords:

• differential algebra
• parametric differential system
• Rosenfeld-Gröbner algorithm

MR Subject classifications:

• 68W30
• 12H05
• 35C11

PUBLIC INTEREST STATEMENT

Studying differential equations from an algebraic point of view is the main goal of the differential algebra. Computing regular representations for differential ideal generated by differential systems is an algebraic tool in this field that analyses the solutions of polynomial differential systems. In this article, we present a new algorithm that computes regular representations for parametric differential systems that has various applications such as biological modeling, dynamical systems, etc.

1. Introduction

Differential algebra was initially founded in the early 20th century to study a system of ordinary or partial differential equations, from a totally algebraic point of view. This mathematical approach was developed by Ritt (1950) and Kolchin (1973) who also prepared a computational algebraic tool for solving partial differential equation (PDE) systems. The well-known Rosenfeld-Gröbner algorithm is one of the most important algorithms in this regard, which indeed can be considered as the beginning point of the computational differential algebra. This algorithm analyses a polynomial differential system in a differential algebraic mode and gives a regular representation of the radical differential ideal generated by this system. The algorithm has various applications for instance in Geometry (Sabzevari, Hashemi, Alizadeh, & Merker, 2016), finding the Lie symmetries of differential equations (Hydon, 2000) and theory of differential equations (Mansfield & Clarkson, 1997). The Rosenfeld-Gröbner algorithm was first described by Boulier (1994) and improved by Boulier, Lazard, Ollivier, and Petitot (1995) thereafter. The input of this algorithm is a polynomial differential system in a differential ring with constant coefficients while its output is a representation of radical of the differential ideal, generated by the input system, as a finite intersection of radical differential ideals. The computed representation allows testing membership in the radical of the ideal generated by given system and also computing Taylor expansions of solutions of this system (Boulier, Lazard, Ollivier, & Petitot, 2009).

As mentioned before, the input of this algorithm is a differential system with constant coefficients. However, sometimes, it is necessary to determine such a representation for a parametric differential system; a differential system that its coefficients depend on some parameters. For instance this system can be used for biological modelling (Boulier, 2007), dynamical systems (Harrington & Van Gorder, 2017; Jauberthie, Trave-Massuyes, & Verdiere, 2016) and so on. In this regard, even if the coefficients field is extended by these parameters, the output of the Rosenfeld-Gröbner algorithm may not include all of the representations for all possible values of the parameters. For example, consider the following differential system in which its coefficients depend on the parameters $a,b$ and $c$.

$P_0=\left\{\begin{array}{c}a{\left(\frac{{\mathrm{\partial }}^2}{\mathrm{\partial }x\mathrm{\partial }y}v(x,y)\right)}^2+3bu(x,y)=0\\ \left(\frac{{\mathrm{\partial }}^3}{\mathrm{\partial }x\mathrm{\partial }{y}^2}v(x,y)\right)\left(\frac{\mathrm{\partial }}{\mathrm{\partial }x}u(x,y)\right)-v(x,y)=0\\ c\left(\frac{\mathrm{\partial }}{\mathrm{\partial }x}v(x,y)\right)+u(x,y)+3=0\end{array}\right.$

To simplify, we use indices:

$P_0=\left\{\begin{array}{c}a{v}_{x,y}^2+3bu=0\\ v_{x,y,y}{u}_x-v=0\\ c{v}_x+u+3=0\end{array}\right.$

In the extended coefficient field by the parameters, with respect to the orderly ranking with considering $u\prec v$ and the graded lexical order $y<x$, the output of the Rosenfeld-Gröbner algorithm for the system $P_0$ is empty. But, is this system really inconsistent for arbitrary values of the parameters? It can be easily shown that the answer is “no”. This system has the following representations for different values of the parameters $a$ and $b$. When $b=0$ and $a\ne 0$ we have:

$\sqrt{[P_0]}=[v,u+3]$

and also when $b=a=0$ and $c\ne 0$ we have:

$\sqrt{[P_0]}=[cv+u_x{u}_{y,y},u_x{u}_{x,y,y}+u_{x,x}{u}_{y,y}-u-3]:\{u_x{\}}^{\mathrm{\infty }}\cap [v,u+3]$

Presently, there is no context which introduces an algorithm giving all representations for all possible values of the parameters for a parametric system. Although, Boulier (2018) explains how the Rosenfeld-Gröbner algorithm can manage different types of the parameters .This context was written from our demand and it was never published.

The main goal of this article is to obtain the distinct representations for all possible values of the parameters. According to this viewpoint, a case is a set of polynomial equalities and inequalities over the parameters accepting the same representation. Here, we present an algorithm with branching style that its root vertex corresponds to the inputted system. The inputted system is a differential system whose coefficients depend on some parameters. This algorithm branches some vertices according to possible values of the parameters and outputs the distinct representation depending on these values of parameters. Moreover, in this algorithm we apply a new criterion which can detect and delete a chain of the redundant computations.

The remainder of this article is organised as follows. We give an introduction to differential algebra in Section 2. In Section 3, we briefly describe the Rosenfeld-Gröbner algorithm. Section 4 describes the new algorithm to decompose a parametric differential system. Finally, some examples are presented in Section 5.

2. Differential algebra

In this section, we review some preliminaries concept of differential algebra. More details can be found in (Hubert, 2000; Kolchin, 1973; Ritt, 1950; Sit, 2002). In the following, we assume that $K$ is a field of characteristic zero.

Definition 2.1. A differential ring is a commutative ring $\mathcal{R}$ associated with a finite set of derivations $\left\{{\delta }_1,\dots ,{\delta }_m\right\}$, which commute with each other and satisfy the following equalities:

where $1\le i\le m$ and $r_1,r_2\in \mathcal{R}$. In a special case, if $m=1$, then $\mathcal{R}$ is called an ordinary differential ring and if $m>1$, then $\mathcal{R}$ is called a partial differential ring.

A differential ideal $I$ of $\mathcal{R}$ is an ideal which is also closed under the action of derivations; i.e., ${\delta }_i(I)\subseteq I$ for each $1\le i\le m$.

We will use $\mathrm{\Theta }$ to denote the free multiplicative semi-group generated by the set $\left\{{\delta }_1,\dots ,{\delta }_m\right\}$. It is easy to see that the elements of $\mathrm{\Theta }$, which are called derivative operators of $\mathcal{R}$, are in the form of $\theta =\delta {}_1^{d_1}\delta {}_2^{d_2}\cdots \delta {}_m^{d_m}$, where each $d_i$ belongs to $\mathbf{N}\cup \left\{0\right\}$ and the sum $ord(\theta )={\sum }_{i=1}^m{d}_i$ is the order of $\theta$.

For each $S\subset \mathcal{R}$, the smallest subset of $\mathcal{R}$ containing $S$, which is also stable under the action of $\mathrm{\Theta }$ is denoted by:

$\mathrm{\Theta }S=\{\theta (s)|\theta \in \mathrm{\Theta },s\in S\}.$

We denote by $(S)$ ($resp.[S]$) the smallest algebraic (resp. differential) ideal of $\mathcal{R}$ containing $S$. If ${\mathcal{R}}_0$ is a subring of $\mathcal{R}$, using ${\mathcal{R}}_0[S]$ (resp. ${\mathcal{R}}_0\left\{S\right\}$), we denote the smallest algebraic (resp. differential) subring of ${\mathcal{R}}_0$ containing $S$ and ${\mathcal{R}}_0$ that are generated by $S$ on ${\mathcal{R}}_0$. As a simple fact, we apply an algebraic approach on differential ideals and subrings due to $[S]=(\mathrm{\Theta }S)$ and ${\mathcal{R}}_0\left\{S\right\}={\mathcal{R}}_0[\mathrm{\Theta }S]$.

Now, we present the following definition which has an important role in the main concepts.

Definition 2.2. Consider a differential ideal $I$ and a set of differential polynomials $S$ from $\mathcal{R}$. The saturation ideal of $I$ by $S$ is defined as follows:

$I:S^{\mathrm{\infty }}=\{p\in \mathcal{R}|sp\in Iforsomes\in S^{\mathrm{\infty }}\},$

where $S^{\mathrm{\infty }}$ denotes the smallest multiplicative family of $\mathcal{R}$ which contains $S$.

In the sequel, we will deal with a differential polynomial ring $\mathcal{R}=K\left\{u_1,\dots ,u_n\right\}$ that is a differential ring generated by $U=\left\{u_1,...,u_n\right\}$ on $K$, where $K$ is a differential field that for each $\theta$ in $\mathrm{\Theta }$ and each constant $k$ in $K$ we have $\theta (k)=0$. In this ring, each $u_i$ (resp. $\theta u_i$) is called an indeterminate (resp. a derivative).

In the next definition, we recall the concept of ranking that will be used to compare derivatives. In fact, rankings in a differential ring play a similar role of monomial orderings in polynomial rings.

Definition 2.3. Let $\mathcal{R}$ be a differential polynomial ring. Each ranking over $\mathcal{R}$ is an ordering $\prec$ over $\mathrm{\Theta }U$ such that for each derivation $\theta$ and $v,w\in \mathrm{\Theta }U$:

• $v\prec \theta v$, and

• $v\prec w$ implies $\theta v\prec \theta w$.

Orderings are divided into two different types: Rankings for which $ord(\theta )<ord(\varphi )$ implies that $\theta (v)\prec \varphi (w)$, which are called orderly, and those for which $v\prec w$ concludes $\theta v\prec \varphi w$, which are called elimination rankings.

Now, we introduce some terms of differential polynomials. Let $p\in \mathcal{R}=K\left\{u_1,...,u_n\right\}$ be a differential polynomial and $\prec$ be a ranking over $\mathrm{\Theta }U$. The leader $ld(p)$ of $p$ is the highest derivative appearing in $p$ with respect to $\mathcal{R}$. If $ld(p)=u$ and $d$ is the degree of $u$ in $p$, then the initial $i_p\in \mathcal{R}$ is defined to be the coefficient of $u^d$ in $p$. The separant $s_p$ of $p$ is the polynomial $\mathrm{\partial }p/\mathrm{\partial }u$. The rank of $p$ is the monomial $u^d$, which is denoted by $rankp$. The rank of a set of polynomials is similarly the set of ranks of the elements of the set. Let $A=\left\{p_1,\dots ,p_m\right\}$ and $A^{\prime }=\left\{p_1^{\prime },\dots ,p_{m\prime }^{\prime }\right\}$ be two non-empty subsets of $\mathcal{R}\mathrm{\setminus }K$. Assume that, $rank{p}_i\underset{\_}{\prec }rank{p}_{i+1}$ and $rankp{}_j^{\prime }\underset{\_}{\prec }rankp{}_{j+1}^{\prime }$ for all $i<m$, $j<m^{\prime }$. The set $A$ is said to be of lower rank than $A^{\prime }$, when either there exist some $i\le min(m,m^{\prime })$ such that $rank{p}_i<rankp{}_i^{\prime }$ and $rank{p}_j=rank{p}_j^{\prime }$ for $1\le j<i$ or $m>m^{\prime }$ and rank $p_j=rankp{}_j^{\prime }$ for $1\le j\le m^{\prime }$. Two sets of polynomials that none of them is of lower rank than the other one are called of the same rank.

For any subset $A$ of $\mathcal{R}\mathrm{\setminus }K$, we denote the set of the initials (resp. separants) of the elements of $A$ by $I_A$ (resp. $S_A$). Let now $H_A=I_A\cup S_A$. Then, $H_A^{\mathrm{\infty }}$ denotes the set of all the power products of the initials and the separants of the elements of $A$.

Definition 2.4. Consider two differential polynomials $p$ and $q$ in the differential ring $\mathcal{R}=K\left\{u_1,\dots ,u_n\right\}$ and let $u^d$ be the rank of $p$. Polynomial $q$ is called partially reduced with respect to $p$ if no proper derivative of $u$ appears in $q$. Also, if the degree of $q$ in $u$ is less than $d$ we say that $q$ is algebraically reduced with respect to $p$. A polynomial $q$ is called reduced with respect to the polynomial $p$ if $q$ is partially and algebraically reduced with respect to $p$.

A set $A\subset \mathcal{R}\mathrm{\setminus }K$ is said to be autoreduced if any element of $A$ is reduced with respect to any other element of the set. Also if the elements of $A$ are pairwise partially reduced and the leaders of them are pairwise different, we say that $A$ is differentially triangular.

One of the important procedures in the context of differential algebra is the way of reducing a differential polynomial with respect to an autoreduced set. Let $p$ be a differential polynomial and $A=\left\{p_1,\dots ,p_s\right\}$ be an autoreduced set. By Ritt’s algorithm of reduction (see Kolchin 1973), there exists a differential polynomial $r$ and non-negative integers $b_1,\dots ,b_s$ and $a_1,\dots ,a_s$ such that

$r\equiv i_{p_1}^{a_1}\cdots i_{p_s}^{a_s}{s}_{p_1}^{b_1}\cdots s_{p_s}^{b_s}p(mod[A]),$

where $i_{\mathrm{\ell }}$ and $s_{\mathrm{\ell }}$ denote the initial and the separant of $p_{\mathrm{\ell }}$ respectively, and $r$ is reduced with respect to $A$. If $r$ is just partially reduced with respect to $A$, then we can write

$r\equiv s_{p_1}^{b_1}\cdots s_{p_s}^{b_s}p(mod[A]).$

For the simplicity in notations, we denote $r$ by $pfullremA$ (resp. $ppremA$), if $r$ is reduced (resp. partially reduced) with respect to $A$.

Now, we explain the concept of $\mathrm{\Delta }-$polynomial of two differential polynomials, which plays a similar role to $S-$polynomial in algebraic polynomials ring. Before that, we need to know the definition of $criticalpairs$ (Boulier et al., 2009). Also, we should state that for each derivative $\theta u$ and $\varphi u$ of the same differential indeterminate $u$, the least common derivative is denoted by $lcd(\theta u,\varphi u)$, which equals to $lcm(\theta ,\varphi )u$.

Definition 2.5. A set $\left\{p_1,p_2\right\}$ of differential polynomials is said to be a critical pair if $p_1$ and $p_2$ are distinct and the leaders of them have common derivatives. If $A$ is a set of differential polynomials then $critical-pairs(A)$ denotes the set of all the pairs which can be formed between any two elements of $A$.

Definition 2.6. Let $\left\{p_1,p_2\right\}$ be a critical pair and denote ${\theta }_{1}u=ld(P_1)$, ${\theta }_{2}u=ld(p_2)$ and ${\theta }_{12}u=lcd({\theta }_1{u}_1,{\theta }_2{u}_2)$. The $\mathrm{\Delta }-$polynomial $\mathrm{\Delta }(p_1,p_2)$ of $p_1$ and $p_2$ is defined as follows:

$\mathrm{\Delta }(p_1,p_2)=s_{p_2}\frac{{\theta }_{12}}{{\theta }_1}{p}_1-s_{p_1}\frac{{\theta }_{12}}{{\theta }_2}{p}_2$

If $A$ is a subset of $\mathcal{R}$, then the set of all $\mathrm{\Delta }-pols(A)$ denotes the set of all possible $\mathrm{\Delta }-$polynomials which can be formed between any two elements of $A$.

Here, we give the definition of solved pairs, which was defined earlier by Boulier et al. (2009) for the first time.

Definition 2.7. A critical pair $\left\{p_1,p_2\right\}$ is said to be solved by a differential system of equations and inequations $A=0$ and $S\ne 0$ if there exists a derivative $v<lcd(p_1,p_2)$ such that:

$\mathrm{\Delta }(p_1,p_2)\in A_v:(S\cap {\mathcal{R}}_v{)}^{\mathrm{\infty }}$

where $A_v=\{\theta p|p\in A,\theta \in \mathrm{\Theta },ld(\theta p)\le v\}$ and $S\cap {\mathcal{R}}_v=\{p\in A|ld(p)\le v\}$.

One can apply the following criterion (lemma 6 in Boulier et al., 2009) to recognise the solved pairs:

Lemma 2.8. Let $\left\{p_1,p_2\right\}$ be a critical pair such that $ld{p}_1\ne ld{p}_2$. If $\mathrm{\Delta }(p_1,p_2)$ is reduced to zero by a set $A$ and $S$ is a set of inequations containing $H_A$; then, the critical pair $\left\{p_1,p_2\right\}$ is solved by the system $A=0$ and $S\ne 0$.

Definition 2.9. Let $\mathcal{R}=K\left\{U\right\}$ be a differential polynomial ring and $\prec$ be a ranking over $\mathrm{\Theta }U$. A differential system of equations $A=0$ and inequations $S\ne 0$ of $\mathcal{R}$ is said to be a regular differential system with respect to $\prec$ if:

• $A$ is differentially triangular

• $S$ contains the separants of the elements of $A$ and it is partially reduced with respect to $A$

• All critical pairs of $A$ are solved by the system $A=0$ and $S\ne 0$ (coherent property)

The differential ideal $[A]:S^{\mathrm{\infty }}$ is called the regular differential ideal defined by the system. Moreover, the system is considered inconsistent if $[A]:S^{\mathrm{\infty }}$ equals to $\mathcal{R}$, and consistent otherwise.

At the end of this section, let us mention some properties and a brief explanation of Gröbner bases for an algebraic ideal (see Becker & Weispfenning, 1991; Cox, Little, & O’Shea, 1992), which is applied in the next sections. Consider $R=K[x_1,\dots ,x_n]$ as a polynomial ring and $\prec {}_{\bar{x}}$ as a term ordering over $R$. Note that the reduction in the polynomial ring is algebraic and the remainder of the reduction is denoted by $algrem$.

If $G$ is a Gröbner basis with respect to $\prec {}_{\bar{x}}$ for ideal $I=(A)$ then we have:

• $I=(G)$, which means that $G$ is also a generator for the ideal $I$.

• If $G$ is also reduced, then it is unique with respect to the ordering $\prec {}_{\bar{x}}$; in other words, for an ideal, there is just one reduced Gröbner basis with respect to certain ordering.

• The ideal $I$ is equal to $R$ (the system $A=0$ has no answer) if and only if $1\in G$ or the reduced Gröbner basis is equal with the set $\left\{1\right\}$.

Note that having the following lemma (Boulier et al., 2009), even if the set of variables is infinite, Gröbner bases can be computed of finitely generated ideals of $K[x_1,...,x_n]$. So, we can compute Gröbner bases of (non-differential) ideals in differential polynomial rings.

Lemma 2.10. Let $I$ be an ideal of a ring $R$ and $x$ be transcendental over $R$. If $\phi$ denotes the canonical ring homomorphism $\phi :R\to R[x]$, then ${\phi }^{-1}(\phi (r))=r$.

Consider the system of equations $A=\left\{p_1,\dots ,p_n\right\}$ and inequations $S=\left\{h_1,\dots ,h_m\right\}$ of $R$. To get a Gröbner basis $G$ of $(A):S^{\mathrm{\infty }}$, we just need to run the following steps:

1. Introduce a new set $\left\{z_1,...,z_m\right\}$ of unknowns and rewrite each inequation $h_i\ne 0$ as $h_i{z}_i=1$.

2. Compute a Gröbner basis $G_0$ of the ideal generated with the set

   $\left\{p_1,\dots ,p_n,h_1{z}_1-1,\dots ,h_m{z}_m-1\right\}$

   with respect to any ordering that eliminates the $z$’s.

3. Construct $G$ by selecting the members of $G_0$ that do not involve $z_i$ for any $1\le i\le m$ ($G=G_0\cap R$).

3. Rosenfeld-Gröbner algorithm

In this section, we describe the Rosenfeld-Gröbner algorithm (see Boulier et al., 2009 for more details). Let $P_0\subset \mathcal{R}$, the Rosenfeld-Gröbner algorithm decomposes the differential radical ideal $\sqrt{[P_0]}$ as a finite intersection of regular differential ideals $P_i$’s:

$\sqrt{[P_0]}=P_1\cap \cdots \cap P_t$

Each regular differential ideal $P_i$ is presented by two sets of differential polynomial equations $A_i$ and differential polynomial inequations $S_i$ such that $P_i=[A_i]:S_i^{\mathrm{\infty }}$. If $G_i$ is a Gröbner basis for the saturation ideal $P_i$, so $G_i$ reduces to zero a differential polynomial $p$ if and only if $p$ belongs to $P_i$. Although, the ideal membership problem is algorithmically undecidable (Umirbaev, 2016), this algorithm permits to test the membership in $\sqrt{[P_0]}$.

This decomposition is not uniquely determined in general, not only because there might be redundant components (some of them may be contained in another) but also it depends on many choices made during its construction, such as the choice of ranking. The following theorem (Boulier et al., 2009) shows that there is such a decomposition for each system of differential polynomials.

Theorem 3.1. If $P_0=0$, $S_0\ne 0$ is a differential system in a differential polynomial ring $\mathcal{R}$, then it is possible to compute finitely many consistent regular differential systems $A_i=0$, $S_i\ne 0$ ($1\le i\le t$) such that:

$\mathrm{\Gamma }=\sqrt{[P_0]:S_0^{\mathrm{\infty }}}=[A_1]:S_1^{\mathrm{\infty }}\cap \cdots \cap [A_t]:S_t^{\mathrm{\infty }}$

This decomposition may contain components redundant w.r.t. $\mathrm{\Gamma }$. Operations needed in this regard are addition, multiplication, differentiation and equality test with zero in the base field of $\mathcal{R}$.

A lemma of D. Lazard (Boulier et al., 1995) shows particularly that the regular ideals $[A_i]:S_i^{\mathrm{\infty }}$ are radical. The following theorem is a differential analogue to Hilbert’s theorem of zeros (Kolchin, 1973).

Theorem 3.2. (Theorem of zeros) Let $\mathcal{R}=K\left\{U\right\}$ be a differential polynomial ring over a differential field of characteristic zero and $P$ be a differential ideal of $\mathcal{R}$. A differential polynomial $p$ vanishes on every solution of $P$ in any differential field extension of $K$, if and only if $p\in \sqrt{P}$.

Corollary 3.3. A differential polynomial $p$ vanishes on every solution of a system of polynomial differential equations and inequations $A=0,S\ne 0$ if and only if $p\in \sqrt{[A]:S^{\mathrm{\infty }}}$.

Here, we give a brief exposition of the current version of the Rosenfeld-Gröbner algorithm, which is presented in (Boulier et al., 2009). The input of this algorithm is a differential system of equations and inequations with a ranking and the output is a set of differential regular ideals. Since a differential regular ideal is differentially triangular and coherent, the algorithm reduces each polynomial equation with respect to others and constructs possible $\mathrm{\Delta }$-polynomials, which can be formed between each pair of polynomials modulo processed polynomials. Then, the initials and the separants of the new polynomials are added to the set of inequations. Finally, to observe any solution, the current system is splitted by the following lemma which is a corollary of the theorem of zeros:

Lemma 3.4. If $A=0,$ $S\ne 0$ is a differential system and $p$ is a differential polynomial then,

$\sqrt{[A]:S^{\mathrm{\infty }}}=\sqrt{[A,p]:S^{\mathrm{\infty }}}\cap \sqrt{[A]:{(S\cup \{p\})}^{\mathrm{\infty }}}.$

This process continues until all systems are regular. Eventually, by the following Rosenfeld’s lemma (Rosenfeld, 1959), the consistent regular systems are detected and generated.

Theorem 3.5. (Rosenfeld’s lemma) If $A=0$, $S\ne 0$ is a regular differential system of a differential polynomial ring $\mathcal{R}$ for a ranking $\prec$ then, every differential polynomial in $[A]:S^{\mathrm{\infty }}$ that is partially reduced with respect to $A$, belongs to $(A):S^{\mathrm{\infty }}$.

By Rosenfeld’s lemma, $1\in [A]:S^{\mathrm{\infty }}$ if and only if $1\in (A):S^{\mathrm{\infty }}$. It concludes that we can verify whether the regular differential system of equations $A=0$ and inequations $S\ne 0$ is inconsistent, by verifying whether the reduced Gröbner basis of algebraic ideal $(A):S^{\mathrm{\infty }}$ equals to $\left\{1\right\}$.

The complete sub-algorithm of this algorithm is based on two criteria which detect unnecessary pairs. These criteria are the analogues of the first and second Buchberger criteria (Buchberger, 1979) established in computing Gröbner bases for ideals.

Proposition 3.6. Let $p$ and $q$ be two differential polynomials in the one differential indeterminate $u$ such that $ld(p)=\theta u$ and $ld(q)=\varphi u$. If they are linear, homogeneous, with constant coefficients, and $lcd(\theta u,\varphi u)=\theta \varphi u$, then $\mathrm{\Delta }(p,q)$ will be reduced to zero with respect to $\left\{p,q\right\}$.

Proposition 3.7. Let $A=0$ and $S\ne 0$ be a differential system and $[p_1,p_2,p_3]$ be the triple of differential polynomials such that the separants of $p_i$’s belong to $S$ and they satisfy in conditions C: $(i)$ the leaders $ld(p_i)={\theta }_{i}u$ $(1\le i\le 3)$ have common derivatives and are pairwise different, $(ii)$ $lcd({\theta }_1,{\theta }_3)$ is a derivative of ${\theta }_2$ and $(iii)$ one of the following conditions holds:

1. ${\theta }_{i}u$ is not a derivative of ${\theta }_{j}u$ ()$i\ne j$

2 $p_1<p_2<p_3$ or $p_3<p_2<p_1$

3. $p_2<p_1<p_3$ and $degree(p_1,{\theta }_{1}u)=1$

4. $p_1<p_3<p_2$ and $degree(p_3,{\theta }_{3}u)=1$

If the critical pairs $\left\{p_1,p_2\right\}$ and $\left\{p_2,p_3\right\}$ are solved by $A=0$ and $S\ne 0$, then the critical pair $\left\{p_1,p_3\right\}$ is also solved by this system.

Now, we present the general form of the algorithm. In each quadruple $⟨A,D,P,S⟩$ the sets $A,P,S$ and $D$ contain the equations already processed, the non processed equations, the inequations and the possible critical pairs of the processed equations that have to be solved.

Algorithm 3.1. The Rosenfeld-Gröbner algorithm

Input: The system $P_0=0$ and $S\ne 0$ and a ranking $\prec$.

Output: The regular systems $A_i=0$ and $S_i\ne 0$ s.th $\sqrt{[P_0]:S^{\mathrm{\infty }}}=\sqrt{[A_1]:S_1^{\mathrm{\infty }}}\cap ...\cap \sqrt{[A_t]:S^{\mathrm{\infty }}}$.

Begin

Set $ToDo:=\left\{⟨,,P_0,S_0⟩\right\}$

$Done:=$

while $ToDo\ne$ do

Select and remove a quadruple $⟨A,D,P,S⟩$ from $ToDo$

if $D=P=$ then

Partially reduce the elements of $A$ pairwise

if the rank of $A$ was not modified then

Partially reduce the elements of $S$w.r.t $A$

if the reduced Gröbner basis of $(A):S^{\mathrm{\infty }}$is not $\left\{1\right\}$then

$Done:=Done\cup \left\{A=0,S\ne 0\right\}$

end if

end if

else

if $P\ne$ then

Select and remove $q_0$ from $P$

else

Select and remove a critical pair $\left\{p_0,p{}_0^{\prime }\right\}$ from $D$

$q_0:=\mathrm{\Delta }(p_0,p{}_0^{\prime })$

end if

$q:=q_{0}fullremA$

if $q=0$ then

$ToDo:=ToDo\cup \left\{⟨A,D,P,S⟩\right\}$

else

$q_i:=q-i{v}^d$($v^d$and $i$ are the initial and the rank of q, respectively)

$q_s:=dq-vs$ ($s$ is the separant of $q$)

$ToDo:=ToDo\cup \left\{⟨A,D,P\cup \left\{i,q_i\right\},S⟩\right\}$

$ToDo:=ToDo\cup \left\{⟨A,D,P\cup \left\{s,q_s\right\},S\cup \left\{i\right\}⟩\right\}$

$ToDo:=ToDo\cup$Complete $(⟨A,D,P,S⟩,q)$

end if

end if

end do

Return $Done$

End

Algorithm 3.2. The Complete sub-algorithm

Input: A quadruple $⟨A,D^{\star },P^{\star },S⟩$ and a reduced polynomial $q$ w.r.t $A$

Output: The refinement of $⟨A,D^{\star },P^{\star },S⟩$ with regard to $q$ based on two propositions 3.6 and 3.7.

Begin

Set $A^{\prime }:=\left\{q\right\}\cup \{p\in A|ldpisnotaderivativeofldq\}$

$D_0:=\left\{possiblecriticalpairs\left\{p,q\right\}|p\in A\right\}$

Obtain

$D_1\subseteq D_0$ as follows:

a critical pair $\left\{p,q\right\}\in D_0$ is not kept in $D_1$ only if:

$\bullet$ $p$ and $q$ satisfy in the hypotheses of the Proposition 3.6 or

$\bullet$ there exists a critical pair $\left\{q,p^{\prime }\right\}$ in $D_1$ such that

the triple $[q,p^{\prime },p]$ satisfies in the conditions C of the Proposition 3.7.

$D_2\subseteq D^{\star }$ as follows:

a critical pair $\left\{p,q\right\}\in D_0$ is not kept in $D_1$ only if:

$\bullet$ there exist a critical pair $\left\{p,p^{\prime }\right\}$ in $D^{\star }$ such that the triple

$[p,q,p^{\prime }]$ satisfies in the conditions C of the Proposition 3.7 and $lcd(ldp,ld{p}^{\prime })$

is different from both $lcd(ldp,ldq)$ and $lcd(ld{p}^{\prime },ldq)$.

$D^{\prime }:=D_1\cup D_2$

$P^{\prime }:=p^{\star }$

$S^{\prime }:=S\cup \left\{i_q,s_q\right\}$

Return $⟨A^{\prime },D^{\prime },P^{\prime },S^{\prime }⟩$

End

4. The statement of the main results

In this section, we deal with a differential system in which the coefficients depend on some parameters. We define the parametric differential ring as $\mathcal{R}=K[{\alpha }_1,...,{\alpha }_t]\left\{u_1,...,u_n\right\}$ . In this ring, the coefficients of the differential polynomials are in the ring $K[{\alpha }_1,...,{\alpha }_t]$. Here, we present a parametric-Rosenfeld-Gröbner algorithm that its input is a system of equations and inequations in the parametric differential ring $\mathcal{R}$. This algorithm outputs all distinct representations for all possible values of the parameters. These representations are recognised by the pair $(N,W)$ which contains equations and inequations in $K[{\alpha }_1,...,{\alpha }_t]$. To be comparable, this pair is presented as Quasi-canonical which is defined as follows (Montes, 2002):

Definition 4.1. The pair $(N,W)$is said to be $k$-quasi-canonical if it satisfies:

• $N$is the reduced Gröbner basis in $Quot(K)[{\alpha }_1,...,{\alpha }_t]$ where $Quot(K)$ is the quotient field of $K$, with respect to the ordering $\prec {}_{\bar{\alpha }}$.

• The inequations in $W$ are algebraically reduced modulo $N$ and are irreducible over $k[{\alpha }_1,...,{\alpha }_t]$, where $k$ is some intermediate field between $Quot(K)$ and the algebraic closure $K$. They are normalised in a canonical form in order to be recognised when compared.

• ${\prod }_{w\in W}w\notin \sqrt{N}$.

• The polynomials in $N$ are square-free.

• If some polynomial in $N$ factors, no factor of it belongs to $W$.

If ${\prod }_{w\in W}w$ is in $\sqrt{N}$, then we say that this pair is inconsistent.

It is necessary to mention the terms zero and non-zero differential conditions of a polynomial $p$ are the initial, separant or the factors of $p$ that can be considered zero and non-zero, respectively. Each of these conditions is in $K[{\alpha }_1,...,{\alpha }_t]$, it is called a parametric condition. Also, the terms new zero and new non-zero conditions are those which have not been considered yet. The Parametric-Rosenfeld-Gröbner algorithm has a tree structure that its root vertex corresponds to the sextuplet $⟨,,P_0,S_0,,⟩$, where $P_0=0$ and $S_0\ne 0$ is the inputted system. This vertex is branched by the sub-algorithm Make-Tree I regarding zero and non-zero parametric and differential conditions of the polynomials of $P_0$, which are obtained by the sub-algorithms Find-New-DiffCondition and Find-New-ParCondition, and some new vertices are created. Each vertex $v$ corresponds to a sextuplet $⟨A_v,D_v,P_v,S_v,N_v,W_v⟩$, where $A_v$ is the set of all processed polynomials, $S_v$ is the union of the set of inequations $S_0$ with the non-zero differential conditions of the polynomials of $A_v$, $D_v$ is set of all critical pairs of $A_v$ that should be solved by the system $A_v=0$ and $S_v\ne 0$, $P_v$ contains all polynomials that are not processed already, and $N_v$ and $W_v$ are respectively the zero and non-zero parametric conditions and are presented as $k$-quasi-canonical. The branching process continues until at a vertex $v$ either the sub-algorithms Parametric-Consistency and Differential-Consistency recognise that the system $A_v=0$ and $S_v\ne 0$ is inconsistent (in this case, the vertex $v$ is called an inconsistent vertex), or both sets $D_v$ and $P_v$ are empty (in this case, the system $A_v=0$ and $S_v\ne 0$ is regular and the vertex $v$ is called a terminal vertex). Finally, the consistent regular systems are detected using Rosenfeld’s lemma that was stated in the previous section and outputted. Each set of outputted regular systems that contains a given parametric conditions makes a regular representation corresponding to these parametric conditions. The general structure of the algorithm is as follows.

Algorithm 4.1. The Parametric-Rosenfeld-Gröbner algorithm

Input: A differential system $P_0=0,S_0\ne 0$ in $K[{\alpha }_1,...,{\alpha }_t]\left\{u_1,...,u_n\right\}$, a ranking $\prec$ and a total ordering $\prec {}_{\bar{\alpha }}$

Output: All distinct representations of $\sqrt{P_0:S_0^{\mathrm{\infty }}}$ for all possible value of parameters ${\alpha }_1,$ $...,{\alpha }_t$

Begin

Set root vertex$:⟨,,P_0,S_0,,⟩$

Make-Tree I$(⟨,,P_0,S_0,,⟩)$ (It starts to the branching recursively.)

At each vertex $v$, $⟨A_v,D_v,P_v,S_v,N_v,W_v⟩$, is stored in the variables table.

if $⟨A_v,D_v,P_v,S_v,N_v,W_v⟩$ is a terminal vertex then

if the reduced Gröbner basis of $(A_v):S_v^{\mathrm{\infty }}$ does not equal to $\left\{1\right\}$ then

return $([A_v,S_v],[N_v,W_v])$

end if

end if

End

We now present the general structure of the recursive sub-algorithm Make-Tree I. The input of this sub-algorithm is a vertex $v$ corresponding to the sextuplet $⟨A_v,D_v,P_v,S_v,N_v,W_v⟩$. This algorithm creates some new branches when the sub-algorithm Find-New-ParCondition finds any new zero or non-zero parametric conditions. If there is not any parametric condition, then the sub-algorithm Make-Tree II is called for branching the vertex. Make-Tree II branches a vertex according to differential conditions of given polynomial. When any new vertex is created by these algorithms, then the algorithm Make-Tree I is called again and some other new branches are created. This process continues until the created vertex $v$ is a terminal or inconsistent vertex.

Algorithm 4.2. The Make-Tree I sub-algorithm

Input: A vertex $v$ corresponding to the sextuplet $⟨A_v,D_v,P_v,S_v,N_v,W_v⟩$ .

Output: Some new vertices.

Begin

if $v$ is a inconsistent vertex or a terminal vertex then

STOP

else

if $D_v\ne$ then

Select and remove a critical pair $\left\{p_1,p_2\right\}$ from $D_v$ and $q:=\mathrm{\Delta }(p_1,p_2)algrem{N}_v$

else

Select and remove a polynomial $p$ from $P_v$ and $q:=palgrem{N}_v$

end if

$q:=qfullrem{A}_v$

if $q=0$ then Make-Tree I $(⟨A_v,D_v,P_v,S_v,N_v,W_v⟩)$

else

Find-New-ParCondition $(q,N_v,W_v)=(q^{\prime },N{.}_v^{\prime },W{}_v^{\prime },newcond)$ (It contains the refinement of $q$, $N_v$ and $W_v$ with the new zero and non-zero parametric conditions)

if there is no new parametric condition then

Make-Tree II$(v,q^{\prime })$

else

for each zero parametric condition $zc$ do

Set $A_u:=\{p\in A_v|pisalgebraicallyreducedw.r.tzc\}$

$P_u:=P_v\cup (A_v\mathrm{\setminus }{A}_u)\cup \left\{q^{\prime }algremzc\right\}$

the new vertex $u:=⟨A_u,D_v,P_u,S_v,N{}_v^{\prime }\cup \left\{zc\right\},W{}_v^{\prime }⟩$

Make-Tree I ($⟨A_u,D_u,P_u,N_u,W_u⟩$)

end do

if the set of non-zero conditions $NZC$ is not empty then

Set the new vertex $u:=⟨A_v,D_v,P_v,S_v,N{}_v^{\prime },W{}_v^{\prime }\cup NZC⟩$

Make-Tree II ($⟨A_u,D_u,P_u,N_u,W_u⟩,q^{\prime }$).

end if

end if

end if

End

This algorithm creates some new vertices according to zero and non-zero conditions. The first step is processing the parametric conditions of the given polynomial. The zero conditions are added one by one to the set of zero parametric conditions $N_v$. Then, all processed polynomials $A_v$ that are not algebraically reduced with respect to the new zero condition are moved to the set of unprocessed polynomials $P_v$. In this way, the new vertices are created and the algorithm Make-Tree I is called again for branching them. If the non-zero conditions set is not empty, then another new vertex is created by adding these conditions to the set $W_v$ and the sub-algorithm Make-Tree II is called to process the differential conditions of the polynomial and branch the vertex.

The inputs of Make-Tree II are a vertex and a polynomial $q$. The general form of this algorithm is as follows:

Algorithm 4.3. The Make-Tree II sub-algorithm

Input: A vertex $v$ and a polynomial $q$.

Output: Some new vertices.

Begin

Find-New-DiffCondition$(q,S_v)$ (It contains two set of zero and non-zero conditions.)

if there is no new differential condition then

Make-Tree I(Update$(v,q,))$

else if the set of non-zero conditions is empty then

for each zero condition $z$ do

$q{}^{\prime }:=subs(z=0,q)$

Set the new vertex $u$ : $⟨A_v,D_v,P_v\cup \left\{z,q^{\prime }\right\},S_v,N_v,W_v⟩$

Make-Tree I$(⟨A_u,D_u,P_u,S_u,N_u,W_u⟩)$

end do

else

Make-Tree I(Update$(v,q,nonzeroconditions))$

Let $\left\{z_1,...,z_t\right\}$ be the set of zero conditions

for $i=t$ down to $1$ do

$q{}^{\prime }:=subs(z_i=0,q)$

Set the new vertex $u$:$⟨A_v,D_v,P_v\cup \left\{z_i,q^{\prime }\right\},S_v\cup \left\{z_1,...,z_{i-1}\right\},N_v,W_v⟩$

Make-Tree I$(⟨A_u,D_u,P_u,S_u,N_u,W_u⟩)$

end do

end if

End

Generally, in Make-Tree II there are two possibilities to create a new vertex:

• When the polynomial $q$ has some zero conditions, these conditions are imposed on the polynomial $q$. The result is a new polynomial with the zero conditions that are added to the set of non-processed polynomials $P_v$ and non-zero conditions that are added to the set of inequations $S_v$.

• When the polynomial $q$ does not have any zero condition, the non-zero conditions (if there is any) are added to the set of inequations $S_v$, the polynomial $q$ is added to the set of processed polynomial $A_v$ and former members of the set $A_v$, and the set $D_v$ is updated. This process is performed in the sub-algorithm update, which will be described later.

The parametric and differential conditions of a polynomial are obtained by the sub-algorithms Find-New-ParCondition and Find-New-DiffCondition, respectively. In the following, we explain these algorithms. The inputs of Find-New-ParCondition are a polynomial $p$ with two sets of the zero parametric conditions $N$ and the non-zero parametric conditions $W$. This algorithm checks the initial of the polynomial $p$ according to old zero and non-zero conditions and returns new conditions, which can be considered zero and non-zero. Before presenting this algorithm, it should be noted that the set of irreducible polynomials that are factors of the polynomials of $W$ is denoted by $PriFact(W)$, which is normalised in a canonical. Also, for each polynomial in $K[{\alpha }_1,...,{\alpha }_t]\left\{u_1,...,u_n\right\}$, the notation $pcoef(p)$ denotes the product of the factors of $p$, which are in $K[{\alpha }_1,...,{\alpha }_t]$.

Algorithm 4.4. The Find-New-ParCondition sub-algorithm

Input: A polynomial $p$ and two sets of zero and non-zero conditions $N$ and $W$.

Output: The refinement of $p$, $N$and $W$ and also, zero and non-zero conditions of $p$.

Begin

set $p{}^{\prime }:=p;sw:=true;N{}^{\prime }:=N;w{}^{\prime }:=W;$

while $sw=true$ do

if $pcoef(i_{p{}^{\prime }})\in \sqrt{N^{\prime }}$ then

$p{}^{\prime }:=p{}^{\prime }-i_{p{}^{\prime }}v{}^d$ ($i_{p{}^{\prime }}$ and $v{}^d$ are the initial and the rank of $p^{\prime }$, respectively)

$N^{\prime }:=$ Gröbner basis for $N{}^{\prime }\cup \left\{i_{p^{\prime }}\right\}$ w.r.t $\prec {}_{\bar{a}}$

$W{}^{\prime }:=\{walgre{m}_{\prec {}_{\bar{a}}}N{}^{\prime }|w\in W{}^{\prime }\}$

else $sw:=false$

end if

end do

$p^{\prime }=p^{\prime }algre{m}_{\prec {}_{\bar{a}}}{N}^{\prime }$

$cond:=PriFact(pcoef(i_{p^{\prime }})$) minus $W^{\prime }$

if $p^{\prime }\notin K[\bar{a}]$ then

return $cond$ (as the zero and non-zero condition)

else

return $cond$ (just as the zero condition)

end if

End

This algorithm checks the parametric coefficient of the initial of the polynomial $p$, $pcoef(i_p)$. When $pcoef(i_p)$ is zero, it begins omitting iteratively the leading term of $p$. In the following, the parametric coefficient $pcoef(i_p)$, which is in $\sqrt{⟨N⟩}$, is added to $N$ in order to improve $N$ and the new Gröbner basis is recomputed. Then, W is also improved. When $pcoef(i_p)$ is not decidable regarding the set of zero and non-zero conditions $N^{\prime }$ and $W^{\prime }$, then p is algebraically reduced with respect to $N^{\prime }$. The algorithm now computes the set $cond$ containing the irreducible factors of $pcoef(i_p)$ that are not in $W$ and returns it. If this is empty, it means that $pcoef(i_p)$ is not zero and p does not have any new parametric condition. Otherwise, if p is not in $K[{\alpha }_1,...,{\alpha }_t]$, so the set cond is as zero and non-zero parametric conditions of $p$. Otherwise, the set cond is as just zero parametric conditions of $p$, because the inputted polynomial of this algorithm comes from the set of equations and cannot be non-zero.

Now, we present the sub-algorithm Find-New-DiffCondition that computes the zero and non-zero differential conditions of a polynomial. The inputs of this algorithm are a differential polynomial $p$ and the set of inequations $S_v$. This sub-algorithm verifies the polynomial $p$ and its initial and separant and finds the new zero and non-zero conditions regarding the set of inequations $S_v$. The following proposition which works as an efficient criterion in this algorithm helps to remove some ineffectual conditions.

Proposition 4.2. Let $p\in \mathcal{R}=K\left\{U\right\}$ be a differential polynomial with the non-zero initial $i_p$ and the separant $s_p$. Let also S be a set of differential inequations. If there is a member $h\in S$ such that it is reduced to zero with respect to $p$, then $p$ cannot be zero.

Proof. Suppose not. Since for some $h\in S$ we have $hfullremp=0$ (the initial and the separant of $p$ are non-zero and the reduction by $p$ is possible), then for some integers $a_i$ we have $i_p^{a_1}{s}_p^{a_2}\equiv 0mod([p])$, suggesting that for a non-zero polynomial $b\in \mathcal{R}$ and a derivative $\theta \in \mathrm{\Theta }$, $i_p^{a_1}{s}_p^{a_2}h=b\theta p$. Beacuse p is assumed to be zero, $h$ should be zero as well, which contradicts the assumption.

Algorithm 4.5. The Find-New-DiffCondition sub-algorithm

Input: A polynomial $p$ and the set of inequations $S$.

Output: The zero and non-zero conditions regarding $p$.

Begin

set $zerocond,non-zerocond:=$

if $p=u_1\cdots u_t$ is a product of distinct factors $\left\{u_1,..,u_t\right\}$ then

for $i=1$ to $t$ do

if $i_{u_i},s_{u_i}\notin S$ or for each $h\in S$, $hfullrem\left\{u_i\right\}\ne 0$ then

Add $c$ to $zerocond$

end if

end do

else

for $c\in \left\{i_p,s_p\right\}\mathrm{\setminus }K$ do ($i_p$ and $s_p$ are the initial and the separant of $p$)

if $i_c,s_c\notin S$ or for each $h\in S$, $hfullrem\left\{c\right\}\ne 0$ then

Add $c$ to $zerocond$ and $non-zerocond$

end if

end do

end if

Return $(zerocond,non-zerocond)$

End

In the Find-New-DiffCondition algorithm if the inputted polynomial p is a product of distinct non-constant factors, then each of these factors may be a zero condition. However, some of these factors that satisfy the hypothesis of Proposition 4.2 cannot be zero and they are removed from zero conditions. It should be noted that in this algorithm we use two obvious ways to find the factors of the inputted polynomial $p$. When $p$ is a product of some polynomials, we consider these polynomials as its factors. For example, let the inputted polynomial be $p=avyux$,y, such that $a$, $u_y$ and $u_{x,y}$ are three factors of $p$. Also, when the greatest common divisor (gcd) of all terms of $p$ does not belong to $K$, we consider it as a factor of $p$. For example, if the inputted polynomial is $p=u^4+u$, so $u$ is the gcd of the two terms of $p$, suggesting that $u$ and $u_3+1$ are two factors of $p$.

Otherwise, the initial and the separant of $p$, provided not being in $K$, should be considered zero and non-zero. However, each of them that satisfies in the hypothesis of Proposition 4.2 will be removed from zero conditions. When a polynomial $q$ satisfies in Proposition 4.2, it means that there is a polynomial $h$ in the set of inequations $S_v$ such that it forces the polynomial $q$ not be zero. In fact, this proposition plays an important role in the Parametric-Rosenfeld-Gröbner algorithm. As mentioned, this proposition decreases the number of zero conditions leads to a decrease in the number of ineffectual branches that will be made in the sub-algorithm Make-Tree II.

Now, we explain the general structure of the sub-algorithm Update. The input of this algorithm is a vertex $u$ corresponding to the sextuplet $⟨A_u,D_u,P_u,S_u,N_u,W_u⟩$, a polynomial $q$ and non-zero conditions. This algorithm adds the new non-zero conditions to the set of inequations $S_u$ and the new polynomial q to the set of processed polynomials $A_u$. Then based on two analogues of Buchberger’s criteria, it starts to make possible critical pairs between $q$ and the other members of $A_u$ and adds them to the set of critical pairs $D_u$. In this way, a new vertex that corresponds to the sextuplet $⟨A_v,D_v,P_v,S_v,N_v,W_v⟩$ is created.

Algorithm 4.6. The Update sub-algorithm

Input: A vertex $u$, a polynomial $q$ and its non-zero conditions.

Output: A new vertex $v$.

Begin

Set $A_v:=\left\{q\right\}\cup \{p\in A_u|pisreducedw.r.tq\}$

$P_v:=P_u\cup \{p|p\in A_{u}s.thlcd(ldq,ldp)\ne ldqandpisnotreducedw.r.tq\}$

$D_0:=\left\{possiblecriticalpairs\left\{p,q\right\}|p\in A_{u}s.thpisreducedw.r.tqorlcd(ldq,ldp)=ldq\right\}$

Obtain

$D_1\subseteq D_0$ as follows:

a critical pair $\left\{p,q\right\}\in D_0$ is not kept in $D_1$ only if:

$\bullet$ $p$ and $q$ satisfy in the hypotheses of the Proposition 3.6 or

$\bullet$ there exist a critical pair $\left\{q,p^{\prime }\right\}$ in $D_1$ such that

the triple $[q,p^{\prime },p]$ satisfies the conditions C of the Proposition 3.7.

$D_2\subseteq D_u$ as follows:

a critical pair $\left\{p,q\right\}\in D_0$ is not kept in $D_1$ only if:

$\bullet$ there exist a critical pair $\left\{p,p^{\prime }\right\}$ in $D_u$ such that the triple

$[p,q,p^{\prime }]$ satisfies in the conditions C of the Proposition 3.7 and $lcd(ldp,ld{p}^{\prime })$

is different from both $lcd(ldp,ldq)$ and $lcd(ld{p}^{\prime },ldq)$.

$D_v:=D_1\cup D_2$

$S_v:=S_u\cup \left\{i_q,s_q\right\}$

Return $⟨A_v,D_v,P_v,S_v,N_v,W_v⟩$

End

If a polynomial $p$ in the set $A_v$ is not reduced with respect to the new polynomial $q$, then it exits from the set $A_v$ for reprocessing. Now, if $ldp$ is not reduced with respect to $ldq$, then the critical pair $\left\{p,q\right\}$ is added to the set $D_0$ to recognise more solved critical pairs by the analogues of the Buchberger criteria; otherwise, it is added to the set $P_v$. The rest of the algorithm is based on two propositions 3.6 and 3.7.

Remark 1. This sub-algorithm is similar to the Complete sub-algorithm. For further information about this sub-algorithm, see the part $5.2$ of the article (Boulier et al., 2009).

Finally, we present the sub-algorithms Parametric-Consistency and Differential-Consistency, which check the termination conditions in the Make-Tree I algorithm. Parametric-Consistency checks the sets of zero and non-zero parametric conditions $N_v$ and $W_v$ of a vertex $v$ and returns $FALSE$ if the pair $(N_v,W_v)$ is inconsistent. Otherwise, it returns a $k$-quasi-canonical representation of the pair $(N_v,W_v)$ according the definition 4.1.

Algorithm 4.7. The Parametric-Consistency sub-algorithm

Input: The sets of zero and non-zero conditions $N,W$ and an ordering $\prec {}_{\bar{\alpha }}$.

Output: $FALSE$, if the pair $(N,W)$ is inconsistent and the $k$ -quasi-canonical

representation of $(N,W)$, otherwise.

Begin

Set $W^{\prime }:=PriFact(\{qalgre{m}_{\prec {}_{\bar{\alpha }}}N|q\in W\})$

$sw:=true;$ $N^{\prime }:=N;$

if ${\prod }_{q\in W}q\in \sqrt{⟨N^{\prime }⟩}$ then

return $FALSE$

else

While $sw=true$ do

$sw:=false;$

$N^{\prime \prime }:=$ Drop any factor of a $p\in N^{\prime }$ that belongs to

$W^{\prime },$ as well as multiple factors.

if $N^{\prime \prime }\ne N^{\prime }$ then

$sw:=true$

$N^{\prime }:=$ Gröbner basis for $N^{\prime \prime }$ w.r.t $\prec {}_{\bar{\alpha }}$

$W^{\prime }:=PriFact(\{qalgre{m}_{\prec {}_{\bar{a}}}{N}^{\prime }|q\in W^{\prime }\})$

end if

end do

return $N^{\prime }$ and $W^{\prime }$

end if

End

For more details and the proof of correctness of this algorithm, the reader can refer to (Montes, 2002).

Now, we explain another sub-algorithm for checking the consistency of the vertices, which is called Differential-Consistency sub-algorithm. For each vertex $v$ corresponding to the sextuplet $⟨A_v,D_v,P_v,S_v,N_v,W_v⟩$, if the output of the Parametric-Consistency is not $FALSE$, then this vertex will be refined by the $k$-quasi-canonical representation of $N_v$ and $W_v$. After that, Differential-Consistency sub-algorithm checks the consistency of this vertex regarding the differential conditions. According to this algorithm, this vertex is inconsistent if either a non-zero element of $K$ appears among the equations $A_v$ or $0$ appears among the inequations $S_v$, or the system $A_v=0$ and $S_v\ne 0$ satisfies in the following proposition. As mentioned in subsection $\mathrm{5.5.2}$ of (Boulier et al., 2009), using this proposition is not very CPU expensive and can point out inconsistencies.

Otherwise, it refines the vertex by reducing the set of inequations $S_v$ with respect to the set of processed equations $A_v$.

Proposition 4.3. Let $A=0$ and $S\ne 0$ be a system of equations and inequations such that the initials and the separants of the members of $A$ belong to $S^{\mathrm{\infty }}$. If there is a polynomial $h\in S$ such that $h$ is reduced to $0$ with respect to $A$, then the system $A=0$ and $S\ne 0$ is inconsistent.

Proof. Let $A=\left\{p_1,...,p_t\right\}$ and for some $h\in S$ we have $hfullremA=0$. Then, for some integers $a_i$ and $b_i$ we have $i_{p_1}^{a_1}\cdots i_{p_t}^{a_t}{s}_{p_1}^{b_1}\cdots s_{p_t}^{b_t}h\equiv 0(mod[A])$. Thus, for some non-zero polynomials $q_i$ and derivatives ${\theta }_i\in \mathrm{\Theta }$ we can write:

$i_{p_1}^{a_1}\cdots i_{p_t}^{a_t}{s}_{p_1}^{b_1}\cdots s_{p_t}^{b_t}h=q_1{\theta }_1{p}_1+\cdots +q_t{\theta }_t{p}_t.$

Since for each $i$, ${\theta }_i{p}_i=0$ and the coefficient of $h$ is non-zero, $h$ should be zero and so the system $A=0$ and $S\ne 0$ is inconsistent.

Algorithm 4.8 The Differential-Consistency sub-algorithm

Input: A vertex $v$ corresponding to a sextuplet $⟨A_v,D_v,P_v,S_v,N_v,W_v⟩$.

Output: $FALSE$, if the system $A_v=0$ and $S_v\ne 0$ is inconsistent and the refinement of $v$, otherwise.

Begin

if $A_v\cap K\ne$ then

Return $FALSE$

else

if $0\in \{r|r=qrem{A}_v,q\in S_v\}$ then

Return $FALSE$

else

Return $⟨A_v,D_v,P_v,\{r|r=qfullrem{A}_v,q\in S_v\}\mathrm{\setminus }K,N_v,W_v⟩$ (Refinement of data)

end if

end if

End

Now, we prove the correctness of the Parametric-Rosenfeld-Gröbner algorithm, but before that we need the following lemma.

Lemma 4.4. If $A=0,$ $S\ne 0$ is a differential system and $p_1{p}_2$ is a product of two differential polynomials then:

$\sqrt{[A,p_1{p}_2]:S^{\mathrm{\infty }}}=\sqrt{[A,p_1]:S^{\mathrm{\infty }}}\cap \sqrt{[A,p_2]:S^{\mathrm{\infty }}}$

Proof. We begin by showing that $\sqrt{[A,p_1{p}_2]:S^{\mathrm{\infty }}}\subseteq \sqrt{[A,p_1]:S^{\mathrm{\infty }}}\cap \sqrt{[A,p_2]:S^{\mathrm{\infty }}}$. Let $p$ be a differential polynomial in $\sqrt{[A,p_1{p}_2]:S^{\mathrm{\infty }}}$. According to the theorem of zeros, it suffices to show that $p$ vanishes on every solution of the systems of $A=0,p_1=0,S\ne 0$ and $A=0,p_2=0,S\ne 0$. Now, let $\alpha$ be a solution of these systems, then it also will be a solution of the system $A=0,p_1{p}_2=0,S\ne 0$. Therefore, $p$ vanishes on $\alpha$ and it will belong to $\sqrt{[A,p_1]:S^{\mathrm{\infty }}}\cap \sqrt{[A,p_2]:S^{\mathrm{\infty }}}$. Conversely, let $p$ be in $\sqrt{[A,p_1]:S^{\mathrm{\infty }}}\cap \sqrt{[A,p_2]:S^{\mathrm{\infty }}}$ and $\alpha$ be a solution of the system $A=0,p_1{p}_2=0,S\ne 0$. We only need to show that $p$ vanishes on $\alpha$. Since $p_1{p}_2$ vanishes on $\alpha$, so $p_1$ or $p_2$ vanishes on $\alpha$. If $p_1$ is so, then $\alpha$ will be a solution of the system $A=0,p_1=0,S\ne 0$ and $p$ vanishes on $\alpha$ (since $p\in \sqrt{[A,p_1]:S^{\mathrm{\infty }}}$). Similarly, if $p_2$ vanishes on $\alpha$, then $p$ is so. Therefore $p$ belongs to $\sqrt{[A,p_1{p}_2]:S^{\mathrm{\infty }}}$ and the proof is completed.

Theorem 4.5. Consider the parametric system $A=0$ and $S\ne 0$ in the parametric differential ring $K[{\alpha }_1,...,{\alpha }_t]\left\{u_1,...,u_m\right\}$, the term ordering $\prec {}_{\bar{a}}$ and the ranking $\prec$. The Parametric-Rosenfeld-Gröbner algorithm decomposes the $A=0,S\ne 0$ with a tree structure that at each terminal vertex $v$ the pair $(N_v,W_v)$ of parametric conditions is $k$ -quasi-canonical for some field $k$, the system $A_v=0$ and $S_v\ne 0$ is regular, and the systems corresponding to terminal vertices $v_1,...,v_t$ with the same parametric conditions satisfy in:

$\sqrt{A:S^{\mathrm{\infty }}}=[A_{v_1}]:S_{v_1}^{\mathrm{\infty }}\cap \cdots \cap [A_{v_t}]:S_{v_t}^{\mathrm{\infty }}$

for these conditions.

Proof. According to Parametric-Consistency, the pair $(N_v,W_v)$ at each terminal vertex $v$ is $k$-quasi-canonical. Now, we prove that the systems corresponding to terminal vertices are regular. At each terminal vertex $v$, two sets $D_v$ and $P_v$ are empty, which means that all possible critical pairs between the members of $A_v$ are solved with the system $A_v=0$ and $S_v\ne 0$. Also, as $D_v$ is the set of critical pairs that should be solved and each member of $A_v$ is reduced with respect to others. So, the set $A_v$ is autoreduced and coherent. Furthermore, according to the Update sub-algorithm, when a new polynomial is added to $A_v$, the initial and separant of this is added to $S_v$ so $S_v$ contains all initials and separants of the members of $A_v$ and the system $A_v=0$ and $S_v\ne 0$ is regular. Now, it is the time to show the regular ideals corresponding with terminal vertices with the same conditions of the pair $(N_v,W_v)$ satisfy in intended intersection according to this condition. As already noted, the sub-algorithm Make-Tree I firstly branches the vertex $v$ with respect to zero and non-zero parametric conditions of a polynomial $p$, which are computed by the Find-New-ParCondition sub-algorithm, and makes new vertices with different parametric conditions. If this polynomial does not have any parametric condition, the Make-Tree II begins to branch the vertex by differential conditions of the polynomial and the parametric conditions of these new vertices are equal. So, it is sufficient that we show when a vertex $v$ is branched by differential conditions of a polynomial, the radical ideal $\sqrt{A_v:S_v^{\mathrm{\infty }}}$ equals to the intersection of radicals of saturation ideals corresponding to the created vertices. If the polynomial $p$ is as a product of some polynomials, then Find-New-DiffCondition returns some zero conditions and Make-Tree II makes some new vertices by adding these conditions to the set of equations. According to the previous lemma, the radical of the saturation ideal of the system corresponding to the vertex $v$ is equal to the intersections of radicals of saturation ideals corresponding to new vertices. Otherwise, Find-New-DiffCondition returns some conditions that should be considered zero and non-zero. In addition, according to Lemma 4.4, the radical of the saturation ideal of the system corresponding to the vertex $v$ is also equal to the intersections of radicals of saturation ideals corresponding to the new vertices. So, the radical of the corresponding saturation ideal with the root vertex for each parametric condition is as the intersections of radicals of saturation ideals corresponding to terminal vertices with the same parametric conditions. Finally, since this ideals are regular and regular ideals are radical (Lazard’s lemma, see Boulier et al., 1995), the claim of the theorem is proved.

5. Example

In this section, we present the output of the Parametric-Rosenfeld-Gröbner algorithm for several examples in the differential ring $\mathcal{R}=Q[a,b,c,d](x,y,z)\left\{m,u,v,w\right\}$ considering the orderly ranking as $w\prec v\prec u\prec m$ and elimination ranking as $m\prec u\prec v\prec w$ for the graded lexical order $z<y<x$. The implementation of this algorithm in Maple is available at the address http://faculty.du.ac.ir/rahmani/software. The output of this algorithm is in the form of a discussion about the distinct representations of given system as an intersection of regular ideals for different cases of values of parameters. As stated in section $5$ of (Boulier, 2018), DifferentialAlgebra packege of Maple permits to define parameters and makes such decompositions.

First consider the parametric differential system $P_1$, also known as Lorenz system (Harrington & Van Gorder, 2017), with the orderly ranking.

$P_1=\left\{\begin{array}{c}{u}_x-a(v-u)=0\\ v_x-u(b-w)+v=0\\ w_x-uv+cw=0\end{array}\right.$

Table 1 describes the discussion of decomposing of system $P_1$ for different values of the parameters $a$, $b$ and $c$. As can be seen, when the parameter $a$ is considered non-zero, we have the following representation for the radical of ideal $[P_1]$ for each arbitrary values of $b$ and $c$:

$\sqrt{[P_1]}=[au-av+u_x,-abu+auw+au+a{u}_x+u_x+u_{x,x},-abc{u}^2+a{u}^4+ac{u}^2+acu{u}_x+u^3{u}_x$

$+au{u}_{x,x}-a{u}_x^2+cu{u}_x+cu{u}_{x,x}+u{u}_{x,x}+u{u}_{x,x,x}-u_x^2-u_x{u}_{x,x}]:\{u{\}}^{\mathrm{\infty }}\cap [u,v,cw+w_x]$

Table 1. Discussion of the system $P_1$ (Lorenz system)

Case	Regular ideals
$a\ne 0$	$[au-av+u_x,-abu+auw+au+a{u}_x+u_x+u_{x,x},$ $-abc{u}^2+a{u}^4+ac{u}^2+acu{u}_x+u^3{u}_x+au{u}_{x,x}-a{u}_x^2+cu{u}_x$ $+cu{u}_{x,x}+u{u}_{x,x}+u{u}_{x,x,x}-u_x^2-u_x{u}_{x,x}]:\{u{\}}^{\mathrm{\infty }},$ $[u,v,cw+w_x]$
$a=0$	$[u_x,-bu+uw+v+v_x,bcu-u^{2}v-cv-c{v}_x-v_x-v_{x,x}]:$ $\{u{\}}^{\mathrm{\infty }},[u,v+v_x,cw+w_x]$

It is notable that if we substitute $a=0$ in this representation, then the first ideal will be inconsistent, suggesting that it is essential that this parameter is not zero. According to this table for the case $a=0$ we have another representation as follows:

$\sqrt{P_1}=[u_x,-bu+uw+v+v_x,bcu-u^{2}v-cv-c{v}_x-v_x-v_{x,x}]:\{u{\}}^{\mathrm{\infty }}\cap [u,v+v_x,cw+w_x],$

This representation is also independent of the values of $b$ and $c$.

Now, consider the Genesio-Tesi system (Harrington & Van Gorder, 2017) that contains three ODE equations and the orderly ranking.

$P_2=\left\{\begin{array}{c}w-v_x=0\\ v-u_x=0\\ au+bv+cw+u^3-w_x=0\end{array}\right.$

The output of the Parametric-Rosenfeld-Gröbner algorithm contains only one case meaning that for each value of the parameters $a$, $b$ and $c$ we have the same representation as follows:

$\sqrt{[P_2]}=[v-u_x,w-u_{x,x},u^3+au+b{u}_x+c{u}_{x,x}-u_{x,x,x}]$

For arbitrary values of $a$, $b$ and $c$ the ideal of this representation is regular and consistent, so this representation can be used for all cases of the values of the parameters.

Finally, we discuss the following PDE system with the elimination ranking. Although this system has no physical significance, it has more distinct representations.

$P_3=\left\{\begin{array}{c}(a+1)u_{x,x}^{2}v+b{u}_{x,x}v+c{u}_x=0\\ u_{x,y}=0\\ a{u}_{y,y}-1=0\end{array}\right.$

Table 2 presents the decomposing of this system. The table shows all distinct representations for all possible values of the parameters. It means that for not mentioned cases there is no regular representation for the radical of ideal $[P_3]$. For instance, in the case $a=0$, the system $P_3$ is inconsistent so the output of Parametric-Rosenfeld-Gröbner algorithm does not contain this case.

Table 2. Discussion of system $P_3$

Case	Regular ideals
$a,b,c,a+1\ne 0$	$[4ac{u}_x-b^{2}v+4c{u}_x,-b{v}_x-2c,v_y,a{u}_{y,y}-1],$ $[av{u}_{x,x}^2+bv{u}_{x,x}+v{u}_{x,x}^2+c{u}_x,u_{x,y},v_y,a{u}_{y,y}-1]:\{2av{u}_{x,x}+bv$ $+2v{u}_{x,x}{\}}^{\mathrm{\infty }},[u_x,a{u}_{y,y}-1]$
$a,c,a+1\ne 0$, $b=0$	$[u_x,a{u}_{y,y}-1],[av{u}_{x,x}^2+bv{u}_{x,x}+v{u}_{x,x}^2+c{u}_x,u_{x,y},v_y,$ $a{u}_{y,y}-1]:\{2av{u}_{x,x}+bv+2v{u}_{x,x}{\}}^{\mathrm{\infty }}$
$a,a+1\ne 0$, $b=c=0$	$[u_{x,x},u_{x,y},a{u}_{y,y}-1],[v,u_{x,y},a{u}_{y,y}-1]$
$a,a+1,b\ne 0$, $c=0$	$[u_{x,y},a{u}_{x,x}+b+u_{x,x},a{u}_{y,y}-1],[u_{x,y},u_{x,x},a{u}_{y,y}-1],$ $[v,u_{x,y},a{u}_{y,y}-1]$
$a=-1,b,c\ne 0$	$[v,u_x,-u_{y,y}-1],[u_x,-u_{y,y}-1]:\{v{\}}^{\mathrm{\infty }},$ $[bv{u}_{x,x}+2c{u}_x,u_{x,y},v_y,-u_{y,y}-1]:\{v{\}}^{\mathrm{\infty }}$
$a=-1,c=0$, $b\ne 0$	$[v,u_{x,y},-u_{y,y}-1],[u_{x,y},u_{x,x},-u_{y,y}-1]$
$a=-1,b=0$, $c\ne 0$	$[u_x,-u_{y,y}-1]$
$a=-1,b,c=0$	$[u_{x,y},-u_{y,y}-1]$

6. Conclusion

We presented a new algorithm with branching style that examines the values of the parameters of the parametric differential system and returns all distinct regular representations for all possible values of these parameters. The branches of this algorithm are made by differential or parametric conditions of equations. When a vertex is branched by parametric conditions only the information of this vertex is needed to follow the branches below it, and no other information about the upper or lateral vertices is needed. Accordingly, this algorithm can be implemented in parallel such that all distinct representations are made individually and simultaneously in a time-saving manner. We also applied a new criterion for reducing the ineffectual branches made by differential conditions that should be processed in this algorithm.

Additional information

Funding

The authors received no direct funding for this research.

Notes on contributors

Sajjad Rahmany

The first author of this article is Shahnaz Fakouri. She is a Ph.D. student of pure mathematics in the computational algebra tendency at Damghan University, Iran. This article is a result of her Ph.D. thesis.

Other authors are Dr. Sajjad Rahmany and Dr. Abdolali Basiri. They are associate Professors of Computer Algebra at the University of Damghan, Iran. They received the Ph.D degrees at University of Pris 6. Their research interests include Gröbner basis and solving polynomials systems. They published more than 30 papers in international journals such as Theoretical Computer Science, Soft Computing, Information Sciences, JIFS and conference proceedings.