Opinion 82: A Good Lemma is Worth a Thousand Theorems

Written: Aug. 14, 2007.

Theorems are nice, but they are usually deadends. A lemma may be "trivial", or easy, to prove, once stated, but if it is good, its value far surpasses even the deepest theorems. Wiki has a fairly long list of lemmas, including the powerful Schur's Lemma, Lovasz's Local Lemma, and many others. But my absolute favorite, that lead to at least two Fields medals (so far), is Szemeredi's Regularity Lemma. (see also the beautiful Komlos-Simonovits exposition). Its significance was lauded in two consecutive MAA Hedrick lectures, last year by Tim Gowers, and this year by Jennifer Chayes. For example, the recent Green-Tao breakthrough, about primes in arithmetic progressions, used a hypergraph extension of Szemeredi's great lemma.

Endre Szemeredi is most famous for his theorem, but his lemma is yet more significant.

So blessed be the lemmas, for they shall inherit mathematics. Even more important than lemmas are observations, but that is another story.

---

Added Aug. 22, 2007: Vince Vatter kindly pointed my attention to this funny economist's critique of lemmas, but of course for them "lemmas" means "complicated".

---

Added Aug. 23, 2007: Todd Trimble kindly pointed out the following quote from Paul Taylor ("Practical Foundations of Mathematics" ,p. 192):

"Lemmas do the work in mathematics: Theorems, like management, just take the credit. A good lemma also survives a philosophical or technological revolution."

---

Added Sept. 11, 2007: Kevin Buchin kindly tole me about the beautiful woderful quote from THE BOOK.

Chapter "Lattice Paths and Determinants" in Aigner, Ziegler:"Proofs from THE BOOK" begins with:

The essence of mathematics is proving theorems – and so, that is what mathematicians do: they prove theorems. But to tell the truth, what they really want to prove once in their lifetime, is a Lemma, like the one by Fatou in analysis, the Lemma of Gauss in number theory, or the Burnside-Frobenius Lemma in combinatorics.

Now what makes a mathematical statement a true Lemma? First, it should be applicable to a wide variety of instances, even seemingly unrelated problems. Secondly, the statement should, once you have seen it, be completely obvious. The reaction of the reader might well be one of faint envy: Why haven’t I noticed this before? And thirdly, on an esthetic level, the Lemma including its proof should be beautiful!

(also in: Martin Aigner, Lattice Paths and Determinants, in H. Alt (Ed.): Computational Discrete Mathematics, LNCS 2122, pp. 1–12, 2001.)

---

Opinions of Doron Zeilberger