Category: mathematics

Dedekind numbers describe the number of ways sets of logical operations can be combined, and are fiendishly difficult to calculate, with only eight known since 1991 – and now mathematicians have calculated the ninth in the series.

The ninth Dedekind number was calculated using the Noctua 2 supercomputer at Paderborn University in Germany

A 42-digit-long number that mathematicians have been hunting for decades, thanks to its sheer difficulty to calculate, has suddenly been found by two separate groups at the same time. This ninth Dedekind number, as it is known, may be the last in the sequence that is feasible to discover.

Dedekind numbers describe the number of ways a set of logical operations can be combined. For sets of just two or three elements, the total number is easy to calculate by hand, but for larger sets it rapidly becomes impossible because the number grows so quickly, at what is known as a double exponential speed.

“You’ve got two to the power two to the power n, as a very rough estimate of the complexity of this system,” says Patrick de Causmaecker at KU Leuven in Belgium. “If you want to find the Dedekind numbers, that is the kind of magnitude of counting that you will have to face.”

The challenge of calculating higher Dedekind numbers has attracted researchers in many disciplines, from pure mathematicians to computer scientists, over the years. “It’s an old, famous problem and, because it’s hard to crack, it’s interesting,” says Christian Jäkel at Dresden University of Technology in Germany.

In 1991, mathematician Doug Wiedemann found the eighth Dedekind number using 200 hours of number crunching on the Cray-2 supercomputer, one of the most powerful machines at the time. No one could do any better, until now.

After working on the problem on and off for six years, Jäkel published his calculation for the ninth Dedekind number in early April. Coincidently, Causmaecker and Lennart van Hirtum, also at KU Leuven, published their work three days later, having produced the same result. Both groups were unaware of one another. “I was shocked, I didn’t know about their work. I thought it would take at least 10 years or whatever to recompute it,” says Jäkel.

The resulting number is 286,386,577,668,298,411,128,469,151,667,598,498,812,366, which is 42 digits long.

Jäkel’s calculation took 28 days on eight graphical processing units (GPUs). To reduce the number of calculations required, he multiplied together elements from the much smaller fifth Dedekind number.

Causmaecker and van Hirtum instead used a processor called a field-programmable gate array (FPGA) for their work. Unlike a CPU or a GPU, these can perform many different kinds of interrelated calculations at the same time. “In an FPGA, everything is always happening all at once,” says van Hirtum. “You can compare it to a car assembly line.”

Like Jäkel, the team used elements from a smaller Dedekind number, in their case the sixth, but this still required 5.5 quadrillion operations and more than four months of computing time using the Noctua 2 supercomputer at Paderborn University, says van Hirtum.

People are divided on whether another Dedekind number will ever be found. “The tenth Dedekind number will be in the realm of 10 to the power of 82, which puts you at the number of atoms in the visible universe, so you can imagine you need something big in technical advancement that also grows exponentially,” says Jakel.

Van Hirtum also thinks the amount of computing power becomes impractical for the next number, requiring trillions more computations which would require capturing the power output of the entire sun. “This jump in complexity remains absolutely astronomical,” he says.

Causmaecker, however, is more positive, as he thinks new ways of calculating could bring that requirement down. “The combination of exponential growth of computing power, and the power of the mathematical algorithms, will go together and maybe in 20 or 30 years we can compute [Dedekind number] 10.”

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

*Credit for article given to Alex Wilkins*

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*

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*

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*

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*

See a vertical stripe, what you are seeing is a run of repeated digits, like 7777, 00000, or 222.

One occurs in the top left:

Sequences like this used to be important examples in motivating discussions about the law of the excluded middle. Statements like: ‘the decimal expansion of pi contains the sequence 7777’, according to the law of the excluded middle, are either true or false. But when you are discussing something that has never been calculated, and that might never be calculated, suggests (to constructivists), that the statement may be neither true or false, and that the sequence 7777 may be somewhat like Schrodinger’s cat, neither existing nor not existing.

Now that the digits of pi have been calculated to astounding lengths, and that mathematics exists to uncover the properties of the pi digit sequence, the expansion of pi is no longer an ideal candidate for constructivist thought experiments. Even some exotic questions about the decimal expansion of pi, like the convergence of the brouwer-heyting sequence, have been resolved. Questions about the expansion of pi that illustrate constructivist problems can still be formulated, but they need to be more complicated than they used to be.

Still, I decided to look more closely at this little sequence that occurs (relatively) early on in the pi expansion. The stripe in the pi colour map mentioned above corresponds to the sequence 999999 beginning at digit 763 and ending at digit 768. This was observed in a set of the first 2281 digits of pi.

I decided to push the software a bit further, and load 10000 digits of pi into the document.  (A file with the first 10000 digits of pi formatted for Fathom or TinkerPlots is here.) The plot below shows the digits with 9 in black and all other digits blanked out – dots are single occurrences of a 9, while vertical stripes are runs of repeated 9s.

Using Tinkerplots’ runLength function we can see how frequent runs of various lengths are, and easily identify the longer ones.

Even with 10000 digits, the 999999 sequence at digit 763 was still the longest sequence of repeated digits. The other runner-up sequences in this first 10000 digits are, two instances of 2222, a single run of 8888, and four distinct occurrences of 7777.

The plot at the bottom of this post shows the distribution of even and odd digits in the decimal expansion of pi’s first 10000 digits, and was inspired by a similar plot from Wolfram Math World.

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

*Credit for article given to dan.mackinnon*