2
$\begingroup$

Van der Waerden's theorem gives us a finite number $W(k,r)$ defined as the smallest positive integer $N$ such that for any $n\geq N$, any $r$-coloring of $[n]=\{1,\dots,n\}$ admits a monochromatic $k$-AP. We can ask the same question except with $[n]$ replaced by $\mathbb{Z}/n\mathbb{Z}$, calling the answer the "cyclic van der Waerden number" and denoting it by $W_c(k,r)$ (seems to be first mentioned in Burkert and Johnson, 2011). An immediate bound is that $W_c(k,r)\leq W(k,r)$, so we know that $W_c$ is finite.

Is there any progress on determining the values of $W_c(k,r)$ that is not just "check every number not greater than $W(k,r)$"? Even if the exact values are not known for larger $k$ and $r$, are there any improved asymptotics on $W_c$ that are better than the Gowers bound for $W$? My quick literature search seems to only produce the Burkert and Johnson paper and a single other one (Grier, 2012) which computes $W_c(3,2)$ but nothing else.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

$W(k,r)\le W_c(k,2r)$ follows from taking an $r$-coloring of $[W(k,r)]$ that has no $k$-AP, and adding 'r' to the colors of the first $W(k,r)/2$ numbers to obtain a $2r$-coloring that has no circular $k$-AP.
Since the best bound for $W(k,r)$ is about $2^{2^{r^{2^{2^k}}}}$, any better bound for $W_c(k,r)$ would improve this as well.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Why the constructed $2r$-coloring has no circular $k$-AP? $\endgroup$
    – Max Alekseyev
    Commented Sep 12, 2020 at 12:40
  • $\begingroup$ To give an example: If $k=3$ and $r=2$, then 12122121 becomes 34342121. A circular AP would need to make a small ($<W(k,r)$) jump and a big ($>W(k,r)$) jump. $\endgroup$
    – domotorp
    Commented Sep 12, 2020 at 13:41
  • $\begingroup$ I'm still not convinced. Can you add a proof for the general case? $\endgroup$
    – Max Alekseyev
    Commented Sep 12, 2020 at 14:01
  • $\begingroup$ Case 1: the circular AP's difference is a positive number $<W(k,r)/2$. Case 2: the circular AP's difference is a negative number $>W(k,r)/2$. In both cases the circular AP is just a regular (non-circular) AP, as otherwise it would change colors. $\endgroup$
    – domotorp
    Commented Sep 12, 2020 at 19:49
  • $\begingroup$ Thanks, I see now. The only question remains - what if $W(k,r)$ is odd? $\endgroup$
    – Max Alekseyev
    Commented Sep 12, 2020 at 21:05

You must log in to answer this question.

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