Quick proofs of hard theorems - MathOverflow

Quick proofs of hard theorems

2010-05-16T19:11:01Z

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 by Paul Siegel for Quick proofs of hard theorems

2010-05-16T19:11:47Z

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 by Henno Brandsma for Quick proofs of hard theorems

2010-05-16T19:24:12Z

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 by Bill Johnson for Quick proofs of hard theorems

2010-05-16T19:25:59Z

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 http://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 by Igor Pak for Quick proofs of hard theorems

2010-05-16T19:34:22Z

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 by Qiaochu Yuan for Quick proofs of hard theorems

2010-05-16T19:40:34Z

People say that Hilbert's basis theorem was once proven using pages of explicit computation with polynomials, but now everyone learns Hilbert's beautiful, if non-constructive, proof instead. Regrettably I have no idea what the "old proof" looks like.

Answer by Bruce Westbury for Quick proofs of hard theorems

2010-05-16T20:30:21Z

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 by Regenbogen for Quick proofs of hard theorems

2010-05-16T20:32:06Z

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 by Steve D for Quick proofs of hard theorems

2010-05-16T22:14:29Z

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 SL(2,q) such that x, y, and xy have orders 2a, 2b, and 2c, and then the images of x,y,xy in PSL(2,q) will have orders a, b, and c as required.

An element of SL(2,q) with distinct eigenvalues is diagonalizable in 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 F_q with multiplicative orders 2a and 2b, and let x = [ [u, 1], [0, u^-1] ] and y = [ [v, 0], [t, v^-1] ] be in 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^-1v^-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 SL(2,q) with order 2c, and then xy will have order 2c.

Answer by maks for Quick proofs of hard theorems

2010-05-16T22:38:04Z

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 by Andres Caicedo for Quick proofs of hard theorems

2010-05-16T22:57:58Z

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 by Timothy Chow for Quick proofs of hard theorems

2010-05-16T23:44:05Z

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 by John Stillwell for Quick proofs of hard theorems

2010-05-16T23:45:36Z

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 by Steven Gubkin for Quick proofs of hard theorems

2010-05-17T01:13:39Z

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 by danseetea for Quick proofs of hard theorems

2010-05-17T04:16:38Z

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 by Gerry Myerson for Quick proofs of hard theorems

2010-05-17T04:34:54Z

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.

Answer by teil for Quick proofs of hard theorems

2010-05-17T05:36:38Z

The fundamental theorem of calculus; all the long and difficult proofs of Eudoxus and Archimedes became clear and simple. Similarly with co-ordinate geometry.

Answer by teil for Quick proofs of hard theorems

2010-05-17T05:46:09Z

Power series. Both conceptually and computationally, in the 17th century they replaced a multitude of ad-hoc methods that had been used for millennia.

Answer by James for Quick proofs of hard theorems

2010-05-17T13:56:21Z

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 by Yiftach Barnea for Quick proofs of hard theorems

2010-05-17T23:02:56Z

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 by Victor Protsak for Quick proofs of hard theorems

2010-05-18T00:34:03Z

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 by Pierre-Yves Gaillard for Quick proofs of hard theorems

2010-05-18T04:40:58Z

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 by Timothy Chow for Quick proofs of hard theorems

2010-05-18T15:19:12Z

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 by aginensky for Quick proofs of hard theorems

2010-05-21T02:25:01Z

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 by Roy Maclean for Quick proofs of hard theorems

2010-05-30T14:03:08Z

The incompressibility method based on Kolmogorov complexity is desribed 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 by Franklin for Quick proofs of hard theorems

2010-07-11T01:49:31Z

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 by Piero D'Ancona for Quick proofs of hard theorems

2010-07-11T09:12:42Z

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 by BlueRaja for Quick proofs of hard theorems

2010-07-11T09:59:55Z

Most of the problems tackled in introductory calculus courses (tangent lines of and areas under basic curves, volumes and areas of solids of revolution, etc) had to be solved on a case-by-case basis, with some pretty complicated and ingenious proofs; now any undergraduate can solve them in a few lines by rote methodology.

Answer by Gerald Edgar for Quick proofs of hard theorems

2010-07-11T12:19:37Z

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 by Alex Bartel for Quick proofs of hard theorems

2010-10-05T09:16:15Z

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 by robot for Quick proofs of hard theorems

2011-01-24T22:44:05Z

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.