Author: IMC

Have you ever struggled with teaching statistics? Do you and your students share a sense of apprehension when data lessons appear in the scheme of work? You’re not alone. Anecdotally, many teachers tell me that statistics is one of the topics they like teaching the least, and I am no exception to this myself. In my mathematics degree, I took the minimum number of statistics-related courses allowed, following a very poor diet of data at school, and carried this negative association into my teaching. Looking back on my career in the classroom, I did not do a good job of teaching statistics, but having had the luxury of spending many years at Cambridge Mathematics immersed in research from excellent statistics teachers and education academics I now understand why!

So now, of course, the question has been posed. Why is statistics hard to teach well? In part, I believe that it stems from viewing statistics through a mathematical lens – understandably, given that we are delivering it alongside quadratic equations, Pythagoras’ theorem, fractions, decimals and percentages. But while statistical analysis would not exist without the mathematical concepts and techniques underpinning it, we have a tendency within curricula to make the mathematical techniques the whole point, and reduce the statistical analysis part to an afterthought or an added extra. Students find the more subjective analysis hard, so it is tempting to make sure everyone can manage the techniques and then focus on the interpretation as something only the most able have time to spend on (although, there is always the additional temptation to move on to other, more properly ‘maths-y’ topics as soon as possible).

This approach is at odds with how education researchers suggest students should encounter statistical ideas. In the early 1990s, George Cobbⁱ and other researchers recommended that statistics should

• emphasise statistical thinking,
• include more real data,
• encourage the exploration of genuine statistical problems, and
• reduce emphasis on calculations and techniques.

Since then, much subsequent research has refined these recommendations to account for new technology tools and new ideas, but the core principles have remained the same. In much of my reading of education research, three ways of seeing or interacting with data keep appearing:

·        Data modelling – the idea that data can be used to create models of the world in order to pose and answer questions

·        Informal inference – the idea that data can be used to make predictions about something outside of the data itself with some attempt made to describe how likely the prediction is to be true

·        Exploratory data analysis – the idea that data can be explored, manipulated and represented to identify and make visible patterns and associations that can be interpreted

In the abstract, these ways of seeing, while distinct, have a degree of overlap, and all students may benefit from multiple experiences of all three approaches to data work from their very earliest encounters with data through to advanced-level study.

Imagine the following classroom activity that could be given to very young students (e.g., in primary school). A class of students is given a list of snacks and treats and the students are asked to rank them on a scale of one to five based on how much they like each item. How could this data be worked with through each of the three approaches?

Firstly, we will consider data modelling. Students could be asked to plan a class party with a limited budget. They can buy some but not all of the items listed and must decide what they should buy so that the maximum number of students get to have things they like. In this activity, students must create a model from the data that identifies those things they should buy more of, and those things they should buy least of, along with how many of each thing they should get – perhaps considering these quantities proportionally. This activity uses the data as a model but inevitably requires some assumptions and the creation of some principles. Is the goal to ensure everyone gets the thing they like most? Or is it to minimise the inclusion of the things students like least? What if everyone gets their favourite thing except one student who gets nothing they like?

Secondly, we will think about this as an activity in informal inference. Imagine a new student is joining the class and the class wants to make a welcome pack of a few treats for this student, but they don’t know which treats the student likes. Can they use the data to decide which five items an unknown student is most likely to choose? What if they know some small details about the student; would that additional information allow them to decide based on ‘similar’ students in the class? While the second part of this activity must be handled with a degree of sensitivity, it is an excellent primer for how purchasing algorithms, which are common in online shops, work.

Finally, we turn to exploratory data analysis. In this approach students are encouraged to look for patterns in the data, perhaps by creating representations. This approach may come from asking questions – e.g., do students who like one type of chocolate snacks rate the other chocolate snacks highly too? Is a certain brand of snack popular with everyone in the class? What is the least popular snack? Alternatively, the analysis may generate questions from patterns that are spotted – e.g. why do students seem to rate a certain snack highly? What are the common characteristics of the three most popular snacks?

Each of these approaches could be engaged in as separate and isolated activities, but there is also the scope to combine them and use the results of one approach to inform another. For example, exploratory data analysis may usefully contribute both to model building and inference making and support students’ justifications for their decisions in those activities. Similarly, data modelling activities can be extended into inferential tasks very easily, simply by shifting the use of the model from the population of the data (e.g., the students in the class it was collected from) to some secondary population (e.g., another class in the school, or as in the example, a new student joining the class).

Looking back on my time in the classroom, I wish that my understanding of these approaches and their importance for developing statistical reasoning skills in my students had been better. While not made explicit as important in many curricula, there are ample opportunities to embed these approaches and make them a fundamental part of the statistics teacher’s pedagogy.

Do you currently use any of these approaches in your lessons? Can you see where you might use them in the future? And how might you adapt activities to allow your students opportunities to engage in data modelling, informal inference and exploratory data analysis?

 For more insights like this, visit our website at www.international-maths-challenge.com.

Credit for the article given to Darren Macey

Luis Caffarelli has been awarded the most prestigious prize in mathematics for his work on nonlinear partial differential equations, which have many applications in the real world.

Luis Caffarelli has won the 2023 Abel prize, unofficially called the Nobel prize for mathematics, for his work on a class of equations that describe many real-world physical systems, from melting ice to jet engines.

Caffarelli was having breakfast with his wife when he found out the news. “The breakfast was better all of a sudden,” he says. “My wife was happy, I was happy — it was an emotional moment.”

Based at the University of Texas at Austin, Caffarelli started work on partial differential equations (PDEs) in the late 1970s and has contributed to hundreds of papers since. He is known for making connections between seemingly distant mathematical concepts, such as how a theory describing the smallest possible areas that surfaces can occupy can be used to describe PDEs in extreme cases.

PDEs have been studied for hundreds of years and describe almost every sort of physical process, ranging from fluids to combustion engines to financial models. Caffarelli’s most important work concerned nonlinear PDEs, which describe complex relationships between several variables. These equations are more difficult to solve than other PDEs, and often produce solutions that don’t make sense in the physical world.

Caffarelli helped tackle these problems with regularity theory, which sets out how to deal with problematic solutions by borrowing ideas from geometry. His approach carefully elucidated the troublesome parts of the equations, solving a wide range of problems over his more than four-decade career.

“Forty years after these papers appeared, we have digested them and we know how to do some of these things more efficiently,” says Francesco Maggi at the University of Texas at Austin. “But when they appeared back in the day, in the 80s, these were alien mathematics.”

Many of the nonlinear PDEs that Caffarelli helped describe were so-called free boundary problems, which describe physical scenarios where two objects in contact share a changing surface, like ice melting into water or water seeping through a filter.

“He has used insights that combined ingenuity, and sometimes methods that are not ultra-complicated, but which are used in a manner that others could not see — and he has done that time and time again,” says Thomas Chen at the University of Texas at Austin.

These insights have also helped other researchers translate equations so that they can be solved on supercomputers. “He has been one of the most prominent people in bringing this theory to a point where it’s really useful for applications,” says Maggi.

For more such insights, log into www.international-maths-challenge.com.

*Credit for article given to Alex Wilkins*

Our laws of nature are written in the language of mathematics. But maths itself is only as dependable as the axioms it is built on, and we have to assume those axioms are true.

You might think that mathematics is the most trustworthy thing humans have ever come up with. It is the basis of scientific rigour and the bedrock of much of our other knowledge too. And you might be right. But be careful: maths isn’t all it seems. “The trustworthiness of mathematics is limited,” says Penelope Maddy, a philosopher of mathematics at the University of California, Irvine.

Maddy is no conspiracy theorist. All mathematicians know her statement to be true because their subject is built on “axioms” – and try as they might, they can never prove these axioms to be true.

An axiom is essentially an assumption based on observations of how things are. Scientists observe a phenomenon, formalise it and write down a law of nature. In a similar way, mathematicians use their observations to create an axiom. One example is the observation that there always seems to be a unique straight line that can be drawn between two points. Assume this to be universally true and you can build up the rules of Euclidean geometry. Another is that 1 + 2 is the same as 2 + 1, an assumption that allows us to do arithmetic. “The fact that maths is built on unprovable axioms is not that surprising,” says mathematician Vera Fischer at the University of Vienna in Austria.

These axioms might seem self-evident, but maths goes a lot further than arithmetic. Mathematicians aim to uncover things like the properties of numbers, the ways in which they are all related to one another and how they can be used to model the real world. These more complex tasks are still worked out through theorems and proofs built on axioms, but the relevant axioms might have to change. Lines between points have different properties on curved surfaces than flat ones, for example, which means the underlying axioms have to be different in different geometries. We always have to be careful that our axioms are reliable and reflect the world we are trying to model with our maths.

Set theory

The gold standard for mathematical reliability is set theory, which describes the properties of collections of things, including numbers themselves. Beginning in the early 1900s, mathematicians developed a set of underpinning axioms for set theory known as ZFC (for “Zermelo-Fraenkel”, from two of its initiators, Ernst Zermelo and Abraham Fraenkel, plus something called the “axiom of choice”).

ZFC is a powerful foundation. “If it could be guaranteed that ZFC is consistent, all uncertainty about mathematics could be dispelled,” says Maddy. But, brutally, that is impossible. “Alas, it soon became clear that the consistency of those axioms could be proved only by assuming even stronger axioms,” she says, “which obviously defeats the purpose.”

Maddy is untroubled by the limits: “Set theorists have been proving theorems from ZFC for 100 years with no hint of a contradiction.” It has been hugely productive, she says, allowing mathematicians to create no end of interesting results, and they have even been able to develop mathematically precise measures of just how much trust we can put in theories derived from ZFC.

In the end, then, mathematicians might be providing the bedrock on which much scientific knowledge is built, but they can’t offer cast-iron guarantees that it won’t ever shift or change. In general, they don’t worry about it: they shrug their shoulders and turn up to work like everybody else. “The aim of obtaining a perfect axiomatic system is exactly as feasible as the aim of obtaining a perfect understanding of our physical universe,” says Fischer.

At least mathematicians are fully aware of the futility of seeking perfection, thanks to the “incompleteness” theorems laid out by Kurt Gödel in the 1930s. These show that, in any domain of mathematics, a useful theory will generate statements about this domain that can’t be proved true or false. A limit to reliable knowledge is therefore inescapable. “This is a fact of life mathematicians have learned to live with,” says David Aspero at the University of East Anglia, UK.

All in all, maths is in pretty good shape despite this – and nobody is too bothered. “Go to any mathematics department and talk to anyone who’s not a logician, and they’ll say, ‘Oh, the axioms are just there’. That’s it. And that’s how it should be. It’s a very healthy approach,” says Fischer. In fact, the limits are in some ways what makes it fun, she says. “The possibility of development, of getting better, is exactly what makes mathematics an absolutely fascinating subject.”

HOW BIG IS INFINITY?

Infinity is infinitely big, right? Sadly, it isn’t that simple. We have long known that there are different sizes of infinity. In the 19th century, mathematician Georg Cantor showed that there are two types of infinity. The “natural numbers” (1, 2, 3 and so on forever) are a countable infinity. But between each natural number, there is a continuum of “real numbers” (such as 1.234567… with digits that go on forever). Real number infinities turn out not to be countable. And so, overall, Cantor concluded that there are two types of infinity, each of a different size.

In the everyday world, we never encounter anything infinite. We have to content ourselves with saying that the infinite “goes on forever” without truly grasping conceptually what that means. This matters, of course, because infinities crop up all the time in physics equations, most notably in those that describe the big bang and black holes. You might have expected mathematicians to have a better grasp of this concept, then – but it remains tricky.

This is especially true when you consider that Cantor suggested there might be another size of infinity nestled between the two he identified, an idea known as the continuum hypothesis. Traditionally, mathematicians thought that it would be impossible to decide whether this was true, but work on the foundations of mathematics has recently shown that there may be hope of finding out either way after all.

For more such insights, log into www.international-maths-challenge.com.

*Credit for article given to Michael Brooks*

Mathematics suggested that time travel is physically possible – and Kurt Gödel proved it. Mathematician Karl Sigmund explains how the polymath did it.

The following is an extract from our Lost in Space-Time newsletter. Each month, we hand over the keyboard to a physicist or mathematician to tell you about fascinating ideas from their corner of the universe. You can sign up for Lost in Space-Time for free here.

There may be no better way to get truly lost in space-time than to travel to the past and fiddle around with causality. Polymath Kurt Gödel suggested that you could, for instance, land near your younger self and “do something” to that person. If your action was drastic enough, like murder (or is it suicide?), then you could neither have embarked on your time trip, nor perpetrated the dark deed. But then no one would have stopped you from going back in time and so you can commit your crime after all. You are lost in a loop. It’s no longer where you are, but whether you are.

Gödel was the first to prove that, according to general relativity, this sort of time travel can be done. While logically impossible, the equations say it is physically possible. How can that actually be the case?

Widely hailed as “the greatest logician since Aristotle”, Gödel is mainly known for his mathematical and philosophical work. By age 25, while at the University of Vienna, he developed his notorious incompleteness theorems. These basically say that there is no finite set of assumptions that can underpin all of mathematics. This was quickly perceived as a turning point in the subject.

In 1934, Gödel, now 28, was among the first to be invited to the newly founded Institute for Advanced Study in Princeton, New Jersey. During the following years, he commuted between Princeton and Vienna.

After a traumatic journey around a war-torn globe, Gödel settled in Princeton for good in 1940. This is when his friendship with Albert Einstein developed. Their daily walks became legendary. Einstein quipped: “I come to my office just for the privilege to escort Gödel back home.”  The two strollers seemed eerily out of their time. The atomic bomb was built without Einstein, and the computer without Gödel.

When Einstein’s 70th birthday approached, Gödel was asked to contribute to the impending Festschrift a philosophical chapter on German philosopher Immanuel Kant and relativity – a well-grazed field. To his mother, he wrote: “I was asked to write a paper for a volume on the philosophical meaning of Einstein and his theory; of course, I could not very well refuse.”

Gödel began to reflect on Kant’s view that time was not, as Newton would have it, an absolute, objective part of the world, but an a priori form of intuition constraining our cognition. As Kant said: “What we represent ourselves as changes would, in beings with other forms of cognition, give rise to a perception in which… change would not occur at all.” Such “beings” would experience the world as timeless.

In his special relativity, Einstein had famously shown that different observers can have different notions of “now”. Hence, no absolute time. (“Newton, forgive me!” sighed Einstein.) However, this theory does not include gravitation. Add mass, and a kind of absolute time seems to sneak back! At least, it does so in the standard model of cosmology. There, the overall flow of matter works as a universal clock. Space-time is sliced in an infinity of layers, each representing a “now”, one succeeding another. Is this a necessary feature of general relativity? Gödel had found a mathematical kernel in a philosophical problem. That was his trademark.

At this stage, according to cosmologist Wolfgang Rindler, serendipity stepped in: Gödel stumbled across a letter to the journal Nature by physicist George Gamow, entitled “Rotating universe?”. It points out that apparently most objects in the sky spin like tops. Stars do it, planets do it, even spiral galaxies do it. They rotate. But why?

Gamow suggested that the whole universe rotates, and that this rotation trickles down, so to speak, to smaller and smaller structures: from universe to galaxies, from galaxies to stars, from stars to planets. The idea was ingenious, but extremely vague. No equations, no measurements. However, the paper ended with a friendly nudge for someone to start calculating.

With typical thoroughness, Gödel took up the gauntlet. He had always been a hard worker, who used an alarm clock not for waking up but for going to bed. He confided to his mother that his cosmology absorbed him so much that even when he tried to listen to the radio or to movies, he could do so “only with half an ear”. Eventually, Gödel discovered exact solutions of Einstein’s equations, which described a rotating universe.

However, while Gamow had imagined that the centre of rotation of our world is somewhere far away, beyond the reach of the strongest telescopes, Gödel’s universe rotates in every point. This does not solve Gamow’s quest for the cause of galactic rotations, but yields another, amazing result. In contrast to all then-known cosmological models, Gödel’s findings showed that there is no “now” that’s valid everywhere. This was exactly what he had set out to achieve: vindicate Kant (and Einstein) by showing that there is no absolute time.

“Talked a lot with Gödel,” wrote his friend Oskar Morgenstern, the economist who, together with John von Neumann, had founded game theory. He knew Gödel from former Viennese days and reported all their meetings in his diary. “His cosmological work makes good progress. Now one can travel into the past, or reach arbitrarily distant places in arbitrarily short time. This will cause a nice stir.” Time travel had been invented.

In Gödel’s universe, you don’t have to flip the arrow of time to go back to the past. Your time runs as usual. No need to shift entropy in return gear. You just step into a rocket and take off, to fly in a very wide curve (very wide!) at a very high speed (but less than the speed of light). The rocket’s trajectory weaves between light cones, never leaving them but exploiting the fact that in a rotating universe, they are not arrayed in parallel. The trip would consume an awful amount of energy.

Gödel just managed to meet the editorial timeline. On his 70th birthday, Einstein got Gödel’s manuscript for a present (and a sweater knitted by Kurt’s wife Adele). He thanked him for the gifts and confessed that the spectre of time travel had worried him for decades. Now the spectre had materialised. Einstein declared Gödel’s paper “one of the most important since my own”, and stated his hope that time travel could be excluded by some as yet unknown physical law. Soon after, Gödel received the first Albert Einstein award. It went with a modest amount of money which Gödel, as it turned out, could use well.

Next, according to philosopher Palle Yourgrau, “something extraordinary happened: nothing”.

For several decades, the mind-bending discovery of Gödel, far from causing “a nice stir”, got very little attention. When Harry Woolf, the director of the Institute for Advanced Study, arranged the eulogies to be given at Gödel’s funeral in 1978, he listed the topics to be covered: set theory and logic, followed by relativity, which he noted was “not worth a talk”.

Only by and by did eminent cosmologists, such as Stephen Hawking, Kip Thorne or John Barrow, convey an area of respectability to the field. Today, it is mainstream. With time, it transpired that, years before Gödel’s breakthrough, several other cosmological models had exhibited both rotation and the possibility of time travel. However, this aspect had never been noticed, not even by the engineers of these universes.

Many physicists are happy to leave the paradoxical aspects of time travel to philosophers. They invoke a “chronology protection law” that would step in to prevent the worst. It sounds like whistling in the dark but helps to overcome the problem of haunting your own present as a revenant from the future.

And does our universe rotate? Gödel was equivocal on that issue. Sometimes he claimed that his model only served as a thought experiment, to display the illusionary character of time, which cannot depend on accidental features of the place we happen to inhabit. Cosmologist Freeman Dyson, however, reported that Gödel, near the end of his life, had shown dismay when told that evidence for a rotating universe is lacking.

For more such insights, log into www.international-maths-challenge.com.

*Credit for article given to Karl Sigmund*

Relating mathematics to questions that are relevant to many students can help address its image problem, argues Eugenia Cheng.

Mathematics has an image problem: far too many people are put off it and conclude that the subject just isn’t for them. There are many issues, including the curriculum, standardised tests and constraints placed on teachers. But one of the biggest problems is how maths is presented, as cold and dry.

Attempts at “real-life” applications are often detached from our daily lives, such as arithmetic problems involving a ludicrous number of watermelons or using a differential equation to calculate how long a hypothetical cup of coffee will take to cool.

I have a different approach, which is to relate abstract maths to questions of politics and social justice. I have taught fairly maths-phobic art students in this way for the past seven years and have seen their attitudes transformed. They now believe maths is relevant to them and can genuinely help them in their everyday lives.

At a basic level, maths is founded on logic, so when I am teaching the principles of logic, I use examples from current events rather than the old-fashioned, detached type of problem. Instead of studying the logic of a statement like “all dogs have four legs”, I might discuss the (also erroneous) statement “all immigrants are illegal”.

But I do this with specific mathematical structures, too. For example, I teach a type of structure called an ordered set, which is a set of objects subject to an order relation such as “is less than”. We then study functions that map members of one ordered set to members of another, and ask which functions are “order-preserving”. A typical example might be the function that takes an ordinary number and maps it to the number obtained from multiplying by 2. We would then say that if x < y then also 2x < 2y, so the function is order-preserving. By contrast the function that squares numbers isn’t order-preserving because, for example, -2 < -1, but (-2)² > (-1)². If we work through those squaring operations, we get 4 and 1.

However, rather than sticking to this type of dry mathematical example, I introduce ones about issues like privilege and wealth. If we think of one ordered set with people ordered by privilege, we can make a function to another set where the people are now ordered by wealth instead. What does it mean for that to be order-preserving, and do we expect it to be so? Which is to say, if someone is more privileged than someone else, are they automatically more wealthy? We can also ask about hours worked and income: if someone works more hours, do they necessarily earn more? The answer there is clearly no, but then we go on to discuss whether we think this function should be order-preserving or not, and why.

My approach is contentious because, traditionally, maths is supposed to be neutral and apolitical. I have been criticised by people who think my approach will be off-putting to those who don’t care about social justice; however, the dry approach is off-putting to those who do care about social justice. In fact, I believe that all academic disciplines should address our most important issues in whatever way they can. Abstract maths is about making rigorous logical arguments, which is relevant to everything. I don’t demand that students agree with me about politics, but I do ask that they construct rigorous arguments to back up their thoughts and develop the crucial ability to analyse the logic of people they disagree with.

Maths isn’t just about numbers and equations, it is about studying different logical systems in which different arguments are valid. We can apply it to balls rolling down different hills, but we can also apply it to pressing social issues. I think we should do both, for the sake of society and to be more inclusive towards different types of student in maths education.

For more such insights, log into www.international-maths-challenge.com.

*Credit for article given to Eugenia Cheng*

Mathematicians have grappled with a so-called “fixed point” theorem. An EPFL-based team has now found an elegant, one-page solution that opens up new perspectives in physics and economics

Take a map of the world. Now put it down on the ground in Central Park, against a rock on Mount Everest, or on your kitchen table; there will always be a point on the map that sits exactly on the actual physical place it represents. Obvious? Not for mathematicians. A more complex theorem, called a “fixed point theorem,” has eluded them since 1963. “Some ideas seem evident to the human mind, but in reality involve complicated concepts that are difficult to demonstrate mathematically,” says Nicolas Monod, head of EPFL’s Chair of Ergodic and Geometric Group Theory. It turns out that the answer was there all along, simple and elegant. To reach it, the team of mathematicians had take a different approach to the problem. Their discovery will impress their fellow mathematicians, of course; but on the longer term, it also will be of interest to physicists and economists.

Surprisingly, this theorem works for all kinds of maps, from a diagram of a metro route to a map of spaces used in quantum physics. But to prove it, a fixed point must be found for every possible case. Since the number of possible maps is infinite, the mathematicians were looking for a universal, purely mathematical method — one that would work in any situation.

The challenge for the mathematicians was to find that fixed point. It was a bit like designing a method that could pinpoint the center of gravity of any object, real or purely mathematical. It seemed like an impossible task for the specialists. “That’s why this approach hadn’t been more fully explored,” Monod explains. “It was in thinking about another space and exchanging our ideas that we realized that we actually could find that center of gravity.” It was possible to determine it in a parallel space. The center of gravity was definitely there … but outside the space you started from. It was a counterintuitive result, but one that allowed them to prove the theorem.

In 2008, a thirty-page article, full of technical jargon, almost arrived at a proof. Even Barry Edward Johnson, who formulated the theorem and worked hard to find a proof all the way up to his death in 2002, was ultimately unsuccessful. Today, the proof is only a few pages long. In addition to the indisputable intellectual satisfaction this elegant result represents, it also opens up long-term perspectives in other disciplines; theories in physics and economics, for example, both make use of the idea of fixed points.

For more such insights, log into our website https://international-maths-challenge.com

Credit of the article given to Ecole Polytechnique Federale de Lausanne

One week after DeepMind revealed an algorithm for multiplying numbers more efficiently, researchers have an even better way to carry out the task.

Multiplying numbers is a common computational problem

A pair of researchers have found a more efficient way to multiply grids of numbers, beating a record set just a week ago by the artificial intelligence firm DeepMind.

The company revealed on 5 October that its AI software had beaten a record that had stood for more than 50 years for the matrix multiplication problem – a common operation in all sorts of software where grids of numbers are multiplied by each other. DeepMind’s paper revealed a new method for multiplying two five-by-five matrices in just 96 multiplications, two fewer than the previous record.

Jakob Moosbauer and Manuel Kauers at Johannes Kepler University Linz in Austria were already working on a new approach to the problem prior to that announcement.

Their approach involves running potential multiplication algorithms through a process where multiple steps in the algorithm are tested to see if they can be combined.

“What we do is, we take an existing algorithm and apply a sequence of transformations that at some point can lead to an improvement. Our technique works for any known algorithm, and if we are lucky, then [the results] need one multiplication less than before,” says Moosbauer.

After DeepMind published its breakthrough, Moosbauer and Kauers used their approach to improve on DeepMind’s method, slicing off another step to set a new record of 95 multiplications. They have published the proof in a pre-print paper, but haven’t yet released details of the approach they used to find improvements on previous methods.

“We wanted to publish now to be the first one out there, because if we can find it in such a short amount of time, there’s quite some risk that we get outdone by someone else again,” says Moosbauer.

The latest paper is entirely focused on five-by-five matrix multiplication, but the method is expected to bring results for other sizes. The researchers say that they will publish details of their technique soon.

Moosbauer says that DeepMind’s approach brought fresh impetus to an area of mathematics that hadn’t been receiving much attention. He hopes that other teams are also now working in a similar vein.

Matrix multiplication is a fundamental computing task used in virtually all software to some extent, but particularly in graphics, AI and scientific simulations. Even a small improvement in the efficiency of these algorithms could bring large performance gains, or significant energy savings.

DeepMind claimed to have seen a boost in computation speed of between 10 and 20 per cent on certain hardware such as an Nvidia V100 graphics processing unit and a Google tensor processing unit v2. But it said that there was no guarantee that similar gains would be seen on everyday tasks on common hardware. Moosbauer says he is sceptical about gains in common software, but that for large and specialised research tasks there could be an improvement.

DeepMind declined a request for an interview about the latest paper, but its researcher Alhussein Fawzi said in a statement: “We’ve been overwhelmed by the incredible reaction to the paper. Our hope was that this work would open up the field of algorithmic discovery to new ideas and approaches. It’s fantastic to see others exploring ideas in this space as well as building on our work so quickly.”

For more such insights, log into www.international-maths-challenge.com.

*Credit for article given to Matthew Sparkes*

Matrix multiplication – where two grids of numbers are multiplied together – forms the basis of many computing tasks, and an improved technique discovered by an artificial intelligence could boost computation speeds by up to 20 per cent.

Multiplying numbers is a fundamental task for computers

An artificial intelligence created by the firm DeepMind has discovered a new way to multiply numbers, the first such advance in over 50 years. The find could boost some computation speeds by up to 20 per cent, as a range of software relies on carrying out the task at great scale.

Matrix multiplication – where two grids of numbers are multiplied together – is a fundamental computing task used in virtually all software to some extent, but particularly so in graphics, AI and scientific simulations. Even a small improvement in the efficiency of these algorithms could bring large performance gains, or significant energy savings.

For centuries, it was believed that the most efficient way of multiplying matrices would be proportional to the number of elements being multiplied, meaning that the task becomes proportionally harder for larger and larger matrices.

But the mathematician Volker Strassen proved in 1969 that multiplying a matrix of two rows of two numbers with another of the same size doesn’t necessarily involve eight multiplications and that, with a clever trick, it can be reduced to seven. This approach, called the Strassen algorithm, requires some extra addition, but this is acceptable because additions in a computer take far less time than multiplications.

The algorithm has stood as the most efficient approach on most matrix sizes for more than 50 years, although some slight improvements that aren’t easily adapted to computer code have been found. But DeepMind’s AI has now discovered a faster technique that works perfectly on current hardware. The company’s new AI, AlphaTensor, started with no knowledge of any solutions and was presented with the problem of creating a working algorithm that completed the task with the minimum number of steps.

It found an algorithm for multiplying two matrices of four rows of four numbers using just 47 multiplications, which outperforms Strassen’s 49 multiplications. It also developed improved techniques for multiplying matrices of other sizes, 70 in total.

AlphaTensor discovered thousands of functional algorithms for each size of matrix, including 14,000 for 4×4 matrices alone. But only a small minority were better than the state of the art. The research builds on AlphaZero, DeepMind’s game-playing model, and has been two years in the making.

Hussein Fawzi at DeepMind says the results are mathematically sound, but are far from intuitive for humans. “We don’t really know why the system came up with this, essentially,” he says. “Why is it the best way of multiplying matrices? It’s unclear.”

“Somehow, the neural networks get an intuition of what looks good and what looks bad. I honestly can’t tell you exactly how that works. I think there is some theoretical work to be done there on how exactly deep learning manages to do these kinds of things,” says Fawzi.

DeepMind found that the algorithms could boost computation speed by between 10 and 20 per cent on certain hardware such as an Nvidia V100 graphics processing unit (GPU) and a Google tensor processing unit (TPU) v2, but there is no guarantee that those gains would also be seen on common devices like a smartphone or laptop.

James Knight at the University of Sussex, UK, says that a range of software run on supercomputers and powerful hardware, like AI research and weather simulation, is effectively large-scale matrix multiplication.
“If this type of approach was actually implemented there, then it could be a sort of universal speed-up,” he says. “If Nvidia implemented this in their CUDA library [a tool that allows GPUs to work together], it would knock some percentage off most deep-learning workloads, I’d say.”

Oded Lachish at Birkbeck, University of London, says the new algorithms could boost the efficiency of a wide range of software, because matrix multiplication is such a common problem – and more algorithms are likely to follow.

“I believe we’ll be seeing AI-generated results for other problems of a similar nature, albeit rarely something as central as matrix multiplication. There’s significant motivation for such technology, since fewer operations in an algorithm doesn’t just mean faster results, it also means less energy spent,” he says. If a task can be completed slightly more efficiently, then it can be run on less powerful, less power-intensive hardware, or on the same hardware in less time, using less energy.

But DeepMind’s advances don’t necessarily mean human coders are out of a job. “Should programmers be worried? Maybe in the far future. Automatic optimisation has been done for decades in the microchip design industry and this is just another important tool in the coder’s arsenal,” says Lachish.

For more such insights, log into www.international-maths-challenge.com.

*Credit for article given to Matthew Sparkes*

TREE(3) is a number that turns up easily from just playing a simple mathematical game. Yet, it is so colossally large that it couldn’t conceivably fit in our universe, writes Antonio Padilla.

There are many numbers that fit quite naturally into our everyday lives. For example, the number five counts the founding members of popular UK band One Direction, the number 31 million, how many followers they have on Twitter and the number zero, the number of followers that actually have decent taste in music (sorry!).

But there are also numbers which are important to mathematicians that can never fit into our everyday lives. There are even those that could never fit into the universe. Like TREE(3). Let me explain.

TREE(3) is a colossus, a number so large that it dwarfs some of its gargantuan cousins like a googol (ten to the one hundred), or a googolplex (ten to the googol), or even the dreaded Graham’s number (too big to write). TREE(3) emerges, quite spectacularly, from a mathematical game known as the Games of Trees. The idea of the game is to build a forest of trees from different combinations of seeds. Mathematically, the trees are just coloured blobs (the seeds) connected by lines (the branches). As you build the forest, your first tree must only have at most one seed, your second tree must have at most two seeds, and so on. The forest dies whenever you build a tree that contains one of the older trees. There is a precise mathematical meaning to “contains one of the older trees”, but essentially you aren’t allowed to write down any combinations of blobs and branches that have gone before.

At the turn of the 1960s, the Game of Trees had piqued the interest of the great gossiping Hungarian mathematician Paul Erdős. Erdős is known for being a prolific collaborator, writing papers with over 500 other mathematicians. He was also an eccentric who would show up at the homes of his collaborators without warning. He would expect food and lodging and dismiss their children as “epsilons”, the term mathematicians often use for something infinitesimal. But Erdős would also be armed with a compendium of interesting mathematical problems, and if he had arrived at your door, chances are he thought you could solve it. In this particular story, Erdős was asking anyone who cared to listen if the Game of Trees could last forever. At Princeton University, a young mathematician who had just completed his doctorate was keen to take on Erdős’ latest problem. His name was Joseph Kruskal and he was able to prove that the Games of Trees could never last an eternity, but it could go on for a very long time.

So how long can the game actually last? This depends on how many different types of seed you have. If you only have one seed type, the forest cannot have more than one tree. For two types of seed, you have a maximum of three trees. As soon as we add a third type of seed, the game explodes. The maximum number of trees defies all comprehension, leaping towards a true numerical leviathan known as TREE(3).

Games like the Game of Trees are important. They can often be crucial in understanding processes that involve some sort of branching, such as decision algorithms in computer science, or the evolution of viruses and antibodies in epidemiology. And yet, despite these real-world applications, they can also generate a number that is too big for the universe.

TREE(3) really is that big. To see why, imagine you sit down with a friend and decide to play the Game of Trees with three different types of seed.  You know the game can last a while so you play as fast as you can without breaking up the space-time continuum. In other words, you draw a tree every 0.00000000000000000000000000000000000000000005 seconds. That’s equivalent to the Planck time, beyond which the fabric of space and time is overwhelmed by quantum effects.

After a year you will have drawn more than a trillion trillion trillion trillion trees, but you will be nowhere near the end of the game. You play for a lifetime before each of you is replaced by state-of-the-art artificial intelligence that shares your thoughts and personality. The game goes on. The AI mind-clones, powered using solar technology, continue playing long after humanity has destroyed itself through war or climate change or some other madness we haven’t even thought of yet.

After 300 million years, with the world’s continents now merged into one supercontinent and the sun noticeably brighter than before, AI you and your AI friend continue to play at breakneck speed. After 600 million years, the brightening sun has destroyed the Earth’s carbon cycle. Trees and forests can no longer grow, and the oxygen level begins to fall. The sun’s deadly ultraviolet radiation begins to break through Earth’s atmosphere, and by 800 million years, all complex life has been destroyed, except for the two AIs, who continue to play the Game of Trees.

After about 1.5 billion years, with Earth gripped by a runaway greenhouse effect, the Milky Way and Andromeda galaxies collide. The two AIs are too engrossed in their game to notice as the solar system is kicked unceremoniously out of the galaxy as a result of the collision. Billions of years pass as the sun runs out of fuel, turning into a red giant that comes dangerously close to swallowing Earth. Its outer layers drift away and the sun ends its life as a feeble white dwarf, barely bigger than Earth is now. The AIs are now struggling for a reliable source of energy but they continue to play. After a quadrillion years, the sun stops shining altogether. The AIs, starved of energy, have been replaced by an even more advanced technology, drawing energy from the bath of photons left over from the big bang, in the cosmic microwave background radiation. This technology continues to play the Game of Trees. The game is far from over, still some way short of its limit, at TREE(3) moves.

Between around 10⁴⁰ years and the googolannum (a googol years), the game continues against the backdrop of a spectacular era of black hole dominance, in which all matter has been guzzled by an army of black holes that march relentlessly across the universe. Beyond the googolannum, those black holes have decayed via a process known as Hawking radiation, leaving behind a cold and empty universe, warmed ever so slightly by a gentle bath of radiated photons. And yet, despite all that has passed, the Game of Trees continues.

Can it reach the limit of TREE(3) moves?

It cannot.

After 10 to the 10 to the 122 years, long before the Game of Trees is complete, the universe undergoes a Poincaré recurrence. It resets itself. This is because our universe is thought to be a finite system that can only exist in a finite number of quantum states. Poincaré recurrence, named after the celebrated French mathematician Henri Poincaré, is a property of any finite system, whether it’s the universe or a pack of playing cards. It says that as you move through the system at random, you will return, inevitably, to where you began. With a pack of cards, you shuffle and shuffle, and then after a long wait you eventually shuffle the pack so that all the cards are lined up just as they were when you first opened them. With our universe, it shuffles and shuffles between its various quantum states, and after around 10 to the 10 to the 122 years, it finds itself back in its primordial state.

The Game of Trees could never finish but it did demonstrate our ability to comprehend the incomprehensible, to go to places with mathematics that the physical world could never achieve. The truth is TREE(3) wasn’t too big for Erdős or Kruskal or any of the other mathematicians who contemplated it, but it was too big for the universe.

For more such insights, log into www.international-maths-challenge.com.

*Credit for article given to Antonio Padilla*

Finding how many knots there are for a given number of string crossings was thought to be an impossibly complex task. Now, algorithm engineering is cracking it – and showing us how to solve other fiendishly intricate maths problems.

IT USED to be one of the most frustrating part of any journey on public transport. You squeeze your way past the other bodies, sit down and fish your earphones out of your pocket. You didn’t bother to wind up the wires into a neat loop the last time you used them, and so – sigh – you now need to spend the next 5 minutes untangling this knot. Thank goodness for the invention of wireless earbuds.

Knots aren’t just an everyday annoyance, though. They are also a source of endless inspiration for researchers. Take mathematician Benjamin Burton, who is fascinated by one simple question: how many knots are there? “There is something tantalising about problems that you can describe to a 10-year-old, but that mathematicians have not yet solved,” he says.

Taking a census of knots is one of those problems that ought to be impossible to solve because of its complexity. There are so many ways the strings can be crossed and looped that even the fastest computer could never catalogue them all. Yet Burton has been giving it a shot, and along the way he is showing that, with a few clever computational tricks, many maths problems that seem insurmountable might not be.

Knots and science have been, ahem, entangled for quite a while. In the dying decades of the 19th century, scientists were grappling with how to understand atoms. One hypothesis saw them as little vortices of fluid that became stable when knotted. Lord Kelvin, who went on to become the president of the UK’s Royal Society, was the first to suggest that each chemical element corresponded to a different type of knot.

The idea was abandoned after the discovery of the electron, but at the time it seemed vital to understand knots. Physicist Peter Guthrie Tait was the first to make a stab at creating a comprehensive list of them. Cards on the table: there are an infinite number of possible knots, because you can keep on adding extra knotty flourishes forever. The question mathematicians are interested in is more subtle. A defining feature of a knot is its crossing number, the number of times the strings cross. The question is, for a given number of crossings, how many different knots are possible? In 1885, Tait, working with mathematician Thomas Kirkman, considered all the knots with up to and including 10 crossings. Drawing them all by hand, he tabulated 364 configurations.

Try to go further and things quickly get a lot more difficult. As you allow more crossings, the number of possible knots rapidly increases. The last major extension to the knot tables was published in 1998. Mathematicians Jim Hoste, Morwen Thistlethwaite and Jeff Weeks recorded all the knots up to and including 16 crossings – all 1.7 million of them.

Going beyond this has, until recently, been unfeasible. To see why, we need to know a bit more about how mathematicians think about knots (see “When is a knot not a knot?“). Unlike real-world knots that are often pieces of string with loose ends, mathematical knots are closed. Imagine tying a knot in a piece of spaghetti, then melding the free ends.

Stretch, twist, bend

Mathematicians treat knots according to the rules of topology, a branch of geometry. These say that a knot remains fundamentally the same if you stretch, twist or bend the strands – but making cuts or new joins is a no-no. This leads to the concept of a prime knot, a knot that can’t be mathematically broken down into two or more simpler knots.

The job of tabulating knots, then, boils down to comparing elaborate tangles to see if they are really the same prime knot. Don’t underestimate how tricky this can be. For 75 years, two knots with 10 crossings were listed separately in tables. But in 1973, Kenneth Perko, a New York lawyer who had studied maths, realised that if you take the mirror image of one, you can manipulate it to become equivalent to the other. The knots are known as the “Perko pair”.

When dealing with millions of knots, the job of identifying doppelgangers becomes so time-consuming that even the fastest supercomputers shouldn’t be theoretically capable of it in a reasonable amount of time. Still, in 2019, Burton, who is based at the University of Queensland in Australia, decided the time was ripe to take a punt.

He knew there is a difference between a knot-sorting algorithm in the abstract and how that algorithm is implemented in computer code. The art of bridging this gap is known as algorithm engineering and Burton thought that with the right tricks, the problem wouldn’t be as hard as it seemed. “Part of what motivated me was creating a showpiece to see if the tools were good enough,” he says.

He began by setting a computer the task of dreaming up all the possible ways that strings can be knotted with up to and including 19 crossings. This is a comparatively simple task and the computer spat out 21 billion knot candidates after just a few days.

The job was then to check each knot was prime and distinct. This involves storing a full topological description of the knots in a computer’s working memory or RAM. A data set of 21 billion knots would require more than 1 terabyte of RAM to store, and computers with that amount are rare. To get around this, Burton made use of a software package he has developed called Regina. It can convert knots into “knot signatures”, strings of letters that capture each tangle’s defining topological properties. The signatures can be stored far more economically than a knot description. Plus, knots that are tangled differently but are really equivalent have the same signature, making it easy to weed out duplicates. Burton managed to whittle down the candidate knots to about 7 billion in a day.

This method wasn’t powerful enough to identify every last duplicate, however. Burton’s next tactic involved calculating what is known as a knot invariant for each candidate knot. Invariants are mathematical objects that capture the essence of a knot – if two knots have different invariants, they are different knots. Invariants are more powerful than signatures, but they are harder to compute: it would have taken Burton’s computer more than a year to calculate these for all the remaining knots. By sorting them into groups and running them on parallel supercomputers, he got through them in days. The pool was down to 370 million.

Burton also had to grapple with non-hyperbolic knots, an especially challenging category. But after several more rounds of sorting, the supposedly impossible became possible. Burton’s census extended the knot tables to cover everything up to and including 19 crossings. The final tally: 352,152,252 knots.

Ian Agol at the University of California, Berkeley, says he is impressed with the calculations. “It will likely be useful to mathematicians searching for knots with specific properties, or who have a knot that they would like to identify,” he says.

He and other mathematicians think that Burton’s work is also an impressive example of algorithm engineering. “This is a growing trend in pure mathematics, where computational methods are being used in more creative ways,” says Hans Boden at McMaster University in Ontario, Canada.

Lorries and cameras

There are plenty of practical problems where algorithm engineering is used to find efficient solutions to hard problems. Some of the most important are in logistics, where optimised routing can save time and huge sums of money. Others include working out how to cover a space with CCTV cameras. In many cases, a perfect solution is impossible to obtain in a reasonable time frame.

This is also the case when it comes to mapping complex evolutionary histories, particularly for plants and bacteria. Algorithms are used to link DNA data in phylogenetic trees, graphs that group closely related species more closely than distantly related ones. However, sometimes genes don’t pass down from parent to offspring, but rather through what is known as horizontal gene transfer from one species to another. Algorithms designed to map these transfers can be very slow.

One algorithm engineering hack to get around this involves parametrising data inputs to make them smaller. For instance, if you fix the number of potential mutations you are considering, the problem can be solved efficiently. Recently, Edwin Jacox, now at the University of California, Santa Cruz, and his colleagues applied this method to cyanobacteria phylogenetic trees. Cyanobacteria played a major role in Earth’s changing biosphere more than 2 billion years ago. The researchers developed a parametrised algorithm that rebuilds the cyanobacteria phylogenetic trees in just 15 seconds.

Whether it is reconstructing evolutionary trees or listing knots, it is clear than the toughest computing problems can be made tractable. “With algorithm engineering and heuristics, things that are slow in practice turn out to be remarkably, surprisingly fast,” says Burton. It means that even the trickiest problems don’t have to leave us in an inescapable tangle.

When is a knot not a knot?

Here is a problem that needs unpicking: if you pull at a messy tangle of wires, how do you know if it will just get more tangled or come apart into a simple loop? This is a problem mathematicans call “unknot recognition” and it is one we might soon solve. Unknot recognition fascinates mathematicians and computer scientists alike because it is part of the famous “P vs NP” question.

To see how it works, take the classic travelling salesperson problem, where we must work out the shortest route for a salesperson to visit a number of cities. If an algorithm designed to solve this problem doesn’t get exponentially harder as more cities are included, it is said to be “P”. This means it is solvable in reasonable – or polynomial, in maths speak – amounts of time. Once you have an answer, you need to check it is correct. If it is easy to check your answer, the problem is classed as “NP”. The big question for mathematicians is whether all NP problems are also P. This is one of the Millennium Prize Problems – answer it conclusively and you will win $1 million.

Unknot recognition dwells in the twilight zone of P vs NP. We already know that this problem is definitely “NP”, or easy to check. If your algorithm can produce an unknotted loop, you can immediately see it has worked. Mathematicians also think it is likely to be P, and we are tantalisingly close to proving it.

In 2014, Benjamin Burton at the University of Queensland in Australia developed an unknotting algorithm that, in practice, solves in polynomial time. His algorithm has held up “for every knot we’ve thrown at it so far”, he says. More recently, Marc Lackenby at the University of Oxford developed an unknot recognition algorithm that is “quasi-P” (which, in maths parlance, means “almost there”). It is unlikely to be converted into executable computer code because it is so complicated, but Lackenby is confident that a simplified version “is going to be genuinely practical”.

Showing that unknot recognition is both P and NP won’t solve the wider Millennium Prize Problem, though it could give us useful pointers. Still, it is an important milestone and mathematicians will be celebrating once we get there.

For more such insights, log into www.international-maths-challenge.com.

*Credit for article given to Larissa Fedunik*