Merging difference resolvent chains into a single one-variable ascending chain

For a difference polynomial ideal represented by a coherent and strong irreducible ascending chain, the resolvent theory of Gao and Yuan (ISSAC 2006) computes a single resolvent chain in one new difference variable $w$: a characteristic set of the form $R,R_1,\ldots,R_s,I_1y_{1,0}-V_1,\ldots,I_py_{p,0}-V_p$ with controlled order, giving an effective primitive-element reduction of an irreducible difference variety to codimension one. For a merely proper irreducible chain, whose perfect saturation decomposes into several prime components, the theory guarantees only a finite family $\mathcal{R}_1,\ldots,\mathcal{R}_t$ of such one-variable chains whose saturation zero sets must be unioned (equivalently, an intersection of perfect ideals). It is open whether these resolvent chains can always be merged into a single coherent one-variable chain $\mathcal{B}$ with $\operatorname{Zero}(\operatorname{sat}(\mathcal{B}))=\bigcup_i\operatorname{Zero}(\operatorname{sat}(\mathcal{R}_i))$, together with a constructive criterion and algorithm for the merge.

Background

Fix a difference field $(\mathcal{K},\mathbf{E})$: a field equipped with a distinguished automorphism $\mathbf{E}$, the transforming operator (for sequences, the shift $a(n)\mapsto a(n+1)$). The ring of difference polynomials $\mathcal{K}\{y_1,\dots,y_n\}$ is the polynomial ring in the infinitely many formal transforms $\mathbf{E}^jy_i$; systems of difference polynomial equations define difference varieties, their common zero sets. A difference ideal is an ideal of this ring closed under $\mathbf{E}$. The radical-like closure appropriate to difference algebra is the perfect closure $\{I\}$, the smallest difference ideal containing $I$ with the property that whenever a product of transforms of an element lies in it, the element itself lies in it; two systems have the same zero set exactly when their perfect closures coincide, and irreducible difference varieties correspond to prime difference ideals. $\mathcal{K}$ is called aperiodic if for every $n$ some $a\in\mathcal{K}$ satisfies $\mathbf{E}^na\neq a$; this genericity hypothesis, needed for primitive-element choices, is assumed throughout the resolvent theory. Modern textbook treatments of this material are Cohn's monograph and Levin's book.

The computational engine is the characteristic set method for difference polynomial systems developed by Gao, Luo, and Yuan, the difference analogue of the Wu–Ritt elimination theory for polynomial systems (elimination by repeatedly extracting lowest-rank triangular generating sets). A difference ascending chain is a finite triangular set $\mathcal{A}=\{A_{1,1}(\mathbb{U},y_1),\dots,A_{p,k_p}(\mathbb{U},y_1,\dots,y_p)\}$ whose variables split into a parametric set $\mathbb{U}$ and leading variables $y_1,\dots,y_p$, each polynomial effective in its leading transform, i.e. genuinely involving a positive power of the transforming operator applied to its leading variable. The order of a difference polynomial in a variable is the highest transform index of that variable occurring in it, and $\operatorname{ord}(\mathcal{A})$ sums the orders of the first polynomial of each block. The saturation ideal $\operatorname{sat}(\mathcal{A})$ quotients out the initials (leading coefficients) of the chain's polynomials and all their transforms; coherence is the internal-consistency condition under which pseudo-division works; a chain is a characteristic set of its saturation when it has minimal rank there. A chain is proper irreducible if its algebraic (non-transformal) saturation is a prime algebraic ideal, and strong irreducible if this primality is uniform enough to force $\operatorname{sat}(\mathcal{A})$ itself to be a reflexive prime difference ideal (reflexive: closed under the inverse transform in the inversive closure); Yuan and Gao gave an effective criterion for the latter. Crucially, for a merely proper irreducible chain the perfect closure $\{\operatorname{sat}(\mathcal{A})\}$ can decompose into several prime components, all sharing the same parametric set, dimension, and order (the unmixedness theorem of Gao–Yuan), so even a single chain's saturation may define a reducible difference variety.

A resolvent is the difference-algebraic analogue of the primitive element trick. Classically (Cohn), every irreducible difference variety of positive dimension is birationally equivalent to a difference variety of codimension one describable in a single new difference variable $w=\sum_i\sigma_iy_i$. Gao and Yuan made this effective: for a coherent strong irreducible chain $\mathcal{A}$, their Theorem 4.1 and Algorithms 4.3–4.4 compute specializations $\sigma_i$ and a single resolvent chain, a characteristic set of $\operatorname{sat}(\mathcal{A},\,w-\sum_i\sigma_iy_i)$ of the form $R,R_1,\dots,R_s,I_1y_{1,0}-V_1,\dots,I_py_{p,0}-V_p$ with $R$ effective in $w$ and $\operatorname{ord}(R,w)=\operatorname{ord}(\mathcal{A})$, from which the original variables are recovered rationally; Corollary 4.2 thus realizes the birational equivalence with a codimension-one variety inside the same ambient transform structure, improving classical constructions that required inverse transforms. When $\mathcal{A}$ is proper irreducible but not strong, Theorem 5.1 still gives existence and order control at the level of the perfect ideal of the extended system, but the computed resolvent systems exist only as a finite family: by Theorem 5.2 and Algorithm 5.3 one obtains one-variable proper irreducible chains $\mathcal{R}_1,\dots,\mathcal{R}_t$ (each of the same resolvent form, with first resolvent polynomial of $w$-order equal to $\operatorname{ord}(\mathcal{A})$) such that

$$\operatorname{Zero}(\operatorname{sat}(\mathcal{A},\,w-\textstyle\sum_i\sigma_iy_i))=\bigcup_{i=1}^t\operatorname{Zero}(\operatorname{sat}(\mathcal{R}_i)),$$

equivalently $\{\operatorname{sat}(\mathcal{A},\,w-\sum_i\sigma_iy_i)\}=\bigcap_i\{\operatorname{sat}(\mathcal{R}_i)\}$. In the differential-algebraic sibling theory the corresponding representation problem is settled: Cluzeau and Hubert proved that every regular differential ideal admits a representation by a single resolvent together with a rewriting system. No difference analogue is known, and the difference setting is intrinsically harder because difference polynomial rings are non-Noetherian — perfect difference ideals do not satisfy the ascending chain condition in general (Levin).

Problem Statement

Let $\mathcal{K}$ be an aperiodic difference field and let $\mathcal{A}$ be a coherent and proper irreducible difference ascending chain with parametric set $\mathbb{U}$ and leading variables $y_1,\dots,y_p$, whose perfect saturation $\{\operatorname{sat}(\mathcal{A})\}$ has more than one prime component. Let $\mathcal{R}_1,\dots,\mathcal{R}_t$ be the one-variable proper irreducible resolvent chains computed for $\mathcal{A}$ (Gao–Yuan, Algorithm 5.3, with nondegenerate specializations $\sigma_i$), so that

$$\operatorname{Zero}(\operatorname{sat}(\mathcal{A},\,w-\textstyle\sum_i\sigma_iy_i))=\bigcup_{i=1}^t\operatorname{Zero}(\operatorname{sat}(\mathcal{R}_i)),$$

equivalently $\{\operatorname{sat}(\mathcal{A},\,w-\sum_i\sigma_iy_i)\}=\bigcap_{i=1}^t\{\operatorname{sat}(\mathcal{R}_i)\}$, each first resolvent polynomial having $w$-order equal to $\operatorname{ord}(\mathcal{A})$.

Does there always exist a single coherent difference ascending chain $\mathcal{B}$ in the one variable $w$ over the same parametric set $\mathbb{U}$ such that

$$\operatorname{Zero}(\operatorname{sat}(\mathcal{B}))=\bigcup_{i=1}^t\operatorname{Zero}(\operatorname{sat}(\mathcal{R}_i))\,?$$

If yes, give a constructive criterion and an algorithm that takes the resolvent chains (or $\mathcal{A}$ and the $\sigma_i$) and produces such a $\mathcal{B}$, with termination and correctness proofs. If not, exhibit an explicit chain $\mathcal{A}$ whose resolvent family provably admits no single-chain representation.

Scope note: the same source also solicits significantly more efficient algorithms for difference resolvent computation (its implementation is dominated by characteristic-set computation). That solicitation is not part of this problem; only the merging question above is asked.

References

1. Xiao-Shan Gao and Chun-Ming Yuan, Resolvent systems of difference polynomial ideals, Proceedings of the 2006 International Symposium on Symbolic and Algebraic Computation (ISSAC '06), ACM, New York, 2006, pp. 101–108. DOI: 10.1145/1145768.1145790, https://doi.org/10.1145/1145768.1145790 (source paper for the open question)
2. Richard M. Cohn, Difference Algebra, Interscience Tracts in Pure and Applied Mathematics 17, Interscience Publishers, New York–London–Sydney, 1965. zbMATH Zbl 0127.26402, https://zbmath.org/3207354
3. Thomas Cluzeau and Evelyne Hubert, Resolvent Representation for Regular Differential Ideals, Applicable Algebra in Engineering, Communication and Computing, 2003. DOI: 10.1007/s00200-002-0110-4, https://doi.org/10.1007/s00200-002-0110-4
4. Thomas Cluzeau and Evelyne Hubert, Probabilistic algorithms for computing resolvent representations of regular differential ideals, Applicable Algebra in Engineering, Communication and Computing, 2008. DOI: 10.1007/s00200-008-0079-8, https://doi.org/10.1007/s00200-008-0079-8
5. Xiao-Shan Gao, Yong Luo, and Chun-Ming Yuan, A characteristic set method for ordinary difference polynomial systems, Journal of Symbolic Computation 44(3), 2009, pp. 242–260. DOI: 10.1016/j.jsc.2007.05.005, https://doi.org/10.1016/j.jsc.2007.05.005
6. X.S. Gao, J. van der Hoeven, C.M. Yuan, and G.L. Zhang, Characteristic set method for differential–difference polynomial systems, Journal of Symbolic Computation, 2009. DOI: 10.1016/j.jsc.2008.02.010, https://doi.org/10.1016/j.jsc.2008.02.010
7. Chun-Ming Yuan and Xiao-Shan Gao, A criterion for testing whether a difference ideal is prime, Journal of Systems Science and Complexity, 2009. DOI: 10.1007/s11424-009-9192-4, https://doi.org/10.1007/s11424-009-9192-4
8. Alexander Levin, Difference Algebra, Algebra and Applications 8, Springer, Dordrecht, 2008. ISBN 978-1-4020-6947-5, https://link.springer.com/book/10.1007/978-1-4020-6947-5
9. Wei Li and Chun-Ming Yuan, Elimination Theory in Differential and Difference Algebra, Journal of Systems Science and Complexity, 2019. DOI: 10.1007/s11424-019-8367-x, https://doi.org/10.1007/s11424-019-8367-x
10. Wei Li, Chun-Ming Yuan, and Xiao-Shan Gao, Sparse difference resultant, Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation (ISSAC '13), ACM, 2013. DOI: 10.1145/2465506.2465509, https://doi.org/10.1145/2465506.2465509
11. Wei Li and Ying-Hong Li, Difference Chow form, Journal of Algebra, 2015. DOI: 10.1016/j.jalgebra.2014.12.037, https://doi.org/10.1016/j.jalgebra.2014.12.037
12. Xiao-Shan Gao, Zhang Huang, and Chun-Ming Yuan, Binomial difference ideals, Journal of Symbolic Computation, 2017. DOI: 10.1016/j.jsc.2016.07.029, https://doi.org/10.1016/j.jsc.2016.07.029
13. Xiao-Shan Gao, Zhang Huang, Jie Wang, and Chun-Ming Yuan, Toric difference variety, Journal of Systems Science and Complexity, 2017. DOI: 10.1007/s11424-017-6174-9, https://doi.org/10.1007/s11424-017-6174-9
14. Alexey Ovchinnikov, Gleb Pogudin, and Thomas Scanlon, Effective difference elimination and Nullstellensatz, Journal of the European Mathematical Society, 2020. DOI: 10.4171/JEMS/968, https://doi.org/10.4171/JEMS/968
15. Chun-Ming Yuan and Zhi-Yong Zhang, New bounds and an efficient algorithm for sparse difference resultants, Journal of Symbolic Computation, 2021. DOI: 10.1016/j.jsc.2021.04.002, https://doi.org/10.1016/j.jsc.2021.04.002
16. Alexander Levin, On the Ascending Chain Condition for Mixed Difference Ideals, International Mathematics Research Notices, 2014. DOI: 10.1093/imrn/rnu021, https://doi.org/10.1093/imrn/rnu021
17. Mingbo Zhang and Xiao-Shan Gao, Decomposition of ordinary difference polynomials, Journal of Symbolic Computation 44(10), 2009, pp. 1394–1409. DOI: 10.1016/j.jsc.2009.04.001, https://doi.org/10.1016/j.jsc.2009.04.001