Status of the Diophantine Module

Hi All,

I am really pleased to say that my work (proposed) with Diophantine equation is coming to an end. I have implemented all the deliverables in my project report. When the current PR gets merged into the master, I can start pushing the rest of my work. I also hope to improve the documentation during the weekend and get them in quickly. Ondrej is currently reviewing the PR. I invite all of you to go through the work and give your feedback. I am really thankful to Aaron, Pernici, Stephen and Julien for the support given so far. First of all let me give you a rough idea about the work currently not in Github.

General Pythagorean equation

A general Pythagorean equation is an equation of the form x_{1}^2 + x_{2}^2 + . . . + x_{k}^2 = x_{k+1}^2. The solutions for the equation can be given by using k parameters like below,

x_{1} = m_{1}^2 + m_{2}^2 + . . . + m_{k-1}^2 - m_{k}^2
x_{2} = 2m_{1}m_{k}
.
.
x_{k} = 2m_{k-1}m_{k}x_{k +1} = m_{1}^2 + m_{2}^2 + . . . + m_{k-1}^2 + m_{k}^2

I implemented solutions for slightly more  general equation a_{1}^2x_{1}^2 + a_{2}^2x_{2}^2 + . . . + a_{k}^2x_{k}^2 = a_{k+1}^2x_{k+1}^2. Solutions for this equation can be constructed from the solutions of the former equation, multiplying each solution x_{i} of it by \frac{lcm(a_{1}, a_{2}, . . . a_{n})}{a_{i}}.

General sum of n squares

I also implemented solutions for x_{i}^2 + x_{2}^2 + . . . + x_{n}^2 = k where k is an integer. It is obvious that equation is solvable only when k \geq 0.

Lagrange’s four square theorem states\textsuperscript{[1]} that every non-negative number can be expressed as a sum of four squares. It is also known that every integer not in the the form 4^k(8m + 7) can be expressed as a sum of three squares\textsuperscript{[2]} where m, n are non-negative integers.  Also any integer which doesn’t contain, in it’s canonical representation, odd powers of a prime of the form 4m + 3 can be expressed as a sum of two squares\textsuperscript{[3]}. For example, N = 2^2.5^3.11^2.3^3 can’t be expressed as a sum of two squares since it contains and odd power of 3, which is a prime of the form 4m+3. But we can express N = 2^2.5^3. 11^2.3^4 as a sum of two squares.

Also, there is an interesting identity, found by Euler, known as Euler’s four square identity which can be stated as,

(a_1^2+a_2^2+a_3^2+a_4^2)(b_1^2+b_2^2+b_3^2+b_4^2) = (a_1 b_1 - a_2 b_2 - a_3 b_3 - a_4 b_4)^2 + (a_1 b_2 + a_2 b_1 + a_3 b_4 - a_4 b_3)^2 + (a_1 b_3 - a_2 b_4 + a_3 b_1 + a_4 b_2)^2 + (a_1 b_4 + a_2 b_3 - a_3 b_2 + a_4 b_1)^2.

So, if we can represent each prime divisor of a number N as a sum of four squares, we can then use this identity to construct such a representation forn. This is the idea behind my implementation of representing number as a sum of four squares. When we know how to do this, we have several approaches for representing a given non-negative integer k as a sum of n squares. Most obvious thing to do is, represent k as a sum of four squares and set other n -4 variables to zero. We can also partition k into approximately n/4 groups and represent each as a sum of four squares and later combine those results. I still haven’t decided on how to do this, I would like to know the ideas of the community.  I used a slightly modified version of  the algorithm found in\textsuperscript{[5]}.  I’ll describe the algorithm in my next blog post.

Apart from that, I did a lot of bug fixing and reviewed Pernici’s Pull request. My tests are now 2x faster after using his functions. A huge thank should go to Pernici for doing a great Job with solving quadratic congruences.

References

[1] Lagrange’s four square theorem, [online], Available: http://en.wikipedia.org/wiki/Lagrange%27s_four-square_theorem
[2] Integer as a sum of three squares, [online], Available: http://www.proofwiki.org/wiki/Integer_as_Sum_of_Three_Squares
[3] Sum of Squares, [online], Available: http://mathworld.wolfram.com/SumofSquaresFunction.html
[4] Euler’s four square identity, [online], Available: http://en.wikipedia.org/wiki/Euler%27s_four-square_identity
[5] http://www.schorn.ch/howto.html

Advertisements

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: