1
$\begingroup$

Let $P\subset \Bbb{Z}[X]$ be a finite set of polynomials with constant-term zero. Then, polynomial vdW says:

For eacg finite $r$, there exists some $N=N(P,r)$, such that every $r$-coloring $C:\{1,\dots,N\}\to \{1,\dots,r\}$ of the first $N$ naturals, we can find integers $n,d>0$ such that $C(n+p(d)) = C(n)$ for all $p\in P$ (where the coloring is defined for each of these inputs).

For general sets of polynomials $P$, we have rather poor upper bounds for $N(P,r)$ as $r$ grows (we just know it is primitive-recursive, by Shelah). But for various special cases, like if $P$ is a bunch of monomials of the same degree, then we have double-exponential bounds $N\le \exp(\exp(r^{O_P(1)}))$, which matches our knowledge for the standard van der Waerden problem.

I was wondering, what are some explicit examples of sets $P$ where we don't know good bounds??

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ I believe e.g. $n$, $n+d$, $n+2d$, $n+d^2$ is an example. There is a path which in theory may lead to e.g. doubly exponential bounds, but this has not been done. $\endgroup$
    – Thomas Bloom
    Commented Aug 12, 2023 at 12:14

1 Answer 1

Reset to default
2
$\begingroup$

Isn't this paper the most up to date? I believe the introduction covers all of the relevant literature.

"Proving a fully general quantitative polynomial Szemerédi theorem remains a very challenging open problem, and effective bounds for sets lacking polynomial progressions of complexity at least one where the polynomials $P_1, \cdots, P_m$ are not homogeneous of the same degree are unknown in the integer setting"

Improve this answer
$\endgroup$
4
  • $\begingroup$ I'm not sure why the OP never reacted to this. It seems very relevant! +1 $\endgroup$
    – David White
    Commented Jan 3 at 17:54
  • $\begingroup$ I haven't been on MO much lately, but yes this is a good answer. of course, this is about density results and not colorings, however that is typical in additive literature... $\endgroup$
    – Zach Hunter
    Commented Jan 4 at 18:47
  • $\begingroup$ When it comes to polynomial Szemeredi, there are no better bounds known for coloring than for density, except in cases where the only bounds for density are from Bergelson-Leibman and the bounds for the coloring versions are then just from Shelah, Walters, etc. $\endgroup$
    – Ryan Alweiss
    Commented Jan 4 at 21:04
  • $\begingroup$ yeah, hopefully that changes. $\endgroup$
    – Zach Hunter
    Commented Jan 5 at 2:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .