Polinomios que son sumas de cuadrados

Question

¿Se conoce algún algoritmo para determinar si un polinomio multivariante con coeficientes enteros puede escribirse como una suma de cuadrados de dichos polinomios?

A modo de antecedente, si sustituimos "polinomio" por "función racional" entonces existe tal algoritmo, porque una función racional es una suma de cuadrados si es definida positiva. Pero esta equivalencia falla para los polinomios.

Answer 1

José escribe: "si tienes un polinomio que es semidefinido positivo, lo más probable es que sea una suma de cuadrados"

Este tipo de afirmación es muy sensible a la distribución de probabilidad que se utilice en el espacio de todos los polinomios. Estoy seguro de que hay formulaciones en las que es verdadera; aquí hay una en la que es falsa.

Fijemos d mayor que 1. Sea Poly(2d,n) el espacio vectorial de los polinomios homogéneos* de grado 2d en n variables. Elijamos polinomios uniformemente al azar de la esfera unitaria de este espacio. Blekherman ha calculado que la probabilidad de que un polinomio sea positivo es ~ n^{-1/2}, mientras que la probabilidad de que sea una suma de cuadrados es ~ n^{-d/2}. Así, para n grande, casi todos los polinomios positivos no son sumas de cuadrados.

Blekherman también tiene un preprint reciente que muestra que, en el mismo sentido, casi todos los polinomios convexos positivos no son sumas de cuadrados.

* Si no te gusta trabajar con polinomios homogéneos, fíjate en que Poly(2d,n) es también el espacio vectorial de los polinomios inhomogéneos en n-1 variables con grado a lo sumo d. Sólo tienes que introducir 1 para la última variable. Bajo esta correspondencia, un polinomio es no negativo en R^n si y sólo si es no negativo en R^{n-1} x {1}. La propiedad de ser estrictamente positivo no se conserva con esta transformación, pero los polinomios que son no negativos y no estrictamente positivos forman un conjunto de medida 0.

Answer 2

Sí, el grupo de Parillo desarrollado un algoritmo y un toolbox de matlab se llama SOSTOOLS

Hay un grado de complejidad, sin embargo, yo no soy un experto en su algoritmo, por lo que no sé que tan eficiente es su algoritmo. Yo recuerdo haber leído que la suma de los cuadrados de los polinomios son densos en el espacio de positivo semidefinite polinomios por alguna norma.. creo que era L1 norma. Y si usted sabe que el polinomio es positivo y convexa, entonces su "más probable" que se trata de una suma de cuadrados (hasta donde yo sé, nadie ha demostrado que no son convexas (multivariante) polinomios que son positivos, pero no de la suma de los cuadrados).

Answer 3

Determinar si un polinomio es o no una suma de cuadrados se puede hacer en tiempo polinómico; el problema es equivalente a la programación semidefinida. Como mencionó José Capco más arriba, Pablo Parrilo es una autoridad en este tema, y ha escrito varios artículos explicando la relación.

Parrilo tiene una exposición particularmente breve, sencilla y autocontenida de esta relación en Parrilo, Pablo A. "Programas de suma de cuadrados y desigualdades polinómicas". SIAG/OPT Views-and-News: Un Foro del Grupo de Actividad de Optimización de SIAM. Vol. 15. No. 2. 2004 .