Deciding strong irreducibility of differential–difference chains and constructing reflexive prime decompositions of perfect differential–difference ideals

For polynomial systems whose unknowns are acted on simultaneously by a derivation and a shift automorphism — differential–difference (DD) systems, which mix differential equations and recurrences — the characteristic set method of Gao, Van der Hoeven, Yuan and Zhang (2009) decomposes zero sets into coherent, proper irreducible ascending chains and decides membership in perfect DD-ideals, but stops short of the prime layer. The paper explicitly leaves open (a) that no algorithm is known to decide whether a DD-ascending chain is strongly irreducible, the paper's characterization of when its saturation ideal is a reflexive prime DD-ideal, and (b) that no constructive procedure expresses a perfect DD-ideal as a finite intersection of reflexive prime DD-ideals, which the authors state would require such a strong-irreducibility test; and it observes for (c) that finite bases for the differential saturation ideals of the difference parts of extended chains — the ideals that enter its definition of proper irreducibility — are generally not known how to compute, a computation its own algorithms avoid rather than perform. As of 2026 all three remain open: the only directly on-topic follow-ups (Gan–Zhou 2013) decompose reflexive DD systems into strictly weaker coherent components; the strong-irreducibility criterion of Yuan–Gao 2009 covers only restricted pure-difference chain classes and has never been extended; effective elimination and consistency theorems for difference and mixed rings do not address irreducibility or prime decomposition; and the purely differential analogue (full irreducibility, equivalent to the generalized Ritt problem) is itself open, so a resolution of the mixed case would be a major surprise.

Background

Many models in mathematics and its applications couple continuous evolution with discrete shifts: differential–difference equations (recurrence–differential equations) describe, for instance, lattices of coupled oscillators, delayed control systems, and discretizations that retain continuous parameters. Algebraically, such a system is a finite set of polynomial equations in unknown functions on which two operators act: a derivation $\delta$ (formal differentiation) and an automorphism $\sigma$ (the shift, with inverse $\sigma^{-1}$). Polynomials built from these operators are differential–difference (DD) polynomials, and the natural algebraic framework is the DD-polynomial ring with its DD-ideals — ideals closed under $\delta$ and $\sigma$ — and, importantly, reflexive DD-ideals, which are also closed under $\sigma^{-1}$. The perfect DD-ideal $\{\mathbb{P}\}$ generated by a finite DD-polynomial set $\mathbb{P}$ is the smallest perfect (radical, in the DD sense) reflexive DD-ideal containing $\mathbb{P}$; its zero set is exactly the solution set of $\mathbb{P}=0$.

The characteristic set method, introduced by Ritt and Kolchin for differential algebra and by Ritt and Wu for polynomial systems, triangulates an input system into an ascending chain (a triangular sequence of polynomials with strictly increasing leading operators) from which membership and zero-set structure can be read off. Gao, Van der Hoeven, Yuan and Zhang (2009) developed this method for DD-polynomial systems. Their central notions are: a coherent chain (the leaders of the chain's polynomials are compatible under the $\delta$ and $\sigma$ actions, so the chain behaves like a consistent triangular system); the saturation $\mathrm{sat}(\mathcal{A})$ of a chain $\mathcal{A}$, roughly the DD-ideal of all polynomials vanishing on the general component of the chain's zero set, obtained by saturating the ideal generated by the chain and its transforms by the initials (leading coefficients) and by making it reflexive and radical; and two irreducibility notions for chains. A chain is properly irreducible when a certain explicitly checkable algebraic condition holds on the leading DD-polynomial; this is computable and implies regularity and that $\mathrm{sat}(\mathcal{A})$ is reflexive, but it does not imply primeness. A proper irreducible chain is strongly irreducible when for every DD-polynomial $P$ its extension $\mathcal{A}_P$ — the algebraic triangular set of transforms of the chain's elements obtained by treating all transformed unknowns as algebraically independent variables (Algorithm Extension, Section 3.2 of the paper) — is algebraically irreducible, that is, regular with no product of two polynomials reduced with respect to it lying in its algebraic saturation; the paper proves (Theorem 5.17) that $\mathrm{sat}(\mathcal{A})$ is a reflexive prime DD-ideal exactly when $\mathcal{A}$ is coherent and strongly irreducible. The main algorithm of the paper, ZDT, decomposes the zero set of any finite DD-polynomial set into a finite union of zero sets of coherent, properly irreducible chains, and as a corollary membership in a perfect DD-ideal is decidable.

So after the 2009 paper the effective theory of DD systems reaches exactly the level of regular (quasi-prime) components but not the prime level: ZDT's output components need not be irreducible, and recognizing when a chain's saturation is a reflexive prime DD-ideal requires verifying strong irreducibility, a condition that quantifies over all DD-polynomials $P$ — an infinite family of algebraic irreducibility tests for which no decision procedure is given. The definition of proper irreducibility also involves the differential saturation $\mathrm{dsat}(\bar{\mathcal{A}})=[\bar{\mathcal{A}}]_{\delta}:H_{\bar{\mathcal{A}}}^{\infty}$ (Eq. (12) of the paper) of the difference part $\bar{\mathcal{A}}$ of the extension $\mathcal{A}^{*}=\mathcal{A}_{\sigma\mathcal{A}}$ of the chain with respect to the shift transforms of its elements — the bottom $\sigma$-transforms of the chain's elements, viewed as differential polynomials, which form a differential triangular set (Lemma 5.3 of the paper). The paper observes that finite bases for such saturation ideals are generally not known how to compute; its own proper-irreducibility test (ProIrr, Section 6.1, via the differential characteristic set algorithm DCS) avoids needing such bases. The situation contrasts with the purely algebraic case, where prime decompositions of radical ideals are computable via factorization and Gröbner bases, and with the purely differential case, where prime decomposition of differential ideals is computable (Hubert 2000) but irreducibility testing of individual chains — the full irreducibility problem, equivalent to the generalized Ritt problem of Golubitsky, Kondratieva and Ovchinnikov — remains open. In the difference and mixed settings there is an additional structural obstruction: Levin showed that the ascending chain condition fails for mixed difference ideals, so Noetherian finite-basis strategies are unavailable.

Problem Statement

Work in the setting of Gao, Van der Hoeven, Yuan and Zhang (2009): a differential–difference (DD) field with commuting derivation $\delta$ and automorphism $\sigma$, DD-polynomial rings, DD-ascending chains, and the saturation ideal $\mathrm{sat}(\mathcal{A})=[\mathcal{A}]:H_{\mathcal{A}}^{\infty}$ of a chain. (The source paper denotes the derivation by $\partial$ and the shift by $\delta$; this statement uses $\delta$ and $\sigma$ throughout, so $\mathcal{A}^{*}=\mathcal{A}_{\sigma\mathcal{A}}$ here corresponds to $\mathcal{A}_{\delta\mathcal{A}}$ in the paper.) The problem is to complete the characteristic set theory of perfect DD-ideals to the prime layer, in three linked parts identified in the source paper: (a) and (b) are explicitly left open there, and (c) is an open computation the paper acknowledges and circumvents in its own algorithms.

(a) Strong-irreducibility decision. Given a DD-ascending chain $\mathcal{A}$ (say, presented by a finite DD-polynomial set), decide by a terminating algorithm whether $\mathcal{A}$ is strongly irreducible — that is (the definition applies to proper irreducible chains), whether for every DD-polynomial $P$ the extension $\mathcal{A}_P$ of the chain (Algorithm Extension, Section 3.2 of the paper: an algebraic triangular set of transforms of the elements of $\mathcal{A}$ in which all transformed unknowns are treated as algebraically independent variables) is an algebraically irreducible triangular set, namely regular and with no product of two polynomials reduced with respect to it lying in its algebraic saturation. By the paper's characterization (Theorem 5.17) this is equivalent to deciding, for a coherent chain, whether $\mathrm{sat}(\mathcal{A})$ is a reflexive prime DD-ideal. The known checkable condition (proper irreducibility) is strictly weaker, so the required algorithm must verify a condition quantified over infinitely many polynomials $P$.

(b) Reflexive prime decomposition. Given a finite DD-polynomial set $\mathbb{P}$, either construct a finite collection of DD-chains $\mathcal{A}_1,\dots,\mathcal{A}_m$ with each $\mathrm{sat}(\mathcal{A}_i)$ a reflexive prime DD-ideal such that $\{\mathbb{P}\}=\mathrm{sat}(\mathcal{A}_1)\cap\cdots\cap\mathrm{sat}(\mathcal{A}_m)$, or prove that no such finite intersection exists for general $\mathbb{P}$ and characterize the inputs for which it does. The source paper states that a constructive version of this decomposition would require an algorithm of type (a).

(c) Saturation bases for difference parts. The definition of proper irreducibility involves the differential saturation $\mathrm{dsat}(\bar{\mathcal{A}})=[\bar{\mathcal{A}}]_{\delta}:H_{\bar{\mathcal{A}}}^{\infty}$ (Eq. (12) of the paper) of the difference part $\bar{\mathcal{A}}$ of the extension $\mathcal{A}^{*}=\mathcal{A}_{\sigma\mathcal{A}}$, which is a differential triangular set (Lemma 5.3 of the paper); the paper observes that "we generally do not know how to compute a basis for this ideal", and its own proper-irreducibility test avoids needing such bases. Provide an algorithm that computes finite (differential) bases for these saturation ideals without extra hypotheses, or prove none exists.

Parts (a)–(c) form one scientific objective: an effective prime-level decomposition theory for mixed differential–difference systems, in which (a) is the recognition primitive, (b) the decomposition built on it, and (c) the constructive saturation calculus for the differential saturation ideals arising in the definition of proper irreducibility. The three parts are jointly posed; (b) is not independent of (a), since its constructive branch presupposes an algorithm of type (a). A decision procedure valid only for a proper subclass, with the general case left open, does not resolve the problem.

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, https://doi.org/10.1016/j.jsc.2008.02.010
2. Xiao-Shan Gao, Yong Luo, Chunming 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. Chunming Yuan, Xiao-Shan 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
4. Zhi Wang Gan, Meng 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
5. Zhiwang Gan, Meng Zhou, A characteristic set method for reflexive differential-difference polynomial systems, Proceedings of the 2nd International Conference on Computer Science and Electronics Engineering (2013). DOI: 10.2991/iccsee.2013.76, https://doi.org/10.2991/iccsee.2013.76
6. Oleg Golubitsky, Marina Kondratieva, Alexey Ovchinnikov, On the generalised Ritt problem as a computational problem (2008). arXiv:0809.1128, https://arxiv.org/abs/0809.1128
7. Alexander Levin, On the ascending chain condition for mixed difference ideals (2012). arXiv:1207.4721, https://arxiv.org/abs/1207.4721
8. Jie Wang, Monomial Difference Ideals (2016). arXiv:1601.01148, https://arxiv.org/abs/1601.01148
9. Jie Wang, Finite Basis for Radical Well-Mixed Difference Ideals Generated by Binomials (2016). arXiv:1610.06990, https://arxiv.org/abs/1610.06990
10. Gleb Pogudin, Primitive Element Theorem for Fields with Commuting Derivations and Automorphisms (2018). arXiv:1812.11375, https://arxiv.org/abs/1812.11375
11. Alexey Ovchinnikov, Gleb Pogudin, Thomas Scanlon, Effective difference elimination and Nullstellensatz, Journal of the European Mathematical Society 22(8):2419–2452 (2020). DOI: 10.4171/jems/968, https://doi.org/10.4171/jems/968 (preprint arXiv:1712.01412)
12. Wei Li, Alexey Ovchinnikov, Gleb Pogudin, Thomas Scanlon, Elimination of unknowns for systems of algebraic differential-difference equations, Transactions of the American Mathematical Society 374(1):303–326 (2020). DOI: 10.1090/tran/8219, https://doi.org/10.1090/tran/8219 (preprint arXiv:1812.11390)
13. James Freitag, Omar León Sánchez, Wei Li, Effective definability of Kolchin polynomials (2018). arXiv:1806.02060, https://arxiv.org/abs/1806.02060
14. Alexander 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 (preprint arXiv:1909.08957)
15. Wei Li, Chun-Ming 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. Bertrand Teguia Tabuguia, Computing with D-Algebraic Sequences (2024). arXiv:2412.20630, https://arxiv.org/abs/2412.20630
17. Evelyne Hubert, Factorization-free decomposition algorithms in differential algebra, Journal of Symbolic Computation 29(4–5):641–662 (2000). DOI: 10.1006/jsco.1999.0344, https://doi.org/10.1006/jsco.1999.0344
18. D. Bouziane, A. Kandri Rody, H. Maârouf, Unmixed-dimensional decomposition of a finitely generated perfect differential ideal, Journal of Symbolic Computation 31(6):631–649 (2001). DOI: 10.1006/jsco.1999.1562, https://doi.org/10.1006/jsco.1999.1562