Author: IMC

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*

Mathematicians who have studied the most efficient way to pack spheres in eight-dimensional space and the spacing of prime numbers are among this year’s recipients of the highest award in mathematics, the Fields medal.

Mathematicians who have studied the most efficient way to pack spheres in eight-dimensional space and the spacing of prime numbers are among this year’s recipients of the highest award in mathematics, the Fields medal.

The winners for 2022 are James Maynard at the University of Oxford; Maryna Viazovska at the Swiss Federal Institute of Technology in Lausanne (EPFL); Hugo Duminil-Copin at the University of Geneva, Switzerland; and June Huh at Princeton University in New Jersey.

Kyiv-born Viazovska is only the second female recipient among the 64 mathematicians to have received the award.

“Sphere packing is a very natural geometric problem. You have a big box, and you have an infinite collection of equal balls, and you’re trying to put as many balls into the box as you can,” says Viazovska. Her contribution was to provide an explicit formula to prove the most efficient stacking pattern for spheres in eight dimensions – a problem she says took 13 years to solve.

Maynard’s work involved understanding the gaps between prime numbers, while Duminil-Copin’s contribution was in the theory of phase transitions – such as water turning to ice, or evaporating into steam – in statistical physics.

June Huh, who dropped out of high school aged 16 to become a poet, was recognised for a range of work including the innovative use of geometry in the field of combinatorics, the mathematics of counting and arranging.

The medal, which is considered to be as prestigious as the Nobel prize, is given to two, three or four mathematicians under the age of 40 every four years.

The awards were first given out in 1936 and are named in honour of Canadian mathematician John Charles Fields. This year’s awards were due to be presented at the International Congress of Mathematicians in Saint Petersburg, Russia, but the ceremony was relocated to Helsinki, Finland.

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

*Credit for article given to Matthew Sparkes*

Do you know someone who knows someone? We have all played this game, often to be amazed that despite the extreme scale of human society, random people can be linked through very small chains of acquaintances—typically, around six. Recently, a group of researchers from across the globe discovered that this magic of six degrees can be explained mathematically. The intriguing phenomenon, they show, is linked to another social experience we all know too well—the struggle of cost vs. benefit in establishing new social ties.

In 1967, a farmer in Omaha, Nebraska received a peculiar letter in his mailbox. The sender was Prof. Stanley Milgram, of Harvard University, and the intended recipient was one of his peers. “If you happen to know this person,” the message read, “please forward this letter to him.”

Of course, the chances of such a direct acquaintance across such a vast social and geographical distance—from Boston to Omaha—were extremely slim, and therefore, the letter further requested that if the recipient didn’t know the intended addressee, they should forward the letter to someone who might.

This letter was one of about 300 identical packages sent with similar instructions. The 300 independent letters began circulating across the United States in pursuit of a social pathway linking “Joe” from the farmlands of middle America with the academic hub of the East Coast. Not all letters made it through, but the ones that did recorded, for the first time experimentally, the familiar social paths—a friend of a friend of a friend—that connect American society.

Quite surprisingly, the paths were found to be extremely short. In a society of hundreds of millions of individuals, the experiment found that it only takes about six handshakes to bridge between two random people. Indeed, Milgram’s experiment confirmed what many of us sense intuitively, that we live in a small world, divided by a mere six degrees of separation.

As groundbreaking as it was, Milgram’s experiment was also shaky. For example, it did not count the letters that didn’t reach their final destination. Most letters never reached their destination in Boston. The few letters that actually did arrived through six steps on average. His findings, however, were reaffirmed in a series of more systematic studies: for example, the millions of users of Facebook are on average five to six clicks apart from one another. Similar distances were also measured across 24,000 email users, actor networks, scientific collaboration networks, the Microsoft Messenger network and many others. Six degrees kept coming up.

Hence, social networks of vastly different scale and context tend to feature extremely short pathways. And most importantly, they seem to universally favour the magic number of six. But why?

A recent paper published in Physical Review X by collaborators from Israel, Spain, Italy, Russia, Slovenia and Chile, shows that simple human behaviour—weighing the costs and benefits of social ties—may uncover the roots of this intriguing phenomenon.

Consider individuals in a social network. Naturally, they wish to gain prominence by navigating the network and seeking strategic ties. The objective is not simply to pursue a large number of connections, but to obtain the right connections—ones that place the individual in a central network position. For example, seeking a junction that bridges between many pathways, and hence funnels much of the flow of information in the network.

Of course, such centrality in the network, while offering extremely valuable social capital, does not come for free. Friendship has a cost. It requires constant maintenance.

As a result, the research shows, social networks, whether on or offline, are a dynamic beehive of individuals constantly playing the cost-benefit game, severing connections on the one hand, and establishing new ones on the other. It’s a constant buzz driven by the ambition for social centrality. At the end, when this tug-of-war reaches an equilibrium, all individuals have secured their position in the network, a position that best balances between their drive for prominence and their limited budget for new friendships.

“When we did the math,” says Prof. Baruch Barzel, one of the paper’s lead authors, “we discovered an amazing result: this process always ends with social paths centered around the number six. This is quite surprising. We need to understand that each individual in the network acts independently, without any knowledge or intention about the network as a whole. But still, this self-driven game shapes the structure of the entire network. It leads to the small world phenomenon, and to the recurring pattern of six degrees,” adds Prof. Barzel.

The short paths characterizing social networks are not merely a curiosity. They are a defining feature of the network’s behaviour. Our ability to spread information, ideas and fads that sweep through society is deeply ingrained in the fact that it only requires a few hops to link between seemingly unrelated individuals.

Of course, not only do ideas spread through social connections. Viruses and other pathogens use them, as well. The grave consequences of this social connectedness were witnessed firsthand with the rapid spread of the COVID pandemic that demonstrated to us all the power of six degrees. Indeed, within six infection cycles, a virus can cross the globe.

“But on the upside,” adds Prof. Barzel, “this collaboration is a great example of how six degrees can play in our favour. How else would a team from six countries around the world come together? This is truly six degrees in action!”

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

Credit of the article given to Bar-Ilan University

Shuffling a pack of cards isn’t as easy as you think, not if you want to truly randomise the cards. Most people will give a pack a few shuffles with the overhand or riffle methods (where the pack is split and the two halves are interweaved). But research has shown this isn’t enough to produce a sufficiently random order to make sure the card game being played is completely fair and to prevent people cheating.

As I wrote in a recent article about card counting, not having an effective shuffling mechanism can be a serious problem for casinos:

Players have used shuffle tracking, where blocks of cards are tracked so that you have some idea when they will appear. If you are given the option to cut the pack, you try and cut the pack near where you think the block of cards you are tracking is so that you can bet accordingly. A variant on this is to track aces as, if you know when one is likely to appear, you have a distinct advantage over the casino.

So how can you make sure your cards are well and truly shuffled?

To work out how many ways there are of arranging a standard 52-card deck, we multiply 52 by all the numbers that come before it (52 x 51 x 50 … 3 x 2 x 1). This is referred to as “52 factorial” and is usually written as “52!” by mathematicians. The answer is so big it’s easier to write it using scientific notation as 8.0658175e+67, which means it’s a number beginning with 8, followed by 67 more digits.

To put this into some sort of context, if you dealt one million hands of cards every second, it would take you 20 sexdecillion, or 20,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000, years to deal the same number of hands as there are ways to arrange a deck of cards.

You would think that it would be easy to get a random order from that many permutations. In fact, every arrangement is, in a sense, random. Even one where the cards are ordered by suit and then rank could be considered random. It is only the interpretation we put on this order that would make most people not consider it random. This is the same as the idea that the lottery is less likely to throw up the numbers one to six, whereas in reality this combination is just as probable as any other.

In theory, you could shuffle a deck so that the cards emerged in number order (all the aces, followed by all the twos, followed by all the threes and so on), with each set of numbers in the same suit order (say spades, hearts, diamonds and clubs). Most people would not consider this random, but it is just as likely to appear as any other specific arrangement of cards (very unlikely). This is an extreme example but you could come up with an arrangement that would be seen as random when playing bridge because it offered the players no advantage, but wouldn’t be random for poker because it produced consistently strong hands.

But what would a casino consider random? Mathematicians have developed several ways of measuring how random something is. Variation distance and separation distance are two measures calculated by mathematical formulas. They have a value of 1 for a deck of cards in perfect order (sorted by numbers and suits) and lower values for more mixed arrangements. When the values are less than 0.5, the deck is considered randomly shuffled. More simply, if you can guess too many cards in a shuffled deck, then the deck is not well shuffled.

Persi Diaconis is a mathematician who has been studying card shuffling for over 25 years. Together with and Dave Bayer, he worked out that to produce a mathematically random pack, you need to use a riffle shuffle seven times if you’re using the variation distance measure, or 11 times using the separation distance. The overhand shuffle, by comparison, requires 10,000 shuffles to achieve randomness.

“The usual shuffling produces a card order that is far from random,” Diaconis has said. “Most people shuffle cards three or four times. Five times is considered excessive”.

But five is still lower than the number required for an effective shuffle. Even dealers in casinos rarely shuffle the required seven times. The situation is worse when more than one deck is used, as is the case in blackjack. If you are shuffling two decks, you should shuffle nine times and for six decks you need to shuffle twelve times.

Many casinos now use automatic shuffling machines. This not only speeds up the games but also means that shuffles can be more random, as the machines can shuffle for longer than the dealers. These shuffling machines also stop issues such as card counting and card tracking.

But even these machines are not enough. In another study, Diaconis and his colleagues were asked by a casino to look at a new design of a card shuffling machine that the casino had built. The researchers found that the machine was not sufficiently random, as they simply did not shuffle enough times. But using the machine twice would resolve the problem.

So next time you’re at a casino, take a look at how many times the dealers shuffle. The cards may not be as random as you think they are, which could be to your advantage.

For more insights like this, visit our website at www.international-maths-challenge.com.
Credit of the article given to Graham Kendall