Gröbner bases and gradings for partial difference ideals. (English) Zbl 1328.12014

Summary: In this paper we introduce a working generalization of the theory of Gröbner bases for algebras of partial difference polynomials with constant coefficients. One obtains symbolic (formal) computation for systems of linear or non-linear partial difference equations arising, for instance, as discrete models or by the discretization of systems of differential equations. From an algebraic viewpoint, the algebras of partial difference polynomials are free objects in the category of commutative algebras endowed with the action by endomorphisms of a monoid isomorphic to \( \mathbb{N}^r\). Then, the investigation of Gröbner bases in this context contributes also to the current research trend consisting in studying polynomial rings under the action of suitable symmetries that are compatible with effective methods. Since the algebras of difference polynomials are not Noetherian, we propose in this paper a theory for grading them that provides a Noetherian subalgebra filtration. This implies that the variants of Buchberger’s algorithm we developed for difference ideals terminate in the finitely generated graded case when truncated up to some degree. Moreover, even in the non-graded case, we provide criterions for certifying completeness of eventually finite Gröbner bases when they are computed within sufficiently large bounded degrees. We generalize also the concepts of homogenization and saturation, and related algorithms, to the context of difference ideals. The feasibility of the proposed methods is shown by an implementation in Maple that is the first to provide computations for systems of nonlinear partial difference equations. We make use of a test set based on the discretization of concrete systems of non-linear partial differential equations.


12H10 Difference algebra
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
Full Text: DOI arXiv


[1] Aschenbrenner, Matthias; Hillar, Christopher J., Finite generation of symmetric ideals, Trans. Amer. Math. Soc., 359, 11, 5171-5192 (2007) · Zbl 1129.13008
[2] Bergman, George M., The diamond lemma for ring theory, Adv. in Math., 29, 2, 178-218 (1978) · Zbl 0326.16019
[3] Bigatti, A. M.; Caboara, M.; Robbiano, L., Computing inhomogeneous Gr\"obner bases, J. Symbolic Comput., 46, 5, 498-510 (2011) · Zbl 1252.13018
[4] Brouwer, Andries E.; Draisma, Jan, Equivariant Gr\"obner bases and the Gaussian two-factor model, Math. Comp., 80, 274, 1123-1133 (2011) · Zbl 1211.13018
[5] Buchberger, B., Ein algorithmisches Kriterium f\`“ur die L\'”osbarkeit eines algebraischen Gleichungssystems, Aequationes Math., 4, 374-383 (1970) · Zbl 0212.06401
[6] Cohn, Richard M., Difference Algebra, xiv+355 pp. (1965), Interscience Publishers John Wiley & Sons, New York-London-Sydeny
[7] [DGPS] W. Decker, G.-M. Greuel, G. Pfister, and H. Sch\"onemann, \newblockSingular 3-1-5 — A computer algebra system for polynomial computations (2012). \newblockhttp://www.singular.uni-kl.de
[8] Eisenbud, David, Commutative Algebra, Graduate Texts in Mathematics 150, xvi+785 pp. (1995), Springer-Verlag: New York:Springer-Verlag · Zbl 0819.13001
[9] [Ge] V. P. Gerdt, Consistency analysis of finite difference approximations to PDE systems. In: Adam G. et al. (Eds.), Proc. of Mathematical Modeling and Computational Physics. MMCP 2011, 28-42, Lecture Notes in Comput. Sci., 7175, Springer, Heidelberg, 2012.
[10] [GB] V. P. Gerdt and Y. A. Blinkov, Involution and difference schemes for the Navier-Stokes equations. In: Gerdt V.P. et al. (Eds.), Proc. of Computer Algebra in Scientific Computing. CASC 2009, 94-105, Lecture Notes in Comput. Sci., 5743, Springer, Berlin, 2009. · Zbl 1260.76008
[11] Gerdt, Vladimir P.; Blinkov, Yuri A.; Mozzhilkin, Vladimir V., Gr\"obner bases and generation of difference schemes for partial differential equations, SIGMA Symmetry Integrability Geom. Methods Appl., 2, Paper 051, 26 pp. (2006) · Zbl 1094.68125
[12] [GR] V. P. Gerdt and D. Robertz, A Maple package for computing Gr\"obner bases for linear recurrence relations. Nucl. Instrum. Methods, 599 (2006), 215-219. \newblockhttp://wwwb.math.rwth-aachen.de/Janet
[13] Gondran, Michel; Minoux, Michel, Graphs, Dioids and Semirings, \em New Models and Algorithms. Operations Research/Computer Science Interfaces Series 41, xx+383 pp. (2008), Springer: New York:Springer · Zbl 1201.16038
[14] Grove, E. A.; Ladas, G., Periodicities in Nonlinear Difference Equations, Advances in Discrete Mathematics and Applications 4, xiv+379 pp. (2005), Chapman & Hall/CRC, Boca Raton, FL · Zbl 1078.39009
[15] Higman, Graham, Ordering by divisibility in abstract algebras, Proc. London Math. Soc. (3), 2, 326-336 (1952) · Zbl 0047.03402
[16] Hillar, Christopher J.; Mart{\'{\i }}n del Campo, Abraham, Finiteness theorems and algorithms for permutation invariant chains of Laurent lattice ideals, J. Symbolic Comput., 50, 314-334 (2013) · Zbl 1263.13031
[17] Kolchin, E. R., Differential Algebra and Algebraic Groups, xviii+446 pp. (1973), Academic Press: New York:Academic Press
[18] [LS] R. La Scala, Extended letterplace correspondence for nongraded noncommutative ideals and related algorithms, preprint (2012), 1-20. arXiv:1206.6027 · Zbl 1329.16039
[19] La Scala, Roberto; Levandovskyy, Viktor, Letterplace ideals and non-commutative Gr\"obner bases, J. Symbolic Comput., 44, 10, 1374-1393 (2009) · Zbl 1186.16014
[20] La Scala, Roberto; Levandovskyy, Viktor, Skew polynomial rings, Gr\"obner bases and the letterplace embedding of the free associative algebra, J. Symbolic Comput., 48, 110-131 (2013) · Zbl 1272.16026
[21] [LM] V. Levandovskyy and B. Martin, A symbolic approach to generation and analysis of finite difference schemes of partial differential equations. In: Langer U. et al. (Eds.), Numerical and Symbolic Scientific Computing: Progress and Prospects. Springer (2012), 123-156. · Zbl 1250.65109
[22] Levi, Decio, Lie symmetries for lattice equations, Note Mat., 23, 2, 139-156 (2004/05) · Zbl 1195.37048
[23] Levin, Alexander, Difference Algebra, Algebra and Applications 8, xii+519 pp. (2008), Springer: New York:Springer · Zbl 1209.12003
[24] Meyer, David A.; Wallach, Noland, Invariants for multiple qubits: the case of 3 qubits. Mathematics of quantum computation, Comput. Math. Ser., 77-97 (2002), Chapman & Hall/CRC, Boca Raton, FL · Zbl 1001.81005
[25] [Ri1] J. F. Ritt, Differential Equations From the Algebraic Standpoint. Amer. Math. Soc. Colloquium Publ., Vol. 14, AMS, New York, 1932.
[26] Ritt, Joseph Fels, Differential Algebra, American Mathematical Society Colloquium Publications, Vol. XXXIII, viii+184 pp. (1950), American Mathematical Society: New York, N. Y.:American Mathematical Society · Zbl 0037.18402
[27] Seiler, Werner M., Involution, \em The formal theory of differential equations and its applications in computer algebra. Algorithms and Computation in Mathematics 24, xxii+650 pp. (2010), Springer-Verlag: Berlin:Springer-Verlag · Zbl 1205.35003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.