97
$\begingroup$

I am looking for examples of theorems that may have originally had a clunky, or rather technical, or in some way non-illuminating proof, but that eventually came to have a proof that people consider to be particularly nice. In other words, I'm looking for examples of theorems for which have some early proof for which you'd say "ok that works but I'm sure this could be improved", and then some later proof for which you'd say "YES! That is exactly how you should do it!"

Thanks in advance.

A sister question: Examples of major theorems with very hard proofs that have NOT dramatically improved over time

$\endgroup$
12
  • 6
    $\begingroup$ Seems related to the earlier MO question mathoverflow.net/questions/43820/extremely-messy-proofs. $\endgroup$ May 3, 2012 at 10:13
  • 3
    $\begingroup$ I don't know the original proof, but I heard that the trick of Rabinovich provided a drastic improvement of the proof of Hilbert's Nullstellensatz. $\endgroup$ May 3, 2012 at 21:42
  • 7
    $\begingroup$ It would be also interesting to hear of theorems where people didn't think that the proof could be much improved, but then were proven wrong. $\endgroup$ Jul 9, 2012 at 6:02
  • 4
    $\begingroup$ Many answers here so far seem to have the form "The original proof of X was very complicated, but now one can prove it as a simple consequence of Y." -- But if the proof of Y is not itself simpler than the original proof of X, should this qualify? $\endgroup$ Jun 28, 2013 at 2:57
  • 3
    $\begingroup$ @LouisDeaett: Good question. There is something, though, still nicer about having a proof follow as a simple consequence of something complicated. It shows there is some larger (unifying?) idea. $\endgroup$
    – Manya
    Dec 3, 2013 at 6:50

46 Answers 46

1
2
9
$\begingroup$

One historical example that should probably be on this list is the Abel-Ruffini Theorem, which states that there is no general solution in radicals to polynomials of degree 5 and higher. Attempting to clarify the bigger picture of why the proof works may have been one of Galois's motivations for his development of what is now Galois Theory- and the proof we have now is quite insightful and illuminating.

$\endgroup$
9
$\begingroup$

Szemeredi's theorem and its special case Roth's theorem have been given quite conceptual proofs by Hilel Furstenberg using ergodic methods which I think is quite natural while the initial proofs were extremely complicated.

$\endgroup$
1
  • 4
    $\begingroup$ The original ergodic proof of Szemeredi's theorem is arguably not a perfect example for this list, since both Austin's and Polymath proofs of the density Hales-Jewett theorem are significantly simpler. $\endgroup$
    – pavel
    Dec 20, 2013 at 22:31
8
$\begingroup$

The original proof of Muller-Schupp theorem saying that finitely generated groups with context-free word problem are exactly the virtually free groups, is really involved (though nice) and uses accessibility and Stallings results on ends.

But there is a short and elementary way to prove Muller-Schupp theorem using rewriting systems, as was recently done by Volker Diekert.

$\endgroup$
8
$\begingroup$

The Amitsur-Levitski Theorem (the standard non-commutative polynomial of order $2n$ vanishes identically on $M_n(k)$) qualifies. The original proof (1950) is messy, with no clear logical structure and takes 17 pages. The natural proof was given in 1976 by S. Rosset in a 2-pages article.

$\endgroup$
5
  • $\begingroup$ Where can I find the 60-pages long original proof? "Minimal identities for algebras" is just 15 pages long ( ams.org/journals/proc/1950-001-04/S0002-9939-1950-0036751-9/… ), and proves AL (its Theorem 1) on its page 7. Does it rely on lots of other references? $\endgroup$ Sep 11, 2015 at 11:28
  • $\begingroup$ Also, it is question whether Rosset's proof is really "natural". It requires a lift to a characteristic-$0$ ring, which is suggested by nothing in the statement; and from there it still proceeds to apply some interesting and highly surprising tricks. I think there is much to be learned from that proof, but "natural" looks different. $\endgroup$ Sep 11, 2015 at 11:35
  • $\begingroup$ Darij, yes 17 pages indeed ! $\endgroup$ Sep 11, 2015 at 15:53
  • $\begingroup$ The paper is 15 pages long, and the theorem is proven on page 7. Now I am really curious how this adds up to 17 ;) $\endgroup$ Sep 11, 2015 at 18:31
  • 1
    $\begingroup$ One thing I can confirm, though: the original proof does look like a mess! $\endgroup$ Sep 11, 2015 at 18:32
7
$\begingroup$

The first proof of the Hopf invariant one theorem due to Adams is very technical. It involves decomposing $sq^{2^n}$ as a composite of secondary cohomology operations when $n\geq 4$. Then Atiyah and Adams came up with a proof that uses $K$-theory which both admired for its elegance and simplicity.

$\endgroup$
7
$\begingroup$

an example from number theory (where such simplifications are not uncommon), Bertrands postulate

for any integer $n > 3$, there always exists at least one prime number $p$ with $n < p < 2n − 2$

was first simplified by Ramanujan and then later by Erdos who also proved a more general case.

another interesting case study here may be Lindemanns proof of transcendence of PI which is subsumed by later more general results. as Wikipedia states "Weierstrass proved the above more general statement in 1885. The theorem, along with the Gelfond–Schneider theorem, is extended by Baker's theorem, and all of these are further generalized by Schanuel's conjecture."

another "possible/controversial" famous/legendary case study here is Fermats Last Theorem; Fermat scribbled in the margin of his book that he had a remarkable proof, but modern consensus is that he must have been mistaken based on the 2020-hindsight of Wiles complex proof. however, strictly speaking, it has not been proven impossible that there exists a short proof.

it seems that later simplifications of proofs is a natural process of the historical/evolutionary progress of mathematics so that results once thought more arcane/inscrutable/complex become more accessible with the polishing/systematization of ideas/techniques.

$\endgroup$
2
  • 3
    $\begingroup$ "However, strictly speaking, it has not been proven impossible that there exists a short proof." Well, sure, but for which theorem has it been proven impossible that there exists a short proof?? $\endgroup$ Dec 24, 2013 at 11:30
  • $\begingroup$ agreed. the question of short proofs is closely related to Kolmogorov complexity theory & Chaitin's incompleteness both tied up with undecidability. there do exist some results or so-called "no-go/barrier theorems" in the form that "a proof for [x] cannot use theory [y]". $\endgroup$
    – vzn
    Dec 24, 2013 at 16:11
6
$\begingroup$

Godel's original proof of his Incompleteness Theorem was immensely more complicated Aaronson's one-paragraph derivation of Incompleteness from Undecidability of Halting Problem. Even including a proof of Undecidability of Halting it would be much shorter and clearer than the original proof.

$\endgroup$
1
  • 9
    $\begingroup$ I agree that the concept of computability does give a nicer proof of Goedel's theorem, but I wouldn't describe the situation in quite this way. Aaronson's sketch glosses over the issue of expressing the halting of a Turing machine as an arithmetical statement. A large fraction of Goedel's proof is devoted to proving the expressibility of syntactical facts in the language of arithmetic, and these complexities are not avoided in Aaronson's sketch; they're just swept under the rug. So I don't think it's fair to say that Goedel's original proof was "immensely more complicated." $\endgroup$ Jan 10, 2016 at 20:32
6
$\begingroup$
  1. Chirka's proof ("On the propagation of holomorphic motions", 2004) of Slodkowski's theorem ("Holomorphic motions and polynomial hulls", 1991) is much simpler. (Slodkowski's paper is not that long, but uses a lot more difficult mathematics. A number of people had previously attempted to give alternative proofs, but these turned out to contain gaps.)

  2. The original proof by Baker that repelling periodic points are dense in Julia sets of transcendental entire functions used the Ahlfors five islands theorem (a very deep result). The proof by Duval and Berteloot (Une démonstration directe de la densité des cycles répulsifs dans l’ensemble de Julia), building on work of Schwick, takes less than a page, and uses only very elementary results (notably, Zalcman's rescaling lemma for normal families). Even for rational functions, this is probably the simplest proof (simpler than the original ones of Fatou and Julia) currently in existence.

$\endgroup$
6
$\begingroup$

Manjul Bhargava's proof of the 15 theorem was dramatically simpler than Conway and Schneeberger's original proof.

$\endgroup$
7
  • $\begingroup$ The bad stuff were given to a computer in MB's proof while CS proof was all by hand. Is there a link to CS' proof? $\endgroup$
    – Turbo
    Nov 8, 2013 at 18:49
  • 4
    $\begingroup$ JAS, I think you are confusing the 15 theorem and the 290 theorem. CS never published a full proof of the 15 theorem because it was so messy (a sketch appears in Schneeberger's Ph.D. thesis), and did not think that the 290 theorem was provable at all. MB's proof of the 15 theorem is short and the computer calculations are pretty modest by modern standards. Granted, the proof of the 290 theorem by MB and Hanke is indeed highly computational, but again, CS didn't have a proof of it at all. $\endgroup$ Nov 8, 2013 at 19:24
  • $\begingroup$ ah ic. I think MB proved something more general. For every subset $S\subseteq\Bbb N$, there is a finite subset $S_f\subsetneq S$ such that if a quadratic form represents $S_f$, then it represents $S$. Is there a link to the proof? How constructive is the set $S_f$? $\endgroup$
    – Turbo
    Nov 8, 2013 at 19:30
  • $\begingroup$ There are several possible links; I think it's easier for you to Google it yourself than for me to try to post the links here. $\endgroup$ Nov 9, 2013 at 0:47
  • 2
    $\begingroup$ @Turbo: For the 15 theorem, see Manjul Bhargava, "On the Conway-Schneeberger fifteen theorem," in Quadratic forms and their applications, Contemp. Math. 272 (1999), 27–37. For the 290 theorem, try math.stanford.edu/~vakil/files/290-Theorem-preprint.pdf $\endgroup$ Jan 21, 2016 at 21:22
5
$\begingroup$

In machine learning and statistics, the technique of Rademacher complexities has a way of radically simplifying otherwise complicated proofs -- in particular those involving margin-based generalization bounds.

Some examples include Support Vector Machine margin bounds, which used to be proved via intricate combinatorial fat-shattering techniques of https://homes.di.unimi.it/~cesabian/Pubblicazioni/jacm-97b.pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.42.6950&rep=rep1&type=pdf http://www.sciencedirect.com/science/article/pii/S0304397500001341 and are now proved in 3 lines (see the Thm. 4.3 in http://www.cs.nyu.edu/~mohri/mlbook/ ).

Another example is margin-based boosting bounds, which were originally proved via an involved covering and sampling argument, http://projecteuclid.org/euclid.aos/1024691352 and now has a very simple Rademacher-based proof (Thm. 5.7 in https://mitpress.mit.edu/books/boosting ).

$\endgroup$
5
$\begingroup$

Some results by Donaldson were simplified via the Seiberg-Witten invariants.

From Wikipedeia: Seiberg–Witten invariants are similar to Donaldson invariants and can be used to prove similar (but sometimes slightly stronger) results about smooth 4-manifolds. They are technically much easier to work with than Donaldson invariants; for example, the moduli spaces of solutions of the Seiberg–Witten equations tend to be compact, so one avoids the hard problems involved in compactifying the moduli spaces in Donaldson theory.

See also this MO answer by Dylan Thurston.

(Added Jan 7, '16) An additional piece of information I learned today from the Zabrodsky's lecture delivered by Peter Ozsváth is about the existence of exotic smooth structure on $\mathbb R^4$. The original proof was based on Freedman theorem and on Donaldson theorem. Results based on new knot invariants such as the Knot Floer homology (and simpler combinatorial descriptions of these invariants) can replace the "Donaldson side" of the proof by a much simpler argument.

$\endgroup$
5
$\begingroup$

Faltings' theorem (aka Mordell conjecture) can be taken as such an example. Different methods have been used so far with various difficulties.

$\endgroup$
0
3
$\begingroup$

DeMoivre's theorem. The pre-calc version of the proof relies on a lot of triangle geometry to establish trigonometric sum formulas and then uses induction. If you use Euler's Identity, it's a one line proof. (Of course, then there's a large amount of analysis implicit in the background.)

$\endgroup$
2
$\begingroup$

See Ostrowski's proof of Luroth theorem in Schinzel's book "Polynomials with special regard to reducibility"

$\endgroup$
1
$\begingroup$

The four color theorem’s first proof by Appel and Haken, which actually contained mistakes, was proved again much more succinctly and successfully by Robertson, Sanders, Seymour, and Thomas (see for instance here). As far as I know, there is no better proof as yet, and unlikely there will ever be one, but who knows.

$\endgroup$
3
  • $\begingroup$ I had never heard that the Appel and Haken proof "actually contained mistakes" so I googled it. Wolfram MathWorld says "This result was finally obtained by Appel and Haken (1977)...no flaws have yet been found, so the proof appears valid. A shorter, independent proof was constructed by Robertson et al." This suggests to me that there are no known mistakes in the Appel and Haken proof mathworld.wolfram.com/Four-ColorTheorem.html $\endgroup$ Oct 13, 2022 at 12:01
  • $\begingroup$ @David White: That information is incorrect. I personally know Seymour and Robertson (and when he was alive, Thomas). Take it from them, the AH proof had mistakes, which AH tried to correct later. But those latter efforts were never checked. Robertson, Sanders, Seymour, and Thomas thought it would be better to find a proof from the start, making sure to verify the proof each step along the way. Their proof has been computer verified by Gonthier using a proof assistant. Not so the proof by Appel and Haken. $\endgroup$
    – EGME
    Oct 14, 2022 at 13:16
  • $\begingroup$ @David White: Check this out from Gonthier: microsoft.com/en-us/research/wp-content/uploads/2016/02/… $\endgroup$
    – EGME
    Oct 14, 2022 at 13:22
-2
$\begingroup$

Liouville's Theorem that there exists a transcendental number had its proof greatly improved by Cantor who showed that a mere counting argument suffices.

Liouville's argument needs facts about how rationals interact with polynomials, and makes use of the metric structure on the reals.

Cantor's argument merely uses the fact that each integer polynomial can be described in finitely many symbols and has only finitely many roots. And it uses this to deduce a stronger result: that almost no reals are algebraic.

$\endgroup$
12
  • 1
    $\begingroup$ I think the downvotes are excessive and have upvoted to compensate, but I also don't think this is fully an answer to the question: Liouvill's proof, while more complicated than the cardinality argument, is by no means "clunky, or rather technical, or in some way non-illuminating." $\endgroup$ May 10, 2020 at 20:30
  • $\begingroup$ @NoahSchweber I think it's both clunky and nonilluminating. The cardinality proof shows that the entire issue really has nothing to do with approximations, rationals or polynomials. You could extend the definition of 'algebraic' in many ways (for example to the closure of the algebraics under $\exp$ and $\log$) and Cantor's proof would show with no extra effort that there were still reals outside your set, whereas Liouville's proof would fall apart. Cantor's proof uses less to do more, and in a way which is more generalizable. $\endgroup$ May 10, 2020 at 21:34
  • $\begingroup$ In any case I added some of these justifications to my answer, so hopefully that will stem the flow of downvotes. $\endgroup$ May 10, 2020 at 21:35
  • 1
    $\begingroup$ @ZachTeitler I just had this conversation on reddit, so you can have the first 20 digits! old.reddit.com/r/math/comments/ggx2vr/… $\endgroup$ May 10, 2020 at 23:11
  • 1
    $\begingroup$ @ZachTeitler Although not phrased explicitly, Cantor's argument easily gives concrete examples. For instance, suppose at stage $n$ we've determined the first $k_n$ bits of the binary expansion of the number $C$ we want to be transcendental. Fixing an appropriate enumeration of the nonconstant polynomials over $\mathbb{Q}$, it's easy enough to find a sub-interval of the interval we've currently limited $C$ to within which the $n$th such polynomial has no zeroes. This isn't truly difficult, although of course Liouville's is simpler by far. $\endgroup$ May 10, 2020 at 23:20
1
2

Not the answer you're looking for? Browse other questions tagged or ask your own question.