# Why do statements which appear elementary have complicated proofs?

The motivation for this question is : Rationals of the form $\frac{p}{q}$ where $p,q$ are primes in $[a,b]$ and some other problems in Mathematics which looks as if they are elementary but their proofs are very much sophisticated.

I would like to consider two famous questions: First the "Fermat's Last Theorem" and next the unproven "Goldbach conjecture". These questions appear elementary in nature, but require a lot of Mathematics for even comprehending the solution. Even the problem, which I posed in the link is so elementary but I don't see anyone even giving a proof without using the prime number theorem.

Now the question is: Why is this happening? If I am able to understand the question, then I should be able to comprehend the solution as well. A Mathematician once quoted: Mathematics is the understanding of how nature works. Is nature so complicated that a common person can't understand as to how it works, or is it we are making it complicated.

At the same time, I appreciate the beauty of Mathematics also: Paul Erdős' proof of Bertrand's postulate is something which I admire so much because, of its elementary nature. But at the same time i have my skepticism about FLT and other theorems.

I have stated 2 examples of questions which appear elementary, but the proofs are intricate. I know some other problems, in number theory which are of this type. Are there any other problems of this type, which are not Number Theoretical? If yes, I would like to see some of them.

-
I don't agree with "If i able to understand the question, then i should be able to comprehend the solution as well." I don't think that it is possible to answer the question "Why is this happening?". (Voted to close as subjective and argumentative.) – Rasmus Sep 23 '10 at 13:00
Rasmus's point is as valid in the natural sciences as in mathematics; there's a lot of seemingly simple physical phenomena that we are at a loss to explain properly. – J. M. Sep 23 '10 at 13:14
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is." — John von Neumann – Pandora Sep 23 '10 at 15:54
I've changed the title to more closely reflect what the question seems to be asking, but I'm not convinced that it's any 'better'... – Larry Wang Sep 25 '10 at 17:59
Why do bad things happen to good people? – Pete L. Clark Nov 28 '10 at 0:08

If you were to ask me why the sky was blue, to give a complete answer I would have to describe the heliocentric model, the earth's atmosphere, and the electromagnetic spectrum.

If you asked me how my computer connected to the internet, the answer would take a considerable amount of time to explain.

If you asked my whether there was life on other planets, I wouldn't be able to give an answer; we just don't know.

Often, it is impossible to give a simple answer to a simple question. This is true in any field you might encounter, ranging from the sciences to the humanities. And it is true in mathematics,

Mathematics allows us to formalize our questions within an axiomatic structure. It lets us ask our questions more precisely. But it in no way guarantees that the simplicity of the question would translate into simplicity of the answer.

Some other simple problems which cannot be answered simply:

The Four color theorem states that any map made up of continuous regions can be colored with 4 colors such that each region gets 1 color and no two adjacent regions get the same color. The proof is quite complex, requiring the use of a computer.

Scheinerman's conjecture is the conjecture that "every planar graph is the intersection graph of a set of line segments in the plane" (sourced from http://en.wikipedia.org/wiki/Scheinerman%27s_conjecture). However, the proof was only completed in 2009, and is fairly difficult.

-
Very nice response! – Ryan Budney Sep 25 '10 at 19:18

I suppose there is a way to formalize your question into a relatively precise one. Let $P$ be the set of all propositions in the language of Zermelo-Frankel set theory for which there exist proofs.

Given a natural number $k$ we want to have an upper bound $l(k)$ on the minimal-length of the proof of any proposition $p$ from $P$ such that the length of the proposition $p$ is at most $k$. Here I'm using "length" in the sense of the number of ASCII characters it would take to write the proposition (or proof of the proposition, respectively).

Presumably $l(k)$ is a non-computable function. Since if $l(k)$ were computable, given a proposition $p$ of length $k$ you'd have a "simple" procedure to find a proof of any statement in Zermelo-Frankel set theory, provided one exists. The idea would be to iterate through all propositions of length at most $l(k)$ and verify they're proofs of $p$. :)

I imagine such a statement is known to logicians. If it is known, I would call it the "rationalization is hard theorem".

-
Yes, this is well known to logicians. In general, the set of provable statements from an effective first-order theory like ZFC is computably enumerable but not decidable, and thus the function $l(k)$ actually is noncomputable in general. In particular it is uncomputable in the cases of ZFC and Peano arithmetic. There are many examples of other theories in which provability is decidable, however. – Carl Mummert Sep 25 '10 at 23:29
@Chandru1: this should be the accepted answer. It is much more precise than the currently accepted answer and tells you exactly what to expect in the worst case. – Qiaochu Yuan Sep 27 '10 at 3:20
@Qiaochu: Users are only notified when addressed by @ if they have previously commented on the same post. See the faq on meta.so. – Larry Wang Sep 28 '10 at 6:58
+1 for "rationalization is hard theorem"! – jericson Oct 14 '10 at 3:19
Yes, there is no computable upperbound on the size of shortest proof of theorems of first order logic. This and similar questions are studied in proof complexity. Search for finite versions of Godel's theorem or check the papers by Sam Buss or Pavel Pudlak. Also check their nice paper "How to Lie Without Being (Easily) Convicted and the Length of Proofs in Propositional Calculus". – Kaveh May 27 '11 at 1:41

This is a very deep question that many famous mathematicians have worked on, including Godel, Hilbert, ...

So the question is why simple elementary problems (say problems with only universal quantifiers) do not have short elementary proofs. But before continuing we first need to agree on "what is an elementary proof?". In proof theory, an elementary proof is a proof that does not use concepts (and formulas) that does not appear in the axioms or in the theorem.

Hilebrt tried to show that reasonable elementary axioms are sufficient for proving all elementary theorems. His attempt failed because of Godel's incompleteness theorem. For any reasonable set of axioms, there is an elementary statement that is not provable from them. So we need non-elementary axioms for proving elementary theorems. This is the first point. Complicated axioms are needed to prove some simple elementary theorems.

Now let's assume that we have a proof of an elementary theorem (from some set of axioms). Then there is an elementary proof for the theorem from the axioms. This due to Gentzen's cut-elemnitation which asserts the existence of cut-free proofs, and moreover we have an algorithm that whenever we give it an arbitrary proof for a theorem, the algorithm converts it to a cut-free proof pf the same theorem from the same axioms. One of the nice properties of a cut-free proof is that any formula in the proof is either a subformlua of one of the axioms or a subformula of the theorem. That seems quite good.

But why people don't use such proofs? The answer is that cut-free proofs can be a lot (super-exponentially) larger than proofs using cuts. Informally you can think of cuts as proving lemmas and then using them for further results. A 100 page proof can turn into a $2^{50000}/500$ page proof after cut-elimination (I am assuming each page contains 500 symbols).

When we use concepts from outside, we usually define them to stand for complicated and hard to understand formulas. This simplifies the understanding of the proof if we are familiar with those concepts. Take for example the following pseudo-statement:

$\forall \epsilon \exists \delta \exists m \forall n>m ...$

This is quite complicated formula if one is not already familiar with similar formulas. The first two quantifiers are the $\epsilon\text{-}\delta$ we know from limits. The second pair is just for all sufficiently large $n$. Or take for example:

$\forall \epsilon \exists \delta \forall y \text{ s.t. } 0<|y-x|<\delta; \ |\frac{y^3+2y^2-x^3-2x^2}{y-x}-3x^2-4x|<\epsilon$

This is much more complicated than $(x^3+2x^2)'=3x^2+4x$. Here we are using newly defined concepts to shorten the formula and make it more human readable. Using lemmas about these concepts we can give a short proof of this equality, while the elementary proof can be much longer. Definitions of new concepts and lemmas can make a proof much shorter and more understandable. So elementary proofs might be harder to understand that non-elementary proofs using concepts from outside. This is the second point.

Now apply what I said above to the several hundred page long proof of FLT, ignoring the fact that the full proof will need to contain the proofs of all theorems and lemmas that are used in the proof. The resulting proof will probably be practicably inexpressible on any medium and completely impossible to understand by a human-being.

If we have a short elementary proof, then it is good. But there are elementary theorems with short non-elementary proofs which do not have short elementary proofs. This is the third point.

In summery:

1. complicated axioms are needed to prove some simple elementary theorems (Godel's incompleteness theorem),
2. non-elementary proofs might be easier to understand,
3. there are elementary theorems with short non-elementary proofs which do not have short elementary proofs.

Items 2 and 3 are related to what we call definitions and lemmas in mathematics and are related to proof theoretic and proof complexity concepts called cuts and extension by definitions. (There are other things that also make a proof more readable and related concepts in proof complexity but going into them would diverge from the question about a proof being elementary.)

Two related notes:

• There is a speed-up theorem by Godel in logic.
• Having a short elementary proof is not sufficient for finding one (assuming widely believed conjectures in computational complexity theory). See this and this.
-
I love your perspective! – Yellow Skies Sep 28 '12 at 2:25

The question may look almost self-evident, yet when translated into math, it sometimes looses that self-evident feature and so it requires (often fairly complicated) proof. My favorite example is the Jordan Theorem. A closed non-intersecting curve separates the plane into "inner" and "outer" regions. Looks like there isn't anything to prove here. But translate the notion of "closed non-intersecting curve" into the formula, and we no longer have any intuitive feel of "inner region", "outer region", and what is that region anyway. The simplest proof requires the machinery of algebraic topology and still quite long.

-
And how do you tell which is inner and which is outer? It might seem obvious, and maybe it's a lot easier than proving that there are two regions, but it's still not as easy as it sounds... – SamB Nov 28 '10 at 0:05
@SamB : A formal statement of the Jordan Curve Theorem looks something like this: "If $f: S^1 \to \mathbb{R}^2$ is continuous and 1-1, then $\mathbb{R}^2 \setminus f(S^1)$ has exactly two path-connected components one of which is bounded ('the inside') and one which is unbounded ('the outside'), both of which having $f(S^1)$ as their boundary." So there is at least a fairly good way to tell which one is the inside – kahen Nov 28 '10 at 1:16

One essential piece of intuition from theoretical computer science: since P $\neq$ NP (we assume!), there are many statements which are easy to state but hard to prove.

-

There are elementary questions that have no elementary answers, other than questions in Number Theory and situations invoking Godel incompleteness. I have in mind finding antiderivatives of elementary functions such as $e^{-x^2}$, $(\sin x)/x$, $1/(\log x)$, and many others. It is known that the antiderivatives of these functions cannot be expressed in closed form in terms of powers, exponentials, logarithms, trig functions, etc.

It's also known that the solutions of simple equations like $x+e^x=0$, $x=\cos x$, $x\log x=1$ and so on can't be expressed in closed form in terms of the standard elementary functions.

-
Gerry, I think the word elementary is overloaded (as many other mathematical names). "Elementary functions" are just a class of functions that are named "elementary functions". I think the question is asking for a different notion of elementary. – Kaveh May 27 '11 at 1:39
OK, let me put it another way. Why should $\int xe^{-x^2}$ be easy, while $\int e^{-x^2}$ is impossible (in terms of functions of 1st year Calculus)? Why should $e^x+e^{-x}=3$ be easy, while $e^x+x=3$ is impossible? I'm pointing out that problems that look very similar to easy problems may be not just complicated but impossible. – Gerry Myerson May 27 '11 at 6:45
I wouldn't exactly call the number e elementary. It requires extension of numbers to include cauchy sequences of rationals. It's not as simple as say $x^2 + 1 = 0$, which also has no "answer" in terms of the simple set of rationals or reals. – Matthew Levy Oct 12 '14 at 20:02

Statements containing the word "every" are really much more complicated than they appear. For example the question "is every even integer n >= 4 the sum of two primes" looks easy, but if I ask "is 329872923459897823598798789723452396862359798797234597972798352 the sum of two primes", that's not really an easy question. Answering with "yes" in the obvious way would require to verify that some huge number is not composite, which isn't really easy. Or you'd have to show that one out of the possibly large set of huge numbers must be a prime number. Answering with "no" if that was the correct answer (which is unlikely but not impossible) would be a lot harder.

-