Complexity bounds for the Ritt–Wu characteristic-set zero-decomposition of ordinary difference polynomial systems

The Ritt–Wu characteristic set method of Gao, Yuan and Zhang (2009) decomposes the zero set of a finite system of ordinary difference polynomials over an inversive difference field, under any admissible ordering, into coherent proper-irreducible difference chains (algorithm RittWuZDT with the proper-irreducibility test ProIrr), or alternatively into algebraic irreducible components via a modified Cohn procedure with its Consistent test. Correctness and termination are proved, but the method carries no quantitative theory. The problem is to give this decomposition a quantitative foundation: establish worst-case complexity bounds in the input parameters (number of variables, orders, degrees, number of polynomials) for the output size and computational cost of the full RittWuZDT and Cohn/Consistent pipeline including ProIrr.

Background

A difference field is a field $\mathcal{K}$ equipped with a distinguished endomorphism $\sigma$ (a shift operator, sending each element to its transform); the field is called inversive when $\sigma$ is an automorphism. The ordinary difference polynomial ring $\mathcal{K}\{x_1,\dots,x_n\}$ is the polynomial ring in the infinitely many transformed variables $\sigma^i x_j$ ($i\ge 0$), on which $\sigma$ acts by shifting indices. A difference ideal is an ideal stable under $\sigma$; it is reflexive if $\sigma f$ belonging to it forces $f$ to belong to it, and reflexive prime ideals are the difference analog of prime ideals and describe irreducible solution sets. Ritt–Wu's characteristic set method, developed by Ritt and Wu Wen-tsün for algebraic and differential polynomial systems and given complexity bounds in the algebraic case by Gallo and Mishra, triangularizes a polynomial system: it computes an ascending chain (a triangular set in which each polynomial introduces a new leading variable with lower order in earlier ones) and splits the zero set until each component is represented by a well-behaved chain. For a difference chain $\mathcal{A}$, the saturation ideal $\operatorname{sat}(\mathcal{A})$ is the ideal of all difference polynomials whose pseudo-remainder vanishes on $\mathcal{A}$; it is the object whose zero set the decomposition tracks. A chain is coherent if the algebraic pseudo-remainders of all pairs of its polynomials (the analog of $S$-polynomials) vanish; it is proper irreducible if the finite transform completion $\mathcal{A}^{*}$ is an algebraic irreducible triangular set whose algebraic saturation $\mathbf{a}\text{-}\operatorname{sat}(\mathcal{A}^{*})$ is closed under $\sigma$ and $\sigma^{-1}$; it is strong irreducible if every transform slice $\mathcal{A}_{(h_1,\dots,h_n)}$ is an algebraic irreducible triangular set. Gao, Luo and Yuan (2009) built the first characteristic set method for ordinary difference polynomial systems under a fixed variable ordering, and Gao, Yuan and Zhang (2009) extended it to arbitrary admissible orderings with the definition of proper irreducible chain just described. In that paper, Theorem 3.8 proves that every coherent proper-irreducible chain is consistent (its saturation ideal has a zero, constructed via Cohn's theory of difference kernels, which are finite algebraic extensions mimicking one step of the shift); Theorems 3.10 and 3.12 establish the equivalence between the chain side and the ideal side: a chain is coherent and strong irreducible with $I=\operatorname{sat}(\mathcal{A})$ exactly when it is a characteristic set of a reflexive prime difference ideal. Algorithmically, Algorithm 2 (RittWuZDT) recursively splits a finite difference polynomial system into coherent proper-irreducible chains; Algorithm 3 (ProIrr) tests proper irreducibility by computing a Gröbner basis (a canonical generating set of a polynomial ideal, used here w.r.t. an eliminating variable ordering) of the algebraic saturation $\mathbf{a}\text{-}\operatorname{sat}(\mathcal{A}^{*})$ and checking closure under $\sigma^{-1}$; Algorithms 4 and 5 (Cohn and Consistent) give a second decomposition route that, unlike Cohn's original order-reduction to order one, preserves the ideal structure, testing extendability of algebraic components through two Gröbner bases on adjacent variable slices. All termination arguments are qualitative (descending chain conditions on ranks). What the paper does not contain is any complexity or termination-cost analysis in terms of the input degrees, orders and number of variables, or any study of the cost or scalability of the Gröbner-basis subroutines on which ProIrr and Consistent rest.

Problem Statement

For the Ritt–Wu characteristic-set zero-decomposition of ordinary difference polynomial systems over an inversive difference field under an arbitrary admissible ordering, as defined by Gao–Yuan–Zhang (2009) — the recursive splitting algorithm RittWuZDT producing coherent proper-irreducible chains with $\operatorname{Zero}(\mathbb{P})=\bigcup_i\operatorname{Zero}(\operatorname{sat}(\mathcal{A}_i))$, the proper-irreducibility test ProIrr based on a Gröbner basis of $\mathbf{a}\text{-}\operatorname{sat}(\mathcal{A}^{*})$, and the modified Cohn decomposition with its Consistent test based on Gröbner bases on adjacent variable slices — establish the missing quantitative foundation: prove worst-case upper bounds, as explicit functions of the number of variables, the number of input polynomials, their maximal degree and maximal order (that is, bounds given by a stated expression in these parameters, and not the trivial bound defined as the maximum over all systems with the same parameters), for the size of the output and for the computational cost of the full RittWuZDT and Cohn/Consistent procedures including the ProIrr subroutine; both routes and both quantities — output size and computational cost — are required, the output-size bound being stated for each route on that route's own output: the number of components and the degrees and orders of the output chains for RittWuZDT, and the number of algebraic irreducible components and their degrees for the modified Cohn/Consistent route.

References

1. Xiao-Shan 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
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. 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
4. 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
5. Mingbo Zhang, Xiao-Shan Gao, Decomposition of ordinary difference polynomials, Journal of Symbolic Computation 44(10):1394–1409, 2009. DOI: 10.1016/j.jsc.2009.04.001, https://doi.org/10.1016/j.jsc.2009.04.001
6. Richard M. Cohn, Difference Algebra, Interscience Tracts in Pure and Applied Mathematics 17, Interscience Publishers, New York, 1965. zbMATH Zbl 0127.26402, https://zbmath.org/?q=an%3A0127.26402
7. G. Gallo, B. Mishra, Efficient Algorithms and Bounds for Wu-Ritt Characteristic Sets, in: Effective Methods in Algebraic Geometry (Progress in Mathematics 94), Birkhäuser, 1991, pp. 119–142. DOI: 10.1007/978-1-4612-0441-1_8, https://doi.org/10.1007/978-1-4612-0441-1_8
8. Wei Li, Chun-Ming Yuan, Elimination Theory in Differential and Difference Algebra, Journal of Systems Science and Complexity 32:287–316, 2019. DOI: 10.1007/s11424-019-8367-x, https://doi.org/10.1007/s11424-019-8367-x
9. Xiao-Shan Gao, Zhang Huang, Chunming Yuan, Binomial difference ideals, Journal of Symbolic Computation 80:665–706, 2017. DOI: 10.1016/j.jsc.2016.07.029, https://doi.org/10.1016/j.jsc.2016.07.029
10. Wei Li, Ying-Hong Li, Difference Chow form, Journal of Algebra 428:67–90, 2015. DOI: 10.1016/j.jalgebra.2014.12.037, https://doi.org/10.1016/j.jalgebra.2014.12.037 (arXiv:1308.2469)
11. Wei Li, Chun-Ming Yuan, Xiao-Shan Gao, Sparse difference resultant, Journal of Symbolic Computation 68:169–203, 2015. DOI: 10.1016/j.jsc.2014.09.016, https://doi.org/10.1016/j.jsc.2014.09.016
12. Chun-Ming Yuan, Zhi-Yong Zhang, New bounds and an efficient algorithm for sparse difference resultants, Journal of Symbolic Computation 107:279–298, 2021. DOI: 10.1016/j.jsc.2021.04.002, https://doi.org/10.1016/j.jsc.2021.04.002
13. 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 (arXiv:1712.01412)
14. Gleb Pogudin, Thomas Scanlon, Michael Wibmer, Solving difference equations in sequences: universality and undecidability, Forum of Mathematics, Sigma 8:e33, 2020. DOI: 10.1017/fms.2020.14, https://doi.org/10.1017/fms.2020.14 (arXiv:1909.03239)
15. Wei Li, Alexey Ovchinnikov, Gleb Pogudin, Thomas Scanlon, Algorithms yield upper bounds in differential algebra, Canadian Journal of Mathematics 75(1):29–51, 2023. DOI: 10.4153/S0008414X21000560, https://doi.org/10.4153/S0008414X21000560 (arXiv:2005.01608)