Elimination of unknowns for systems of algebraic differential-difference equations. (English) Zbl 1458.12003
Designing methods for solving equations is probably the original problem area of algebra. When we solve systems of linear equations, we triangulate the system, i.e., we generate an equivalent (same solutions) system in which some variables are eliminated from some of the equations. Elimination of variables is also the goal we try to obtain when we apply methods of resultants or Gröbner bases to algebraic equations. Can we pursue such a goal also for algebraic differential-difference equations? The authors of this paper show that we can.
A central fact was proven by Gauss in the Fundamental Theorem of Algebra: every non-constant univariate polynomial with complex coefficients has at least one complex root. Hilbert has extended this to the Nullstellensatz: every ideal \(I\) in an \(n\)-variate polynomial ring over an algebraically closed field \(K\) which does not contain a non-zero constant has a root in \(K^n\). In other words, \(I\) has a common root if and only if \(1 \not\in I\). The Nullstellensatz can even be made “effective” by giving a bound \(B\) such that \(1\) is not in \(I\) if and only if 1 cannot be generated as a sum of multiples from a finite basis of \(I\) by employing multiplies of degree bounded by \(B\).
In this paper the authors show that such effective bounds for deciding the solvability of systems can also be derived for equations in differential-difference rings.
A central fact was proven by Gauss in the Fundamental Theorem of Algebra: every non-constant univariate polynomial with complex coefficients has at least one complex root. Hilbert has extended this to the Nullstellensatz: every ideal \(I\) in an \(n\)-variate polynomial ring over an algebraically closed field \(K\) which does not contain a non-zero constant has a root in \(K^n\). In other words, \(I\) has a common root if and only if \(1 \not\in I\). The Nullstellensatz can even be made “effective” by giving a bound \(B\) such that \(1\) is not in \(I\) if and only if 1 cannot be generated as a sum of multiples from a finite basis of \(I\) by employing multiplies of degree bounded by \(B\).
In this paper the authors show that such effective bounds for deciding the solvability of systems can also be derived for equations in differential-difference rings.
Reviewer: Franz Winkler (Linz)
MSC:
| 12H05 | Differential algebra |
| 12H10 | Difference algebra |
| 03C10 | Quantifier elimination, model completeness, and related topics |
| 14Q20 | Effectivity, complexity and computational aspects of algebraic geometry |
Software:
DifferentialEliminationReferences:
| [1] | Delay differential equations and applications, Proceedings of the NATO Advanced Study Institute held at the Cadi Ayyad University, Marrakech, September 9-21, 2002, NATO Science Series II: Mathematics, Physics and Chemistry 205, xxvi+581 pp. (2006), Springer, Dordrecht · Zbl 1116.34002 · doi:10.1007/1-4020-3647-7 |
| [2] | Boulier, Fran\c{c}ois; Ollivier, Fran\c{c}ois; Lazard, Daniel; Petitot, Michel, Computing representations for radicals of finitely generated differential ideals, Appl. Algebra Engrg. Comm. Comput., 20, 1, 73-121 (2009) · Zbl 1185.12003 · doi:10.1007/s00200-009-0091-7 |
| [3] | BM07 R. F. Bustamante Medina, Differentially closed fields of characteristic zero with a generic automorphism, Revista de Matematica: Teoria y Aplicaciones, 14\penalty 0 (1):\penalty 0 81-100, 2007. URL https://doi.org/10.15517/rmta.v14i1.282. |
| [4] | C15 Z. Chatzidakis, Model theory of fields with operators – a survey, Logic Without Borders: Essays on Set Theory, Model Theory, Philosophical Logic and Philosophy of Mathematics, volume 5 of Ontos Mathematical Logic, De Gruyter, 2015, pages 91-114. https://doi.org/10.1515/9781614516873.91. |
| [5] | Cohn, Richard M., A difference-differential basis theorem, Canadian J. Math., 22, 1224-1237 (1970) · Zbl 0206.05104 · doi:10.4153/CJM-1970-141-3 |
| [6] | Gao, X. S.; Van der Hoeven, J.; Yuan, C. M.; Zhang, G. L., Characteristic set method for differential-difference polynomial systems, J. Symbolic Comput., 44, 9, 1137-1163 (2009) · Zbl 1169.13019 · doi:10.1016/j.jsc.2008.02.010 |
| [7] | Gao, Xiao-Shan; Li, Wei; Yuan, Chun-Ming, Intersection theory in differential algebraic geometry: generic intersections and the differential Chow form, Trans. Amer. Math. Soc., 365, 9, 4575-4632 (2013) · Zbl 1328.14010 · doi:10.1090/S0002-9947-2013-05633-4 |
| [8] | Heintz, Joos, Definability and fast quantifier elimination in algebraically closed fields, Theoret. Comput. Sci., 24, 3, 239-277 (1983) · Zbl 0546.03017 · doi:10.1016/0304-3975(83)90002-6 |
| [9] | Hrushovski, Ehud; Point, Fran\c{c}oise, On von Neumann regular rings with an automorphism, J. Algebra, 315, 1, 76-120 (2007) · Zbl 1127.03033 · doi:10.1016/j.jalgebra.2007.05.006 |
| [10] | Kaplansky, Irving, An introduction to differential algebra, 64 pp. (1976), Actualit\'{e}s Scientifiques et Industrielles, No. 1251, Publications de l’Institut de Math\'{e}matique de l’Universit\'{e} de Nancago, No. V, Hermann, Paris · Zbl 0954.12500 |
| [11] | Koecher, Max; Krieg, Aloys, Elliptische Funktionen und Modulformen, viii+331 pp. (2007), Springer-Verlag, Berlin · Zbl 1129.11001 |
| [12] | Kolchin, E. R., Differential algebra and algebraic groups, xviii+446 pp. (1973), Pure and Applied Mathematics, Vol. 54, Academic Press, New York-London · Zbl 0264.12102 |
| [13] | Kondratieva, M. V.; Levin, A. B.; Mikhalev, A. V.; Pankratiev, E. V., Differential and difference dimension polynomials, Mathematics and its Applications 461, xiv+422 pp. (1999), Kluwer Academic Publishers, Dordrecht · Zbl 0930.12005 · doi:10.1007/978-94-017-1257-6 |
| [14] | Lang, Serge, Elliptic functions, with an appendix by J. Tate, Graduate Texts in Mathematics 112, xii+326 pp. (1987), Springer-Verlag, New York · Zbl 0615.14018 · doi:10.1007/978-1-4612-4752-4 |
| [15] | Le\'{o}n S\'{a}nchez, Omar, Estimates for the coefficients of differential dimension polynomials, Math. Comp., 88, 320, 2959-2985 (2019) · Zbl 1412.12004 · doi:10.1090/mcom/3429 |
| [16] | Levin, Alexander, Reduced Gr\"{o}bner bases, free difference-differential modules and difference-differential dimension polynomials, J. Symbolic Comput., 30, 4, 357-382 (2000) · Zbl 0994.13009 · doi:10.1006/jsco.1999.0412 |
| [17] | Levin, Alexander, Difference algebra, Algebra and Applications 8, xii+519 pp. (2008), Springer, New York · Zbl 1209.12003 · doi:10.1007/978-1-4020-6947-5 |
| [18] | Mansfield, E. L.; Szanto, A., Elimination theory for differential difference polynomials. Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation, 191-198 (2003), ACM, New York · Zbl 1072.68684 · doi:10.1145/860854.860897 |
| [19] | Marker, D.; Messmer, M.; Pillay, A., Model theory of fields, Lecture Notes in Logic 5, x+154 pp. (1996), Springer-Verlag, Berlin · Zbl 0911.12005 · doi:10.1007/978-3-662-22174-7 |
| [20] | Maury, Bertrand; Faure, Sylvain, Crowds in equations, Advanced Textbooks in Mathematics, ix+190 pp. (2019), World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ · Zbl 1395.91001 |
| [21] | Moosa, Rahim; Scanlon, Thomas, Model theory of fields with free operators in characteristic zero, J. Math. Log., 14, 2, 1450009, 43 pp. (2014) · Zbl 1338.03067 · doi:10.1142/S0219061314500093 |
| [22] | OPV2018 A. Ovchinnikov, G. Pogudin, and N. Thieu Vo, Bounds for elimination of unknowns in systems of differential-algebraic equations, accepted for publication in Int. Math. Res. Not. (IMRN), 2020. DOI 10.1093/imrn/rnaa302. URL https://arxiv.org/abs/1610.04022. |
| [23] | Ovchinnikov, Alexey; Pogudin, Gleb; Scanlon, Thomas, Effective difference elimination and Nullstellensatz, J. Eur. Math. Soc. (JEMS), 22, 8, 2419-2452 (2020) · Zbl 1475.12012 · doi:10.4171/JEMS/968 |
| [24] | Pogudin, Gleb; Scanlon, Thomas; Wibmer, Michael, Solving difference equations in sequences: universality and undecidability, Forum Math. Sigma, 8, e33 pp. (2020) · Zbl 1462.13029 · doi:10.1017/fms.2020.14 |
| [25] | apps-bio-DDE F. A. Rihan, C. Tunc, S. H. Saker, S. Lakshmanan, and R. Rakkiyappan, Applications of delay differential equations in biological systems, Complexity, (2018), 1-3. https://doi.org/10.1155/2018/4584389. · Zbl 1405.00027 |
| [26] | Ritt, Joseph Fels, Differential Algebra, American Mathematical Society Colloquium Publications, Vol. XXXIII, viii+184 pp. (1950), American Mathematical Society, New York, N. Y. · Zbl 0037.18402 |
| [27] | Rosenfeld, Azriel, Specializations in differential algebra, Trans. Amer. Math. Soc., 90, 394-407 (1959) · Zbl 0192.14001 · doi:10.2307/1993179 |
| [28] | Schost, \'{E}ric, Complexity results for triangular sets, International Symposium on Symbolic and Algebraic Computation (ISSAC’2002) (Lille), J. Symbolic Comput., 36, 3-4, 555-594 (2003) · Zbl 1074.68082 · doi:10.1016/S0747-7171(03)00095-6 |
| [29] | Zhou, Meng; Winkler, Franz, Computing difference-differential dimension polynomials by relative Gr\"{o}bner bases in difference-differential modules, J. Symbolic Comput., 43, 10, 726-745 (2008) · Zbl 1149.13014 · doi:10.1016/j.jsc.2008.02.001 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
