## 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: 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, so 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: Then a real embedding of L  is similarly defined as being a field homomorphism: We note that the complex embeddings can be given in pairs: 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 and its complex embeddings as 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 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 The proof of this is rather complicated and involves defining a map, whose kernel is this finite cyclic group, which takes 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: As r + s – 1 = 0, we get that is a finite group. By explicitly defining the isomorphism we can deduce that the finite cyclic group is simply {+/- 1}, and is generated by one element – the fundamental unit, i.e. 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 , 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: • 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: • If d = 5: (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 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 (𝛼) = { x + 𝛼y | x, y ∈ }
• 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 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 an ideal of OL. Let f= deg gi(x).

Then p1 ,…, pare disjoint prime ideals of OL and 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 = (√−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 = (√d). Then As – 11 = 1 (mod 4), OL . 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 (√−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 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!

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. 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: 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 Beginning of Chaos

In 1887, King Oscar II of Norway and Sweden offered a prize for the solution of the following maths problem:

Say you have a number of celestial bodies with known mass and you know the speed and direction they are moving in at some given point in time. Use Newton’s laws of motion and the universal law of gravitation to calculate the trajectories of the bodies.

After three years, the French mathematician Henri Poincaré, who restricted himself to the case where there are just three bodies, won the prize.

However, after winning the prize, Poincaré noticed a flaw in his solution putting him in an embarrassing position, as his manuscript was to be published for the King’s birthday within a few weeks’ time!

In his attempt to correct his work, Poincaré discovered that even this simple problem suffered from the Butterfly Effect: “sensitive dependence on initial conditions“. This means that the smallest variation in the initial values can build up over time to create massive discrepancies in the trajectories. Hence, you cannot reliably predict the motion of planets over time, as you can’t know the initial values with an infinite degree of accuracy.

With this discovery, Poincaré laid the foundations for Chaos theory.

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: 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

## Prime Number Theorem

Today I thought I’d quickly discuss a extremely important theorem in one of my favourite areas in mathematics: Number Theory (as you can probably tell by the number of posts that I’ve published about primes!).

Perhaps the first property of π(x) – the number of primes less than or equal to x – is that π(x) tends to infinity as x tends to infinity. In other words, the prime numbers are infinite, which was proved by Euclid in “Elements”. A more precise result, established by Euler in 1737, was that the series of reciprocals of the prime numbers: is a divergent series. In doing so, Euler found an alternative way to prove that there was an infinite number of primes, as if there wasn’t then the series would have a finite value.

The Prime Number Theorem states that if π(x) is the number of primes less than or equal to x, then Although the notation ~ may be unfamiliar, it simply means that π(x) is asymptotically equal to x/lnx, i.e. Note that the prime number theorem is equivalent to saying that the nth prime number pn satisfies the following relationship: The PNT was proposed by Gauss in 1792 when he was only 15 years old! (Makes you wonder what you’ve been doing with your life so far…) He later refined this estimate to HAPPY HALLOWEEN! M x