What is an
Elementary Proof?
Different things in different contexts.

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''.)

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.)
)

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 nonelementary proofs rather
than follow the elementary one.

An Elementary proof is one that some bright high school students can come up with
during a High School Math Competition.

The following is elementary: Show that any for any 3coloring of the natural numbers
there exists x,y that are the same color such that xy is a square.

The following is probably not elementary: Show that any for any 4coloring of the natural numbers
there exists x,y that are the same color such that xy 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.

The following is elementary: Show that if n is a power of 2 then if there are 2n1 integers
then some n of them sum to 0 mod n.

The following is probably not elementary: Show that if n is any integer then if there are 2n1 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.

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.

Posted By GASARCH to
Computational Complexity at 2/09/2010 03:24:00 PM