Polynôme somme de carrés

En mathématiques, un polynôme homogène à coefficients réels ${\displaystyle h(x)}$ de degré ${\displaystyle 2m}$, en les n variables ${\displaystyle x=(x_{1},\ldots ,x_{n})}$ est somme de carrés (en anglais SOS pour sum of squares) si et seulement s'il existe des polynômes homogènes ${\displaystyle g_{1}(x),\ldots ,g_{k}(x)}$ de degré ${\displaystyle m}$ tels que

${\displaystyle h(x)=\sum _{i=1}^{k}g_{i}(x)^{2}.}$

Exemple et propriétés

Le polynôme homogène de degré 4 en deux variables ${\displaystyle h(x)=x_{1}^{4}-x_{1}^{2}x_{2}^{2}+x_{2}^{4}}$ s'écrit sous la forme

${\displaystyle h(x)=x_{1}^{4}-x_{1}^{2}x_{2}^{2}+x_{2}^{4}=(x_{1}^{2}-x_{2}^{2})^{2}+(x_{1}x_{2})^{2}}$.

Il est donc la somme de deux carrés.

Tout polynôme homogène qui est somme de carrés est un polynôme positif (un polynôme qui ne prend que des valeurs positives) ; la réciproque n'est pas vraie et Hilbert a prouvé que, pour ${\displaystyle n=2,m=1}$ ou pour ${\displaystyle n=3,m=2}$, un polynôme homogène est somme de carrés si et seulement s'il est positif^[1]. Il en est de même pour le problème analogique des polynômes homogènes symétriques positifs ^[2],[3].

Des conditions suffisantes pour qu'un polynôme homogène soit somme de carrés ont été données^[4],[5]. De plus, un polynôme homogène réel positif peut être approchée arbitrairement près (pour la norme ${\displaystyle l_{1}}$ de son vecteur de coefficients) par une suite de polynômes homogènes qui sont sommes de carrés^[6].

Représentation matricielle carrée (SMR)

On peut voir le problème d'établir qu'un polynôme homogène ${\displaystyle h(x)}$ est somme de carrés comme la résolution d'un problème d'optimisation convexe. En effet, ${\displaystyle h(x)}$ peut s'écrire sous la forme

${\displaystyle h(x)=x^{\{m\}'}(H+L(\alpha ))x^{\{m\}}}$

où ${\displaystyle x^{\{m\}}}$ est un vecteur contenant une base des polynômes homogènes de degré ${\displaystyle m}$ en ${\displaystyle x}$ (comme par exemple les monômes de degré degré ${\displaystyle m}$ en ${\displaystyle x}$), le symbole ′ désigne la transposée, où ${\displaystyle H}$ est la matrice symétrique vérifiant

${\displaystyle h(x)=x^{\left\{m\right\}'}Hx^{\{m\}}}$

et où ${\displaystyle L(\alpha )}$ est une paramétrisation linéaire de l'espace linéaire

${\displaystyle {\mathcal {L}}=\left\{L=L':~x^{\{m\}'}Lx^{\{m\}}=0\right\}.}$

La dimension du vecteur ${\displaystyle x^{\{m\}}}$ est égale à

${\displaystyle \sigma (n,m)={\binom {n+m-1}{m}},}$

et la dimension du vecteur ${\displaystyle \alpha }$ est :

${\displaystyle \omega (n,2m)={\frac {1}{2}}\sigma (n,m)\left(1+\sigma (n,m)\right)-\sigma (n,2m).}$

Avec ces notation, le polynôme ${\displaystyle h(x)}$ est une somme de carrés si et seulement s'il existe un vecteur ${\displaystyle \alpha }$ tel que

${\displaystyle H+L(\alpha )\geq 0}$,

ce qui signifie que la matrice ${\displaystyle H+L(\alpha )}$ est semi-définie positive. On se ramène ainsi à la vérification d'une inégalité matricielle linéaire qui est un problème d'optimisation convexe. L'expression

${\displaystyle h(x)=x^{\{m\}'}\left(H+L(\alpha )\right)x^{\{m\}}}$

a été introduite dans^[7] sous le nom de représentation matricielle carrée (square matrix representation abrégé en SMR) afin d'établir si un polynôme homogène est somme de carrés à travers une inégalité matricielle linéaire. Cette représentation est également connue sous le nom de matrice de Gram^[8].

Exemples

• On considère le polynôme homogène de degré 4 en deux variables ${\displaystyle h(x)=x_{1}^{4}-x_{1}^{2}x_{2}^{2}+x_{2}^{4}}$ . On a

${\displaystyle m=2,~x^{\{m\}}=\left({\begin{array}{c}x_{1}^{2}\\x_{1}x_{2}\\x_{2}^{2}\end{array}}\right)\!,~H+L(\alpha )=\left({\begin{array}{ccc}1&0&-\alpha _{1}\\0&-1+2\alpha _{1}&0\\-\alpha _{1}&0&1\end{array}}\right)\!.}$

Pour la valeur ${\displaystyle \alpha =1}$ on a ${\displaystyle H+L(\alpha )\geq 0}$ ; il s'ensuit que ${\displaystyle h(x)}$ est somme de carrés.

• On considère le polynôme homogène de degré 4 en trois variables ${\displaystyle h(x)=2x_{1}^{4}-2.5x_{1}^{3}x_{2}+x_{1}^{2}x_{2}x_{3}-2x_{1}x_{3}^{3}+5x_{2}^{4}+x_{3}^{4}}$ . On a

${\displaystyle m=2,~x^{\{m\}}=\left({\begin{array}{c}x_{1}^{2}\\x_{1}x_{2}\\x_{1}x_{3}\\x_{2}^{2}\\x_{2}x_{3}\\x_{3}^{2}\end{array}}\right)\!,~H+L(\alpha )=\left({\begin{array}{cccccc}2&-1.25&0&-\alpha _{1}&-\alpha _{2}&-\alpha _{3}\\-1.25&2\alpha _{1}&0.5+\alpha _{2}&0&-\alpha _{4}&-\alpha _{5}\\0&0.5+\alpha _{2}&2\alpha _{3}&\alpha _{4}&\alpha _{5}&-1\\-\alpha _{1}&0&\alpha _{4}&5&0&-\alpha _{6}\\-\alpha _{2}&-\alpha _{4}&\alpha _{5}&0&2\alpha _{6}&0\\-\alpha _{3}&-\alpha _{5}&-1&-\alpha _{6}&0&1\end{array}}\right)\!.}$

Comme ${\displaystyle H+L(\alpha )\geq 0}$ pour ${\displaystyle \alpha =(1.18,-0.43,0.73,1.13,-0.37,0.57)}$, il s'ensuit que ${\displaystyle h(x)}$ est somme de carrés.

Somme de carrés de polynômes non commutatifs

On considère l'algèbre libre ${\displaystyle R\langle X\rangle }$ engendrée par ${\displaystyle n}$ symboles non commutants ${\displaystyle X=\{x_{1},\ldots ,x_{n}\}}$, muni de l'involution ~, qui fixe ${\displaystyle R}$ et les ${\displaystyle x_{i}}$ et qui retourne les mots sur ${\displaystyle X}$ . Par analogie au cas commutatif, les polynômes symétriques non commutatifs sont les polynômes non commutatifs invariants par l'involution ~.

Un polynôme non commutatif est somme de carrés s'il existe des polynômes non commutatifs ${\displaystyle h_{1},\ldots ,h_{k}}$ tel que

${\displaystyle f(X)=\sum _{i=1}^{k}h_{i}(X)^{\sim }h_{i}(X).}$

Lorsqu'une matrice réelle de dimension ${\displaystyle r\times r}$ est évaluée en un polynôme non commutatif symétrique ${\displaystyle f}$ , et qu'on obtient une matrice semi-définie positive, ${\displaystyle f}$ est dite matrice-positif. Dans le cadre non commutatif, un polynôme non commutatif est somme de carrés si et seulement s'il est matrice-positif^[9]. De plus, il existe des algorithmes pour décomposer les polynômes matrice-positifs en une somme des carrés de polynômes non commutatifs^[10].

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Polynomial SOS » (voir la liste des auteurs).

1. David Hilbert, « Ueber die Darstellung definiter Formen als Summe von Formenquadraten », Mathematische Annalen, vol. 32, n^o 3,‎ septembre 1888, p. 342–350 (DOI 10.1007/bf01443605, lire en ligne).
2. M. D. Choi et T. Y. Lam, « An old question of Hilbert », Queen's Papers in Pure and Applied Mathematics, vol. 46,‎ 1977, p. 385–405.
3. Charu Goel, Salma Kuhlmann et Bruce Reznick, « On the Choi–Lam analogue of Hilbert's 1888 theorem for symmetric forms », Linear Algebra and Its Applications, vol. 496,‎ mai 2016, p. 114–120 (DOI 10.1016/j.laa.2016.01.024, arXiv 1505.08145).
4. Jean B. Lasserre, « Sufficient conditions for a real polynomial to be a sum of squares », Archiv der Mathematik, vol. 89, n^o 5,‎ 2007, p. 390–398 (DOI 10.1007/s00013-007-2251-y, arXiv math/0612358, lire en ligne)
5. Victoria Powers et Thorsten Wörmann, « An algorithm for sums of squares of real polynomials », Journal of Pure and Applied Algebra, vol. 127, n^o 1,‎ 1998, p. 99–104 (DOI 10.1016/S0022-4049(97)83827-3, lire en ligne ).
6. Jean B. Lasserre, « A Sum of Squares Approximation of Nonnegative Polynomials », SIAM Review, vol. 49, n^o 4,‎ 2007, p. 651–669 (DOI 10.1137/070693709, arXiv math/0412398).
7. G. Chesi, A. Tesi, A. Vicino et R. Genesio « On convexification of some minimum distance problems » (1999) (lire en ligne)
   — « (ibid.) », dans Proceedings of the 5th European Control Conference, Karlsruhe, Germany, IEEE, p. 1446–1451.
8. M. Choi, T. Lam et B. Reznick « Sums of squares of real polynomials » (1995) (lire en ligne)
   — « (ibid.) », dans Proceedings of Symposia in Pure Mathematics, p. 103–125.
9. J. William Helton, « "Positive" Noncommutative Polynomials Are Sums of Squares », The Annals of Mathematics, vol. 156, n^o 2,‎ septembre 2002, p. 675–694 (DOI 10.2307/3597203, JSTOR 3597203)
10. Sabine Burgdorf, Kristijan Cafuta, Igor Klep et Janez Povh, « Algorithmic aspects of sums of Hermitian squares of noncommutative polynomials », Computational Optimization and Applications, vol. 55, n^o 1,‎ 25 octobre 2012, p. 137–153 (DOI 10.1007/s10589-012-9513-8)

Voir également

• Dix-septième problème de Hilbert
• Sommes de carrés