You are currently browsing the category archive for the ‘For Everyone’ category.

The study of  whole numbers is one of the oldest lines of inquiry in mathematics which is still thriving today. After all, it is possible in pure mathematics for the relevance of work done thousands of years ago to be undiminished today. I want to talk today about what is possibly the prototypical example of such a piece of mathematics. I am referring to Euclid’s proof of the infinitude of prime numbers.

A divisor of a number n is another, smaller number, for which there is no remainder when n is divided by it. For example, three is a divisor of six, seven is a divisor of seven and thirty-nine is a divisor of one hundred and seventeen. A prime number is a number with exactly two divisors. Let’s think about what it means to have exactly two divisors. Firstly, we observe that every whole number has at least one divisor, namely the number itself. Secondly, every whole number except for ‘1’ has at least two divisors: The number itself and the number ‘1’. So, with the exception of the number ‘1’, being prime expresses the quality of having the fewest possible divisors. Why must there must be infinitely many such numbers?

Ever wonder what happens when you send your card details over the internet? How exactly does public-key encryption work? I will write a brief, non-technical introduction to these concepts and the mathematical background in them, containing some sample code and plenty of examples.

Before we describe the RSA algorithm, there is one important mathematical concept, which is prime numbers and their factorization. Recall that a number $p$ is prime if no other number divides $p$ other than itself and $1$. For technical reasons we exclude the number $1$ from being prime. So lets see some examples. Is $3$ prime? Well, yes, no other number other than $3$ and $1$ divide it. Is $24$ prime? No, because $24 = 12 \times 2$.

There is a fundamental theorem in number theory which says that every number $n$ can be uniquely written as a product of prime numbers, i.e. $n = p_1^{\alpha_1} \dots p_k^{\alpha_k}$ where $p_1, \dots, p_k$ are prime. So again, a few examples cannot hurt. Take the number $24$. We know that $24 = 12 \times 2$, but now $12$ is not prime so $12 = 6 \times 2 = 3 \times 2 \times 2$. Hence $24 = 3 \times 2 \times 2 \times 2 = 3 \times 2^3$. That’s what a prime factorisation is, and what the theorem says is pretty basic, if a number $n = 3 \times 2^3$, then $n = 24$.

At this point now I can state what is the fundamental idea behind RSA:

Factoring a number into prime factors is much harder than checking if a number is prime!

But why is this true? There are technical reasons for this but I prefer to think along the following lines. Computers are much like humans, so imagine if a human is given the task of factorising numbers and checking if numbers are prime.

Let’s jump straight in. Suppose I have a collection of n different objects, where n is some unknown but fixed whole number. Suppose I want to arrange k of them in a row on my shelf, where k is some unknown but fixed whole number less than or equal to n. In how many ways can this be done?

This is a counting problem. You are being asked to count how many of something there are. The answer will be a formula involving the unknown quantities n and k. Counting is often thought of as being easy. While it is true that the things which must be counted are easy to describe (I have just done so in a couple of sentences), this does not mean that the problem of counting them is easy. So, in this post I continue my quest to explain some basic things about counting and how to do it.

Now that you’ve decided on your outfit, you take a trip to the cinema with a friend. When you get there, you see that there are only two seats left and they are next to each other. In how many different ways can you and your friend occupy these two seats? Well, once seated, either you will be sitting on the left and your friend will be to the right of you or you are sitting on the right with your friend on your left. So there are two ways in total. This is very easy to see, but what if there were three of you and three seats left? In how many ways can you and your two friends occupy the three seats?

This post is in the ‘Mathematics for Everyone’ category. These posts will be short snippets and will, I hope, increase slowly in complexity.

Suppose that you are going out to the cinema tonight and that you do not know what to wear. You have narrowed down your choice considerably but you cannot decide which of three different tops and which pair of two different pairs of jeans you would like to wear. You would wear any top with any pair of jeans, but you need to choose which top and which pair of jeans. How many different complete outfits are you choosing from?

There are plans to build a Museum of Mathematics in Manhattan and over \$20 million has already been raised for the ’cause’. The Math Midway, which already exists as a traveling exhibition, has something of a preview of coming attractions. There is also a discussion about what mathematicians would like to see at the museum taking place on MathOverflow here.

What do you think of this idea? Personally, I am skeptical, though I may just be being snobbish – it is likely that my academic leaning precludes a fair judgement of such a thing as a museum of mathematics because I will always be tempted to say “If you want to learn about maths, then maybe you should study some maths: Read some books, pay attention at school, discuss maths with teachers, discuss it online, join a math club/circle etc.” I’d be worried about the negative effect of people going in and saying “Oh so this is maths? It’s boring”. Which seems to me even less desirable than “I know nothing about maths”, because my response to the latter can be “If you studied it like I do, then you too would love it!”

So, if it can be accepted that not everything is necessarily amenable to ‘museumization’, then I would definitely argue that mathematics falls into this category and would make a poor subject for a traditional-style museum. (I’ve never been a huge fan of Science Museums either, so perhaps I’m just the wrong person to ask – what do ‘proper’ academic scientists think of the Science Museum in London, for example?)

It sounds a bit romanticised by it’s also arguable that one really does need to invest some effort into appreciating mathematics. Every mathematician knows the feeling when, while at the pub, having just defended the beauty and awesomeness of mathematics, a friend says defiantly “Go on, tell me some maths”…  Show me the beauty and awesomeness. But this is impossible. The passivity of this stance immediately places the friend outside of those who are capable of appreciating mathematics on the scale that the mathematician does. You can’t just sit there and be shown. You have to do. You have to show yourself! The mathematician knows that her friend isn’t actually prepared to spend the next hour struggling to appreciate some minute idea which the mathematician seems to assert is worth understanding.

This comment was sort-of inspired by seeing the MathOverflow discussion, but there is a character limit on comments in the forum!

### But Did Homer Catch the Bus?

Before we get on to the continuum hypothesis, let’s talk briefly about what we did in the last post because it’s a nice introduction to an important idea. We saw that it was possible to add up infintely many things. Let’s discuss this in the context of one of the paradoxes we introduced last time.

Let’s think back to Homer running for the bus (introduced at the start of the previous post). Suppose the distance to the bus is 100 metres. The way the paradox is phrased makes it seem as though, by splitting up 100 into infinitely many bits, it is impossible for Homer to traverse the entire distance because he cannot do infinitely many journeys in a finite amount of time. The mathematical definition we discussed last time (that of a series summing up to a finite quantity – one of the basic ideas of mathematical analysis) ignores this potential problem.

Imagine an arrow in flight. At any given instant in time, the arrow is not moving, because an instant is a snapshot. If it cannot move in an instant then it cannot move in any instant and motion is therefore impossible.

This is one of Zeno’s Paradoxes!  Here is another:

Suppose that Homer is running for a bus. Before he gets to the bus he must get halfway there. Before he gets halfway there he must get a quarter of the way there and before that an eighth of the way there and so on. Completing the journey requires completion of an infinite number of tasks. Is this possible? Zeno maintained that it was not. Mathematical thought has something to say about these paradoxes. We will by no means lay to rest every possible concern of the philosopher but in this post and the next we will investigate the mathematical ideas which are brought to light by these things and then move on to discussing the continuum hypothesis.

We’ll now discuss a classic example of a set which is larger than the set of natural numbers, in the sense that it is infinite but not countable. Such sets are called (sarcastic drum-roll) uncountable. The existence of such sets shows that there really are different sizes of infinity.

### Power

The set which we are going to think about is a large collection of sets, so, a set of sets, if you will. Each element of our big collection will be a set of natural numbers. In fact, I want to consider every possible set of natural numbers, and gather all these sets together in one big collection.

Therefore, our big collection includes, for example, the set containing one, two and twenty and nothing else. The (self-explanatory) notation for this set would be {1,2,20}.  Our big collection also contains sets like {1} and {17}, as well as things like {1,2,3,4,5,6,7} and {,2,40,644,9999}, as well as infinite sets like the set of prime numbers, or square numbers, or multiples of 19 and so forth. It is a vast collection. The set I’m describing is the set of all subsets of the natural numbers and is called the power set of the natural numbers.

In 1877, a mathematician called Georg Cantor put forward a simple hypothesis called the continuum hypothesis. It was a statement about infinity which he believed to be true, but was unable to prove. With hindsight, this was nothing to be ashamed of; it would be 100 years before the mystery surrounding the difficulty of its proof would be understood.

Throughout the 1870’s Cantor had been working on set theory and the theory of the infinite but his work was not received well. People debated about whether or not his ‘theory of the infinite’ was mathematics at all: Did his work really belong to philosophy? Should it be discarded because it challenged the uniqueness of the absolute infinity of God? Infinity had sometimes been seen as a convenient tool to be used when reasoning informally but ultimately when reasoning about the finite world. The ‘actual infinity’ of Cantor’s work was too alien for many mathematicians and philosophers of the time. So, what was his bold hypothesis? And what was so weird and abhorrent about infinity? In this first post on the topic I will introduce infinite sets and we’ll think about how to think about them mathematically.