A Brilliant Idea In Publishing
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 “
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:
- Poincaré Recurrence And Number Theory, by Harry Furstenberg.
- Internal Set Theory: A New Approach To Nonstandard Analaysis, by Edward Nelson.
- Invariants of Finite Groups And Their Applications To Combinatorics, by Richard Stanley.
- On The Parallelizability Of The Spheres by Raoul Bott and John Milnor.
- An Elementary Introduction To The Langlands Program, by Stephen Gelbart.
- 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.
- 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
The number 
Recurrence Theorem
Let’s state the theorem precisely and then give the almost shockingly short proof. Let 
for all measurable sets. This is all we need to state the theorem:
Theorem: For any measurable set
with
, there exists a point
so that
for some
.
I quote Furstenberg:
The proof is extremely simple. Assume that no point
for all
whenever
. But the sets
all have the same measure
.
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
subsets, and let
be a natural number. Then one of the subsets contains an arithmetic progresssion of length
.
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?
[Fixed broken link]
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
http://neu-tr.academia.edu/IbrahimCahit/Papers/880545/Graceful_harmonious_and_cordial_graphs
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)
agree. perhaps you like this, too:
http://www.math.nmsu.edu/hist_projects/
Some of my favorite short and clever results in CS:
http://theorychatclub.blogspot.com/2011/10/short-clever-results.html
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.
Do people really say things like “my seminal paper”? Geez, even I didn’t say that.
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!
Even though someone else said doesn’t change the affected nature of you saying it.
Nonentity
Please see
math.usm.my/bulletin/pdf/v30n2/v30n2p11.pdf
(Adrian Riskin, “Cordial Deficiency”)
ijamc.psit.in/ijamc/index.php/ijamc/article/download/86/pdf2.4.5
(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”)
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.
It’s a trivial idea so I don’t think anyone would deserve credit for it.
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.
Here is a quote from Laplace about this “trivial” idea:
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.
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.
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.
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.
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.
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.
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”.
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.
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
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
+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).
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.
Phil Miller,
Thanks. Our alert staff check all links, but we do make plenty of errors. Thanks. I believe it is now functioning properly.
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):
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:
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! 🙂
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.
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
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