## [Computational Complexity] Ridiculously hard proof of easy theorem

Expand Messages
• Justin Kruskal is a High School Student working with me on VDW stuff (of course). The following conversation happened recently. BILL: Justin, you ve seen a
Message 1 of 1 , Aug 13, 2008
Justin Kruskal is a High School Student working with me on VDW stuff (of course). The following conversation happened recently.

BILL: Justin, you've seen a proof of VDW's theorem, but there are easier things you haven't seen and should. Can you prove that the number of primes is infinite?

JUSTIN: Thats easy.

BILL: Good. How does it go?

JUSTIN: By the Green-Tao Theorem there are arbitrarily long arithmetic sequences of primes. Hence there are an infinite number of primes.

What to make of this?
1. Justin does not know how to proof the Green-Tao theorem (neither do I). However, if the proof does not use the fact that there are an infininte number of primes, then Justin's proof is valid. READERS: does anyone know, does it use the infinitude of the primes?
2. Justin now knows the standard proof. However, he should also learn that, at the level of math where he is at, you should be able to prove everything you use.
3. When does one start using theorems whose proofs one does not know? In research this is common. For basic coursework it should be rare.

--
Posted By GASARCH to Computational Complexity at 8/13/2008 07:33:00 AM
Your message has been successfully submitted and would be delivered to recipients shortly.