post

Read Issue 10 now!

Our latest edition, Issue 10, is available now. Enjoy the articles online or scroll down to view the magazine as a PDF.

Features

Fun

Printed versions

or

Download Issue 10 as a PDF

post

Can computers prove theorems?

How do we prove that $2 + 2 = 4$? At school, this might have been taught to you in the following way. You were given a box of little plastic cubes, two cubes were put in one of your hands and then two more cubes in the other, and you were challenged to count how many cubes you had in total.

But this doesn’t really prove that $2 + 2 = 4$: it proves that 2 plastic cubes + 2 plastic cubes = 4 plastic cubes. You could try it again with pencils and show that 2 pencils + 2 pencils = 4 pencils, and after you’ve tried it with sufficiently many things you might become convinced that there is an underlying pattern. But is this a proof that $2 + 2 = 4$? Proving it like this feels a bit like an experimental science—it works with cubes, it works with pencils, and this is evidence that it works in general. I think we are all pretty confident that, whatever the actual rules of maths are, they probably don’t mention pencils.

But what are the rules of maths? Are there any rules at all, or do we all just have some inbuilt intuition as to what constitutes a valid mathematical argument? Before the 1900s, people worked intuitively, and there was broad agreement as to what constituted a correct argument. But as people began to do more complex and abstract mathematics, this approach became problematic, because people’s intuitions could differ. Ask a room full of teenagers whether $0.9999999\ldots=1$, and you will get different opinions. This is because different people have different intuitions about what the real numbers actually are. Differences of opinion as to whether arguments were valid forced mathematicians into actually writing down an official rulebook: the axioms of maths. Continue reading

post

In conversation with Clifford Cocks

Throughout history, people have wanted to communicate in secret. But for a long time, the need for sender and recipient to agree on a way to encode their message (a ‘key’) meant that secure communication was costly, and mostly used by the military. But in the 1970s new mathematical ideas paved the way for public-key cryptography, a communication strategy that doesn’t rely on a mutually agreed key. If you’ve ever banked or shopped online then you’ve used public-key cryptography, most probably a type called the Diffie–Hellman protocol. (If you want to brush up on Diffie–Hellman, this is a great time to dig out Axel Kerbec’s article Hiding in plain sight from Chalkdust issue 09.) One of the lesser-known figures in the story of public-key cryptography is Clifford Cocks, a former chief mathematician at Britain’s GCHQ (the Government Communication Headquarters). Cliff’s relative anonymity is because, due to the secretive nature of his employer, his contribution was not made public for 24 years. We caught up with him via video call to find out what it felt like to have cracked the code, but kept it secret. Continue reading

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

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

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

Black mathematician month 2019

This is our third year of running Black Mathematician Month and we could not be more pleased for this time to come round again.

We believe that diversity is important in all fields. I work on mathematical modelling applied to biological and medical problems, and one of the most exciting advances on the horizon is the idea of personalised medicine. This is the idea that medicine should be tailored to the individual. When medicine is prescribed, the questions of gender, age and ethnic background, among others, should be taken into account in order to establish the most successful treatment. However, for this goal to be possible we need to consider a wide range of different people, and the most direct way to do this is to have a diverse group of people involved in the research. If mathematics is supposed to benefit all of society, then surely the same is true for us.

Why focus on black mathematicians?

Usually, when we speak about diversity in mathematics we focus solely on gender. However, there are female mathematics role models in the public eye—Rachael Riley on Countdown, Hannah Fry on Radio 4, are but a few of the more famous female mathematicians. But how many black mathematicians can you name? Stepping onto any university campus, it’s easy to notice that the research community is not ethnically representative of the population. Similar issues have been raised in the ‘Decolonising the curriculum’ movement and were noted in reports by the charity Advance HE. Here, although it was noted that 23.6% of mathematics students are BME (Black and minority ethnic), the real issue is hidden by lumping all BME students together. A recent report showed that, shockingly, only 0.6% of all UK professors are black, compared to about 4.6% of the population in England and Wales.

Towards diversity in higher education

People are trying to tackle the problem. It was announced that Stormzy will be funding another round of scholarships at Cambridge this year. Leading Routes run a range of different events and have recently published the `Broken pipeline’ report into why there are not more black students with fully funded PhD places.  Throughout February 2019, Mathematically gifted and black published the profiles of 28 black mathematicians. Chalkdust also wants to do our part. The aim of Black mathematician month is to raise the profile of black mathematicians, in order to provide role models for the next generation who aspire to study mathematics and to generate a conversation about the role of diversity in mathematics. 

In previous years we have published interviews and articles written by black mathematicians, which you can read here. This year, throughout October we will be giving our Twitter account up for ‘take-overs’ by black academics who are leading the conversation on what we can do to improve diversity in the mathematical sciences. Further, from the past few years we have realised that promoting diversity once a year is not enough. This is why we are planning two events for early 2020. One will be for year 9 and 10 school children in London, with a series of workshops and talks to encourage them to consider carrying on studying mathematics. The second will be a networking event for black students, academics and those in industry working in the mathematical sciences. Keep an eye out for these events!

Black mathematician month is something we feel strongly about, however it’s also something that we need help in running. If you would like to get involved or would like to tell us about any events you are running for Black mathematician month, please get in touch!

post

Crossnumber winners, issue 09

With issue 10 of Chalkdust fast approaching, it’s time to announce the winners of the Chalkdust prize crossnumber #9! Before we reveal the winners, here is the solution of the crossnumber.

2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
9 6 4 8 8 9 3
9 4 6 6 1 6 9 4
1 3 1 1 1 7 2 5 9 5
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
9 2 2 8 2 0 8 7
9 1 9 2 2 2 9 2 3 5 8 3 8
3 6 1 5 3 3 7 1 9 9
5 7 1 2 2 9 1 9 2 2 2 9 2
8 1 6 3 4 2 1 3
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
8 9 9 4 7 4 3 2 7 4
2 3 4 0 7 4 1 2
3 6 6 4 8 3 3
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9

The sum of the across clues was 2222222406182591.

There were 100 entries, 66 of which were correct. The randomly selected winners are:

  1. Matt Hutton, who wins a £100 Maths Gear goody bag,
  2. George Lambert, who wins a Chalkdust T-shirt,
  3. Sami Wannell, who wins a Chalkdust T-shirt,
  4. Deborah Tayler, who wins a Chalkdust T-shirt.

Well done to Matt, George, Sami and Deborah, and thanks to everyone else who attempted the crossnumber. See you shortly in issue 10…

post

Reproduce or die

It was about 1975 when I first heard of John Conway’s Game of life, a cellular automaton that is able to mimic aspects of living organisms, such as moving, reproducing and dying. Some school friends who had joined the computer club awoke my curiosity and even though I didn’t know the exact rules at the time, I made up my own version and called it: Reproduce or die 2/4. Let me explain.

John Conway’s version takes place in an infinite 2D checkerboard universe where time goes by in discrete steps. Each square or ‘cell’ in his universe has two possible states, either alive or dead. An initial configuration of living cells is created and the state of any cell at the next time step depends on how many living neighbouring cells it has at the current moment. Conway included all eight neighbouring cells surrounding the one being considered (see the green cell in the figure below), called the Moore neighbourhood. There are four cells touching its sides (labelled s in the figure): north, south, east and west and four neighbouring cells touching corners (labelled c) with the cell in question: NE, NW, SE and SW. If a cell has just two living neighbours, it will stay alive or stay dead. If it has three living neighbours, it will stay alive or come alive. Any other total and it will die or stay dead. For more about Conway’s version, check out this link.

Neighbouring cells.

In my checkerboard 2D universe, I only consider the 4 side cells that surround a living cell, i.e. the ones north, south, east and west (the cells marked ‘s’ above), known as the Von Neumann neighbourhood. I ignore the corner cells (marked ‘c’). The rules are simple:

  • If a living cell has exactly two living side neighbours in the present time step (or generation as I call it), then two new daughter cells are born into the two empty side cells (i.e. they come alive) and the parent stays alive in the next generation.
  • Every other cell dies or stays dead in the next generation.

As the only cells that survive are ones that have two out of four possible living neighbours and they also reproduce (all others dying), I call my version Reproduce or Die 2/4. At first I worked out the new generations by hand on graph paper, but when home computers became a reality in the early 1980’s, I wrote my own programs.

Applying the rules

Consider three living cells in a row (below left, shown in green) in the first generation. The end ones have only one neighbour each so they will die. The middle cell has two neighbours so will live and at the same time will produce two offspring, one in each of the empty neighbours cells (marked ‘0’), one above and one below (see middle figure below). A new shape is created, which is also a line of three living cells but this time vertical. In the next generation, only the middle cell will survive and will create two daughter cells, one to the left and one to the right. The ‘organism’ returns to its original shape (below right) and then repeats the cycle continuously. It is an oscillator of period 2. I call it the rod.

The evolution of the ‘rod’, from left to right.

Consider now a set of three living cells that make a small corner (below left). The end cells each have only one neighbour (the corner cell itself) so will die, but the middle cell that makes the corner has two neighbours so will live and give birth to two daughter cells, one in each of the two unoccupied side cells. The new shape is still a corner, but pointing the other way. In the next generation, the end cells will die and the middle cell will reproduce offspring into the two empty side cells and voila, we get the same starting shape again. This too is an oscillator of period two. I call this shape the corner. Every birth that is possible in this universe is built up of just these two: the rod and the corner.

The evolution of the ‘corner’, from left to right.

For simplicity, the chosen universe for the remainder of this article has a finite size (20×20 cells) but has periodic boundary conditions, like some video games. This means that the top of the spreadsheet is connected to the bottom and the right side is connected to the left side, so the universe is like the surface of a torus. Let us now see what kind of creatures can inhabit this cosmic doughnut when we start combining more than three living cells next to each other.

Shakers and movers

Five oscillators of period two. Clockwise from top: corner, rod, H, and the small and large butterflies. The grid on the right shows the second generation of each oscillator.

The Reproduce or die 2/4 universe cannot be static, due to the chosen rules and in its simplest state it has to at least oscillate, so let us have a look at a few of the ‘shakers’ that live here. Five oscillators are shown above.

The ‘corner’ and ‘rod’ have already been introduced. Each has a period of two and both are among the most common shapes to turn up in random initial conditions i.e. those where the initial state of each cell is chosen at random. The H also has a period of two. The ‘large and small butterflies’ shown above also have periods of two and seem quite rare, but have appeared as end products of a symmetric explosion (see later).

A good game of life would be boring if it didn’t have any mobile creatures, so fortunately this universe has a fair share of travelling folk. Four examples are shown below. In this case all move north:

Gliders that move north. Four time-steps are shown, going clockwise from top left. The gliders are called (clockwise from bottom left in the first time-step) the small C, the hat, the short leg, and the leg1.2.3.2.

The first glider (bottom left) I call the small C. It evolves over three generations before returning to its original shape, but it has moved one cell north during this period. It thus has a speed 1/3 that of light and a period of 3. (Note: speed of light is the name given to the maximum possible speed, which in this universe is one cell per time interval). The small C is very different to all the other gliders so far discovered, as will become clear. The next glider (above the C), I call the hat. It keeps the same shape every generation (so has a period of one) and moves at the speed of light: one cell per time step. It is the most common glider in this version of the Game of Life. The top right shape in, I call the short leg, which is like the hat but with one short limb. It has a period of two and moves at the speed of light. The final example (bottom right shape) is the leg1.2.3.2. This one has a period of 4 before it returns to its initial shape and like almost every glider it moves at the speed of light.

As with John Conway’s Game of Life, this version also has shapes that create strings of gliders (guns as they are called), plus there are many interesting collisions involving moving shapes, but time and space are limited so let us move onto one of the more spectacular performances in the presentation.

The big bang

There is a category of simple regular shapes that grow like an explosion and maintain their symmetry through each ensuing generation. I call the simplest one, starting with a 2×2 array of living cells, the ‘big bang’. A selection of stages of this explosion is shown below. Each generation might make a unique repeating floor tile, or possibly, one of the most challenging crosswords layouts ever!

The big bang on the 1st, 11th, 21st, 41st, 81st and 136th generation.

In an infinite universe, all such shapes would grow indefinitely, but as it is finite here, the advancing ‘shock waves’ of the exploding shapes meet each other at the edges and then interfere. The big bang eventually settles down to a simple oscillating pattern of 12 corners on the 136th generation, much like the formation of the galaxies (or stars) in our own universe. All other symmetrical patterns settle down, but some with a long dance, needing up to seven generations in the end repeating cycle.

A random field

A random initial field.

A random field is one where the initial state of the cells, alive or dead is decided by a probability rating $p$, e.g. $p = 0.5$ would mean the chance of a cell starting alive would be 50%, hence about 50% of the cells would be alive using a random number function at the start. Most random, asymmetric shapes produce what seem to be permanent disorder that expands and fills the space and looks like it never wants to settle down. As this particular universe is finite in size, then there are a finite number of possible states, so in fact all configurations will repeat, even if they take a long time. To the right is a typical example of such a random population many generations after its creation. In this example one can see, top right, an oscillating corner, while near the centre is a hat glider, moving downwards. Neither shape will survive more than a generation or two, but this is how precarious life is in this universe.

Conclusion

The Reproduce or die 2/4 variation does have its moments of oscillators, gliders, guns, collisions and explosions, with some amazing kaleidoscopic patterns to delight the eyes. The downside is that there are far too many uncontrolled population growths that swamp and destroy the more interesting order. Life in such volatile fields is short-lived and fleeting, much like the real universe. Perhaps that is what makes this kind of life so precious.

Whatever next?!

In Reproduce or die 2/4, there are a few questions I would like to ask:

  • How would changing the finite size of the universe change the outcomes? I used a 20×20 universe, but I’d expect it to be different for, say a 30×30. Readers will have a chance to try this out!
  • In a random field, is there a pattern to the population density?
  • What is the frequency of appearance of stable shapes, like the hat, corner and rod?
  • What would happen if the Reproduce or die 2/4 rules were modified slightly? For example when two cells are trying to be born into the same square, what if they cancelled out and it remained empty? That might dampen down those unwanted exponential explosions.

I asked one of my physics students, Dmitry Mikhailov, to create the Reproduce or Die world so readers could play with it themselves. He kindly took up the challenge and has made an interactive version here. All images in this article are also thanks to his program and Dmitry’s contribution is much appreciated.

Please share your discoveries of any interesting news shapes. Remember, stable shapes are hard to find as most situations end in disarray, so don’t be put off (unless you like entropy!). Finally, why not consider trying to create your own set of rules and you can then be the god (or goddess) of your own universe!