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

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

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