AMS eBook CollectionsOne of the world's most respected mathematical collections, available in digital format for your library or institution
An Elementary Recursive Bound for Effective Positivstellensatz and Hilbert’s 17th problem
About this Title
Henri Lombardi, Laboratoire of Mathématiques (UMR CNRS 6623) UFR des Sciences et Techniques, Université of Franche-Comté 25030 Besançon cedex France, Daniel Perrucci, Departamento de Matemática, FCEN, Universidad de Buenos Aires and IMAS CONICET-UBA, Argentina and Marie-Françoise Roy, IRMAR (UMR CNRS 6625), Université de Rennes 1, Campus de Beaulieu 35042 Rennes cedex France
Publication: Memoirs of the American Mathematical Society
Publication Year:
2020; Volume 263, Number 1277
ISBNs: 978-1-4704-4108-1 (print); 978-1-4704-5662-7 (online)
DOI: https://doi.org/10.1090/memo/1277
Published electronically: March 2, 2020
Keywords: Hilbert’s 17th problem,
Positivstellensatz,
Real Nullstellensatz,
degree bounds,
elementary recursive functions
MSC: Primary 12D15, 14P99, 13J30
Table of Contents
Chapters
- 1. Introduction
- 2. Weak inference and weak existence
- 3. Intermediate value theorem
- 4. Fundamental theorem of algebra
- 5. Hermite’s Theory
- 6. Elimination of one variable
- 7. Proof of the main theorems
- 8. Annex
Abstract
We prove an elementary recursive bound on the degrees for Hilbert’s 17th problem. More precisely we express a nonnegative polynomial as a sum of squares of rational functions, and we obtain as degree estimates for the numerators and denominators the following tower of five exponentials \begin{equation*} 2^{ 2^{ 2^{d^{4^{k}}} } } \end{equation*} where $d$ is the degree and $k$ is the number of variables of the input polynomial. Our method is based on the proof of an elementary recursive bound on the degrees for Stengle’s Positivstellensatz. More precisely we give an algebraic certificate of the emptyness of the realization of a system of sign conditions and we obtain as degree bounds for this certificate a tower of five exponentials, namely \begin{equation*} 2^{ 2^{\left (2^{\max \{2,d\}^{4^{k}}}+ s^{2^{k}}\max \{2, d\}^{16^{k}\mathrm {bit}(d)} \right )} } \end{equation*} where $d$ is a bound on the degrees, $s$ is the number of polynomials and $k$ is the number of variables of the input polynomials.- Emil Artin, Über die Zerlegung definiter Funktionen in Quadrate, Abh. Math. Sem. Univ. Hamburg 5 (1927), no. 1, 100–115 (German). MR 3069468, DOI 10.1007/BF02952513
- Saugata Basu, Richard Pollack, and Marie-Françoise Roy, On the combinatorial and algebraic complexity of quantifier elimination, J. ACM 43 (1996), no. 6, 1002–1045. MR 1434910, DOI 10.1145/235809.235813
- Saugata Basu, Richard Pollack, and Marie-Françoise Roy, Algorithms in real algebraic geometry, 2nd ed., Algorithms and Computation in Mathematics, vol. 10, Springer-Verlag, Berlin, 2006. MR 2248869
- Saugata Basu, Richard Pollack, and Marie-Françoise Roy, Algorithms in real algebraic geometry, 2nd ed., Algorithms and Computation in Mathematics, vol. 10, Springer-Verlag, Berlin, 2006. MR 2248869
- Grigoriy Blekherman, João Gouveia, and James Pfeiffer, Sums of squares on the hypercube, Math. Z. 284 (2016), no. 1-2, 41–54. MR 3545483, DOI 10.1007/s00209-016-1644-7
- J. Bochnak, M. Coste, and M.-F. Roy, Géométrie algébrique réelle, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 12, Springer-Verlag, Berlin, 1987 (French). MR 949442
- W. Dale Brownawell, Local Diophantine Nullstellen inequalities, J. Amer. Math. Soc. 1 (1988), no. 2, 311–322. MR 928261, DOI 10.1090/S0894-0347-1988-0928261-3
- Léandro Caniglia, André Galligo, and Joos Heintz, Borne simple exponentielle pour les degrés dans le théorème des zéros sur un corps de caractéristique quelconque, C. R. Acad. Sci. Paris Sér. I Math. 307 (1988), no. 6, 255–258 (French, with English summary). MR 956817
- Paul J. Cohen, Decision procedures for real and $p$-adic fields, Comm. Pure Appl. Math. 22 (1969), 131–151. MR 244025, DOI 10.1002/cpa.3160220202
- George E. Collins, Quantifier elimination for real closed fields by cylindrical algebraic decomposition, Automata theory and formal languages (Second GI Conf., Kaiserslautern, 1975), Springer, Berlin, 1975, pp. 134–183. Lecture Notes in Comput. Sci., Vol. 33. MR 0403962
- Michel Coste, Henri Lombardi, and Marie-Françoise Roy, Dynamical method in algebra: effective Nullstellensätze, Ann. Pure Appl. Logic 111 (2001), no. 3, 203–256. MR 1848137, DOI 10.1016/S0168-0072(01)00026-4
- M. Coste and M.-F. Roy, Thom’s lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets, J. Symbolic Comput. 5 (1988), no. 1-2, 121–129. MR 949115, DOI 10.1016/S0747-7171(88)80008-7
- David Cox, John Little, and Donal O’Shea, Ideals, varieties, and algorithms, 3rd ed., Undergraduate Texts in Mathematics, Springer, New York, 2007. An introduction to computational algebraic geometry and commutative algebra. MR 2290010
- D. E. Daykin. Hilbert’s 17th problem. Ph.D. Thesis, Univ. of Reading, (1961) unpublished.
- James H. Davenport and Joos Heintz, Real quantifier elimination is doubly exponential, J. Symbolic Comput. 5 (1988), no. 1-2, 29–35. MR 949111, DOI 10.1016/S0747-7171(88)80004-X
- Charles N. Delzell, Kreisel’s unwinding of Artin’s proof, Kreiseliana, A K Peters, Wellesley, MA, 1996, pp. 113–246. MR 1435764
- Gema M. Diaz-Toca, Laureano Gonzalez-Vega, and Henri Lombardi, Generalizing Cramer’s rule: solving uniformly linear systems of equations, SIAM J. Matrix Anal. Appl. 27 (2005), no. 3, 621–637. MR 2208324, DOI 10.1137/S0895479802418860
- D. W. Dubois, A nullstellensatz for ordered fields, Ark. Mat. 8 (1969), 111–114. MR 272761, DOI 10.1007/BF02589551
- G. Efroymson, Local reality on algebraic varieties, J. Algebra 29 (1974), 133–142. MR 364240, DOI 10.1016/0021-8693(74)90118-5
- F. R. Gantmacher, The theory of matrices. Vols. 1, 2, Chelsea Publishing Co., New York, 1959. Translated by K. A. Hirsch. MR 0107649
- L. González-Vega, H. Lombardi, T. Recio, and M.-F. Roy, Spécialisation de la suite de Sturm et sous-résultants, RAIRO Inform. Théor. Appl. 24 (1990), no. 6, 561–588 (French, with English summary). MR 1082916, DOI 10.1051/ita/1990240605611
- D. Yu. Grigor′ev, Complexity of deciding Tarski algebra, J. Symbolic Comput. 5 (1988), no. 1-2, 65–108. MR 949113, DOI 10.1016/S0747-7171(88)80006-3
- D. Yu. Grigor′ev and N. N. Vorobjov Jr., Solving systems of polynomial inequalities in subexponential time, J. Symbolic Comput. 5 (1988), no. 1-2, 37–64. MR 949112, DOI 10.1016/S0747-7171(88)80005-1
- Dima Grigoriev and Nicolai Vorobjov, Complexity of Null- and Positivstellensatz proofs, Ann. Pure Appl. Logic 113 (2002), no. 1-3, 153–160. First St. Petersburg Conference on Days of Logic and Computability (1999). MR 1875740, DOI 10.1016/S0168-0072(01)00055-0
- Grete Hermann, Die Frage der endlich vielen Schritte in der Theorie der Polynomideale, Math. Ann. 95 (1926), no. 1, 736–788 (German). MR 1512302, DOI 10.1007/BF01206635
- C. Hermite. Remarques sur le théorème de sturm. C. R. Acad. Sci. Paris, 36, 52–54, (1853).
- David Hilbert, Sur les problèmes futurs des mathématiques, Les Grands Classiques Gauthier-Villars. [Gauthier-Villars Great Classics], Éditions Jacques Gabay, Sceaux, 1990 (French). Les 23 problèmes. [The 23 problems]; Translated from the 1900 German original by M. L. Laugel and revised by the author; Reprint of the 1902 French translation. MR 1188875
- Hilbert D. Mathematische Probleme. Göttinger Nachrichten, (1900), 253–297, and in Archiv der Mathematik und Physik, (3) 1 (1901), 44–63 and 213–237.
- David Hilbert, Mathematical problems, Bull. Amer. Math. Soc. 8 (1902), no. 10, 437–479. MR 1557926, DOI 10.1090/S0002-9904-1902-00923-3
- Lars Hörmander, Linear partial differential operators, Die Grundlehren der mathematischen Wissenschaften, Bd. 116, Academic Press, Inc., Publishers, New York; Springer-Verlag, Berlin-Göttingen-Heidelberg, 1963. MR 0161012
- Zbigniew Jelonek, On the effective Nullstellensatz, Invent. Math. 162 (2005), no. 1, 1–17. MR 2198324, DOI 10.1007/s00222-004-0434-8
- János Kollár, Effective Nullstellensatz for arbitrary ideals, J. Eur. Math. Soc. (JEMS) 1 (1999), no. 3, 313–337. MR 1714736, DOI 10.1007/s100970050009
- G. Kreisel. Hilbert’s 17-th problem. in Summaries of talks presented at the Summer Inst. of Symbolic Logic at Cornell Univ (1957)
- G. Kreisel. Sums of squares. Summaries of Talks Presented at the Summer Institute in Symbolic Logic in 1957 at Cornell Univ., Princeton, Institute for Defense Analysis, (1960) 313–320.
- J.-L. Krivine, Anneaux préordonnés, J. Analyse Math. 12 (1964), 307–326 (French). MR 175937, DOI 10.1007/BF02807438
- Peter Lancaster and Miron Tismenetsky, The theory of matrices, 2nd ed., Computer Science and Applied Mathematics, Academic Press, Inc., Orlando, FL, 1985. MR 792300
- Vo-Khac Khoan, Introduction aux méthodes mathématiques modernes de la physique. Espaces préhilbertiens; série de Fourier; spectre des opérateurs. Distributions, convolutions et transformation de Fourier; espaces de Sobolev. Equations différentielles; transformation de Laplace; fonctions orthogonales. Equations aux dérivées partielles; méthode de Galerkine-Fourier, Centre de Documentation Universitaire, Paris, 1968 (French). Faculté des Sciences d’Orléans, Cours de Mathématiques C2 de la Maîtrise de Physique. MR 0366135
- S. Lojasiewicz. Ensembles semi-analytiques. Institut des Hautes Etudes Scientifiques, 1965 - 153 pages.
- Henri Lombardi, Théorème des zéros réel effectif et variantes, Théorie des nombres, Année 1988/89, Fasc. 1, Publ. Math. Fac. Sci. Besançon, Univ. Franche-Comté, Besançon, 1989, pp. 31 (French, with English summary). MR 1052946
- Henri Lombardi, Effective real Nullstellensatz and variants, Effective methods in algebraic geometry (Castiglioncello, 1990) Progr. Math., vol. 94, Birkhäuser Boston, Boston, MA, 1991, pp. 263–288. MR 1106428
- Henri Lombardi, Nullstellensatz réel effectif et variantes, C. R. Acad. Sci. Paris Sér. I Math. 310 (1990), no. 8, 635–640 (French, with English summary). MR 1065427
- Henri Lombardi, Théorème des zéros réel et variantes, avec une majoration explicite des degrés, Mémoire d’habilitation (1990).
- Henri Lombardi, Une borne sur les degrés pour le théorème des zéros réel effectif, Real algebraic geometry (Rennes, 1991) Lecture Notes in Math., vol. 1524, Springer, Berlin, 1992, pp. 323–345 (French, with English and French summaries). MR 1226264, DOI 10.1007/BFb0084631
- Leonard Gaines Monk, ELEMENTARY-RECURSIVE DECISION PROCEDURES, ProQuest LLC, Ann Arbor, MI, 1975. Thesis (Ph.D.)–University of California, Berkeley. MR 2625932
- Daniel Perrucci and Marie-Françoise Roy, Zero-nonzero and real-nonreal sign determination, Linear Algebra Appl. 439 (2013), no. 10, 3016–3030. MR 3116410, DOI 10.1016/j.laa.2013.09.010
- Daniel Perrucci and Marie-Françoise Roy, Elementary recursive quantifier elimination based on Thom encoding and sign determination, Ann. Pure Appl. Logic 168 (2017), no. 8, 1588–1604. MR 3650356, DOI 10.1016/j.apal.2017.03.001
- James Renegar, On the computational complexity and geometry of the first-order theory of the reals. I. Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals, J. Symbolic Comput. 13 (1992), no. 3, 255–299. MR 1156882, DOI 10.1016/S0747-7171(10)80003-3
- Jean-Jacques Risler, Une caractérisation des idéaux des variétés algébriques réelles, C. R. Acad. Sci. Paris Sér. A-B 271 (1970), A1171–A1173 (French). MR 274437
- H. E. Rose, Subrecursion: functions and hierarchies, Oxford Logic Guides, vol. 9, The Clarendon Press, Oxford University Press, New York, 1984. MR 752696
- J. Schmid. On the degree complexity of Hilbert’s 17th problem and the Real Nullstellensatz, Habilitation, University of Dortmund, n ř 70, Seminar of logic, Paris 7, (2000).
- A. Seidenberg, A new decision method for elementary algebra, Ann. of Math. (2) 60 (1954), 365–374. MR 63994, DOI 10.2307/1969640
- Gilbert Stengle, A nullstellensatz and a positivstellensatz in semialgebraic geometry, Math. Ann. 207 (1974), 87–97. MR 332747, DOI 10.1007/BF01362149
- Alfred Tarski, A decision method for elementary algebra and geometry, University of California Press, Berkeley and Los Angeles, Calif., 1951. 2nd ed. MR 0044472
- B. L. van der Waerden, Modern Algebra. Vol. I, Frederick Ungar Publishing Co., New York, N. Y., 1949. Translated from the second revised German edition by Fred Blum; With revisions and additions by the author. MR 0029363
- H. Warou, An algorithm and bounds for the real effective Nullstellensatz in one variable, Algorithms in algebraic geometry and applications (Santander, 1994) Progr. Math., vol. 143, Birkhäuser, Basel, 1996, pp. 373–387. MR 1414460