Deciding strong irreducibility of ascending chains and computing prime decompositions of perfect ideals of differential-difference polynomials

The characteristic set method of Gao, Van der Hoeven, Yuan and Zhang for mixed differential-difference (DD) polynomial systems (J. Symbolic Comput. 44(9):1137-1163, 2009) decomposes the zero set of any finitely generated DD-polynomial system into unions of zero sets of regular and proper irreducible ascending chains and solves the perfect ideal membership problem, but it cannot decompose the perfect DD-ideal generated by the system into an intersection of prime ideals. The authors state that this requires an algorithm for checking whether a chain is strongly irreducible - whether the algebraic extension of the chain with respect to every DD-polynomial is an irreducible triangular set - which they explicitly leave as an open problem, and they further acknowledge that finite bases for the differential saturation ideals of transformed chains are generally not known to be computable. This record states that problem in the ordinary mixed setting (one derivation and one translation, interacting by $\partial\delta = h\cdot\delta\partial$, over an inversive computable base field): give a decision procedure for strong irreducibility of ascending chains (equivalently, for primeness of their saturation ideals, which by the source's Theorem 5.17 coincide with reflexive prime DD-ideals), construct the induced Ritt-style decomposition of perfect DD-ideals into reflexive prime components, and, subsidiarily, compute finite bases for the transformed differential saturations.

Background

A difference field is a field $K$ equipped with an injective endomorphism $\delta$ (a translation, or shift operator), and a differential field carries a derivation $\partial$ (an additive map satisfying the Leibniz product rule). Difference algebra, originated by Ritt and Raudenbush for algebraic difference equations and systematized in Cohn's monograph, studies polynomial systems in unknowns $y$ together with all their transforms $\delta^k y$; differential algebra does the same with derivatives. Systems that mix both operators - delay differential equations, discretized PDE schemes, hybrid continuous-discrete models - lead to mixed differential-difference (DD) polynomial systems.

The source paper works in the ordinary mixed setting: $K$ is a computable field containing $\mathbb{Q}(x)$, equipped with a derivation $\partial$ and a translation $\delta$ related by $\partial\delta = h\cdot\delta\partial$ for a fixed nonzero $h \in K$, and $K$ is inversive ($\delta$ surjective on $K$, called reflexive in the paper). The DD-polynomial ring $K\{y_1,\dots,y_n\}$ is obtained by closing the indeterminates under both operators. A DD-ideal is an algebraic ideal closed under $\partial$ and $\delta$; it is reflexive if $\delta P \in I$ implies $P \in I$, and perfect if it contains every polynomial some transform-power product of which lies in it - the radical-type closure governing vanishing sets; perfect ideals are automatically reflexive, and $\{\mathbb{P}\}$ denotes the perfect ideal generated by a set $\mathbb{P}$.

The characteristic set method (the Wu-Ritt triangularization technique) represents ideals by ascending chains, that is, finite triangular sets $\mathcal{A}$ of DD-polynomials with distinct leading variables, and by their saturation ideals $\mathrm{sat}(\mathcal{A})$, which saturate with respect to the initials and separants of the chain and all their transforms. In the algebraic and differential settings, Rosenfeld's Lemma reduces membership and ideal-theoretic properties of the saturation ideal to algebraic computations with the finite triangular set, and this underlies the classical constructive decompositions into prime (irreducible) components. In the DD setting Rosenfeld's Lemma fails - the source paper gives an explicit coherent chain whose saturation ideal contains a polynomial undetectable by the algebraic counterpart - so the paper introduces a hierarchy of chain classes: coherent and regular chains (a chain is the characteristic set of its saturation ideal, so membership is decided by pseudo-remainders), proper irreducible chains (a constructive regularity criterion, combining algebraic irreducibility of a finite extension $\mathcal{A}^*$ of the chain with a closure condition on the differential saturation $\mathrm{dsat}(\overline{\mathcal{A}})$ of the difference part $\overline{\mathcal{A}}$ of the chain), and strongly irreducible chains: a proper irreducible chain $\mathcal{A}$ is strongly irreducible if for every DD-polynomial $P$ the algebraic extension $\mathcal{A}_P$ of $\mathcal{A}$ with respect to $P$ (the algebraic triangular set built from $\mathcal{A}$ and the variables of $P$) is an irreducible triangular set. The paper's central structure theorem (Theorem 5.17) states that a coherent chain is strongly irreducible if and only if its saturation ideal is a reflexive prime DD-ideal, and conversely every reflexive prime DD-ideal is the saturation ideal of its strongly irreducible characteristic set.

What the paper achieves: the Noetherian property for DD-systems, a zero-decomposition algorithm splitting the zero set of any finitely generated DD-polynomial set into zero sets of proper irreducible (hence regular and reflexive) chains, and an algorithm for the perfect ideal membership problem. What it cannot do: decompose a perfect DD-ideal into an intersection of prime ideals. The authors state this verbatim as an open problem whose missing ingredient is the strong-irreducibility test - the definition quantifies over all DD-polynomials $P$, and no finite reduction of this infinitary condition is known. The paper also demonstrates that proper irreducibility does not imply primeness (a chain can factor only after applying a difference transform), and that the proper-irreducibility test itself requires membership checks in differential saturation ideals $\mathrm{dsat}(\overline{\mathcal{A}})$ of transformed chains for which finite bases are generally not known to be computable, so some steps are made constructive only by bypassing techniques. In the pure differential case, prime decomposition is classical via Rosenfeld's Lemma; in the pure difference case only partial criteria are known (for certain chains); the mixed case is the remaining gap.

Problem Statement

In the setting of the source paper - the ordinary mixed differential-difference polynomial ring $K\{y_1,\dots,y_n\}$ over a computable, inversive DD-field $K$ containing $\mathbb{Q}(x)$, with derivation $\partial$ and translation $\delta$ satisfying $\partial\delta = h\cdot\delta\partial$ for some nonzero $h \in K$, under an admissible elimination ranking - the following problems, stated as open by Gao, Van der Hoeven, Yuan and Zhang, remain:

(1) Strong irreducibility decision problem. Given an ascending chain $\mathcal{A}$ of DD-polynomials, decide whether $\mathcal{A}$ is strongly irreducible. Strong irreducibility is defined for proper irreducible chains, and proper irreducibility is itself decidable by the source paper's algorithm (Proposition 6.3), so the problem is well posed on arbitrary ascending chains: a chain that fails the proper-irreducibility test is simply not strongly irreducible. Concretely, decide whether, for every DD-polynomial $P$, the algebraic extension $\mathcal{A}_P$ of $\mathcal{A}$ with respect to $P$ is an irreducible triangular set; equivalently (together with coherence, by the source's Theorem 5.17), whether the saturation ideal $\mathrm{sat}(\mathcal{A})$ is a reflexive prime DD-ideal.

(2) Prime (irreducible) decomposition. Given a finite set $\mathbb{P}$ of DD-polynomials, compute a finite family of coherent, strongly irreducible chains $\mathcal{A}_1,\dots,\mathcal{A}_m$ whose saturation ideals are reflexive prime DD-ideals and whose intersection equals the perfect DD-ideal $\{\mathbb{P}\}$; equivalently, decompose the DD-variety of $\mathbb{P}$ into finitely many irreducible components with their characteristic sets.

(3) Subsidiary constructive gap, as flagged by the authors. For chains arising in the proper-irreducibility test, compute finite bases for the differential saturation ideals $\mathrm{dsat}(\overline{\mathcal{A}})$ of the difference parts $\overline{\mathcal{A}}$ of transformed chains, so that the membership checks in the definition of proper irreducibility become fully constructive without extra hypotheses.

The single scientific objective uniting these deliverables is to extend the Ritt-style algorithmic ideal decomposition theory - prime components and irreducible decomposition - from the algebraic and differential settings to the mixed differential-difference setting: item (1) is the load-bearing decision problem that item (2) requires within the characteristic set framework, and item (3) is the acknowledged constructive gap inside the current regularity machinery. The decomposition theory is sought in the stated generality - arbitrary finitely generated DD-polynomial systems over any admissible base field, with no restriction to special classes such as binomial ideals or bounded-order chains. On the negative branch, if no terminating decision algorithm for strong irreducibility exists, then, since (2) requires deciding strong irreducibility of the chains it must produce, no algorithm computes the decomposition asked in (2).

References

1. X. S. Gao, J. Van der Hoeven, C. M. Yuan, G. L. Zhang, "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; author preprint (full text) at https://www.texmacs.org/joris/charset/charset.pdf
2. X. S. Gao, Y. Luo, C. M. Yuan, "A characteristic set method for ordinary difference polynomial systems", Journal of Symbolic Computation 44(3):242-260, 2009. DOI: 10.1016/j.jsc.2007.05.005; https://doi.org/10.1016/j.jsc.2007.05.005
3. X. S. Gao, C. M. Yuan, G. L. Zhang, "Ritt-Wu's characteristic set method for ordinary difference polynomial systems with arbitrary ordering", Acta Mathematica Scientia 29(4):1063-1080, 2009. DOI: 10.1016/S0252-9602(09)60086-2; https://doi.org/10.1016/S0252-9602(09)60086-2
4. G.-L. Zhang, X. Gao, "Properties of Ascending Chains for Partial Difference Polynomial Systems", in: Computer Mathematics (ASCM 2007, Revised and Invited Papers), Springer, 2008, pp. 307-321. DOI: 10.1007/978-3-540-87827-8_25; https://doi.org/10.1007/978-3-540-87827-8_25
5. C. Yuan, X.-S. Gao, "A criterion for testing whether a difference ideal is prime", Journal of Systems Science and Complexity 22(4):627-635, 2009. DOI: 10.1007/s11424-009-9192-4; https://doi.org/10.1007/s11424-009-9192-4
6. Z. Gan, M. Zhou, "A characteristic set method for reflexive differential-difference polynomial systems", Proceedings of the 2nd International Conference on Computer Science and Electronics Engineering (ICCSEE 2013), Atlantis Press, 2013, pp. 295-300. DOI: 10.2991/ICCSEE.2013.76; https://doi.org/10.2991/ICCSEE.2013.76
7. Z. Gan, M. Zhou, "Decomposition of Reflexive Differential-Difference Polynomial Systems", Applied Mechanics and Materials 380-384:1645-1648, 2013. DOI: 10.4028/www.scientific.net/AMM.380-384.1645; https://doi.org/10.4028/www.scientific.net/AMM.380-384.1645
8. W. Li, A. Ovchinnikov, G. Pogudin, T. Scanlon, "Elimination of unknowns for systems of algebraic differential-difference equations", Transactions of the American Mathematical Society 374(1):303-326, 2021. DOI: 10.1090/tran/8219; arXiv:1812.11390; https://arxiv.org/abs/1812.11390
9. A. Ovchinnikov, G. Pogudin, T. Scanlon, "Effective difference elimination and Nullstellensatz", Journal of the European Mathematical Society 22(8):2419-2452, 2020. DOI: 10.4171/jems/968; arXiv:1712.01412; https://arxiv.org/abs/1712.01412
10. G. Pogudin, T. Scanlon, M. Wibmer, "Solving difference equations in sequences: universality and undecidability", Forum of Mathematics, Sigma 8, 2020. DOI: 10.1017/fms.2020.14; arXiv:1909.03239; https://arxiv.org/abs/1909.03239
11. A. Levin, "On the Ascending Chain Condition for Mixed Difference Ideals", International Mathematics Research Notices 2015(10):2830-2840, 2015 (published online 28 February 2014). DOI: 10.1093/imrn/rnu021; arXiv:1207.4721; https://arxiv.org/abs/1207.4721
12. A. Levin, "Bivariate Dimension Polynomials of Non-Reflexive Prime Difference-Differential Ideals. The Case of One Translation", Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation (ISSAC 2018), ACM, 2018, pp. 255-262. DOI: 10.1145/3208976.3209008; https://doi.org/10.1145/3208976.3209008
13. A. Levin, "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; https://doi.org/10.1016/j.jsc.2019.10.014
14. X.-S. Gao, Z. Huang, C.-M. Yuan, "Binomial difference ideals", Journal of Symbolic Computation 80:665-706, 2017. DOI: 10.1016/j.jsc.2016.07.029; arXiv:1603.03987; https://arxiv.org/abs/1603.03987
15. W. Li, C.-M. Yuan, "Elimination Theory in Differential and Difference Algebra", Journal of Systems Science and Complexity 32(1):287-316, 2019. DOI: 10.1007/s11424-019-8367-x; https://doi.org/10.1007/s11424-019-8367-x
16. R. F. Bustamante Medina, "Differentially closed fields of characteristic zero with a generic automorphism", Revista de Matematica: Teoria y Aplicaciones 14(1):81-100, 2007. DOI: 10.15517/rmta.v14i1.282; https://doi.org/10.15517/rmta.v14i1.282
17. R. M. Cohn, "Difference Algebra", Interscience Tracts in Pure and Applied Mathematics 17, Interscience Publishers / John Wiley & Sons, New York, 1965. zbMATH: Zbl 0127.26402; https://zbmath.org/3207354
18. J. F. Ritt, H. W. Raudenbush, "Ideal theory and algebraic difference equations", Transactions of the American Mathematical Society 46:445-452, 1939. DOI: 10.1090/s0002-9947-1939-0000605-4; https://doi.org/10.1090/s0002-9947-1939-0000605-4
19. A. Rosenfeld, "Specializations in differential algebra", Transactions of the American Mathematical Society 90:394-407, 1959. DOI: 10.1090/s0002-9947-1959-0107642-2; https://doi.org/10.1090/s0002-9947-1959-0107642-2
20. X. Gao, Z. Li, "Mechanized methods for differential and difference equations" (in Chinese, English summary), Journal of Systems Science and Mathematical Sciences 29(9):1222-1237, 2009. zbMATH: Zbl 1212.68447; https://zbmath.org/5733431