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).

Voir également

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

• Portail des mathématiques