## [Computational Complexity] What is an Elementary Proof?

Expand Messages
• 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.
Message 1 of 1 , Feb 9, 2010
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.

--
Posted By GASARCH to Computational Complexity at 2/09/2010 03:24:00 PM
Your message has been successfully submitted and would be delivered to recipients shortly.