What is an Elementary Proof?

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.

"