Computational Complexity

Monday, July 26, 2010

 
A Seventh Mil. Problem

Posted by GASARCH

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 &Sigma_{x ∈ 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 = &cup_{k&isin N} {2^k + i : 0 &le i < k }
   
   The set A has arbitrarily long arithmetic sequences but If &Sigma_{x ∈ 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.

11:35 AM # 3 comments

1.  Anonymous says:  
   
   how about finding the probability that nobody will ever find proofs for any one of those conjectures, not now, not ever?
   

   10:05 PM, July 26, 2010

2.  Anonymous says:  
   
   I think it's a great problem for
   generating public attention,
   as it is easy to understand
   even for non mathematicians.
   
   As the Tao-Green-Theorem was
   widley recognized as a big
   breaktrough in mathematics,
   i would like to ask, if there are
   other sets where a proof of the
   special case would be similar
   important.
   
   This could be an advantage for
   choosing the conjecture, as even
   if the main problem is to hard,
   many impotant special cases
   would benefit from the status of a
   millenium problem.
   
   I think this might lower the risk of
   working on such a problem and
   making no progress whatsoever.
   

   9:50 AM, July 27, 2010

3.  V. Deolalikar says:  
   
   Now we need 2 new problems!
   And i'll get $1.200.000!
   Just awesome
   

   4:20 PM, August 12, 2010

Comment Feeds: This Post All