GSoC 2013 Application Thilina Rathnayake: Diophantine Equations Module - sympy/sympy GitHub Wiki

Name : Thilina Rathnayake

University : University of Moratuwa, Sri Lanka.

Email : [email protected]

Github : thilinarmtb

IRC : thilinarmtb on freenode

I am a 2nd year undergraduate in Computer Science and Engineering

Department. My semester 4 examinations are about to start in mid May and end

on the first week in June. During this period, amount of time I am able to spend

on this project will be limited. With the end of the examinations I will be able to

spend most of my time (Nearly 12-16 hrs per day) on this project. I like to continue

contributing to Sympy on this project and other interesting projects.

I have been programming for about five years now. I started with C, then learned

C++, Java, C# and finally python. I have also done a wee bit of web programming

with PHP. At present, I heavily use C++ and python. Eclipse, CodeBlocks, and

IDLE are my favourite IDEs and used them under Ubuntu in my earlier projects,

but about a year ago, I switched to Fedora. I occasionally run Windows on

Oracle VM to do C# programming. As for my programming experience, I have

created an Apparel Management system with Java for the OOSD (Object

Oriented Software Design) module and a GIS (Geographical Information System)

for my OOP module. I have competed in IEEEXtreme competition and used C++

and Python in solving problems.

I have been using python for problem solving. I also use scikit-learn for kaggle

competitions with numpy and scipy. My favourite feature in python is that it's

simplicity. Anyone could learn python easily and quickly. I love the map()

function, it makes code shorter and sweeter. I like solve_congruence function in

Sympy.

Ex: To find the number which is 2 mod 3, 3 mod 4 and 4 mod 5,

from sympy.ntheory.modular import solve_congruence

solve_congruence((2, 3), (3, 4), (4, 5))

I have used git to push my patch for issue 3562. (Still not merged)

I would like to work on creating a Diophantine Equation (DE) module for Sympy. Wolfram Alpha currently solves commonly found DEs. DEs I mentioned under deliverables cover almost all the equations wolfram alpha currently solves. I participated in IMO(International Mathematical Olympiad) 2007 and have an honourable mention. I was introduced to DE in the training sessions for IMO and I have always found them interesting ever since. I love number theory and as a consequence, DEs. I think I have an enough mathematical background to succeed with this project.

A module for solving DEs will be implemented. As a start I hope to solve the following

5 classical DEs which are found most frequently. Module will be implemented very

similar to the ODE module so that adding solutions to the new types of equations and

updating/ improving solutions will be easy.

1. a1x1 + a2x2 + a3x3 + ...+ anxn = b (Linear diophantine equation)

Here a1, a2, ... an and b are constants. This solvable if gcd(a1, a2, …, an) divides b.

Here gcd stands for greatest common divisor. Solving this equation means expressing any two variables using other variables and an arbitrary integer m. i.e. solution is given by,

x1 = x1, x2 = x2, ... xn-2 = xn-2, xn-1 = f( x1, x2, ... xn-2, m), xn = g( x1, x2, ... xn-2, m)

Here, f and g are functions to be determined.

2. x12 + x22 + x32 + ... xn2 = k

Here k is an non negative integer. There will be a number of solutions depending

on n and k. Solving this means assigning constants b1, b2, ... bn to xi's

respectively.

3. x12 + x22 + x32 + ... xn2 = xn+1**2 (Extension of Pythogorean equation)

Solving this is pretty standard. All the solutions can be given as,

x1 = m12 + m22 + m32 + ... mn-12- mn**2

x2 = 2m1mn

:

:

xn = 2mn-1mn

xn+1 = m12 + m22 + m32 + ... mn-12+ mn**2

where mi ’s are arbitrary integers.

4. x2 + axy + y2 = z**2

Here a is a constant. If z is a variable, a general solution can be given to this equation

using a and three arbitrary integers. All the solutions can be given as two symmetrical families,

x = k(an2 - 2mn) x = k(m2 - n**2)

y = k(m2 - n2) y = k(an**2 - 2mn)

z = k(amn- m2 -n2) z = k(amn- m2 -n2)

where k, m, n are arbitrary integers. If z is a constant, actual solutions can be given

(If they exist).

5. x2 - Dy2 = 1 (Simplified Pell's equation)

Here D is a non square positive integer. General Pell equation x2 - Dy2 = m is Harder

to solve.

Let ( x0, y0) be the fundamental solution to the Pell’s equation above (minimal solution

not equal to (1, 0), We can prove that such a solution exist). Then all the other

solutions given by ( xn, yn)n>=1

xn+1 = x0xn + Dy0yn, yn+1 = y0xn + x0yn, x1 = x0, y1 = y0

We can verify that these indeed satisfy Pell’s equation using induction. Assume that

( xn, yn) is a solution then,

xn+12 - Dyn+12 = (x0xn + Dy0yn)**2- D(y0xn + x0yn)**2

               = (x0**2 - Dy0**2) (xn**2 - Dyn**2) (Expanding and simplifying)

               = 1. 1

               = 1

So (xn+1, yn+1) Satisfy Pell’s equation. Proof is complete by induction. Also it has been

proved that all the solutions to the Pell equation are of the above form. Further it can

be shown that,

xn-1 + sqrt(D)yn-1 = (x0 + sqrt(D)y0)**n for n >= 1.

This gives a easy method to find xn and yn. Solutions for x2 - Dy2 = -1 can also be given

with slight modifications to the above method.

The equation ax2 - by2 = 1 can be solved in certain instances given that the product

ab is not a perfect square. The Pell’s resolvent of above equation is u2 - abv2 = 1

if A, B be first equation’s smallest solutions then the general solution can be given by,

xn = Aun + bBvn, yn = Bun + aAvn where n >= 0.

Sympy’s ODE module gives a huge insight on how the solving process for the

DEs should be implemented. The method given there is almost identical to this

particular scenario except for the fact that we are dealing with DE instead of ODEs.

Here is a rough description of what I am going to do.

Implement a function, diop_solve() which would take a diophantine equation

in the form f(x, y, z, ..) = 0 and solve it. Solution will be based on the type of the DE

passed to the function. To determine the type of a DE, another function classify_diop()

will be implemented. classify_diop() will return one of the elements in “alltypes” list

which contains the currently solved equation types. The return value of classify_diop()

will be used to call the function which can solve the DEs of that type.

Below is a very simplified pseudo code for the above procedure.

alltypes = (“linear”, “pell”, “pythogorean”, …..)

diop_solve(eq):

type = classify_diop(eq)

# various types of validation will be done here

solv_func = globals()[ ‘diop_’ + type]

solv_func(eq)

classify_diop(eq):

“””

Matching “eq” with currently solved equations takes place here.

This will return the type of DE and information that was found

during matching which will be helpful in solving equation.

eg: linear, quadratic, pell … etc.

“””

diop_linear(eq):

“”” This will solve linear DEs. “””

diop_pell(eq):

“”” This will solve Pell’s equations. “””

:

:

And so on.

Here diop_solve(), classify_diop() and other functions are demonstrated as taking one

argument although they would take multiple arguments as in ODE module.

Adding a solution to a new type of equation can also be implemented as in ODE module.

Roughly, a type name to that particular type of equation must be selected and added to the

“alltype” list. Then add an expression to match that type of equations in classify_diop().

Next the solution should be implemented in a function, diop_().

I hope to follow the following schedule loosely.

Week 1 - 4:  Work on classification function and helper functions
that have to be implemented. Write Matching expressions for the equation types.

Week 5: Solve the General Pythogorean equation. (3rd on the Deliverables)

Week 6 - 7: Solve the Quadratic Diophantine equation (4th on the Deliverables)

Week 8 - 9: Solve the General Pythogorean equation with a constant on the right. 

(2nd on the Deliverables)

Week 10 - 11: Solve linear Diophantine equation.

Week 12 - 13: Solve Pell’s Equation.

Week 14: Solving equations which can be reduced to Pell’s equation.

Here the first 4 weeks are devoted to implement the common functionalities required by all

the equations. Tests will be done in parallel with the coding of the project.

[1] Andreescu, Titu. Andrica, Dorin. Cucurezeanu, Ion. An Introduction to Diophantine Equations

[2] Wolfram Mathworld. Diophantine Equations [online]. Available: http://mathworld.wolfram.com/DiophantineEquation.html

[3] Wikipedia. Diophantine Equation [online]. Available: http://en.wikipedia.org/wiki/Diophantine_equation

[4] Sympy 0.7.2 Documentation, ODE [online]. Available: http://docs.sympy.org/0.7.2/modules/solvers/ode.html

[5] Wolfram Mathworld. Pell Equation [online]. Available: http://mathworld.wolfram.com/PellEquation.html