# What are bounds on this van der Waerden-esque problem?

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 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.

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.
• very nice! did you mean to write $4xp^3+2yp^2+zp$? Dec 15, 2021 at 18:28