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, (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 and . In other words, we want to find non-trivial integer solutions to the equation when it has integer coefficients (clearly 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 to a normal form by two rational transformations of the variables. Lets assume that (We can always switch variables if ). With an easy simplification followed by clearing of the denominators , one can easily see that the transformation given by puts our original equation in the form where . Finally, the transformation puts the equation in the desired form, . Since finding integer solutions is equivalent to finding rational solutions and the transformations we used were rational, If an integer solution exist for we can conclude that the new form 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 to have a non-trivial integer solution. If has a non-trivial integer solution, we can use the inverse transformation to recover the solutions for . It turns out that the conditions for solubility of are,
1. All three variables, should not have the same sign.
2. The three quadratic congruence equations, 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 to the form (We can easily do this by multiplying entire equation by ). If then is a solution to our equation. If then is a solution to our equation. Otherwise we continue reducing and 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, which are co-prime to each other. Suppose we have found a non-trivial solution for the equation . We can always assume that by a switching of the variables. Then assuming and substituting in the original equation, one can find an expression for using and . So we can find parametrized solutions for by substituting the value of .
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.
 The algorithmic resolution of Diophantine equations, Nigel P. Smart, London Mathematical Society Student Texts 41, Cambridge University Press, Cambridge, 1998.
 Efficient Solution of Rational Conices, J. E. Cremona and D. Rusin, Mathematics of Computation, Volume 00, Number 0.
 L.J. Mordell, Diophantine Equations, Academic Press, 1969.