# 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 for$n$. 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