post

On √2

One of the first theorems lots of students see is that the square root of two is irrational (ie not a fraction). Therefore, we cannot restrict our attention to rational numbers only. Clearly $\sqrt{2}$ is a number we must have, as by Pythagoras’ theorem it represents the length of the hypotenuse of a right-angled isosceles triangle with vertical sides $1$. What the theorem says is that $\sqrt{2}$ is never $x/y$ with $x$, $y$ integers. Or, to put it another way, $$2\ne \frac{x^2}{y^2}\Leftrightarrow x^2\ne 2y^2,$$ that is, the square of an integer is never twice the square of another integer. However, they are both integers. The closest they can be apart is $1$, ie $$x^2-2y^2=\pm 1.$$ This is the simplest form of Pell’s equation: $x^2-Ny^2=\pm 1$. When $N =2$, one can easily find a solution in the integers $(x, y)=(1, 1)$. With a little more thinking we find the solutions

$(x, y)$ Why?
$(1, 1) $ $1^2-2\cdot 1^2=-1$
$(3, 2) $ $3^2-2\cdot 2^2=+1$
$(7, 5) $ $7^2-2\cdot 5^2=-1$
$(17, 12)$ $17^2-2\cdot 12^2=+1$

Continue reading

post

Spotlight on: Pamela Harris

As far as Pamela E Harris knew when she was growing up, there were no Latina mathematicians. Through almost 20 years of schooling she had never met one. Then, one year shy of earning her PhD, she did. It meant a lot to know that she wouldn’t be the only one. The lack of role models who shared a similar heritage and background made Harris’ experience one of isolation. She says she feared that she wouldn’t be able to succeed as a mathematician. However, in 2012 when Harris attended a meeting of the Society for the Advancement of Chicanos/Hispanics and Native Americans in Science (Sacnas), it changed her life. She is now part of a large, supportive community that uplifts and helps each other become leaders in their respective fields.

The making of a mathematician

Partitioning an integer involves dividing it up into smaller parts. Image: Flickr user MTSOfan, CC BY-NC-SA 2.0

Harris spent her childhood in Mexico and emigrated to California with her family when she was eight. Things were rough financially and, after a short return to Mexico, her family emigrated to Wisconsin. There, she attended Marquette University, and it’s here that she began to think seriously about becoming a mathematician. She says, “During my fourth year as an undergraduate student, my real analysis professor said, ‘When you go to graduate school…’. With this comment alone, she changed the course of my life. Her comment started me on the path to graduate school but, more importantly, her belief in my ability to succeed motivated me for years past the start of my graduate programme.”

Harris attended the University of Wisconsin-Milwaukee where she earned a masters, then a PhD in mathematics. Her research interests became algebra and combinatorics. She explains her work in this way: “Consider the following combinatorial problem: In how many ways can the positive integer n be written as a sum of positive integers (ignoring the order)?” For example, the number 3 can be written in the following three ways: 3, 2 + 1, 1 + 1 + 1. “Although this process is simple, determining a formula for the partition function, which counts the number of integer partitions of n, eluded generations of mathematicians and was only recently solved by Ken Ono, Jan Bruinier, Amanda Folsom, and Zach Kent in 2011. Their formula relied on the new and surprising discovery that partitions are fractal in nature.”

Finding formulae

Now an assistant professor in the department of mathematics and statistics at Williams College in Massachusetts, Harris researches vector partition functions and graph theory: work that has been supported through awards from the National Science Foundation and the Center for Undergraduate Research in Mathematics. A vector partition function computes the number of ways that one can write a vector, say v, by summing given vectors {a1, a2, …} in such a way that the coefficient of each ai is a non-negative integer. For example, one could ask, how many ways are there to make £5 from standard British coins? In this case the (one-dimensional) vector v is 5 and the set of given vectors ai is just the set of coin denominations: {2, 1, 0.5, 0.2, 0.1, 0.05, 0.02, 0.01}.

Harris says, “Vector partition functions have many interesting properties, but finding formulae for vector partition functions is also very difficult.” In particular, Harris has worked on a vector partition function known as Kostant’s partition function which is important for representation theory. Representation theory is a branch of mathematics that tries to solve problems about abstract algebraic objects by representing their elements as matrices, which are easier to work with. In the case where the abstract object is a Lie algebra (pronounced ‘Lee’) understanding the representation turns out to involve combinatorics and Kostant’s partition function.

Inspiring the next generation

Fields medallist Artur Avila is one of the best-known Latin American mathematicians.

Harris also enjoys working with undergraduates on mathematical research. “I find that many undergraduate students do not know what mathematical research is about, or how one does research. Working to help them understand how as a mathematician we can take a problem and generalise it further to find new results, is one of the most rewarding aspects of my job.”

“Mathematics has taught me to be patient, to work hard and to be resilient. I know most times I will fail to answer the questions I pose, but I do know that along the way I will grow and develop new insights.”

Being Latina, an immigrant and the first in her family to graduate from university, Harris is firmly and actively dedicated to improving diversity and retention rates among women and minorities in science, and in mathematics in particular. She travels widely – her favourite perk of being a mathematician – to share research findings and to co-organise research symposia and professional development sessions for the national conference of Sacnas. She was a Project NExT (New Experiences in Teaching) fellow from 2012 to 2013, and is an editor of the e-mentoring blog of the American Mathematical Society. Her work has created new research opportunities for underrepresented students that support and reinforce their identity as scientists. In 2016, she helped develop and create the website lathisms.org, an online platform that features the extent of the research, teaching and mentoring contributions of Latinxs and Hispanics in the mathematical sciences.

Impact beyond mathematics

Harris (back centre) with her students. Image: Lisa Jacobs.

Harris is grateful for the support of her community and her mentors, including that first analysis professor who gave her her early self-belief. “I have been very lucky to be surrounded by peers and mentors. They often remind me that as a Latina mathematician, my work has an impact outside of the walls of my institution and that I can make a difference in the mathematical community. Their support has been invaluable throughout my career, and I am grateful to have them in my corner. I certainly wouldn’t be where I am today without them.”

post

Artificial music

Out of all the words in the English dictionary, art is possibly the one with the most debatable definition. In his 1897 book What Is Art?, Russian writer Leo Tolstoy argued that “art begins when a person, with the purpose of communicating to other people a feeling they once experienced, calls it up again within themself and expresses it by certain external signs”. An important aspect in Tolstoy’s argument is that of the artist’s sincerity—that is, the extent to which the artist has experienced the feeling that they are expressing—which is crucial in determining the appreciation of the work by others.

Contrary to Tolstoy’s belief is the one popularised by the French writer Théophile Gautier in the early 19th century, summarised in the slogan l’art pour l’artart for art’s sake. For Gautier, the intrinsic value of a work of art has to be completely detached from any sort of sentimental, social or moral context.

New technologies add a layer of complexity to the old and neverending discussion about what should be considered art. What would the conversation between Tolstoy and Gautier be like after having been presented with one of Emmy’s musical compositions? Emmy, short for ‘Experiments in Music Intelligence’, was created in 1981 by David Cope, nowadays professor emeritus at the University of California, Santa Cruz. Cope, who was suffering from composer’s block, wanted to build software able to generate new material in line with his own pieces, using these pieces as the main input for the software. However, due to the lack of personal works, he started by taking the pieces of various classical composers as the input for his computer programs instead. After spending some time perfecting Emmy, Cope was able to produce, in a matter of minutes, thousands of new instances of music in JS Bach’s style. This resulted in the 1993 release of Bach by Design, one of his several computer-generated music albums.

Since Cope’s days, music-generating systems using artificial intelligence have experienced big advances. Nowadays, there are all sorts of user-friendly systems: IBM Watson Beat, Google Magenta’s NSynth Super, Jukedeck, Melodrive, Spotify’s Creator Technology Research Lab, Amper Music, and so on. Some music systems, like Amper, have explicitly been taught the rules of music theory. However, most AI music systems use artificial neural networks to generate output. The neural networks identify patterns from the multiple samples of source material they are fed with. These patterns are then used to create new music in the form of an audio file or a music score. While some systems will simply create a melody from a given note, others are able to harmonise a given melody.

A chorale harmonisation or a chorale is a musical piece traditionally intended to be sung by a congregation during a German Protestant service. It is often written for soprano, alto, tenor and bass. The soprano is the voice that holds the melody, which is usually a Lutheran hymn tune, while the other three voices provide the harmony.

 

For a taste of what AI is capable of doing, you can have a look at the Google Doodle from 21 March 2019, celebrating Bach’s 334th birthday. Coconet is the machine learning model that makes this Doodle work. Trained with a relatively small dataset of 306 choral harmonisations by Bach, Coconet can harmonise a melody entered by the user in Bach’s contrapuntal style in a matter of seconds. The mechanisms behind the Doodle are explored in the following section.

Coconet in a nutshell

Coconet’s task involves taking incomplete musical scores and filling them up with the missing material. For the result to be loyal to Bach’s style, Coconet needs to first be trained to know what is the ‘right’ style. This training is done by randomly erasing some notes from the original chorales composed by Bach and asking Coconet to reconstruct the erased notes. A rank is given to quantify the accuracy of Coconet’s version with respect to Bach’s. Coconet will then be encouraged to repeat high-ranked guesses in future reconstructions of incomplete music scores, while trying to avoid low-ranked guesses.

So how is the music extracted from probability distributions? One could think naively that it is OK to just pick the pitch which corresponds to the highest probability assigned to the missing notes for each voice independently. However, Bach chorales are all about harmony and harmony is all about interactions between notes; the melodic lines of the different voices cannot be considered in isolation.

To account for these interaction effects, there are several solutions. Perhaps the most obvious one would be to assign the highest probability pitches to one of the voices, and then feed Coconet with this new version of the incomplete chorale. The model would update the probability distributions for the other voices. The process could then be iterated until all the voices are complete. Although it is simple, this solution is not ideal; very different results might be obtained depending on which voice is completed first.

Coconet opts for a more robust solution. At first, all the pitches in the incomplete chorale are filled up simultaneously according to the highest probabilities for each of the individual voices. But this result is just taken as a draft. Then, some of the guesses are randomly erased and the new incomplete chorale is fed into Coconet again. New probability distributions are obtained for the new gaps. The process, called blocked Gibbs sampling, is repeated until the probability distributions given at consecutive iterations of the process are similar enough to always give the same pitch.

The diverse opinions about the final products are as interesting, if not more, as the mechanisms behind AI-generated music. The audience’s reaction to artificially generated music was spectacularly tested at the University of Oregon in 1997. There, the pianist Winifred Kerner performed three pieces: one written by her husband, the composer Steve Larson; another one written by Bach; and the last one, generated by Emmy. After her performance, the audience was asked to guess which was which. To Larson’s despair, the audience concluded that his composition had been created by Emmy and that Emmy’s work was genuine Bach.

Larson was not the only one feeling uncomfortable about the fact that Emmy had been able to fool a whole audience. American professor of cognitive science Douglas Hofstadter, author of the 1979 Pulitzer prize-winning book Gödel, Escher, Bach, had argued a machine “would have to wander around the world on its own, fighting its way through the maze of life and feeling every moment of it” in order to produce anything similar to the masterpieces. In a 1997 article published by the New York Times, he claimed that the only comfort he could take from Larson’s experiment in front of the audience was that “Emmy doesn’t generate style on its own. It depends on mimicking prior composers”.

The introduction of this sort of sophisticated and yet easy-to-use system not only opens a philosophical discussion on what should be called art, but it also brings in an ethical problem. In 2017, music-streaming service Spotify hired AI researcher François Pochet as the new director of the Spotify Creator Technology Research Lab. The hiring added even more weight to the accusation made by the magazine Music Business Worldwide that the platform had launched several playlists authored by fictional artists. These playlists, with around 500 million streams, were mood-themed with titles such as ‘peaceful piano’ or ‘ambient chill’: precisely the kind of atmospheric musical genres that AI is really good at generating. If this music had been created by Spotify’s AI, it would mean that they could have avoided paying royalties to the rights’ owners, as technically nobody would be the owner of this artificially created music. For the amount of streams that the playlists received, the cost would be in the range of \$3m. In the end, Spotify declared that the music in the playlists was actually composed by real artists and that they were being paid the corresponding royalties.

AI-generated music is controversial, but also exciting. AI is clever enough to generate short fragments of music in the style of Bach’s chorales. Indeed, despite the expressiveness in these pieces, the composition techniques used by the German genius to compose them tend to be rather algorithmic. It is also clever enough to create nice atmospheric music. However, AI still has a lot to learn in order to be able to produce a masterpiece in its own developed style, let alone the interpretation aspect. It will be a few years until the rise of a new Leonard Cohen. But AI is on the right track. As Pablo Picasso once put it: “Good artists borrow, great artists steal”… and this is precisely how machine learning works!

post

They might not be giants

“If I have seen farther,” the scientist said,
“it’s not because I am a giant.
“Great minds of the past have helped me get ahead;
it’s their shoulders on which I’m reliant.”

“Now listen to me!” said the great on whose shoulder
the first one was glad to have stood.
“I’m quite short of stature, it’s just that I’m older
and those before me were so good.”

And sure enough, this one was perched on the neck
of a giantist of great renown
who balanced in turn on another; by heck!
It’s little guys all the way down.

And some were thought giants, and some were thought midgets
and some were thought nothing at all,
but each would insist, “Those below were no idjits.
It’s them that have made me so tall.”

And scrambling around them their fans would aspire,
to see something not seen before
by climbing the tower of dwarves, ever higher
for glimpses, or footholds, or more.

Most could not scale to the summit in time,
before their peak fitness would end.
Some found it tough and abandoned the climb
while some would, with vigour, descend:

Aware that such heights were so taxing to reach,
they helped to lift people and hopes,
inventing new ladders and platforms to teach,
securing and showing the ropes.

“They might not be giants, but they must go far
and that journey isn’t for me.
I’ll boost them through science, raise them and the bar
and profit from what they will see.”

So said the teacher while lifting a child
on shoulders so humble and stressed.
The youth saw a vista that had them beguiled
and bounded straight up to the crest.

post

Crocheting fractals

Ever since getting into the mathematical field of really cool shapes (I think some call it ‘topology’), I’ve been keen to bring as many of these shapes to life as possible. When you’re holding a shape in your hands and it still doesn’t make sense in your head, that’s when you know you’ve encountered one of the best. My method of choice for making these shapes is crochet. It’s essentially a way of connecting a series of loops of yarn to gradually build up a surface. Before I start, I have to mention the book Crocheting Adventures with Hyperbolic Planes by Daina Taimina: it’s what got me into mathematical crochet, and it goes into a lot of detail about geometry as well as providing plenty of patterns to try out.

However, as much as I love them, hyperbolic surfaces aren’t going to be the topic of this article. The crocheting project I’m going to discuss instead is one which I developed myself, after my love of making cool shapes had been going on for a little while. At this point, I’d played around with various circle circumference functions, crocheted ‘integrals’ and ‘derivatives’ of the same function, and made Möbius strips, but what I really wanted to try and create was some kind of fractal.

Choosing the fractal was easy enough: I wanted something that was made using a relatively simple rule, and didn’t get too squiggly to be difficult to make a decent approximation of. The Koch curve, for instance, despite being simple, gets very squiggly and has a lot of angles and turns. Likewise, the dragon curve, beautiful as it is, has nowhere for the yarn to attach to so we cannot create a continuous surface. In the end, I settled on Sierpinski’s triangle. It’s simple, it’s modular so I could potentially make smaller pieces and sew them together, and all the points are connected to each other.

The next question, then, was how? I decided to keep it simple: I wanted to make a long chain, and by connecting it to itself at certain points using slip-stitches, I wanted to trace out all the lines of the triangle.

For non-crocheters, a ‘chain’ is exactly what you imagine: it’s just a long line of loops all linked to the next. A slip-stich is like adding an extra loop, except not only is the loop linked to the whole chain behind it, it’s also connected to the crochet at another point. I’ve drawn a few sets of diagrams below so you can picture what goes on.

From left to right. Creating a chain: The yarn is looped around the hook, then pulled through the previous loop. Repeating this forms a chain. Making a slip-stitch: The hook is inserted into a stitch in the chain, then the yarn is looped around the hook. The yarn is then pulled through both stitches to form the image on the right..

At this point, I’d figured out what I wanted to make and how. One thing I didn’t know, however, was if it was even possible. Can you create Sierpinski’s triangle by making a chain and attaching it to itself at certain points using slip-stitches? You can simplify the problem a little bit by removing the context of crochet from the equation, and just thinking about drawing a continuous line that connects to itself at certain points. In other words: is it possible to draw Sierpinski’s triangle in one continuous line? If so, then I’d be able to trace the path of the line with crochet, and create it. It might be fun to stop reading here and have a go at solving this problem yourself.

As soon as I realised this was a problem about tracing a shape with one continuous line, my mind went straight to graph theory. Graph theory is another area of maths which I adore (my interests seem to be anything that isn’t in the A-level maths syllabus), so I was very excited to be using it to solve a genuine real-world problem I’d come up with. It’s the study of nodes and the connections between them, and is often used to figure out the best route between places (by modelling locations as nodes, and roads as the connections). I decided to start by modelling the basic first iteration of the triangle as a graph, or a series of nodes and connections, as you can see on the left on the next page. Using the draw function on Excel (which has the handy property of allowing you to ‘replay’ your drawing, so you can watch the path being traced again), I had a quick go at tracing the lines, and found a solution, as you can see on the right:

Of course, a proof consisting of one example for one iteration wasn’t going to be sufficient, but at least I had some evidence that it was probably going to be possible. This was the point where I decided to properly bring out the graph theory, and apply an idea first proposed by Euler when he was solving the Seven Bridges of Königsberg problem.

The Seven Bridges of Königsberg is a fairly famous problem. A series of seven bridges all cross the river at various points, and the question is whether it is possible to walk across all seven bridges, starting anywhere, but only crossing each bridge once.

A map showing the seven bridges over the river at Königsberg.

It turns out to be impossible, but the reasoning behind it is what is key to solving our Sierpinski’s triangle problem. The first step – as with our triangle – is to remove the problem from its context. We can model the top and bottom banks as nodes, as well as the ‘islands’ in the middle and on the right. The bridges become connections between the nodes.

The map simplified into a graph.

Euler solved this problem by considering two kinds of nodes: a node with an even number of connections, and a node with an odd number of connections. Let’s start with the even node.

An ‘even’ node with four connections.

If you were to start your walk from somewhere outside the node, then ‘entering’ the node would ‘cost’ you one connection and leaving it would ‘cost’ you one more. So passing through the node will cost you two connections. Because there are an even number of connections, and passing through the node uses up an even number of connections too, you can ‘clear’ all the connections just by passing through the node as many times as you need. These kinds of even nodes are therefore redundant when your path starts outside the node. But what if you want to start your walk ‘inside’ the node? Again, because the number of connections are even, you have to leave the node as many times as you enter: starting outside the node means that if you entered the node, you have to leave it. Starting inside the node means that if you leave the node, you have to enter it again. In other words, if you start your walk on an even node, you have to finish it there.

An ‘odd’ node with three connections.

The next situation to consider is the odd node. This time, if you start your walk outside the node and pass through it as often as you can, you will always be left with one connection remaining. This also means that if you start your walk outside the node, you will have to finish your walk inside the node. The same logic can be used to show that if you start your walk inside the node, you have to finish it outside, and at a different node. This means that if you have an odd node, you either have to start your walk there or end it there.

Let’s recap the rules we’ve just worked out:

  1. For an even node, we can disregard it if we start our walk somewhere else. Otherwise, we have to both start and finish there.
  2. For an odd node, we have to either start there or finish there.

Now, clearly there’s only going to be one start point and one end point to our walk. That means we cannot have more than two odd nodes anywhere in our graph. It’s also impossible to have a graph with just one odd node. This leaves us with two situations where we know we’ll be able to trace a path that goes through all of our connections only once: either there are no odd nodes, or there are two of them.

If we go back to the Seven Bridges of Königsberg problem and count the number of connections to each node, we can see that each of the four nodes has an odd number of connections. Therefore, it is impossible to walk across each bridge in Königsberg only once. An exciting discovery for the world of graph theory, perhaps, but rather disappointing for a visiting tourist.

However, what we’re really interested in here is whether or not it’s possible to draw Sierpinski’s triangle in one continuous line.

The graph of Sierpinski’s triangle again.

If we return to my little diagram and count the number of connections at each node, every single node has an even number of connections. We’ve already proven it’s possible to draw this shape in one line using an example, but now we can also prove it using graph theory. So, we’ve proven it’s possible to crochet any Sierpinski’s triangle, right? Not quite.

To show it’s possible for any iteration of Sierpinski’s triangle, we’re going to use a trick whereby we show that if it’s possible for one iteration, it’s possible for the next one too. I’ve been throwing around the term ‘iteration’ a lot, but I haven’t actually specified what I mean by it. In the case of this triangle, let’s say that each time you make an iteration, you take three of your current triangles and glue them together to make a bigger one. In the above example, you can see that we took a regular triangle and attached three together at each corner. For the next iteration, we’ll take three copies of our triangle from the current iteration, and stick them together to make a bigger triangle again.

The second iteration of Sierpinski’s triangle.

You’ll notice that I’ve coloured in three pairs of nodes in the diagram on the right. These pairs of nodes are the only nodes whose number of connections will change after an iteration. You’ll also notice that I haven’t drawn any extra connections to connect the nodes of each pair. That’s because these nodes actually overlap when you make an iteration. They both ‘merge’ to create one of the corners of the new empty centre triangle.

Regardless of what the rest of the triangle looks like, we know that the corners at the very edge of Sierpinski’s triangle will have two connections, because they’ll be corners of a triangle. So, when we combine these corners into one node like on the diagram, we’ll end up with four connections. This means that each time we iterate our triangle, we will continue to have only even nodes, and we will therefore continue to have a shape which we can crochet. Since we’ve also shown that it’s possible to crochet the first iteration, we now know that it is possible to create any iteration after the first one.

Satisfied, I sat down with some yarn and a ridiculous number of stitch markers, and a few hours later I had managed to create a fourth-iteration Sierpinski’s triangle. Of course, this is just the fourth iteration, and it only comes out to about 25cm in length. One of the many joys of combining maths with crochet is the number of different directions and adaptions you can easily make, allowing us to ask many different questions about crocheting fractals. How many iterations would you need to make a triangle that was as large as a person? Or a house? Or how about the whole of Russia? It might also be fun to think about whether it would be possible to create other shapes and patterns like this. For example, would it be possible to crochet a cube? If not, how might you adapt the design to make it possible?

The finished product!

If you want to crochet your own fractal, click here for full instructions.

post

Secrets, surveys and statistics

Have you ever shoplifted?

Have you ever cheated on your partner?

Have you driven a car under the influence of alcohol or drugs?

If you ask such sensitive questions in a survey, don’t expect honest answers. Participants might worry that you wouldn’t be able to provide full anonymity and their embarrassing responses might end up in the wrong hands. They may skip more sensitive questions or, even worse, just blatantly lie, which would make your survey utterly useless. Luckily, there is a way to design fully anonymous surveys. All you need is money. No, I’m not asking you to bribe your respondents. A simple fair coin you keep in your pocket serves not only as the means to pay for services, but also as an excellent generator of events with some known probability (in this case with probability $1/2$). In fact, a die or coloured balls in an urn would do, they’d just generate different probabilities.
Continue reading

post

Curiosities of linearly ordered sets

You might look at the title and ask yourself: what is a linearly ordered set? A good example of such a set would be counting the number of years that have passed since the Big Bang—the age of the universe. It will look something like this:
$$
\overset{\text{Bang!}}{0} \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow \dots \rightarrow \overset{\text{Now?}}{\text{13,772,000,000}} \rightarrow \cdots
$$
More formally, a set $S$ is a collection of objects $x$, and if an object is in a set it is called an element of the set: $x \in S$. Simply put, a linearly ordered set is an arrangement of the elements of a set one after another. If we assume that the universe will exist forever, our example represents a linear arrangement for the set $\mathbb{N}$ of non-negative integers. This specific order is called the natural order on $\mathbb{N}=\mathbb{Z}^+\cup\{0\}$. Keep this example in mind while we define what a linear order is. Continue reading

post

When Truchet met Chladni

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

post

Playing billiards with cue-bics

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

post

Hiding in plain sight

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!