All posts by Markus Shepherd

The Prime Bet

Let's say you sit in a pub, minding your own business, when all of a sudden a stranger walks up to you and offers you a bet:

We'll choose two positive integers at random. If they have any divisor in common (other than 1) I'll pay you a dollar, else you'll pay me a dollar. Are you in?

Apart from the question what kind of establishments you frequent, you should be wondering: is this a good bet for you?

When two integers have no divisors in common except the trivial divisor 1 we say they are coprime or relatively prime. 6 and 9 have the common divisor 3, so they are not coprime, whilst 8 and 9 only have the trivial common divisor 1, so they are coprime.

This makes you start thinking: "As numbers grow bigger, aren't there a lot of divisors out there? After all, half the numbers are even, so if we hit two even numbers, they'll have the factor 2 in common and I'll win. And then there's 3, 5, 7, ... Seems like a good deal!" Continue reading The Prime Bet

Numbers of the World

Recently Matt Parker uploaded a video to his YouTube channel where he discussed numbers and the words used to represent them in different languages, more precisely the length of these words:

The basic idea is the following:

  1. one has 3 letters,
  2. two has 3 letters,
  3. three has 5 letters,
  4. four has 4 letters,
  5. five has 4 letters,
  6. six has 3 letters,
  7. seven has 5 letters,
  8. eight has 5 letters,
  9. nine has 4 letters,
  10. ten has 3 letters,

and so on... This can be seen as a function

f(n) = \text{number of letters of $n$ spelled out}.

Continue reading Numbers of the World

Primes from a Different World

Every textbook on number theory will begin with a treatise on prime numbers; every treatise on prime numbers will begin by emphasising their importance as building blocks or atoms of our number system: every integer can be expressed as a product of prime numbers in one way and one way only. Six is two times three and there is no other way to decompose it.1 Euclid proved this over two thousand years ago and it is so fundamental (hence the name fundamental theorem of arithmetic) to our thinking about numbers that we take it for granted. It is not!

There are numbers that behave very much like the integers but have a different structure. One rather simple example are the Gaussian integers (usually denoted \mathbb Z[i]) which look just like complex numbers z=x+iy, except that x and y are restricted to integer values. They live in the complex plane, but exclusively on a discrete grid amongst their continuous cousins.

Gaussian_integer_lattice.svg Continue reading Primes from a Different World

  1. Yes, you can write 12 as 3*4 or 2*6, but you can continue either way and eventually reach the unambiguous 2*2*3. 

Visualising the Riemann Hypothesis

One stubborn source of frustration when working with complex numbers is the fact that visualisation becomes tedious, if not impossible. Complex numbers have 2 "real" dimensions in themselves, which give rise to the complex plane. That's all good and fair. But if you talk about a function with complex domain and codomain, you already deal with a 4-dimensional graph. Unfortunately, my mind can only handle 3 dimensions (on a good day). One can resort to taking the absolute value of the function instead, or map real and imaginary part individually, resulting in a 3-dimensional graph, but all of these solutions fail to satisfy in one respect or another.

However, there is one more dimension we can exploit: time! Used in the right way, this can produce wonderful videos like this one:

Continue reading Visualising the Riemann Hypothesis

A Toy Keyless Encryption Protocol

Cryptography is a natural application of number theory and so I'd like to write down a few thoughts about it in this blog. (The fact that there are real world applications to number theory deserves some appreciation in itself, but it would throw us too much off track here.) One particularly nice feature of cryptography is the ability to explain its inner workings with real world analogies about security.

For instance, one way two parties (who we, by convention, call Alice and Bob) could hide their secrete communication is if Alice writes a letter, puts it in a box, and locks it with a padlock for which both she and Bob have a key, but no one else. Then Alice can send this box safely through any public means as anyone who intercepts it will not be able to open the box, rendering it useless to them. This is the principle behind symmetric cryptography. The obvious problem is that Alice and Bob will only be able to communicate if they managed to obtain identical keys beforehand.

Alternatively, Bob could distribute padlocks for which only he possesses the key to anyone who's interested. Now Alice can obtain such a padlock, use it to close the box with her letter and send it off to Bob. She won't be able to open the box, but neither will anybody else -- except Bob. It sounds tedious to ship padlocks for every single communication, but the advantage is that there's no need whatsoever for Bob to restrict distribution to trusted parties, making it possible for anyone to send him messages securely. This is the basis of public key cryptography (a field which is extremely number theory heavy -- a course about it will feature extensively theorems on primes, groups, elliptic curves, lattices, and many more really abstract concepts).

But there is yet another way parties could communicate securely. Let's imagine Alice uses a lock for which only she has a key. She ships this of to Bob who cannot unlock it himself -- instead, he'll add another padlock himself and sends everything back to Alice. She couldn't open it herself anymore, but she can remove her padlock and still send it off to Bob once more knowing no one except Bob will be able to open her secret. Finally, Bob opens his lock and can read Alice's message. No need to meet up and share keys, no shipping padlocks. Continue reading A Toy Keyless Encryption Protocol

Prime Generating Sequences

A couple of months ago (really, a long, long time ago) I found an interesting question on Mathematics Stack Exchange (another site to effectively waste away hours of your life). It reminded me of my Bachelor's thesis (which I wrote a really, really long time ago) about the sequence

g_n=\mathrm{gcd}(n,a_{n-1})=(n,a_{n-1}) \quad\text{for}\quad n>1,

where a_1=7 and


Here, \mathrm{gcd}(a,b)=(a,b) stands for the greatest common divisor,1 i.e., the largest integer d that divides both a and b. This may not seem terribly interesting at first sight, but if you look at the first few values for g_n you'll notice something curious:

1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 23, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 47, 3, 1, 5, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 101...

There are for sure a lot of ones in there, but other than that, all the numbers are primes. This is not a bias in the first few example -- Eric Rowland proved that all values of g_n are either 1 or a prime in a beautiful little paper back in 2008. Continue reading Prime Generating Sequences

  1. It's common to abbreviate gcd(a,b)=(a,b) in number theory, and I shall do so in the remainder of the article. Similarly, it's convention to write lcm(a,b)=[a,b]. 

If One at a Time is too Difficult, Try All at Once!

In the past months, I spent as much time as I had on taking online courses at Coursera. One particularly interesting course, both from a mathematical and computational point of view, is Analytic Combinatorics which applies combinatorics (i.e., the art of counting) to the analysis of algorithms by finding formulae, exact or asymptotic, for their running time.

It is notoriously difficult to find exact formulae for general combinatorial constructs. Typically, we want to know how many objects, e.g., trees, permutations, sequences, with certain properties there are of a given size. Famously, the number of binary trees (and about a million other constructions) is governed by the Catalan numbers

C_n = \frac{1}{n+1}{2n\choose n}.

Continue reading If One at a Time is too Difficult, Try All at Once!

Applying the Explicit Formula

It's quite some time since we arrived at Riemann's main result, the explicit formula

J(x)=\mathrm{Li}(x)-\sum_{\Im\varrho>0}\left(\mathrm{Li}(x^\varrho)+\mathrm{Li}(x^{1-\varrho})\right)+\int_x^\infty\frac{\mathrm{d}t}{t(t^2-1)\log t}-\log2,

where J(x) is the prime power counting function introduced even earlier. It's high time we applied this!

First, let's take a look at J(x) when calculating it exactly:

J(x) Continue reading Applying the Explicit Formula

Tossing the Prime Coin

One of the problems with explaining the Riemann Hypothesis is that its fascination comes from its deep connection to prime numbers, but its definition is in terms of complex analysis which requires a fair deal of undergraduate mathematics to understand -- and that is before you even got started to grasp what the heck the zeta-zeros have to do with the distribution of primes. My "cocktail party explanation" of the Riemann Hypothesis would usually be something like: "The prime numbers are as equally distributed as you could wish for." But there is actually a surprisingly easy interpretation of the Riemann Hypothesis: "Prime numbers behave like a random coin toss." Continue reading Tossing the Prime Coin