Quantum computers, Conway knots, and AI for the Mathematical Olympiad: these are the major breakthroughs in computers and mathematics in 2020

Latest update time：2021-01-02

Reads：

Lei Shishi from Aofei Temple
Quantum Bit Report | Public Account QbitAI

The relationship between mathematics and computers has always been that you are in me and I am in you .

Computer programs are inseparable from mathematics, and they also bring convenience to mathematical calculations.

Quanta Magazine, a well-known foreign science website, took stock of several major breakthroughs in the two disciplines of computer science and mathematics in 2020.

There are puzzles that have troubled mathematicians for more than 50 years , and there are also AI and mathematics combined.

Of course, the two mathematicians who solved the century-old math problem that Terence Tao failed to solve during the quarantine period are also on the list.

Lets come look.

TOP1: Major breakthrough in “quantum entanglement”

This year, the most important breakthrough in the computer field is the proof that MIP*=RE.

Its proof means that quantum computers that use quantum logic to calculate (rather than classical computers that use 0s and 1s to calculate) can theoretically verify the answers to a large number of problems.

Five computer scientists from the University of Technology Sydney, California Institute of Technology, University of Texas at Austin, and University of Toronto jointly published their research results in a paper called " MIP * = RE ".

This paper proves that the class of languages MIP determined by the interaction of classical verification with multiple quantum theory verifications is equivalent to the class of recursively enumerable languages RE.

In other words, MIP*=RE multi-party interactive proof, combined with the computing power of quantum entanglement, provides a solution to the Turing halt problem.

As for the conclusion of this paper, physicists saw the answer to Tsirelson's physics problem in it, and mathematicians got the answer to Connes' embedding conjecture in it.

Henry Yuen, one of the authors, said: "Just like the blind men and the elephant , people in different scientific fields have seen different parts, and although they are all correct, they have not figured out the original appearance of the elephant."

In the 1980s, computer scientists invented the theory of interactive proofs and probabilistic verifiable proofs (PCP) . MIP* = RE is the classic PCP theorem, which can be recursively extended to infinity with the help of quantum entanglement.

The paper concludes that two machines can be entangled and mutually verified to solve the Turing halt problem. At the same time, it also proves that the Connes embedding conjecture is wrong.

They also cited the classic two-game mutual verification game Bell/CHSH, where the endless entanglement verification between the two would increase the winning rate of the game. So the final question is how to stop the entanglement verification process.

In addition, the first author of this paper is Professor Zhengfeng Ji from the Center for Quantum Software and Information at the University of Technology Sydney.

Ji Zhengfeng received his Ph.D. in Computer Science and Technology from Tsinghua University in 2007.

Paper address:
https://arxiv.org/abs/2001.04383

TOP2: Solving the Conway Twist

In June this year, the famous British mathematician John Conway died of COVID-19, leaving behind a difficult problem called the "Conway Knot" that has plagued the mathematics community for 50 years .

A month after his death, Lisa Piccirillo, a PhD student at the University of Texas at Austin, spent a week solving the problem.

Over the years, mathematicians have discovered a variety of knots that are topologically cuttable but not smoothly cuttable. However, all of these knots have more than 12 crossovers.

Among the knots with less than 12 crossing points, only the slice state of the Conway knot has never been found.

Why is it so important that the Conway Knot is smooth and cuttable?

Because smooth, cuttable knots provide mathematicians with a way to explore the strange properties of four-dimensional space .

Therefore, whether the Conway knot is smooth and cuttable has become a rigid standard for major breakthroughs in knot theory.

Lisa thought that if she could create a knot with the same trace for the Conway twist, then maybe it could work better with the shear invariance.

So she managed to construct a complex knot whose trace was the same as the Conway knot. Lisa used a tool called Rasmussen's s-invariant.

The results showed that the knot she constructed was not smoothly cuttable, so it was inferred that the Conway knot was not smoothly cuttable either.

"This is a very beautiful proof," mathematicians exclaimed.

TOP3: AI participating in IMO

Mathematics has a history of thousands of years of development, but human memory is limited. Even first-class mathematicians cannot remember all mathematical formulas and theorems.

As a result, many mathematical scientists turned to " digitalization of mathematics " and built a digital library of mathematical achievements accumulated over thousands of years.

Using a Microsoft software program called Lean, mathematicians built a basic math database called Mathlib , which contains all the knowledge a sophomore math major should learn.

They compile mathematical knowledge into computer language and solve difficult mathematical problems based on a huge library of mathematical formulas and theorems.

Lean's problem-solving method is the same as the algorithm of chess and Go AI, which follows the decision tree until the algorithm finds the optimal solution.

Currently, Lean is planning to participate in the next IMO (International Mathematical Olympiad). The result of the competition is still unknown, and many people are pessimistic about the outcome.

However, there are some particularly successful cases of AI solving complex math problems.

Several computer researchers from Stanford University, Carnegie Mellon University, and Rochester Institute of Technology used AI to solve the Keller conjecture, which had troubled mathematicians for 90 years , using only 40 computers and 30 minutes .

So, what new breakthroughs have there been in mathematics and computing this year?

Progress in Geometry

Inscribed square problem

During the epidemic, two scientists, Andrew Lobb and Joshua Greene, who were confined at home, felt bored.

So they moved their fingers and solved a math problem that has puzzled people for a century. Even Terence Tao failed to challenge this difficult math problem.

The question is: For any simple closed loop, can we always find four points on it to form a rectangle with any aspect ratio?

This problem is also called the inscribed square problem , which originated in 1911. German mathematician Otto Toeplitz predicted that any simple closed curve contains four points that can be connected to form a square.

This sentence sounds simple, but from ancient times to the present, many mathematicians have racked their brains to prove it but have not been able to do so.

In 1977, mathematician Herbert Vaughan made a breakthrough by using the Möbius strip to solve the inscribed rectangle problem.

He proved that in any closed loop in three-dimensional space, there are at least four points that can form a rectangle.

The genius mathematician Terence Tao used the integration method to solve the inscribed square problem under specific circumstances.

He used the method of integration to prove that in the special case where the curve consists of two Lipschitz figures with constants less than 1, there must be four points on the curve that can form a square.

But neither of them has proved whether rectangles with arbitrary length-to-width ratios (including squares) can exist.

In their approach, Andrew Lobb and Joshua Greene embedded the Möbius strip in four-dimensional symplectic space and proved that the Möbius strip can be embedded in four-dimensional symplectic space without intersecting.

This means that every closed smooth curve must contain a set of four points that can be connected together to form rectangles of all aspect ratios.

Further reading: https://mp.weixin.qq.com/s/E-I_3C-3m0KTI1XjYaKWcA

New discovery of the dodecahedron

Mathematicians have spent more than 2,000 years studying the tetrahedron, hexahedron, octahedron, dodecahedra, and icosahedron, special shapes also known as the Platonic solids, and for many years, they still knew very little about them.

There has always been a thought about the Platonic solids. Suppose you start from a corner of a Platonic solid, is there a straight line path that can return to the original corner without passing through other corners?

For tetrahedrons, cubes, octahedrons, and icosahedrons composed of equilateral triangles or squares, scientists have come to the specific conclusion that they do not exist . You must go through other corners, otherwise you will never get back to the starting point.

However, the regular dodecahedron is composed of pentagons. Does it also conform to this theorem?

Jayadev Athreya, David Aulicino and Patrick Hooper published their research on the dodecahedron in the journal Experimental Mathematics.

They believe that since the regular dodecahedron is composed of pentagons and pentagons and the regular dodecahedron are geometrically related, the high symmetry of the former can be used to explain the structure of the latter.

The researchers were therefore able to identify all the straight-line paths that the dodecahedron could take back to its starting point and to classify these paths according to the dodecahedron's hidden symmetries.

There are countless such straight paths of the regular dodecahedron , which can be divided into 31 natural families.

Paper address:
https://www.tandfonline.com/doi/abs/10.1080/10586458.2020.1712564

Sublimation of mathematical thinking

Upgrading the Langlands Mathematics Bridge

In the 17th century, French mathematician Fermat proposed "Fermat's Last Theorem", which states that when the integer n>2, the equation x2 ⁺ y2 ⁼ z2 ^about x, y, and z has no positive integer solutions.

In 1995, it was proved by British mathematician Andrew Wiles, more than 300 years later.

Wells also proposed the concept of a mathematical bridge . This means that this equation is a bridge between two mathematical fields. If you connect this bridge, you can solve the infinitive.

However, this is only a small part of the Langlands Project. The Langlands Project was proposed by Canadian mathematician Robert Langlands to study the network conjecture between number theory and geometry , and is considered the largest project in modern mathematical research.

△ Canadian mathematician Robert Langlands

Mathematicians have extended this approach to the connection between rational coefficients and elliptic curves, and more recently, to simple irrational coefficients. But their approach breaks down when it comes to imaginary numbers, or higher exponents, like 4 or 5.

Therefore, in order to overcome the above obstacles, Frank Calegari of the University of Chicago and David Geraghty, a scientist at Facebook, published a paper online on how to build a more general infinitive bridge and put forward three conjectures.

In order to verify the three conjectures, mathematicians quickly held a secret seminar and compiled them into a paper signed by 10 people.

Although the research results of this paper have made a huge breakthrough in the Langlands project in the field of mathematics, there is still no solution for infinitives with exponents greater than 6 or more than 2 variables.

Therefore, there is still room for expansion of the Langlands project .

Mathematical paper address:
https://arxiv.org/abs/1812.09999

Polynomials and Power Series

The repulsive force in physics also exists in mathematics.

Vesselin Dimitrov of the University of Toronto proved their existence and obtained experimental results.

In general, a polynomial has as many roots as its degree. So X ² - 4 has two roots, and X ⁵ - 7 X ³ + 2 X ² - 4 X - 9 has five roots.

Mathematicians are curious about the relationship between the roots of polynomials.

A cyclotomic polynomial is introduced here. The so-called cyclotomic polynomial is an irreducible polynomial. Mathematicians have discovered that its roots follow a specific geometric method and are distributed within a circle, so it is named the " Root of Unity ".

But in practice, most are non-cyclotomic polynomials.

Mathematicians predict that every non-cyclotomic polynomial must have a root outside the circle.

They speculated that this was due to " repulsion ", just like electrons in physics, their smallest roots fell inside the circle and had a repulsive force like a magnet, repelling other roots outside the circle.

But for a long time, mathematicians were unable to prove this theory.

Dimitrov did this by converting the problem of the size of the roots of a polynomial into a power series. A power series, like a polynomial, has infinite solutions.

He started with a non-cyclotomic polynomial, found its roots, raised them to different powers, multiplied them, and then took the square root of the product. Finally, based on this square root, he constructed a power series with the essential properties of a polynomial.

Dimitrov proved that the coefficients of a power series must be integers, and if its Hankel determinants are also large, then an initial root of the non-cyclotomic polynomial must also be large. Thus, the connection between the roots of a polynomial and the power series is proved.

Other mathematicians commented: "His method is very elegant and indirectly proves the conjecture about repulsion."

Reference link:
https://www.quantamagazine.org/new-math-measures-the-repulsive-force-within-polynomials-20200514/

The Duffin-Schaeffer conjecture was proved

James Maynard, a young mathematician from Oxford University, solved the Duffin-Schaeffer conjecture, a difficult mathematical problem that has troubled everyone for 80 years .

The Duffin-Shaeffer conjecture is an important conjecture in metric Diophantine approximation, proposed by physicist Richard Duffin and mathematician Albert Schaeffer in 1941.

As we all know, most real numbers are irrational numbers such as π and √2, which cannot be expressed by fractions.

This conjecture assumes that f:N→R≥0 is a real-valued function with positive values, and it holds true only if the series:

It is divergent (q>0, φ(q) is the Euler function, which represents the number of positive integers smaller than q and coprime to q) . For the irrational number α, there are infinite rational numbers that satisfy the inequality | α-(p/q) |< f(q)/q.

This proof had puzzled mathematicians for years, until James Maynard and Dimitris Koukoulopoulos of the University of Montreal cracked it.

In their proof, they create a graph using denominators : they plot the denominators as points on the graph, and connect two points with a line if they have many prime factors in common.

In this way, the structure of the graph encodes the overlap between the irrational numbers approximated by each denominator, an overlap that is difficult to measure directly.

In this way, they proved the correctness of the Duffin-Schaeffer conjecture .

The above are some of the most important research advances in the field of computer science and mathematics this year, selected by Quanta Magazine.

Which of these studies do you think has more academic value?

Or in other words, are there any other major research breakthroughs that are not on the list but are also major research breakthroughs this year?

Major breakthroughs in computer science and mathematics in 2020:
https://www.quantamagazine.org/quantas-year-in-math-and-computer-science-2020-20201223/