Wednesday, September 28, 2011

A candidate for a new Millenium Problem

In a prior post I wrote that the Erdos-Turan Conjecture should be a Millennium problem. Today I am going to (1) suggest a generalization of the Erdos-Turan Conjecture should be a Millennium problem instead, and also suggest (2) a far harder problem be another candidate. For some history see here. (This is an excerpt from my still-being-written book on VDW stuff- so if you find a mistake or suggestions please comment or email me.)

Recall the poly VDW theorem:
Let p1,...,pk ∈ Z[x] such that pi(0)=0. Let c ∈ N. There exists W=W(p1,...,p_k;c) such that for any c-coloring of {1,...,W} there exists a,d such that a, a+p1(d), ..., a+pk(d) are all the same color.
Much like VDW's theorem was before Gowers result, (1) there is a proof that gives bounds that are not primitive recursive (Walters proof) (2) there is a density-type theorem that does not give good bounds, (3) there is a proof by Shelah that gives primitive recursive bounds, but they are still quite large.

We make the following conjecture which we hope will lead to better bounds on the poly VDW numbers.
CONJ: Let p1,...,pk ∈ Z[x] such that pi(0)=0. If Σx ∈ A 1/x diverges then there exists a,d such that

a, a+p1(d), ..., a+pk(d) are all in A.
  1. The case where all of the polynomials are linear is often called the Erdos-Turan Conjecture. It is still open.
  2. The following is a subcase that is orthogonal to the Erdos-Turan Conj: If Σx ∈ A 1/x diverges then there exists two elements of A that are a square apart.
  3. Green and Tao showed that the set of primes have arb. large AP's. Then Tao and Ziegler showed the following: Let p1,...,pk ∈ Z[x] such that pi(0)=0. There exists a, d such that

    a, a+p1(d), ..., a+pk(d) are all primes.

    SO the CONJ is true for a particular set of interest.
We also pose a question which is more interesting but likely much harder:
If A is a set then let dA(n) =|A ∩ {1,...,n}|/n. The lim supn → ∞ dA(n) is the upper positive density. We will be interested in the function dA(n).
QUESTION: Let p1,...,pk ∈ Z[x] such that pi(0)=0. Find functions e1(n) and e2(n) (not that far apart) such that e1(n) ≥ e2(n), and the following occurs:
  1. If for almost all n, dA(n) ≥ e1(n) then there exists a,d such that a, p1(d),...,pk(d) ∈ A.
  2. There exists A such that, for almost all n, dA(n) ≥ e2(n), and there is NO a,d such that a, p1(d),...,pk(d) ∈ A.
For the case of 3-AP's the following are known:
  1. If for almost all n dA(n) ≥ (log log n)5/log n then A has a 3-AP. (See this Tom Sanders paper.)
  2. There exists a set A such that, for almost all n dA(n) ≥ 1/n\sqrt(log n) and A has no 3-APs (See Michael Elkin's paper for a slightly better result that I didn't have the energy to typeset.)
These two functions are NOT close together. So even in the case of 3-AP's we do not know the answer. I want to know the e1,e2 for ALL finite sets of polynomials with 0 constant term. We've got our work cut out for us.

It is my hope that progress on the question will lead to better bounds on some poly VDW numbers. A similar question DID lead to better bounds on the VDW numbers.


  1. Why should it be a Millennium problem?
    Apologies, but it looks like a very hard problem which has perhaps some interesting applications, but it doesn't seem to be so groundbreaking as other Millennium problems.

  2. Anon- Great Question.
    The problems I propose will involve LOTS of diff areas of mathematics (as did their analogs for VDW's theorem)
    and this is certainly a PLUS.

    As to the problems INTRINSIC worth, this is indeed
    debatable. Is it like FLT- LOTS of nice things come out of it but FLT is not, in and of itself, that interesting.
    Or is it like P=?NP--- which is asking a very
    important question? How do my problems compare to the
    other Mil Prize Problems in this regard?

    1) My problem is certainly LESS intrinsically important than P=?NP and Navier-Strokes.
    These deal with important problems motivated by
    the real real world.

    2) Poincare's Conjecture (now Perelman's theorem)
    and Riemann hypothesis--- These deal with objects
    that people in math care about- primes and surfaces.
    Do they have real world motivations as well?
    Are Primes actually important? Harder to argue for
    these, though I think most mathematicians would agree
    that both are MORE intrinsically important than
    my problems.

    3) Birch and Swinnerton-Dyer Conj, Hodge Conj,
    Yang-Mills Theory, I do not pretend to know
    about, but if a reader wants to fill us in on
    their intrinsic importance, that will help the

  3. AH- Anon, you misunderstand.
    `The Millennuim problems' are a real set of problems
    and P =? NP is already one of them.

    The Poincare Conjecture was one of them and it was solved hence the question has been raised (I first saw it on
    Godel's Last Letter Blog) of if there is a problem to
    replace it.

  4. If I had to nominate a problem in this general area as a millennium problem, then my choice would be finding upper and lower bounds for Szemerédi's theorem that were broadly comparable. I feel that the original Erdös-Turán problem isn't suitable because it focuses attention on what may well be the wrong bound (roughly n/log n). And I also think that if the polynomial version of the problem is ever solved, the real conceptual leap forward, which is what I would want to reward with a million dollars, will have taken place with the linear case.

    There's a reasonable chance that this wouldn't make too much difference, since the way to beat the n/log n bound might well turn out to be "to understand properly what is going on" -- which would then lead to a proof that gave a bound of the correct type. But in the case of Roth's theorem, I think there is also a chance that someone will at some point manage, thanks to a heroic effort (similar to what Bateman and Katz recently did in the F_3^n case), to get just beyond the n/log n bound. And I also think that the correct bound for this problem is much better.