I was reading a problem list by Erdos (doi). On page 144 (which is the 12-th page of the pdf), a problem stuck out to me.

For positive integer $n$, let $h(n)$ be the smallest $k$ such that $[n] := \{1,\dots,n\}$ can be partitioned into $k$ parts $A_1,\dots,A_k$ so that $A_i \cup A_j$ lacks arithmetic progressions of length four for each $i,j \in [k]$. I was wondering if this quantity $h(n)$ has been studied, and if so what bounds are known.

Observations: A simple upper bound is the following. Let $c:[k] \to [n]$ be a coloring (which obviously corresponds to a partition of $[n]$ into $k$ parts). If there exists a monochromatic arithmetic progression of length 3, $P = \{n,n+d,n+2d\} \subset [1,2n/3]$, then we have $d<n/3$ implying $n+3d \in [n]$ meaning there exists an arithmetic progression of length four.

Hence we must have $W_{h(n)}(3) > 2n/3$. I am not too familiar with the bounds for the multicolor van der Waerden numbers, but by Bloom and Sisak's density result this implies $h(n) \gg \log^{1+c}(n)$ for some $c>0$.

Also, I'm pretty sure a bound of $h(n)\ll n^{1-\epsilon}$ for some $\epsilon > 0$ should follow by appropriately modifying the work of Tomon and Pach on rainbow arithmetic progressions.


1 Answer 1


The bound $h(n) \ll n^{2/3}$ is achievable by the following twisted cubic construction: Let $X=\mathbb{F}_p^3$ ($p\geq5$) and $Y_{ij}=\{(t,t^2+i,t^3+j): t \in \mathbb{F}_p\}$. The sets $Y_{ij}$ partition $X$ and $Y_{ij} \cup Y_{kl}$ never contains any 4-AP.

If there were a 4-AP, $\{a,b,c,d\}$, there must be two elements belonging to $Y_{ij}$ and two belonging to $Y_{kl}$, since none of $Y_{ij}$ contains a 3-AP. We may assume $\{a,b\} \in Y_{ij}$ and $\{c,d\} \in Y_{kl}$. In this case, the vectors $a-b$ and $c-d$ would be parallel, but a twisted cubic does not contain any pair of secants that are parallel.

We can "project" $\mathbb{F}_p^3$ on $\mathbb{Z}$ by sending $(a,b,c)$ (taking values in $0 ... p-1$) to $4ap^2+2bp+c$. In this projection, if a subset of $\mathbb{F}_p^3$ does not contain a 4-AP, the image would not contain a 4-AP either. So we can project the $Y_{ij}$s on $\mathbb Z$ without creating any 4-APs. By translating the projected $Y_{ij}$s by $4xp^3+2yp^2+zp$ $(x,y,z \in \{0,1\})$ and renaming the variables, we can partition $0 ... 8p^3-1$ by $8p^2$ sets.

Thus the bound $h(n) \ll n^{2/3}$ is achievable.

  • 1
    $\begingroup$ very nice! did you mean to write $4xp^3+2yp^2+zp$? $\endgroup$ Dec 15, 2021 at 18:28
  • $\begingroup$ Yes, it's corrected. $\endgroup$ Dec 16, 2021 at 5:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.