Author: IMC

Fermat’s last theorem puzzled mathematicians for centuries until it was finally proven in 1993. Now, researchers want to create a version of the proof that can be formally checked by a computer for any errors in logic.

Mathematicians hope to develop a computerised proof of Fermat’s last theorem, an infamous statement about numbers that has beguiled them for centuries, in an ambitious, multi-year project that aims to demonstrate the potential of computer-assisted mathematical proofs.

Pierre de Fermat’s theorem, which he first proposed around 1640, states that there are no integers, or whole numbers, a, b, and c that satisfy the equation aⁿ + bⁿ = cⁿ for any integer n greater than 2. Fermat scribbled the claim in a book, famously writing: “I have discovered a truly marvellous proof of this, which this margin is too narrow to contain.”

It wasn’t until 1993 that Andrew Wiles, then at Princeton University, set the mathematical world alight by announcing he had a proof. Spanning more than 100 pages, the proof contained such advanced mathematics that it took more than two years for his colleagues to verify it didn’t contain any errors.

Many mathematicians hope that this work of checking, and eventually writing, proofs can be sped up by translating them into a computer-readable language. This process of formalisation would let computers instantly spot logical mistakes and, potentially, use the theorems as building blocks for other proofs.

But formalising modern proofs can itself be tricky and time-consuming, as much of the modern maths they rely on is yet to be made machine-readable. For this reason, formalising Fermat’s last theorem has long been considered far out of reach. “It was regarded as a tremendously ambitious proof just to prove it in the first place,” says Lawrence Paulson at the University of Cambridge.

Now, Kevin Buzzard at Imperial College London and his colleagues have announced plans to take on the challenge, attempting to formalise Fermat’s last theorem in a programming language called Lean.

“There’s no point in Fermat’s last theorem, it’s completely pointless. It doesn’t have any applications – either theoretical or practical – in the real world,” says Buzzard. “But it’s also a really hard question that’s become infamous because, for centuries, people have generated loads of brilliant new ideas in an attempt to solve it.”

He hopes that by formalising many of these ideas, which now include routine mathematical tools in number theory such as modular forms and Galois representations, it will help other researchers whose work is currently too far beyond the scope of computer assistants.

“It’s the kind of project that could have quite far-reaching and unexpected benefits and consequences,” says Chris Williams at the University of Nottingham, UK.

The proof itself will loosely follow Wiles’s, with slight modifications. A publicly available blueprint will be available online once the project is live, in April, so that anyone from Lean’s fast-growing community can contribute to formalising sections of the proof.

“Ten years ago, this would have taken an infinite amount of time,” says Buzzard. Even so, he will be concentrating on the project full-time from October, putting his teaching responsibilities on hold for five years in an effort to complete it.

“I think it’s unlikely he’ll be able to formalise the entire proof in the next five years, that would be a staggering achievement,” says Williams. “But because a lot of the tools that go into it are so ubiquitous now in number theory and arithmetic geometry, I’d expect any substantial progress towards it would be very useful in the future.”

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

*Credit for article given to Alex Wilkins*

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*

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*

How can you ensure you use the fewest bags when loading your shopping? A dash of maths will help, says Peter Rowlett.

You have heaped your shopping on the supermarket conveyor belt and a friendly member of the checkout staff is scanning it through. Items are coming thick and fast and you would like to get them in as few bags as possible. What is your strategy?

This is an example of an optimisation problem, from an area of maths called operational research. One important question is, what are you trying to optimise? Are you thinking about the weight of the items, or how much space they will take up? Do you guess how many bags you might need and start filling that many, or put everything in one until you need to start another?

We design algorithms to solve packing problems when they come up at a larger scale than your weekly shop, like making better use of warehouse space or fitting boxes into delivery vans. Similar algorithms are used for cutting raw materials with minimal waste and storing data on servers.

Bag-packing algorithms generally involve placing items into a single bag until you get to one that won’t fit because you have hit a maximum weight or size. When necessary, you open a second bag, and each time you reach an item that won’t fit in an existing bag, you start a new one.

If you are filling multiple bags at once, it is likely you will come across an item that could fit in more than one bag. Which do you choose? There is no clear best answer, but different algorithms give different ways to make this decision. We are looking for rules that can be applied without detailed thought. You might have more subtle requirements, like putting two items in the same bag because they go in the same cupboard at home, but here we want the kind of simple rule a computer program can mindlessly apply to get the most efficient outcomes, using the fewest bags, every time.

One algorithm we could employ is called first fit. For each new item, you look through the bags in the order you opened them, placing the item in the first one it fits in. An advantage is that this is quick to implement, but it can overlook options and end up using more bags than needed.

An alternative that often uses fewer bags overall is called worst fit. When faced with a choice, you look through the currently open bags for the one with the most space and place the item there.

These algorithms work more effectively if you handle the objects in decreasing order – packing the largest or heaviest first will usually need fewer bags.

So now you are armed with a secret weapon for packing: the worst-fit decreasing algorithm. The next time you are in the checkout line, load your bulkiest shopping onto the conveyor belt first, and always put items in the bag with the most space available – it might just help you use fewer bags overall.

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

*Credit for article given to Peter Rowlett*

When you look at a train or university timetable you don’t think about how the timetable was made – you’re thinking about your trip or where your next class is.

In that moment, you couldn’t care less about all the juggling and compromising that needs to happen to get a timetable working.

Not surprisingly, though, this is a difficult process dating back many years and one that perplexes mathematicians even today.

To understand the difficulty associated with creating timetables – those timetables we all rely so heavily on – we need to understand the nature of difficulty itself.

In particular, we need to understand how it applies in a mathematical context.

Seriously, how hard can it be?

Not surprisingly, some tasks in mathematics are harder than others – but even this perception is complicated. Many important computational tasks are hard, or at least appear to be hard.

Knowing precisely what “hard” and “easy” mean has itself turned out to be extremely challenging. To really know a computational task is hard, we have to really know that there isn’t some nice efficient method waiting to be discovered that would render the task straightforward.

Our old friend timetabling is a classic example of a problem for which the precise difficulty is unknown.

I don’t get it, and my train’s leaving …

Consider a university timetable: a computer can easily check that such a timetable has no clashes but a clash-free timetable cannot (in general) be guaranteed. Because of this, finding a timetable with the minimum number of clashes is a genuine mathematical challenge.

Commercial timetabling applications can’t in general do any better than attempt to approximate the minimum number of clashes.

As yet, no-one has yet proved that timetabling cannot be solved efficiently. In fact, the ability to solve timetabling efficiently hinges on one of the foremost unsolved problems in mathematics: the so-called “P vs NP” problem.

A Millennium Problem

Roughly speaking, the “P vs NP” problem asks whether:

1) finding correct solutions to a problem (e.g. constructing a clash-free timetable) is genuinely harder task than …

2) … simply checking a given correct solution (e.g. checking to see if a completed timetable is clash-free).

Intuitively, you would believe finding a solution should be harder than checking a solution.

Think of your favourite Sudoku puzzle: checking that your solution is correct is easy – each square, column and row can only contain each number from one to nine once. But finding the solution – completing the puzzle – is hard graft.

But it’s not quite as simple as that.

In 2000, the Clay Institute chose “P vs NP” as one of seven Millennium Prize problems, with a $1 million prize for the person who solves it.

Constraint satisfaction

Algebraic and logical methods have proved particularly useful in understanding what determines the difficulty of a problem.

Among the computational problems in the NP class – i.e. problems that can’t “easily” be solved by a computer – Constraint Satisfaction Problems (or CSPs, as they are affectionately known) have received particular attention.

Any problem that involves giving values to a large collection of objects that obey some constraints is a CSP – and timetabling is one such problem.

In a school or university setting, we assign exam slots to particular subjects, obeying the constraint that subjects with common enrollment are scheduled at different times.

Map colouring is a CSP closely related to timetabling. In the above image we gave each state and territory one of three colours – red, green or blue – with the constraint that neighbouring states and territories must have different colours.

Map colouring is typical of “hard” problems in the class NP: given a successfully three-coloured map it is easy to verify that it obeys the neighbouring region constraint (so checking is easy). But in general there is no known efficient algorithm for deciding if a map can be a successfully three-coloured.

With every CSP one may associate an algebraic structure, but be warned: even by the imaginative standards of modern algebra, these structures are unusual beasts.

Numbers of the beast

In the familiar high school “algebra of numbers”, operations such as addition and multiplication are used to combine numbers to produce new ones. So, combining 1 and 2 using + gives 3.

For a CSP such as timetabling though, the role of numbers is taken by the available timetable slots, and the operations used to combine these are even more bizarre.

(How bizarre are these operations? Well, they are “technical generalisations of symmetries”, known as “polymorphisms”. You did ask!)

Despite their unusual character, these weird algebraic oddities are known to precisely determine the difficulty of a CSP.

A problem such as timetabling turns out to have very few polymorphisms: a classic hallmark of a difficult problem.

Many mathematicians and theoretical computer scientists around the world are working hard to prove it is precisely this absence of interesting properties that causes computational difficulty.

Will anyone ever solve this mighty head-scratcher? The chance of winning a Millenium Prize – not to mention $1 million – is definitely a motivating factor.

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

*Credit for article given to Peter Rowlett*

Can three cubed numbers be added up to give 42? Until now, we didn’t know

It might not tell us the meaning of life, the universe, and everything, but mathematicians have cracked an elusive problem involving the number 42.

Since the 1950s, mathematicians have been puzzling over whether any integer – or whole number – can be represented as the sum of three cubed numbers.

Put another way: are there integers k, x, y and z such that k = x³ + y³ + z³ for each possible value of k?

Andrew Booker at Bristol University, UK, and Andrew Sutherland at the Massachusetts Institute of Technology, US, have solved the problem for the number 42, the only number less than 100 for which a solution had not been found.

Some numbers have simple solutions. The number 3, for example, can be expressed as 1³ + 1³ + 1³ and 4³ + 4³ + (-5) ³ . But solving the problem for other numbers requires vast strings of digits and, correspondingly, computing power.

The solution for 42, which Booker and Sutherland found using an algorithm, is:

42 = (-80538738812075974)³ + 80435758145817515³ + 12602123297335631³

They worked with software firm Charity Engine to run the program across more than 400,000 volunteers’ idle computers, using computing power that would otherwise be wasted. The amount of processing time is equivalent to a single computer processor running continuously for more than 50 years, says Sutherland.

Earlier this year, Booker found a sum of cubes for the number 33, which was previously the lowest unsolved example.

We know for certain that some numbers, such as 4, 5 and 13, can’t be expressed as the sum of three cubes.

The problem is still unsolved for 10 numbers less than 1000, the smallest of which is 114.

The team will next search for another solution to the number 3.

“It’s possible we’ll find it in the next few months; it’s possible it won’t be for another hundred years,” says Booker.

People interested in aiding the search can can volunteer computing power through Charity Engine, says Sutherland.

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

*Credit for article given to Donna Lu*

What is pure mathematics? What do pure mathematicians do? Why is pure mathematics important?

These are questions I’m often confronted with when people discover I do pure mathematics.

I always manage to provide an answer but it never seems to fully satisfy.

So I’ll attempt to give a more formulated and mature response to these three questions. I apologise ahead of time for the oversimplifications I’ve had to make in order to be concise.

Broadly speaking, there are two different types of mathematics (and I can already hear protests) – pure and applied. Philosophers such as Bertrand Russell attempted to give rigorous definitions of this classification.

I capture the distinction in the following, somewhat cryptic, statement: pure mathematicians prove theorems and applied mathematicians construct theories.

What this means is that the paradigm in which mathematics is done by the two groups of people are different.

Pure mathematicians are often driven by abstract problems. To make the abstract concrete, here are a couple of examples: “are there infinitely many twin primes” or “does every true mathematical statement have a proof?”

To be more precise, mathematics built out of axioms, and the nature of mathematical truth is governed by predicate logic.

A mathematical theorem is a true statement that is accompanied by a proof that illustrates its truth beyond all doubt by deduction using logic.

Unlike an empirical theory, it is not enough to simply construct an explanation that may change as exceptions arise.

Something a mathematician suspects of being true due to evidence, but not proof, is simply conjecture.

Applied

Applied mathematicians are typically motivated by problems arising from the physical world. They use mathematics to model and solve these problems.

These models are really theories and, as with any science, they are subject to testifiability and falsifiability. As the amount of information regarding the problem increases, these models will possibly change.

Pure and applied are not necessarily mutually exclusive. There are many great mathematicians who tread both grounds.

Pure

There are many problems pursued by pure mathematicians that have their roots in concrete physical problems – particularly those that arise from relativity or quantum mechanics.

Typically, in a deeper understanding of such phenomena, various “technicalities” arise (believe me when I tell you these technicalities are very difficult to explain). These become abstracted away into purely mathematical statements that pure mathematicians can attack.

Solving these mathematical problems then can have important applications.

Ok computer

Let me give a concrete example of how abstract thought lead to the development of a device that underpins the functions of modern society: the computer.

The earliest computers were fixed program – i.e. they were purpose-built to perform only one task. Changing the program was a very costly and tedious affair.

The modern remnants of such a dinosaur would be a pocket calculator, which is built to only perform basic arithmetic. In contrast, a modern computer allows one to load a calculator program, or word-processing program, and you don’t have to switch machines to do it.

This paradigm shift occurred in the mid 1940s and is called the stored-program or the von Neumann architecture.

The widely accessible, but lesser-known, story is that this concept has its roots in the investigation of an abstract mathematical problem called the Entscheidungsproblem (decision problem).

The Entscheidungsproblem was formulated in in 1928 by the famous mathematician David Hilbert.

It approximately translates to this: “does there exist a procedure that can decide the truth or falsehood of mathematical statement in a finite number of steps?”

This was answered in the negative by Alonzo Church and Alan Turing independently in 1936 and 1937. In his paper, Turing formulates an abstract machine, which we now call the Turing machine.

The machine possesses an infinitely long tape (memory), a head that can move a step at a time, read from and write to the tape, a finite instruction table which gives instructions to the head, and a finite set of states (such as “accept”, or “deny”). One initiates the machine with input on the tape.

Such a machine cannot exist outside of the realm of mathematics since it has an infinitely long tape.

But it is the tool used to define the notion of computability. That is, we say a problem is computable if we can encode it using a Turing machine.

One can then see the parallels of a Turing machine with a fixed-program machine.

Now, suppose that there is a Turing machine U that can take the instruction table and states of an arbitrary Turing machine T (appropriately encoded), and on the same tape input I to T, and run the Turing machine T on the input I.

Such a machine is called a Universal Turing Machine.

In his 1937 paper, Turing proves an important existence theorem: there exists a universal Turing machine. This is now the parallel of the store-program concept, the basis of the modern programmable computer.

It is remarkable that an abstract problem concerning the foundations of mathematics laid the foundations to the advent of the modern computer.

It is perhaps a feature of pure mathematics that the mathematician is not constrained by the limitations of the physical world and can appeal to the imagination to create and construct abstract objects.

That is not to say the pure mathematician does not formalise physical concepts such as energy, entropy etcetera, to do abstract mathematics.

In any case, this example should illustrate that the pursuit of purely mathematical problems is a worthwhile cause that can be of tremendous value to society.

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

*Credit for article given to Lashi Bandara*

Calculating Ramsey numbers is so difficult that one mathematician once said he’d rather fight off an alien invasion. Now, mathematicians have made the first major advance in nearly a century.

The key to a successful party is a good mix of people

Mathematicians have made a breakthrough on an incredibly difficult problem in combinatorics, the study of combinations. It is the first significant advance in nearly a century for our understanding of Ramsey numbers, which can be used to describe the minimum size of a party where cliques of a certain size can or can’t exist.

Named after mathematician Frank Ramsey, these numbers deal with the possible relationships between nodes on a mathematical network called a graph, which are a major object of study in maths. The numbers, first discovered in 1928, can be described in terms of people at a party.

Suppose you are hosting a party and want to make sure there is a good balance between people who know each other and those who don’t. Too many mutual acquaintances will form a clique, excluding the others at the party, while too few risks an anti-clique, plagued by awkward small talk.

The question, then, is whether there is a minimum party size that will always produce a clique or anti-clique of a certain size. This is the Ramsey number. For instance, the Ramsey number for a clique of three is six, because in a six-person party you can always find either a clique of three people who know each other, or who don’t.

While this is simple for small numbers, like three, it rapidly becomes very difficult to calculate for larger numbers as the possible combinations grow. It has long been a goal for mathematicians to find a general solution for any Ramsey number.

Paul Erdős, who in 1935 found that the upper limit for any Ramsey number is 4 to the power of the clique size, once said that finding the exact Ramsey number for a clique of six was so difficult that if aliens asked us to try to calculate it, or be destroyed, we would have no choice but to try to attack them first. Since then, generations of mathematicians have tried to significantly improve upon Erdős’s limit, but without much success.

Now, Julian Sahasrabudhe at the University of Cambridge and his colleagues have shown the upper limit for Ramsey numbers can be reduced from 4 to the power of the clique size to 3.993 to the power of the clique size.

“From the outside, it seems sort of silly — like, OK, mathematicians are just trying to improve some number and who cares?” says Sahasrabudhe. “But what’s interesting about these quantitative changes, like the difference between the Erdős bound and previous bounds and our work, is there’s really some quantitative improvement that reflects a deepening of our understanding of the [mathematical] structures.”

Sahasrabudhe and his colleagues first started working on the problem in 2018, at the National Institute for Pure and Applied Mathematics in Rio de Janeiro, Brazil. “It’s a famous problem and we wanted to be ambitious and had some ideas — and it seemed like it was actually going pretty well, which was exciting,” says Sahasrabudhe.

In the first few months the team had sketched out a rough plan of what the proof could look like, he says, but quickly ran into an obstacle, which involved calculating how points clumped together on high-dimensional spheres.

After trying to solve this problem for years and failing, Sahasrabudhe and his team realised they could reformulate their proof to avoid the sphere question entirely, after which things rapidly progressed. “Instead of going over the mountain, we realised we could actually somehow sneak around it,” he says.

The final proof, which is more than 50 pages long and yet to be formally verified, uses elements of Erdős’s original proof, which involved zooming into particular people in arbitrarily large parties and working out the probabilities of their relationships to their neighbours, and also identifying adjacent structures to cliques called “books”, which are easier to find but guarantee that cliques exist.

“For at least the last 50 years, every eminent person in my field has tried quite hard to improve these bounds and failed,” says David Conlon at the California Institute of Technology. “The fact that they have now improved this result is a big deal.”

Now that the barrier of 4 has been broken, other researchers can now use and optimise Sahasrabudhe and his team’s methods to get the number slightly lower than 3.993. “This is a fiendishly hard problem,” says Peter Cameron at the University of St Andrews, UK. “A tiny little improvement like this represents a huge breakthrough in techniques for attacking it.”

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

*Credit for article given to Alex Wilkins*

Not only do quantum computers have the edge over classical computers on some tasks, but they are also exponentially faster, according to a new mathematical proof.

A chip from Google’s Sycamore quantum computer

It’s official – there is now proof that quantum computers can perform some tasks exponentially faster than classical computers, and it could massively boost their usefulness.

Quantum computers use quantum bits, or qubits, to measure and extract information. Unlike the bits of classical computers, which can store a 1 or 0, qubits can store multiple values at the same time. This theoretically gives them a huge speed advantage over classical computers and algorithms. However, demonstrating that the machines have this quantum advantage, and can actually beat regular machines, hasn’t been easy.

In 2018, for instance, an example of quantum advantage – for recommendation systems such as those you might find on Netflix or Amazon – was overturned and shown to be achievable using a classical algorithm.

Now, however, Hsin-Yuan Huang at the California Institute of Technology and his colleagues have proved mathematically that not only can quantum computers have the edge on some tasks, they can be exponentially faster too.

“We now have the right mathematical framework for proving this exponential separation,” says Huang. People have flipped between saying it is possible to get exponential speed-up and becoming very pessimistic about it, he says. “It’s like a rollercoaster ride.”

Speed advantage

Huang and his team used their mathematical framework to prove the speed advantage on three broad classes of quantum problems, which involved measuring and predicting properties of a quantum system, extracting information from noisy real-world signals and learning how quantum systems change through time. For each problem, they showed that the classical version of the experiment would need to be run an exponential number of times more.

Unlike previous examples of quantum advantage like boson sampling, these problems could have useful applications, such as building advanced sensors to detect gravitational waves or measuring complex biological systems.

The researchers then performed two experiments that demonstrated this advantage on Google’s Sycamore quantum computer, made challenging by the presence of statistical noise, which wasn’t covered in their proofs.

The first experiment measured quantum properties of a system that is inaccessible to classical computers because of the uncertainty principle, which says, for example, that we can’t be certain about both the position and the momentum of particles at the same time. The second experiment involved finding whether a quantum process was the same if it was run forwards or backwards in time, which could be important in high-energy and nuclear physics.

“The authors are able to show that there are some experiments where there’s a lower bound on how many samples you’re going to need using a classical computer,” says Ashley Montanaro at the University of Bristol, UK. “They’re able to outperform that bound even using a noisy quantum computer, which, for me, is a very impressive achievement given the early stage of today’s quantum hardware.”

While the framework that Huang and his team came up with is general, they only used it for specific classes of problems. Future work will need to explicitly prove quantum advantage for many more quantum problems, says Huang.

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

*Credit for article given to Alex Wilkins*

 

Let’s lay down some definitions:

• Let FF be a field and let EE be an extension of FF. An element α∈Eα∈E is algebraicover FF if there is a polynomial f(x)f(x) in F[x]F[x] such that f(α)=0f(α)=0 (i.e. α∈Eα∈E is an algebraic element if it is the root of some polynomial with coefficients in FF).
• Let FF be a field and let EE be an extension of FF. If K⊂EK⊂E is a subset of EE which contains all elements which are algebraic over FF, then KK is actually a subfieldof EE and an algebraic extension of FF. We call KK the algebraic closure of FF and denote it by ¯¯¯¯FF¯. [1]

It’s a fact that an algebraic closure ¯¯¯¯FF¯ exists for every field FF (and is actually unique up to isomorphism). So we can draw a containment picture like the one above.

Those familar with some topology and/or analysis will notice that such a “field tower” is suggestive of a vaguely analogous result: given a topological space XX we can always (assuming some conditions about XX, namely it being locally-compact Hausdorff) stick an open set VV and its closure ¯¯¯¯VV¯ between a certain compact set KK and open set UU:  K⊂V⊂¯¯¯¯V⊂U.K⊂V⊂V¯⊂U.

Now, don’t buy too much into the analogy. I only mention this topological result to motivate the fact that the closure of a set and the algebraic closure of a field do indeed convey the same concept: wholeness. It seems then that we can view algebraic elements as the mathematical cousins of limit points of sequences of real numbers. Why? Because, topologically speaking, what is the closure of a set? The collection of limit points of that set, right? So in particular, when we let our topological space be RR, the set of real numbers (with the usual topology) and consider the subset {xn}∞n=1{xn}n=1∞ – some sequence of real numbers,

• we say x∈Rx∈R is a limit pointof {xn}{xn} if for every ϵ>0ϵ>0 there is an n∈Nn∈N such that |xn−x|<ϵ|xn−x|<ϵ.

Then in light of our comments above, we can make the analogous statement for a subset of polynomials {fn(x)}⊂F[x]⊂E[x]{fn(x)}⊂F[x]⊂E[x]:

• We say α∈Eα∈E is an algebraic element(over FF) if there is an n∈Nn∈N such that fn(α)=0fn(α)=0**.

Notice there’s no need for an approximation by ϵϵ in the second bullet. Why? Well, imagine placing a “metric” dd on E[x]E[x] by d:E[x]×E[x]→Ed:E[x]×E[x]→E via***

(So intuitively, f(x)f(x) is far away from αα if αα is not a root, but if αα is a root of f(x)f(x), then f(x)f(x) and αα are just as close as they can be.) In this way, the distance between an algebraic element and its corresponding polynomial is precisely 0. So in this case there’s no need to approximate a distance of zero by an arbitrarily small ϵϵ-ball – we have zero exactly!

And thus we have stumbled upon another insight into one of the main differences between analysis and algebra: you know the adage –

Analysts like inequalies; algebraists like equalities!

Digging Deeper

It would be interesting to see if there’s something in the language of category theory which allows one to see that closure of an algebraic field and closure of a topological set really are the same. Now I don’t know much about categories, but as one of my classmates recently suggested, we might want to look for a functor from the category of fields to the category of topological spaces such that the operation of closure is equivalent in each. In this case, perhaps it’s more appropriate to relate an algebraic closure to the completion of a topological space, as opposed to its closure. Admittedly, I’m not sure about all the details, but I think it’s worth looking into!

Footnotes:

* This is actually a bit deceiving. How we measure “closeness” really depends on the topology of the space we’re working on. For example, we can place the ray topology on RR so that the open sets are intervals of the form (a,∞)(a,∞) for a∈Ra∈R. Then in the strict definition of a limit point we see that -763 is a limit point of the interval (0,1)(0,1) even though it’s “far away”!

** Okay okay… there’s no reason to assume an arbitrary collection of polynomials is countable. I really should write FF for some family of polynomials in which case this statement would read “…if there is some f∈Ff∈F such that f(α)=0f(α)=0.” But bear with me for analogy’s sake.

*** I put “metric” in quotes here because as defined dd is not a metric in the strict sense of the word. Indeed, we don’t have the condition d(f(x),α)=0d(f(x),α)=0 if and only if “f(x)=αf(x)=α” since the latter is like comparing apples and oranges! But it would be interesting to see if we could place looser version of a metric on a polynomial ring. For instance, the way I’ve defined dd here, an open ball centered at αα would correspond to all polynomials in E[x]E[x] which have αα as a root! This idea seems to be related to Hilbert’s Nullstellensatz and the Zariski topology.

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

*Credit for article given to Tai-Danae Bradley*