Quick proofs of hard theorems

Question

Mathematics is rife with the fruit of abstraction. Many problems which first are solved via "direct" methods (long and difficult calculations, tricky estimates, and gritty technical theorems) later turn out to follow beautifully from basic properties of simple devices, though it often takes some work to set up the new machinery. I would like to hear about some examples of problems which were originally solved using arduous direct techniques, but were later found to be corollaries of more sophisticated results.

I am not as interested in problems which motivated the development of complex machinery that eventually solved them, such as the Poincare conjecture in dimension five or higher (which motivated the development of surgery theory) or the Weil conjectures (which motivated the development of l-adic and other cohomology theories). I would also prefer results which really did have difficult solutions before the quick proofs were found. Finally, I insist that the proofs really be quick (it should be possible to explain it in a few sentences granting the machinery on which it depends) but certainly not necessarily easy (i.e. it is fine if the machinery is extremely difficult to construct).

In summary, I'm looking for results that everyone thought was really hard but which turned out to be almost trivial (or at least natural) when looked at in the right way. I'll post an answer which gives what I would consider to be an example.

I decided to make this a community wiki, and I think the usual "one example per answer" guideline makes sense here.

Answer 1

Here is my example. In the 1930's (I think), Wiener gave a proof that if $f$ is a continuous nonvanishing function on the circle with absolutely convergent Fourier series, then so is $1/f$. The proof was a long piece of hard analysis, involving detailed local calculations and complicated estimates. Later (in the 1940's?), Gelfand found that the statement follows from the basic theory of Banach algebras as follows. The functions on the circle with absolutely convergent Fourier series can be characterized as the image of the Gelfand transform $\Gamma: l^1(\mathbb{Z}) \to C(S^1)$. In general if $\Gamma: B \to C(M)$ is the Gelfand transform from a commutative Banach algebra to the ring of continuous functions on its maximal ideal space, then $x$ is invertible in $B$ if and only if $\Gamma(x)$ is invertible in $C(M)$. So the hypotheses on $f$ imply that $f = \Gamma(x)$ for some invertible $x$ in $l^1(\mathbb{Z})$, and a simple calculation shows that $1/f = \Gamma(x^{-1})$.

Answer 2

There is a theorem in finite group theory, that if $a$, $b$, and $c$ are integers all greater than $1$, there exists a finite group $G$ with elements $x$ and $y$ such that: $x$ has order $a$, $y$ has order $b$, and $xy$ has order $c$. I think the first person to prove this was G.A. Miller, whose proof looked at lots of separate cases, and had tons of long, tedious calculations in symmetric groups (I will try and find the paper and post the reference later). I don't know who discovered the more modern proofs, but Derek Holt posted a proof on the group-pub that is one of the most elegant things I've ever seen. Unfortunately, it doesn't seem to be available on the archive of the list, so I will just post it here verbatim:

Let $q$ be a prime power such that $q-1$ is divisible by $2a$, $2b$, and $2c$. We will construct elements $x, y$ of $\operatorname{SL}(2,q)$ such that $x$, $y$, and $xy$ have orders $2a$, $2b$, and $2c$, and then the images of $x,y,xy$ in $\operatorname{PSL}(2,q)$ will have orders $a$, $b$, and $c$ as required.

An element of $\operatorname{SL}(2,q)$ with distinct eigenvalues is diagonalizable in $\operatorname{GL}(2,q)$, and so its order is determined by its characteristic polynomial which is determined by its trace. In particular, since $2a,2b,2c > 2$, this applies to elements with these orders.

Let $u$ and $v$ be elements of the field $\mathbb{F}_q$ with multiplicative orders $2a$ and $2b$, and let $x = \left( \begin{array}{cc} u & 1 \\ 0 & u^{-1} \end{array} \right)$ and $y = \left( \begin{array}{cc} v & 0 \\ t & v^{-1} \end{array} \right)$ be in $\operatorname{SL}(2,q)$, where $t$ remains to be chosen. Then $x$ and $y$ have orders $2a$ and $2b$.

The trace of $xy$ is $uv + t + u^{-1}v^{-1}$, and so by suitable choice of $t$, we can make this equal to any value we like. So we can make it equal to the trace of an element of $\operatorname{SL}(2,q)$ with order $2c$, and then $xy$ will have order 2c.

Answer 3

Cantor's proof of the existence of transcendental numbers. With a (now) obvious one-line argument he showed that there are uncountably many of them --- when Liouville, Hermite and others had to take (putative) transcendental numbers one at a time ...

Newman's argument (especially Korevaar's and Zagier's version of it) turned the Prime Number Theorem, which took a century to be proved, into something that can be explained in a few minutes to any graduate student.

Answer 4

In 1917 Hardy and Ramanujan proved that all but $o(x)$ integers $n \leq x$ have $\log\log n + O((\log\log n)^{1/2 + \epsilon})$ distinct prime factors. The proof was long and relied on establishing (by induction!) an precise bound for the number of integers with exactly $k$ distinct prime factors (with $k$ arbitrary, and possibly tending to infinity with $x$). A short "two-line" proof was found by Turan in 1934.

Hardy disliked Turan's proof, because as he claimed, it did not give proper insight. However as it turned it was Turan's method that was prone to generalization. Twenty years later his inequality became the more general Turan-Kubilius inequality. Curiously enough it was later realized by Elliott that taking the "dual" of Turan-Kubilius's inequality yields immediately the arithmetic large sieve inequality! :-)

Answer 5

The Nielsen-Schreier subgroup theorem: subgroups of free groups are free. This has a very quick proof using the fact that a group is free precisely when it acts freely and without inversions on a tree.

Answer 6

The Cayley-Hamilton theorem. Apparently, Cayley only proved it for $2\times2$ and - in a horrendous calculation - for $3\times3$ matrices and then wrote something outrageous in the spirit of "and similarly, we can prove it for any $n$". Hamilton then proved another special case in a paper on linear operators on the space of quaternions. Nowadays, it is proven in full generality in just a couple of lines, using the fact that the set of diagonalisable matrices of a given dimension, for which the theorem is trivially true, is dense in the set of all matrices of the same dimension.

Answer 7

The Brouwer fixed point theorem might be such an example. With homotopy theory it's easy to prove, but the original proof was "hands on".

Answer 8

The fundamental theorem of algebra is a very easy consequence of Liouville's theorem in complex analysis.

There is also the (even simpler) proof due to Schep.

Answer 9

Though the idea behind it all is childishly simple, yet the method of analytic geometry is so powerful that the very ordinary boys of seventeen can use it to prove results which would have baffled the greatest of Greek geometers--Euclid, Archimedes, and Apollonius.

---E.T. Bell, in Men of Mathematics

Answer 10

The original article containing proof of the Radon-Nikodým theorem has about 50 pages. John von Neumann proved it by little trick and Riesz representation theorem (that one about Hilbert space functionals) in three lines.

Answer 11

Lomonosov's 1973 proof that every compact operator $T$ has a hyperinvariant subspace (i.e., a subspace that is invariant for every operator that commutes with $T$) was much simpler than proofs existing then that every compact operator has an invariant subspace. See https://en.wikipedia.org/wiki/Invariant_subspace_problem. However, Wikipedia fails to mention that Lomonosov's proof was further simplified to replace the Schauder fixed point theorem by the spectral radius formula $\lim \|T^n\|^{1/n}$ (see e.g. Rudin's Functional Analysis), so that Lomonosov's theorem is taught (or assigned as an exercise) in classes in which the spectral radius formula is introduced.

Answer 12

The Van der Waerden conjecture for the permanents was stated in 1926 and remained open for over 50 years. It was considered "one of the famous open problems in combinatorial theory" (in van Lint's words). It turned out to be an easy consequence of the Alexandrov-Fenchel inequality from late 1930s. See this article for the history and basically the whole proof.

Answer 13

The associativity of the group law on an elliptic curve can be proved by a tedious and unenlightening calculation, but it can be derived pretty quickly once you have developed some curve theory (Riemann-Roch, etc.).

Answer 14

I've lately have found myself admiring the proof of the fundamental theorem of algebra using linear algebra, due to H. Derksen, American Mathematical Monthly, 110 (7) (2003), 620–623.

He proves directly that linear operators on finite dimensional complex vector spaces admit eigenvectors, and deduces the fundamental theorem from this. I like the argument because it is completely elementary: All it uses is that odd dimensional polynomials over the reals have a real root, and that complex numbers have complex square roots (in particular, it avoids the machinery of complex or real analysis, and can even be presented without any reference to determinants). Moreover, the proof gives the result that $R(\sqrt{-1})$ is algebraically closed whenever $R$ is a real closed field, which before I had only seen proved using Galois theory or analogous, relatively sophisticated techniques.

Derksen's proof is a nice induction where first odd dimensions are taken care of, then dimensions of the form 4k+2, then of the form 8k+4, etc.

Answer 15

Quadratic Reciprocity. Gauss' original proof is entirely elementary, but far from easy (I think I recall reading that Gauss himself said he spent more than a year tormented trying to find a proof).

There are many modern proofs. Using algebraic number theory and in particular the Kronecker-Weber theorem, we now have a conceptual proof, literally 4-5 lines in length.

Answer 16

It was about 20 years ago that I have learned it, so I migth not remember things correctly. However, I think Stoke's theorem was considered non-trivial originally. But using differential forms it can be proved by a one line argument.

Answer 17

I have two entries, although there is a wealth of elementary geometric examples similar to #1 and several alternative proofs of #2.

(1) Pascal's theorem: If H is hexagon whose vertices lie on a conic section Q then the points $A,B,C$ where the pairs of the opposite sides intersect are collinear.

I think that the first proof used Menelaus's criterion of collinearity and required a figure, as well as keeping track of various points and lines in order to use Menelaus's theorem. A beautiful short proof based on Bezout's theorem is in vol 1 of Shafarevich's "Algebraic geometry":

If the sides of H are given by the vanishing of linear forms $l_1,l_2,l_3$ and $m_1,m_2,m_3$ in homogeneous projective coordinates, where $l_i$ is the opposite of $m_i$, then $l_1 l_2 l_3 - \lambda m_1 m_2 m_3$ vanishes at the vertices of $H$ and one more arbitrarily chosen point on Q, for a suitable $\lambda$; since $6+1>2\cdot 3$, by Bezout, the cubic is reducible, so it consists of Q and another component, which is a line passing through $A,B,C$.

(2) Isoperimetric inequality: If a simple closed curve in the plane has length $L$ and bounds the region of area $A$ then $L^2-4\pi A\geq 0$ (with equality only in the case of a circle).

The first proof of the isoperimetric property of the circle was attempted by Jacob Steiner using the "four rod" method (related to "Steiner's symmetrization"), but it proceeded under the assumption that the minimum is attained and so was incomplete. Weierstrass gave the first rigorous proof based on variational calculus and it was painstaking. Adolf Hurwitz found an essentially one-line proof (after all the notation has been set up) that is reproduced in "Einfuhrung in die Differentialgeometrie" by Wilhelm Blaschke (p.33 of 1950 edition):

$$ L^2-4\pi A = 2\pi^2 \sum_2^{\infty} \frac{a_k^2+{a_k}^{\prime 2}}{k^2-1}\geq 0. $$

Here $a_k$ and $a_k^{\prime}$ are the Fourier coefficients of the position vector of the curve w.r.t. unit tangent vector.

Answer 18

Don't know for sure if this example qualifies, but it certainly is a hard problem which becomes trivial from the right point of view. (I learned this from Martin Gardner, proper credits might be researched if necessary).

Problem: three circles in the plane, no two with the same radius, pairwise disjoint. For each pair of circles, there are four straight lines tangent to both; take the two which leave both circles on the same side; they intersect at a point. Repeat the construction for each pair of circles. We get three points: prove that they are collinear.

You may want to think a little about the problem; can be solved both by plane or analytic geometry, with some effort. Not too difficult, but not a one-liner.

Now consider the following solution: add a dimension. You have three spheres, and if you section them through their centers with a plane you get the original three circles. Consider the cones determined by each couple of spheres; the section is the couple of tangent lines seen above, and the tips of the cones are the three points in the problem. Now take two planes touching the three spheres from above and from below....

Answer 19

Short-time existence for the Ricci flow was initially proved by Hamilton by a long and involved argument using the Nash-Moser implicit function theorem. Then Dennis DeTurck found a nice trick which showed that the Ricci flow is equivalent to a standard parabolic problem.

Answer 20

The theorem that the left-hand trefoil knot is not isotopic to the right-hand trefoil knot was originally proved (by Max Dehn in 1914), by a rather grueling analysis of the automorphisms of the trefoil knot group. The theorem became much easier with the advent of the Jones polynomial in the 1980s.

Answer 21

Here is another example from functional analysis. There are several basic results, such as the principle of uniform boundedness and the open mapping theorem, that follow easily from the Baire category theorem. However, I recall from reading Halmos's autobiography I Want to Be a Mathematician that the original proofs of these results were rather complicated and the theorems were considered to be significant achievements.

Answer 22

I was told by my (graduate school) teacher of functional analysis that originally the complex case of the Hahn-Banach theorem was considered a major open problem. It was eventually shown to be such a simple consequence of the real case, that now, no one knows who came up with the trick.

Answer 23

I believe Schur's Lemma was originally considered difficult (after all it did get named). However it is now a one-line proof in an undergraduate course.

I suspect Schur was interested in finite dimensional representations of finite dimensional algebras over the complex numbers. Then the lemma is that the endomorphism ring of an irreducible representation is the complex numbers. Don't ask me why this was considered difficult. The definition of an abstract algebra was not published until after Molien and Wedderburn's results so I can see the statement would have been convoluted.

Answer 24

Bezout's theorem - You can prove it with grueling arguments about resultants, or you can use cohomological machinery to do it in one line.

Answer 25

The most recent and astonishing one is Zeev Dvir's proof on Kakeya conjecture over finite field, it is surprisingly elementary and beautiful. It probably tells us sometimes it is just a change of thoughts we need to prove hard theorems.

https://terrytao.wordpress.com/2008/03/24/dvirs-proof-of-the-finite-field-kakeya-conjecture/

Another one is the elementary proof of the Gaussian correlation inequality, which is so simple that it has been a while for people to believe. Later people wrote another paper to explain it.

https://arxiv.org/abs/1512.08776

Answer 26

Hindman's theorem : if I remember correctly, the original proof was elementary but very long and complicated; whereas a proof using an idempotent ultrafilter can be explained in less than a page.

Still with ultrafilters, there's also Tychonoff's theorem : the original proofs, either Tychonoff's with complete accumulation points, or the one with the Alexander subbase theorem are somewhat technical and require some imagination.

The proof using ultrafilters is extremely straightforward and anyone who has learned about ultrafilters can find it with little to no imagination. It also has the advantage of showing that if you work with Hausdorff spaces, you don't need the full axiom of choice, whereas the Alexander subbase theorem uses Zorn's lemma indistinctly.

Answer 27

Gelfand–Mazur theorem. "A complex Banach algebra, with unit 1, in which every nonzero element is invertible, is isometrically isomorphic to the complex numbers."

The proof is the one everybody knows.

Answer 28

The alternating sign matrix conjecture was first proved by Doron Zeilberger; the proof was enormously computational. Later, Greg Kuperberg gave a much shorter proof using results from statistical mechanics. Kuperberg's proof is still not trivial, but it is more conceptual.

(It's worth mentioning that very recently, Fischer and Konvalinka have announced a bijective proof of the same theorem, which is pleasing to a combinatorialist, but far from trivial, and hence probably not an answer to the question.)

Answer 29

The incompressibility method based on Kolmogorov complexity is described in "Kolmogorov Incompressibility Method in Formal Proofs A Critical Survey", V Megalooikonomou - 1997, as often being more elegant, intuitive, simpler and shorter than counting arguments, or the probabilistic method, in areas such as lower bounds, average case complexity, random graphs or pumping lemmas in formal language theory.

Answer 30

How about de Branges' proof of the Bieberbach conjecture? My understanding is that his original proof ran to 100+ pages, but others soon found a way of bringing it down to considerably less than that - maybe not a quick proof, but a relatively quick proof.