Elliptic Curves

An elliptic curve (not to be confused with an ellipse) is a certain kind of polynomial equation which can usually be expressed in the form

$\displaystyle y^{2}=x^{3}+ax+b$

where $a$ and $b$ are numbers (more precisely, elements of some field) which satisfy the condition that the quantity

$\displaystyle 4a^{3}+27b^{2}$

is not equal to zero. This is not the most general form of an elliptic curve, as it will not hold for coefficients of “finite characteristic” equal to $2$ or $3$; however, for our present purposes, this definition will suffice.

Examples of elliptic curves are the following:

$\displaystyle y^{2}=x^{3}-x$

$\displaystyle y^{2}=x^{3}-x+1$

which, for real $x$ and $y$ may be graphed in the “Cartesian” or “$x$$y$” plane as follows (image courtesy of user YassineMrabet of Wikipedia):

This rather simple mathematical object has very interesting properties which make it a central object of study in many areas of modern mathematical research.

In this post we focus mainly on one of these many interesting properties, which is the following:

The points of an elliptic curve form a group.

A group is a set with a law of composition which is associative, and the set contains an “identity element” under this law of composition, and every element of this set has an “inverse” (see Groups). Now this law of composition applies whether the points of the elliptic curve have rational numbers, real numbers, or complex numbers for coordinates, and it is always given by the same formula. It is perhaps most visible if we consider real numbers, since in that case we can plot it on the $x$$y$ plane as we have done earlier. The law of composition is also often called the “tangent and chord” or “tangent and secant” construction.

We now expound on this construction. Given two points on the elliptic curve $P$ and $Q$ on the curve, we draw a line passing through both of them. In most cases, this line will pass through another point $R$ on the curve. Then we draw a vertical line that passes through the point $R$. This vertical line will pass through another point $R'$ on the curve. This gives us the law of composition of the points of the elliptic curve, and we write $P+Q=R'$. Here is an image courtesy of user SuperManu of Wikipedia:

The usual case that we have described is on the left; the other three images show other different cases where the line drawn does not necessarily go through three points. This happens, for example, when the line is tangent to the curve at some point $Q$, as in the second picture; in this case, we think of the line as passing through $Q$ twice. Therefore, when we compute $P+Q$, the third point is $Q$ itself, and it is through $Q$ that we draw our vertical line to locate $Q'$, which is equal to $P+Q$.

The second picture also shows another computation, that of $Q+Q$, or $2Q$. Again, since this necessitates taking a line that passes through the point $Q$ twice, this means that the line must be tangent to the elliptic curve at $Q$. The third point that it passes through is the point $P$, and we draw the vertical line through $P$ to find the point $P'$, which is equal to $2Q$.

Now we discuss the case described by the third picture, where the line going through the two points $P$ and $Q$ which we want to “add” is a vertical line. To explain what happens, we need the notion of a “point at infinity” (see Projective Geometry). We write the point at infinity as $0$, expressing the idea that it is the identity element of our group. We cannot find this point at infinity in the $x$$y$ plane, but we can think of it as the third point that the vertical line passes through aside from $P$ and $Q$. In this case, of course, there is no need to draw another vertical line – we simply write $P+Q=0$.

Finally we come to the case described by the fourth picture; this is simply a combination of the earlier cases we have described above. The vertical line is tangent to the curve at the point $P$, so we can think of it as passing through $P$ twice, and the third point is passes through is the point at infinity $0$, so we can write $2P=0$.

We will not prove explicitly that the points form a group under this law of composition, i.e. that the conditions for a set to form a group are satisfied by our procedure, but it is an interesting exercise to attempt to do so; readers may try it out for themselves or consult the references provided at the end of the post. It is worth mentioning that our group is also an abelian group, i.e. we have $P+Q=Q+P$, and hence we have written our law of composition “additively”.

Now, to make the group law apply even when $x$ and $y$ are not real numbers, we need to write this procedure algebraically. This is a very powerful approach, since this allows us to operate with mathematical concepts even when we cannot visualize them.

Let $x_{P}$ and $y_{P}$ be the $x$ and $y$ coordinates of a point $P$, and let $x_{Q}$ and $y_{Q}$ be the $x$ and $y$ coordinates of another point $Q$. Let

$\displaystyle m=\frac{y_{Q}-y_{P}}{x_{Q}-x_{P}}$

be the slope of the line that connects the points $P$ and $Q$. Then the point $P+Q$ has $x$ and $y$ coordinates given by the following formulas:

$\displaystyle x_{P+Q}=m^{2}-x_{P}-x_{Q}$

$\displaystyle y_{P+Q}=-y_{P}-m(x_{P+Q}-x_{P})$

In the case that $Q$ is the same point as $P$, then we define the slope of the tangent line to the elliptic curve at the point $P$ using the formula

$\displaystyle m=\frac{3x_{P}^{2}+a}{2y_{P}}$

where $a$ is the coefficient of $x$ in the formula, of the elliptic curve, i.e.

$\displaystyle y^{2}=x^{3}+ax+b$.

Then the $x$ and $y$ coordinates of the point $2P$ are given by the same formulas as above, appropriately modified to reflect the fact that now the points $P$ and $Q$ are the same:

$\displaystyle x_{2P}=m^{2}-2x_{P}$

$\displaystyle y_{2P}=-y_{P}-m(x_{2P}-x_{P})$

This covers the first two cases in the image above; for the third case, when $P$ and $Q$ are distinct points and $y_{P}=-y_{Q}$, we simply set $P+Q=0$. For the fourth case, when $P$ and $Q$ refer to the same point, and $y_{P}=0$, we set $2P=0$. The point at infinity itself can be treated as a mere point and play into our computations, by setting $P+0=P$, reflecting its role as the identity element of the group.

The group structure on the points of elliptic curves have practical applications in cryptography, which is the study of “encrypting” information so that it cannot be deciphered by parties other than the intended recipients, for example in military applications, or when performing financial transactions over the internet.

On the purely mathematical side, the study of the group structure is currently a very active field of research. An important theorem called the Mordell-Weil theorem states that even though there may be an infinite number of points whose coordinates are given by rational numbers (called rational points), these points may all be obtained by performing the “tangent and chord” or “tangent and secant” construction on a finite number of points. In more technical terms, the group of rational points on an elliptic curve is finitely generated.

There is a theorem concerning finitely generated abelian groups stating that any finitely generated abelian group $G$ is isomorphic to the direct sum of $r$ copies of the integers and a finite abelian group called the torsion subgroup of $G$. The number $r$ is called the rank of $G$. The famous Birch and Swinnerton-Dyer conjecture, which currently carries a million dollar prize for its proof (or disproof), concerns the rank of the finitely generated abelian group of rational points on an elliptic curve.

Another thing that we can do with elliptic curves is use them to obtain representations of Galois groups (see Galois Groups). A representation of a group $G$ on a vector space $V$ over a field $K$ is a homomorphism from $G$ to $GL(V)$, the group of bijective linear transformations of the vector space $V$ to itself. We know of course from Matrices that linear transformations of vector spaces can always be written as matrices (in our case the matrices must have nonzero determinant to ensure that the linear transformations are bijective). Representation theory allows us to study the objects of abstract algebra using the methods of linear algebra.

To any elliptic curve we can associate a certain algebraic number field (see Algebraic Numbers). The elements of these algebraic number fields are “generated” by the algebraic numbers that provide the coordinates of “$p$-torsion” points of the elliptic curve, i.e. those points $P$ for which $pP=0$ for some prime number $p$.

The set of $p$-torsion points of the elliptic curve is a $2$-dimensional vector space over the finite field $\mathbb{Z}/p\mathbb{Z}$ (see Modular Arithmetic and Quotient Sets), also written as $\mathbb{F}_{p}$. Among other things this means that we can choose two $p$-torsion points $P$ and $Q$ of the elliptic curve such that any other $p$-torsion point can be written as $aP+bQ$ for integers $a$ and $b$ between $0$ and $p-1$. When an element of the Galois group of the algebraic number field generated by the coordinates of the $p$-torsion points of the elliptic curve permutes the elements of the algebraic number field, it also permutes the $p$-torsion points of the elliptic curve. This permutation can then be represented by a $2\times 2$ matrix with coefficients in $\mathbb{F}_{p}$.

The connection between Galois groups and elliptic curves is a concept that is central to many developments and open problems in mathematics. It plays a part, for example in the proof of the famous problem called Fermat’s Last Theorem. It is also related to the open problem called the Kronecker Jugendtraum (which is German for Kronecker’s Childhood Dream, and named after the mathematician Leopold Kronecker), also known as Hilbert’s Twelfth Problem, which seeks a procedure for obtaining all field extensions of algebraic number fields whose Galois group is an abelian group. This problem has been solved only in the special case of imaginary quadratic fields, and the solution involves special kinds of “symmetries” of elliptic curves called complex multiplication (not to be confused with the multiplication of complex numbers). David Hilbert, who is one of the most revered mathematicians in history, is said to have referred to the theory of complex multiplication as “…not only the most beautiful part of mathematics but of all science.”

References:

Elliptic Curve on Wikipedia

Mordell-Weil Theorem on Wikipedia

Birch and Swinnerton-Dyer Conjecture on Wikipedia

Wiles’ Proof of Fermat’s Last Theorem on Wikipedia

Hilbert’s Twelfth Problem on Wikipedia

Complex Multiplication on Wikipedia

Image by User YassineMrabet of Wikipedia

Image by User SuperManu of Wikipedia

Fearless Symmetry: Exposing the Hidden Patterns of Numbers by Avner Ash and Robert Gross

Elliptic Tales: Curves, Counting, and Number Theory by Avner Ash and Robert Gross

Rational Points on Elliptic Curves by Joseph H. Silverman