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

 

Advertisements

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

Towers of Hanoi

The Problem

The Tower of Hanoi is a famous problem first posed in 1883 by E. Lucas. There are 3 rods and n disks resting on one rod, sorted in size like a pyramid with the smallest disk on top. Given that you can only move the disks one at a time and that you can never place a bigger disk on a smaller disk, the aim is to move all the disks from the left hand post to the right hand post in the smallest number of moves possible.

Towers Of Hanoi
Source: http://www.codenuclear.com

Obtaining a Recurrence

Consider n = 0, the simplest case with no discs. As there are no discs to move, we cannot make any moves, so the number of steps required is 0. Letting Sn be the number of moves required for n disks, we get S= 0.

Now, we must consider how the problem scales. With n = 1, a single step will solve the problem. With n = 2, the answer is 3 steps: one to move the top (small) disk to another rod, one step to move the big disk to the destination rod, and lastly one step to move the small disk on top of the big disk.

We now consider n discs. We need Sn-1 steps to move all disks except the biggest one, then move the biggest disks then move the sub-tower on top of that disc with Sn-1 steps again. So we have the following upper bound:

Screenshot 2019-07-03 at 5.29.06 PM.pngWhat about a lower bound? At some point we must move the biggest disk to the destination rod. To get to the biggest disk, we must have moved all disks on top of it to another rod (the sub-tower), and after having moved the biggest disk, we must move this sub-tower back on top of that rod back onto the biggest disk. Due to these constraints due to the rules of the problem, we know that for n > 0 we must take at least 2*(Sn-1) + 1 steps.

Hence, this recurrence relation gives us the exact number moves needed.

Simplifying the Recurrence

Claim: Sn = 2n – 1 for all natural n.

Proof (by Induction):

Clearly true for n = 0.

Then Sk+1 = 2*(Sk + 1 = 2*(2k – 1) + 1, by the induction hypothesis.
So Sk+1 = 2*2k – 2 + 1 = 2k+1 – 1, as required.

So the claim holds by induction.

So we have found an easy formula for the number of steps needed to solve the Tower of Hanoi problem for any n!

M x

 

I’m back!

After a long year of university filled with lots of ups and downs, I am finally back! I decided to take a year out of blog post writing to focus on my final year as an maths undergraduate. A year later, I have finished my final exams and found out that I did well enough to get a spot in the masters program! Feeling refreshed and filled with one more year of maths to share, I am ready to start writing regular posts again.

Thank you for staying subscribed despite my lack of output this year and hopefully see you in many more posts to come!

M x

The woman who could help put men on Mars

Kathleen Howell is an American scientist and aerospace engineer. Her contributions to the theory of dynamical systems have been applied to spacecraft trajectory design, which led to the use of near-rectilinear halo orbit (NRHO) in various NASA space missions.

Unlike an ordinary flat orbit, an NRHO can be slightly warped. Further, it stands on end, almost perpendicular to an ordinary orbit – hence “near rectilinear”.

NASA have decided that an NRHO would be an ideal place to put the Lunar Orbital Platform-Gateway, which is a planned way station for future human flights to the Moon and eventually Mars. The plan is for the Gateway’s circuit to pass tight over the Moon’s north pole at high speed and more slowly below the south pole, because of the greater distance from the moon.

Imagine moving your hand in circles, as if washing a window, while you walk forward. Except you’re making hand circles around the moon while walking around Earth.” – Bloomberg

Although this orbit seems to be an ordinary circuit of the moon, it’s actually part of a family of orbits, centred on an empty point, called L2 (or Lagrange Point 2). Here, around 45,000 miles beyond the far side of the Moon, the gravitational forces of the Earth and the moon are in balance with the centrifugal forces on the spacecraft.

Although we are taught in school that orbits must be around something, it is quite possible to orbit around nothing, so long as that ‘nothing’ is a Lagrange point.

“It is elegant and very rich. All the forces come together to produce an unexpected path through space” – Howell

Howell’s work build on an 18th century discovery, by Euler, who theorised that for any pair of orbiting bodies, there are 3 points in space where gravitational and centrifugal forces balance precisely. In 1772, Lagrange found two more such spots. All five are now known as Lagrange points.

Image result for ;lagrange points
Source: Wikipedia

In 2017 Kathleen Howell was elected to National Academy of Engineering “for contributions in dynamical systems theory and invariant manifolds culminating in optimal interplanetary trajectories and the Interplanetary Superhighway“.

M x