×

An elementary recursive bound for effective Positivstellensatz and Hilbert’s 17th problem. (English) Zbl 1465.14001

Memoirs of the American Mathematical Society 1277. Providence, RI: American Mathematical Society (AMS) (ISBN 978-1-470-44108-1/pbk; 978-1-4704-5662-7/ebook). v, 125 p. (2020).
As a succinct first summary essentially the authors own words may be the best ones: “An elementary recursive bound on the degrees for Hilbert’s 17th problem is given. 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 \(\exp_2(\exp_2(\exp_2(\exp_d(\exp_4(k))))),\) where \(d\) is the degree and \(k\) is the number of variables of the input polynomial and \(\exp_l(x)=l^x.\) 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 emptiness of the realization of a system of sign conditions and we obtain as degree bounds for this certificate a tower of five exponentials, namely \( \exp_2(\exp_2(\exp_2(\max\{2,d\}^{4^k}+ s^{2^k}\max\{2,d\}^{16^k \text{bit}(d)})))\) 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 and bit(d) is the length of the binary representation of \(d.\)”
The reviewer continues giving some rough ideas of the concepts involved. Let \(K\) be an ordered field and let \(K[x]=K[x_1,\dots , x_k].\) A system of signconditions in \(K[x]\) is a list \(\mathcal{F}=\{\mathcal{F}_{\neq},\mathcal{F}_{\geq}, \mathcal{F}_{=} \}\) of three sets of polynomials (as indicated) in \(K[x]\) by which one defines, given an ordered field \(L\supseteq K,\) the set \(\text{Real}(\mathcal F, L)=\{\xi\in L^k: \text{ for all } P \in \mathcal F_{\neq}, P(\xi)\neq 0, \text{ for all } P \in \mathcal F_{\geq}, P(\xi)\geq 0, \text{ for all } P \in \mathcal F_{=}, P(\xi)= 0 \}.\) Then \(\text{Real}(\mathcal F, L)\) is said to be the realization of \(\mathcal{F}\) in \(L.\) If \(\text{Real}(\mathcal F, L)=\emptyset\) then the system \(\mathcal{F}\) is called unrealizable in \(L.\)
Now consider a finite set \(\mathcal{P}\subset K[x]\) and \( \mathcal{P}^2=\{p^2: p\in \mathcal P\}.\) Define \(\mathcal{M(P)}:=\)multiplicative monoid generated by \(\mathcal{P};\) \(\mathcal{N(P)}:=\{\text{ polynomials of form } \sum_{i=1}^m \omega_iV_i^2\cdot N_i, \text{ with } \omega_i\in K_{+}, V_i\in K[x], N_i\in \mathcal{M(P)} \}\); and \(\mathcal{I(P)}:=\)ideal generated by \(\mathcal{P} \in K[x].\) A system of sign conditions \(\mathcal{F}\) is is said incompatible, notation \(\downarrow \mathcal{F}\downarrow,\) if there is an algebraic identity \(S+N+Z=0\) with \(S\in \mathcal{M}(\mathcal F_{\neq}^2), N\in \mathcal{N}(\mathcal F_{\geq}), Z\in \mathcal{I}(\mathcal F_{=}).\)
A version of Stengle’s Positivstellensatz [G. Stengle, Math. Ann. 207, 87–97 (1973; Zbl 0253.14001)] states that given a system of sign conditions \(\mathcal F,\) its unrealizability in any ordered extension of \(K\) and its incompatibility are equivalent. Right on the first pages the authors show by very short proofs how the real Nullstellensatz can be deduced and from this in turn Stengle’s improved version of Artin’s solution to Hilbert’s 17th problem. H. Lombardi [Lect. Notes Math. 1524, 323–345 (1992; Zbl 0782.14001)] has given complexity bounds for the Positivstellensatz which involve towers of powers of 2 whose length increase linearly with \(k.\) From this similar enormous bounds follow for the other two theorems. With the tools of weak inference and weak existence designed by Lombardi at the time and by replacing Cohen-Hoermander quantifier elimination by a new type of quantifier elimination based on Thom encoding of real algebraic numbers; see [D. Perrucci and M.-F. Roy, Ann. Pure Appl. Logic 168, No. 8, 1588–1604 (2017; Zbl 1373.14060)], the authors achieve very notable improvements getting down from primitive recursive bounds to elementary recursive bounds.
Chapter 2 is dedicated to obtain many weak inference rules continuously used in later chapters. Assume \(\mathcal{F}, \mathcal{F}_1, \dots, \mathcal{F}_m, \mathcal{H}\) are systems of sign conditions and we know that if \(\mathcal F\) is satisfied at \(\vartheta\in R^k\), then one of \(\mathcal{F}_1, \dots ,\mathcal F_m\) is satisfied at \(\vartheta\). Then if the enlarged signconditions \([\mathcal F_1,\mathcal H], \dots, [\mathcal F_m,\mathcal H]\) are unsatisfiable, then \([\mathcal F,\mathcal H]\) will be unsatisfiable. (Here, naturally \([\mathcal F,\mathcal H]= \{\mathcal{F}_{\neq}\cup \mathcal{H}_{\neq} , \mathcal{F}_{\geq}\cup \mathcal{H}_{\geq} , \mathcal{F}_{=}\cup \mathcal{H}_{=} \}\). ) A weak inference is a construction to reflect this on the incompatibility level: it produces from initial incompatibilities \(\downarrow \mathcal F_1,\mathcal H\downarrow, \downarrow \mathcal F_2,\mathcal H\downarrow ,\dots , \downarrow \mathcal F_m,\mathcal H\downarrow \) a final incompatibility \( \downarrow \mathcal F ,\mathcal H\downarrow. \) Theorems proving such constructions are generically written \( \mathcal{F} \vdash \bigvee\limits _{j=1}^m \mathcal{F}_j,\) making aptly use of well-known symbols of Logic. The authors accompany such theorems almost always with degree bounds. To give a flavour of such results we cite (using with the authors a notational abuse)
Lemma 2.17: Let \(P\in K[u]=K[u_1,\dots,u_n].\) Then \(P\neq 0 \vdash P>0 \vee P<0.\) If we have incompatibilities in \(K[v]\) where \(v \supset u\) with monoid part \(S_1 \cdot P^{2e_1}\) and \(S_2 \cdot P^{2e_2}\) and degree in \(w\subset v\) bounded in \(\delta_{w,1}\) and \(\delta_{w,2},\) the final incompatibility has monoid part \(S_1\cdot S_2\cdot P^{2(e_1+e_2)}\) and degree in \(w\) bounded by \(\delta_{w,1}+ \delta_{w,2}.\)
Here and in similar theorems the superset of the original variable set creeps in via the auxiliary sign conditions \(\mathcal{H}.\) Section 2 contains also a generalization of weak inference, called weak existence. An application of the principle of weak existence is the intermediate value theorem in chapter 3 which reads now as if \(P= \sum_{0\leq h\leq p} C_h y^h \in K[u][y],\) then \( \exists(t_1,t_2) [C_p \neq 0, P(t_1)P(t_2)\leq 0] \vdash \exists [P(t)=0].\) Here already the degree estimates for the final incompatibility are doubly exponential in \(p\) (the degree of \(P\) with respect to \(y\)). The proof is based on the fact that if a field is real its extension by an irreducible polynomial of odd degree is also real, an idea E. Artin [Abh. Math. Semin. Univ. Hamb. 5, 100–115 (1926; JFM 52.0122.01)] used in his famous solution to Hilbert’ s 17th problem. The theorem is used to prove the weak existence of the real root for a monic polynomial of odd degree (again with doubly exponential bounds). Chapter 4 uses this theorem to give a weak existence form of the fundamental theorem of algebra for a polynomial \(p\) based on Laplace’s proof by induction on the largest nonnegative integer \(r\) such that \(2^r|\deg p.\) The chapter continues with sections on the decomposition of polynomials into irreducible factors also with multiplicities. Hermite created a theory in which a quadratic form (hence a matrix Her\((P,Q)\) – in fact a Hankel matrix) is associated to two one-variable real polynomials \(P,Q\) and which allows to express the number of roots in \(\mathbb C\) of \(P\) where \(Q\) is nonzero as the rank of the matrix Her\((P,Q);\) and the difference of the number of real roots of \(P\) where \(Q\) is positive minus the number of roots of \(P\) where \(Q\) is negative as the signature of Her\((P,Q).\) This theorem and its formulation in terms of weak inference and attendant degree estimates are the object of the long chapter 5. Along the way Sylvester’s law of inertia is treated and a link of Hermite’s theory to subresultants is given. Chapter 6 is titled ‘Elimination of one variable’ . In Section 6.1 it is noted that given a polynomial \(P\) of degree \(p\) in \(K[y],\) the signs of the first \(p-1\) derivatives of \(P\) at a real root \(\theta\) of \(P\) define a sequence which is unique to it. This is called Thom encoding of \(\theta\) with respect to \(P.\) It gives rise to a new elimination method for families \(\mathcal Q\) of univariate polynomials which depend on parameters. \(\text{Elim}(\mathcal Q)\) is a family of polynomials which determines the realizable sign conditions of \(\mathcal Q.\) A classic method for this is Cylindrical Algebraic Decomposition – see e.g. [B. F. Caviness (ed.) and J. R. Johnson (ed.), Quantifier elimination and cylindrical algebraic decomposition. Proceedings of a symposium, Linz, Austria, October 6–8, 1993. Wien: Springer (1998; Zbl 0906.03033)] – but this is because its close connection to topology (semi-algebraic connectivity) not suitable for getting algebraic identities for showing incompatibilities. The chapter relies heavily on chapter 2 of course but uses only the two culminating results from chapters 4 and 5 respectively. Finally chapter 7 proves the two main results with which the paper opened: it establishes elementary recursive bounds as well for the Positivstellensatz as for the solution to Hilbert’s 17th problem. Only the main result of chapter 6 is used. The annex, chapter 8, gives a number estimates for the multiple exponentials used earlier.
Although the paper is quite technical and the statements of the theorems because of the constructive nature and/or the complexity estimates longer than usual, the exposition which uses in later chapters only the culminating results of earlier ones will help to grasp more rapidly the main thread of reasoning. The paper resumes certainly decades of work and presents a breakthrough in its area.

MSC:

14-02 Research exposition (monographs, survey articles) pertaining to algebraic geometry
12D15 Fields related with sums of squares (formally real fields, Pythagorean fields, etc.)
14P99 Real algebraic and real-analytic geometry
13J30 Real algebra
03F65 Other constructive mathematics
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Artin, Emil, \"Uber die Zerlegung definiter Funktionen in Quadrate, Abh. Math. Sem. Univ. Hamburg, 5, 1, 100-115 (1927) · JFM 52.0122.01 · doi:10.1007/BF02952513
[2] Basu, Saugata; Pollack, Richard; Roy, Marie-Fran\c{c}oise, On the combinatorial and algebraic complexity of quantifier elimination, J. ACM, 43, 6, 1002-1045 (1996) · Zbl 0885.68070 · doi:10.1145/235809.235813
[3] Basu, Saugata; Pollack, Richard; Roy, Marie-Fran\c{c}oise, Algorithms in real algebraic geometry, Algorithms and Computation in Mathematics 10, x+662 pp. (2006), Springer-Verlag, Berlin · Zbl 1102.14041
[4] Basu, Saugata; Pollack, Richard; Roy, Marie-Fran\c{c}oise, Algorithms in real algebraic geometry, Algorithms and Computation in Mathematics 10, x+662 pp. (2006), Springer-Verlag, Berlin · Zbl 1102.14041
[5] Blekherman, Grigoriy; Gouveia, Jo\~ao; Pfeiffer, James, Sums of squares on the hypercube, Math. Z., 284, 1-2, 41-54 (2016) · Zbl 1375.14187 · doi:10.1007/s00209-016-1644-7
[6] Bochnak, J.; Coste, M.; Roy, M.-F., G\'eom\'etrie alg\'ebrique r\'eelle, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)] 12, x+373 pp. (1987), Springer-Verlag, Berlin · Zbl 0633.14016
[7] Brownawell, W. Dale, Local Diophantine Nullstellen inequalities, J. Amer. Math. Soc., 1, 2, 311-322 (1988) · Zbl 0651.10022 · doi:10.2307/1990919
[8] Caniglia, L\'eandro; Galligo, Andr\'e; Heintz, Joos, Borne simple exponentielle pour les degr\'es dans le th\'eor\`eme des z\'eros sur un corps de caract\'eristique quelconque, C. R. Acad. Sci. Paris S\'er. I Math., 307, 6, 255-258 (1988) · Zbl 0686.14001
[9] Cohen, Paul J., Decision procedures for real and \(p\)-adic fields, Comm. Pure Appl. Math., 22, 131-151 (1969) · Zbl 0167.01502 · doi:10.1002/cpa.3160220202
[10] Collins, George E., Quantifier elimination for real closed fields by cylindrical algebraic decomposition. Automata theory and formal languages (Second GI Conf., Kaiserslautern, 1975), 134-183. Lecture Notes in Comput. Sci., Vol. 33 (1975), Springer, Berlin · Zbl 0318.02051
[11] Coste, Michel; Lombardi, Henri; Roy, Marie-Fran\c{c}oise, Dynamical method in algebra: effective Nullstellens\"atze, Ann. Pure Appl. Logic, 111, 3, 203-256 (2001) · Zbl 0992.03076 · doi:10.1016/S0168-0072(01)00026-4
[12] Coste, M.; Roy, M.-F., Thom’s lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets, J. Symbolic Comput., 5, 1-2, 121-129 (1988) · Zbl 0689.14006 · doi:10.1016/S0747-7171(88)80008-7
[13] Cox, David; Little, John; O’Shea, Donal, Ideals, varieties, and algorithms, Undergraduate Texts in Mathematics, xvi+551 pp. (2007), Springer, New York · Zbl 1118.13001 · doi:10.1007/978-0-387-35651-8
[14] D. E. Daykin. Hilbert’s 17th problem. Ph.D. Thesis, Univ. of Reading, (1961) unpublished.
[15] Davenport, James H.; Heintz, Joos, Real quantifier elimination is doubly exponential, J. Symbolic Comput., 5, 1-2, 29-35 (1988) · Zbl 0663.03015 · doi:10.1016/S0747-7171(88)80004-X
[16] Delzell, Charles N., Kreisel’s unwinding of Artin’s proof. Kreiseliana, 113-246 (1996), A K Peters, Wellesley, MA · Zbl 0876.12002
[17] Diaz-Toca, Gema M.; Gonzalez-Vega, Laureano; Lombardi, Henri, Generalizing Cramer’s rule: solving uniformly linear systems of equations, SIAM J. Matrix Anal. Appl., 27, 3, 621-637 (2005) · Zbl 1097.15006 · doi:10.1137/S0895479802418860
[18] Dubois, D. W., A nullstellensatz for ordered fields, Ark. Mat., 8, 111-114 (1969) · Zbl 0205.06102 · doi:10.1007/BF02589551
[19] Efroymson, G., Local reality on algebraic varieties, J. Algebra, 29, 133-142 (1974) · Zbl 0275.14018 · doi:10.1016/0021-8693(74)90118-5
[20] Gantmacher, F. R., The theory of matrices. Vols. 1, 2, Translated by K. A. Hirsch, Vol. 1, x+374 pp. Vol. 2, ix+276 pp. (1959), Chelsea Publishing Co., New York · Zbl 0927.15001
[21] Gonz\'alez-Vega, L.; Lombardi, H.; Recio, T.; Roy, M.-F., Sp\'ecialisation de la suite de Sturm et sous-r\'esultants, RAIRO Inform. Th\'eor. Appl., 24, 6, 561-588 (1990) · Zbl 0732.68059 · doi:10.1051/ita/1990240605611
[22] Grigor’ev, D. Yu., Complexity of deciding Tarski algebra, J. Symbolic Comput., 5, 1-2, 65-108 (1988) · Zbl 0689.03021 · doi:10.1016/S0747-7171(88)80006-3
[23] Grigor’ev, D. Yu.; Vorobjov, N. N., Jr., Solving systems of polynomial inequalities in subexponential time, J. Symbolic Comput., 5, 1-2, 37-64 (1988) · Zbl 0662.12001 · doi:10.1016/S0747-7171(88)80005-1
[24] Grigoriev, Dima; Vorobjov, Nicolai, Complexity of Null- and Positivstellensatz proofs, Ann. Pure Appl. Logic, 113, 1-3, 153-160 (2002) · Zbl 0992.03073 · doi:10.1016/S0168-0072(01)00055-0
[25] Hermann, Grete, Die Frage der endlich vielen Schritte in der Theorie der Polynomideale, Math. Ann., 95, 1, 736-788 (1926) · JFM 52.0127.01 · doi:10.1007/BF01206635
[26] C. Hermite. Remarques sur le theoreme de sturm. C. R. Acad. Sci. Paris, 36, 52-54, (1853).
[27] Hilbert, David, Sur les probl\`emes futurs des math\'ematiques, Les Grands Classiques Gauthier-Villars. [Gauthier-Villars Great Classics], ii+60 pp. (1990), \'Editions Jacques Gabay, Sceaux
[28] Hilbert D. Mathematische Probleme. Gottinger Nachrichten, (1900), 253-297, and in Archiv der Mathematik und Physik, (3) 1 (1901), 44-63 and 213-237.
[29] Hilbert, David, Mathematical problems, Bull. Amer. Math. Soc., 8, 10, 437-479 (1902) · JFM 33.0976.07 · doi:10.1090/S0002-9904-1902-00923-3
[30] H\"ormander, Lars, Linear partial differential operators, Die Grundlehren der mathematischen Wissenschaften, Bd. 116, vii+287 pp. (1963), Academic Press, Inc., Publishers, New York; Springer-Verlag, Berlin-G\"ottingen-Heidelberg · Zbl 0108.09301
[31] Jelonek, Zbigniew, On the effective Nullstellensatz, Invent. Math., 162, 1, 1-17 (2005) · Zbl 1087.14003 · doi:10.1007/s00222-004-0434-8
[32] Koll\'ar, J\'anos, Effective Nullstellensatz for arbitrary ideals, J. Eur. Math. Soc. (JEMS), 1, 3, 313-337 (1999) · Zbl 0986.14043 · doi:10.1007/s100970050009
[33] G. Kreisel. Hilbert’s 17-th problem. in Summaries of talks presented at the Summer Inst. of Symbolic Logic at Cornell Univ (1957)
[34] 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. · Zbl 0148.00105
[35] Krivine, J.-L., Anneaux pr\'eordonn\'es, J. Analyse Math., 12, 307-326 (1964) · Zbl 0134.03902 · doi:10.1007/BF02807438
[36] Lancaster, Peter; Tismenetsky, Miron, The theory of matrices, Computer Science and Applied Mathematics, xv+570 pp. (1985), Academic Press, Inc., Orlando, FL · Zbl 0558.15001
[37] Vo-Khac Khoan, Introduction aux m\'ethodes math\'ematiques modernes de la physique. Espaces pr\'ehilbertiens; s\'erie de Fourier; spectre des op\'erateurs. Distributions, convolutions et transformation de Fourier; espaces de Sobolev. Equations diff\'erentielles; transformation de Laplace; fonctions orthogonales. Equations aux d\'eriv\'ees partielles; m\'ethode de Galerkine-Fourier, 249 pp. +ii pp. (1968), Centre de Documentation Universitaire, Paris · Zbl 0194.30006
[38] S. Lojasiewicz. Ensembles semi-analytiques. Institut des Hautes Etudes Scientifiques, 1965 - 153 pages. · Zbl 0241.32005
[39] Lombardi, Henri, Th\'eor\`eme des z\'eros r\'eel effectif et variantes. Th\'eorie des nombres, Ann\'ee 1988/89, Fasc.1, Publ. Math. Fac. Sci. Besan\c{c}on, 31 pp. (1989), Univ. Franche-Comt\'e, Besan\c{c}on · Zbl 0787.14035
[40] Lombardi, Henri, Effective real Nullstellensatz and variants. Effective methods in algebraic geometry, Castiglioncello, 1990, Progr. Math. 94, 263-288 (1991), Birkh\"auser Boston, Boston, MA · Zbl 0748.14023
[41] Lombardi, Henri, Nullstellensatz r\'eel effectif et variantes, C. R. Acad. Sci. Paris S\'er. I Math., 310, 8, 635-640 (1990) · Zbl 0719.14035
[42] Lombardi, Henri, Th\'eor\`eme des z\'eros r\'eel effectif et variantes. Th\'eorie des nombres, Ann\'ee 1988/89, Fasc.1, Publ. Math. Fac. Sci. Besan\c{c}on, 31 pp. (1989), Univ. Franche-Comt\'e, Besan\c{c}on · Zbl 0787.14035
[43] Lombardi, Henri, Une borne sur les degr\'es pour le th\'eor\`eme des z\'eros r\'eel effectif. Real algebraic geometry, Rennes, 1991, Lecture Notes in Math. 1524, 323-345 (1992), Springer, Berlin · Zbl 0782.14001 · doi:10.1007/BFb0084631
[44] Monk, Leonard Gaines, ELEMENTARY-RECURSIVE DECISION PROCEDURES, 89 pp. (1975), ProQuest LLC, Ann Arbor, MI
[45] Perrucci, Daniel; Roy, Marie-Fran\c{c}oise, Zero-nonzero and real-nonreal sign determination, Linear Algebra Appl., 439, 10, 3016-3030 (2013) · Zbl 1309.14047 · doi:10.1016/j.laa.2013.09.010
[46] Perrucci, Daniel; Roy, Marie-Fran\c{c}oise, Elementary recursive quantifier elimination based on Thom encoding and sign determination, Ann. Pure Appl. Logic, 168, 8, 1588-1604 (2017) · Zbl 1373.14060 · doi:10.1016/j.apal.2017.03.001
[47] Renegar, James, 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, 3, 255-299 (1992) · Zbl 0763.68042 · doi:10.1016/S0747-7171(10)80003-3
[48] Risler, Jean-Jacques, Une caract\'erisation des id\'eaux des vari\'et\'es alg\'ebriques r\'eelles, C. R. Acad. Sci. Paris S\'er. A-B, 271, A1171-A1173 (1970) · Zbl 0211.53401
[49] Rose, H. E., Subrecursion: functions and hierarchies, Oxford Logic Guides 9, xiii+191 pp. (1984), The Clarendon Press, Oxford University Press, New York · Zbl 0539.03018
[50] J. Schmid. On the degree complexity of Hilbert’s 17th problem and the Real Nullstellensatz, Habilitation, University of Dortmund, n r 70, Seminar of logic, Paris 7, (2000).
[51] Seidenberg, A., A new decision method for elementary algebra, Ann. of Math. (2), 60, 365-374 (1954) · Zbl 0056.01804 · doi:10.2307/1969640
[52] Stengle, Gilbert, A nullstellensatz and a positivstellensatz in semialgebraic geometry, Math. Ann., 207, 87-97 (1974) · Zbl 0253.14001 · doi:10.1007/BF01362149
[53] Tarski, Alfred, A decision method for elementary algebra and geometry, iii+63 pp. (1951), University of California Press, Berkeley and Los Angeles, Calif. · Zbl 0044.25102
[54] van der Waerden, B. L., Modern Algebra. Vol. I, xii+264 pp. (1949), Frederick Ungar Publishing Co., New York, N. Y. · Zbl 0039.00902
[55] Warou, H., An algorithm and bounds for the real effective Nullstellensatz in one variable. Algorithms in algebraic geometry and applications, Santander, 1994, Progr. Math. 143, 373-387 (1996), Birkh\"auser, Basel · Zbl 0863.12001
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.