research-article

Certificates of impossibility of Hilbert-Artin representations of a given degree for definite polynomials and functions

Authors:

Erich L. Kaltofen,

Lihong ZhiAuthors Info & Claims

ISSAC '12: Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation

Pages 195 - 202

https://doi.org/10.1145/2442829.2442859

Published: 22 July 2012 Publication History

Abstract

We deploy numerical semidefinite programming and conversion to exact rational inequalities to certify that for a positive semidefinite input polynomial or rational function, any representation as a fraction of sums-of-squares of polynomials with real coefficients must contain polynomials in the denominator of degree no less than a given input lower bound. By Artin's solution to Hilbert's 17th problems, such representations always exist for some denominator degree. Our certificates of infeasibility are based on the generalization of Farkas's Lemma to semidefinite programming.

The literature has many famous examples of impossibility of SOS representability including Motzkin's, Robinson's, Choi's and Lam's polynomials, and Reznick's lower degree bounds on uniform denominators, e.g., powers of the sum-of-squares of each variable. Our work on exact certificates for positive semidefiniteness allows for non-uniform denominators, which can have lower degree and are often easier to convert to exact identities. Here we demonstrate our algorithm by computing certificates of impossibilities for an arbitrary sum-of-squares denominator of degree 2 and 4 for some symmetric sextics in 4 and 5 variables, respectively. We can also certify impossibility of base polynomials in the denominator of restricted term structure, for instance as in Landau's reduction by one less variable.

References

[1]

Ahmadi, A. A., and Parrilo, P. A. A convex polynomial that is not SOS-convex. Mathematical Programming (2011).

[2]

Alizadeh, F. Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM Journal on Optimization 5 (1995), 13--51.

Digital Library

[3]

Artin, E. Über die Zerlegung definiter Funktionen in Quadrate. Abhandlungen Math. Seminar Univ. Hamburg 5, 1 (1927), 100--115.

[4]

Blekherman, G. Dimensional difference between nonnegative polynomials and sums of squares. Computing Research Repository abs/0907.1339 (2009). URL http://arxiv.org/abs/0907.1339.

[5]

Chesi, G. On the gap between positive polynomials and SOS of polynomials. IEEE Trans. Automatic Control 52, 6 (June 2007), 1066--1072.

[6]

Choi, M. D., Lam, T. Y., and Reznick, B. Even symmetric sextics. Mathematische Zeitschrift 195 (Dec. 1987), 559--580.

[7]

Dattorro, J. Convex Optimization & Euclidean Distance Geometry. Meboo Publishing, USA, 2011.

[8]

Giesbrecht, M., Lobo, A., and Saunders, B. D. Certifying inconsistency of sparse linear systems. In ISSAC 98 Proc. 1998 Internat. Symp. Symbolic Algebraic Comput. (New York, N. Y., 1998), O. Gloor, Ed., ACM Press, pp. 113--119.

Digital Library

[9]

Guo, F. SDPTools: High precision SDP solver in Maple. MM-Preprints 28 (2009), 66--73. URL: http://www.mmrc.iss.ac.cn/pub/mm28.pdf/05-guofeng.pdf.

[10]

Harrison, J. Verifying nonlinear real formulas via sums of squares. In Proceedings of the 20th International Conference on Theorem Proving in Higher Order Logics, TPHOLs 2007 (Kaiserslautern, Germany, 2007), K. Schneider and J. Brandt, Eds., vol. 4732 of Lecture Notes in Computer Science, Springer-Verlag, pp. 102--118. URL http://www.cl.cam.ac.uk/~jrh13/papers/sos.pdf.

Digital Library

[11]

Hilbert, D. Über die Darstellung definiter Formen als Summe von Formenquadraten. Math. Ann. 32, 3 (1888), 342--350.

[12]

Hillar, C. Sums of polynomial squares over totally real fields are rational sums of squares. Proc. American Math. Society 137 (2009), 921--930. URL: http://www.math.tamu.edu/~chillar/files/totallyrealsos.pdf.

[13]

Hutton, S. E., Kaltofen, E. L., and Zhi, L. Computing the radius of positive semidefiniteness of a multivariate real polynomial via a dual of Seidenberg's method. In Proc. 2010 Internat. Symp. Symbolic Algebraic Comput. ISSAC 2010 (New York, N. Y., July 2010), S. M. Watt, Ed., Association for Computing Machinery, pp. 227--234. URL: http://www.math.ncsu.edu/~kaltofen/bibliography/10/HKZ10.pdf.

Digital Library

[14]

Kaltofen, E. A short proof of C. Hillar's totally real SOS theorem. Email to Bernd Sturmfels and Chris Hillar, Jan. 2009. URL http://www.math.ncsu.edu/~kaltofen/bibliography/09/totallyreal.pdf.

[15]

Kaltofen, E., Yang, Z., and Zhi, L. A proof of the Monotone Column Permanent (MCP) Conjecture for dimension 4 via sums-of-squares of rational functions. In SNC'09 Proc. 2009 Internat. Workshop on Symbolic-Numeric Comput. (New York, N. Y., 2009), H. Kai and H. Sekigawa, Eds., ACM Press, pp. 65--69. URL: http://www.math.ncsu.edu/~kaltofen/bibliography/09/KYZ09.pdf.

Digital Library

[16]

Kaltofen, E. L., Li, B., Yang, Z., and Zhi, L. Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients. J. Symbolic Comput. 47, 1 (Jan. 2012), 1--15. In memory of Wenda Wu (1929-2009). URL: http://www.math.ncsu.edu/~kaltofen/bibliography/09/KLYZ09.pdf.

Digital Library

[17]

Klep, I., and Schweighofer, M. Infeasibility certificates for linear matrix inequalities, 2011. URL http://www.math.uni-konstanz.de/~schweigh/publications/infeasible.pdf.

[18]

Lasserre, J. B. Global optimization with polynomials and the problem of moments. SIAM Journal on Optimization 11 (2001), 796--817.

Digital Library

[19]

Lasserre, J. B. Moments, Positive Polynomials and Their Applications. Imperial College Press, 2009.

[20]

Laurent, M. Sums of squares, moment matrices and optimization over polynomials. In Emerging Applications of Algebraic Geometry of IMA Volumes in Mathematics and its Applications (2009), vol. 149, Springer, pp. 157--270.

[21]

Peyrl, H., and Parrilo, P. A. Computing sum of squares decompositions with rational coefficients. Theoretical Computer Science 409 (2008), 269--281.

Digital Library

[22]

Powers, V., and Wörmann, T. An algorithm for sums of squares of real polynomials. Journal of Pure and Applied Algebra 6, 1 (1998), 99--104.

[23]

Prajna, S., Papachristodoulou, A., and Parrilo, P. A. SOSTOOLS: Sum of squares optimization toolbox for MATLAB. http://www.cds.caltech.edu/sostools.

[24]

Quarez, R. Bounding the rational sums of squares over totally real fields. Computing Research Repository abs/0907.2336 (2009). URL http://arxiv.org/abs/0907.2336.

[25]

Rajwade, A. R. Squares. Cambridge University Press, 1993.

[26]

Reznick, B. Extremal PSD forms with few terms. Duke Mathematical Journal 45, 2 (1978), 363--374.

[27]

Robinson, R. M. Some definite polynomials which are not sums of squares of real polynomials. In Selected questions of algebra and logic (1973), pp. 264--282. Abstract in Notices Amer. Math. Soc. 16 (1969), p. 554.

[28]

Safey El Din, M., and Zhi, L. Computing rational points in convex semi-algebraic sets and SOS decompositions. SIAM J. Optimization 20, 6 (2010), 2876--2889. URL http://arxiv.org/abs/0910.2973.

Digital Library

[29]

Scheiderer, C. A remark on descending sums of squares representations, July 2009. Manuscript, 2 pages.

[30]

Sturm, J. F. Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optimization Methods and Software 11/12 (1999), 625--653.

[31]

Vandenberghe, L., and Boyd, S. Semidefinite programming. SIAM Review 38, 1 (1996), 49--95.

Digital Library

Cited By

Magron VSafey El Din MSchweighofer MVu TMaza MZhi L(2022)Exact SOHS Decompositions of Trigonometric Univariate Polynomials with Gaussian CoefficientsProceedings of the 2022 International Symposium on Symbolic and Algebraic Computation10.1145/3476446.3535480(325-332)Online publication date: 4-Jul-2022
https://dl.acm.org/doi/10.1145/3476446.3535480
Magron VSafey El Din M(2021)On exact Reznick, Hilbert-Artin and Putinar's representationsJournal of Symbolic Computation10.1016/j.jsc.2021.03.005107:C(221-250)Online publication date: 1-Nov-2021
https://dl.acm.org/doi/10.1016/j.jsc.2021.03.005
Blekherman GGouveia JPfeiffer J(2016)Sums of squares on the hypercubeMathematische Zeitschrift10.1007/s00209-016-1644-7284:1-2(41-54)Online publication date: 21-Apr-2016
https://doi.org/10.1007/s00209-016-1644-7
Show More Cited By

Index Terms

Certificates of impossibility of Hilbert-Artin representations of a given degree for definite polynomials and functions

Recommendations

On exact Reznick, Hilbert-Artin and Putinar's representations
Abstract
We consider the problem of computing exact sums of squares (SOS) decompositions for certain classes of non-negative multivariate polynomials, relying on semidefinite programming (SDP) solvers.

We provide a hybrid numeric-...
Representations of q-orthogonal polynomials

The linearization problem is the problem of finding the coefficients C"k(m,n) in the expansion of the product P"n(x)Q"m(x) of two polynomial systems in terms of a third sequence of polynomials R"k(x), P"n(x)Q"m(x)=@?k=0n+mC"k(m,n)R"k(x). Note that, in ...
Computing low-degree factors of lacunary polynomials: a Newton-Puiseux approach
ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation

We present a new algorithm for the computation of the irreducible factors of degree at most d, with multiplicity, of multivariate lacunary polynomials over fields of characteristic zero. The algorithm reduces this computation to the computation of ...

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences

ISSAC '12: Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation

July 2012

390 pages

ISBN:9781450312691

DOI:10.1145/2442829

General Chair:
Joris van der Hoeven
École Polytechnique, France
,
Program Chair:
Mark van Hoeij
Florida State U.

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Grenoble University: Grenoble University
INRIA: Institut Natl de Recherche en Info et en Automatique

In-Cooperation

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 July 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Division of Computing and Communication Foundations
National Natural Science Foundation of China
NCSU
NKBRPC 2011CB302400

Conference

ISSAC'12

Sponsor:

Grenoble University
INRIA

ISSAC'12: International Symposium on Symbolic and Algebraic Computation

July 22 - 25, 2012

Grenoble, France

Acceptance Rates

ISSAC '12 Paper Acceptance Rate 46 of 86 submissions, 53%;

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
61
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Magron VSafey El Din MSchweighofer MVu TMaza MZhi L(2022)Exact SOHS Decompositions of Trigonometric Univariate Polynomials with Gaussian CoefficientsProceedings of the 2022 International Symposium on Symbolic and Algebraic Computation10.1145/3476446.3535480(325-332)Online publication date: 4-Jul-2022
https://dl.acm.org/doi/10.1145/3476446.3535480
Magron VSafey El Din M(2021)On exact Reznick, Hilbert-Artin and Putinar's representationsJournal of Symbolic Computation10.1016/j.jsc.2021.03.005107:C(221-250)Online publication date: 1-Nov-2021
https://dl.acm.org/doi/10.1016/j.jsc.2021.03.005
Blekherman GGouveia JPfeiffer J(2016)Sums of squares on the hypercubeMathematische Zeitschrift10.1007/s00209-016-1644-7284:1-2(41-54)Online publication date: 21-Apr-2016
https://doi.org/10.1007/s00209-016-1644-7
Zhi LNagasaka KWinkler FSzanto A(2014)Symbolic-numeric algorithms for computing validated resultsProceedings of the 39th International Symposium on Symbolic and Algebraic Computation10.1145/2608628.2627491(25-26)Online publication date: 23-Jul-2014
https://dl.acm.org/doi/10.1145/2608628.2627491
Kaltofen E(2014)Symbolic Computation and Complexity Theory Transcript of My TalkComputer Mathematics10.1007/978-3-662-43799-5_1(3-7)Online publication date: 1-Oct-2014
https://doi.org/10.1007/978-3-662-43799-5_1

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents