Elliptic Curves, commonly represented as +Ax+B (where A and B are constants) involve interactions between Geometry, Number Theory and Algebra. This project explores rational points on Elliptic Curves. By repeatedly applying geometric procedure (tangent-secant method) to a finite set of solutions, all of the possibly infinitely many rational solutions to an elliptic curve equation may be found. We will examine the relation between integer solutions of Diophantine Equations and rational points on elliptic curves. The simple looking Diophantine equation ++ = n (where n is a fixed positive integer) is infamous for having very large minimal solutions. This homogenous equation in three variables can be transformed to an elliptic curve in a two dimensional plane. Additionally, rational points on the elliptic curve lead us to least positive integer solutions of the Diophantine equation. We will be learning about solutions of ++ = 6 in this project.
2
y
3
x
a
b+c
b
a+c
c
a+b
a
b+c
b
a+c
c
a+b
Background
Background
Diophantine Equations
Diophantine Equations
A Diophantine equation refers to an equation usually expressed as a polynomial with integer coefficients involving two or more unknowns. The primary focus of these equations lies in finding solutions that are limited to integers. There are several functions in Mathematica for solving equations, such as FindInstance[ ], Solve[ ], Reduce[], and FindRoot[ ].
A few examples are as follows:
A few examples are as follows:
In[]:=
Solve[3*x+4*y==498,{x,y},Integers]
Out[]=
x,y
In[]:=
FindInstance[x^2+y^2-45==z^2,{x,y,z},Integers]
Out[]=
{{x-8,y-9,z-10}}
Diophantine Equations can be of any degree. In Mathematica, there exists a specific function called FrobeniusSolve[ ] to solve 1st degree/Linear Diophantine Equations. So, 12w+39x+25y+7z = 207 this LDE will be solved as,
In[]:=
FrobeniusSolve[{12,39,25,7},207]
Out[]=
{{0,0,1,26},{0,0,8,1},{0,1,0,24},{1,0,5,10},{1,1,4,8},{1,2,3,6},{1,3,2,4},{1,4,1,2},{1,5,0,0},{2,0,2,19},{2,1,1,17},{2,2,0,15},{3,0,6,3},{3,1,5,1},{4,0,3,12},{4,1,2,10},{4,2,1,8},{4,3,0,6},{5,0,0,21},{6,0,4,5},{6,1,3,3},{6,2,2,1},{7,0,1,14},{7,1,0,12},{9,0,2,7},{9,1,1,5},{9,2,0,3},{11,0,3,0},{12,0,0,9},{14,0,1,2},{14,1,0,0}}
checking one of the solutions,
In[]:=
ReplaceAll[12w+39x+25y+7z,Thread[{w,x,y,z}->{4,1,2,10}]]==207
Out[]=
True
The non trivial Minimal Solution of a Diophantine equation are the smallest positive integers that satisfy the equation.
ab+c+ba+c+ca+b = n where n is a fixed positive integer
a
b+c
b
a+c
c
a+b
This is the Diophantine equation that we study in this project. Though it may look simple, this type of Diophantine equation is notorious for having a large minimal solution. It is computationally difficult to find a solution by brute force. Let’s try for n = 6.
In[]:=
FindRoot++==n&&y^2==x^3+A*x^2+B*x,{x,y}
a
b+c
b
a+c
c
a+b
Out[]=
FindRoot++n&&+A+Bx,{x,y}
a
b+c
b
a+c
c
a+b
2
y
3
x
2
x
In[]:=
FindInstance++==6,{a,b,c},PositiveIntegers
a
b+c
b
a+c
c
a+b
Out[]=
FindInstance++6,{a,b,c},
c
a+b
b
a+c
a
b+c
>0
We will solve this using rational points on elliptic curves.
Elliptic Curves
Elliptic Curves
An elliptic curve is defined over a field K and describes points in , the Cartesian product of K with itself. The Weierstrass equation for an elliptic curve is defined as +Ax+B with some coefficients A and B in the field K.
2
K
2
y
3
x
In[]:=
Manipulate[ContourPlot[{y^2==x^3+a*x+b},{x,-30,70},{y,-200,200},Axes->True,PerformanceGoal->"Quality"],{a,-500,500},{b,-500,500}]
Out[]=
Slightly modified and more general equation of an elliptic curve,+A+Bx+C
2
y
3
x
2
x
Rational Points on Elliptic Curve
Rational Points on Elliptic Curve
A rational number is the quotient of two integers. A point (x, y) situated in a plane is considered a rational point if both its coordinates are rational numbers. Similarly, a line is classified as a rational line when its equation can be expressed using rational numbers. Elliptic curves have an intriguing combination of algebraic structure and geometric properties. When we consider the set of rational points on an elliptic curve, it forms a group, allowing us to perform arithmetic operations with these points. Three points on the elliptic curve “add up to zero” if there is a line that goes through all three of them at once, counting with intersection multiplicities. If a line intersects only two points on the curve, we say that they are additive inverses. And since there’s no other point in the plane that works, we create the point O at infinity. This definition gives us some operation, say +, on the points of an elliptic curve. This operation turns out to be associative.
Formally, group addition on an elliptic curve has the following properties:
1.
2.
3.
4.
Mordell Weil’s Theorem suggests that the group of rational points is always finitely generated (i.e., there always exists a finite set of group generators) for elliptic curves. In other words, there is a finite set of points,…,∈E(Q) ,
for some ,,…,∈Z
And t would be the rank of this Elliptic Curve.
Formally, group addition on an elliptic curve has the following properties:
1.
P+OO+PPfor all P∈E
2.
P+(-P)Ofor all P∈E
3.
P+(Q+R)(P+Q)+Rfor all P,Q,R∈E
4.
P+QQ+Pfor all P,Q∈E
Mordell Weil’s Theorem suggests that the group of rational points is always finitely generated (i.e., there always exists a finite set of group generators) for elliptic curves. In other words, there is a finite set of points
P
1
P
t
P++…+
n
1
P
1
n
2
P
2
n
t
P
t
n
1
n
2
n
t
And t would be the rank of this Elliptic Curve.
Group Addition (Geometric Approach)
Group Addition (Geometric Approach)
Geometrically, group addition on an elliptic curve is done by the tangent and secant method. Following are the steps to do so :
Step 1: Start with a given point L on a cubic curve.
Step 2: Draw the tangent line at point L on the curve.
Step 3: Find the third point of intersection between the tangent line and the curve.
Step 4: If two points, L and M, are given on the curve, draw a line passing through both points.
Step 5: Determine the third point of intersection (x,y) between the line and the curve.
Step 6: The reflection of that point with respect to the x axis, i.e., (x, -y), is L+M.
Note that this procedure can be applied to most choices of M and N since cubic curves typically intersect lines at exactly three points. Consider this procedure as a way to “add” two points on the curve and obtain a third point.Following calculates the slope and then the equation of the tangent at the initial points, which eventually leads us to the next points.
Step 1: Start with a given point L on a cubic curve.
Step 2: Draw the tangent line at point L on the curve.
Step 3: Find the third point of intersection between the tangent line and the curve.
Step 4: If two points, L and M, are given on the curve, draw a line passing through both points.
Step 5: Determine the third point of intersection (x,y) between the line and the curve.
Step 6: The reflection of that point with respect to the x axis, i.e., (x, -y), is L+M.
Note that this procedure can be applied to most choices of M and N since cubic curves typically intersect lines at exactly three points. Consider this procedure as a way to “add” two points on the curve and obtain a third point.Following calculates the slope and then the equation of the tangent at the initial points, which eventually leads us to the next points.
In[]:=
slope[{x1_,y1_},{x2_,y2_}]:=If[x1==x2&&y1==y2,(3(x1)^2+(-5))/(2*y2),(y2-y1)/(x2-x1)];intercept[{x1_,y1_},{x2_,y2_}]:=y1-slope[{x1,y1},{x2,y2}]*x1;nextpoint[{x1_,y1_},{x2_,y2_}]:={slope[{x1,y1},{x2,y2}]^2-x1-x2,-slope[{x1,y1},{x2,y2}]^3+slope[{x1,y1},{x2,y2}]*(x1+x2)-intercept[{x1,y1},{x2,y2}]}
Adding a point to itself
Adding a point to itself
The elliptic curve at hand is -5x+8. We will find the first rational point L on the curve by using FindInstance[ ].
2
y
3
x
In[]:=
L={x,y}/.First[FindInstance[y^2==x^3-5x+8,{x,y},Integers]]
Out[]=
{1,-2}
In[]:=
nextpoint[L,L](*thisis2L*)
Out[]=
-,
7
4
27
8
In[]:=
Show[ContourPlot[{y^2==x^3-5x+8},{x,-3,5},{y,-7,7},Epilog->{PointSize[0.020],Magenta,Point[NestList[nextpoint[#,L]&,L,1]],{Style[Text["L",L,{0,-1.5}],15,Black],Style[Text["2L",nextpoint[L,L],{0,-1.5}],15,Black]}}],Plot[slope[L,L]*x+intercept[L,L],{x,-3,3},PlotStyle->{Green}],Graphics[{Dashed,Line[{{-7/4,27/8},{-7/4,-27/8}}]}]]
Out[]=
Adding 2 points
Adding 2 points
In[]:=
M=nextpoint[L,L]
Out[]=
-,
7
4
27
8
In[]:=
nextpoint[L,M](*thisisM+L*)
Out[]=
,
553
121
11950
1331
Following is the list of L,2L,3L,4L.... till 8L
Using Rational Points on Elliptic Curve to Solve Diophantine Equation
Using Rational Points on Elliptic Curve to Solve Diophantine Equation
Turning Diophantine Equation to Elliptic curve (Algebraic Expressions)
Turning Diophantine Equation to Elliptic curve (Algebraic Expressions)
To get rid of the denominators and express the Diophantine equation in its cubic form, we will multiply out the denominators on both sides and Cancel out common terms.
Multiply through by the denominators and factor terms:
Elliptic Curve for Diophantine Equation with n = 6
Elliptic Curve for Diophantine Equation with n = 6
Determine the parameters A and B
Find a rational point on the elliptic curve
As mentioned before, this elliptic curve is of rank 1 (see reference 2). That is, we can generate all the rational points with P. So we will keep on producing 2P, 3P,... using the Tangent - Secant Method. And later, check if each one of those corresponds to a positive integer solution for the original Diophantine equation.
Computing Rational Points using Tangent - Secant Method
Computing Rational Points using Tangent - Secant Method
The following are generalised versions of the duplication formulae used in earlier sections.
Mapping rational Solutions of Elliptic Curves back to the Diophantine Equations
Mapping rational Solutions of Elliptic Curves back to the Diophantine Equations
Multiply the solution by the LCM of the denominators of the three fractions to obtain integer values:
Check that the solution works:
In the previous section we looked at the smallest positive integer solution, which appears at 11P. Here, we will hunt for all the positive solutions that the rational points yield until 700P (where P is (-8,104)). Since this requires calculating tangent and secant over and over again, it takes a while to generate 700 points. Following is the code one can use to generate the data.
If you wish to use the already generated data please use the following code. Since it increases the file size a lot, I have only included all the visualisation plots of this data.
Below is the plot telling at which multiple of P do we get all the 26 positive solutions.
The Plots below are of rational points that lead to the positive solutions. It is Fascinating to observe that all of them are on the first bulb like component of the elliptic curve.
If we take differences of the multiples i.e. after how many steps will the next positive solution occur ? It’s interesting to observe that most times it’s 22.
Solving for other values of n
Solving for other values of n
The functions defined in this notebook do not work for all n. They do work for n = 4 and 14, solutions are given below.
Minimal Solution is
And the maximum number of digits in minimal solution is
For 14, Maximum number of digits in the minimal solution is -
Concluding Remarks
Concluding Remarks
Keywords
Keywords
◼
Diophantine Equations
◼
Minimal Solution
◼
Elliptic Curves
◼
Rational Points
◼
Abelian Group
◼
Number Theory
Acknowledgement
Acknowledgement
I would like to thank my project mentors John McNally and Daniel Robinson for their support and discussions on practical implementations of many ideas. They helped make the Wolfram Summer School Experience rewarding for me. I would also like to thank Paul Abbott and Sotiris Michos for his insights on my project as well as Mads Bahrami, Emily Carter and Danielle Rommel Mayer for making the admission process and virtual school experience smooth. And, I would like to thank Stephan Wolfram and Jonathan Gorard for the project idea.
References
References
1
.Rational Points on Elliptic Curves by Joseph H. Silverman and John T. Tate
http://ndl.ethernet.edu.et/bitstream/123456789/53787/1/Joseph%20H.%20Silverman.pdf
http://ndl.ethernet.edu.et/bitstream/123456789/53787/1/Joseph%20H.%20Silverman.pdf
2
.An unusual cubic representation problem by Andrew Bremnera, Allan Macleod
http://publikacio.uni-eszterhazy.hu/2858/1/AMI_43_from29to41.pdf
http://publikacio.uni-eszterhazy.hu/2858/1/AMI_43_from29to41.pdf
3
.Problem Based Approach on Diophantine Equations by Titu Andreescu, Ion Cucurezeanu and Dorin Andrica
https://www.isinj.com/mt-usamo/An%20Introduction%20to%20Diophantine%20Equations%20-%20A%20Problem-Based%20Approach%20-%20Andreescu,%20Andrica%20and%20Cucurezeanu%20(Birk,%202011).pdf
https://www.isinj.com/mt-usamo/An%20Introduction%20to%20Diophantine%20Equations%20-%20A%20Problem-Based%20Approach%20-%20Andreescu,%20Andrica%20and%20Cucurezeanu%20(Birk,%202011).pdf
4
.Solving a Diophantine Equation with Elliptic Curves by Darren Yao
http://simonrs.com/eulercircle/crypto2019/darren-ec.pdf
http://simonrs.com/eulercircle/crypto2019/darren-ec.pdf
5
.Two more Representation Problems by Andrew Bremner and Richard K. Guy
http://simonrs.com/eulercircle/crypto2019/darren-ec.pdf
http://simonrs.com/eulercircle/crypto2019/darren-ec.pdf
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
From elliptic curves to Diophantine equations: a journey through rational points
by Aditi Kulkarni
Wolfram Community, STAFF PICKS, July 13, 2023
https://community.wolfram.com/groups/-/m/t/2959701
by Aditi Kulkarni
Wolfram Community, STAFF PICKS, July 13, 2023
https://community.wolfram.com/groups/-/m/t/2959701