Algorithmic computation of multivariate differential dimension polynomials for nonlinear differential field extensions, and the classification of their invariants

For a finitely generated differential field extension $L/K$ whose commuting derivation set $\Delta$ is partitioned into blocks $\Delta=\Delta_1\cup\cdots\cup\Delta_p$, Levin's multivariate differential dimension polynomial $\Phi_{\eta|K}(t_1,\dots,t_p)$ refines the classical Kolchin polynomial: it records the transcendence degrees of the fields generated by derivatives whose order in each derivation block is separately bounded, and thereby captures finer birational invariants of the extension and of the systems of algebraic PDEs the extension describes. Existence and the basic invariant theory are known (Levin 2001; Levin, ISSAC 2020), and in the linear (differential-module) setting the polynomial is computable by Gröbner-basis methods with respect to several orderings. For a nonlinear extension, however, given by generators of the prime differential ideal it defines, no algorithm is known, because the classical Ritt–Kolchin characteristic-set algorithm relies on a single ranking of the derivatives and does not extend to the multiple term orderings induced by the partition; the corresponding theory of autoreduced sets is in its infancy. The problem asks for a provably terminating algorithm computing $\Phi_{\eta|K}$ for arbitrary finitely generated differential field extensions, together with the classification of all invariants of these polynomials and of their relationships across different partitions of the derivation set.

Background

A differential field is a field $K$ of characteristic zero equipped with a finite set $\Delta=\{\delta_1,\dots,\delta_m\}$ of commuting derivations (for example, rational functions in variables $x_1,\dots,x_m$ with $\delta_i=\partial/\partial x_i$). The ring of differential polynomials $K\{y_1,\dots,y_n\}$ is the ordinary polynomial ring in the infinitely many indeterminates $\theta y_j$, where $\theta=\delta_1^{e_1}\cdots\delta_m^{e_m}$ ranges over all derivative operators; a finitely generated differential field extension $L=K\langle\eta_1,\dots,\eta_n\rangle$ is obtained by adjoining to $K$ finitely many elements together with all their derivatives. Writing $\operatorname{trdeg}$ for transcendence degree, the differential transcendence degree $\Delta\text{-}\operatorname{trdeg}_K L$ is the maximal number of elements of $L$ all of whose derivatives are algebraically independent over $K$.

For such an extension, Kolchin's differential dimension polynomial (the Kolchin polynomial) is the unique numerical polynomial $\omega_{\eta|K}(t)$ — a polynomial with rational coefficients taking integer values at all nonnegative integers, hence an integer combination of the binomial polynomials $\binom{t+i}{i}$ — such that

$$\omega_{\eta|K}(r)=\operatorname{trdeg}_K K(\theta\eta_j:\operatorname{ord}\theta\le r,\ 1\le j\le n)$$

for all sufficiently large $r$, where $\operatorname{ord}\theta=e_1+\cdots+e_m$. It is the differential-algebraic analogue of the Hilbert polynomial: its leading coefficient equals $\Delta\text{-}\operatorname{trdeg}_K L$, and its degree and lower coefficients (the type and typical dimension) are birational invariants of the extension, central to the dimension theory of differential algebra, to the model theory of differentially closed fields, and to measuring the 'strength' of a system of algebraic partial differential equations, i.e. the amount of free data in its general solution. The classical route to computing $\omega_{\eta|K}$ is the Ritt–Kolchin characteristic-set method. One fixes a ranking, meaning a well-ordering of the derivative operators that is compatible with differentiation; the leader of a differential polynomial is its highest-ranked derivative, and a finite set of differential polynomials is autoreduced if no member contains a derivative, other than itself, of another member's leader. A characteristic set of a prime differential ideal $P$ is an autoreduced subset of $P$ of lowest rank from which membership in $P$ can be tested by reduction, and the Kolchin polynomial is read off combinatorially from the leaders of such a set. The Ritt–Kolchin algorithm constructs a characteristic set from any finite generating set of a differential ideal by an iterative autoreduction scheme whose termination rests on the well-ordering of a single ranking; modern characteristic-decomposition algorithms in computer algebra have made the univariate computation routine and extended it from prime to characterizable differential ideals, i.e. differential ideals that coincide with the ordinary polynomial ideal generated by one of their characteristic sets, so that purely algebraic reduction suffices to test membership (see the monograph of Kondratieva, Levin, Mikhalev and Pankratiev for the univariate theory, and Lange-Hegermann's algorithmic treatment of characterizable ideals).

When the independent variables fall into groups with different roles — for instance space variables versus time — one wants a finer invariant that treats the groups separately. Fixing a partition $\Delta=\Delta_1\cup\cdots\cup\Delta_p$ into nonempty blocks with $\operatorname{Card}\Delta_i=m_i$, Levin (2001) introduced the multivariate differential dimension polynomial $\Phi_{\eta|K}(t_1,\dots,t_p)$: the unique numerical polynomial in $p$ variables such that

$$\Phi_{\eta|K}(r_1,\dots,r_p)=\operatorname{trdeg}_K K(\theta\eta_j:\operatorname{ord}_{\Delta_i}\theta\le r_i\ \text{for every } i,\ 1\le j\le n)$$

for all tuples with every $r_i$ sufficiently large, where $\operatorname{ord}_{\Delta_i}\theta$ is the total order of $\theta$ along the derivations of block $\Delta_i$. Existence was proved with a specially designed reduction and characteristic-set technique that uses, simultaneously, the $p$ term orderings $<_1,\dots,<_p$ on the derivatives, each of which compares the order within one derivation block first. The polynomial admits the canonical expansion $\Phi_{\eta|K}=\sum a_{i_1\dots i_p}\prod_{j=1}^{p}\binom{t_j+i_j}{i_j}$ with integer coefficients and $\deg_{t_j}\Phi_{\eta|K}\le m_j$, and it refines the Kolchin polynomial, which is the case $p=1$. Its invariant content is richer: Levin's ISSAC 2020 paper proved that the coefficient $a_{m_1\dots m_p}$ of the top summand equals $\Delta\text{-}\operatorname{trdeg}_K L$; that $\Phi_{\eta|K}$ takes its simplest form $d\prod_{j=1}^{p}\binom{t_j+m_j}{m_j}$ exactly when the generators are algebraically independent over $K$ in the ordinary sense (a multivariate analogue of a theorem of Sit and Johnson from 1979); and that coefficients of terms involving only some of the variables encode differential transcendence degrees of subextensions obtained by differentiating only within the complementary blocks.

What is missing is computation. If the extension is defined by linear differential equations — equivalently, one computes with finitely generated modules over the commutative ring $K[\delta_1,\dots,\delta_m]$ of differential operators — then Gröbner-basis methods with respect to several orderings compute the multivariate polynomials (Levin 2007, with later extensions to modules over Weyl algebras by Dönch and Levin). But for a general nonlinear extension, given by a finite generating set of the prime differential ideal $P\subset K\{y_1,\dots,y_n\}$ that it defines, computing $\Phi_{\eta|K}$ requires a characteristic set of $P$ with respect to the multiple term orderings $<_1,\dots,<_p$ at once, and here the classical theory breaks down: the Ritt–Kolchin reduction algorithm and its termination proof rely on a single ranking; the theory of autoreduced sets with respect to several orderings exists only at the level needed for the existence proof of $\Phi$; and the analogous machinery that Levin built for difference and difference-differential polynomial rings depends essentially on the translation operators and has no published pure-differential counterpart. As a consequence, no algorithm is known that computes $\Phi_{\eta|K}$ for nonlinear extensions, and the invariant structure of these polynomials across different partitions of $\Delta$ is only partially mapped.

Problem Statement

Let $K$ be a differential field of characteristic zero with a finite commuting set of derivations $\Delta=\{\delta_1,\dots,\delta_m\}$, and fix a partition $\Delta=\Delta_1\cup\cdots\cup\Delta_p$ into nonempty blocks with $\operatorname{Card}\Delta_i=m_i$. Let $L=K\langle\eta_1,\dots,\eta_n\rangle$ be a finitely generated differential field extension, presented by a finite set $F\subset K\{y_1,\dots,y_n\}$ of differential polynomials generating the prime differential ideal $P$ of all differential polynomial relations satisfied by $\eta_1,\dots,\eta_n$ over $K$. Let $\Phi_{\eta|K}(t_1,\dots,t_p)$ be the multivariate differential dimension polynomial of the extension associated with the generators and the partition, that is, the unique numerical polynomial with

$$\Phi_{\eta|K}(r_1,\dots,r_p)=\operatorname{trdeg}_K K(\theta\eta_j:\operatorname{ord}_{\Delta_i}\theta\le r_i\ \text{for all }i,\ 1\le j\le n)$$

for all tuples $(r_1,\dots,r_p)$ with each $r_i$ sufficiently large; its existence, the degree bounds $\deg_{t_i}\Phi_{\eta|K}\le m_i$, and the integer-coefficient canonical expansion in the binomial basis are known.

Both objectives below are required parts of the task, and the algorithm of (1) must handle both input representations described there.

(1) Primary objective — make $\Phi$ effectively computable in the nonlinear case. Construct an explicit, provably terminating algorithm that takes as input the finite set $F$ (or, when no primality is promised, finite generators of an arbitrary differential ideal together with a decomposition of it into prime or characterizable components) and the partition of $\Delta$, and outputs the multivariate differential dimension polynomial $\Phi_{\eta|K}(t_1,\dots,t_p)$, the unique numerical polynomial equal to the transcendence-degree function above. The algorithm must handle arbitrary finitely generated, in general nonlinear, extensions; restricting to linear defining equations or to differential modules does not suffice, since those cases are already computable by several-ordering Gröbner-basis methods.

(2) Secondary objective — complete the invariant theory. Determine exactly which characteristics of $\Phi_{\eta|K}$ — its coefficients $a_{i_1\dots i_p}$ in the canonical expansion in the binomial basis and its partial degrees $\deg_{t_i}\Phi_{\eta|K}$ — are invariants of the extension, i.e. independent of the choice of the finite system of generators, and classify the relationships among the invariants obtained from different partitions of $\Delta$: which invariants of a coarser partition are determined by a refinement, and how the invariants of a nontrivial partition relate to the classical Kolchin polynomial and to the differential transcendence degrees of the subextensions defined by subsets of $\Delta$.

References

1. Alexander Levin. Some properties of multivariate differential dimension polynomials and their invariants. Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation (ISSAC '20), ACM, 2020. DOI: 10.1145/3373207.3404013. https://doi.org/10.1145/3373207.3404013
2. Alexander B. Levin. Multivariable dimension polynomials and new invariants of differential field extensions. International Journal of Mathematics and Mathematical Sciences, 2001. DOI: 10.1155/S0161171201006767. https://doi.org/10.1155/S0161171201006767
3. Alexander B. Levin. Gröbner bases with respect to several orderings and multivariable dimension polynomials. Journal of Symbolic Computation, 2007. DOI: 10.1016/j.jsc.2006.05.006. https://doi.org/10.1016/j.jsc.2006.05.006
4. Alexander Levin. Multivariate Difference-Differential Dimension Polynomials and New Invariants of Difference-Differential Field Extensions. arXiv:1302.1505, 2013. https://arxiv.org/abs/1302.1505 (journal version: Mathematics in Computer Science, 2020, DOI: 10.1007/s11786-019-00436-1)
5. Alexander Levin. Generalized Gröbner Bases and New Properties of Multivariate Difference Dimension Polynomials. Proceedings of the 2021 International Symposium on Symbolic and Algebraic Computation (ISSAC '21), ACM, 2021. DOI: 10.1145/3452143.3465544. https://doi.org/10.1145/3452143.3465544
6. Alexander Levin. Bivariate Kolchin-type dimension polynomials of non-reflexive prime difference-differential ideals. The case of one translation. Journal of Symbolic Computation, 2021. DOI: 10.1016/j.jsc.2019.10.014. https://doi.org/10.1016/j.jsc.2019.10.014 (preprint: arXiv:1909.08957)
7. Alexander Levin. Generalized characteristic sets and new multivariate difference dimension polynomials. Applicable Algebra in Engineering, Communication and Computing, 2024. DOI: 10.1007/s00200-023-00628-0. https://doi.org/10.1007/s00200-023-00628-0
8. Alexander Levin. New Difference Gröbner Bases and Bivariate Difference Dimension Polynomials. Mathematics in Computer Science, 2024. DOI: 10.1007/s11786-024-00589-8. https://doi.org/10.1007/s11786-024-00589-8
9. Alexander Levin. Bivariate Differential Dimension Polynomials via Bigraded Rees Construction. Proceedings of the 2026 International Symposium on Symbolic and Algebraic Computation (ISSAC '26), ACM, 2026. DOI: 10.1145/3815436.3815456. https://doi.org/10.1145/3815436.3815456
10. Alexander Levin. New dimension polynomials of inversive difference field extensions and inversive difference modules. Journal of Symbolic Computation, 2026. DOI: 10.1016/j.jsc.2025.102521. https://doi.org/10.1016/j.jsc.2025.102521
11. Alexander Levin. Multivariate Bernstein-type Polynomials of Finitely Generated D-Modules. arXiv:2404.02069, 2024. https://arxiv.org/abs/2404.02069
12. Christian Dönch and Alexander Levin. Computation of Bivariate Characteristic Polynomials of Finitely Generated Modules over Weyl Algebras. arXiv:1212.1833, 2012. https://arxiv.org/abs/1212.1833 (journal version: Bivariate dimension polynomials and new invariants of finitely generated D-modules, International Journal of Algebra and Computation 23(7), 1625–1651, 2013. DOI: 10.1142/S0218196713500409. https://doi.org/10.1142/S0218196713500409)
13. Markus Lange-Hegermann. The Differential Dimension Polynomial for Characterizable Differential Ideals. arXiv:1401.5959, 2014. https://arxiv.org/abs/1401.5959
14. William Sit and Joseph Johnson. On the Differential Transcendence Polynomials of Finitely Generated Differential Field Extensions. American Journal of Mathematics, 1979. DOI: 10.2307/2374138. https://doi.org/10.2307/2374138
15. M. V. Kondratieva, A. B. Levin, A. V. Mikhalev, E. V. Pankratiev. Differential and Difference Dimension Polynomials. Kluwer Academic Publishers, 1999. DOI: 10.1007/978-94-017-1257-6. https://doi.org/10.1007/978-94-017-1257-6
16. James Freitag, Omar León Sánchez, and Wei Li. Effective definability of Kolchin polynomials. Proceedings of the American Mathematical Society, 2019. DOI: 10.1090/proc/14869. https://doi.org/10.1090/proc/14869
17. Omar León Sánchez. Estimates for the coefficients of differential dimension polynomials. Mathematics of Computation, 2019. DOI: 10.1090/mcom/3429. https://doi.org/10.1090/mcom/3429