# Theorems that are 'obvious' but hard to prove

There are several well-known mathematical statements that are 'obvious' but false (such as the negation of the Banach--Tarski theorem). There are plenty more that are 'obvious' and true. One would naturally expect a statement in the latter category to be easy to prove -- and they usually are. I'm interested in examples of theorems that are 'obvious', and known to be true, but that lack (or appear to lack) easy proofs.

Of course, 'obvious' and 'easy' are fuzzy terms, and context-dependent. The Jordan curve theorem illustrates what I mean (and motivates this question). It seems 'obvious', as soon as one understands the definition of continuity, that it should hold; it does in fact hold; but all the known proofs are surprisingly difficult.

Can anyone suggest other such theorems, in any areas of mathematics?

-
Perhaps the isoperimetric inequality. – Péter Komjáth Jan 9 '11 at 11:28
Perhaps the Kepler Conjecture: en.wikipedia.org/wiki/Kepler_conjecture – Aaron Meyerowitz Jan 9 '11 at 11:57
A former colleague of mine used to say (to students), "A theorem is obvious if a proof instantly springs to mind," a maxim I like a lot. I think what you are talking about is theorems where a plausible argument instantly springs to mind but falls short of being a proof. – gowers Jan 9 '11 at 15:12
I am tempted to vote to close as subjective and argumentative given the comments on the existing answers. Can we narrow the definition of 'obvious' being used? Something like gowers' definition is good, but depends a lot on one's training. Perhaps something like "if you asked an undergraduate if it were true, they'd bet yes." – Qiaochu Yuan Jan 9 '11 at 16:46
I disagree that the Jordan curve theorem is "obvious" but admits a surprisingly difficult proof. The proof for curves with reasonable regularity is not difficult, while the truth of the theorem for wild curves is not so obvious, I think. (At least, I think it is reasonable to argue that most people's sense of this being intuitively clear comes from imagining a rather regular curve in the plane, not a wild one.) – Emerton Jan 10 '11 at 16:46

## 52 Answers

Here is an example proof of which is not conceptually difficult, but tedious to write down in full detail: There exists a universal Turing machine.

The reason I find this obvious is that, after learning the definition of what a TM is, a moment's thought will suggest that we should be able to encode information of any TM to a natural number since it is a finitary object. Then, it is conceivable that there is an algorithm which decodes any natural number and carry out the instructions.

Of course, constructing the universal machine and proving that it can actually simulate all the other machines involve some unpleasant details.

-

I think a very good example is Kepler Conjecture:

http://en.wikipedia.org/wiki/Kepler%27s_conjecture

This conjecture stated that the most "tight" stack of same balls have only two kinds of arrangement with a fixed density.

Every physicist knows that it's true, no mathmaticans ever proved it.

Fortunately, Hales used computers to step forward a little little bit.

-

P is not equal to NP. This is "obvious", is a straightforward arithmetic proposition doesn't involve any fancy set theory or spacefilling curves, and yet it's so hard that there have whole workshops ("Barriers") and important papers (BGS, natural proofs etc.) devoted to the question of what makes it so hard. Scott Aaronson describes "a would-be P≠NP prover who hasn’t yet grasped the sheer number of mangled skeletons and severed heads that line his path." P≠PSPACE is even more obvious and yet there is a comparable lack of progress.

-

I think Godel's completeness theorem is very intuitive. For example, can you imagine a first order theorem that would be true for all groups, that you wouldn't be able to prove (by Godel's definition of prove'). Of course not! But the proof of the completeness theorem is hard.

-
I agree that the completeness theorem sounds very intuitive, but I think this is misleading. It takes some serious thought to convince yourself that a particular definition of formal proofs captures mathematical practice (even if you believe intuitively that some definition should work, it's much less obvious that a given deductive system really is complete). Furthermore, I'd bet that many mathematicians would find it equally intuitive that there should be a complete proof system for second-order logic, and of course incompleteness tells us there isn't. So completeness is pretty subtle... – Henry Cohn Sep 8 '12 at 18:17

Very good candidates for this question are theorems that amount to saying that some sequence behaves randomly in a way. Both the fact that the statements are obvious and the fact that they are usually hard to prove, are explained by the fact that there is just no reason for the sequence to nót behave randomly. The primes are of course notorious for this. Easy example that springs to mind: there are about as many primes whose last (decimal) digit is $1$ as there are primes whose last digit is $3$.

-

Since this was resurrected, here is the statement that at this time seems to me to have the greatest gap between obviousness of truth and obviousness of proof:

• There exists a natural set theoretic universe in which every subset of [0,1] is Lebesgue measurable, so that the reals admit no well order and do not inject into aleph-1.

Here are a different class of obvious theorems, these are only obvious in the sense of physical intuition. They took a long time to prove:

• The existence of solid matter occupying space (in the lowest energy state, the electron-nucleus system occupies a volume proportional to the number of nuclei)
• The positive energy theorem--- every asymptotically flat solution of GR obeying the appropriate energy condition has a positive mass at infinity, with zero mass only for Minkowski space.
• Hard sphere collisions on a negatively curved space are ergodic.

Here is a physically obviously true statement, which can be seen from physical intuition, but which is not proven (as far as I know):

• The asymptotic fate of GR with a positive cosmological constant is within any causal patch, and except for a set of initial conditions of measure zero, a deSitter space.

The reason this is obvious is because the deSitter space maximizes the horizon area, which is a measure of the entropy.

-

A differentiable manifold M that is homeomorphic to the n-sphere is also diffeomorphic to the n-sphere . Obvious, but wrong ! (But right for 1-, 2-, 3-, 5-, 6- and 12-spheres).

-

The Carpenter's rule: a planar linkage can be straightened without the links running into each other. Although the statement had initially seemed obvious, its truth or falsity was a matter of debate among the experts for several years until Bob Connelly, Eric Demaine, and Günter Rote finally proved it. (The analogous statement in 3 dimensions is actually false.)

-
And the analogous statement in dimensions greater than 3 is true: they can always be straightened! $\mathbb{R}^3$ is the exception. – Joseph O'Rourke Aug 26 '11 at 23:51

I'm not sure if it is considered obvious, but I think the Collatz conjecture is also a good example (not just hard to prove, but still unproven!). I've always found it very frustrating that such a simple conjecture does not lend itself to a simple proof.

'Obvious' here sort of means: Try a lot of values, and you'll get a feeling THAT it indeed holds, but also WHY it holds.

http://en.wikipedia.org/wiki/Collatz_conjecture

-
How can you tell that there is no counterexample at $2^{3013}+3^{2012}+5^{1003}+7^{691718}+1$? Or perhaps the number after that? Or after that? Etc.? – Asaf Karagila Aug 26 '11 at 9:53

The most deadly example I know is the Hauptvermutung in dimensions 2 and 3 (in dimension $>3$, it is the ultimate "obvious but false" theorem). The Hauptvermutung, or "Main Conjecture" states that any two triangulations of a polyhedron are combinatorially equivalent, i.e. they become isomorphic after subdivision.
The Hauptvermutung is so obvious that it gets taken for granted everywhere, and most of us learn algebraic topology without ever noticing this huge gap in its foundations (of the text-book standard simplicial approach). It is implicit every time one states that a homotopy invariant of a simplicial complex, such as simplicial homology, is in fact a homotopy invariant of a polyhedron, unless one also proves independence relative to triangulation.
The Hauptvermutung for 2-manifolds was proven by Radó, and for 3-manifolds by Moïse in 1953. It is a genuinely deep, difficult theorem.
Edit: This answer is essentially taken from Page 4 of The Hauptvermutung Book.

-
At least since the introduction of singular homology, there is no gap in the foundations of algebraic topology. But I agree that the Hauptvermutung has a feeling like being obvious. – Lennart Meier Jan 10 '11 at 18:46
By "subdivision," I believe you mean PL-subdivision, making the Hauptvermutung a little less obvious. An essentially equivalent statement to its falsity in dimension 5 that I find very unintuitive is that there exists a 4-dimensional simplicial complex $K$ which is not a triangulation of a manifold, but whose suspension $\Sigma K$ is a triangulation of a 5-sphere. – Richard Stanley Jan 12 '11 at 0:59

No exatly what asked..

But historically: The fifth postulate of Euclid (to a point outside a straight line passes exactly one line parallel to this line). At first it seems an obvious fact, and tried to prove it....

-

The stability of Minkowski Spacetime

An asymptotically flat initial data set for the Einstein equations that is sufficiently "close" to the initial data for Minkowski spacetime generates a solution to the Einstein equations that approaches Minkowski spacetime asymptotically. (try saying that fast 3 times)

It is "obvious" because of our physical experience and intuition with gravity, and it is hard to prove because Einstein's equations are quite subtle and complicated.

There are other theorems in mathematical relativity that fall into this category, but this one is especially striking since it is particularly difficult to prove, while it "feels" blatantly true.

-

No one has mentioned the 4-color map theorem yet. it would seem to be a classic example.

-
No one has mentioned it because it isn't obvious. – Johannes Hahn Feb 28 '11 at 20:05
It appears to be obvious. Combine the obvious fact that more than 3 is necessary with the fact you can't construct a 5 region map that requires 5 colors (follows directly from the fact that the complete graph of 5 node is not plainer) leads most people who look at it casually to mistakenly conclude that 4 is sufficient. – Mark Biggar Feb 28 '11 at 21:42

On page 33 of Stable Mappings and Their Singularities by Golubitsky and Guillemin (GTM 014; 1974), the following proposition is characterized as an "obvious, but surprisingly complicated result":

Proposition 1.10: Let S be a nonempty open subset of $\mathbb{R}^n$. Then S is not of measure zero.

Edit: As pointed out in the comments, Gowers already mentioned an equivalent result whose difficulty is more clear. Please vote this answer down (I can't vote down my own answers).

-
I must be completely missing the point here. Why is this hard? Can't you just show that there is a small cube inside $S$? – Deane Yang Feb 28 '11 at 2:14
I suppose that this is trivial if one constructs Lebesgue measure by first assigning measure to rectangles and in the end declares a set to be of measure zero if...well, if it has Lebesgue measure zero. If one merely has the classical definition of a zero measure set (a set such that $\forall \varepsilon > 0$ can be covered by countably many rectangles so that the sum of their volumes is at most $\varepsilon$), this is nontrivial. Actually Gowers already mentioned an equivalent result, in which the difficulty is more clear. – Mark Feb 28 '11 at 3:34
Does this mean that it is hard to show that a rectangle does not have measure zero? – Deane Yang Feb 28 '11 at 15:54

Dynamic programing principle (DPP) is one of the 'obvious' and also intuitive one, in the control problem. Many papers proves its validity in various setup, and all proofs are very complicated. But, there is rarely a counter example of DPP. I wonder, if there is general framework on it. See, Dynamic programming principle (DPP)

-

It is obvious that there is a unique point in any given affine plane in a finite-dimensional euclidean vector space which is closest to the origin.

Therefore it would seem similarly obvious that every de Rham cohomology class on a compact oriented riemannian manifold should have a unique representative with minimal $L^2$ norm: namely, its harmonic representative.

Yet it takes some effort (elliptic regularity,...) to prove that the harmonic representative does in fact exist, i.e., that it is a smooth differential form.

-

On an elementary level, the intermediate value theorem is surprisingly deep.

On a less elementary level, the prime number theorem is "obvious" from $\sum_{p\leq x}1/p\sim \log\log x$ (that was noticed by Euler) and Dirichlet's theorem on primes in arithmetic progressions is "obvious" if you use the sieve of Erathostenes.

-

That the identity map of the circle is not nullhomotopic. [When one thinks about it, it is pretty much equivalent to the Brouwer fixed point theorem, which is not as obvious.]

-
This was my introduction to many sophisticated mathematical ideas. When teaching several variable calculus I asked my self how I could convince students that Stokes theorem was useful, and found that it could be used to prove this fact, hence also the fundamental theorem of algebra, Brouwer fix point theorem, etc... Equivalently, why is the one form "dtheta" locally exact but not exact? – roy smith Jan 20 '11 at 6:04

The first of the Tait Conjectures seems intuitively obvious:

Any reduced diagram of an alternating link has the fewest possible crossings.

This 19th century conjecture is difficult to prove, with the proof coming only in 1987 by Kauffman, Murasugi, and Thistlethwaite, using the Jones Polynomial. The discovery of this proof was a huge coup for quantum topology; a quantum invariant was used to prove a difficult classical open problem.
While this is certainly hard to prove, I don't think it's unexpectedly hard to prove. Knot diagrams modulo Reidemeister moves form a rather complicated algebraic structure; and there's no reason to expect that any statement about knot diagrams should be easy to prove.

-

"Global regularity of the Navier-Stokes equation" is not yet in this category, but once a proof is found, I am sure it will be.

More generally, there are many PDE which are "obviously" solvable for physical reasons, but for which actually proving existence (particularly in "global", "non-perturbative" situations, and requiring strong (regular) solutions rather than weak ones), is extremely difficult. A typical example is the Boltzmann equation, for which good global regularity results have only become available recently, with the work of Villani and others.

EDIT: Admittedly, many of the global regularity problems become a lot easier if one applies a physically reasonable truncation. For instance, global regularity for Boltzmann is much easier if one can somehow restrict the particle velocities to never exceed some upper bound $c$. But then the non-obvious fact moves elsewhere; rather than global regularity, the issue is whether one has sufficiently quantitative bounds that these thresholds rarely get triggered. Physically, it is intuitively obvious that a Boltzmann gas is not routinely churning out particles travelling at close to the speed of light; but it is remarkably difficult to quantify and then establish this rigorously.

-

I agree this question is interesting, but only in a psychological rather than mathematical sense, i.e. the only reason the jordan curve theorem seems obvious is that we do not appreciate the generality of the definition of "continuous", rather taking our simplest intuitive examples as typical. Indeed the proof for smooth functions is pretty easy (cf. Guillemin and Pollack), and how many of us distinguish intuitively between (piecewise) smooth and continuous functions? For instance young students assume the intermediate value theorem is obvious because they do not appreciate the local nature of the definition of continuity, i.e. they intuitively assume that the intermediate value theorem is the definition of continuity, as indeed it was in a less rigorous time. Of course the proof of the IVT is a justification of the reasonableness of the definition of continuity. As Moishezon remarked to us as students: " even if it is obvious, you still have to prove it". Or as Tate said after giving an irresistible pictorial argument in first year honors calc. for the continuity of a composition of continuous functions; :"Of course this is NOT a proof! I have merely rendered it intuitively plausible!" (a statement i did not believe at the time.)

Problems in freshman calculus: 1) Give a characterization of a function g such that g is a primitive of a given Riemann integrable function f. Is it enough to assume that g is continuous and differentiable wherever f is continuous, and that g has derivative equal to f at such points? E.g. is a continuous function which is differentiable with derivative zero a.e. a constant function? If not, what assumptions do you have to add?

2) Give an intrinsic characterization of a function g that is a primitive of some unknown Riemann integrable function on [a,b]. Is it enough to assume that g is Lipschitz continuous?

I guess i would give more credence to this if it concerned say theorems that have physically compelling arguments that are hard to make mathematically rigorous, such as Riemann's arguments for the existence of meromorphic functions of second kind with arbitrary poles.

When someone says it is "obvious" that Euclidean space R^n has dimension n, they are really saying that any definition for which this is false is a bad definition, not that it is easy to give an appropriate definition, nor that it is easy to prove the theorem even for a good definition. So this is just an imprecise use of language.

Let me pose a little fun question: Since everyone knows that if n < m, there can be a continuous surjection, but no homeomorphism from R^n to R^m, what about a continuous injection from R^m to R^n? What is the obvious answer? Is it also the correct answer? How much does your response draw on some non obvious mathematical reasoning?

My best idea in the direction of the original question is: "why is a straight line the shortest smooth curve joining two points?"

-

It takes Russell and Whitehead several hundred pages to prove that $1+1=2$ in Principia Mathematica. They then say that "the above proposition is occasionally useful."

-
I've always wondered about the next sentence: "It is used at least three times, in $\ast 113 \cdot 66$ and $\ast 120 \cdot 123 \cdot 472$." [my emphasis]. Does this express some sort of dry humour or is it meant seriously? – Theo Buehler Jan 12 '11 at 3:58

The Kneser-Poulsen conjecture says that if a finite set of (labeled) unit balls in $\mathbb{R}^n$ is rearranged so that in the new configuration, no pairwise distance is increased, then the volume of the union of the balls does not increase. This was finally proved by Bezdek and Connelly in dimension 2 but remains open in higher dimensions.

There are several other notorious elementary problems in geometry that might qualify, e.g., the equichordal point problem, though this one is not quite as "obvious" as the Kneser-Poulsen conjecture.

-
It seems to me far from obvious that that result should be true in all dimensions, especially after the dramatic disproof of the Borsuk conjecture due to Kahn and Kalai or the disproof of the Busemann-Petty conjecture. – gowers Jan 13 '11 at 16:23

There are a number of facts in multivariable calculus that are obvious but hard to prove. For instance, the change-of-variables formula in a multiple integral is very easy to justify heuristically by talking about little parallelepipeds but troublesome (as I discovered to my cost in a course I once gave) to justify rigorously. And the same goes for the inverse function theorem: although the proof can be made quite transparent and the need for continuous differentiability makes good intuitive sense, there seems to be an irreducible core of actual work needed (in particular, the use of a fixed-point theorem to replace the use of the intermediate-value theorem in the 1D case).

I'd be quite glad to be told that this answer was wrong. If anyone knows of a link to an exposition of these results, particularly the first, that does proper justice to their intuitive obviousness, I'd be very pleased to hear about it.

-
I'm afraid you're right. The change of variables formula for multiple integrals is a notorious "Is it really this hard?" moment in mathematical exposition. – Pete L. Clark Jan 11 '11 at 18:14
The inverse and implicit function theorems are actually equivalent. – Paul Siegel Jan 15 '11 at 15:57

Inspired by the trefoil knot example: "If two knots are smoothly* isotopic, then their complements are homeomorphic." I'm not sure exactly how hard the proof is, but it certainly seems obvious, and I don't think there is a one line proof.

*Thanks to Richard Kent for pointing out that I need this adverb.

-
You need to put "smoothly" in front of "isotopic," otherwise the statement is false: all knots are isotopic (by shrinking all the "knottedness" to a point, a.k.a. bachelor's unknotting). Usually, one fixes this by defining knots to be equivalent if they are ambient isotopic, in which case you get the homeomorphism for free. (In the smooth case, the proof amounts to proving that the isotopy extends to the 3-sphere.) – Richard Kent Jan 10 '11 at 0:36
That was a misleading passage in Wikipedia. I tried to clarify it. – Douglas Zare Jan 11 '11 at 1:30
Glad to help, David. I agree with the assessment that the extension is obvious but not easy. – Richard Kent Jan 11 '11 at 4:22
@Daniel I disagree about which is the natural formalism. My physical intuition for why you can't untie a trefoil is that it would have to pass through itself, which I capture with the injectivity hypothesis. The fact that I would have to move space out of the way is completely irrelevant. After all, if I put a knotted rope in a vacuum, it is still knotted! – David Speyer Jan 11 '11 at 14:50

The notorious Dehn's Lemma, and it's generalizations, the Loop Theorem and the Sphere Theorem. It was a bone in the throat of 3-manifold topology for almost half a century, despite being obvious', until proven by Papakyriakopoulos in 1957.
A comment on why it is obvious: the only singularities one can possibly imagine a disc having are things like "stretch a feeler out and around and around through the disc"- and it's obvious how to re-embed to get rid of those. Dehn's Lemma is a statement in the PL category, not in the topological category, so nothing pathological can occur. There's nothing which could possibly go wrong- no way you could possibly create a singularity in a DISC which you can't kill by re-embedding. But... prove it!

-
-1: All kinds of stuff could go wrong! – Richard Kent Jan 9 '11 at 16:23
I don't know much about 3-manifolds, so perhaps my intuition is undeveloped--that said, when I found out about the sphere theorem, I did a double-take. Were someone to have asked me if I thought this was true before I ran across it, I would have guessed it was wildly optimistic. – Daniel Litt Jan 10 '11 at 18:39
@Richard: Almost all undergraduates I know would answer neither "yes" nor "no" but would stare blankly, not understanding the question. – Timothy Chow Aug 26 '11 at 18:26

In the same genre, if not the same type: The Fundamental Theorem of Algebra. Easily understood by high schoolers, plausible, beautifully simple to state. As far as I know, there are no nice proofs understandable by a good (not brilliant) high school student.

-
I do not know why this is plausible. What would be an "obvious" reason to expect that a degree 6 polynomial with real coefficients has a complex root? – Andrés Caicedo Jan 10 '11 at 23:30
Here is a proof whose main idea is understandable by many high school students. The winding number of the image of the circle of radius $r$ changes from $0$ at $r=0$ to the degree of the polynomial for $r$ large, and it can only change when there is a $0$ of the polynomial. – Douglas Zare Jan 11 '11 at 1:11
If I'm following this correctly, some comments say the example is unsuitable because proving the theorem is actually easy, while the oldest comment says it's unsuitable because it's not obvious. What a mess! Keeping in mind how long it took between the result being conjectured and the first actual proof, I think we are too far removed in time from the result to truly appreciate it from a historical perspective, and the FTA is too fundamentally rooted in students educations to imagine how hard it would be for someone who was a blank slate. – Thierry Zell Jan 11 '11 at 14:43
@Thierry: agreed. Anything Euler attempted unsuccessfully to prove can't be all that easy. I think your comments apply to comments on several other answers as well in relation to how rooted algebraic topology is in many mathematicians' educations these days. – Qiaochu Yuan Jan 12 '11 at 14:34

I think this answers your question in a perverse way: All statements in the theory of Natural Numbers provable from the ZFC axioms of set theory. They are obviously true by definition.

EDIT: Looking at this objectively, it probably sounds like I'm saying if a statement is true, then it's obviously true. However, that was not my intent, and I apologize for what may have sounded like a thoughtless response. This is how I see it:

All statements expressible in the language of arithmetic can be represented by formulas in the language of set theory that are only $\Delta_1$ in the Levy hierarchy. In particular, all transitive models will agree on whether they are true. If we further restrict ourselves to only consider the true statements in $\mathbb{N}$ that are ZFC theorems, then all ZFC models will agree that these statements must be true so they are about as obvious to ZFC models as possible. Now if you are an oracle having knowledge of all such true statements, then you will probably develop an intuition that makes them all seem "intuitively obvious." This reflects the answers suggesting that a theorem is obvious after you prove it.

To add one more related point here, when addressing G$\ddot{\textrm{o}}$del's Incompleteness Theorem, one can naively ask about completing PA in the "obvious" way, i.e., by extending it to be the theory consisting of all true statements in $\mathbb{N}$. But of course such a completion is not computable.

-
What is this definition of "obviously true" that makes these obviously true? – Chris Eagle Jan 10 '11 at 4:00

Inspired by the trefoil knot is knotted" answer, how about the fact that Reidemeister moves generate isotopy of PL knots? This is pretty obvious but a full proof requires a lot of machinery. Indeed, the proof was not known to Reidemeister, who took the fact that his eponymous moves generate isotopy as an unproven axiom. (See Daniel Moskovich's comment.)

-
Are you sure? I think Reidemeister did prove it in Knottentheorie (1932), entirely combinatorially. There is a "general position" issue, which is an issue for all of PL topology- but it's no harder for the Reidemeister Theorem than anywhere else. See mathoverflow.net/questions/15217/… – Daniel Moskovich Jan 10 '11 at 0:52
I stand corrected. It didn't make it into the original edition of Knotentheorie, but was proved 6 years earlier by Reidemeister (1926), and independently by Alexander and Briggs (1927), as I found by nosing around in the math library this morning. All details are there, including general position arguments. Wikipedia, to my surprise, is entirely accurate: en.wikipedia.org/wiki/Reidemeister_move – Daniel Moskovich Jan 10 '11 at 13:40

$\mathbb R^n$ is not homeomorphic to $\mathbb R^m$ unless $m = n$.

-
1+. I think this is the key point of the answer of Georges Elencwajg. It's not so really about one specific topological dimension and its computation, but rather that we can distinguish the affine spaces at all. I wonder how many decades (centuries?) mathematicians were convinced of this fact without having a proof? – Martin Brandenburg Jan 12 '11 at 8:01

## protected by quidMar 14 '14 at 20:12

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?