15
$\begingroup$

I was watching a video where a problem in Galois theory was posed such that it became necessary to tell if a certain element was a perfect square in a finite field extension of the rationals. By writing a general element in terms of its $\mathbb{Q}$-basis and squaring it, the result was a system of quadratic equations. In particular, it was system of three non-homogeneous equations in three unknowns.

The video deferred the solution to a computer algebra system, which felt unsatisfying. I was wondering what techniques would be useful for solving general equations of this kind.

My only thought was that Groebner bases might be useful (and I'm sure that's how the computer algebra system solves it). But I don't know much about them, and I wonder how amenable the Buchberger algorithm is to solving it by hand.

$\endgroup$
6
  • 7
    $\begingroup$ let us see your system! $\endgroup$ Commented Jan 29, 2017 at 9:44
  • 2
    $\begingroup$ It's the system that you get the following way. Take the polynomial t^3 - 3t - 1. Freely adjoin a root of this polynomial. Then show that when you divide out the root from the polynomial and show the remaining quadratic is reducible by showing that its discriminant is a perfect square in the field. $\endgroup$ Commented Jan 29, 2017 at 11:20
  • 1
    $\begingroup$ I don't see how in a splitting field of a cubic a problem involving squaring an element can give rise to a system of three quadratic equations $\endgroup$ Commented Feb 15, 2017 at 19:58
  • $\begingroup$ It's not especially relevant to the question. But ultimately you end up needing to know if some element in the extension is a perfect square. Take an arbitrary element written in terms of some basis and square it, and set it equal to the element you're trying to root. The result is quadratic in the arbitrary coefficients you started with. $\endgroup$ Commented Feb 16, 2017 at 20:12
  • $\begingroup$ Is there a link to the video? $\endgroup$ Commented Feb 17, 2017 at 0:48

3 Answers 3

12
$\begingroup$

It seems systems like these can be solved with the use of resultants.

Say we have three polynomials $f(x, y, z) = g(x, y, z) = h(x, y, z) = 0$ in three variables.

We can treat each as a polynomial in the ring $R[x,y][z]$. We can use a resultant to form a new, simpler system $F(x, y) = Res(f, g) = 0$ and $G(x, y) = Res(g, h) = 0$. This effectively eliminates the $z$ variable from our system.

Doing this again, we get a final polynomial $R(x) = Res(F, G)$ (taken with respect to $y$ this time over the ring $R[x]$).

We solve $R(x) = 0$ to get all possible values of $x$.

Then, we go through each of these possible values and plug them into the system $F(x, y) = G(x, y) = 0$. This gives us the corresponding values for $y$.

And then, with values for $x$ and $y$ in hand, we solve the original system $f(x, y, z) = g(x, y, z) = h(x, y, z) = 0$ to get the corresponding $z$ values.

$\endgroup$
2
  • 3
    $\begingroup$ If I understand this method correctly, $R(x)$ will be a higher degree polynomial which can't necessarily be solved exactly. $\endgroup$ Commented Jan 23, 2022 at 19:11
  • 1
    $\begingroup$ Although now that I think about it, there is no way around this. Any polynomial system can be turned into a quadratic system. $\endgroup$ Commented Jan 23, 2022 at 19:15
9
$\begingroup$

Consider a quadratic equation of form $ax^2 +by^2 +cxy+dx+ey+f=0$. The polynomial can be decomposed into two factors (polynomial) such as $ax+By+C$ and $dx+Ey+F$. Therefore for a system of two quadratic equations we get four polynomials of first degree (i.e linear equations). The combination of these four equations give four systems of equations where the solutions satisfy the initial quadratic system of equations; look at this example: Solve following system of quadratic equations:

$$\begin{cases} 2x^2+2y^2 +5xy-x+y-1=0 \\ -3x^2-2y^2+5xy+10x-8y-8=0 \\ \end{cases} $$ The first equation can be written as:

$$(x+2y-1)(2x+y+1)=0$$ and the second one can be written as:

$$(-x+y+2)(3x-2y-4)=0$$

We get four systems of equations, which give following solutions: $$\begin{cases} x+2y-1=0 \\ -x+y+2=0 \\ \end{cases} $$ give $x=5/3$ and $y=-1/3$

$$\begin{cases} x+2y-1=0 \\ 3x-2y-4=0 \\ \end{cases} $$ give $x=5/4$ and $y = -1/8$

$$\begin{cases} 2x+y+1=0 \\ -x+y+2=0 \\ \end{cases} $$ give $x=1/3$ and $y=-5/3$ and

$$\begin{cases} 2x+y+1=0 \\ 3x -2y-4=0 \\ \end{cases} $$
give $x=2/7$ and $y=-11/7$

These are the solutions of the quadratic system of equations.

$\endgroup$
1
  • 13
    $\begingroup$ This is a good thing to keep in mind, but it looks like it only applies when the quadratics are all reducible.... which is a very special condition. $\endgroup$ Commented Feb 17, 2017 at 12:10
0
$\begingroup$

This answers only the question of the OP restricted to two quadratic equations with two variables. For this case the calculation is rather straightforward.

We want to calculate the solution of the following system of equations:

$$C\,y^2+B\,x\,y+E\,y+A\,x^2+D\,x+F=0 \tag{1.1}$$ $$c\,y^2+b\,x\,y+e\,y+a\,x^2+d\,x+f=0 \tag{2.1}$$

This can be written as

$$C\,y^2+p_{1}\left(x , 1\right)\,y+p_{2}\left(x , 2\right)=0 \tag{1.2}$$ $$c\,y^2+p_{3}\left(x , 1\right)\,y+p_{4}\left(x , 2\right)=0 \tag{2.2}$$

where $p_i(x,n)$ is a polynomial of variable $x$ an degree at most $n$. We can calculate $y$ from $(1.2)$:

$$\left[ y=-\left({{\sqrt{p_{2}\left(x , 1\right)^2-4\,C\,p_{1}\left( x , 2\right)}+p_{2}\left(x , 1\right)}\over{2\,C}}\right) ,\\ y={{ \sqrt{p_{2}\left(x , 1\right)^2-4\,C\,p_{1}\left(x , 2\right)}-p_{2} \left(x , 1\right)}\over{2\,C}} \right] $$

so we have

$$y=s\,\sqrt{p_{5}\left(x , 2\right)}+p_{6}\left(x , 1\right)$$

where $s \in \{-1,1\}$.

Now we substitute $y$ in $(2.2)$ and get

$$p_{3}\left(x , 1\right)\,\left(s\,\sqrt{p_{5}\left(x , 2\right)}+ p_{6}\left(x , 1\right)\right)+c\,\left(s\,\sqrt{p_{5}\left(x , 2 \right)}+p_{6}\left(x , 1\right)\right)^2+p_{4}\left(x , 2\right)=0$$

We bring all square-root-terms to the left side of the equation and combine the polynomials to polynomials $p_7$ and $p_8$ and get $$p_{7}\left(x , 2\right)=p_{8}\left(x , 1\right)\,s\sqrt{p_{5}\left(x , 2\right)}$$

Now we square the equation to get rid of the root and finally have a polynomial equation of $x$ of maximum degree $4$. The other solution $y$ doen not contribute anything new because when squaring $s$ becomes $1$.

$\endgroup$

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.