120th Anniversary of Hilbert's Problems

The computational software algorithms used in EDA are fundamentally mathematical in nature. Many algorithms are various forms of computation using very large sparse matrices. Last Saturday was a significant anniversary in the foundations of mathematics.

One hundred and twenty years ago last Saturday, August 8, 1900, the German mathematician David Hilbert gave a presentation at the Sorbonne in Paris. He listed twenty-three problems in mathematics, all unsolved at the time, that would turn out to be very influential and set the agenda for much of mathematics for the early part of the twentieth century. Some were solved in the way expected by Hilbert. Some were solved, but not at all in the way that Hilbert expected, most notably Gödel's proof that mathematics could not be proved to be both consistent and complete. Some were proven unprovable. And some remain notoriously unsolved, such as the Riemann Hypothesis. Many of the problems were not actually stated precisely enough to make it clear whether subsequent work solved the problem or not. But some were resolved only in the 1970s.

Hilbert numbered the problems, so often they are known by titles like "Hlbert's 10th problem" or just "the 10th problem" if the context is obvious. There were actually 24 problems, but Hilbert dropped the 24th and it was only discovered in his original manuscript in 2000. Also, in 2000, the Clay Mathematics Institute did something similar to Hilbert's 23 problems.

Here are the first three problems, which are fairly approachable (the problems, not the solutions!):

1. Continuum hypothesis. There is no set with cardinality between the integers and the real numbers (surprisingly the rationals have the same cardinality as the integers, so that doesn't get you a solution). Proven impossible to prove or disprove in the normal formalization of mathematics using set theory. Unclear whether this counts as a solution.
2. Prove the axioms of arithmetic are consistent. Gödel's 1931 Incompleteness Theory shows that this cannot be done within the axioms of arithmetic itself.
3. Given two polyhedra of equal volume, is it always possible to cut up one and reassemble the pieces to make the second. No, you can't. Proved in 1900.

Millennium Prize Problems

In 2000, on May 24, the Clay Mathematics Institute proposed seven problems in mathematics and offered a million-dollar prize for solving any of them. One has been solved but the solver declined the money.

The most relevant for computer science and EDA is the P=NP problem which I wrote about in some level of detail in my post What Does P≠NP Mean?

The other six problems are:

• The Poincaré Conjecture. A problem in topology solved by reclusive mathematician Grigori Perelman who declined the million-dollar prize money, and the Fields medal.
• The Birch and Swinnerton-Dyer Conjecture. Swinnerton-Dyer gets a walk-on part in the Cambridge Computer Laboratory where I studied once I became a computer scientist instead of a mathematician in my third year. Swinnerton-Dyer did a lot of work on the Titan operating system at the Cambridge Computer Laboratory, that I actually used before it was finally turned off in 1973.
• The Hodge Conjecture. A problem in topology I don't really understand.
• Navier-Stokes Existence and Smoothness. Fluid dynamics...my least favorite subject in undergraduate mathematics. But you need to solve turbulence, one of the great unsolved problems in physics/mathematics without any basic understanding even today.
• The Riemann Hypothesis. This is fundamental to a lot of other theorems to do with prime numbers, but the actual hypothesis is pretty opaque (all the non-trivial zeros of the Zeta function have real part ½). Almost all modern mathematics in number theory starts by assuming the Riemann Hypothesis is true and it would be almost unbelievable if it was disproved. This was also Hilbert's eighth problem.
• Yang-Mills Existence and Mass Gap. I don't understand this one. It is related to quantum gauge theory, and quantum mechanics was my second least favorite subject in undergraduate mathematics. I think that the problem is to reconcile some of quantum mechanics with relativity, which today don't match up and so we know our understanding of physics is incomplete

Learn More

There is a huge amount of literature about all these problems, both Hilbert's 23 problems and the Millennium Prize Problems. The Wikipedia page Hilbert's Problems is a good starting point if you want to dig deep. Of course, there's a Wikipedia page for the Millennium Prize Problems too.

If you are especially interested in the second Hilbert problem on the consistency of arithmetic, I strongly recommend computer scientist Douglas Hofstadter's tour de force 1979 book Godel, Escher, Bach (still in print).

Sign up for Sunday Brunch, the weekly Breakfast Bytes email.