Elliptic Curves: The Basics

Working over the rationals (or more precisely any field with characteristic 0) an elliptic curve is a curve given the equation

such that the discriminant, which is 4A3 + 27B2, is non-zero. Equivalently, the polynomial on the right hand side has distinct roots, ensuring that the curve is non-singular. Though we restrict our attention to these non-singular curves we note that if the right hand side is a cubic polynomial, there are only two types of singular curves, corresponding to whether there is a double root (node) or triple root (cusp).

Source: Wolfram Mathworld

Point at Infinity

The point at infinity is an important point that always lies on an elliptic curve. For those who have studied algebraic geometry this is a familiar concept and comes from defining a projective closure of the equation defining the elliptic curve. However, informally it can be described as an idealised limiting point at the ‘end’ of each line.

If you imagine a vertical straight line, which intersects the elliptic curve at most two times.

The point at infinity is the point at which the two ends of this vertical line ‘meet’.

The reason that elliptic curves are amazing objects is because we can use geometry to make the points on the curve a group. Therefore we can use tools from algebraic number theory to study them.

Making Points on an Elliptic Curve into a Group

This is done using the chord and tangent process:

We denote the point at infinity on an elliptic curve E over Q as OE. E meets each line in 3 points, counted with multiplicity. Given two points on E, say P and Q, let R be the third point of intersection of PQ and E. Then P ⊕ Q is the third point of intersection of OER (vertical line through R) and E.

Source: jeremykun.com

If P = Q we take the tangent at P instead of the line PQ.

Then E with the group law on points defined above, denoted by (E, ⊕), is an abelian group:

  • The fact that is abelian is clear by construction
  • Identity: OE – this is why the point at infinity is such an important point and exists on all elliptic curves.
  • Inverses: Given a point P, let S be the point of intersection of the tangent at OE and E. Then let Q be the intersection of PS and E. Then the inverse of P is defined to be Q. Note that if OE is a point of inflection (point of multiplicity 3) then S = OE in the above.
  • Associativity: This is much harder to prove. It can be done by identifying (E, ⊕) with a subgroup of the Picard Group, which related to something called divisors.

Divisors are a tool for keeping track of poles and zeroes. For example, suppose a function g has a zero at a point P of order 3, and a pole at another point Q of order 2, and a pole at O of order 1 (note the number of zeroes and poles are equal, as they must be for a function). Then using divisors, we can say all this concisely as follows:

div g=3P−2Q−O

More precisely, we can define a divisor D to be a ‘formal sum’ of points on E (meaning that we write a sum of points using a + symbol but no actual operation is defined), say

Then the degree of a divisor is the sum of the coefficients.

This set of divisors forms a group, Div(E), generated by the points on E. Immediately we can identify a subgroup of Div(E), namely the divisors of degree zero denoted Div0(E).

We can also define an equivalence relation ~ on divisors: D1, D2 ∈ Div(E) are linearly equivalent, written D1 ~ D2, if exists an f such that div(f) = D1 – D2.

We can now introduce the Picard Group. It is a subgroup of Div(E), defined by quotienting out by this equivalence relation

A subgroup of the Picard group is given by

We’re now ready to go back to talking about elliptic curves. The point of this discussion is that we know (Pic0(E), +) is a group which has the associative property. Furthermore, we can show that we have a bijection between (E, ⊕) and (Pic0(E), +) that preserves the group structure i.e. we have an isomorphism of groups. So, using this isomorphism we can identify the two groups and deduce that (E, ⊕) is also associative.

Consequence

Say we started looking at points defined over Q (denoted by E(Q)). A natural question is to ask how we know that the addition or inverses of these points remains in Q?

We defined the group law by looking at the intersections of lines and curves. So, working through the algebra, we can get explicit equations for the addition of points and inverses. For example if we have an elliptic curve E over Q and a point P = (x,y) in E(Q), then -P = (x, -y).

These explicit equations are useful because they tell us that the points do indeed remain defined over Q. More precisely, we find that (E(Q), ⊕) is a subgroup of (E, ⊕):

  • The identity OE is in E(Q) by definition
  • (E(Q), ⊕) is closed under addition and has inverses by the explicit formulae
  • Associativity and commutativity is inherited from (E, ⊕).

Note: This in fact holds for any field K, not just Q, but we must be a bit more careful, as the elliptic curve may not be expressible in the nice form y2 = x3 + Ax + B so the formulae are a bit messier. The reason why this is important is that we often want to consider elliptic curves over finite fields, something I will explore in future posts.

M x

4: An Example

In this blog post I will show you how you can use the tools developed in parts 1, 2 and 3 to solve a problem in number theory.

Determine all the integer solutions of the equations x2 − 3y2 = m for m = −1 and 13.

Noting that x2 − 3y2 = (x – √3y)(x + √3), first we find the fundamental unit, e = a + b√3, of the number field Q(√3):

For b = 1, 3b2 + 1 = 4 = 2and so a = 2. Hence the fundamental unit is e = 2 +√3.

First we note that the norm of an element in Q(√d) is:

N(a + b√d) = a2 − db2

We will use the following three facts:

  1. N(x + √3y) = x2 − 3y2 = m.
  2. If we have a unit u, then N(a) = N(ua) for some a in Q(√d), as N(u) = 1 and N(ua) = N(u)N(a) (i.e. norm is multiplicative).
  3. In the last post, we saw how the units in the ring of algebraic integers of L is of the form:

Screenshot 2019-10-13 at 10.01.15 PM.png

Thus, multiplying x + √3y by a unit is equal to multiplying x + √3y by a power of the fundamental unit e.

So how do we solve this equation? First, by fact 1 we have to do find the element of Q(√3) that has norm +m or -m (there will be one such element for each, up to multiplication by a unit). Using fact 1 and 2, we deduce all the solutions to the equation are given by (x, y) such that:

  • N(e) = – 1, N(x + √3y) = -m: en(x + √3y) for n a natural number.
  • N(e) = – 1, N(x + √3y) = m: e2n(x + √3y) for n a natural number.
  • N(e) = 1, N(x + √3y) = m: en(x + √3y) for n a natural number.

m = -1

Noting that for any element a,|N(a)| = 1 if and only if a is a unit. Hence as the solutions are given by (x, y) where N(x + √3y) = -1, we must have that x + √3y is a unit. But,

Screenshot 2019-10-13 at 10.01.15 PM.pngso all units have norm 1, and thus there are NO integer solutions to this equation.

 m = 13

We need to find (x, y) such that N(x + √3y) = x2 − 3y2 = 13 (because N(e) = 1).

  • When y = 1, x2 = 14, so x is not an integer.
  • When y = 2, x2 = 25, so x = 5.

Hence we get that all solutions are of the form:

en(5 + 2√3), for n a natural number and e = 2 +√3, fundamental unit


This is the last post of this series! Next I’ll be delving into Galois Theory. M x

 

3: Dirichlet’s Unit Theorem

Last time, I discussed Dedekind’s Criterion. In this post I aim to introduce Dirichlet’s Unit Theorem.

Let L be a number field (finite extension of the field of rational numbers).

We will define a complex embedding of L as being a field homomorphism:

Screenshot 2019-10-12 at 6.49.21 PM.png

Then a real embedding of L  is similarly defined as being a field homomorphism:

Screenshot 2019-10-12 at 6.49.57 PM.png

We note that the complex embeddings can be given in pairs:

Screenshot 2019-10-12 at 6.51.38 PM.png

where we obtain one embedding by taking the complex conjugate of the other embedding in the pair.

Hence, given a number field L, we can label its real embeddings as

Screenshot 2019-10-12 at 6.57.45 PM.png

and its complex embeddings as

Screenshot 2019-10-12 at 6.58.36 PM.png

Noting that the degree, n, of the field extension L/Q (where Q is the field of rational numbers) is equal to the total number of embeddings and hence we deduce that n = 2s + r. The fact that there is this equivalence is non-trivial, so don’t worry if you don’t immediately see why this is! In order to prove this we must use tools from Galois Theory, such as something called the ‘Tower Law’, and therefore I will emit the proof from this blog post.


Let me know if you’re interested in seeing Galois Theory related posts in the future!


Letting Screenshot 2019-10-12 at 7.01.18 PM.png be the units in the ring of algebraic integers of L we are now ready to state Dirichlet’s Unit Theorem.

Dirichlet’s Unit Theorem

Screenshot 2019-10-12 at 7.04.57 PM.png

The proof of this is rather complicated and involves defining a map, whose kernel is this finite cyclic group, which takes Screenshot 2019-10-12 at 7.01.18 PM.png into a lattice. Considering lattices are involved in the proof, you can start to see where the isomorphism with the integers comes from.

Why is this useful?

Take the case where r = 0 and s = 1, i.e. L is an imaginary quadratic number field:

Screenshot 2019-10-12 at 7.11.23 PM.png

As r + s – 1 = 0, we get that Screenshot 2019-10-12 at 7.01.18 PM.png is a finite group. By explicitly defining the isomorphism we can deduce that the finite cyclic group is simply {+/- 1}, and Screenshot 2019-10-12 at 7.01.18 PM.png is generated by one element – the fundamental unit, i.e.

Screenshot 2019-10-12 at 7.17.07 PM.png

I’ve purposefully skipped a lot of the details as what is important is the result. The proof requires a bit of magic and is not terribly enlightening. However, the result is extremely important – using this, for the case of imaginary quadratic fields, we can completely specify Screenshot 2019-10-12 at 7.01.18 PM.png, provided we find the fundamental unit.

Finding the Fundamental Unit

It turns out that finding the fundamental unit in this case is extremely straightforwards. There are various different cases.

  • If d = 2, 3 (mod 4) we characterise the fundamental unit u in the following way: let b be the least positive integer such that db2 + 1 or db2 – 1 is of the form a2 for some natural number a. Then:

Screenshot 2019-10-12 at 7.25.39 PM.png

  • If d = 1 (mod 4) and d is not equal to 5: let b be the least positive integer such that db2 + 4 or db2 – 4 is of the form a2 for some natural number a. Then:

Screenshot 2019-10-12 at 7.27.40 PM.png

  • If d = 5: 

Screenshot 2019-10-12 at 7.28.33 PM.png

(If you would like the proof as to WHY this is true, leave me a comment below and I’ll be happy to make a post!)

Example: d = 2

Then 𝑏 = 1 works since 2 − 1 = 1so 1 + √2 is a fundamental unit.


In order to get a lot of the symbols I had to LaTex some of the sections so sorry if the formatting is a little off! Next time we will start solving some equations using algebra!

M x

2: Dedekind’s Criterion

In episode 1, I introduced the idea of prime ideals. Today we will extend this idea and prove a really important result in algebraic number theory: Dedekind’s Criterion.

We will use the following fact:

If P, contained in O, is a non-zero prime ideal, then there is a unique prime number p such that pP.

For those who are more advanced, this is because the ideal generated by p, namely (p), is the kernel of

Screen Shot 2019-09-17 at 11.12.53 AM.png

Then P|pOand N(P) = pfor some f > 0.

The proof of Dedekind’s Criterion uses a lot of Group Theory and therefore I will not prove it for you. However, it is a really useful tool in algebraic number theory and so I will state it and show how it can be used to factor ideals (remember that in episode 1 we showed that this factorisation is unique).

Before stating the theorem, let me define a few things:

  • Let 𝛼 ∈ Othen Screen Shot 2019-09-17 at 11.39.55 AM.png(𝛼) = { x + 𝛼y | x, y ∈ Screen Shot 2019-09-17 at 11.39.55 AM.png}
  • Let 𝐿/𝐾 be a field extension and let 𝛼 ∈ 𝐿 be algebraic over 𝐾 (i.e. there is a polynomial p with coefficients in such that p(𝛼)=0). We call the minimal polynomial of 𝛼 over 𝐾 the monic polynomial 𝑓 with coefficients in K of the least degree such that f(𝛼) = 0.
  • Say we have a polynomial p(x) = anx+ an-1xn-1 … + a1x1 + a0  with coefficients in K. Then its reduction mod p is defined as p(x) = anx+ … + a0 where ai  ≡ ai (mod p).
  • In episode 1 we defined the degree of a field extension L/K. We denote this as [L:K].
  • Z/pZ is the additive group of the integers mod p. For p prime, this is a finite field. We usually denote this as Fp.

Okay, now we’re ready for the theorem!

Theorem: Dedekind’s Criterion

Let 𝛼 ∈ Obe such that 𝐿 = Q(𝛼). Let 𝑓(x), with integer coefficients, be its minimal polynomial and let 𝑝 be a prime integer such that 𝑝 does not divide the degree [O∶ Z[𝛼]]. Let 𝑓(x) be its reduction mod p and factor

Screen Shot 2019-09-17 at 12.02.55 PM.png

where g1(x), … , gr(x F𝑝 [x] are distinct monic irreducible polynomials. Let gi(x) ∈ Z[x] be any polynomial with gi(x) (mod 𝑝) = gi(x), and define

Screen Shot 2019-09-17 at 12.11.25 PM.png

an ideal of OL. Let f= deg gi(x).

Then p1 ,…, pare disjoint prime ideals of OL and

Screen Shot 2019-09-17 at 12.14.55 PM.png

If you don’t quite understand the theorem, don’t worry! The first time I read this I was really confused as well. I think the more examples you see and the more you use it the easier it becomes to understand. Because of this, I will give you an example next.

Example

Let L = Screen Shot 2019-09-17 at 11.39.55 AM.png(√−11) and p = 5. We will use the following result:

Let d ∈ Z be square-free and not equal to 0 or 1. Let L = Screen Shot 2019-09-17 at 11.39.55 AM.png(√d). Then 

Screen Shot 2019-09-17 at 12.20.18 PM.png

As – 11 = 1 (mod 4), OLScreen Shot 2019-09-17 at 12.22.14 PM.png. Then, [OL: Z[√−11]] = 2 and so we can apply Dedekind’s criterion to 𝛼 = √−11 for p = 5. Then the minimal polynomial is f(x) = x+ 11, so 𝑓(x) = f(x) (mod 5) = x+ 1 = (x+2)(x+3) F5 [x].

Therefore by Dedekind’s Criterion, 5OL= P·where

P = (5, √−11 + 2) and Q = (5, √ −11 + 3)

and P, Q are distinct prime ideals in OL. So we have found how 5 splits in Screen Shot 2019-09-17 at 11.39.55 AM.png(√−11).


In the next episode I will talk about Dirichlet’s Unit Theorem and then we will be ready to solve some problems in Number Theory!

M x

1: Unique Factorisation of Ideals

The next few posts will be me detailing some interesting results in the area of Maths that I hope to specialise in: Algebraic Number Theory. The first result will be the unique prime factorisation of ideals. But first, what is an ideal?

Ideals

If you’re not familiar with the definition of a ring click here, as we’ll need this for the following discussion.

An ideal, I, is a subset of a ring R if :

  • It is closed under addition and has additive inverses (i.e. it is an additive subgroup of (R, +. 0);
  • If aI and bR, then a · bI.

I is a proper ideal if does not equal R.

Ring of Integers

In order to prove the result, I need to introduce the concept of number fields and the ring of integers. A number field is a finite field extension over the rationals.

Field Extension: a field extension F of a field E  (written F/E) is such that the operations of E are those of restricted to E, i.e. is a subfield of F.

Given such a field extension, F is a vector space over E, and the dimension of this vector space is called the degree of the extension. If this degree is finite, we have a finite field extension.

So if is a number field, E would be the rationals.

Suppose is a number field. An algebraic integer is simply a fancy name for an element of F such that there exists a polynomial f with integer coefficients, which is monic (the coefficient of the largest power of x is 1), such that f(a) = 0.

The algebraic integers in a number field F form a ring, called the ring of integers, which we denote as OF. It turns out that the ring of integers is very important in the study of number fields.

Prime Ideals

If P is a prime ideal in a ring R, then for all x, y in R, if xyP, then x ∈ P or y ∈ P. As OF is a ring we can consider prime ideals in OF.

Division = Containment

We want to try and deal with ideals in the same way we deal with numbers, as ideals are easier to deal with (ideals are a sort of abstraction of the concept of numbers). After formalising what it means to be an ideal and proving certain properties of ideals, we can prove that given two ideals I and J, I dividing (written I|J) is equivalent to J containing I.

Three Key Results

Now, there are three results that we will need in order to prove the prime factorisation of ideals that I will simply state:

  1. All prime ideals P in Oare maximal (in other words, there are no other ideals contained between P and R). Furthermore, the converse also holds: all maximal ideals in OF are prime.
  2. Analogously to numbers (elements of a number field F), if I, J are ideals in Owith J|I, there exists an ideal contained in I, such that I = JK.
  3. For prime ideal P, and ideals I,J of  OF , PIJ implies PI or PJ.

Main Theorem

Theorem: Let I be a non-zero ideal in OF . Then I can be written uniquely as a product of prime ideals.

Proof:  There are two things we have to prove: the existence of such a factorisation and then its uniqueness.

Existence: If is prime then we are done, so suppose it isn’t. Then it is not maximal (by 1) so there is some ideal J, properly contained in I. So J|I, so (by 2) there is an ideal K, contained in I, such that I = JK. We can continue factoring this way and this must stop eventually (for the curious, I make the technical note that this must stop as we have an infinite chain of strictly ascending ideals, and OF is Noetherian).

Uniqueness: If P1 · · · Pr = Q1 · · · Qs, with Pi , Qj prime, then we know P1 | Q1 · · · Qs, which implies P1 | Qi for some i (by 3), and without loss of generality i = 1. So Q1 is contained in P1. But Q1 is prime and hence maximal (by 1). So P1 = Q1. Simplifying we get P2 · · · Pr = Q2 · · · Qs. Repeating this we get r = s and Pi = Qi for all i (after renumbering if necessary).

Why is this important?

For numbers, we only get unique prime factorisation in what is called a unique factorisation domain (UFD). Examples of UFDs are the complex numbers and the rationals. However, the integers mod 10 no longer form a UFD because, for example, 2*2 = 4 = 7*2 (mod 10).

However, we have the unique prime factorisation of ideals in the ring of algebraic integers of any number field. This means that we can prove many cool results by using this unique prime factorisation, which we can then translate into results about numbers in that number field. I will detail some of these in future blog posts.

M x

Catalan’s Conjecture

Although popularly known as Catalan’s conjecture, this is in fact a theorem in number theory, proven by Preda Mihăilescu in 2002, 158 years after it was conjecture in 1844 by French and Belgian mathematician Eugène Charles Catalan.

The theorem states that the only solution in the natural numbers of

{\displaystyle x^{a}-y^{b}=1}

for a,b>1; x,y>0 is x = 3, a=2, y=2, b=3.

Catalan ‘Near Misses’ (i.e. xa – yb <= 10; 2 <= x,y,a,b <= 100; a,b prime)

  • 33 – 52 = 2
  • 27 – 53 = 3
  • 23 – 22 = 62 – 25 = 53 – 112 = 4
  • 25 – 33 = 5
  • 25 – 52 = 42 – 32 = 27 – 112 = 7
  • 42 – 23 = 8
  • 52 – 42 = 62 – 33 = 152 – 63 = 9
  • 133 – 37 = 10

Proving the Conjecture

Similarly to Fermat’s last theorem, the solution to this conjecture was assembled over a long period of time. In 1850, Victor Lebesgue established that b cannot equal 2. But then it was only after around 100 years, in 1960, that Chao Ko constructed a proof for the other quadratic case: a cannot equal 2 unless x = 3.

Hence, this left a,b odd primes. Expressing the equation as (x-1)(xa-1)/(x-1) = yb one can show that the greatest common divisor of the two left hand factors is either 1 or a. The case where the gcd = 1 was eliminated by J.W.S Cassels in 1960. Hence, only the case where gcd = a remained.

It was this “last, formidable, hurdle” that Mihailescu surmounted. In 2000, he showed that a and b would have to be a ‘Wieferich pair’, i.e. they would have to satisfy ab-1 ≡ 1 (mod b2) and ba-1 ≡ 1 (mod a2). In 2002,  he showed that such solutions were impossible!

Video

M x

MATHS BITE: Sierpinski Number

A Sierpinski number is an odd natural number k such that {\displaystyle k\times 2^{n}+1} is not prime for all natural numbers n. In 1960, Sierpinski proved that there are infinitely many odd integers k with this property, but failed to give an example. Numbers in such a set with odd k and k < 2^n are called Proth numbers.

78557, 271129, 271577, 322523, 327739, 482719, 575041, 603713, 903983, 934909,….

-List of some known Sierpinski Numbers

Sierpinski Problem

The Sierpinski problem asks what the smallest Sierpinski number is. In 1967, Sierpinski and Selfridge conjectured that 78557 is the smallest Sierpinski number. To show this is true, we need to show that all the odd numbers smaller than 78557 are not Sierpinski numbers, i.e. for every odd k below 78557 there is a positive interger n such that {\displaystyle k\times 2^{n}+1} is prime. There are only five numbers which have not been eliminated:

k = 21181, 22699, 24737, 55459, and 67607

Numberphile Video

Find out more here. M x

Ramsey’s Theorem

Ramsey’s theorem is a fundamental theorem in combinatorial mathematics, and initiated the combinatorial theory called Ramsey Theory. This theory aims to seek regularity in disorder: “general conditions for the existence of substructures with regular properties“.

Ramsey’s theorem states that:

“for each pair of positive integers k and l there exists an integer R(k,l) such that any graph with R(k,l) nodes contains a clique with at least k nodes or an independent set with at least l nodes.


Clique:

A clique of agraph G is a complete subgraph of G.

Clique_950.gif
Source: MathWorld

Independent Set:

An independent vertex set of a graph is a subset of the vertices such that no two vertices in the subset represent an edge of the graph. Below are some examples:

IndependentSet_900.gif
Source: MathWorld


Another formulation of the theorem states that “there exists a least positive integer R(rs) for which every blue-red edge colouring of the complete graph on R(rs) vertices contains a blue clique on vertices or a red clique on s vertices”. Extending this theorem, we can apply this to n colours rather than just 2.

For a proof of this theorem, click here.

Ramsey Numbers

The numbers R(r,s) in Ramsey’s theorem are called Ramsey numbers. Ramsey numbers give the solution to the party problem that asks:

“the minimum number of guests, R(mn), that must be invited so that at least m will know each other or at least n will not know each other”

Connecting Ramsey numbers to graph theory, the Ramsey number is the minimum number of vertices, v = R(m,n), needed in order for all undirected graphs of order v to contain a clique of order m or an independent set of order n. Ramsey’s theorem tells us that this exists for all m and n.

Click here for an article on how to calculate R(4,3).

M x

MATHS BITE: The Kolakoski Sequence

The Kolakoski sequence is an infinite sequence of symbols {1,2} that is its own “run-length encoding“. It is named after mathematician Willian Kolakoski who described it in 1965, but further research shows that it was first discussed by Rufus Oldenburger in 1939.

This self-describing sequence consists of blocks of single and double 1s and 2s. Each block contains digits that are different from the digit in the preceding block.

To construct the sequence, start with 1. This means that the next block is of length 1. So we require that the next block is 2, giving the sequence 1, 2. Continuing this infinitely gives us the Kolakoski sequence: 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, etc.

M x

Fermat’s Little Theorem

Statement:

Let p be a prime then ap ≡ a (mod p), for any natural number a.

Proof using Modular Arithmetic:

Firstly, we need to discuss Wilson’s theorem. This states:

(p-1)! ≡ -1 (mod p) is p is prime.

We must first prove this theorem:

If p is prime, then 1, 2, …, p-1 are invertible mod p. Now we can pair each of these numbers with its inverse (for example 3 with 4 in mod 11). The only elements that cannot be paired with a different number are 1 and -1, which are self-inverses, as shown below:

Screen Shot 2017-01-02 at 6.30.37 PM.png

Now (p-1)! is a product of (p-3)/2 inverse pairs together with -1 and 1, whose product is -1.

So (p-1)! ≡ -1 (mod p).

Back to the proof of Fermat’s Little Theorem.

The statement of Fermat’s Little Theorem is equivalent to ap-1 ≡ 1 (mod p) if a ≢ 0 (mod p).

Consider the numbers a, 2a, …., (p-1)a. These are each distinct mod p and so they are congruent to 1, 2, …., (p-1) (mod p) in some order.

 Hence a·2a···(p-1)a ≡ 1·2···(p-1) (mod p).

So ap-1(p-1)! ≡ (p-1)!.

And therefore ap-1 ≡ 1 (mod p).

We can extend this to a≡ a (mod p) as shown below:

When a ≡ 0 (mod p): 0≡ 0 (mod p). So a≡ a (mod p).

When a ≢ 0 (mod p): We can multiply through by a, as a and p are coprime. Then we get a≡ a (mod p), as required.

Hence, we have proved Fermat’s Little Theorem, a very important result in number theory.

M x