Examples of famous problems resolved easily

Have there been examples of seemingly long standing hard problems, answered quite easily possibly with tools existing at the time the problems were made? More modern examples would be nice. An example could be Hilbert's basis theorem. Another could be Dwork's p-adic technique for rationality of zeta functions from algebraic varieties.

-
Just a hunch, but the first place I'd check for modern examples would be Erdos. –  David H Oct 18 '13 at 17:40
@DavidH He is famous but have you got any examples of his work? –  Turbo Oct 18 '13 at 18:16
Are you looking for "easy" proof, or "elementary" proof? For example, would Erdos-Selberg's elementary proof of prime number theorem count? –  user27126 Oct 19 '13 at 9:07
Dear JAS, I'm not sure what you mean by "resolved easily". As an example, Dwork's proof is a masterpiece of brilliant argument (in my view), combining a bunch of unlikely ideas, including compact operator techniques in a $p$-adic context, and Borel's criterion for a power series to be a rational function. If you mean "without constructing an enormous new machine", then this applies to many, indeed most, problems, I would say. Regards, –  Matt E Oct 19 '13 at 12:15
@Sanchez Yes that would count. –  Turbo Oct 19 '13 at 19:21

I'm sure there are loads. One that comes to mind is the Seven Bridges of Konisberg problem.

http://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg

Basically, the problem asked: is there a path which you can walk such that you cross every bridge once and only once. (you can't do things like walk halfway onto a bridge and walk back).

It was kinda known, well... conjectured, that there was no solution to this problem. Basically because no one found a solution to this problem and no one could prove why or why not.

Until Euler of course. As usual, it is always Euler who saves the day. He showed that there was no answer to this problem, as in, it was impossible to construct a path such that you cross every bridge just once.

The justification ended up being really simple: First, you have to put the problem in terms of the areas in town as opposed to the bridges. From the illustration, you can see that you can split the town into 4; the top, the bottom, the right and the center. Also, you have to realize that in order not to reuse a bridge, every region in town must have an even number of bridges (an entry bridge and an exit bridge). If you don't have an even number of bridges, you get stuck in one of the regions (As in, if there's just 1 bridge, you use that bridge and then get stuck. If there are 3 bridges, you go in through one, go out from the second, and then get stuck upon using the third). So, if you look closely, the regions have all odd numbers of bridges connecting them. (3 connecting to the top region, 5 connecting to the center, 3 connecting to the right and 3 connecting to the bottom)

Therefore, from this you get the idea of eulerian cycles and from there loads of properties of graphs and then graph theory was born. And if it were not for graph theory we'd be lost when it comes to the telephone network and the internet. So, yeah, long-standing problem with a simple solution and with even more long-standing benefits.

Acknowledgment: About the problem, another possibility would be if you had only 2 regions with an odd number of bridges connecting them, and all the rest must have an even number of bridges. The logic behind this would be that one of those two regions would be your "starting" point and the other would be you "ending" point or finish line. In this case, you would get an Eulerian path instead of a cycle

-
On the topic of Euler, I've always been fond of his approach to solving the [Basel Problem]. –  David H Oct 18 '13 at 15:38
Yup, who would've thought that the answer would have $\pi$ in it? That man was a genius –  TheSeamau5 Oct 18 '13 at 15:39
Interestingly, it seems to be the same if you are paddling a boat too :) Is it the same problem that way? –  Greg Hill Oct 18 '13 at 16:21
How famous was the Koenigsberg bridges problem before Euler solved it? Is there any reason to believe that any mathematician had considered it? –  bof Oct 19 '13 at 2:42
A typo that goes through the post: Euler did not show that "there is no answer to the question", he proved that the answer was "No". –  AD. Dec 8 '13 at 9:24

I don't know how old or how famous Tarski's Unique Square Root Problem was when the young László Lovász solved it. Certainly Tarski was very famous, and I'm sure he thought the problem was quite hard. Lovász's solution, while brilliant, was surely much shorter and simpler than Tarski or anyone had expected.

Tarski's Problem. If two finite structures (groups, rings, lattices, graphs, whatever) have isomorphic squares, must they be isomorphic? (The square of a structure $A$ is the direct product $A\times A$.)

Lovász solved Tarski's problem in the affirmative with a clever counting argument, which I will try to reproduce since I'm having trouble finding a good reference. I assume that all structures are finite structures of a fixed type, e.g., finite groups. Let $A,B$ be two structures such that $A\times A\cong B\times B$.

For any structures $X$ and $Y$, let $h(X,Y)$ be the number of homomorphisms, and $i(X,Y)$ the number of injective homomorphisms, from $X$ to $Y$.

Claim 1. For any structure $X$, we have $h(X,A)=h(X,B)$.

Proof. $h(X,A)^2=h(X,A^2)=h(X,B^2)=h(X,B)^2$, so $h(X,A)=h(X,B)$.

Claim 2. For any structure $X$, we have $i(X,A)=i(X,B)$.

Waving of Hands. We can use the inclusion-inclusion principle to express $i(X,A)$ in terms of values of $h(Y,A)$ where $Y$ ranges over quotients of $X$. (I think I could write a correct proof of this, but it would take some laborious typing. Anyway, it's obvious, isn't it?) Since $h(Y,A)=h(Y,B)$ by Claim 1, it follows that $i(X,A)=i(X,B)$.

Now we have $i(A,B)=i(B,B)\ge1$ and $i(B,A)=i(A,A)\ge1$, i.e., we have injective homomorphisms from $A$ to $B$ and from $B$ to $A$. Since the structures are finite, it follows from this that they are isomorphic.

I learned this argument by word of mouth, attributed to Lovász, several decades ago. This paper (which I haven't read) seems to be the source: L. Lovász, Operations with structures, Acta Math. Acad. Sci. Hungar. 18 (1967) 321-328; see Theorem 4.1 on p. 327, which appears to be a generalized version of the Unique Square Root Theorem.

-
Do you have a reference for this? –  Turbo Oct 19 '13 at 8:36
This is the list. cs.elte.hu/~lovasz/publications.html I am unable to locate the paper in your mind. Could you point me from the list? –  Turbo Oct 19 '13 at 9:35
I do not know. However looking at it, I am thinking why has not such generality been used in Graph Theory? After all graphs are finite structures and hence any result here should carry over to graphs.... right? –  Turbo Oct 19 '13 at 10:17
Do you know what an infinite vector of type $\omega$ mean in 3.6? Could you explain where should I look for an introduction to the paper? –  Turbo Oct 19 '13 at 10:20
@J.A. The paper cs.elte.hu/~lovasz/scans/LocFinCategories.pdf from the list seems to be the right one. –  Johannes Hahn Mar 14 at 23:56

I like the establishment of the independence of Euclid's 5th postulate from the others for winner in this category. It's arguably the first long-standing problem of pure mathematics, and maybe the oldest example we have of a mathematical community posing a problem to itself and investigating it collaboratively. Perhaps some leniency is required here as to how accessible the "methods" by which it was eventually resolved really would have been to the Greeks, but in the spirit of positive historico-imaginationism I'm going to say they could have done it. I have no doubt Archimedes could have accomplished much of the necessary editing and improvements in rigor to Euclid's Elements, had been of a mindset and motivation to do so. The harder ingredient is a brilliant mathematician with enough childish instinct to go the distance and say "I don't care if Euclid's axioms are self-evident truths of your world. This is MY world where dragons are real, my sword is magic, and parallel lines can intersect each other." Who knows. Had the Fates granted Plato a star-student interested in mathematics (instead of the metaphysician he got in Aristotle)....

-
Ehhhhh, Euclid was the gold standard of mathematical rigor (no, scratch that, of all intellectual rigor in any field) for centuries, so I doubt that Archimedes or any other Greek-era mathematicians were at all likely to even realize that such editing/improvements were necessary. Rigor as we currently understand it is such a recently-developed concept that even Euler's original works look almost laughably imprecise by our standards. That said, maaaaaaybe the Greeks could have realized that Euclid's first four postulates apply equally well to poles and great circles on spherical surfaces... –  Kyle Strand Oct 18 '13 at 21:45
@KyleStrand Absolutely, Euclid was the gold standard of rigor, which is why it received so much attention. Virtually every ancient copy we have of Elements originally belonged to various later mathematicians for their personal study, as we can tell from annotations and commentaries recorded in the margins. It's a myth that Euclid laid a rigorously golden egg and that was that for 2000 years. –  David H Oct 18 '13 at 22:13
+1 for "positive historico-imaginationism". –  Marnix Klooster Oct 25 '13 at 15:42

Steiner-Lehmus theorem is a good one: Any triangle that has two equal angle bisectors (each measured from a vertex to the opposite side) is isosceles.

To quote from "Geometry Revisited", by Coxeter and Greitzer: This theorem was sent to the great Swiss geometer Jacob Steiner in 1840 by C.L. Lehmus (whose name would otherwise have been forgotten long ago) with a request for a pure geometrical proof. Steiner gave a fairly complicated proof which inspired many other people to look for simpler methods. Papers on the Steiner-Lehmus theorem appeared in various journals in 1842, 1844, 1848, almost every year from 1854 till 1864, and with a good deal of regularity during the next hundred years.

It turns out to be a straightforward proof when converted to the contrapositive form, devised by two English engineers, Gilbert and Macdonnell, in 1963, showing that (see first diagram below) if in $\Delta ABC,\ B \neq C,$ then $BM \neq CN.$ The proof is given in Geometry Revisited, this is just an outline, but it rests on an easy lemma that if a triangle has two different angles, the smaller angle has the longer internal bisector.

One direct proof involves solving a complicated algebraic equation based on the formula for the length of a triangle's angular bisector. See diagram below.

To summarize, the theorem had a simple proof available using methods of the time (19th century), but was seen as difficult all the way up to well into the 20th century!

-
What application are you using? It looks great. –  par Oct 18 '13 at 17:33
@par It's GeoGebra. –  grgarside Oct 18 '13 at 18:11
@grgarside thank you –  par Oct 18 '13 at 19:32
@par Yes - GeoGebra. Free, easy to use, great annotation capability. –  Greg Hill Oct 18 '13 at 20:23
@GregHill Why did you capture the entire screen rather than the illustration only? –  user93957 Nov 1 '13 at 22:37

From least likely to fit your criteria to most, in my opinion:

Halting problem
Special Cases of Fermats last theorem (n = 3, n = 4...)
These problems weren't around for very long, but their solutions are fairly easy to understand after you've seen them.

Polynomial time primality
This problem has been around forever, but the solution is only "relatively" easy; as in, it's simple for those who study number theory algorithms. It's not introductory material though. It is fairly modern though.

Sum of inverse squares
$\sum_{k = 0}^{\infty} {\frac 1 {k^2}} = \text{???}$

Definitely a winner here. It had been known for a long time that the sum converged to something finite, but no one had any clue what. The solution evaded the best mathematicians for generations until Euler came down from heaven and told us.

Edit: From "A History of PI" by Petr Beckmann
\begin{align} \sin(x) &= x - \frac {x^3} {3!} + \frac {x^5} {5!} - \frac {x^7} {7!} \cdots \\ &= x \cdot (1 - \frac {x^2} {3!} + \frac {x^4} {5!} - \frac {x^6} {7!} \cdots)\end{align}

Let $y^2 = x$, consider $\sin(x) = 0$ for $x \ne 0$:
$0 = 1 - \frac y {3!} + \frac {y^2} {5!} - \frac {y^3} {7!} \cdots \tag{P}$

We know roots of $\sin(x)$ are $0, \pm \pi, \pm 2 \pi, \cdots$, so the roots of $(P)$ are $(\pi)^2, (2 \pi)^2, (3 \pi)^2 \cdots$.

By theory of equations, the sum of the inverse of the roots of $(P)$ is the negative of the linear coefficient. So $$\frac 1 {\pi^2} + \frac 1 {(2 \pi)^2} + \frac 1 {(3 \pi)^2} + \cdots = \frac 1 {3!}$$

$$\frac 1 {1^2} + \frac 1 {2^2} + \frac 1 {3^2} + \cdots = \frac {\pi ^2} 6$$

There is a property of finite polynomials, that if:

$$0 = a_0 + a_1x + a_2x^2 + \cdots a_nx^n = a_n(x - r_0)(x - r_1)(x - r_2)\cdots(x - r_n)$$

then

$$\frac {a_1} {a_0} = \frac 1 {r_0} + \frac 1 {r_1} + \frac 1 {r_2} + \cdots \frac 1 {r_n}$$

It is a major skip in reasoning to assume that this is true for infinite polynomials, but I think this is what the author was getting at.

-
+1 for sum of inverse squares –  BlueRaja - Danny Pflughoeft Oct 18 '13 at 22:35
Dear Daniel, Is it really the case that Euler's argument resolved the sum of inverse squares "easily"? What is your standard for something being easy? Factoring $sin z$ as an infinite degree polynomial (which is my understanding of how he argued, at least at first) seems like a fairly insightful step to me. I guess I'm just unsure what the parameters of the question (and your answer) are. Cheers, –  Matt E Oct 19 '13 at 12:19
I added how I first saw the result. I think it's a lot easier than whats on wikipedia. It does require knowledge of theory of equations though, so I guess it depends on your point of view. That's why it's a soft question I guess. –  DanielV Oct 19 '13 at 13:40
I can't say I know what the "theory of equations is", and this argument is far from easy when all the details are added. You completely skipped the assertion that \sin x is an infinite product of quadratic terms $(x^2 - \pi^2/n^2)$ (and not of the separate linear factors) and therefore haven't had to deal at all with the convergence issues of this product, let alone the issue of to what it converges. The argument may be easy but the proof is not so simple. –  Ryan Reich Oct 19 '13 at 15:05
@Matt I took "easily" in the question to mean something like, "the solution can be explained to someone with a high-school proficiency in math in a few minutes," which inverse-sum-of-squares fits (compare this to, say, Fermat's Last Problem). It doesn't necessarily mean the solution was easy to find. –  BlueRaja - Danny Pflughoeft Oct 21 '13 at 19:34

Zhang's recent result on the boundedness of prime gaps uses surprisingly simple ideas that were available for a long time before.

-
Although this is true, there are lots of clever ideas in the paper and one cannot call this proof easy, whatever the definition of "easy" you take. –  user0810 Oct 21 '13 at 22:42
@Proba Oh, of course, you are perfectly right. I was mostly giving an example to the "with tools existing at the time the problems were made" part. –  Bruno Joyal Oct 21 '13 at 22:54

The Sylvester-Gallai theorem was posed by Sylvester in 1893 and first proved by Melchior in 1941 (who was apparently even unaware of Sylvester's problem). Several more proofs followed and all (including Melchior's) are fairly elementary.

-

$\zeta(3)$

I do not know how long it took for Apéry to prove that $\zeta(3)$ is irrational. However, as Alf van der Poorten recounted in his Mathematical Intelligencer article,

Anyhow, I considered ‘A Proof that Euler Missed’ a racy title. It arose after Cohen’s report at Helsinki, with someone (specifically, an old friend I was sitting next to) sourly commenting ‘A victory for the French peasant . . . ’. To this Nick Katz retorted: ‘No __ ! No! This is marvellous! It is something Euler could have done.’

A charming example of an elegant solution to an engineering problem is Peaucellier's Linkage to convert circular motion to linear motion, using circular inversion. James Watt had created a linkage to convert circular motion to nearly linear motion, but it wasn't perfect. Peaucellier, a French army officer found a method that was perfect. Körner, in his book Fourier Analysis, recounts that Sylvester showed Lord Kelvin a model of it, and:

[H]e 'nursed it as if it had been his own child, and when a motion was made to relieve him of it, replied "No! I have not had nearly enough of it—it is the most beautiful thing I have ever seen in my life"'.

-

The primality of Fermat numbers. That conjecture was a great fail albeit the numbers were pretty big to calculate by hand.

-

Van der Waerden's conjecture on the permanent of a doubly stochastic matrix, proved independently by Falikmann & Egorychev. It turned out to be an easy consequence of an inequality which had been known for a long time.

-

The Dinitz conjecture maybe doesn't belong here because it wasn't all that famous, but it was an open problem for over ten years and the proof was really, really trivial.

-

Finite field Kakeya "conjecture"

Let $\mathbb{F}_q$ be the finite field with $q$ elements and $A\subset \mathbb{F}_q^n$ be a set which contains a line in every possible direction. Then there exists constant $c>0$ (depending only on $n$) such that $$|A|\geq cq^n.$$

Dvir's proof of this is extremely elementary and easy, but nevertheless ingenious. The whole paper is 6 pages long, but one could easily fit the whole argument in less than a page. See here.

-

Modern example: Polynomial time constructive proof for Lovasz Local Lemma (LLL) was proved by Moser and Tardos in 2010.

Problem's History: Lovasz along with Erdos introduced LLL in their 1975 seminal paper "Problems and results on 3-chromatic hypergraphs and some related questions".This paper only gave existential results. In 1991, Beck gave a an algorithmic approach of LLL but the algorithmic results where a constant away from LLL's existential results.

In 2010, Moser and Tardos proposed an algorithm whose results was equal to LLL's existential results.

-
Even the tools here remain addition and multiplication, at a slightly higher level the tools are new. So this wont qualify. –  Turbo Oct 23 '13 at 8:17
The approach taken by Moser and Tardos is the simplest approach one can think. Thats the reason I thought this could qualify as one of the answers. –  Bagaria Oct 23 '13 at 14:14