# How to reduce a quartic form to a quadratic form with equal roots

Preface: To clear the theoretical background this question is cross-posted on math.stackexchange here.

I have a polynomial in $n$ variables of the form

$$P(x_1,x_2,\dots,x_n)=\left(\sum_{i,j}a_{ij}x_ix_j+\sum_{i}b_{i}x_i+c\right)^2$$

Is there some way to find a polynomial also in $n$ variables of degree at most 2

$$Q(y_1,y_2,\dots,y_n)=\sum_{i,j}d_{ij}y_iy_j+\sum_{i}e_{i}y_i+f$$

with the same roots and which is positive for all values in the domain? You may assume that all the variables only take on the values $0$ or $1$ and all coefficients are real.

At the moment my code is quite messy and FindInstance[] fails when there are a lot of variables.

getVariables[exp_]:=Union@Cases[exp,_Symbol,\[Infinity]]
generateConstraint[tuple_,f_,g_]:=Module[{val=f/.tuple},If[val==0,0==g/.tuple,0<g/.tuple]]

{f,g,nV,constraints,aVars,bVars,cVars,variables=Evaluate@getVariables@eq},
nV=Length@variables;
aVars=$a[1]; bVars=Array[$b,nV];
cVars=Table[\$c[a,b]//Sort,{a,nV},{b,nV}];
f=eq;
g=aVars+bVars.variables+variables.cVars.variables;
Expand[g/.First@FindInstance[And@@constraints,Flatten@{aVars,bVars,cVars}]]
]

convertEqToQuadraticForm[(x y - z w - 1)^2]
(*1 + (w x)/2 - (w y)/2 - 2 x y + y^2 + 2 w z - y z + z^2*)


Is there a nicer way to do this?

• Your first line can be replaced simply by Variables[exp]. Jan 19 '15 at 23:14
• I don't understand your example x y - z w - 1 because in the first sentence, you say that you have a polynomial of the form P=(...)^2 but your example is not of that form. Furthermore, if you have P=f*f doesn't that imply that f has the same roots as P and it is what you want? Except that it might miss the property of being positive. This all looks like it is a question for Mathematics. Jan 20 '15 at 0:30
• @halirutan sorry that was a typo. It was meant to be (xy-zw-1)^2. The positivity is the main challenge of the question. I have cross posted the question on the maths stackexchange.
– E.O.
Jan 20 '15 at 9:46
• @E.O. That's better, because the guys over there should know the theoretical background of your problem. I have another question: You write we can assume that the variables only take 0 or 1 as value. Is it important that the polynomial is positive everywhere or is it enough when it is positive when the variables have 0/1 values? Jan 20 '15 at 13:57
• @halirutan sorry, I should have made that clear. It only needs to be positive when the variables have 0/1 values.
– E.O.
Jan 20 '15 at 14:15

One can go about this using an anzatz that each product of variables is replaced by a sum of corresponding new variables. Some GroebnerBasis rewriting and reduction by the result can then recover the desired form.

convertEqToQuadraticForm[form_, t_] :=
Module[{vars = Variables[form], len, tvars, reps, allvars, gb},
len = Length@vars;
tvars = Array[t, len];
reps = Table[
vars[[i]]*vars[[j]] - (t[i] + t[j]), {i, len - 1}, {j, i, len}];
allvars = Join[vars, tvars];
gb = GroebnerBasis[reps, allvars];
PolynomialReduce[form, gb, allvars][[2]]
]


convertEqToQuadraticForm[(x y - z w - 1)^2, t]

This might need a specialized term order in general in order to force the new variables to minimal degrees. Also the above ansatz is a bit naive. Better might be, for each quadratic term in input e.g. term_k = c[k]*w[i]*w[j], to have a replacement of the form c[k]*(a[i,k]*y[i] + a[j,k]*y[j]).