Solving Ternary Quadratic forms by descent method

Now SymPy can solve Ternary Quadratic forms !!!! I thought of adopting a new style for giving more details on this amazing news, So Let’s try a Q&A approach and see how it goes.

Q1. What is a “Ternary Quadratic form”?

A ternary quadratic form is an equation of the form, Q(x, y, z) \equiv Ax^2 + Bxy + Cxz + Dy^2 + Eyz + Fz^2 = 0 (Yes, It’s a little bit odd representation with square terms scattered but you will see later why this is a better representation). One important thing worth observing is that the degree of each term is precisely two. This makes it a lot easier to solve the equation and moreover, it makes finding integer solutions to the equation equivalent to finding the rational solutions. We are particularly interested in the case where A, B, C, D, E, F, x, y, z \in \mathbb{Z} and  (x, y, z) \neq (0, 0, 0). In other words, we want to find non-trivial integer solutions to the equation when it has integer coefficients (clearly (x, y, z) = (0, 0, 0) is always a solution to this equation so we call it the `trivial` solution).

Q2. Can we make the equation more simpler to deal with?

Yes, It turns out that we can. We can convert Q to a normal form Q' \equiv ax^2 + by^2 + cz^2 = 0 by two rational transformations of the variables. Lets assume that A \neq 0(We can always switch variables if A = 0).  With an easy simplification followed by clearing of the denominators , one can easily see that the transformation given by x \rightarrow x - (By + Cz)/2A puts our original equation in the form A'x ^2 + D'y^ 2 + E'yz + F'z^ 2= 0 where A', D', E' , F' \in \mathbb{Z}. Finally,  the transformation y \rightarrow y - E'z/2D' puts the equation in the desired form, ax^2 + by^2 + cz^2 = 0. Since finding integer solutions is equivalent to finding rational solutions and the transformations we used were rational, If an integer solution exist for Q we can conclude that the new form Q' should also have an integer solution.

Q3. What are the required conditions to have a non-trivial solution(s)?

It’s sufficient to consider the conditions on  Q' to have a non-trivial integer solution. If Q' has a non-trivial integer solution, we can use the inverse transformation to recover the solutions for Q. It turns out that the conditions for solubility of Q' are,
1. All three variables, a, b, c should not have the same sign.
2. The three quadratic congruence equations, x^2 + bc \equiv 0 \ (mod \ a), x^2 + ca \equiv 0 \ (mod \ b), x^2 + ab \equiv 0 \ (mod \ c) should be solvable.

You can find the proofs for  the sufficiency of these conditions in the references. It is also a proven fact that If one non-trivial solution exist for one of the equations, there will be infinitely many non-trivial solutions.

Q4. What are the algorithms that can be used ?

There are quite a few algorithms which can be used to tackle down a non-trivial solution. There is a method which uses sieving and another one based on quadratic number fields. But the descent method due to Lagrange beats the above methods when it comes to performance. The idea is like this. Suppose there is a solution, then under some conditions we can deduce that an even smaller solution should exist. We continue making the solution smaller and smaller until we find an equation which has a solution we can easily spot.  First we convert ax^2 + by^2 + cz^2 = 0 to the form w^2 = Ax^2 + By^2 (We can easily do this by multiplying entire equation by -c). If A = 1 then (x, y, w) = (1, 0, 1) is a solution to our equation. If B = 1 then (x, y, z) = (0, 1, 1) is a solution to our equation. Otherwise we continue reducing A and B until we arrive at a situation like above.

Q5. How can one find all the non-trivial solutions?

Well, All the non-trivial solutions can be represented using two parameters, p, q which are co-prime to each other. Suppose we have found a non-trivial solution (x_{0}, y_{0}, z_{0}) for the equation Q(x, y, z) = 0. We can always assume that x_{0} \neq 0 by a switching of the variables. Then assuming (x, y, z) = (x_{0}r, y_{0}r + p, z_{0}r + q) and substituting in the original equation, one can find an expression for r using p and q. So we can find parametrized solutions for (x, y, z) by substituting the value of r.

Q6. Any Improvements to current methodology?

Yes, An efficient algorithm for solving the quadratic congruence should be implemented. Also, there is an algorithm in MAGMA which currently solves this kind of equations. I plan to implement that also so that I can verify my results and if it is faster than the descent method, replace the descent method with it.

And a special thank should go to Mario for helping me out with the bugs in my code.

References

[1] The algorithmic resolution of Diophantine equations, Nigel P. Smart, London Mathematical Society Student Texts 41, Cambridge University Press, Cambridge, 1998.
[2] Efficient Solution of Rational Conices, J. E. Cremona and D. Rusin, Mathematics of Computation, Volume 00, Number 0.
[3] L.J. Mordell, Diophantine Equations, Academic Press, 1969.

Advertisements

8 Comments

  1. How do you switch variables if A = D = F = 0?

    • Sorry Aaron, I just saw your comments. If A = D = F = 0, there is no need to change the variables since our equation is of the form B*x*y + C*y*z + E*z*x = 0, we can output any of the solution of the form (0, 0, t), (0, t, 0), (t, 0, 0). In DE module, I still didn’t finalize what is to be output

  2. Another issue, is D’ guaranteed to not be 0 given that A != 0?

    • If D is zero, We don’t need to perform the transformation to eliminate y

  3. So do you actually need to solve the quadratic congruence or do you just need to check if a solution exists or not?

    • To test solubility, there is no need to solve quadratic congruence but solving the ternary quadratic normal equations requires solving quadratic congruence (In the descent method).

  4. There the solution of this equation.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: