Deciding strong irreducibility of difference ascending chains and computing reflexive prime decompositions of perfect difference ideals

The characteristic-set method of Gao, Luo and Yuan for nonlinear ordinary difference polynomial systems (J. Symbolic Comput. 44(3), 2009) proves that a coherent and strongly irreducible difference ascending chain is the characteristic set of a reflexive prime difference ideal — strong irreducibility is defined for proper irreducible chains and demands that the chain together with all its finitely shifted transforms form an irreducible algebraic triangular set for every choice of shift bounds — and that every reflexive prime difference ideal admits such a characteristic set under a suitable variable order. Regularity has a constructive substitute in the paper (proper irreducibility), but strong irreducibility does not: no procedure is given, or known, to decide it. Consequently the paper's Ritt-Wu algorithm decomposes a difference polynomial system only into regular components whose saturation ideals need not be prime, and it remains unknown how to decompose the perfect difference ideal generated by a finite system into an intersection of reflexive prime ideals. The problem posed here: give an algorithm that decides, for an arbitrary difference ascending chain over an inversive difference field of characteristic zero, whether it is strongly irreducible (in the source's sense: proper irreducible, with every shifted transform family $\mathcal{A}^{(h_1,\ldots,h_p)}$ an irreducible algebraic triangular set), and thereby an algorithm computing the reflexive prime decomposition of any finitely generated perfect difference ideal; a rigorous undecidability proof for this input class would resolve the decision problem equally. Follow-up literature supplies criteria only for special classes (coprimality of degrees; binomial difference ideals) and repeatedly records the general case as open, most explicitly in 2009 and again in 2017.

Background

Difference algebra studies systems of equations relating the successive shifts $y(x)$, $y(x+1)$, $y(x+2), \ldots$ of unknown sequences; it is the discrete analogue of differential algebra. A difference field $(\mathcal{K}, \delta)$ is a field equipped with a shift operator $\delta$ (here assumed to be an automorphism, i.e. the field is inversive, and of characteristic zero; the model case is $\mathbb{Q}(x)$ with $\delta: f(x) \mapsto f(x+1)$). For indeterminates $y_1, \ldots, y_n$, the ring of difference polynomials $\mathcal{K}\{y_1, \ldots, y_n\}$ is the polynomial ring in all transforms $\delta^j y_i$ ($j = 0, 1, 2, \ldots$) with the induced action of $\delta$; a difference ideal is an ideal stable under $\delta$. A solution of a finite system $\mathcal{P}$ of difference polynomials is a tuple from a difference extension field of $\mathcal{K}$ annihilating every member of $\mathcal{P}$. The perfect closure $\{\mathcal{P}\}$ — obtained from the difference ideal $[\mathcal{P}]$ by closing under the rule that a product of transforms of a difference polynomial lies in the ideal only if the polynomial does, and under reflexivity ($\delta P \in I \Rightarrow P \in I$) — is the difference analogue of the radical and, by the classical theory of Ritt and Cohn, is the vanishing ideal of the solution set of $\mathcal{P}$ over all difference extension fields.

Triangular methods rewrite such systems as unions of simpler ones. An ascending chain $\mathcal{A} = A_1, \ldots, A_m$ is a finite set of difference polynomials with strictly increasing ranks, each reduced with respect to the others; the initial of a chain element is its leading coefficient, and the saturation ideal $\operatorname{sat}(\mathcal{A})$ is the smallest difference ideal containing $\mathcal{A}$ in which every initial — and every transform of every initial — becomes invertible. $\mathcal{A}$ is a characteristic set of an ideal when every element of the ideal pseudo-reduces to zero modulo $\mathcal{A}$. In the algebraic case, Aubry, Lazard and Moreno Maza proved that a triangular set is a characteristic set of its saturated ideal exactly when it is regular (its initials are invertible); the differential analogue, built on Rosenfeld's reduction lemma and Lazard's lemma, underlies the classical decomposition of differential ideals into prime components in the tradition of Ritt and Kolchin.

These lemmas fail for difference chains, because the shift of a difference polynomial is not linear in its leading variable. Gao, Luo and Yuan therefore introduced chain conditions adapted to the difference case. Coherence is an effectively checkable compatibility condition among the transforms of chain elements that share a leading variable; regularity requires all transforms of the initials to be invertible; they proved that $\mathcal{A}$ is a characteristic set of $\operatorname{sat}(\mathcal{A})$ if and only if $\mathcal{A}$ is coherent and regular. Proper irreducibility — a finite algebraic irreducibility pattern across the variable blocks of the chain, including an effectiveness (leading-variable occurrence) condition — is their constructive sufficient condition for regularity, and a coherent proper irreducible chain provably has a nonempty zero set (via Cohn's theory of difference kernels, the algebraic data specifying a generic solution of a difference system). On this basis their Ritt-Wu zero-decomposition algorithm splits the zero set of any finite difference polynomial system into zero sets of saturation ideals of coherent proper irreducible chains, which also decides consistency of such systems and solves perfect-ideal membership.

What the theory does not deliver is the prime level. Writing the chain in the source's block form with $p$ leading variables and writing $\mathcal{A}^{(h_1, \ldots, h_p)}$ for its extension — the algebraic triangular set consisting of the chain elements together with their transforms up to recursively determined shift bounds $\hat h_i \ge h_i$ (each transform treated as a separate algebraic variable; Section 3.2 of the source, eqs. (1)–(3) and Lemma 3.3) — a proper irreducible chain is called strongly irreducible if $\mathcal{A}^{(h_1, \ldots, h_p)}$ is an irreducible algebraic triangular set for every $(h_1, \ldots, h_p) \in \mathbb{N}^p$. Gao-Luo-Yuan proved that a coherent and strongly irreducible chain has a reflexive prime saturation ideal (prime as an algebraic ideal among all transforms, and reflexive), and conversely that every reflexive prime difference ideal admits a coherent strongly irreducible characteristic set under a suitable variable order — an intrinsic chain-level analogue of Cohn's earlier criterion by characteristic sequences. The converse is existential over variable orders: the paper explicitly notes that not every characteristic set of a reflexive prime ideal is strongly irreducible (for instance, a characteristic set of $[y_2(x+1)+y_1(x)]$ under the order $y_1 < y_2$ is not effective and hence not strongly irreducible), so primeness of the saturation ideal of a given chain does not imply its strong irreducibility. But strong irreducibility quantifies over infinitely many shift tuples, and no method is known to decide it: this is the explicit gap between the regular decomposition the algorithm computes and a difference-algebraic analogue of prime decomposition.

Problem Statement

Let $\mathcal{K}$ be an inversive difference field of characteristic zero with effectively computable arithmetic (for instance $\mathbb{Q}(x)$ with $\delta: x \mapsto x+1$), and work in the difference polynomial ring $\mathcal{K}\{y_1, \ldots, y_n\}$. After a suitable renaming of the variables, a difference ascending chain $\mathcal{A}$ can be written in the block form of the source (Section 3.2, form (1)) with $p$ leading variables $y_1, \ldots, y_p$ — block $i$ consisting of the chain elements whose leading variable is $y_i$ — and a parameter set $U = \{u_1, \ldots, u_q\}$ with $p + q = n$. For a tuple of nonnegative integers $(h_1, \ldots, h_p)$, let $\mathcal{A}^{(h_1, \ldots, h_p)}$ denote the extension of $\mathcal{A}$ in the sense of the source (Section 3.2, eq. (3)): the sequence consisting of each chain element together with its transforms up to recursively determined bounds $\hat h_i \ge h_i$ (including the intermediate transforms inserted between consecutive elements of the same block), which is an algebraic triangular set when every occurring transform of every parameter and of every leading variable is treated as a separate algebraic variable, with parameters $V \cup P(\mathcal{A})$ in the sense of the source's Lemma 3.3. Recall that $\mathcal{A}$ is proper irreducible (source, Section 4.1) if its zero-shift extension $\mathcal{A}^{(0, \ldots, 0)}$ is an irreducible algebraic triangular set and, for each block $c$, the first element $A_{c,1}$ is effective — its leading variable $y_c(x)$ occurs in it — and remains irreducible after specialization by a generic point of the preceding blocks.

(1) Strong-irreducibility decision. Give an algorithm that takes as input a difference ascending chain $\mathcal{A}$ — in particular the coherent and proper irreducible chains produced by the Ritt-Wu zero decomposition — and decides whether $\mathcal{A}$ is strongly irreducible, that is (following the source's definition, which is stated for proper irreducible chains), whether $\mathcal{A}$ is proper irreducible and $\mathcal{A}^{(h_1,\ldots,h_p)}$ is an irreducible algebraic triangular set for every $(h_1,\ldots,h_p) \in \mathbb{N}^p$. A coherent and strongly irreducible chain has a reflexive prime saturation ideal (source, Theorem 4.3), so such a decision procedure is the missing step toward prime-level decomposition; the chain-level converse, however, is existential (Theorem 4.4), and the source explicitly warns that not every characteristic set of a reflexive prime ideal is strongly irreducible, so primeness of $\operatorname{sat}(\mathcal{A})$ is a different, weaker predicate on a given chain and a test for it alone does not answer (1). The algorithm must be correct on arbitrary nonlinear chains over any such $\mathcal{K}$; criteria restricted to special classes (binomial difference ideals, coprimality patterns of degrees) do not answer the question.

(2) Reflexive prime decomposition. Give an algorithm that takes a finite set $\mathcal{P} \subset \mathcal{K}\{y_1, \ldots, y_n\}$ of difference polynomials and computes coherent strongly irreducible chains $\mathcal{A}_1, \ldots, \mathcal{A}_t$ such that

$\{\mathcal{P}\} = \operatorname{sat}(\mathcal{A}_1) \cap \cdots \cap \operatorname{sat}(\mathcal{A}_t),$

a decomposition of the perfect difference ideal generated by $\mathcal{P}$ into reflexive prime components, with the corresponding decomposition of the solution set of $\mathcal{P} = 0$ into irreducible difference varieties, each component carrying its dimension and order read off from its characteristic set.

These two deliverables form one scientific objective — an effective prime-decomposition theory for ordinary difference polynomial systems — and part (1) is its identified keystone: by the chain-level criterion above, a decision procedure for strong irreducibility is precisely what is missing to upgrade the existing regular decomposition of $\{\mathcal{P}\}$ into a decomposition into reflexive prime ideals, as the follow-up literature states explicitly (recording the general check of whether $\operatorname{sat}(\mathcal{A})$ is a reflexive prime difference ideal for a difference ascending chain as open in the same terms). A complete solution must therefore deliver the decision procedure of (1) and, derived from it, the decomposition algorithm of (2) made explicit for the coherent chains returned by the Ritt-Wu zero decomposition; the decision procedure of (1) alone does not resolve the objective. A rigorous proof that no algorithm as in (1) exists for this input class settles the whole objective equally, since (2) presupposes such a procedure. The problem is posed for ordinary difference polynomial systems in the full generality of the source paper; no restriction to binomial, linear, or fixed-order classes is admitted.

References

1. X.-S. Gao, Y. Luo, C. Yuan, A characteristic set method for ordinary difference polynomial systems, Journal of Symbolic Computation 44(3) (2009) 242-260. DOI: 10.1016/j.jsc.2007.05.005, https://doi.org/10.1016/j.jsc.2007.05.005
2. C. Yuan, X.-S. Gao, A criterion for testing whether a difference ideal is prime, Journal of Systems Science and Complexity 22(4) (2009) 627-635. DOI: 10.1007/s11424-009-9192-4, https://doi.org/10.1007/s11424-009-9192-4
3. 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) (2009) 1137-1163. DOI: 10.1016/j.jsc.2008.02.010, https://doi.org/10.1016/j.jsc.2008.02.010
4. 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 (2009) 1063-1080. DOI: 10.1016/S0252-9602(09)60086-2, https://doi.org/10.1016/S0252-9602(09)60086-2
5. G.-L. Zhang, X.-S. Gao, Properties of ascending chains for partial difference polynomial systems, in: Computer Mathematics (ASCM 2007), Lecture Notes in Computer Science 5081, Springer (2008) 307-321. DOI: 10.1007/978-3-540-87827-8_25, https://doi.org/10.1007/978-3-540-87827-8_25
6. M. Zhang, X.-S. Gao, Decomposition of ordinary difference polynomials, Journal of Symbolic Computation 44 (2009) 1394-1409. DOI: 10.1016/j.jsc.2009.04.001, https://doi.org/10.1016/j.jsc.2009.04.001
7. X.-S. Gao, Z. Huang, C.-M. Yuan, Binomial difference ideals, Journal of Symbolic Computation 80 (2017) 665-706. DOI: 10.1016/j.jsc.2016.07.029, https://doi.org/10.1016/j.jsc.2016.07.029 (preprint arXiv:1404.7580, 'Binomial Difference Ideal and Toric Difference Variety', https://arxiv.org/abs/1404.7580)
8. G. Pogudin, T. Scanlon, M. Wibmer, Solving difference equations in sequences: universality and undecidability, Forum of Mathematics, Sigma 8 (2020) e14. DOI: 10.1017/fms.2020.14, https://doi.org/10.1017/fms.2020.14 (arXiv:1909.03239, https://arxiv.org/abs/1909.03239)
9. A. Ovchinnikov, G. Pogudin, T. Scanlon, Effective difference elimination and Nullstellensatz, Journal of the European Mathematical Society 22 (2020) 2419-2452. DOI: 10.4171/jems/968, https://doi.org/10.4171/jems/968
10. W. Li, C. Yuan, Elimination theory in differential and difference algebra, Journal of Systems Science and Complexity 32 (2019) 287-316. DOI: 10.1007/s11424-019-8367-x, https://doi.org/10.1007/s11424-019-8367-x
11. V.P. Gerdt, D. Robertz, Algorithmic approach to strong consistency analysis of finite difference approximations to PDE systems, Proceedings of ISSAC 2019, ACM (2019) 163-170. DOI: 10.1145/3326229.3326255, https://doi.org/10.1145/3326229.3326255
12. J. Wang, Difference indices of quasi-prime difference algebraic systems, Journal of Symbolic Computation 87 (2018) 1-13. DOI: 10.1016/j.jsc.2017.05.004, https://doi.org/10.1016/j.jsc.2017.05.004
13. 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. DOI: 10.2991/iccsee.2013.76, https://doi.org/10.2991/ICCSEE.2013.76
14. R.M. Cohn, Difference Algebra, Interscience Tracts in Pure and Applied Mathematics 17, Interscience Publishers, New York (1965). zbMATH: 0127.26402, https://zbmath.org/3207354
15. P. Aubry, D. Lazard, M. Moreno Maza, On the theories of triangular sets, Journal of Symbolic Computation 28 (1999) 105-124. DOI: 10.1006/jsco.1999.0269, https://doi.org/10.1006/jsco.1999.0269
16. A. Rosenfeld, Specializations in differential algebra, Transactions of the American Mathematical Society 90 (1959) 394-407. zbMATH: 0192.14001, https://zbmath.org/3305245
17. D. Lazard, A new method for solving algebraic systems of positive dimension, Discrete Applied Mathematics 33 (1991) 147-160. DOI: 10.1016/0166-218X(91)90113-B, https://doi.org/10.1016/0166-218X(91)90113-B
18. E.R. Kolchin, Differential Algebra and Algebraic Groups, Academic Press, New York (1973). zbMATH: 0264.12102, https://zbmath.org/3415973
19. J.F. Ritt, Differential Algebra, American Mathematical Society Colloquium Publications 33, New York (1950). zbMATH: 0037.18402, https://zbmath.org/3056446