A Fleet of Computers Helps Settle a 90-Year-Old Math Problem:
A team of mathematicians has finally finished off Keller's conjecture, but not by working it out themselves. Instead, they taught a fleet of computers to do it for them.
Keller's conjecture, posed 90 years ago by Ott-Heinrich Keller, is a problem about covering spaces with identical tiles. It asserts that if you cover a two-dimensional space with two-dimensional square tiles, at least two of the tiles must share an edge. It makes the same prediction for spaces of every dimension—that in covering, say, 12-dimensional space using 12-dimensional "square" tiles, you will end up with at least two tiles that abut each other exactly.
Over the years, mathematicians have chipped away at the conjecture, proving it true for some dimensions and false for others. As of this past fall, the question remained unresolved only for seven-dimensional space.
But a new computer-generated proof has finally resolved the problem. The proof, posted online last October, is the latest example of how human ingenuity, combined with raw computing power, can answer some of the most vexing problems in mathematics.
The authors of the new work—Joshua Brakensiek of Stanford University, Marijn Heule and John Mackey of Carnegie Mellon University, and David Narváez of the Rochester Institute of Technology—solved the problem using 40 computers. After a mere 30 minutes, the machines produced a one-word answer: Yes, the conjecture is true in seven dimensions. And we don't have to take their conclusion on faith.
The answer comes packaged with a long proof explaining why it's right. The argument is too sprawling to be understood by human beings, but it can be verified by a separate computer program as correct.
In other words, even if we don't know what the computers did to solve Keller's conjecture, we can assure ourselves they did it correctly.
(Score: 1, Interesting) by Anonymous Coward on Monday August 24 2020, @01:55PM (1 child)
Whenever I've seen a proof like this fail, it's been in the initial reduction of the hypothesis to the simplified problem space that they verify by brute force.
The strong form of this proof is
In cases like this B is proven by iterating over all of the possible cases of B. The weak link is the "if and only if" part. If that's not completely correct then the computation doesn't matter one iota.
(Score: 0) by Anonymous Coward on Monday August 24 2020, @08:04PM
So what you're saying is: Sometimes we find mistakes in the part that a human can follow and check for mistakes.
But whatever mistakes may or may not be lurking in the opaque, machines-only parts, us humans haven't found them yet.
And no, I'm not suggesting our computers are engaged in a conspiracy of lies; that would be silly. But you have to wonder about aliens with precision cosmic-ray tech flipping bits to stymie our mathematical progress and keep us from developing the warp drive.