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 p₁,...,p_k ∈ Z[x] such that p_i(0)=0. Let c ∈ N. There exists W=W(p₁,...,p_{_k};c) such that for any c-coloring of {1,...,W} there exists a,d such that a, a+p₁(d), ..., a+p_k(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 p₁,...,p_k ∈ Z[x] such that p_i(0)=0. If Σ_{x ∈ A} 1/x diverges then there exists a,d such that

a, a+p₁(d), ..., a+p_k(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 p₁,...,p_k ∈ Z[x] such that p_i(0)=0. There exists a, d such that
   
   a, a+p₁(d), ..., a+p_k(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 d_A(n) =|A ∩ {1,...,n}|/n. The lim sup_{n → ∞} d_A(n) is the upper positive density. We will be interested in the function d_A(n).

QUESTION: Let p₁,...,p_k ∈ Z[x] such that p_i(0)=0. Find functions e₁(n) and e₂(n) (not that far apart) such that e₁(n) ≥ e₂(n), and the following occurs:

1. If for almost all n, d_A(n) ≥ e₁(n) then there exists a,d such that a, p₁(d),...,p_k(d) ∈ A.
2. There exists A such that, for almost all n, d_A(n) ≥ e₂(n), and there is NO a,d such that a, p₁(d),...,p_k(d) ∈ A.

For the case of 3-AP's the following are known:

1. If for almost all n d_A(n) ≥ (log log n)⁵/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 d_A(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.