## [Computational Complexity] A Seventh Mil. Problem

Expand Messages
• Richard Lipton had a wonderful post asking for a seventh Millennium Prize now that Poincare s conjecture has been solved. I posted a suggestion on his blog but
Message 1 of 1 , Jul 26, 2010
• 0 Attachment
Richard Lipton had a wonderful post asking for a seventh Millennium Prize now that Poincare's conjecture has been solved. I posted a suggestion on his blog but got no comments. I'll expand on it and see if I get any comments here.

HISTORY: The original proof of VDW's theorem , in 1927, yields INSANE (not primitive recursive ) bounds on the VDW numbers. (Shelah (1988) later got primitive recursive bounds and Gowers (2001) got bounds you can actually write down!) Inspired by VDW's proof Erdos and Turan (1936), made two conjectures:
1. If A is a subset of N of positive upper density then A has arbitrarily long arithmetic sequences. Proven by Szemeredi in 1975 (see here for more.)
2. If &Sigmax ∈ A 1/x diverges then A has arbitrarily long arithmetic sequences. (This conjecture implies the first one.)
A proof of either of these yields a proof of VDW theorem. The hope was that it would lead to a proof with better bounds. Szemeredi's proof of the first conjecture did not yield better bounds; however, Gowers proved the first conjecture a different way that did yield better bounds on the VDW numbers.

The second conjecture is still worthwhile since it may yield even better bounds and because it is interesting in its own right. So, I propose the second conjecture of Erdos-Turan as the 7th Millennium problem. (It might need a snazzier name. The Divergence Conjecture? The k-AP Conjecture? Suggestions are welcome!)
1. Greene and Tao have already shown that the primes have arbitrarily large arithmetic progressions.
2. The work that has gone into Szemeredi's theorem and the Greene-Tao theorem spanned many areas of mathematics. Hence this is not just an isolated problem.
3. The problem has been open since 1936. Hence it is a hard problem.
4. Will more connections to other parts of math be made? Is the problem too hard? A NO answer to both of these would make it not that good a problem.
5. The converse to the conjecture is not true. Note the following set:

A = &cupk&isin N {2^k + i : 0 &le i < k }

The set A has arbitrarily long arithmetic sequences but If &Sigmax ∈ A 1/x converges.
6. Is there a plausible condition that characterizes the sets that have arbitrarily long arithmetic sequences?
7. There is already (I think) a 3000 dollar bounty on the second conjecture. So the Clay Math Institute will have to just give 997,000 dollars.

--
Posted By GASARCH to Computational Complexity at 7/26/2010 11:35:00 AM
Your message has been successfully submitted and would be delivered to recipients shortly.