From Euclid To Gauss via Pell

While the fourth week of GSoC is coming to an end, I managed to finish two of the five deliverables of my project proposal. So the fourth week is more of a transition week for me as I had to correct few bugs associated with current implementation of QDEs (Quadratic Diophantine Equation) and LDEs (Linear Diophantine Equation) and find new resources for the future work, solving Ternary Quadratic Forms.

In QDE I had a little problem dealing with the case where B**2 - 4*A*C is a perfect square. General solution procedure for this case is to use a transformation which converts this case to the Simple Hyperbolic case which I had solved previously. Then the original solutions can be recovered from the solutions of the transformed equation using two divisible criteria which should be satisfied to honour the transformation. Things went wrong when the solutions of the transformed equation involved parameters because I had to check finitely many equivalence classes with respect to modulo 4*A*sqrt(B**2 - 4*A*C in that case and find whether there are any classes satisfying the criteria and find a nice representation for the solutions if at least one such class exist. I found this hard going but finally managed to implement it. Work related to the QDEs are almost finished and there are a few optimization steps to be carried out. For example I use brute force to solve the congruence equation x**2 = D (mod a) and there is an algorithm which is more efficient. I hope to implement it since this equation will come up in my future work too. Several extensions can also be carried out like finding the rational solutions satisfying a given QDE and implementing other algorithms like the cyclic method which also solves QDEs.

I also corrected an error I had done in linear Diophantine equations due to which the solutions returned by the solver were only a subset of the exact solutions. I corrected this and checked the results with the Wolfram Alpha. Now, the solutions returned by the solver can be made identical to that returned by the Wolfram Alpha by a single shift or by inverting the parameter. Since the parameters returned in solutions for linear Diophantine equations has no boundary conditions and can be an any integer, this does not make the two solution sets different.

During the week, I also studied the ternary quadratic forms, on which I plan to work in the weeks to come. A ternary quadratic form is a homogeneous equation in three variables and having a degree two, i.e. a equation of the form Ax**2 + By**2 + Cz**2 + Dyz + Exz + Fxy = 0. I found a good resource on this, “Algorithmic resolution of Diophantine equations” by Nigel P. Smart.


Leave a Reply

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

You are commenting using your 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: