# Finding solutions of polynomials system

Let $f_1,...,f_n$ be a set of polynomials in $x_1,...,x_n$ with rational coefficients. I need to check whether a system $$f_1=a_1,...,f_n=a_n$$ has a real solution for large enough count of points.

To specify, there is 4 polynomials of degree 2 in 4 variables, and 10^4-10^7 values of $a_1,...,a_n$. I tried

Size = 30 (* really 100-300 *)
f[x1_, x2_, y1_, y2_] := x1 + y1 - 1 (* in fact I need polynomial of degree 2, *)
g[x1_, x2_, y1_, y2_] := x2 + y2     (* but it does not work even for degree 1 *)
Equation[a_, b_] := Reduce[f[x1, x2, y1, y2] == 0 && g[x1, x2, y1, y2] == 0 &&
x1^2 + x2^2 == a && y1^2 + y2^2 == b, {x1, x2, y1, y2}, Reals]
CheckPoint[{a_, b_}] := ! (FindInstance[Equation[a, b], {x1, x2, y1, y2}, Reals] == {})
Points = Select[Tuples[Range[-Size, Size], 2], CheckPoint]
Graphics[Point[#] & /@ Points, Frame -> True,
PlotRange -> {{-Size, Size}, {-Size, Size}}]


but it reduces system each time. Is there efficient enough way to do it almost in no time?

• Could you send some code? Commented Jun 6, 2014 at 18:40
• most likely you need to tackle this numerically ( FindRoot ) Commented Jun 6, 2014 at 19:50

Solutions in this example will all have x1 = (1+a-b)/2. You can use that to solve for x2:

Solve[((1 + a - b)/2)^2 + x2^2 == a^2, x2]

(* Out[46]= {{x2 -> -(1/2) Sqrt[-1 - 2 a + 3 a^2 + 2 b + 2 a b -
b^2]}, {x2 -> 1/2 Sqrt[-1 - 2 a + 3 a^2 + 2 b + 2 a b - b^2]}} *)


So the condition that there be real-valued solutions is that 1 - 2 a + 3 a^2 + 2 b + 2 a b - b^2>=0. You can check that instead of invoking FindInstance on the full system and it will be much faster.

• "in fact I need polynomial of degree 2" Commented Jun 9, 2014 at 5:39
• I can only work with the input I am provided. Feel free to post the actual problem of interest. Commented Jun 9, 2014 at 15:36
• Thank you, Daniel, I mean only that the question is more general, whether there is a way to find out solvability of arbitrary polynomial system over reals, not considering any concrete input. Commented Jun 9, 2014 at 15:51
• The answer is yes, clearly, and you are doing so in a way that is possibly optimal, lacking any information about the specifics of the system. That said, there may be cases where some a priori analysis can be done. Your examples, both the one posted and the one you actually want to tackle, probably both fall into this category. Reason being, most things stay the same between systems, only certain parameters get altered. In such cases there are sometimes preprocessing approaches that can improve speed for e.g. questions of existence of real solutions. Commented Jun 9, 2014 at 16:16