# Differential ideal membership problem

We know that in the ordinary algebra ideal case, the ideal membership problem can be solved by the Grobner Base theory, then, is there a counterpart theory in the differential ideal case?

To be precise, suppose I is a differential ideal in the differential ring k{y_1,...,y_n}, which is generated by a finite set of differential polynomials{f_1,...,f_m},can we choose a base A={g_1,...g_d} in I ,such that I is also generated by A,and we can use it to determine whether a differential polynomial belongs to I or not by a method that is similar to the use of the Grobner Base .

-
You might try Googling "differential Grobner bases." – Qiaochu Yuan Nov 29 '10 at 9:57
@Qiauchu: Google gives 3,320 texts. You suggest reading them all? – Mark Sapir Nov 29 '10 at 14:53

I am not sure that what you want is decidable. You may want to look at this paper: MR1017781 (it is also explained in Section 7.6.2 of MR1361261). We proved there the following. There exists a system $p_1,...,p_n$ of linear differential operators with polynomial coefficients (over the field of char=0) such that the solvability of the system of PDEs

$$\left\\{\begin{array}{c} p_1(u_1,...,u_m)=r_1\\\ \ldots \\\ p_n(u_1,...,u_m)=r_n\end{array}\right.$$

in polynomials $u_1,...,u_m$ for a given set of polynomials $v_1,...,v_n$ is undecidable. In other words, given the left hand side of a system of linear differential equations with polynomial coefficients, it is not possible to decide for every right hand side whether the system has a solution. A yet another reformulation is in terms of the Weyl algebra $W_n$. There exists a matrix $D$ over $W_n$, such that the solvability of equation

$$D\cdot \vec u=\vec r$$ (given $\vec r$, find $\vec u$) in polynomials is undecidable.

-
@Sapir: I was motivated by Ritt's one problem.In his classical book on differential algebra(page 177), Ritt asked the following question: For p,i>0,what is the least q such that (y_i)^q mod 0 ([y^p])? – Jiang Nov 29 '10 at 15:49
What is $y$ ($y_i$)? I do not have Ritt's book here, and I do not have time to read it. It would be better if you update your question, making it more concrete. You are not seem to be interested in the general membership problem for differential ideals. – Mark Sapir Nov 29 '10 at 18:54
@Sapir:we work in the ordinary differential ring k{y},so $y$ is the indeterminate,$y_i$ is its i-th derivative. – Jiang Nov 30 '10 at 4:00
Dear Mark: sorry if I'm being dense, but could you explain how this is related to the undecidability of the differential ideal membership? How I interpret Ougaos question it ask: given a system of polynomial differential equations, how to decide if another differential equation $F=0$ is a differential consequence of the system. – Michael Bächtold May 20 '11 at 14:23
@Michael: As I understood it (and it was long ago, so I may have forgotten), you can do the following. Consider the Weyl algebra and its action of the ring of polynomials: $d_x\cdot p=\partial p/\partial_x$, $x\cdot p=xp$. Then a differential equation with polynomial coefficients can have the form $D\cdot \vec u=\vec 0$ with $D$ from $W_n$ (a diff. operator). Of course $\vec u$ is a vector of polynomials. Now with every such equation, you associate a left ideal in $W_n$, and I interpreted the question as the membership in that left ideal. I suspected (still do) that it is not decidable. – Mark Sapir May 20 '11 at 14:43

In "Some constructions in rings of differential polynomials" Gallo and Mishra show that for certain infinitely generated differential ideals the membership problem is undecidable.

Which does not exclude that membership is decidable for finitely generated ideals (the case mainly encountered in real life). According to this article from 2006 that problem is still open.

But maybe this is useful: in 2009 Gao, Van der Hoeven, Yuan and Zhang showed that perfect ideal membership is decidable. (I think "perfect" means "radical" in differential algebra terminology)

-