## 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
their intrinsic importance, that will help the
discussion.