I was reading a problem list by Erdos ([doi](https://doi.org/10.1111/j.1749-6632.1989.tb16392.x)). 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.



What are bounds on this van der Waerden-esque problem?
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.


