Deciding strong irreducibility of difference ascending chains and primeness of difference saturation ideals

In the characteristic-set approach to ordinary difference polynomial systems, the saturation ideal of a difference ascending chain is a reflexive prime difference ideal exactly when the chain is coherent and strong irreducible, so deciding primeness of the ideals produced by the method reduces to deciding strong irreducibility of chains. Yuan and Gao (2009) gave sufficient coprimality criteria covering certain chains, but the general decision problem they left open remains unsolved: no algorithm is known that decides, for an arbitrary difference ascending chain over a computable inversive difference field of characteristic zero, whether the chain is strong irreducible - equivalently whether its saturation ideal is prime - and no impossibility result is known either. The problem is the difference-algebraic counterpart of the classical Ritt problem in differential algebra, and computing irreducible (prime) decompositions of general difference varieties is blocked precisely on it. Only special classes are currently decidable: coprime-degree patterns, control-form chains via a Jacobian criterion, and binomial/monomial difference ideals via lattice criteria.

Background

Difference algebra studies systems of equations of the form $P(\dots,\sigma^j y_i,\dots)=0$, where $\sigma$ is a fixed injective endomorphism of a base field $\mathbb{K}$ (the pair $(\mathbb{K},\sigma)$ is called a difference field), called the transforming operator; for example $\mathbb{K}=\mathbb{Q}(t)$ with $\sigma(t)=t+1$, so that such systems describe recurrences. The field is called inversive when $\sigma$ is an automorphism. The difference polynomial ring $\mathbb{K}\{y_1,\dots,y_n\}$ is the polynomial ring in all transforms $\sigma^j y_i$ ($j\ge 0$); a difference ideal is an ideal closed under $\sigma$, and it is reflexive if $\sigma f\in I$ implies $f\in I$. Reflexive prime difference ideals play the role of irreducible subvarieties in difference algebraic geometry, so testing them is the difference analog of testing irreducibility of an algebraic variety.

The characteristic set method of Ritt and Wu is the standard elimination tool: it rewrites a finite polynomial system as an ascending chain $\mathcal{A}=A_1<\dots<A_m$, a triangular set in which each $A_i$ involves only the transforms of one leading variable. From a chain one forms the saturation ideal $\operatorname{sat}(\mathcal{A})=[\mathcal{A}]:\mathbb{I}_{\mathcal{A}}^{\infty}$, obtained from the difference ideal $[\mathcal{A}]$ generated by the chain by inverting the multiplicative set $\mathbb{I}_{\mathcal{A}}$ generated by the initials (leading coefficients) of the $A_i$ and their transforms. In the purely algebraic case, irreducible chains have prime saturation ideals and all the relevant properties are decidable by polynomial factorization. In the difference case this fails. Gao, Luo, and Yuan (2009) proved that a chain is the characteristic set of a reflexive prime difference ideal if and only if it is coherent (a pairwise pseudo-remainder compatibility condition on the rows of the chain that share the same leading variable) and strong irreducible, where strong irreducible means that for every tuple of nonnegative integers $(h_1,\dots,h_m)$ the extension $\mathcal{A}(h_1,\dots,h_m)$ is an irreducible algebraic triangular set. The extension is defined in Gao, Luo, and Yuan (reference [2], Section 3.2, formula (3)) with all occurring transforms treated as independent algebraic variables: grouping the rows of the chain into blocks by leading variable, it contains, for each block, transforms of the first row up to a bound fixed by the order of the second row, the intermediate rows themselves, and transforms of the last row up to a bound $\hat h_i$ coupled recursively to $h_i$ and to the orders of the rows above; for a chain with a single row per leading variable, quantifying over all tuples $(h_1,\dots,h_m)$ amounts to requiring irreducibility of every finite truncation of the chain and its transforms. Their zero-decomposition algorithm produces coherent proper irreducible chains, which need not be strong irreducible, so the prime-decomposition step of the difference characteristic set method is blocked exactly on deciding strong irreducibility.

Two phenomena make this decision problem hard. First, Cohn's classical example: over $\mathbb{Q}(t)$ with $\sigma t=t+1$, the chain $\mathcal{A}=\{x_1^2+t, x_2^2+t+k\}$ has $\operatorname{sat}(\mathcal{A})$ not prime for every integer $k>1$, because $A_2-\sigma^k A_1=(x_2-\sigma^k x_1)(x_2+\sigma^k x_1)$; the witnessing factorization appears at transform order $k$, and $k$ is unbounded across a family whose members all have the same orders and degrees. Hence no test that inspects transforms only up to a bound calibrated to the order and degrees of the input can decide the property in general. Second, the key structural lemmas of the algebraic and differential theories (Rosenfeld's lemma and Lazard's lemma) have no difference analog, so irreducibility at any finite stage of the transform hierarchy does not propagate to later stages.

Yuan and Gao (2009) gave the first broadly applicable sufficient criteria: if an irreducible difference polynomial $P$ of positive order has degree $d$ in its highest transform and degree $s\neq 0$ in the base variable with $\gcd(s,d)=1$, then $P$ is strong irreducible and $\operatorname{sat}(P)$ is a reflexive prime difference ideal; an analogous pairwise-coprime condition on selected degrees decides strong irreducibility for multi-row chains. These criteria cover many chains met in practice but leave arbitrary chains undecided. Later work decided further special classes: chains of control-theory form $V_i\sigma x_i-U_i$ via nonvanishing of a Jacobian determinant (Gao, Yuan, and Zhang, 2009), and monomial and Laurent binomial difference ideals via $\mathbb{Z}[x]$-lattice saturation criteria, with a complete prime decomposition algorithm inside the binomial class (Gao, Huang, and Yuan, 2017). On the effective side, Ovchinnikov, Pogudin, and Scanlon (2020) proved a difference Nullstellensatz and elimination theorem with explicit bounds on transform orders, making consistency and bounded-order consequences of difference systems decidable - but these bounds control ideal membership, not factorizations, and do not decide primeness. In differential algebra the analogous question, the classical Ritt problem (whether inclusion of prime differential ideals given by characteristic sets is algorithmically decidable), is a recognized open computational problem (Golubitsky, Kondratieva, and Ovchinnikov, 2009); no reduction between the differential and difference cases is known.

Problem Statement

Let $\mathbb{K}$ be a computable inversive difference field of characteristic zero (for instance $\mathbb{Q}(t_1,\dots,t_r)$ with $\sigma(t_i)=t_i+1$), and let $\mathcal{A}=A_1<\dots<A_m$ be an ordinary difference ascending chain in $\mathbb{K}\{y_1,\dots,y_n\}$ - ordinary meaning that a single transforming operator $\sigma$ is used, as opposed to the partial case of several commuting operators. The decision problem ranges over arbitrary such chains, and in particular over the coherent proper irreducible chains produced by the characteristic-set zero-decomposition algorithm. Recall that $\mathcal{A}$ is strong irreducible if for every tuple of nonnegative integers $(h_1,\dots,h_m)$ - one truncation order for each leading variable of the chain - the extension $\mathcal{A}(h_1,\dots,h_m)$ is an irreducible algebraic triangular set, all occurring transforms being treated as independent algebraic variables. The extension is defined precisely in Gao, Luo, and Yuan (reference [2], Section 3.2, formula (3)): grouping the rows of the chain into blocks $A_{i,1}<\dots<A_{i,k_i}$ by leading variable $y_i$, with $o_{i,j}=\operatorname{ord}(A_{i,j},y_i)$, it contains, for each block, the transforms of the first row $A_{i,1}$ up to order $o_{i,2}-o_{i,1}-1$, the intermediate rows $A_{i,2},\dots,A_{i,k_i-1}$ themselves, and the transforms of the last row $A_{i,k_i}$ up to order $\hat h_i-o_{i,k_i}$, where the bounds are coupled recursively downward from the top block by $\hat h_i=\max\{h_i,o_i,o_{i,k_i}\}+1$, with $o_i$ the maximum order of $y_i$ occurring in the already-constructed transforms of the blocks above (and $\hat h=\max\{h,o_{k}\}+1$ for the top block). For a chain with a single row per leading variable - in particular in the single-polynomial case included below - quantifying over all tuples $(h_1,\dots,h_m)$ is equivalent to requiring irreducibility of every finite truncation. (In the sources the notion is defined for proper irreducible chains; the chains output by the zero-decomposition algorithm of Gao, Luo, and Yuan are coherent and proper irreducible, so the definition applies to them, and the condition is restated here directly so that it is meaningful for arbitrary chains.) By the criterion of Gao, Luo, and Yuan, a chain is the characteristic set of a reflexive prime difference ideal if and only if it is coherent and strong irreducible, so for the chains considered here, deciding strong irreducibility is equivalent to deciding primeness of the saturation ideal $\operatorname{sat}(\mathcal{A})=[\mathcal{A}]:\mathbb{I}_{\mathcal{A}}^{\infty}$, where $\mathbb{I}_{\mathcal{A}}$ is the multiplicative set generated by the initials of the $A_i$ and their transforms.

The problem is to settle the general decision question left open by Yuan and Gao (2009): either give an algorithm which, on input any such chain $\mathcal{A}$ (in particular any chain arising in the characteristic-set zero-decomposition of a finite system of difference polynomials), terminates and correctly decides whether $\mathcal{A}$ is strong irreducible - equivalently, for coherent input chains, whether $\operatorname{sat}(\mathcal{A})$ is prime; or give effectively checkable necessary and sufficient structural conditions on $\mathcal{A}$ from which such a decision procedure follows; or prove that no such algorithm exists. The single-polynomial case is included: decide whether a non-linear difference polynomial $P$ of positive order is strong irreducible, i.e. whether the triangular set $(P,\sigma P,\dots,\sigma^n P)$ is irreducible for every $n$. An affirmative answer is expected to yield, via the equivalence above, an algorithm decomposing any finitely generated perfect difference ideal into an intersection of reflexive prime difference ideals - the step currently missing from the difference characteristic set method.

References

1. 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
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. Gui-Lin Zhang, Xiao-Shan Gao. Properties of Ascending Chains for Partial Difference Polynomial Systems. In: Computer Mathematics (ASCM 2007), Lecture Notes in Computer Science 5081, pp. 307-321, Springer, 2008. DOI: 10.1007/978-3-540-87827-8_25. https://doi.org/10.1007/978-3-540-87827-8_25
4. Xiaoshan Gao, Chunming Yuan, Guilin 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
5. Xiao-Shan Gao, Zhang Huang, Chun-Ming Yuan. Binomial difference ideals. Journal of Symbolic Computation 80:665-706, 2017. DOI: 10.1016/j.jsc.2016.07.029. arXiv:1603.03987. https://doi.org/10.1016/j.jsc.2016.07.029
6. 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. arXiv:1712.01412. https://doi.org/10.4171/jems/968
7. O. D. Golubitsky, M. V. Kondratieva, A. I. Ovchinnikov. On the generalized Ritt problem as a computational problem. Journal of Mathematical Sciences 163(5):515-522, 2009. DOI: 10.1007/s10958-009-9689-3. arXiv:0809.1128. https://doi.org/10.1007/s10958-009-9689-3