Big Results Can Come In Small Packages

Susan Friedlander is currently the Editor in Chief of the Bulletin of the American Mathematical Society, and also the Director of the Center for Applied Mathematical Sciences. She works on partial differential equations such as the Navier-Stokes equations. These equations are famously hard to understand, partially because of their connection to turbulence. Of course another measure of their difficulty is that they are the core of one of the remaining Clay Millennium Prize Problems.

Today I would like to talk about one of Friedlander’s brilliant ideas that has nothing to do with either the Navier-Stokes equations or turbulence.

In the latest issue of the Bulletin, October 2011, Friedlander devoted the entire issue to an interesting experiment. She had her editors select six articles from past generations that were seminal and helped stimulate research for decades, and then republished them. The were printed exactly as they appeared before—even with one or two simple typos that were there the first time. On page 215 there is “${d(x,x') <}$ otherwise”: which seems like a typo to me.

Five dated from the period 1977-1984, one was from earlier. Each editor wrote a brief introduction to their selected paper, but the stars were the original papers:

1. Poincaré Recurrence And Number Theory, by Harry Furstenberg.
2. Internal Set Theory: A New Approach To Nonstandard Analaysis, by Edward Nelson.
3. Invariants of Finite Groups And Their Applications To Combinatorics, by Richard Stanley.
4. On The Parallelizability Of The Spheres by Raoul Bott and John Milnor.
5. An Elementary Introduction To The Langlands Program, by Stephen Gelbart.
6. Lectures On Morse Theory, Old And New, by Raoul Bott.

I think this idea of republishing important papers is terrific, and I personally greatly enjoyed the issue, and urge you to take a look at it. It was wonderful to see these famous papers—we should try this experiment in theory of computing. Congratulations to Friedlander.

## Poincaré

The first paper is beautiful discussion of the modern consequences of one of the great results of Henri Poincaré, who made fundamental contributions to almost all aspects of math and physics, and was called a polymath. What I found so interesting about the paper is that Furstenberg shows how Poincaré’s theorem helped launch an entire area of research, yet it has a tiny and simple proof.

This made me think about the size of proofs and the impacts of proofs. There is, at best, a weak connection between the length of a proof and its impact and importance in mathematics. There are long proofs that have had small impact on math; there are long proofs that have had a large impact; there are short proofs that have had a small impact—no surprise with these statements. What may be surprising is that there are proofs of statements that have had huge impact, yet the proofs can be small, even tiny.

## Long Proofs With Huge Impact

Finding examples of proofs that are large, even huge, that have had large impact on mathematics is pretty easy. A moment’s thought yields many examples—you may have your own, and your own may be even better than mine.

${\bullet }$ Fermat’s Last Theorem: Andrew Wiles proved the famous theorem that there is no solution to ${x^{n} + y^{n} = z^{n}}$ where ${n\geq 3}$ and ${x,y,z}$ are non-zero integers. The proof is clearly long, and has had major impact on the understanding of number theory.

${\bullet }$ Simple Group Classification: This is the work of many mathematicians, and classifies all finite simple groups into certain infinite families with twenty-six special exceptions. The classification proof is beyond large; it is estimated to be tens of thousands of pages long. The theorem is used in many places in mathematics to solve problems invoking finite groups and even beyond.

${\bullet }$ Gödel’s Relative Consistency Of The Axiom Of Choice: Kurt Gödel proved that the Axiom of Choice (AC) can be added to set theory without causing it to become inconsistent. Set theory, as in ZF, is already inconsistent or remains so after the addition of AC. This was immensely important since AC while very useful is also quite powerful and leads to many surprising results. For instance, AC shows:

• There are sets that are not Lebesgue measurable.
• There is a way to cut up a solid sphere into five pieces and reassembly them into a sphere that is twice the volume. This is called the Banach-Tarski paradox after the great mathematicians Stefan Banach and Alfred Tarski.

## Short Proofs With Huge Impact

${\bullet }$ Euclid’s Theorem: Euclid proved almost 2300 years ago that there are an infinite number of primes. Recall the proof is to assume that there are only a finite number of primes: let ${p_{1},\dots,p_{m}}$ be all the primes. Then look at

$\displaystyle q = p_{1} \times \cdots \times p_{m} + 1.$

The number ${q>1}$ and so is divisible by some prime, let it be denoted by ${r}$. Then by assumption ${r = p_{i}}$ for some ${i}$. But this implies that ${r}$ divides ${1}$, which is a contradiction.

${\bullet }$ Halting Is Undecidable: Alan Turing of course proved that there is no Turing Machine that can tell if an arbitrary Turing Machine will halt on a given input. The proof of great importance is a clever diagonalization argument. Yet it can almost be stated as an afterthought.

${\bullet }$ Recurrence Theorem: This is due to Poincaré, and I will explain it and the proof in the next section.

## Recurrence Theorem

Let’s state the theorem precisely and then give the almost shockingly short proof. Let ${X}$ be an abstract space, and let ${\mu}$ be a measure on it. We put ${\mu(X) = 1}$ and assume that the class of measurable sets, i.e. ${A \subseteq X}$ for which ${\mu(A)}$ is defined, is sufficiently extensive. Also let ${T}$ map ${X}$ to ${X}$ so that the measure is preserved,

$\displaystyle \mu(T^{-1}A) = \mu(A),$

for all measurable sets. This is all we need to state the theorem:

Theorem: For any measurable set ${V}$ with ${\mu(V)>0}$, there exists a point ${x \in V}$ so that ${T^{n}x \in V}$ for some ${n>0}$.

I quote Furstenberg:

The proof is extremely simple. Assume that no point ${x \in V}$ returned to ${V}$. Then ${T^{-n}V \cap V = \emptyset}$ for all ${n>0}$, and so ${T^{-n}V \cap T^{-m}V = \emptyset}$ whenever ${n \neq m}$. But the sets ${T^{-m}V}$ all have the same measure ${\mu(V)>0}$, and they cannot be disjoint since ${\mu(\bigcup_{n=1}^{\infty} T^{-n}V) \le \mu(X)=1}$.

The importance of this theorem is many-fold. It helps shed light on physical systems, which is why Poincare studied it in the first place. It also has helped yield insights into combinatorics. For example, generalizations of it are shown to prove the famous theorem of Bartel Leendert van der Waerden:

Theorem: Divide the integers into ${r}$ subsets, and let ${\ell>0}$ be a natural number. Then one of the subsets contains an arithmetic progresssion of length ${\ell}$.

## Open Problems

What are your favorite examples of short proofs with large impact? The fact that they exist may even suggest some ideas for automated discovery of proofs. It plausible that while getting computers to find proofs that are huge may be impossible, getting them to help find very short ones might be possible. What about an automatic search for short, tiny, proofs with huge impact?

Also do you like Friedlander’s republish idea?

32 Comments leave one →
1. November 28, 2011 12:34 am

I think my seminal 1987 paper on cordial graphs give short proofs with large impact (Google scholar listed 131 of them). Friedlander’s republish idea is interesting and you can re-publish the original paper in somewhere else as well. See

2. November 28, 2011 2:46 am

How about the “Schwartz-Zippel-DeMillo-Lipton Lemma”? It has been tremendously useful, and it has very short proofs (cf: http://cstheory.stackexchange.com/questions/1772/alternative-proofs-of-schwartzzippel-lemma)

3. November 28, 2011 3:18 am

agree. perhaps you like this, too:
http://www.math.nmsu.edu/hist_projects/

4. November 28, 2011 6:51 am

Some of my favorite short and clever results in CS:

http://theorychatclub.blogspot.com/2011/10/short-clever-results.html

5. Alex Lopez-Ortiz permalink
November 28, 2011 8:51 am

SIGCOMM’s Computer Communications Review had for several years a section on for republishing results which had great impact on Networks research. The selection mechanism was also rather interesting. All you needed to do was write a half page introduction to the paper which, if the editors agreed with its content, would appear as preamble to the republished paper.

6. Alan Turing permalink
November 28, 2011 9:53 am

Do people really say things like “my seminal paper”? Geez, even I didn’t say that.

• November 28, 2011 12:27 pm

Someone else said that in his paper, it is not my original saying. I should put it in between quotation marks. But I see you like to be called Alan Turing!

• November 28, 2011 3:09 pm

Even though someone else said doesn’t change the affected nature of you saying it.

• November 29, 2011 11:59 am

Nonentity

• November 28, 2011 12:44 pm

math.usm.my/bulletin/pdf/v30n2/v30n2p11.pdf
(Adrian Riskin, “Cordial Deﬁciency”)

(V. J. Kaneria,, S. K. Vaidya, “Index of cordiality for complete graphs and cycle”)

arxiv.org/pdf/1103.4994
(Elliot Krop, Sin-Min Lee, Christopher Raridan, “On the edge-balanced index sets of product graphs”)

November 29, 2011 12:09 am

Perhaps not a short proof, but the idea of a place value system for representation of numbers has had such a large impact it is almost taken for granted today, and we don’t even seem to know which person to credit for it, as lamented by this paper: http://crd.lbl.gov/~dhbailey/dhbpapers/decimal.pdf by Bailey et al.

November 29, 2011 8:41 am

It’s a trivial idea so I don’t think anyone would deserve credit for it.

November 29, 2011 12:26 pm

Yes, it’s such a trivial idea that nobody thought of it for 2500 years :): that’s the point that paper makes. And you should also keep in mind that one of the main spurs to the renaissance of European mathematics starting 1200 CE was the introduction of the Indo-Arabic place value system into Europe by FIbonacci.

November 30, 2011 12:15 am

Here is a quote from Laplace about this “trivial” idea:

…….the ingenious method of expressing all numbers
by means of ten symbols, each symbol receiving a value of position as
well as an absolute value; a profound and important idea which appears
so simple to us now that we ignore its true merit. But its very sim-
plicity and the great ease which it has lent to all computations put our
arithmetic in the first rank of useful inventions; and we shall appre-
ciate the grandeur of this achievement the more when we remember
that it escaped the genius of Archimedes and Apollonius, two of the
greatest men produced by antiquity.

• November 30, 2011 6:57 am

It still is a thoroughly trivial idea, no matter what Laplace may have written. It is simply the most efficient way of writing numbers when one has b symbols at its disposal, and the trivial greedy algorithm works for this and leads to the positional system.
I’m pretty sure I for one would have discovered it pretty easily in the past.

December 1, 2011 12:40 am

I’m pretty sure I for one would have discovered it pretty easily in the past.

I am pretty sure you would have discovered the infinitude of primes too, as well as the Pythagoras theorem, and the fact that derivative and integration are inverse operations. Those are all pretty trivial too, in the same way.

The fact that today you feel you would have discovered these things, and no one, not Archimedes, not Euclid, not Baudhayan, and Babylonians discovered it (even though they all discovered pretty cool stuff: Archimedes discovered integration, Euclid’s contributions need not a count, and Baudhayan was one of the first people to talk of geometrical constructions and theorems, including the Pythagoras theorem, possibly before Pythagoras) seems to suggest to me that it is certainly not as trivial as you make it out to be.

November 30, 2011 7:43 am

It is indeed a thoroughly trivial idea, despite what Laplace may have written (arguments from authority don’t work for me). The system is simply the most efficient way of writing numbers, or distinct strings, when one has b symbols at his disposal. The trivial greedy algorithm works for this problem and leads to the positional system. For example, with one digit one can obviously express b numbers. How to add more? Just place one of the b digits after all numbers formed so far, then choose the other one, etc. Then take all such numbers and add one more digit, and so on. This is optimal and is precisely the positional system for fixed-width numbers (leading zeroes allowed).

I am pretty sure I for one would have easily discovered it back in the time.

December 1, 2011 12:45 am

It is not an argument from authority: I just added the quote to tell of the history of the problem. It was not a well known fact that someone just came and claimed for herself. It was something that beat everybody for 2500 years.

The fact that that you can talk today about “positional system” and “leading zeroes” and “digits” today is because you learnt these concepts in elementary school. Ancient mathematicians did not have that luxury, and could not claim that “For example, with one digit one can obviously express b numbers” because the very concept of “digit” did not exist.

December 1, 2011 12:50 am

Also, another simple idea with a big impact is “diagonalization”. Now given the positional representation for numbers, it takes a couple of lines to see that not you cannot list all possible numbers which can be represented thus. Yet it took 1500 years after the positional system had been defined for the notion of “uncountability” to be defined and proved. I am pretty sure that you could have done that too pretty easily in the past, but the fact stands that nobody did.

December 1, 2011 1:07 am

Also, another concept that you use in comment (even explicitly) without realizing it did not exist before the discovery of the positional system: the very notion of using a “base” for denoting numbers.

December 1, 2011 4:46 am

I only use those terms to make it more explicit what I mean, but that’s by no means necessary. By a “digit” I just mean a symbol. Same with a “base”: it’s just the set of symbols I want to use to describe numbers. So the way I’m using those has nothing to do with the positional system. Just replace “digit” by “symbol” and “base” by “number of letters I want to use”.

December 1, 2011 4:52 am

Also about “leading zeroes”: again it’s not necessary to talk about that. It’s just to make it clear how what I’m describing relates to the system we all know now. You’re totally missing my point. None of these concepts are necessary to describe or even come up with the system. You only need to ask the question: how can I obtain as many different labels as possible by using the letters in the alphabet? That’s all there is to it. So don’t tell me that one needs to know about “digits” and “base” in advance because they are exactly the same thing as “letter” and “alphabet”, respectively. And I’m pretty sure those two concepts did exist.

Diagonalization on the other hand is a very simple argument, but unlike the positional system it’s far from obvious if you’ve never seen it before.

November 29, 2011 12:15 am

Another class of really short proofs of a fundamental theorem is that of the pictorial proofs of Pythagoras’ theorem such as those found in Bhaskara’s Lilavati. The proof in Lilavati (literally, “The Beautiful”) apparently comprises just one word “Behold”. http://www.robertnowlan.com/pdfs/Bhaskara.pdf

9. Luke G permalink
November 29, 2011 1:01 am

A few other theorems I would mention for high impact and easy proofs:
Fermat’s little theorem
Cantor’s proof that the reals are uncountable (hinted at when you mention undecidability)
Ramsey’s theorem
Cauchy-Schwarz inequality

November 29, 2011 1:33 am

+1 for mentioning Cauchy Schwarz (or Schwarz-Bunyakovsky if you used Russian books in high school, like me). I would also add the whole idea is “convex functions” and Jensen’s inequality, which is such a fountain of important basic results (including Cauchy-Schwarx-Bunyakovsky, or AM-GM or the most of mathematical programming).

10. November 29, 2011 11:28 am

There’s a typo in your Wikipedia link for the Banach-Tarski paradox. Somehow, the hyphen got replaced with a hyphen struck over the letter D.

November 29, 2011 11:38 am

Phil Miller,

Thanks. Our alert staff check all links, but we do make plenty of errors. Thanks. I believe it is now functioning properly.

11. November 29, 2011 1:22 pm

One of my favorite examples of a “short proof with large impact” is also an example of another perennial theme here Gödel’s Lost Letter: “proofs coming in twos (or more)”. This example is a theorem often attributed to Loup Verlet (1966):

Symplectic shadowing theorem: Efficient integration methods exist that generate the exact symplectomorphisms associated to Hamiltonian dynamical systems that shadow natural dynamical systems.

As Verlet himself has documented, this symplectic shadowing theorem was in fact appreciated earlier by — in succession — Isaac Newton (1687), Jean Baptiste Delambre (1792), Johann Franz Encke (1865), Carl Størmer (1907), and Richard Feynman (1965). Students of math-and-science history will find more informartion in Chris Budd’s short survey titled “Geometric integration and its applications” (2006) and in the longer article by Hairer, Lubich, and Wanner titled “Geometric numerical integration illustrated by the Størmer–Verlet method” (2003) … the latter survey includes photocopies of Feynman’s original 1965 sketches! 🙂

Existing proofs of the symplectic shadowing theorem incorporate geometric, analytic, algebraic, combinatoric, dynamical and even algorithmic and informatic elements, which is unsurprising given the ambitious practical objective that moticates the theorem: the efficient simulation of complex systems by algorithms that get the detailed dynamical trajectories almost right and the first and second laws of thermodynamics exactly right.

Already a respectably large fraction of all the computer cycles in the world is devoted to symplectic integration, and as these methods are increasingly applied to quantum dynamical systems and to classical-quantum hybrids, this fraction bids fair to increase.

One of many well-posed and reasonably natural open problems is a quantum-extended version of symplectic shadowing conjecture:

The extended symplectic shadowing conjecture: Do efficient integration methods exist that generate the exact symplectomorphisms and causally separable informatic correlations associated to Lindbladian/Kählerian dynamical systems that shadow natural Lindbladian/Hilbert dynamical systems?

As during the 278-year span 1687-1965, there is presently ample empirical evidence to suggest that extended symplectic shadowing methods do exist, but there is not yet a rigorous statement-and-proof of the theorem … and even laying out the best framework for stating-and-proving the theorem will require considerable math-physics-engineering creativity.

This to my mind suggests that there is plenty of wonderful (and hopefully simple) fundamental math waiting to be discovered, and (equally important) plenty of practical applications that are awaiting the discovery of that math, and even global-scale enterprises that will be enabled by those practical applications. And with this extended hope, my best wishes for a happy holiday season are extended to everyone! 🙂

12. Dan Fox permalink
December 6, 2011 5:35 am

I liked some of the chosen articles, and read them with interest (in particular that of Gelbart), but think that the republishing scheme is a terrible waste of a great forum like the BAMS.

All the republished articles are already available for free online and easily found by an interested student with access to a decent search engine. At the same time, it would certainly be possible to fill an issue of the BAMS with equally interesting newly written surveys (as is done in most issues).

The laudable objective of bringing to the attention of the young and ignorant the great overview articles of ancient decades of the past millenium could also be accomplished by directing them to the online repository.

• GS Chandy permalink
December 16, 2011 1:03 pm

I believe Dan Fox has come out with a most valid critique of Susan Friedlander’s idea of re-publishing some seminal articles. She might have done better to have pointed to those articles and provided some commentary on their significance, what came out of them, and so on.

— GSC

13. GS Chandy permalink
December 16, 2011 12:50 pm

David claims that the idea of the “place-value system” is obvious (and trivial?) and that – had it not been already discovered at this time – he would have discovered it.

I’d be very keen to know some of other ‘obvious’/’trivial’ ideas David has discovered/would have discovered (assuming they had not already been discovered)

— the concept of zero, perhaps ? It’s obvious, trivial – and essential. I’m sure David would have had the idea first, had not some unknown Indians already had it some centuriies ago.

— using symbols to count instead of fingers and toes. This too is obvious and trivial – and obviously David would have sorted it all out if we did not already have the idea in place.

— What else???

GSC