Monday, November 23, 2009

An undervalued Math Problem

As most of you know there are 7 problems worth $1,000,000 (see here). It may be just 6 since Poincare's conjecture has probably been solved. Why are these problems worth that much money? There are other open problems that are worth far less money. What determines how much money a problem is worth?

When Erdos offered money for a problem (from 10 to 3000 dollars) I suspect that the amount of money depended on (1) how hard Erdos thought the problem was, (2) how much Erdos cared about the problem, (3) how much money Erdos had when he offered the prize, and (4) inflation. (If anyone can find a pointer to the list of open Erdos Problems please comment and I'll add it here.)

Here is a problem that I have heard is hard and deep, yet it is only worth $3000 (Erdos proposed it). I think that it should be worth more.

BACKGROUND: Szemeredi's theorem: Let A&sube N. If the limit as n goes to infinity of size(A &cap {1,...,n})/n is bounded below by a positive constant then A has arbitrarily long arithmetic sequences. Intuition: if a set is large then it has arb long arith seqs. The CONJECTURE below uses a diff notion of large.

CONJECTURE: Let A&sube N. If &suma&isin A 1/a div

KNOWN: Its known that if A is the set of all primes (note that &suma&isin A 1/a diverges) then A has arbitrarily large arithmetic progressions. Nothing else is known! The conjecture for 3-AP's isn't even known!

Is this a good problem? If it is solved quickly (very unlikely) than NO. If absolutely no progress is made on it and no interesting mathematics comes out of the attempts than NO. It has to be just right.


  1. the available space for the comment is not sufficient to contain a full proof for this conjecture..

  2. Neither money nor politics should mix with mathematics.

  3. "Neither money nor politics should mix with mathematics."

    Yes! Also, I should have a pony.

  4. There are a few lists of Erdős problems, but I don't know if anyone's compiled a comprehensive list. I've read that Erdős liked to throw out problems and prizes offhandedly, in talks and lectures, so a few might not be well-documented.

    Fan Chung has compiled a list of Erdős problems in graph theory:

    Here's another partial list:

    It's interesting to ask whether the practice of offering cash prizes for problems has proven effective in getting problems solved more quickly.

    In the case of Erdős, I imagine it's the prestige (and pleasure) of cracking an Erdős problem that draws people in, not the cash. I don't know if small bounties by someone less prolific would prove as attractive!

  5. If it is solved quickly (very unlikely) then NO.

    In general important insights do not come by easily, but you should not confuse correlation with causality.

    For example, Frey's conjecture on Fermat's Last Theorem was based on an embarrasingly simple observation. It was surprising no one else noticed it before, but it was the key link connecting FLT to a rich area of mathematics.

  6. To be fair, I'm not sure that Erdos knew how much harder that problem was than, for instance, Szemeredi's theorem. Glancing at the history, it seems to have been conjectured roughly contemporaneously with Szemeredi's proof, and I suspect that part of the reason the bounty's so high is that Erdos saw that the "incremental" arguments of Roth and Szemeredi wouldn't generalize to this case, and so the prize was offered to find different approaches to arithmetic Ramsey theorems. But even Furstenberg's ergodic methods aren't nearly strong enough to approach this conjecture -- indeed, I think Green and Tao's transference principle is the only thing we have (so far!) that allows us to do density Ramsey theory in a set of density zero.

  7. I solved all problems but feel a little too tired and selfish to share them here.

  8. I think that when the Clay problems were chosen - the problem was not considered important in the "Hamming sense" - let me quote " `important problem' must be phrased carefully. The three outstanding problems in physics, in a certain sense, were never worked on while I was at Bell Labs...We didn't work on (1) time travel, (2) teleportation, and (3) antigravity. They are not important problems
    because we do not have an attack". Things have change after Green/Tao and the transference principle.

  9. If the conjecture is true, it would imply:

    Whenever both A and B lack arbitrarily large A.P.s, then so does their union.

    This would generalize Gleason's theorem (consider the contrapositive, and apply to a finite union which is all of N) but somehow, it doesn't seem particularly plausible.