Recall the poly VDW theorem:
Let p_{1},...,p_{k} ∈ Z[x] such that p_{i}(0)=0. Let c ∈ N. There exists W=W(p_{1},...,p_{_k};c) such that for any ccoloring of {1,...,W} there exists a,d such that a, a+p_{1}(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 densitytype 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_{1},...,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_{1}(d), ..., a+p_{k}(d) are all in A.
 The case where all of the polynomials are linear is often called the ErdosTuran Conjecture. It is still open.
 The following is a subcase that is orthogonal to the ErdosTuran Conj: If Σ_{x ∈ A} 1/x diverges then there exists two elements of A that are a square apart.

Green and Tao
showed that the set of primes have arb. large AP's.
Then
Tao and Ziegler
showed the following:
Let p_{1},...,p_{k} ∈ Z[x] such that p_{i}(0)=0.
There exists a, d such that
a, a+p_{1}(d), ..., a+p_{k}(d) are all primes.
SO the CONJ is true for a particular set of interest.
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_{1},...,p_{k} ∈ Z[x] such that p_{i}(0)=0. Find functions e_{1}(n) and e_{2}(n) (not that far apart) such that e_{1}(n) ≥ e_{2}(n), and the following occurs:For the case of 3AP's the following are known:
 If for almost all n, d_{A}(n) ≥ e_{1}(n) then there exists a,d such that a, p_{1}(d),...,p_{k}(d) ∈ A.
 There exists A such that, for almost all n, d_{A}(n) ≥ e_{2}(n), and there is NO a,d such that a, p_{1}(d),...,p_{k}(d) ∈ A.
 If for almost all n d_{A}(n) ≥ (log log n)^{5}/log n then A has a 3AP. (See this Tom Sanders paper.)
 There exists a set A such that, for almost all n d_{A}(n) ≥ 1/n^{\sqrt(log n)} and A has no 3APs (See Michael Elkin's paper for a slightly better result that I didn't have the energy to typeset.)
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.
Why should it be a Millennium problem?
ReplyDeleteApologies, 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.
Anon Great Question.
ReplyDeleteThe 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 NavierStrokes.
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 SwinnertonDyer Conj, Hodge Conj,
YangMills 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
discussion.
what about P=NP?
ReplyDeleteAH Anon, you misunderstand.
ReplyDelete`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.
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ösTurá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.
ReplyDeleteThere'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.