14
$\begingroup$

The quartic form

$$(x^2 + y^2 + z^2)^2 - 3 ( x^3 y + y^3 z + z^3 x)$$

is non-negative for all real $x$, $y$, $z$, as one can check (with some effort). A theorem of Hilbert implies that there exist quadratic forms $Q_1$, $Q_2$, $Q_3$ so that

$$(x^2 + y^2 + z^2)^2 - 3( x^3 y + y^3 z + z^3 x) = Q_1^2 + Q_2^2 + Q_3^2$$

I would like to find an explicit writing of the quartic forms, with rational quadratic forms $Q_i$. Maybe more than $3$ terms are necessary.

$\endgroup$
4
  • $\begingroup$ Why $3$ quadratic forms? What is special about $3$? $\endgroup$ Commented Sep 5, 2017 at 15:55
  • $\begingroup$ In this case ( positive quartic forms) $3$ squares will do. I don't know how HIlbert proved his result. It is not valid for more variables or higher degree I suppose, there are counter examples. So $3$ is just the number that will do. $\endgroup$ Commented Sep 5, 2017 at 15:59
  • $\begingroup$ I believe $2$ will do in this case. I will update my answer soon. $\endgroup$ Commented Sep 5, 2017 at 16:14
  • $\begingroup$ @Rodrigo de Azevedo: That would be pretty nice then. So you can get a positive semidefinite matrix of rank $2$ in that subspace. Interesting. If you could just produce the matrix that would do it. $\endgroup$ Commented Sep 5, 2017 at 16:18

4 Answers 4

Reset to default
28
$\begingroup$

We are given a trivariate quartic form

$$ f (x, y, z) := (x^2 + y^2 + z^2)^2 - 3 ( x^3 y + y^3 z + z^3 x) $$

which can be rewritten as the sum of $9$ monomials

$$f (x, y, z) = x^4 + y^4 + z^4 + 2 x^2 y^2 + 2 x^2 z^2 + 2 y^2 z^2 - 3 x^3 y - 3 y^3 z - 3 z^3 x $$

and we would like to write it as the sum of squares (SOS) of quadratic forms. The fewer the better.

SOS decomposition

A general trivariate quartic form is parametrized as follows

$$\begin{array}{c} \begin{bmatrix} x^2\\ y^2\\ z^2\\ x y\\ x z\\ y z\end{bmatrix}^\top \begin{bmatrix} q_{11} & q_{12} & q_{13} & q_{14} & q_{15} & q_{16}\\ q_{12} & q_{22} & q_{23} & q_{24} & q_{25} & q_{26}\\ q_{13} & q_{23} & q_{33} & q_{34} & q_{35} & q_{36}\\ q_{14} & q_{24} & q_{34} & q_{44} & q_{45} & q_{46}\\ q_{15} & q_{25} & q_{35} & q_{45} & q_{55} & q_{56}\\ q_{16} & q_{26} & q_{36} & q_{46} & q_{56} & q_{66}\end{bmatrix} \begin{bmatrix} x^2\\ y^2\\ z^2\\ x y\\ x z\\ y z\end{bmatrix} = \\\\ = q_{11} x^4 + q_{22} y^4 + q_{33} z^4 + 2 q_{14} x^3 y + 2 q_{15} x^3 z + 2 q_{24} x y^3 + 2 q_{26} y^3 z + 2 q_{35} x z^3 + 2 q_{36} y z^3 + (2 q_{12} + q_{44}) x^2 y^2 + (2 q_{13} + q_{55}) x^2 z^2 + (2 q_{23} + q_{66}) y^2 z^2 + (2 q_{16} + 2 q_{45}) x^2 y z + (2 q_{46} + 2 q_{25}) x y^2 z + (2 q_{34} + 2 q_{56}) x y z^2\end{array}$$

Note that the $6 \times 6$ matrix above, which we denote by $\mathrm Q$, is symmetric by construction. Hence, we have $1 + 2 + \cdots + 6 = 21$ unknowns (instead of $6^2 = 36$). We recover the particular quartic $f$ if the following $15$ affine equality constraints are satisfied

$$\begin{array}{rl} q_{11} &= 1\\ q_{22} &= 1\\ q_{33} &= 1\\ 2 q_{14} &= -3\\ q_{15} &= 0\\ q_{24} &= 0\\ 2 q_{26} &= -3\\ 2 q_{35} &= -3\\ q_{36} &= 0\\ 2 q_{12} + q_{44} &= 2\\ 2 q_{13} + q_{55} &= 2\\ 2 q_{23} + q_{66} &= 2\\ 2 q_{16} + 2 q_{45} & = 0\\ 2 q_{46} + 2 q_{25} &= 0\\ 2 q_{34} + 2 q_{56} &= 0\end{array}$$

Note that we have $21 - 15 = 6$ degrees of freedom. These $15$ equality constraints can be written much more economically in the following form

$$\mathcal A (\mathrm Q) = \mathrm b$$

where $\mathcal A : \mbox{Sym}_6 (\mathbb R) \to \mathbb R^{15}$ is a linear function and $\mathrm b \in \mathbb R^{15}$.

Our goal is to find a (symmetric) positive semidefinite $6 \times 6$ matrix $\rm Q$ such that the $15$ equality constraints above are satisfied. If such a matrix $\rm Q$ exists, then there exists a ("square root") matrix $\rm R$ such that $\rm Q = R R^T$ and, thus, $f$ can be written as a SOS of quadratic forms.

Approximate solution

We would like matrix $\rm Q$ to be low-rank, in order to have as few terms in the SOS decomposition as possible. Hence, we have the following rank-minimization problem

$$\begin{array}{ll} \text{minimize} & \mbox{rank} (\mathrm Q)\\ \text{subject to} & \mathcal A (\mathrm Q) = \mathrm b\\ & \mathrm Q \succeq \mathrm O_6\end{array}$$

Unfortunately, the objective function, $\mbox{rank} (\mathrm Q)$, is non-convex. One popular heuristic is to minimize the nuclear norm of $\rm Q$, which is a convex proxy for $\mbox{rank} (\mathrm Q)$. Fortunately, the nuclear norm of a symmetric, positive semidefinite matrix is its trace, i.e., a linear function of the matrix's (diagonal) entries. Thus, we obtain the following semidefinite program (SDP)

$$\begin{array}{ll} \text{minimize} & \mbox{tr} (\mathrm Q)\\ \text{subject to} & \mathcal A (\mathrm Q) = \mathrm b\\ & \mathrm Q \succeq \mathrm O_6\end{array}$$

which is convex and, thus, computationally tractable. The following Python + NumPy + CVXPY script solves the SDP above:

from cvxpy import * import numpy as np np.set_printoptions(linewidth=125) # matrix variable Q = Semidef(6) # objective function objective = Minimize( trace(Q) ) # constraints constraints = [ Q[0,0] == 1, Q[1,1] == 1, Q[2,2] == 1, 2*Q[0,3] == -3, Q[0,4] == 0, Q[1,3] == 0, 2*Q[1,5] == -3, 2*Q[2,4] == -3, Q[2,5] == 0, 2*Q[0,1] + Q[3,3] == 2, 2*Q[0,2] + Q[4,4] == 2, 2*Q[1,2] + Q[5,5] == 2, 2*Q[0,5] + 2*Q[3,4] == 0, 2*Q[3,5] + 2*Q[1,4] == 0, 2*Q[2,3] + 2*Q[4,5] == 0 ] # create optimization problem prob = Problem(objective, constraints) # solve optimization problem prob.solve() print "Solution = \n", Q.value print "Solution after rounding = \n", np.round(Q.value, 1) # compute eigendecomposition of the solution Lambda, V = np.linalg.eigh( Q.value ) print "Eigenvalues = \n", Lambda

This script produces the following output:

Solution = [[ 1.00052427e+00 -4.93986993e-01 -4.93986993e-01 -1.50131075e+00 8.16263094e-04 1.48128400e+00] [ -4.93986993e-01 1.00052427e+00 -4.93986993e-01 8.16263094e-04 1.48128400e+00 -1.50131075e+00] [ -4.93986993e-01 -4.93986993e-01 1.00052427e+00 1.48128400e+00 -1.50131075e+00 8.16263095e-04] [ -1.50131075e+00 8.16263094e-04 1.48128400e+00 2.98994780e+00 -1.48087234e+00 -1.48087234e+00] [ 8.16263094e-04 1.48128400e+00 -1.50131075e+00 -1.48087234e+00 2.98994780e+00 -1.48087234e+00] [ 1.48128400e+00 -1.50131075e+00 8.16263095e-04 -1.48087234e+00 -1.48087234e+00 2.98994780e+00]] Solution after rounding = [[ 1. -0.5 -0.5 -1.5 0. 1.5] [-0.5 1. -0.5 0. 1.5 -1.5] [-0.5 -0.5 1. 1.5 -1.5 0. ] [-1.5 0. 1.5 3. -1.5 -1.5] [ 0. 1.5 -1.5 -1.5 3. -1.5] [ 1.5 -1.5 0. -1.5 -1.5 3. ]] Eigenvalues = [ -3.66863824e-04 1.62150777e-03 1.62150779e-03 4.11202771e-02 5.96370990e+00 5.96370990e+00]

The SDP solver produces a matrix $\rm Q$ whose (numerical) rank is $2$. Note that one of the eigenvalues of $\rm Q$ is slightly negative due to numerical noise.

Exact solution

The approximate solution produced by the SDP solver suggests that the exact solution is

$$\mathrm Q = \begin{bmatrix} 1 & - \frac{1}{2} & - \frac{1}{2} & - \frac{3}{2} & 0 & \frac{3}{2}\\- \frac{1}{2} & 1 & - \frac{1}{2} & 0 & \frac{3}{2} & - \frac{3}{2}\\- \frac{1}{2} & - \frac{1}{2} & 1 & \frac{3}{2} & - \frac{3}{2} & 0\\- \frac{3}{2} & 0 & \frac{3}{2} & 3 & - \frac{3}{2} & - \frac{3}{2}\\0 & \frac{3}{2} & - \frac{3}{2} & - \frac{3}{2} & 3 & - \frac{3}{2}\\ \frac{3}{2} & - \frac{3}{2} & 0 & - \frac{3}{2} & - \frac{3}{2} & 3\end{bmatrix}$$

It is easy to verify that, indeed, this is the exact solution. Using Python + SymPy:

from sympy import * # build Q matrix U = Matrix([[ 1, -1, -1, -3, 0, 3], [ 0, 1, -1, 0, 3, -3], [ 0, 0, 1, 3, -3, 0], [ 0, 0, 0, 3, -3, -3], [ 0, 0, 0, 0, 3, -3], [ 0, 0, 0, 0, 0, 3]]) Q = (U + U.T) / 2 print "Determinant = ", Q.det() print "Rank = ", Q.rank() print "Eigenvalues = ", Q.eigenvals() # compute Cholesky decomposition L = Q.cholesky() print "6x2 square root = ", L[:,[0,1]] ##################################### # compute the exact SOS decomposition ##################################### x, y, z = symbols('x y z') # quartic form f = (x**2 + y**2 + z**2)**2 - 3 * ( x**3 * y + y**3 * z + z**3 * x) # quadratic forms q1 = (L[:,0].T * Matrix([x**2, y**2, z**2, x*y, x*z, y*z]))[0,0] q2 = (L[:,1].T * Matrix([x**2, y**2, z**2, x*y, x*z, y*z]))[0,0] print "Error polynomial = ", simplify(q1**2 + q2**2 - f)

This script produces the following output:

Determinant = 0 Rank = 2 Eigenvalues = {0: 4, 6: 2} 6x2 square root = Matrix([[ 1, 0], [-1/2, sqrt(3)/2], [-1/2, -sqrt(3)/2], [-3/2, -sqrt(3)/2], [ 0, sqrt(3)], [ 3/2, -sqrt(3)/2]]) Error polynomial = 0

Thus, a SOS decomposition of $f$ is

$$\boxed{\begin{array}{rl} f (x,y,z) &= \left( x^{2} - \frac{y^{2}}{2} - \frac{z^{2}}{2} - \frac{3}{2} x y + \frac{3}{2} y z \right)^2 + \left( \frac{\sqrt{3}}{2} \left( y^{2} - z^{2} - x y + 2 x z - y z \right) \right)^2\\ &= \frac{1}{4} \left( 2 x^{2} - y^{2} - z^{2} - 3 x y + 3 y z \right)^2 + \frac{3}{4} \left( y^{2} - z^{2} - x y + 2 x z - y z \right)^2\end{array}}$$

References

$\endgroup$
11
  • $\begingroup$ Oh, great, so this is a SOS method, right? $\endgroup$ Commented Sep 3, 2017 at 0:37
  • $\begingroup$ Yes, it is Parrilo's method. $\endgroup$ Commented Sep 3, 2017 at 0:39
  • $\begingroup$ That is indeed impressive! Did not expect to have a solution in $2$ terms. Do you think that there are just finitely many solutions of rank $2$? $\endgroup$ Commented Sep 8, 2017 at 16:41
  • $\begingroup$ The column space of $\rm Q$ is $2$-dimensional. Every orthonormal basis for this $2$-dimensional column space leads to a SOS decomposition with 2 terms. $\endgroup$ Commented Sep 8, 2017 at 23:10
  • 1
    $\begingroup$ @TuongNguyenMinh Actually, my previous comment may have been wrong. I removed it. Do you have experience with symbolic computation? If so, and if you have some time, looking for a rank-1 matrix that satisfies the constraints would be interesting. $\endgroup$ Commented Apr 25, 2021 at 12:42
23
$\begingroup$

$$(x^2 + y^2 + z^2)^2 - 3 ( x^3 y + y^3 z + z^3 x)=\frac{1}{2}\sum_{cyc}(x^2-y^2-xy-xz+2yz)^2=$$ $$=\frac{1}{6}\sum_{cyc}(x^2-2y^2+z^2-3xz+3yz)^2.$$

$\endgroup$
0
4
$\begingroup$

$$(\,\sum\limits_{cyc}\,x^{\,2}\,)^{\,2}- 3(\,\sum\limits_{cyc}\,x^{\,3}y\,)= \frac{1}{6}\left ( \sum\limits_{cyc}\,(\,-\,3\,yz+ 3\,xy+ y^{\,2}+ z^{\,2}- 2\,x^{\,2}\,)^{\,2} \right )$$ $$(\,\sum\limits_{cyc}\,x^{\,2}\,)^{\,2}- 3(\,\sum\limits_{cyc}\,x^{\,3}y\,)= \frac{1}{2}\left ( \sum\limits_{cyc}\,(\,-\,yz- zx+ 2\,xy+ z^{\,2}- x^{\,2}\,)^{\,2} \right )$$ After that, using $ab+ bc+ ca= 0\!\therefore\!a\equiv (a- b)(b- c),b\equiv (b- c)(c- a),c\equiv (c- a)(a- b)$, so $$(\,\sum\limits_{cyc}\,x^{\,2}\,)^{\,2}- 3(\,\sum\limits_{cyc}\,x^{\,3}y\,)= \frac{1}{14}\left ( \sum\limits_{cyc}\,(\,x^{\,2}+ 2\,y^{\,2}- 3\,z^{\,2}- 4\,xy- yz+ 5\,zx\,)^{\,2} \right )$$ $$(\,\sum\limits_{cyc}\,x^{\,2}\,)^{\,2}- 3(\,\sum\limits_{cyc}\,x^{\,3}y\,)= \frac{1}{14}\left ( \sum\limits_{cyc}\,(\,2\,x^{\,2}+ y^{\,2}- 3\,z^{\,2}- 5\,xy+ yz+ 4\,zx\,)^{\,2} \right )$$ $$(\,\sum\limits_{cyc}\,x^{\,2}\,)^{\,2}- 3(\,\sum\limits_{cyc}\,x^{\,3}y\,)= \frac{1}{14}\left ( \sum\limits_{cyc}\,(\,3\,x^{\,2}- y^{\,2}- 2\,z^{\,2}- 5\,xy+ 4\,yz+ zx\,)^{\,2} \right )$$ $$(\,\sum\limits_{cyc}\,x^{\,2}\,)^{\,2}- 3(\,\sum\limits_{cyc}\,x^{\,3}y\,)= \frac{1}{14}\left ( \sum\limits_{cyc}\,(\,3\,y^{\,2}- 2\,z^{\,2}- x^{\,2}- xy- 4\,yz+ 5\,zx\,)^{\,2} \right )$$ because we always have the following equality with $\sum\limits_{cyc}\left ( (\,a- b\,)(\,b- c\,) \right )\left ( (\,b- c\,)(\,c- a\,) \right )= 0$ $$\left ( \sum\limits_{cyc}\left ( (\,a- b\,)(\,b- c\,) \right )^{\,2} \right )(\,x^{\,2}+ y^{\,2}+ z^{\,2}\,)= \sum\limits_{cyc}\,\left ( \sum\limits_{cyc}\,\left ( x(\,a- b\,)(\,b- c\,) \right ) \right )^{\,2}$$

Furthermore, we have $\sum\limits_{cyc}\,(\,-\,3\,yz+ 3\,xy+ y^{\,2}+ z^{\,2}- 2\,x^{\,2}\,)= 0= \left ( \sum\limits_{cyc}(\,a- b\,) \right )$. To apply $$\sum\limits_{cyc}\,\frac{(\!a- b\!)^{2}}{2}\!=\!\frac{(\!a+ b- 2c\!)^{2}\!+\!3(\!a- b\!)^{2}}{4}\!=\!\frac{(\!b+ c- 2a\!)^{2}\!+\!3(\!b- c\!)^{2}}{4}\!=\!\frac{(\!c+ a- 2b\!)^{2}\!+\!3(\!c- a\!)^{2}}{4}$$ $$(\!\sum\limits_{cyc}\,x^{\,2}\!)^{\,2}- 3(\!\sum\limits_{cyc}\,x^{\,3}y\!)= \frac{(\!2\,x^{\,2}- y^{\,2}- z^{\,2}- 3\,xy+ 3\,yz\!)^{\,2}+ 3(\!y^{\,2}- z^{\,2}- xy- yz+ 2\,zx\!)^{\,2}}{4}$$

$\endgroup$
4
$\begingroup$

Using Macaulay2 (version 1.16) with package SumsOfSquares:

i1 : needsPackage( "SumsOfSquares" ); i2 : R = QQ[x,y,z]; i3 : f = (x^2 + y^2 + z^2)^2 - 3*( x^3 * y + y^3 * z + z^3 * x); i4 : sosPoly solveSOS f 1 2 1 1 1 2 2 9 1 2 2 2 1 2 2 o4 = (3)(- -x + x*y - -x*z - -y*z + -z ) + (-)(- -x + -y + x*z - y*z - -z ) 2 2 2 2 4 3 3 3 o4 : SOSPoly

Printing:

i5 : tex o4 o5 = $\texttt{SOSPoly}\left\{\texttt{coefficients}\,\Rightarrow\,\left\{3,\,\frac{9}{4}\right\},\,\texttt{generators}\,\Rightarrow\,\left\{-\frac{1}{2}\,x^{2}+x\,y-\frac{1}{2}\,x\,z -\frac{1}{2}\,y\,z+\frac{1}{2}\,z^{2},\,-\frac{1}{3}\,x^{2}+\frac{2}{3}\,y^{2}+x\,z-y\,z-\frac{1}{3}\,z^{2}\right\},\,\texttt{ring}\,\Rightarrow\,R\right\}$

In $\TeX$:

$$\texttt{SOSPoly}\left\{\texttt{coefficients}\,\Rightarrow\,\left\{3,\,\frac{9}{4}\right\},\,\texttt{generators}\,\Rightarrow\,\left\{-\frac{1}{2}\,x^{2}+x\,y-\frac{1}{2}\,x\,z -\frac{1}{2}\,y\,z+\frac{1}{2}\,z^{2},\,-\frac{1}{3}\,x^{2}+\frac{2}{3}\,y^{2}+x\,z-y\,z-\frac{1}{3}\,z^{2}\right\},\,\texttt{ring}\,\Rightarrow\,R\right\}$$

Hence,

$$\boxed{ f = 3 \left( -\frac{1}{2}\,x^{2}+x\,y-\frac{1}{2}\,x\,z -\frac{1}{2}\,y\,z+\frac{1}{2}\,z^{2} \right)^2 + \frac{9}{4} \left( -\frac{1}{3}\,x^{2}+\frac{2}{3}\,y^{2}+x\,z-y\,z-\frac{1}{3}\,z^{2} \right)^2 }$$

$\endgroup$
1
  • 2
    $\begingroup$ Oh, great! It's good to know that Macaulay can do it. I have to try it. $\endgroup$ Commented Aug 28, 2020 at 17:00

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.