While catching up on past issues of Chalkdust over the Christmas break, I was intrigued to see that issue 07 featured an article on Chladni figures (On the cover: Chladni figures of a square drum by James Cann), followed in issue 08 by an article on Truchet tiles (Too good to be Truchet by Colin Beveridge). This coincidence fascinated me because, although not the focus of the articles, there is a remarkable conjecture that links these two apparently unrelated objects, via the mathematics of percolation theory. Continue reading →

Icy patches sit in wait and bare trees shiver in anticipation but spring is still dawdling, likely enjoying a final cuppa before going back to work. What are we to do while days are dreary and the wind rummages through empty branches? Why, stay inside and play with geometry software, of course! Yet winter was long and snowy, and after one too many hours indoors the treasure trove of maths is perhaps running low.

What to do once ancient theorems are re-proved and the excitement of a parametric plot has wilted? Well, there is still a nugget of algebra that could flourish into hours of exploratory fun. So grab your Geometer’s Sketchpads, your Geogebra, or simply some transparencies and coloured markers, and let’s play billiards with polynomials. Continue reading →

For a very long time now, people have been coming up with ingenious ways of exchanging messages securely. From the basic Caesar cipher to the Enigma, however, there has been a universal caveat: how to agree on the encryption/decryption key without meeting face to face?

To put it simply, consider the following situation: Alice and Bob want to communicate with one another using an Enigma machine. Alice adjusts the settings of her machine, tells Bob what those settings are, types a secret message, and sends the encrypted text to Bob, who then adjusts his own machine’s settings and proceeds to decrypt the message.

But hang on a minute. How exactly did Alice give her settings to Bob? Alice can’t send encrypted messages unless Bob has those settings, but at the same time Alice has no way of secretly passing those settings on to Bob. Is there a way for them to somehow come up with a shared secret key (ie the settings for the machines) by exchanging messages visible to anyone listening to their conversation?

The Diffie–Hellman protocol allows us to do exactly that. Let’s dig in and see how it works!

Some modular arithmetic

We are all used to the regular addition and multiplication of numbers. Indeed no one would ever question that $4 + 11 = 15$. In modular arithmetic, we change the rules slightly, by saying two numbers $a$ and $b$ are the same mod ${p}$, or congruent mod ${p}$, if their difference is an integer multiple of $p$, and we write $a \equiv b \bmod{p}$. For example, since $15 – 1 = 2\times7$, we would write $15 \equiv 1 \bmod{7}$. This is sometimes know as clock arithmetic because we kind of wrap around every time we reach $p$.

Let’s think of what happens when we take the integers mod ${5}$. Observe that any integer will be congruent to one of $0,1,2,3,4$, and that none of $0,1,2,3,4$ are congruent to each other. The set $\{0,1,2,3,4\}$ is therefore enough to “represent” all the integers mod ${5}$, and we call this set $\mathbb{Z}_5$.

Just as with the regular integers, we can add and multiply integers mod ${p}$ together. Of particular interest to us is the multiplication, because it gives an interesting structure to the set. Notice that almost every element in the set $\mathbb{Z}_p$ has what we call a multiplicative inverse. For example in $\mathbb{Z}_5$, $2 \times 3 \equiv 1 \bmod{5} $, so we say that $3$ is the inverse of 2 mod ${5}$ (and vice-versa that $2$ is the inverse of 3 mod ${5}$). Similarly, $4\times 4\equiv 1 \bmod{5}$, so we say that $4$ is its own inverse mod ${5}$.

I did say almost every element, because $0$ never has a multiplicative inverse. This could cause some problems down the road, so we decide to do away with zero entirely, and call the resulting set $\mathbb{Z}_p^*$. Now, $\mathbb{Z}_p^*$ together with multiplication has a lot of structure, and it is in fact an example of a group. We will see another example of a group later on in the article.

There is something special about $\mathbb{Z}_p^*$ that makes it very useful in cryptography. Let’s look at $\mathbb{Z}_7^*$ and enumerate the powers of 3 mod ${7}$. We have:

The elements of $\mathbb{Z}_7^*$ written in a circle, with arrows showing multiplication by 3

$3^1 \equiv 3 \bmod{7}$
$3^2 \equiv 2 \bmod{7}$
$3^3 \equiv 6 \bmod{7}$
$3^4 \equiv 4 \bmod{7}$
$3^5 \equiv 5 \bmod{7}$
$3^6 \equiv 1 \bmod{7}$

What do we notice? Every one of $1,2,3,\ldots,6 \bmod{7}$ can be expressed as a power of 3 mod ${7}$! Because of this, we say that $3$ is a primitive root mod ${7}$ and that $\mathbb{Z}_7^*$ is a cyclic group. Note that not every element of $\mathbb{Z}_7^*$ is a primitive root: if we instead looked at powers of 2 mod ${7}$ for example, we would only get half of all possible values. Because $7$ is prime, however, we are guaranteed the existence of primitive roots in $\mathbb{Z}_7^*$. This simple fact will be paramount in making sure our Diffie–Hellman protocol is secure, but before we get there, let me give you a small problem: can you list all the primitive roots mod ${7}$?

It shouldn’t take very long to determine that these are $3$ and $5$. But $7$ is a small prime; what about finding all the primitive roots mod ${23}$?

This is a bit tedious if you try every number up to $23$, but you should find exactly $10$ distinct primitive roots. Notice that $10$ is exactly the number of integers smaller than $22$ which are coprime to $22$. This is not a coincidence! In general, there are exactly $\phi(p-1)$ distinct primitive roots in $\mathbb{Z}_p^*$, where $\phi(n)$ is the number of integers between $1$ and $n$ that are coprime to $n$. Although this doesn’t tell us how to find primitive roots, it does give an upper bound on how many numbers we have to try before finding a primitive root. Computers are reasonably good at finding primitive roots, but the larger the prime the longer it takes. Because of this, we tend to reuse primes whose primitive roots we’ve already computed when doing cryptography.

Discrete logarithms and the Diffie–Hellman key exchange

Now let’s think about another problem: if I give you some $k$, say $k=3$, can you compute $5^k \bmod{7}$? This is not too difficult, and computers are quite fast at computing powers of elements mod ${p}$.

The inverse problem, though, is not so straightforward: given that $5^k \equiv 3 \bmod{7}$, can you find $k$? Yet again, because $7$ is a small prime, you shouldn’t have a hard time figuring out the answer. I invite you to think about your process in solving the problem.

My guess is that you raised $5$ to different powers until you found that $5^5 \equiv 3 \bmod{7}$. What if I told you that $5^k \equiv 48 \bmod{53}$? Can you find $k$ then? Going about it the same way as before, it might take you a while. The general problem of finding $k$ such that $g^{k} \equiv m \bmod{p}$, where $g$ is a primitive root, is known as the discrete logarithm problem, and it is a very difficult problem indeed when $p$ is very large. Hence the function
$$
k \mapsto g^{k} \bmod{p}
$$
is an example of a trapdoor function: it’s easy to compute $g^{k} \bmod{p}$, but hard to find $k$ if you only know $g$ and $g^{k} \bmod{p}$.

We can use this trapdoor function to publicly exchange keys. Let’s see how:

That’s it! I personally find it hard not to be taken aback by the simplicity of the procedure: because Alice knows $n$, she can raise $g^{m}$, which she received from Bob, to the $n$th power and get $g^{nm}$, and similarly for Bob. After an exchange of information taking place entirely in plain sight, Alice and Bob now have a secret key that they can use to encrypt all further communication! This is what made the Diffie–Hellman protocol revolutionary.

To understand why this is secure, let us put ourselves in the shoes of an attacker. In the course of the whole exchange, what do we see? Because the communications are not encrypted, we will know the values $p$, $g$, $g^{n} \bmod{p}$, and $g^{m} \bmod{p}$. To obtain $g^{nm} \bmod{p}$, one essentially needs to solve the discrete logarithm problem to find $n$ or $m$.

Ironically enough, there is no formal proof that the discrete log problem is hard to solve. We do have quite a few algorithms that compute discrete logarithms, but none of them performs particularly well. There is an efficient quantum algorithm due to Peter Shor: it is an algorithm that would run on a quantum computer, which could pose a threat to current systems should practical quantum computers ever hit the market.

Another type of logjam

But quantum computing aside, Diffie–Hellman is not perfect. As mentioned before, choosing such large primes and finding their primitive roots is not something you want to do every single time you initiate a link, and, in practice, the same primes are reused. This is fine in general, as the discrete logarithm problem is considered hard enough for very large groups, even if those groups are known in advance.

In 2015, however, a group of computer scientists reported that pre-computations were feasible for those primes which we know are used—essentially building a lookup table of the powers of primitive roots for those specific primes. These pre-computations would take a lot of resources, and the estimated cost of such an operation is in the hundreds of millions of dollars, which has been pointed out to be well within the budget of some national agencies.

This vulnerability is known as logjam. The ways to circumvent it are to either use larger primes, or to use a variant of the Diffie–Hellman protocol known as elliptic-curve Diffie–Hellman.

What is an elliptic curve?

An elliptic curve is the solution set of an equation of the form: $y^{2} = x^{3} + ax^{2} + bx + c$. For us, the numbers $a$, $b$, and $c$ will be integers. We also require, as a technicality, that the curve has no cusps and does not cross itself. We have to specify which values of $x$ and $y$ we allow: rational numbers? real numbers? complex numbers? We will denote the set (field) we draw our values from by $k$ and the elliptic curve by $\mathcal{C}(k)$. On the next page, there are some examples of elliptic curves over the real numbers.

Later on, we will be considering curves over finite fields, in particular the $\mathbb{Z}_p$ we talked about earlier. Here’s what our curves look like over those fields:

You might be thinking that these don’t exactly look like curves, but they are: they’re the set of points that satisfy the equation over $\mathbb{Z}_p$. What we’re interested in is the structure of the points on those curves, and in practice we may have lots of questions about those points: how many are there? Is there an effective way of finding all of them?

A theorem of Hasse tells us that in general, there should be about $p+1$ points on an elliptic curve over $\mathbb{Z}_p$, and another result by Mordell and Weil tells us that starting with finitely many points on an elliptic curve, we can generate all the points on the curve. We won’t
understand the proof of this theorem by the end of this article, however it would be nice to understand what it is saying.

How can we generate new points from old points? It turns out that’s not particularly complicated. Take two points $P$ and $Q$ on the elliptic curve. Draw a line through $P$ and $Q$. This line will intersect the curve at some third point, which we name $P*Q$.

$y^{2}=x^{3}-x+4$ with point addition constructions

This point is on the elliptic curve, so we could stop here, but we go one step further, and for good reasons. Draw a vertical line through $P*Q$. It will intersect the curve at one other point, and this point we name $P+Q$.

If $P$ and $Q$ are the same point, then we do the same thing except that we draw a line tangent to $P$ instead of through $P$ and $Q$ at the beginning.

This new “addition” of points is the first step to giving some structure to the set of points on an elliptic curve.

Let’s make another definition: starting from a point $P$, draw a vertical line through it. Just as before this vertical line intersects the curve at one other point, and we call this point $-P$. Now I want you to add $P$ and $-P$ together. What happens? It seems like the whole thing breaks down: the line through $P$ and $-P$ doesn’t intersect the curve anywhere else, so we don’t get a third point at all. We can circumvent this by thinking of there being an extra point on the elliptic curve, a point which exists at infinity and where all vertical lines meet.

To make this notion clear requires some projective geometry, and this might be a good moment to ask for a leap of faith–it works. To give you some intuition, you could think of our flat plane as being embedded on some very large sphere. Then any two vertical lines we draw will look parallel as seen from within the plane, but if we pull back and see them as being on the sphere, we will see that they all intersect at the north pole of the sphere. Therefore we can think of the north pole as our extra point at infinity, and we call it $\mathcal{O}$. This analogy is very limiting and should really be taken with a grain of salt, but I hope it gives some intuition for what $\mathcal{O}$ is. Now it becomes clear that $P + (-P) = \mathcal{O}$. Furthermore $P + \mathcal{O} = P$, so $\mathcal{O}$ serves as an additive identity.

Lastly, addition of points on elliptic curves defined like this is associative. The bottom line is that the set of points on an elliptic curve with addition is quite similar to the set $\mathbb{Z}_p^*$ with multiplication: it’s a group!

Though the geometric explanation for the group law makes sense, it has its shortcomings: it doesn’t tell us how to compute the coordinates of $P+Q$ in a way a computer could follow, and it doesn’t work when we consider our curve over $\mathbb{Z}_p$. These issues are easily taken care of: since all we’re doing is playing with equations of lines and cubics, we can derive formulae for the coordinates of $P+Q$ in terms of the coordinates of $P$ and $Q$ (I invite the motivated reader to try and find these formulae). Once we have the formulae, we can use them to define addition of points and forget altogether about the previous geometric description.

Elliptic curves over finite fields and our trapdoor function

Let’s actually go through an example of an elliptic curve over a finite field to get a sense of what’s going on. Consider the curve $y^{2} = x^{3} + x$ over $\mathbb{Z}_5$, the integers modulo $5$. We are going to compute all the points on this curve. The way to do this is to plug values of $x$ into the right-hand side and to see if we get a square modulo $5$, in which case we get a solution. For example plugging $x=0$, we get $y^{2}\equiv 0 \bmod{5}$, which has solution $y=0$, so $(0,0)$ is a point on our curve. Plugging $x=1$, we get $y^{2} \equiv 2 \bmod{5}$, which doesn’t have any solutions. Plugging $x=2$, we get $y^{2} \equiv 0 \bmod{5}$, so $(2,0)$ is on our curve.

Continuing like this, we find $(3,0)$ and no other points. We also shouldn’t forget $\mathcal{O}$ (it’s there even over finite fields!). Hence in this case $\mathcal{C}(\mathbb{Z}_5) = \{\mathcal{O}, (0,0), (2,0), (3,0)\}$.

A slightly more interesting example is the curve $y^{2} = x^{3} + 2x + 2$ over $\mathbb{Z}_{17}$. I invite you to check that $P = (3,1)$ is a point on this elliptic curve. If we do some computations (most likely with a computer), we find that $19P = \mathcal{O}$ and that $P, 2P, \ldots, 18P \ne \mathcal{O}$. We say that $P$ has order 19. We also find that $P, 2P,\ldots, 18P$ are all distinct. An interesting question is now: given the point $P$ and a point $kP$ on our elliptic curve, can we find $k$?

The problem is analogous to the discrete logarithm problem, and is called the elliptic curve discrete logarithm problem. Even though it is relatively easy to state, it is very hard to solve, and our methods for tackling it are only marginally better than brute-forcing. This is why we can use smaller prime numbers in the protocol without fear of getting hacked. Choosing a point $G$ on our elliptic curve, our trapdoor function is then $$k \mapsto kG,$$ and we can implement Diffie–Hellman as before:

How much better are elliptic curves?

The whole point of using elliptic curve cryptography instead of ‘classical’ algorithms is that we are able to achieve comparable cryptographic strength with much smaller key sizes. For example, a 228-bit elliptic curve key is equivalent to a 3072-bit Diffie–Hellman key. This means that choosing a 69-digit prime $p$ for our $\mathbb{Z}_p$ in elliptic curve Diffie–Hellman gives us roughly the same security as using a 925-digit prime for regular Diffie–Hellman. As you can imagine, computations are much faster with smaller numbers.

Personally, I think the sheer fact that elliptic curves, which are objects used extensively in pure mathematics, can be impactful in everyday applications is amazing in and of itself!

Are you a mathematician? Care to quantify that?

For decades, mathematicians have been having fun by measuring the collaborative distance between themselves and the most prolific mathematician (in terms of number of individual papers published) to date, Paul Erdős (although he may only be number two; this is disputed).

Your Erdős number is calculated by the shortest collaborative distance between you and Erdős, where 0 is ‘you are Erdős’ and 4 is ‘you published a paper with someone who published a paper with someone who published a paper with someone who published a paper with Erdős.’ He was a favourite amongst people who tell colourful stories about mathematicians and people who write mathematical quotes on coffee mugs alike, widely quoted as saying: “A mathematician is a device for turning coffee into theorems.” Erdős died in 1996, meaning the number of people with an Erdős number of 0 or 1 is now finitely bounded. (Unless you believe in ghostwriting.)

The criteria used to define ‘paper’ and ‘published with’ vary, as you can imagine, but the Erdős Number Project at Oakland University in Michigan, USA, suggests:

Our criterion for inclusion […] is some research collaboration between them resulting in a published work. Any number of additional coauthors is permitted. Not normally included are joint editorships, introductions to books written by others, technical reports, problem sessions, problems posed or solved in problem sections of journals, seminars, very elementary textbooks, books on history, memorial or other tributes, biography, translations, bibliographies, or popular works.

Erdős wrote or co-wrote 1475 papers by this definition. How many people do you think there are with
Erdős number 1? What about 2? See if you can make a reasonable conjecture before I tell you.

There are approximately 511 people with Erdős number 1, and around 11,002 people with exactly Erdős number 2. Were you close? Now, what do you think happens to the distribution of these values as the Erdős numbers increase? See if you can predict the results for Erdős numbers 3 and 4. What do you predict to be the mean and median Erdős number for published mathematicians? What about non-mathematicians (however you define them) —w

What sort of numbers would you expect from them?

A plot of the ‘Erdős function’ using approximate (and restricted) data from the Mathematical Review database in the US. Was it the sort of distribution you anticipated? The mean Erdős number from this data comes in at 4.65 and the median Erdős number is 5.

The Erdős number project at Oakland University has some intriguing things to say, including the revelation that at least one non-mathematician (a medical doctor) has an Erdős number of at most 9 —and that someone once auctioned off an Erdős number of 5 on eBay. There is even a suggestion that there may be a horse with an Erdős number of 3… I went in search of that horse, of course.

Recent work by animal psychologists showing that not only primates but even birds have surprising intellectual capacities, opens the question as to whether non-humans can boast an Erdős number. The answer is indeed yes; the story is however curious.
Jerry Grossman at Oakland University contributed an article to a Bridge magazine, jointly with Smarty, his wife’s horse. As Grossman (Grossman, Jerrold Wayne) has an Erdős number of 2, the horse achieved an Erdős number of 3.’ — The Extended Erdős Number Project

So: if we relax the criteria enough to include almost any publication, then yes, at least one and probably more horses have an Erdős number (please write in if you know of more—the Extended Equine Erdős Number Project sounds like a brilliant plan). This would also mean that the numbers quoted previously would be significantly higher—but only, presumably, above the Erdős number of 1, because Erdős himself didn’t publish much in ‘lowbrow’ places. Does the measure become meaningless if we relax the constraints to this degree? We can turn to several parallels for ideas.

The Bacon project computes an actor’s ‘distance’ from Kevin Bacon in the much the same way, using IMDB. This means that it uses data from a single database of credits on films and TV shows—an imperfect but fairly defined line (does it include cameos? singers? writers and directors?).

Looking further afield, we come to the general principle of ‘six degrees of separation’, originally coined by Frigyes Karinthy in 1929—the idea that in any kind of highly connected network of human relationships or endeavours, the ‘average’ shortest path is six. Watts and Strogatz showed that in ‘small-world networks’, the average path length between two nodes is equal to $\ln N/\hspace{-2pt}\ln K$ where $N$ is the total number of nodes, and $K$ is the number of acquaintances per node.

For example, in 2011 the average distance between people (by number of connections) was 4.74 on Facebook, and 4.67 on Twitter. Of course, here we have pretty discrete rules about connection: the idea of ‘friending’ or ‘following’ on social media is slightly less nebulous than ‘knowing’ in real life. Should we use some kind of index to tell people how connected they are to an arbitrary person of value on social media? It’s likely this would have very little meaning; those sorts of connections, unlike publication credits, are easily obtained and cheaply won.

So it seems that by most reasonably strict definitions, any mathematician worth their salt would expect an Erdős number of around 4 or 5, right?

(I’ve been working up to something. Did you notice?)

Source: 4th Estate

I can remember exactly when I first heard of Erdős. It’s February 2000. I’m 16 years old and for my birthday, someone gets me a book with a weird title: The Man Who Loved Only Numbers. I’m not particularly into men and feel pretty much the same way about numbers (perhaps I’m pi-curious), so I put it into a pile and forget about it for a while. Then, one evening, casting around for new reading material, I pick up the purple and turquoise paperback out of idle curiosity.

I don’t sleep that night. I devour the book like it’s chocolate. I’m thrilled by the portrait of the highly eccentric, highly prolific mathematician who just arrives on each international doorstep with a suitcase and a catalogue of problems to solve, sure of a welcome and a cabal of willing minds. I’m utterly intrigued by the religious overtones of the book; to Erdős, mathematics is inseparable from a kind of fanaticism that inextricably connects him to a higher being who he suggests has written a book of all the perfect proofs in the world (called, somewhat underwhelmingly, The Book). His life’s mission: to discover as many of them as possible. His motto: “my mind is open”.

When he said someone had ‘died’, Erdős meant that the person had stopped doing mathematics. When he said someone had ‘left’, the person had died.

A teenage me, proficient but not amazing at mathematics, dreams of an Erdős number to call my own and all that it might bring: validation, acceptance into a community, that magic label “mathematician”. I’m tired of people not taking me seriously, of calling me a “silly girl”. I have no authority in my little world, and the tales of Erdős and the reverential welcome he gets wherever he goes seem far, far out of reach.

It’s October 2017. Winter is setting in. I’m cold and grumpy. I stumble into work and fire up my computer, opening my email inbox.

Then I sit up straight in my chair and punch the air, thinking ‘what a time to be alive’. This is the email I received on that fateful day:

I have just received my copy of Mathematics Today and see that you have very kindly added my name to your brilliant article. You now have the privilege of having an Erdős number 3, so shout about that! My PhD supervisor published with Erdős when the latter visited Reading many years ago. I have a couple of publications with my supervisor, so I’m a 2!

Let me be clear—this was not a ‘brilliant’ mathematics research paper—it was a very ordinary review article from a conference, where I happened to have credited a kind colleague who read it through and suggested amendments with an entirely earned co-authorship. Nowhere in my wildest dreams would I have imagined that this would be the result. Thrilled is something of an understatement. Somehow, the time and space between me and this ‘real’ mathematician, respected and revered, had been shrunk. I was breathing the same air as Erdős. (Please don’t write in about that, either.)

But of course, after the euphoria had died down, I saw the real truth: while I might feel happy about this numerical value placed on my metaphorical value as a mathematician, it’s in many ways meaningless. The stuff that suggests a person has contributed to the field can be as intangible as a patient explanation to a child or a quick sketch of a unifying structure in the air with a finger. While formal publication is important, it’s not all or even most of what mathematicians do. The focus on getting this type of validation is pretty telling of a group of people who feel insecure, and I’d put actors and mathematicians right at the top of that list, in my humble experience.

What about the veritable army of maths teachers out there painstakingly explaining quadratic relationships for the fiftieth time to the same class? What about the pubfuls of people playing with puzzles and games and origami every month? What about the women and LGBT people and BAME people and disabled people and countless others who don’t get to study to the highest level they like, don’t get picked for the jobs they’re qualified for, don’t get to publish their ideas where they deserve?

This isn’t just an ‘only measuring in one dimension’ problem—it’s a problem of thinking that the product, not the process, is the thing. Translated into education contexts, it’s easy to see why we have generations of children thinking not getting a perfect score on a mathematics exam means they are not a (‘natural’) mathematician.

Put simply: you are not a mathematician because of an Erdős number. Sometimes, you are a mathematician in spite of it.

Do we need a better measure? Nope. We need to stop measuring.

Erdős is widely quoted, and often misattributed—see, for example, the first page of this article, where I suggested he said “A mathematician is a device for turning coffee into theorems”.

Another famously misattributed quote (this time to Einstein) would seem to apply here:

Not everything that can be counted counts, and not everything that counts can be counted. — William Bruce Cameron

A good puzzle leads you to explore unexpected places and discover hidden gems of mathematics – Me, just now

Image: Wikimedia commons user Dougism. CC BY-SA 4.0.

By that reasoning, Catriona Shearer’s puzzles rate extremely highly. Many of them have sent me on an intriguing journey through mathematics, right from the very first that I encountered. The resulting magical mathematical expedition is what I hope to show you in this article.

The puzzle itself is given below. For such a lovely puzzle (as we’ll see), it didn’t get much traction. Indeed, the next day Catriona posted an update with some of her ideas about solving the problem. That second tweet was sufficient to pique my curiosity. After a couple of back-and-forth tweets, I learnt that the problem had been inspired by the bell ringing pattern. With a little time to spare (these were posted in the school holidays!), I set to and investigated. I was pleasantly surprised to find myself embarking on an adventure that started with a morning of bell ringing, continued with a merry afternoon of braiding, and ended the day with a mad dash in a taxi.

Let’s ring in the changes

Those around me have gotten used to me declaring “but that’s mathematics” to the point that they are quick to reply yes, but you say that everything is mathematics”. Which is fair enough: I do have a tendency to think that. But with bell ringing, I’m not on my own in this claim.

In bell ringing, the bells are rung in changes or rows. Each change consists of every bell being rung once in some order. From one change to the next, bells can swap position with a neighbouring bell. We can draw this in the fashion of Catriona’s pictures wherein each row is a change and each bell is a dot in that row. The first diagram below shows three such changes. A picture that doesn’t paint a thousand words is missing something. In this case, it’s very tempting to `join the dots’ and that’s a helpful thing to do as it shows the progression of each bell. Of course, colour is always a welcome addition as in Catriona’s original picture. Indeed, with the colours we don’t need the labels. The second diagram shows the end result.

All tangled up

Images such as the above are reminiscent of braid diagrams. A braid in mathematics is very like a braid in “real life”: it consists of strands travelling in a given direction which can cross over or under each other. The picture below gives a simple example.

If you haven’t encountered braids before, here is a quick precis. They form a part of both topology and algebra. In topology, they are closely related to knots and links. Knots in mathematics model knots in the `real world’, the main difference being that we join the ends to stop them undoing themselves. Links generalise knots in that they can have multiple strands. A braid can be made into a knot or a link by joining the strands from the bottom back up to the top and the crossings of the braid then create the knottedness of the resulting knot. Braids also find a place in algebra. The set of braids on a fixed number of strands forms a group, with the group operation being concatenation: placing one braid after another. These groups have a lot of structure which provides a rich source of study.

Knots, links, and braids have many applications both in wider mathematics and further. One such application is in the study of DNA: the helix structure of DNA makes it naturally braided. When DNA is replicated as part of cell division, it remains tangled so has to be untangled for it to properly separate and be able to pass into the two new cells. There is a particular enzyme that does this, so a mathematical concept—unlinking—is realised by a particular biological process.

The bell ringing diagrams are not quite braid diagrams, however. The difference is that in bell ringing there is no information as to which strand crosses over which. Despite the temptation of modelling the swaps by actually intertwining the bell ropes, this would quickly lead to them being unringable. There is no movement in the swaps in bell ringing and so there is no obvious choice of which strand should go over which.

There are a variety of ways that the choices could be made, and readers might find it an interesting diversion to come up with rules to follow and to see what different braids result from the same bell ringing diagram. In what follows we will be most interested in something called the linking number of two strands. This is a concept on loan from the theory of links which measures how intertwined two strands are. It is straightforward to calculate with braids: pick two strands and follow them down the braid diagram. Each time they cross count 1 if the right crosses over the left and -1 if the left crosses over the right. At the end, halve the number. This is the linking number of the two strands. Some examples are given above, showing why it measures their entanglement.

A very simple rule to use when converting a bell-ringing diagram to a braid diagram is to make every crossing “right over left”. This would ensure that the linking number between any two strands is as large as it can be. A possible line of enquiry would be to see how the linking number is affected by other choices of rule. With this rule, Catriona’s original puzzle translates to the braid shown above.

Enter the taxi

The original problem asked about the area swept out between two strands as the braid progresses. (It is worth pointing out that this doesn’t depend on the choices of crossings in the braid.) There was also the “must swap if possible” rule but we can equally well work with patterns that don’t have that property. We shall, however, assume that our braids are drawn in the more angular fashion of the original braid, which matches the style of the original problem.

To talk about area, we need to decide on some units. We’ll assign length 1 to everything atomic: the horizontal distance between adjacent strands and the vertical distance between the lines corresponding to the bells being played. Now let’s look at two strands, say the red and orange strands. The first part of their journey looks like a trapezium, as in the following picture.

Our choice of units make the area easy to calculate: it is simply the average of the two horizontal sides. More generally, for any two strands then the area of one segment where they don’t cross is the average of their horizontal distances at the start and end of that segment. The crossings behave differently, see the picture below. In this case, the area given by the above rule is 1 but the actual area is 1/2. As is common in mathematics, we’ll make that 1/2 look more complicated to make life simpler later on. We’ll write it as 1 – 1/2 where we think of the 1 as being the area given by the trapezium rule and the -1/2 a correction for the crossing.

To see what this looks like, let’s establish some convenient notation. We’ll convert each thread in the braid into a list of numbers. These will record the position of each strand as it passes down the braid. Equivalently, the list is of the position of the bell in each change. The lists for the braid above are (from left to right):

\begin{align*}
1 2 3 4 5 5 4 3 2 1 1 \\
2 1 1 2 3 4 5 5 4 3 2 \\
3 4 5 5 4 3 2 1 1 2 3 \\
4 3 2 1 1 2 3 4 5 5 4 \\
5 5 4 3 2 1 1 2 3 4 5
\end{align*}

Notice that the last change is the same as the first. Let’s look at the calculation of the area between the first two strands. Separating it by change, it is:

\begin{align*}
{|2 – 1| + |1 – 2|}/2 &- 1/2  \\
+ {|1 – 2| + |1 – 3|}/2 &    \\
+ {|1 – 3| + |2 – 4|}/2 &    \\
+ {|2 – 4| + |3 – 5|}/2 &    \\
+ {|3 – 5| + |4 – 5|}/2 &     \\
+ {|4 – 5| + |5 – 4|}/2 &- 1/2 \\
+ {|5 – 4| + |5 – 3|}/2 &      \\
+ {|5 – 3| + |4 – 2|}/2 &      \\
+ {|4 – 2| + |3 – 1|}/2 &      \\
+ {|3 – 1| + |2 – 1|}/2
\end{align*}

What is important to note in this is that the second term in each fraction is the first term of the next. This even works with the last and first terms. Writing $u^a$ and $v^a$ for the terms in each list, we therefore have that this part simplifies to
$$
\sum^{10}_{a=1} |u^a – v^a|$$

Note that we’ve used the fact that the first and last terms in our lists are the same here. The other part is the linking number of these two strands, at least the way that we’ve drawn the crossings. As the area doesn’t depend on the choices of crossings then this might not always be the linking number of the given choices. What we can say is that it is the maximum linking number. Let’s write this maximum linking number of the strands which start at positions $i$ and $j$ as $Χ_{i,j}$.

Now let us return to the first part of the expression for the area, given in the equation above. This is where the taxis arrive. The taxicab metric—more formally known as the $\ell^1$ metric—is a way of measuring distance between points. In 2D, the image is of points laid out on a grid, much like a city such as New York, as in the next diagram. You can move along the lines on the grid but you can’t move across them. The distance between two points is therefore not the standard Euclidean distance but a different formula. More prosaically, it is not “as the crow flies” but rather “as the taxi drives”. The distance between the two points in the diagram to the right is 2 + 1 + 2 + 2 = 7. No matter what choice of route, no shorter distance can be found. This gives rise to the formula for the taxicab distance between two points $a=(x_a,y_a)$ and $b=(x_b ,y_b)$ as:
$$|a – b|_1 = |x_a – x_b| + |y_a = y_b|$$
There’s nothing special about 2D here. The analogous formula holds with arbitrary length vectors. Thinking of a vector as just a list of numbers (i.e. without trying to assign any physical meaning to the directions), our listing for each strand of our braid gives a vector.
The expression in the above equation shows that we should drop the repeated ending position and so the vectors from the braid in Catriona’s original puzzle are of length 10. Our vectors from that braid are therefore:
\begin{align*}
v_1 &= (1,2,3,4,5,5,4,3,2,1) \\
v_2 &= (2,1,1,2,3,4,5,5,4,3) \\
v_3 &= (3,4,5,5,4,3,2,1,1,2) \\
v_4 &= (4,3,2,1,1,2,3,4,5,5) \\
v_5 &= (5,5,4,3,2,1,1,2,3,4)
\end{align*}
The area formula then simplifies to: $A(v_i,v_j) = |v_i – v_j|_1 – Χ_{i,j}$. Calculating this for the above vectors (exploiting a bit of symmetry to avoid too many calculations), we get:

\begin{align*}
A(v_1,v_2) &= A(v_2,v_4) = A(v_4,v_5) = A(v_5,v_3) = A(v_3, v_1) = 15 \\
A(v_1,v_4) &= A(v_4,v_3) = A(v_3,v_2) = A(v_2,v_5) = A(v_5,v_1) = 23
\end{align*}

In conclusion, the area between two strands is given by taking the taxicab metric applied to the corresponding vectors and then subtracting their maximum linking number.

And finally

As I said at the outset, the mark of a good problem is that it gives you the opportunity to travel in mathematics.
This particular problem took me on a meandering wander through some parts of mathematics that I know well, but that I hadn’t realised were so closely connected. It is easy to forget how intricately connected mathematics is, and I find expeditions such as this one help to remind me of this.

While I knew of the connection between bell ringing and braids, I certainly wasn’t expecting to see the taxicab metric making an appearance.

Moreover, its role here is to calculate an area whereas its natural home is as a way to measure length, so it also served to remind me that area and length are more closely tied together than I often allow. This journey has also led me to places that I’d like to revisit when I have a bit more time. For example, the relationship between bell ringing and braids is not quite as I’d thought: I hadn’t realised the significance of the crossings. So there’s plenty to explore further with trying out different crossing rules to see what braids appear. Plus it gives me an excuse to draw some more braid diagrams, which is always a bonus.

This article is inspired by a puzzle from Catriona Shearer. The central council of church bell ringers is always looking for mathematically-minded recruits! Find them at cccbr.org.uk.

I originally wrote this piece as my semi-final entry for the Big Internet Math-Off, an online competition run by the Aperiodical. The knock-out tournament saw $2^4$ mathematicians go head-to-head in presenting ideas they found particularly interesting. Each round readers voted for their favourite of $2^1$ entries, with the winner advancing to the next round, until only $2^0$ participant emerged victorious.

The audience was given the brief to vote for the entry that made them ‘do the loudest “aha!”‘ This ‘aha!’ success criterion seemed entirely fitting since our response to mathematics is often exactly this; involuntary, emotional and beyond the reach of words. As such, when asked ‘why do you like mathematics?’, I always feel words cannot fully capture quite what it is to find something mathematically satisfying, or mathematically beautiful.

But mathematics itself is the opposite; using maths we can convey huge ideas, completely, and efficiently. When we look at things mathematically it is like we are casting a perfect light on to the world that allows us to see the very structure and essence of things.

I chose to write about the phantom parabola because it demonstrates this power; by using mathematics (in a simple, ‘aha!’-inducing way) we reveal something that was otherwise hidden. I introduce the phantom parabola as a ghost story, in a blatant clickbait-esque attempt to make people read on and vote. But as this is a story about invisible mathematics that genuinely gives me the goose bumps, as well as an ‘aha!’, I think my claim is justified.

Continue reading →

We bought a new toy for our three-year-old, a robot caterpillar. This has a head and eight segments which tell the caterpillar to perform actions like moving and playing music. A caterpillar is formed by the head, always at the front, followed by at least one segment. These form an ordered set of commands which are executed in sequence.

This is a fun toy which principally involves colourful lights and music, while also developing some logical thinking and proto-programming skills in 3– 5-year-olds. But that’s not why I’m writing about it.

On the packaging is made the following claim, acting for me like a red rag to a bull:

“8 pieces. Endless combinations!”

A robot caterpillar

This cannot possibly be true. You cannot arrange eight pieces endlessly and never repeat the same combination. This isn’t how infinity works.

My son is quite into counting, though he becomes a little inconsistent around “five-teen” so perhaps swapping segments into place and counting them isn’t the way to go about this. Thankfully, mathematics has an answer: combinatorics.

Some combinatorics fundamentals

Imagine you have three tiles containing letters A, B and C, and you want to know how many different ways you can arrange these.

Six rearrangements of three different tiles labelled A, B and C.

Notice that there are three options for which tile to place first: A, B or C. Once one of these is chosen, there are two options for which tile to place second. In the first two rearrangements A is placed first leaving two options for which to place second: B or C. Once either is chosen, there is one option remaining for the third and final tile.

This means that there are $3! = 3 \times 2 \times 1$ options for arrangements of three different tiles. This logic continues for any number of tiles, indeed any number of objects. The number of ways of arranging $n$ objects is

$$n\hspace{1pt}!=n \times (n-1) \times (n-2) \times \ldots \times 3 \times 2 \times 1 \text{.}$$

Let’s consider a different problem: say you have a bag of three balls labelled with letters A, B and C, and you want to know how many different ways there are of pulling two balls out of the bag. In particular, imagine you aren’t interested in which order the balls came out of the bag (as is the case in, say, a lottery).

At first, this may appear very similar to the tiles. There are three choices for the first ball, then two choices remaining for the second ball, then one choice for the ball left in the bag. That’s $n\hspace{1pt}!$, and for three balls the $3!=6$ options are listed here:

Six ways of choosing two balls from three labelled A, B and C.

However, if you look at the pairs of balls just above, you will notice that we are counting some twice. Whether you draw A and then B or B and then A, you are still holding A and B at the end of the draw. Actually, there are only three different ways to draw two balls from three. To see how this works for a larger case, consider a bag with ten unique balls from which you desire to draw three, and you aren’t interested in the order of the three.

You could consider drawing balls to be an act of arranging objects: arrange ten balls into a line and then ‘draw’ the three leftmost balls. Doing so, you arrange the balls into two groups: the three you have drawn and the seven you have not.

Arranging ten balls and drawing three of them.

There are $10!$ ways to arrange these ten balls. But within these $10!$ arrangements, there are $7!$ that simply shuffle the balls left in the bag, which doesn’t affect which three are drawn. So we are down to $\frac{10!}{7!}$ arrangements. This represents all possibilities for drawing three balls from the bag. If we aren’t interested in the order that these three are drawn, then we can further reduce this number by $3!$, the number of ways of arranging them. This gives a formula for the number of ways of drawing three balls from ten when the order of the three drawn isn’t important:

$$\frac{10!}{3! \times 7!} = 120 \text{.}$$

In general, the number of ways of choosing $r$ objects from $n$ without repetition when we don’t care about the order of the objects chosen is

$$\frac{n\hspace{1pt}!}{r\hspace{1pt}!(n-r)!}\text{.}$$

This is the binomial coefficient and can be written using the notation $\displaystyle\binom{n}{r}$.

The binomial coefficient, and the fact that there are $n\hspace{1pt}!$ ways of arranging $n$ objects are key tools at the heart of combinatorics.

We can get very surprising and unintuitive results through combinatorics. I used to give a talk about coincidences which started with two counting problems—the birthday problem and shuffling cards (see the sidebars on this page and the previous page for descriptions of these problems). Though I know the methods involved and intellectually it makes sense, I still find it hard to genuinely, intuitively appreciate that if I collect $23$ unconnected people, there is a $50\%$ chance that two of them will share a birthday. Meanwhile, I find it really hard to (genuinely, intuitively) believe that a bunch of cards I’ve just thrown on a table are arranged in a way such that it is extremely unlikely any pack of cards has been arranged in the history of the universe. Such is the nature of combinatorics, which offers techniques to address counterintuitive counting problems.

Back to the caterpillar

With eight segments to arrange, it feels to me like there can’t be very many different ways to arrange these. But, as I know, numbers in these sorts of problems are counterintuitively large. Let’s put an upper bound on the number, anyway, to dispute the `endless’ claim.

If all eight segments were different, for sequences using $k\leq 8$ positions, we choose $k$ segments from the $8$ possible segments and there are $k\hspace{1pt}!$ ways to arrange these, so the number of possible sequences would be

$$\binom{8}{k} k\hspace{1pt}! = \frac{8!}{(8-k)!} \text{.}$$

Notice that for $k=8$, this reduces to $8!$, as you might expect.

The number of possible sequences using any number from $1$ to $8$ segments would be the sum of this arrangement for all possible lengths, ie

$$\sum_{k=1}^{8} \frac{8!}{(8-k)!} = 109600 \text{.} $$

I think you’ll agree with me that $109,\!600$ is significantly smaller than infinity. For this problem, though, it’s definitely too large.

But it isn’t that simple

The caterpillar has three identical segments which instruct it to move forwards, two to turn left, two to turn right and one to stop and play music.

For the avoidance of doubt, some other features and restrictions:

• there are eight positions that can hold segments, the head is always present;
• any number of segments from $1$–$8$ may be used, and not $0$;
• the order of segments matters, because it is a sequence of commands;
• segments are connected (by USB), so there can be no gaps in a sequence—if a position is unfilled, the caterpillar ends at the preceding segment.

Let the forwards segments be labelled $F$, the left $L$, the right $R$ and the music $M$, and let a sequence be denoted by a string of letters from left to right (eg the head, not denoted, is on the left of the string). Then some examples of valid caterpillar sequences would be $FFFM$, $FFMF$, $FLRFLRFM$, $LRL$, $F$, and so on.

In the simple analysis that led to the upper bound $109,\!600$, we were over-counting the cases where multiple $F$, $L$ and $R$ segments are used. For example, the sequence $FF$ would be counted twice, even though they produce functionally identical caterpillars.

There is a neat trick in combinatorics for counting in this kind of circumstance-generating functions.

Generating functions-an example

Say I have three cards, two blue and one green, and I want to know how many ways I can arrange them into sequences of length 1-3. This is fairly straightforward to enumerate by hand, as you can see here.

For a generating function approach, I assign two functions. For green, I use $1+g$. Think of this as the $1$ representing no green card being selected and $g$ representing one green card being selected. For blue, I use $1+b+b^{\hspace{1pt}2}$. Similarly to green, $1$ and $b$ represent no blue cards and one blue card, with $b^{\hspace{1pt}2}$ representing two blue cards being selected.

Now we simply multiply the two functions together.

$$(1+g)(1+b+b^{\hspace{1pt}2}) = 1+b+b^{\hspace{1pt}2}+g+gb+gb^{\hspace{1pt}2}$$

Arrangements of two blue cards and one green card of length 1, 2 and 3.

Each term of the expansion represents a selection from the set of three cards. For example, $g$ represents choosing one green card only for the sequence `green’, and $b^{\hspace{1pt}2}$ represents choosing just the two blue cards for the sequence ‘blue, blue’. The term $gb$ represents choosing one green and one blue card, and there are $2!=2$ ways to arrange these two cards: ‘green, blue’ and ‘blue, green’. We didn’t have this rearrangement problem with $b^{\hspace{1pt}2}$ because the two blue cards are identical. The term $gb^{\hspace{1pt}2}$ represents choosing all three cards. There are $3!$ ways to arrange three cards, but $2!$ of them are the same, because the two blue cards are identical. So we can arrange $gb^{\hspace{1pt}2}$ in $\frac{3!}{2!}=3$ ways. The final term in our expansion is $1$, which represents choosing none of the cards. Whether this is a valid sequence depends on the context and the rules you are following.

Generating caterpillars

Since there are three $F$ segments, we can use the function $1+f+f^{\hspace{2pt}2}+f^{\hspace{2pt}3}$ to represent these. For the two $R$ segments, use $1+r+r^{\hspace{1pt}2}$, and for the two $L$ segments use $1+\ell+\ell^2$. Finally, for the one $M$ use $1+m$.

To find out how many different ways there are of selecting from these segments, expand $(1+f+f^{\hspace{2pt}2}+f^{\hspace{2pt}3})(1+r+r^{\hspace{1pt}2})(1+\ell+\ell^2)(1+m)$. The expansion has $72$ terms, each representing a different caterpillar. One of these, however, is formed by multiplying the four $1$s together to get $1$, which represents selecting no segments. Since this isn’t a valid caterpillar (the toy doesn’t work using only the head), there are $71$ different ways of forming caterpillars up to length $8$.

For example, one of the terms of the expansion is $f^{\hspace{2pt}3}r\ell^2m$. This represents choosing $F$, $F$, $F$, $R$, $L$, $L$ and $M$ for a caterpillar of length $7$. A caterpillar of length $7$ can be arranged $7!$ ways, but some of these are duplicates; how many depends on which segments are involved. In this case, a caterpillar involving three $F$s, an $R$, two $L$s and a $M$ can be rearranged $\frac{7!}{3!2!}=420$ different ways, with $7!$ divided by $3!$ for the three identical $F$s and $2!$ for the two identical $L$s.

We complete this calculation for all $71$ valid selections of segment arrangements. The total number of possible caterpillars is 5023.

So the “endless combinations” claimed on the packaging is, in fact, a little over five thousand possible caterpillars. Not endless, but certainly enough to keep us busy for a while! Oh, and the manufacturer sells add-on kits containing extra and different segments, which opens up whole new worlds of combinatorics possibilities…

If you are interested in a gentle-but-thorough introduction to combinatorics, I heartily recommend Robin Wilson’s Combinatorics: A Very Short Introduction.

Go ahead and try to solve this little problem! Or, even better, grab a friend (or enemy) and think about the problem together.

Continue reading →