Programs not programs

Richard Hamilton is the mathematician who laid out the route that eventually led to the positive solution to the three-dimensional Poincaré Conjecture by Grigori Perelman. He is the Davies Professor of Mathematics at Columbia University. While Perelman famously declined both the Fields Medal in 2006 and the official Clay Millennium Prize recognition in 2010, citing among other factors the lack of concomitant recognition for Hamilton, Hamilton was awarded the Leroy Steele prize in 2009, shared the Shaw Prize in 2011, and had earlier won the 2003 Clay Research Award alongside Terence Tao.

Today Ken and I wish to talk about programs in mathematics, not C++ programs, but programs of attack on a hard open problem. Ken likes the British form “programme” for this.

Hamilton’s brilliant program created a path, a very technical and difficult path, that Perelman was able to ascend. Without this path it is unclear whether the Poincaré Conjecture would have been solved so quickly into the new millennium. The proof of Fermat’s Last Theorem in 1994 also grew out of a far-reaching program named for Robert Langlands’ work and conjectures in the 1960s. The specific program on Fermat via elliptic curves was opened by Gerhard Frey in 1984, and electrified by Ken Ribet’s proof in 1986 of a conjecture that created new connections.

What Is A Program?

A program is not easy to define. I view it a bit like laying out a route for the ascent of a unclimbed mountain. The top of the mountain is the goal, is the solution of the open problem. From the ground the top looks scary, far away, and may seem an impossible climb. Many professional and amateur mathematicians may have tried already to climb to the top, only to fail: some stopped short and returned unhurt, while others fell.

Thus a program in this sense is a potential route to the top of our mountain. From the ground it takes great vision, great insight, and much more, to be able to “see” that a certain route may indeed yield the top of the mountain. Most of us would probably just start climbing and quickly hit a part of the mountain that is an impasse. We get stuck. It looks like this:

source—“Mount Everest Made Easy”

But Hamilton was an example of those with vision to see a plausible route to the top—-in his case to the solution of the Poincaré Conjecture. Of course, he had partial evidence that his route, his program, made some sense. It was different from previously-tried routes that all had failed. He also could use his route to get at least partial results. Following his route he proved special cases of the Poincaré, which in our metaphor is like reaching a height further up toward the peak of the mountain than anyone else had ever done.

Perhaps the simplest definition of a program is that it is something other than a “program”—at least the type of program we wrote when learning Algol or Pascal or C. Those programs were single procedures to solve an already-determined problem. A program gives a way to “mount” the mountain for analysis, as distinct from the act of solving the problem. We have recently contrasted “object-oriented” programs from procedural ones in this context.

What distinguishes a program is developing a new ingredient and/or approach. This can be a new object, a connection, an expanded battlefield, or a theme developed from more-fundamental scientific principles. A program can have all or some of these—the more, the better.

I hope this helps explain a bit what a program is in this context. let’s turn to look at a few programs. Some have already been successful, others are still pending.

Some Programs

First we look again at the examples introduced above.

Hamilton: Ricci flow—a new object. This idea applies to Riemannian manifolds quite generally, not just the ones used by Perelman.

Langlands: An expanded theatre—as with “programme” Ken likes the British spelling in this context. The first National Academy of Sciences Award in Mathematics recognized his

“extraordinary vision that has brought the theory of group representations into a revolutionary new relationship with the theory of automorphic forms and number theory.”

Of course an expanded theatre brings new connections, but those are often for others to find.

Frey: A new connection via elliptic curves. Sometimes the best way to prove a theorem is to see what you get if it’s false. Consider the elliptic curve

whose right-hand side is a cubic polynomial with distinct roots . The discriminant of a polynomial is the product of the squared pairwise differences of its roots. Here if , we get for the discriminant:

Thus an integer solution to Fermat’s equation with would create an elliptic curve with the special property that its discriminant is a sixth or higher power of an integer. If is a prime—the only cases needed to prove Fermat—then existing tools in the theory of elliptic curves hinted that the curve would acquire more properties that are “too special”—they self-contradict. For Andrew Wiles to complete the proof, with assistance from Richard Taylor, however required transferring the final problems to another part of Langlands’ theatre, involving Galois representations and class numbers. The curves in this case had actually been found by Yves Hellegouarch, but Frey developed the properties.

Ribet: A new connection, via a new result. When Ribet proved the so-called epsilon conjecture, it completed a path of implication from a conjecture named variously for Goro Shimura, Yutaka Taniyama, and André Weil, clear through to Fermat’s Last Theorem. Wiles did not prove the whole latter conjecture, but enough of it to deduce Fermat. Taylor was part of a team that completed the whole of the work in 2001: the conjecture is now a theorem.

Some Programs in Computational Complexity

In computational complexity we have our own Everest: resolving the question. But in a sense we haven’t even gotten over the foothills: no one has proved any truly general and meaningful super-linear lower bounds: none on circuit size, nor above the slightest super-linear functions on Turing machine running time. However, it is possible that this landscape is fractal: the whole range may have the same obstacles regardless of height, and scaling one hill may be as hard as opening the path to the top.

There are many programs in our field that we could mention, but we’ll stay with four of the ones that are directed squarely at the peak:

Mike Sipser: Circuit Lower Bounds. I (Ken) like to state the theme as, “Machines have moving parts; circuits don’t.” That is, a circuit is a fixed combinatorial structure, without the dynamic head movements and memory-access patterns of a Turing machine or RAM program. Thus a circuit is a fixed target for lower-bound arguments. One can also easily differentiate the structure of circuits according to depth, fan-in, width, and various connectivity notions.

The “Sipser Program” began auspiciously with strong lower bounds against polynomial-size circuits of constant depth, even allowing unbounded fan-in gates that count modulo some fixed prime number. However, at the level of threshold gates or logarithmic depth it encountered a barrier, one erected almost 20 years ago by Alexander Razborov and Stephen Rudich. The barrier may require cliff-scaling or finding a new base camp, or maybe the premise on which it was erected (the exponential security of pseudorandom generators, including ones based on factoring) isn’t true and we can plow ahead with the program after all.

Despite the stopping of progress, I feel it is wrong to say the program bogged down—rather, it was rocked by several other programs we could equally well highlight: one-way functions (and) pseudorandom generators, hardness versus randomness, even algebraic methods in complexity. This kind of clash is good: programs should impact each other.

Ryan Williams: New ideas for circuit lower bounds: This is a plow-ahead movement, armed with the theme of looking for new upper bounds and expanding the kinds of problems considered—as we tried to style it here. Just this week, he has tackled the relation of his ideas to natural proofs, and has improved his lower bounds.

Ketan Mulmuley: His program of Geometric Complexity Theory expands the theatre in the direction of Langlands, employing group representation theory and deep concepts of algebra. Here is his overview last summer for Communications of the ACM. While the attack is most squarely on Leslie Valiant’s algebraic analogue of , which embraces permanent versus determinant, the effects may be tantamount. In his FOCS 2012 paper, he has linked complexity questions to Emmy Noether’s century-old Normalization Lemma.

Michael Freedman: Knot theory and topology. Freedman won a Fields Medal in 1986 for his work on the 4-dimensional case of the Poincaré Conjecture. He has since worked at the juncture of enumerative combinatorics, knot theory, and topology. Problems in these fields are often naturally complete for or –cum–. This 2008 paper shows a special knot-theoretic consequence of being properly contained in . His program has yielded results on quantum computing, including a proposal for a topological quantum computer, which also relates to versus .

Open Problems

While reaching the top of the mountain—solving the open problem—is the most fun, laying out potential programs is of critical importance. I (Dick) think that we need more of the latter in complexity theory. We lack, in my opinion, visionaries who can lay out programs that may succeed. I hope we get more of them in the future.

Atle Selberg once said:

There have probably been very few attempts at proving the Riemann hypothesis, because simply no one has ever had any really good idea for how to go about it!