## Tuesday, February 09, 2010

### What is an Elementary Proof?

What is an Elementary Proof? Different things in different contexts.
1. An Elementary Proof is one that does not use Complex Analysis. Basic Calculus is fine. This was the criteria when people asked for an Elementary Proof of The Prime Number Theorem. Such a proof was found by Erdos and Selberg. (See this paper for the history) Later Oliver Sudac (TCS, The Prime Number Theorem is PRA Provable, Vol 257, NOT Online) showed there is a proof in Primitive Recursive Arithmetic which is weaker than Peano Arithmetic. An interesting article on this which IS online is by Jeremy Avigad on all of this is at Number Theory and Elementary Arithmetic. From what I hear, the original proof is still the easiest way to prove it. (NOTE- Oliver Sudac, if you are reading this put your paper on line. If you do not then over time it will be called Avigad's theorem''.)
2. An Elementary proof is one that can be taught to a class of bright college students in about two hours. If you hear someone say Shelah's primitive recursive bounds on the VDW bounds is elementary this is what they mean. (See here. for the paper.) )
3. An Elementary proof is one that does not use advanced techniques. The original proof of Szemeredi's Theorem is rather difficult; however, it does not use advanced techniques. You could probably teach it to a class of bright college students in about two months. Even so, I would hesitate to call it elementary. It might be easier to learn the background mathematics for one of the non-elementary proofs rather than follow the elementary one.
4. An Elementary proof is one that some bright high school students can come up with during a High School Math Competition.
1. The following is elementary: Show that any for any 3-coloring of the natural numbers there exists x,y that are the same color such that x-y is a square.
2. The following is probably not elementary: Show that any for any 4-coloring of the natural numbers there exists x,y that are the same color such that x-y is a square. I wanted to put it on the Maryland Math Competition to find out if it was elementary, but alas they didn't let me. I do not know of a proof that a bright college student could do on his own. The theorem is true by poly VDW thm; however, I would very much want to see an easier proof.
3. The following is elementary: Show that if n is a power of 2 then if there are 2n-1 integers then some n of them sum to 0 mod n.
4. The following is probably not elementary: Show that if n is any integer then if there are 2n-1 integers then some n of them sum to 0 mod n. The proof in here is elementary in that you could explain it to a bright college student in 30 minutes; however, I don't think they could come up with it themselves.
5. In Elementary Particle Theory it is the particles that are elementary, not the theory.
It is hard to pin down Elementary rigorously. I just want to be able to understand a proof and the intuition behind it. But we can't define elementary in terms of what I want.

What theorem would you most want to see an elementary proof of? For me it would be Gowers bounds on the VDW numbers.

1. Anything I can understand is elementary, and usually trivial. :)

2. I like definition 3 best. 1 is a particular example consistent with this. Definitions 2 and 4 are more like "easy" as opposed to "elementary." An "elementary" proof is one where the individual steps are simple, as opposed to relying on deep results.

Put another way, a high-school student could check the proof, given time. It might still take a genius to find it.

3. It is important to distinguish elementary proofs from elementary tools.

Elementary proof is an argument which looks rather trivial in a developed theoretical context. At the same time, elementary tools often lead to non-elementary and unnatural proofs.

E. g. in this respect, Grothendieck is a master of elementary proofs.

4. Elementary proof is an argument which looks rather trivial in a developed theoretical context.

While that would have been a perfectly fine definition, in fact elementary proof already is somewhat vaguely defined, and it does just mean that the tools used in the proof are basic. As the link says, "some elementary proofs can be quite complicated".

5. Olivier Sudac's article is available online at http://dx.doi.org/10.1016/S0304-3975(00)00116-X

Did you mean to say that it should be freely available?

6. In proof theory, a proof of a theorem from a set of axioms is elementary iff the proof does not use concepts from outside of the axioms or the theorem, which technically means that all formulas appearing in the proof are subformulas of the axioms or the theorem. When one uses concepts from outside, one is usually defining new concepts representing complicated formulas and uses lemmas about these concepts (cut rule). By Gentzen's cut-elimination any proof can be made elementary, but the problem is that the size of the proof can grow super-exponentially, i.e. a one page proof can become 2^500/500 pages (assuming each page is around 500 letters). I am not even talking about 300-page proof of FLT. So size of an elementary proof is also important.

Proof theoretic definition of an elementary proof (cut free proof) satisfies 1 and 3. If it is also short, then teaching it shouldn't be hard and therefore it will satisfy 2. And the only problem in finding this short proof is when one needs to find the right instances of terms needed in L\forall and R\exists rules, and that's probably the reason that a short elementary proof would not satisfy 4.