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


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


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.



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?

  • $\begingroup$ Your first line can be replaced simply by Variables[exp]. $\endgroup$ Jan 19, 2015 at 23:14
  • $\begingroup$ 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. $\endgroup$
    – halirutan
    Jan 20, 2015 at 0:30
  • $\begingroup$ @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. $\endgroup$
    – E.O.
    Jan 20, 2015 at 9:46
  • $\begingroup$ @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? $\endgroup$
    – halirutan
    Jan 20, 2015 at 13:57
  • $\begingroup$ @halirutan sorry, I should have made that clear. It only needs to be positive when the variables have 0/1 values. $\endgroup$
    – E.O.
    Jan 20, 2015 at 14:15

1 Answer 1


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]]

Your example.

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

(* Out[65]= 1 - 2 t[1] - 2 t[2] + 2 t[3] + t[3]^2 + 2 t[4] - 
 2 t[3] t[4] + t[4]^2 *)

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.