An artificial intelligence has disproved five mathematical conjectures 鈥� unproven theorems 鈥� despite not being equipped with any information about the problems.
at Tel Aviv University in Israel used an AI approach to search for examples that would disprove a range of long-standing conjectures in graph theory, an area of mathematics that involves studying objects made of nodes and links. Mathematicians thought these conjectures were true, but hadn鈥檛 been able to prove them.
Advertisement
For each conjecture, Wagner created a measure of how close an example was to disproving it. For instance, if a conjecture proposed that a certain problem couldn鈥檛 be solved in fewer than five steps, an example with six steps would be closer to a disproof than one with seven, and a solution with four steps would serve as a counterexample to the conjecture.
Wagner programmed a neural network to create random examples and use these measures to assess their suitability as a counterexample. The AI discarded the worst scoring ones and then replaced them with more random examples before starting again. In dozens of cases the AI was unable to find an example that disproved the theory, but in five cases it landed on a solution which showed that the conjecture must be false.
鈥淲e just discard the bad ones and learn from the best examples every iteration,鈥� says Wagner. 鈥淚t鈥檚 basically the simplest possible thing you can do, the architecture. There is nothing fancy going on.鈥�
Wagner ran the AI on his 5-year-old laptop, which took anything from a couple of hours to a couple of days to disprove each of the five conjectures. The results were often counterintuitive, he says. 鈥淚 would never have come up with these constructions by myself even if you gave me hundreds of years.鈥�
鈥淚t鈥檚 completely impressive,鈥� says at Iowa State University, who had one of her conjectures disproved by the AI. 鈥淲hat we鈥檙e seeing here is a huge benefit of artificial intelligence with no downside, from a mathematical perspective. It鈥檚 simply finding stuff for us, the way someone with great insight could. The counterexamples are needles in haystacks.鈥�
While the AI has succeeded in disproving conjectures, proving them is much harder. To disprove an idea requires creating and testing a vast amount of potential solutions to see if any contradict the conjecture, a mechanistic task that can be automated, but a proof is a creative work that requires insightful leaps and involves stringing together many logical steps.
The first theorem to be proved with the help of a computer was the four colour theorem, which states that any map can be coloured using only four colours so that there are no two countries touching of the same colour. The proof, found in 1976, involved using a computer to check an exhaustive list of examples and was considered inelegant by some at the time, but the use of computers to solve mathematical problems has since become much more prevalent.
Still, Hogben says it is important that human mathematicians should always be able to follow a proof. 鈥淚 personally would never have a problem with a disproof that can be verified. A computer proof that is not verifiable by hand, I would personally have some concerns about. To me that breaks the gold standard of mathematics.鈥�
at the Coll猫ge de France in Paris said that the approach was an interesting proof of concept. 鈥淚t鈥檚 hard to imagine that this is the end of the story. Maybe it can be worked into a simple 鈥榗heck your conjectures鈥� tool that would be of great help to mathematical researchers,鈥� he said.
Reference:
