Math Is Like The Stock Market
It goes up, it goes down, it does not grow monotonically
Louis de Branges is an analyst, not a stock trader, but an expert in the theory of real and complex valued functions. He is best known for his proof of a long-standing open problem from complex analysis.
Today Ken and I want to talk not about any recent proof claim, but about the nature of them in general.
The growth of mathematical knowledge is not monotone. Sometimes mathematicians make errors and they are unfixable; sometimes they make errors and they are fixable; sometimes they make errors and they lead to whole new vistas. The growth and accumulation of knowledge is complex and chaotic—this has been the case in the past, and continues to be the case today. I cannot imagine it will not continue to be the case in the future.
One of the reasons for creating GLL is to examine and expose the human side of mathematics. It is done by people, by people who make errors, by people who discover errors, by people who fix errors, and by people who try their best to advance the field. I hope that GLL and other forums are places where we can discuss ideas in a positive manner. I do not think that attacks on researchers are appropriate, nor that they advance the free exchange of ideas.
I have already written a number of times on this very issue, but perhaps I can give a few more examples to make the point again. I love mathematics, I love to see new results, new insights, new attempts to solve hard problems. I hope you do too.
I think that failure must be an option—with apologizes to Gene Kranz—if the field is to continue to grow and be as exciting as it has for thousands of years. As an aside, Kranz apparently never actually said the exact words “Failure is not an option.” Recall Kranz was the mission leader in Houston for Apollo 13, which was the moon mission that had an explosion and almost lost the three astronauts that were aboard. One of the flight controllers who worked with Kranz on Apollo 13 was once asked:
“Weren’t there times when everybody, or at least a few people, just panicked?” His answer was “No, when bad things happened, we just calmly laid out all the options, and failure was not one of them.
Ken remembers his father telling him of IBM or AT&T having a program colloquially called the “Terrible Twenty”: they would fund 20 researchers freely with the attitude that if just one hit a breakthrough they would break even, and if two did, or three others at least produced workable products, they would show a nice profit. The 16 or 18 or 19 who failed were a necessary part of this equation, for if the company knew in advance what would hit big, they wouldn’t need the program. We cannot trace the name “terrible twenty” on Google, but it shows those researchers were paid great respect.
Even Carl Gauss could make claims that were only partial proofs. The fundamental theorem of algebra is:
Theorem: Any non-trivial polynomial over the complex numbers has at least one root.
Gauss is usually credited with the first correct proof in his 1799 dissertation: “New Proof of the Theorem That Every Algebraic Rational Integral Function in One Variable Can be Resolved into Real Factors of the First or the Second Degree.” While his claimed proof was much closer to a rigorous one, it assumed some properties of curves that were not proved by him.
Augustin-Louis Cauchy made a number of “errors.” He seemed to confuse various types of continuity and made other similar claims that were not correct. This should take nothing away from his sweeping impact on mathematics, but is a reminder for us how knowledge is created in mathematics. One interesting claim that he made is featured recently in a lovely article by Marek Jarnicki and Peter Pflug: “Directional Regularity vs. Joint Regularity”.
Cauchy claimed, in his 1821 book Cours d’analse, that if is continuous in each variable, then it is continuous in both. That is if and are continuous for any fixed and , then is continuous as a function of two variables. This is false. As Jarnicki and Pflug say, “every student nowadays knows this statement is not correct.” It took almost fifty years for the discovery of counterexamples.
The best example, perhaps, is due to Giuseppe Peano:
The famous Bieberbach Conjecture was solved by de Branges in 1984. The class consists of the functions
that are regular and one-to-one inside the unit disk, . Ludwig Bieberbach conjectured in 1916 that
for these functions. The conjecture was striking: the global property of one-to-one somehow controlled the size of all the coefficients of the functions.
It took over 70 years for de Branges to solve the full conjecture. Previously, the conjecture was proved for small values of : the values proved in order were,
Note, this is not a typo: the value came only in 1972, even though was proved in 1969. Even results for one value of often had quite long and difficult proofs, and it must have seemed highly unlikely that a uniform proof was near that would do all values of at once. If de Branges have proved the conjecture for all , that would probably would have been a major achievement. But he proved all at once.
His proof was initially rejected by the mathematical community. Few mathematicians—none?—would even look at his claimed proof, which initially was long and actually part of a whole book he was writing—385 pages. Though he was a professional mathematician, a full professor at Purdue, he had claimed proofs before of famous conjectures, and all previous ones had turned out to be wrong. His track record was not promising.
He eventually visited the Steklov Institute of Mathematics in Leningrad for an extended period of time. There was a seminar there that began to look at his manuscript and the proof in detail. The expected outcome was a fatal error. They expected to discover the proof was useless, uncorrectable.
Wrong. Gradually it started to be clear that while there were mistakes, many claims were essentially correct. Often it was easy to substitute a correct argument for de Branges’ original one. Over time, however, the “fog” began to lift and the experts at Steklov began to see that de Branges ideas could be made into a valid proof. The Bieberbach Conjecture was true: de Branges had succeeded where all before him had failed. An immense achievement.
There is a beautiful article that details the “Last 100 days of the Bieberbach Conjecture.”
Since de Branges great achievement he has continue to work and claim proofs of some of other great open problems. For example, for a time he claimed a proof of the Riemann Hypothesis, which was based on a novel approach through the theory of spaces of entire functions. The proof is wrong, but some interesting mathematics did come out of this failed attempt: There is now a class of special entire functions called de Brange functions and there is some continuing work looking into their properties.
Andrew Wiles’ fix (with help from Richard Taylor) to his proof of Fermat’s Last Theorem is a case of an earlier failed proof attempt actually proving vital. As he described it on the 1997 NOVA special “The Proof” (scroll down):
In September , I decided to go back and look one more time at the original structure of Flach and Kolyvagin to try and pinpoint exactly why it wasn’t working, try and formulate it precisely. One can never really do that in mathematics, but I just wanted to set my mind to rest that it really couldn’t be made to work. And I was sitting here at this desk. It was a Monday morning, September 19, and I was trying, convincing myself that it didn’t work, just seeing exactly what the problem was, when suddenly, totally unexpectedly, I had this incredible revelation. I realized what was holding me up was exactly what would resolve the problem I had had in my Iwasawa theory attempt three years earlier, was—It was the most—the most important moment of my working life. It was so indescribably beautiful; it was so simple and so elegant, and I just stared in disbelief for twenty minutes.
Then, during the day, I walked around the department. I’d keep coming back to my desk and looking to see if it was still there. It was still there. Almost what seemed to be stopping the method of Flach and Kolyvagin was exactly what would make horizontal Iwasawa theory [succeed]. My original approach to the problem from three years before would make exactly that work. So, out of the ashes seemed to rise the true answer to the problem. So, the first night, I went back and slept on it. I checked through it again the next morning, and by eleven o’clock, I was satisfied and I went down and told my wife, “I’ve got it. I think I’ve got it. I’ve found it.” And it was so unexpected, I think she thought I was talking about a children’s toy or something and said, “Got what?” And I said, “I’ve fixed my proof. I’ve got it.”
The area of cryptography is filled with many claims and errors. However, some of the mistakes have led to great new ideas. I believe that one of the issues in this area is how unintuitive the area is. Many of the simple rules that apply elsewhere in the design of algorithms fail completely when designing crypto protocols.
A simple example is the use of known algorithms as subroutines. In the design of data structures or algorithms, there is no problem with using another algorithm as a black box, one that can be used over and over. This fails completely in the crypto area: a major source of research is when and how to use known protocols to build new ones. This is still an active research direction.
Perhaps because the basic computational model is non-interactive and well understood, there have been fewer subtle errors in computational complexity. Rather than enumerate them, we’ll focus on one we think is important, involving probabilistic and oracle machines which are less well understood—the we is Ken and I.
Does have a time hierarchy? Same question for the quantum analogue, .
What we really mean is that we can define and for reasonable time functions . Then given a condition for to be significantly but not terribly less than , such as which yields the Deterministic Time Hierarchy Theorem for Turing machines, can we show:
Lance Fortnow and Mike Sipser thought they had given surprising negative evidence by constructing an oracle relative to which would equal , i.e., bounded-error probabilistic linear time. Between polynomial and linear there would be no hierarchy provable with standard “relativizable” techniques. However, problems in their argument led to a retraction—even with truth-table use of the oracle there were “subtle problems in the way we combine machines.” Note this is like the issue with cryptography and algorithms above.
I, Dick, thought about this problem a while ago, and thought I had a proof that there was a hierarchy. After sleeping on it, I discovered the fatal flaw; some problems are very slippery.
Nevertheless, Fortnow and Sipser’s work led to new challenges and some new results:
- Christer Berg and Johan Håstad wrote a paper explaining the issues clearly.
- Jin-Yi Cai, Ajay Nerurkar, and D. Sivakumar proved a nice hierarchy for probabilistic polynomial time above polynomial, a Buffalo product.
- Per Ken’s memory, Rutger Verbeek thought he had solved Lance and Mike’s problem, but the complicated proof again had flaws. However, this led him and Robert Rettinger to a valid solution (alternate link) to the truth-table case—which is enough to indicate that getting a true hierarchy will be hard.
- Lance and Rahul Santhanam, however, proved a tight hierarchy when the probabilistic machines have one or more bits of nonuniform advice, or when they can fail on a small fraction of instances. Dieter van Melkebeek and Konstantin Pervyshev extended the former result to almost any “semantic” machine model, so it holds for with advice as well.
- Recently there has been interest in whether hierarchies are tied up with de-randomization issues, such as indicated by this StackExchange item with a nice answer by Ryan Williams.
In summary: mathematics does not more forward in a perfect monotone fashion. Mathematicians make mistakes, and sometimes they are fixed and sometimes not. But one thing is certain: unless people try to prove great results they will never be resolved. I discussed this before in comparing math to mountain climbing.