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

## Features

• ### Can computers prove theorems?

And will we soon all be out of a job? Kevin Buzzard worries us all.
• ### In conversation with Clifford Cocks

We chat to the crypto chief about inventing RSA... but not being able to tell anyone
• ### On √2

Yiannis Petridis connects square roots and continued fractions
• ### Spotlight on: Pamela Harris

Pamela E Harris's story, as told by Talithia Williams
• ### Artificial music

Carmen Cabrera Arnau explores the use of AI in composition
• ### They might not be giants

Angela Brett might not be standing on their shoulders

• ### On the cover: Islamic geometry

Explaining the mathematics of tiling, and the cover of Issue 10
• ### Secrets, surveys and statistics

Paula Rowińska uses mathematics to answer some awkward questions
• ### Curiosities of linearly ordered sets

Andrei Chekmasov explores order and infinity

## Fun

• ### Prize crossnumber, Issue 10

Can you solve it?
• ### Dear Dirichlet, Issue 10

Letter writing, hospital visits, and getting the family active are among the topics of discussion in this issue's Dear Dirichlet advice column
• ### Comic: The Inverse Homotopy, part 7

Part 7 of our mathematical comic's adventure
• ### Which mathematician are you?

How do you like your numbers? Prime? Positive but infinitely small? Find out which famous mathematician you are
• ### What’s hot and what’s not, Issue 10

Fashion is fleeting, Chalkdust regulars are not.
• ### Top Ten: issues of Chalkdust

The definitive chart of the best issues of Chalkdust
• ### Page 3 model: Bees

You won't bee-lieve it
• ### Top ten vote issue 10

Vote for your favourite picture of a scorpion
• ### How to make: tessellating shortbread

Tasty and mathematical

or

# 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

# 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

# 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$

# 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”.

## 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!