Giants Known For Small Things
How small results can be extremely important
By permission of Paul Helm, artist—source
Johannes Brahms is one of the “Three B’s” of music, along with Johann Sebastian Bach and Ludwig van Beethoven. Yet among pieces of music one would call “Brahms’ X,” he seems to be widely known only for Brahms’ Lullaby. His great German Requiem is close, but Wikipedia won’t even forward …/wiki/Brahms’s_Requiem or …/wiki/Brahms’_Requiem to it unless you remove the apostrophe. Whereas Beethoven’s Fifth and Ninth, and Bach’s chorales, fugues, and cantatas come trippingly off the cloud.
Today Ken and I wish to point out a curious phenomenon: often the simplest results are the best known. Also they may be the most important after all.
‘Who is best known for what’ belongs to a genre of culture trivia questions that have been debated in taverns for centuries. Yet only in the past two decades have we had a neutral way to resolve them: the Internet. The distribution of hits on various searches gives unscientific but meaningful survey feedback. Thus we have tried searching “N’s Theorem” putting various names in place of ‘N’—and you can do likewise.
Often what you get for famous “giants” of the field are simple results. We are not saying that the giants are only known for these results—after all, Brahms is known for much more than the lullaby. Yet how many parents have used this great lullaby—this is one version:
Lullaby and goodnight
With roses bedight
With lilies o’erspread
Is baby’s wee bed
Lay thee down now and rest
May thy slumber be blessed
Lay thee down now and rest
May thy slumber be blessed
—to try to get their little ones to sleep? Countless. It is also musically formative for them.
(source with podcast)
I think there are a number of reasons for this phenomenon, but first let’s give a few examples. We will begin with two by Niels Henrik Abel.
Abel was a Norwegian mathematician who made many seminal contributions to mathematics during his tragically short life. His work included brilliant research into the theory of functions, particularly elliptic functions, and created a new class of functions now called abelian functions. And yes he is the “abel” in the term “abelian group,” and the “Abel” in the Abel Prize.
As we discussed recently here, Abel is indeed famous for giving the first rigorous proof of the impossibility of solving the quintic equation by radicals. Earlier a serious—and almost correct—“proof” had been given by Paolo Ruffini, but it was ignored for various reasons, perhaps owing to his manuscript being 500 pages. See this for some of the history. Yet what we find for Abel’s X by itself are two results on infinite sums that are bagatelles by today’s standards:
Abel’s lemma: One of Abel’s most useful results is a simple summation formula that he needed in another paper. It is the following:
This is often called summation by parts, because it allows a non-trivial transformation of any finite sum. While it is easy to prove, it is used frequently in all parts of mathematics—especially in analytic number theory. The ability to re-write any sum is what gives this result its immense power. I (Dick) was reading a number theory paper just the other day and counted three calls to this trick in four pages.
Note it is really the finite version of integration by parts:
This is a perfect example of how sum formulas can be much more involved than integration formulas. Too bad in complexity theory we mostly deal with finite sums. Oh well.
Abel’s theorem: This is the other paper, and says that if converges, then converges to the same value as approaches from below. Isn’t this obvious? Well it’s non-trivial since makes the latter sum diverge, but today we might not even bother pointing that out in a lecture. Two hundred years ago, just at the time of Cauchy’s convergence criterion, it was important to be rigorous with series, while now we use results like this tacitly all the time.
Joseph-Louis Lagrange made key contributions to all fields of analysis, number theory, and classical and celestial mechanics. One of my favorites is the four square theorem proved in 1770: that every positive integer is the sum of four squares. One interesting comment related by our friends at Wikipedia is:
Due to thorough preparation, he was usually able to write out his papers complete without a single crossing-out or correction.
Ken and I have no idea what we would do without word processing, spell checkers, and the ability to make changes easily. Ken didn’t begin writing his dissertation at Oxford until he had introduced such a system to the University.
The “small” result of Lagrange is the classic theorem of his: Suppose that is a subgroup of the finite subgroup . Then the size, in number of elements, of divides the size of . This theorem is an invaluable tool in all of finite group theory. Indeed this restriction on the size of subgroups is what makes group theory so different from other mathematical areas: in graph theory, for example, there is no such restriction on the size of a subgraph.
Augustin-Louis Cauchy did so much great and seminal research that we will not even try to list some of the areas. We have already mentioned his convergence criterion for a sequence :
But when we search on Cauchy’s Theorem, we mainly get Lagrange in a mirror, or the Schwarz is with us.
Cauchy’s theorem: If is a prime number that divides the order of a finite group , then has an element of order . Caution: this is not true in general if is not a prime—the converse of Lagrange is false, in general.
Cauchy Inequality: For all complex valued vectors ,
Where would a fraction of our results in theory be without this irreplaceable tool? Of course the history of this fundamental result is more involved as you probably know since we often call it the “Cauchy-Schwarz” inequality. More properly it is sometimes called the Cauchy-Bunyakovsky-Schwarz Inequality. The sum version was published in 1821 by Cauchy, the integral version by Viktor Bunyakovsky in 1859, and it was rediscovered by Hermann Schwarz in 1888. Whatever you call it, we all need and depend on it.
Banach and Tarski
Stefan Banach picked up the mantle about series and convergence, with his notion of a Banach space. But his most useful result seems again to be almost a definition:
Banach’s Theorem: A contraction mapping on a Banach space , meaning the distance from to is always bounded by times the distance from to , has a unique fixed point such that . Proof: Iterate and use the triangle inequality for uniqueness.
Though some algebra makes the proof stretch over a page, it’s really this simple. Nevertheless, this idea is used umpteen times in analysis, usually for a proof that a solution exists. Among many fixed-point theorems this is about the simplest one to prove. Yet it is one of the most useful.
Alfred Tarski did an incredible amount of deep work in geometry as well as logic. Yet a development by Emil Post following Alan Turing renders the modern understanding of his “Theorem” completely simple.
Tarski’s Theorem: The set of true statements in the natural numbers is not definable in formal arithmetic. Proof: If were definable it would be in some fixed level of Post’s arithmetical hierarchy, but then we’d have which would collapse the hierarchy, which is false by Turing’s theorem. Well our friends at Wikipedia say there is technically more to it, but the above simple treatment is what gets it included in a fair number of introductory theory courses.
Simple and simple. But when you put both names together, you get the Banach-Tarski theorem, which is so un-simple and incredible that our Wiki friends call it a “Paradox” and neither Ken nor I really understands it.
Little Lemmas in Complexity
Venturing into our era, it is perhaps not the time to make “known for” judgments. But we would like to point out two simple results that go into the background of our technical thinking, yet are invaluable.
Turing Machine Linear Speedup: Juris Hartmanis and Richard Stearns have made many key contributions to complexity theory—we’ve been discussing one recently. One of the simplest remarks they have is the linear speedup theorem. The linear speedup theorem states that given any real and any Turing machine solving a problem in time , there is another machine that solves the same problem in time at most . This is one of those almost trivial remarks that is invaluable. The key “trick” is to increase the alphabet so the machine does more computation per unit time: the theory version of upgrading from a 16-bit processor chip to a 64-bit processor chip. We believe they showed tremendous insight in actually making this simple idea a concrete result. Cool.
Block Respecting Turing Machines: John Hopcroft, Wolfgang Paul, and Les Valiant have done many many brilliant things in their research together and separately. In their famous paper “On Time Versus Space” they needed to show that any Turing Machine that runs in time can be replaced by another Turing Machine that accepts the same language, runs in the same time, and is block respecting. The big result in that paper is the proof that space is more powerful than time—a landmark theorem. But in their proof they needed to make the machines block respecting.
I (Dick) recall that Wolfgang told me he thought that this lemma was more important than the “big” separation theorem. I was a bit skeptical at the time. But over the years I have used this lemma several times. I covered the lemma three years ago here and gave a new application. It is used in my joint paper with Ryan Williams which just appeared at the Computational Complexity Conference in Portugal.
Why This Phenomenon?
We think the answer is fairly simple, but we may be wrong. What happens in many cases when great researchers are trying to prove a “big” result is that they face some roadblock. Since they may be the first to face this obstacle they prove the required lemma to get around it. The new passageway means more to other researchers than the particular theorem that was found. At least that is how to explain some of the above examples.
Another fact is that short is sweet and simple is sweeter. We remember the four notes of Beethoven’s Fifth, and the “Ode to Joy” of the Ninth, although the depth of these pieces is elsewhere.
The third reason is that although simplicity need not mark a great proof, it goes with a great theorem statement, and may be required for a great idea. Most of these results, and maybe most others you would find, are the first application of a simple but profound new idea.
What is your favorite simple result by a great researcher that is an invaluable tool? We wish we had a good name for these results. Any suggestions?