Past open problems with sudden and easy-to-understand solutions

What are some examples of mathematical facts that had once been open problems for a significant amount of time and thought hard or unsolvable by contemporary methods, but were then unexpectedly solved thanks to some out-of-the-box flash of genius, and the proof is actually short (say, one page or so) and uses elementary mathematics only?

• Not elementary, but both the statement and the proof of Nash-Kuiper were extremely unexpected. Dec 23 '15 at 19:13
• Would a new simple proof to an establised "hard" theorem count? Dec 23 '15 at 19:22
• In which case, see here mathoverflow.net/questions/24913/quick-proofs-of-hard-theorems Dec 23 '15 at 19:28
• Consider the Collatz' conjencture. It has been open for decades, and yet it has a very simple solution. We just don't know what the solution is. Dec 27 '15 at 13:09
• Not math and not an actual proof, but gaze tracking: eyes or face? Considered unsolvable, solved by a 12 year old. rsbl.royalsocietypublishing.org/content/9/1/20120850 Dec 27 '15 at 23:52

The integral of $\sec x$ stumped mathematicians in the mid-seventeenth century for quite a while until, in a flash of insight, Isaac Barrow showed that the following can be done:

$$\int \sec x \,\mathrm{d}x= \int \frac{1}{\cos x} \, \mathrm{d}x=\int \frac{ \cos x}{\cos^2 x} \, \mathrm{d}x=\int \frac{ \cos x}{1-\sin^2 x} \, \mathrm{d}x.$$

Using $u$-substitution and letting $u=\sin x$, the integral transforms to

$$\int \frac{1}{1-u^2} \, \mathrm{d}u,$$

which is easily evaluated by partial fractions.

• This is great! Showing this in an integral calculus course would improve the students' self confidence for sure.
– Dahn
Dec 24 '15 at 15:11
• The way I was shown how to integrate $\sec x$ was to multiply by $\tfrac{\sec x + \tan x}{\sec x + \tan x}$ and then substitute $u = \sec x + \tan x$. This method has less hindsight involved. Dec 24 '15 at 23:20
• @JimmyK4542 That is not a method---just a disguised form of checking the integral is $\ln | \sec x + \tan x |$ by differentiating. I taught it with substitution and partial fractions. Dec 25 '15 at 1:10
• The actual history of this result is somewhat different. The formula for the integral (which is needed for construction of Mercator's projection maps) was discovered in a numerical comparison of two tables of numbers, and published in 1645. James Gregory found a very complicated proof in 1668, and Barrow a simpler one in 1670. All this was before the Fundamental Theorem of Calculus: once you have that, it's completely elementary to verify by differentiating. See e.g. these notes. Dec 25 '15 at 5:29
• The Tangent Half-Angle Substitution solves this with ease. Dec 25 '15 at 11:10

Theorem: transcendental numbers exist and there are (uncountably) infinitely many of them.

The existence of transcendental numbers had been conjectured for over 100 years before Liouville constructed one in 1844. Other numbers such as $e$ were shown to be transcendental one by one. Cantor was able to prove their existence with ease:

Proof: the algebraic numbers are countable and the real numbers are uncountable.

• Though, in fairness to Liouville, in 1844 the concept of what exactly the "real numbers" were was not as concrete as it was later (I don't have an exact cite but Dedekind says he first started thinking about the continuity of $\mathbb{R}$ in 1858).
– Owen
Dec 23 '15 at 22:34
• It should be noted that once you prove the existence of one transcendental, you can prove the existence of infinite transcendentals easily ($e$, $e+1$, $e+2$, etc...). I suppose you could say the existence of infinite algebraically independent transcendental numbers instead. Dec 24 '15 at 1:03
• @PyRulez: Just say that there are uncountably many transcendental numbers to rule out simple ways of obtaining them from one. Even more, there are uncountably many uncomputable transcendental numbers! Dec 24 '15 at 5:46
• @user21820 The problem is, before Cantor came along, uncountable v.s. countable did not make sense. (Liouville would have been like "well, I can't count either.") Once you are able to distinguish countable and uncountable, the problem is basically solved. Dec 24 '15 at 15:21
• @PyRulez: Ah I see what you meant. You want to make a statement that does not involve cardinality but is difficult to solve without. Well, I guess algebraic independence is one historically earlier concept that works. Dec 24 '15 at 15:39

The $\mathcal{AKS}$ (Agrawal, Kayal, Saxena) algorithm, which proves that we can answer if a number is prime or not in polynomial time. It has been found in 2003 and is said "reachable by ordinary man" in reason of the background it needs to be understood. More info here (wiki) and here (the paper).

• I'm pretty sure the original paper is from 2002 not 2003. Anyway, it can be understood by a master student in computer science without to many troubles. Dec 24 '15 at 20:50
• @Bakuriu : I hesitated too (2003 was perhaps the date of the acceptation of this paper), but in the paper they cite their article by [AKS03] and they date it 2003, so I simply take 2003 as the official date. Dec 24 '15 at 21:35

It is not completely elementary, but Abel's proof of the Abel-Ruffini theorem is quite short, 6 pages, and can with a bit of introduction be understood by someone without a degree in mathematics. The Abel-Ruffini theorem states that there is no general solution in radicals to a degree 5 or higher polynomial equation.

The Abel-Ruffini theorem had been open for over two hundred years and was one of the central problems in mathematics of that time, akin to the Riemann Hypothesis now. For degree 2, a formula had been known since 2000 BC to the Babylonians. For degree 3 and 4, formulas had been discovered 200 years earlier. The search for a formula of degree 5 had been long in progress.

Euler has stated the theorem but never managed to prove it, and it took Gauss many years to prove this theorem, and right now we have over 200 different proofs, some of which could be explained in an hour long lecture.

• Or on a T-shirt... Dec 25 '15 at 18:55
• I have that T-shirt. Dec 26 '15 at 7:05
• @Kevin T-shirt with a whole proof of QR? Can you give a link? Dec 26 '15 at 22:44
• @DamianReding: (a) It's more of a proof sketch than an actual proof and (b) I only got it by participating in a specific summer program in high school, so (c) I don't know where you can buy it. Dec 26 '15 at 22:47
• @Kevin, can you tell which proof of QR is printed on the T-shirt. Dec 27 '15 at 9:47

Some people thought for hundreds of years that the Euclidean parallel postulate could be proven from the other four axioms of Euclidean geometry. Giovanni Saccheri even wrote a book about it – Euclides ab omni naevo vindicatus (Euclid Freed of Every Flaw).

However, with the discovery of hyperbolic geometry in 1826 by Nikolai Lobachevsky, the conjecture was suddenly disproven, and hyperbolic geometry is not very hard to understand.

The problem was one of the most important problems in geometry in that time.

• I think you can drop the "one of." This would be the cultural equivalent of logic or algebra being disproven today. Dec 24 '15 at 0:02
• I might change "People thought..." to "Some people thought...", because others (most?) thought the opposite throughout that time period. Equivalently, you could say today that "[some] people think they have a proof of $P = NP$", but that really gives the wrong impression. For example, in 1388, "Khayyám refutes the previous attempts by other Greek and Persian mathematicians to prove the proposition." -- en.wikipedia.org/wiki/Omar_Khayyam#Theory_of_parallels Dec 24 '15 at 0:23

The Quillen-Suslin theorem, which states that any f.g. projective module over a polynomial ring $k[X_1, \dots, X_n]$ is free, was originally an open conjecture of Serre. Quillen even won a Fields medal in part for his part in the proof. Later on, Vaserstein gave a proof that was short and simple enough to fit in as an appendix to Lang's "Algebra," a standard graduate-level text.

Algebraic solution of the cubic equation was a major open problem for millenia, counting the time from the Greeks or from much earlier solutions of quadratic equations.

The formula can be derived in a few lines, using modern notation.

This is the largest ratio of (age of the problem)/(length of solution) I can think of from mathematical history.

Another large ratio is Euler's sum of powers conjecture where a complete solution to a problem raised in 1769 can be written in $22$ characters: $$27^5 + 84^5 + 110^5 + 133^5 = 144^5$$

Perhaps this example qualifies.

Victor Klee posed the question of how many vertex "guards" are sometimes necessary and always sufficient to see the interior of a simple polygon in the plane. This problem is now sometimes called the art gallery problem. V. Chvatal found a nice proof relatively soon after the problem was publicized but a surprisingly simple and appealing proof was found by Steve Fisk a few years later. Klee's original problem has been generalized in many ways and has led to a huge literature including new methods to solve unrelated problems, and related problems that are yet to be resolved.

https://en.wikipedia.org/wiki/Art_gallery_problem

• Fisk's proof is based on the fact that a simple plane polygon can be triangulated using diagonals between existing vertices. The fact that this is possible to not that hard (though there were incorrect proofs in the past) but an "easier" proof using the notion of an ear of a polygon was developed by Gary Meisters, who died about a month ago. Meisters' showed that polygons with 4 or more vertices have at least two ears made it possible to use induction to prove that simple polygons can be triangulated: legacy.com/obituaries/coloradoan/… Dec 29 '15 at 19:54

For a long while the Stanley-Wilf conjecture was one of the most prominent open problems in enumerative combinatorics, until it was resolved with an elementary one-page proof by Marcus and Tardos.

A permutation $$\sigma$$ on $$\{1, \ldots, n\}$$ is said to contain a permutation $$\pi$$ on $$\{1, \ldots, k\}$$ if there exist integers $$1 \le i_1< \ldots< i_k \leq n$$ such that $$\sigma(i_a) <\sigma(i_b)$$ if and only if $$\pi(a) < \pi(b)$$. If $$\sigma$$ does not contain $$\pi$$, we say that $$\sigma$$ avoids $$\pi$$. Let $$S_n(\pi)$$ be the number of permutations on $$\{1, \ldots, n\}$$ that avoid $$\pi$$. The Stanley-Wilf conjecture is that for all permutations $$\pi$$ there exists a constant $$c_\pi$$ such that, for all $$n$$, $$S_n(\pi) \le c_\pi^n$$.

Marcus and Tardos proved the related Furedi-Hajnal conjecture with a simple but very clever pigeonhole argument. The Furedi-Hajnal conjecture was already known to imply Stanley-Wilf: the one-paragraph argument by Klazar can also be found in the Marcus-Tardos paper.

Chevalley-Warning theorem. You can see short historical note on it here.

• Please summarize for us click-averse. Jan 1 '16 at 1:48

The proof of Apéry's theorem is elementary in the sense of requiring only very old techniques (A Proof thet Euler Missed).

The imposibility of the duplication of the cube and the trisection of an angle are easy consequences of elementary field theory.

• field theory is not (considered) elementary! Dec 31 '15 at 22:01

Hilbert's basis theorem become a generalized solution to a problem that a lot of mathematicians had struggled with for a long time:

If $R$ is a Noetherian ring, a ring where all ideals are finitely generated, then so is $R[X]$, the ring of polynomials over $X$ with coefficients in $R$.

This is an incomplete answer. There is a problem somehow linked to Erdos that goes something like this: a set of points has that a line paso get through 2 distinct points in the set also passed through a third distinct one; prove that the set is infinite. (Something like that...) anyway there was a really long solution to this problem and soon after a 4-liner using the external principle. Something like 'find the line and point with the shortest distance', the a proof by contradiction since in any finite set there would be a (many) minimum(/a).

• Please do the research to make this into a complete answer. Dec 26 '15 at 2:41
• You are thinking of Kelly's proof of the Sylvester-Gallai theorem.
– bof
Dec 28 '15 at 8:23
• The original question was asked by Sylvester and years later Erdos asked the question in the dual form - the problem can be thought of as being in the projective plane. Tibor Gallai provided an answer and later Kelly a very elegant metrical proof. However, there was an even simpler proof buried in Deutsche Mathematik, published by the Nazis. This proof by Eberhard Melchior was a combinatorial proof more in keeping with Sylvester's original setting. More details are here: en.wikipedia.org/wiki/Sylvester%E2%80%93Gallai_theorem Dec 29 '15 at 14:43

Our complex analysis professor told us that huge amounts of literature was written studying analytic functions that are bounded. Then came https://en.wikipedia.org/wiki/Liouville%27s_theorem_(complex_analysis) like a hammer. Super easy proof, (according to my professor) very unexpected result at the time.

I haven't found a verification of this anecdote, but fun story in any case.

From "Polygonal Rooms Not Illuminable from Every Point" by George W. Tokarsky, The American Mathematical Monthly Vol. 102, No. 10 (Dec., 1995), pp. 867-879:

Imagine two people in a dark room with many turns and cul-de-sacs. Assuming that the walls, floors and ceilings are constructed of reflective material, can one person strike a match and be seen by the other after repeated reflections, no matter where the two are located?

This problem has been attributed to Ernst Strauss in the early 1950's, and has remained open for over forty years. It was first published by Victor Klee in 1969. [...]

In this article, we will settle the above problem in the negative. We will as well give elementary techniques for constructing rooms, both in the plane and in three-space, which are not illuminable from every point.

The proof that if $f$ has absolutely convergent Fourier series and is never zero, then its inverse $\frac{1}{f}$ also has an absolutely convergent Fourier series.

Wiener gave a proof in 1932. Gelfand (1941) later developed the theory of Banach algebras to provide an elementary proof.

Here is the first information-theoretic incompleteness theorem. Consider an N-bit formal axiomatic system. There is a computer program of size N which does not halt, but one cannot prove this within the formal axiomatic system. On the other hand, N bits of axioms can permit one to deduce precisely which programs of size less than N halt and which ones do not. Here are two different N-bit axioms which do this. If God tells one how many different programs of size less than N halt, this can be expressed as an N-bit base-two numeral, and from it one could eventually deduce which of these programs halt and which do not. An alternative divine revelation would be knowing that program of size less than N which takes longest to halt. (In the current context, programs have all input contained within them.)

The proof of this closely resembles G. G. Berry's paradox of the first natural number which cannot be named in less than a billion words,'' published by Russell at the turn of the century (Russell, 1967). The version of Berry's paradox that will do the trick isthat object having the shortest proof that its algorithmic information content is greater than a billion bits.'' More precisely, that object having the shortest proof within the following formal axiomatic system that its information content is greater than the information content of the formal axiomatic system: ...,'' where the dots are to be filled in with a complete description of the formal axiomatic system in question.

1. A universal approach and proof to all self-referential paradoxes, from Cantor to Goedel and Turing, through the work on Cartesian Closed categories of Lawvere, Eilenberg and others on category theory.

Following F. William Lawvere, we show that many self-referential paradoxes, incompleteness theorems and fixed point theorems fall out of the same simple scheme. We demonstrate these similarities by showing how this simple scheme encompasses the semantic paradoxes, and how they arise as diagonal arguments and fixed point theorems in logic, computability theory, complexity theory and formal language theory.

Theorem 1 (Generalized NFL theorem). Let H be an arbitrary (randomized or deterministic) search heuristic for functions $f \in F > \subset F_{A,B}$ where $F$ is closed under permutations. Let $r(H)$ be the average (under the uniform distribution on $F$) of the expected runtimes of $H$ on $F$. Then $r(H)$ is a value independent of $H$, i.e., $r(H)$ is the same for all $H$.

[..]The generalized NFL theorem is by no means surprising. If a class of functions does not change by any permutation on the input space, there is no structure which can be used for search. Hence, all search strategies show the same behavior.

(there is another reference for a simple proof of NFL that also displays its elementary character, but cannot seem to find it at this point)