Fix $\alpha>0$. Does there exist $\epsilon = \epsilon(\alpha)>0$ such that if $S\subset [N]:=\{1,\dots,N\}$ has $\ge \alpha N$ elements, then for any function $f:S\to [0,1]$, there exist some arithmetic progression $P=\{x<y<z\}\subset S$ where $f(x)+f(z)-2f(y)\le O(N^{-\epsilon})$?
Behrend's construction tells us that $\epsilon(\alpha)\le O(\frac{1}{\log 1/\alpha})$ (this is done by passing to a set $S$ of density $\approx 2^{-D}$ which is Freimann isomorphic to a $O(N^{-1/D})$-separated subset of $\Bbb{R}^D$, and then evaluating the $2$-norm). So $\epsilon(\alpha)\to 0$ as $\alpha\to 0$. But I don't know how to rule out the possibility that $\epsilon(\alpha)=0$ holds.
Remarks:
A rather general way to view things is as follows:
Given a set $S$ and a system of triples $\mathcal{T}\subset S^3$, we define the "inequality-chromatic number" of $\mathcal{T}$, $\chi_<(\mathcal{T})$ to be the smallest $r$ such that there is a coloring $C:S \to [r]$ where for $(x,y,z)\in \mathcal{T}$, we have $C(x)+C(z)>2C(y)$.
If there exists $f:S\to [0,1]$ where every 3-AP (arithmetic progression of length three) $P=\{x <y<z\}$ satisfies $f(x)+f(z)-2f(y)> \delta$, then taking $\mathcal{T} = \mathcal{T}_{3AP}(S) $ to be the set of 3-APs $P \subset S$ (with entries ordered from smallest to greatest), then we must have that $\chi_<(\mathcal{T}) \ll 1/\delta$ (basically we split $[0,1]$ into intervals of length $O(1/\delta)$ and use $f$ to create a coloring $C$, as "rounding" can't influence things much).
Using this perspective, I can show that if $S$ contains an arithmetic progression of length $k$, then $\chi_<(\mathcal{T}_{3AP}(S))\gg k^2$. Whence one can see that naively applying the ideas from Behrend's construction can't do better here (since the set $S$ you pass to here basically looks like a generalized arithmetic progression of rank $D =\log(1/\alpha)$, giving progressions of length $\approx N^{1/D}$).
But if $S\subset [N]$ is a random dense subset, then there are not any progressions of polynomial length. Instead one would need a saturation result or something.
