Monday, July 26, 2010

A Seventh Mil. Problem

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.


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

  2. 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

    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.

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