Effective computation of multivariate difference–differential dimension polynomials via characteristic sets with respect to several term orderings

For a finitely generated extension of a difference–differential field, Levin (2020) proved the existence of a multivariate dimension polynomial that refines the classical univariate Kolchin-type dimension polynomial by separately tracking transcendence growth along each block of a partition of the basic derivations and translations, determined its generator-independent invariants, and showed it distinguishes systems of algebraic difference–differential equations that the univariate polynomial cannot. The proof adapts the Ritt–Kolchin characteristic-set method to several simultaneous term orderings, but the published theory is essentially an existence and invariants theory: a coherence theory is provided only for linear ideals, the computation sketched in the preprint versions reduces the polynomial to a difference–differential Gröbner basis of the Kähler module via a generalized Buchberger algorithm yet carries no termination or complexity guarantee for the reduction steps, translation similarity, or inclusion–exclusion counting into the binomial basis, and the treated sufficient conditions and examples are linear. The problem is to make this theory effective: construct a provably terminating algorithm that computes the multivariate difference–differential dimension polynomial of a given defining ideal, in particular a nonlinear prime one. The problem remains open: all subsequent work concerns pure difference extensions or special bivariate mixed cases, and no implementation exists.

Background

A difference–differential field is a field $K$ equipped with finitely many commuting derivations $\delta_1,\dots,\delta_m$ (the differential structure, modeling continuous change) and commuting automorphisms $\alpha_1,\dots,\alpha_n$ (the difference, or shift, structure, modeling discrete change such as time steps or lattice translations). The ring of difference–differential ($\Delta$-$\sigma$-) polynomials $K\{y_1,\dots,y_s\}$ is the polynomial ring in all operator translates $\lambda y_j$, where $\lambda=\delta_1^{k_1}\cdots\delta_m^{k_m}\alpha_1^{l_1}\cdots\alpha_n^{l_n}$ with nonnegative derivation exponents and integer translation exponents. Such rings encode systems of algebraic difference–differential equations, which arise for instance as discretizations of partial differential equations and as differential–difference models. Given a finitely generated extension $L=K\langle\eta_1,\dots,\eta_s\rangle$ obtained by adjoining elements together with all their operator translates — equivalently, given the prime $\Delta$-$\sigma$-ideal $P$ of all algebraic relations among the translates — a fundamental invariant is the dimension polynomial: Kolchin proved for differential fields that the transcendence degree over $K$ of the field generated by the transforms of total order at most $t$ is, for all sufficiently large $t$, a polynomial in $t$. The classical univariate $\Delta$-$\sigma$-dimension polynomial collapses all derivations and translations into a single order parameter and hence carries only coarse invariants of the extension. Levin (2020) refined this by fixing a partition of the derivations into $p$ blocks and of the translations into $q$ blocks and proving that the transcendence degree of the field generated by transforms whose orders with respect to each block are bounded by $(r_1,\dots,r_{p+q})$ is, for all sufficiently large tuples, a polynomial $\Phi(t_1,\dots,t_{p+q})$ in $p+q$ variables; this polynomial has a canonical expansion in the binomial basis $\prod_v\binom{t_v+i_v}{i_v}$ and carries strictly more invariants (for a linear defining equation with parameters $a,b,c$ the univariate polynomial determines only $a+b+c$, while $\Phi$ determines $a$, $b$, $c$ individually, which decides instances of the equivalence problem for systems that the univariate polynomial cannot). The proof adapts the Ritt–Kolchin method of characteristic sets — autoreduced sets of $\Delta$-$\sigma$-polynomials whose leaders are selected simultaneously with respect to the $p+q$ term orderings, multiplicative reduction by translates of initials and separants, and inclusion–exclusion counting of the terms not divisible by any leader, where divisibility is complicated by translation similarity (translation exponent tuples lying in a common orthant of $\mathbb{Z}^n$). An autoreduced set is called coherent when every translate of every element reduces to zero modulo the set; the paper proves that coherent autoreduced sets characterize characteristic sets of linear $\Delta$-$\sigma$-ideals. However, the published constructive content stops short of a provably terminating computation: coherent sets are described only for linear ideals, the computation sketched in the preprint versions reduces $\Phi$ to a $\Delta$-$\sigma$-Gröbner basis of the Kähler module via a generalized Buchberger algorithm but comes with no termination or complexity analysis of the reduction and counting steps, and the sufficient conditions and worked examples concern linear defining equations; no implementation exists. The algorithmic side of the older univariate theory is well developed by contrast — reduced Gröbner bases in free difference–differential modules (Levin 2000), relative Gröbner bases computing the univariate difference–differential dimension polynomial (Zhou–Winkler 2008), whose termination was settled by Huang–Zhou (2015), and a characteristic-set method for differential–difference polynomial systems under a single ranking (Gao–Van der Hoeven–Yuan–Zhang 2009) — but none of these produces dimension polynomials that are multivariate in the block orders.

Problem Statement

Make the multivariate difference–differential dimension polynomial of Levin (2020) effectively computable. In the setting of a difference–differential field $K$ with basic derivations $\Delta=\{\delta_1,\dots,\delta_m\}$ partitioned into $p$ blocks and basic translations $\sigma=\{\alpha_1,\dots,\alpha_n\}$ partitioned into $q$ blocks, and a finitely generated extension $L=K\langle\eta_1,\dots,\eta_s\rangle$ given by its defining prime $\Delta$-$\sigma$-ideal $P\subseteq K\{y_1,\dots,y_s\}$ (specified by a finite set of generators), the source paper proves the existence of the multivariate $\Delta$-$\sigma$-dimension polynomial $\Phi(t_1,\dots,t_{p+q})$, with $\Phi(r_1,\dots,r_{p+q})$ equal to the transcendence degree over $K$ of the field generated by all transforms of the generators whose orders with respect to each block of derivations and translations are bounded by $r_1,\dots,r_{p+q}$, for all sufficiently large tuples, together with its binomial-basis expansion and invariants. The open problem is to turn this existence theory into a provably terminating computation: construct an algorithm that, given the finite generators of the defining prime $\Delta$-$\sigma$-ideal, computes $\Phi$ in its binomial-basis expansion for arbitrary finitely generated $\Delta$-$\sigma$-extensions in the general partition setting, with a proof of termination and, ideally, a complexity analysis in the numbers of derivations, translations, blocks, and generators. In particular, the algorithm must be correct for nonlinear prime defining ideals: the sufficient conditions and worked examples of the source paper are linear, whereas its existence theorem is proved for arbitrary defining prime ideals.

Coherence of autoreduced sets is currently characterized only for linear $\Delta$-$\sigma$-ideals, and no terminating algorithmic construction of characteristic sets with respect to the $p+q$ term orderings is known for general defining ideals.

References

1. Levin, Alexander: Multivariate Difference–Differential Dimension Polynomials. Mathematics in Computer Science 14(2), 361–374 (2020). DOI 10.1007/s11786-019-00436-1. https://doi.org/10.1007/s11786-019-00436-1
2. Levin, Alexander: Multivariate Difference-Differential Dimension Polynomials. Preprint (2012). arXiv:1207.4757. https://arxiv.org/abs/1207.4757
3. Levin, Alexander B.: Multivariate difference-differential dimension polynomials and new invariants of difference-differential field extensions. Proceedings of ISSAC 2013, 267–274 (2013). DOI 10.1145/2465506.2465521. Also arXiv:1302.1505. https://doi.org/10.1145/2465506.2465521
4. Kolchin, E. R.: The notion of dimension in the theory of algebraic differential equations. Bulletin of the American Mathematical Society 70, 570–573 (1964). DOI 10.1090/S0002-9904-1964-11203-9. https://doi.org/10.1090/S0002-9904-1964-11203-9
5. Kondratieva, M. V.; Levin, A. B.; Mikhalev, A. V.; Pankratiev, E. V.: Differential and Difference Dimension Polynomials. Kluwer Academic Publishers, Dordrecht (1999). DOI 10.1007/978-94-017-1257-6. https://doi.org/10.1007/978-94-017-1257-6
6. Levin, Alexander: Reduced Gröbner Bases, Free Difference–Differential Modules and Difference–Differential Dimension Polynomials. Journal of Symbolic Computation 30(4), 357–382 (2000). DOI 10.1006/jsco.1999.0412. https://doi.org/10.1006/jsco.1999.0412
7. Zhou, Meng; Winkler, Franz: Computing difference-differential dimension polynomials by relative Gröbner bases in difference-differential modules. Journal of Symbolic Computation 43(10), 726–745 (2008). DOI 10.1016/j.jsc.2008.02.001. https://doi.org/10.1016/j.jsc.2008.02.001
8. Huang, Guanli; Zhou, Meng: Termination of algorithm for computing relative Gröbner bases and difference differential dimension polynomials. Frontiers of Mathematics in China 10(3), 635–648 (2015). DOI 10.1007/s11464-015-0439-1. https://doi.org/10.1007/s11464-015-0439-1
9. Gao, X. S.; Van der Hoeven, J.; Yuan, C. M.; Zhang, G. L.: Characteristic set method for differential–difference polynomial systems. Journal of Symbolic Computation 44(9), 1137–1163 (2009). DOI 10.1016/j.jsc.2008.02.010. https://doi.org/10.1016/j.jsc.2008.02.010
10. Levin, Alexander: Bivariate Kolchin-type dimension polynomials of non-reflexive prime difference-differential ideals. The case of one translation. Journal of Symbolic Computation 102, 173–188 (2021). DOI 10.1016/j.jsc.2019.10.014. Also arXiv:1909.08957. https://doi.org/10.1016/j.jsc.2019.10.014
11. Levin, Alexander: Generalized characteristic sets and new multivariate difference dimension polynomials. Applicable Algebra in Engineering, Communication and Computing 35(1), 31–53 (2024). DOI 10.1007/s00200-023-00628-0. https://doi.org/10.1007/s00200-023-00628-0
12. Levin, Alexander: New Difference Gröbner Bases and Bivariate Difference Dimension Polynomials. Mathematics in Computer Science 18(3), Article 15 (2024). DOI 10.1007/s11786-024-00589-8. https://doi.org/10.1007/s11786-024-00589-8
13. Levin, Alexander: New Multivariate Dimension Polynomials of Inversive Difference Field Extensions. Journal of Mathematical Sciences 284(4), 508–526 (2024). DOI 10.1007/s10958-024-07367-8. Also arXiv:2309.05082. https://doi.org/10.1007/s10958-024-07367-8
14. Levin, Alexander: A New Type of Dimension Polynomials of Inversive Difference Field Extensions. Proceedings of ISSAC 2024, 126–133 (2024). DOI 10.1145/3666000.3669683. https://doi.org/10.1145/3666000.3669683
15. Levin, Alexander: New dimension polynomials of inversive difference field extensions and inversive difference modules. Journal of Symbolic Computation 134, Article 102521 (2026). DOI 10.1016/j.jsc.2025.102521. https://doi.org/10.1016/j.jsc.2025.102521
16. Fornasiero, Antongiulio; Kaplan, Elliot: Hilbert polynomials for finitary matroids. Pacific Journal of Mathematics 333(2), 273–308 (2024). DOI 10.2140/pjm.2024.333.273. Also arXiv:2208.01560. https://doi.org/10.2140/pjm.2024.333.273
17. Harfsheno, Hamzeh; Basiri, Abdolali; Rahmany, Sajjad: Generalization of Buchberger's Algorithm with Respect to Several Orderings on Difference Modules. Mathematical Researches 7(3), 513–526 (2021). DOI 10.52547/mmr.7.3.513. https://doi.org/10.52547/mmr.7.3.513