The Ritt problem, originating in Ritt's 1936 work on singular solutions of algebraic differential equations and recorded as unresolved in Kolchin's monograph, asks whether there exists an algorithm that decides, given the characteristic sets of two prime differential ideals in a ring of differential polynomials over a computable differential field of characteristic zero, whether one ideal is contained in the other. Golubitsky, Kondratieva and Ovchinnikov proved this problem equivalent to computing the essential (non-redundant) prime decomposition of a radical differential ideal, to deciding primality of a radical differential ideal, to computing generators of a prime differential ideal from a characteristic set, and to deciding whether a differential polynomial is a zero divisor modulo a radical differential ideal. The question is the precise obstruction behind the remark in the TDDS Maple package paper on Thomas decompositions of nonlinear PDE systems that deciding to which prime component of a radical differential ideal a given solution belongs is a related difficult problem: all known decomposition algorithms (Ritt-Kolchin, Rosenfeld-Groebner, Thomas) may output redundant components, and as reaffirmed in 2021 by two co-authors of the TDDS paper, no effective way is known to decide superfluousness. The problem remains open: no decision algorithm and no undecidability proof is known for general computable differential fields with a splitting algorithm.

Background

Systems of polynomial nonlinear ordinary or partial differential equations can be studied through differential algebra. Fix a differential field kk of characteristic zero with commuting derivations δ1,…,δm\delta_1,\ldots,\delta_m (for example k=Q(x1,…,xm)k=\mathbb{Q}(x_1,\ldots,x_m) with δi=∂/∂xi\delta_i=\partial/\partial x_i) and differential indeterminates y1,…,yny_1,\ldots,y_n. The differential polynomial ring k{y1,…,yn}k\{y_1,\ldots,y_n\} is the commutative polynomial ring in all formal derivatives θyj\theta y_j, where θ\theta ranges over finite compositions of the derivations, with each derivation extended to act on higher-order derivatives. An ideal stable under all derivations is a differential ideal; one equal to its radical is a radical differential ideal; one whose quotient ring is an integral domain is a prime differential ideal. The Ritt-Raudenbush basis theorem, the differential analogue of Hilbert's basis theorem, implies that every radical differential ideal is determined by finitely many differential polynomials and equals a finite intersection of its essential prime components, meaning its minimal prime differential over-ideals.

Computation with these ideals is organized by rankings, well-orderings of the set of all derivatives compatible with differentiation. Relative to a ranking, each nonzero differential polynomial has a leader (its highest-ranked derivative), an initial (its leading coefficient as a polynomial in the leader) and a separant (the initial of any proper derivative of it). Every prime differential ideal PP admits a characteristic set CC, an autoreduced set of least rank (autoreduced means no element contains a derivative of the leader of another), and is representable as the differential ideal generated by CC saturated by HCH_C, the product of the initials and separants of the elements of CC:

P=[C]:HC∞.P = [C] : H_C^{\infty}.

Membership of a differential polynomial in PP can be tested by reduction to zero modulo this representation, but only for questions settled away from the locus where HCH_C vanishes.

Classical algorithms, namely the Ritt-Kolchin characteristic-set algorithm, the Rosenfeld-Groebner algorithm and the Thomas decomposition, take finitely many differential polynomials and return a finite family of prime or characterizable differential ideals, each given by a characteristic set, whose intersection is the radical differential ideal generated by the input. The Maple package TDDS implements the Thomas decomposition for polynomially nonlinear PDE systems containing equations and inequations; a distinguishing property is that the solution sets of the output subsystems are disjoint, so the solution of a well-posed (regular) initial problem belongs to exactly one output subsystem. Three limitations, however, affect every known algorithm of this family. The computed decompositions can be redundant, and no effective way is known to decide whether a component is superfluous. A singular analytic solution, one whose jet at some point makes an initial or separant vanish, may satisfy several components, and there is in general no algorithm deciding to which essential components it belongs. And the decompositions are not canonical: the output depends on the ranking and on case-distinction choices. All three limitations meet in one classical question, the Ritt problem, which Ritt confronted in his 1936 study of singular solutions and which Kolchin's monograph records as unresolved; the TDDS paper cites it as a related difficult problem with contributions by Ritt and Hubert.

Golubitsky, Kondratieva and Ovchinnikov recast the Ritt problem as a computational problem over a computable differential field (a field whose elements can be indexed by natural numbers so that the field operations and the derivations become computable functions) of characteristic zero admitting a splitting algorithm, an algorithm deciding irreducibility of univariate polynomials over the field, which is needed for any factorization-type subroutine. They proved the following equivalent: deciding containment of two prime differential ideals given by their characteristic sets; computing a non-redundant (essential) prime decomposition of a radical differential ideal given by generators; deciding whether a radical differential ideal is prime; computing generators of a prime differential ideal from a characteristic set; and deciding whether a differential polynomial is a zero divisor modulo a radical differential ideal. A positive solution of any one formulation yields algorithms for all of them. Special cases were settled classically by Ritt, Levi, Kolchin and Cohn, but the general problem remains open, and the 2021 literature by co-authors of the TDDS paper still treats component superfluousness as undecidable in practice.

Problem Statement

Let kk be a computable differential field of characteristic zero admitting a splitting algorithm (for instance k=Qk=\mathbb{Q} or k=Q(x1,…,xm)k=\mathbb{Q}(x_1,\ldots,x_m) with the standard partial derivatives), and let k{y1,…,yn}k\{y_1,\ldots,y_n\} be the ring of differential polynomials over kk.

The Ritt problem: does there exist an algorithm that, given the characteristic sets of two prime differential ideals P1P_1 and P2P_2 of k{y1,…,yn}k\{y_1,\ldots,y_n\}, decides whether P1⊆P2P_1\subseteq P_2?

By the proven equivalence theorem of Golubitsky-Kondratieva-Ovchinnikov, an affirmative answer is equally an algorithm for any of the following: computing the essential, that is non-redundant, prime decomposition of a radical differential ideal given by a finite set of generators; deciding whether such an ideal is prime; computing a finite generator set of a prime differential ideal from one of its characteristic sets; or deciding whether a given differential polynomial is a zero divisor modulo a radical differential ideal. Equivalently, following the TDDS formulation: given a Thomas decomposition, or any characteristic-set decomposition, of a polynomially nonlinear differential system, decide which output components are essential, that is produce an irredundant decomposition, and thereby decide, for an analytic solution specified by differential data, for instance by the characteristic set of its vanishing prime differential ideal, that is singular with respect to some components, to which essential prime components it belongs. The question is posed in full generality, for arbitrary numbers of derivations and differential indeterminates and arbitrary rankings, not merely for a restricted class of systems; a resolving answer is either a proven terminating decision algorithm or a proof that no such algorithm exists over the stated class of base fields.

References

  1. V. P. Gerdt, M. Lange-Hegermann, D. Robertz, The MAPLE package TDDS for computing Thomas decompositions of systems of nonlinear PDEs, Computer Physics Communications 234 (2019) 202-215, DOI 10.1016/j.cpc.2018.07.025, preprint arXiv:1801.09942, https://arxiv.org/abs/1801.09942
  2. M. Lange-Hegermann, D. Robertz, W. M. Seiler, M. Seiss, Singularities of algebraic differential equations, Advances in Applied Mathematics 131 (2021) Article 102266, DOI 10.1016/j.aam.2021.102266, preprint arXiv:2002.11597, https://arxiv.org/abs/2002.11597
  3. O. Golubitsky, M. Kondratieva, A. Ovchinnikov, On the generalized Ritt problem as a computational problem, Journal of Mathematical Sciences (New York) 163 (2009) 515-522, DOI 10.1007/s10958-009-9689-3, preprint arXiv:0809.1128, https://arxiv.org/abs/0809.1128
  4. J. F. Ritt, On the singular solutions of algebraic differential equations, Annals of Mathematics (2) 37 (1936) 552-617, DOI 10.2307/1968478, https://www.jstor.org/stable/1968478
  5. E. Hubert, Factorization-free decomposition algorithms in differential algebra, Journal of Symbolic Computation 29 (2000) 641-662, DOI 10.1006/jsco.1999.0344, https://doi.org/10.1006/jsco.1999.0344
  6. E. R. Kolchin, Differential Algebra and Algebraic Groups, Pure and Applied Mathematics vol. 54, Academic Press, New York, 1973, zbMATH Zbl 0264.12102, https://zbmath.org/?q=an:0264.12102
  7. R. M. Cohn, Specializations of differential kernels and the Ritt problem, Journal of Algebra 61 (1979) 256-268, DOI 10.1016/0021-8693(79)90316-8, https://doi.org/10.1016/0021-8693(79)90316-8, zbMATH Zbl 0432.12016, https://zbmath.org/?q=an:0432.12016
  8. R. M. Cohn, Valuations and the Ritt problem, Journal of Algebra 101 (1986) 1-15, DOI 10.1016/0021-8693(86)90093-1, https://doi.org/10.1016/0021-8693(86)90093-1, zbMATH Zbl 0593.12012, https://zbmath.org/?q=an:0593.12012
  9. M. Lange-Hegermann, The differential counting polynomial, Foundations of Computational Mathematics 18 (2018) 291-308, DOI 10.1007/s10208-018-9378-z, https://doi.org/10.1007/s10208-018-9378-z
  10. J. Cano, S. Falkensteiner, D. Robertz, J. R. Sendra, Algebraic and Puiseux series solutions of systems of autonomous algebraic ODEs of dimension one in several variables, Journal of Symbolic Computation 114 (2023) 1-17, DOI 10.1016/j.jsc.2022.04.012, https://doi.org/10.1016/j.jsc.2022.04.012
  11. T. Bächler, V. P. Gerdt, M. Lange-Hegermann, D. Robertz, Algorithmic Thomas decomposition of algebraic and differential systems, Journal of Symbolic Computation 47 (2012) 1233-1266, DOI 10.1016/j.jsc.2011.12.043, https://doi.org/10.1016/j.jsc.2011.12.043
  12. A. Ovchinnikov, G. Pogudin, T. N. Vo, Bounds for elimination of unknowns in systems of differential-algebraic equations, International Mathematics Research Notices 2022 (2022) 12342-12377, DOI 10.1093/imrn/rnaa302, https://doi.org/10.1093/imrn/rnaa302