Abstract
Let \(P\in\mathbb{Z[X]}\) be a polynomial of degree p with coefficients in the monomial basis of bit-size bounded by τ. If P is positive on [−1,1], we obtain a certificate of positivity (i.e., a description of P making obvious that it is positive) of bit-size O(p 4(τ+log 2 p)). Previous comparable results had a bit-size complexity exponential in p and τ (Powers and Reznick in Trans. Am. Math. Soc. 352(10):4677–4692, 2000; Powers and Reznick in J. Pure Appl. Algebra 164:221–229, 2001).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Basu, S., Pollack, R., Roy, M.-F.: Algorithms in Real Algebraic Geometry, 2nd edn. Springer, Berlin (2006). Revised version of the first edition online at http://perso.univ-rennes1.fr/marie-francoise.roy/
Bochnak, J., Coste, M., Roy, M.-F.: Real Algebraic Geometry, 2nd edn. Springer, Berlin (1998)
Bernstein, S.: Sur la représentation des polynômes positifs. Soobshch. Har’k. Mat. Obshch. 2(14), 227–228 (1915). Collected Papers of S.N. Bernstein, vol. 1, Constructive Theory of Functions (1905–1930), pp. 251–252. Academy of Sciences, USSR (1952)
Bugeaud, Y., Mignotte, M.: Private communication (2005)
Caruso, F.: The SARAG library. In: Proceedings of the ICMS ’06. Springer, Berlin (2006). Stable version included in maxima: http://maxima.sourceforge.net/, last version online at http://perso.univ-rennes1.fr/marie-francoise.roy/bpr-posted1.html
Eigenwillig, A., Sharma, V., Yap, C.K.: Almost tight recursion tree bounds for the Descartes method. In: Proceedings of the 2006 International Symposium on Symbolic and Algebraic Computation, Italy, pp. 71–78. ACM, New York (2006)
Leroy, R.: Certificates of positivity in the multivariate Bernstein basis, in preparation
Lukacs, F.: Verschärfung des ersten Mittelwertsatzes der Integralrechnung fur rationale Polynome. Math. Z. 2, 295–315 (1918)
Markov, A.A.: Lectures notes on functions with the least deviation from zero (1906). Reprinted in Achiezer, N. (ed.) Selected Papers, pp. 244–291. Gos TechIzdat (1948)
Nesterov, Y.: Squared functional systems and optimization problems. In: Frenk, H., Roos, K., Terlaky, T., Zhang, S. (eds.) High Performance Optimization, pp. 405–440. Kluwer Academic, Dordrecht (2000)
Polya, G.: Über positive Darstellung von Polynomen. Vierteljahrsschr. Nat. Forsch. Ges. Zür. 73, 141–145 (1928). Collected Papers, vol. 2, pp. 309–313. MIT (1974)
Powers, V., Reznick, B.: Polynomials that are positive on an interval. Trans. Am. Math. Soc. 352(10), 4677–4692 (2000)
Powers, V., Reznick, B.: A new bound for Polya’s Theorem with applications to polynomials positive on polyhedra. J. Pure Appl. Algebra 164, 221–229 (2001)
Powers, V., Reznick, B.: Private communication (2006)
Reif, U.: Sharp, quantitative bounds on the distance between a polynomial piece and its Bezier control polygon. Comput. Aided Geom. Des. 17, 579–589 (2000)
Stengle, G.: A Nullstellensatz and a Positivstellensatz in semialgebraic geometry. Math. Ann. 207, 87–97 (1974)
Szegö, G.: Orthogonal Polynomials. AMS Colloquium Publications, vol. XXIII (1939)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Boudaoud, F., Caruso, F. & Roy, MF. Certificates of Positivity in the Bernstein Basis. Discrete Comput Geom 39, 639–655 (2008). https://doi.org/10.1007/s00454-007-9042-x
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-007-9042-x