An Improved Upper Bound for Colorings Without Symmetrically Colored $k$-Term Arithmetic Progressions

Abstract

Given a coloring $c$ and an even $k\ge 4$, a nontrivial $k$-term arithmetic progression~($k$-AP) $a,a+d,\dots ,a+(k-1)d$ is called symmetrically colored if $c(a+(i-1)d)=c(a+(k-i)d)$, $\forall i\in [k/2]$. Deng, Tidor, and Zhao asked whether $[N]$ admits a coloring with $N^{o(1)}$ colors and no such 4-APs, and gave an $O(N^{{\log }_{22}3})$-coloring of $[N]$. We give an $O_k(p)$-coloring of $\mathbb{Z}/p^{k^2/4}\mathbb{Z}$ without such $k$-APs for every even $k\ge 4$ and every prime $p>k$, and hence an $O_k(N^{4/k^2})$-coloring of $[N]$, improving the exponent in the upper bound for $4$-APs from ${\log }_{22}3$ to $1/4$. The construction combines a carry-control coloring of base-$p$ digits with a layered field norm mapping. Together with Behrend-style product colorings, our result for $4$-APs gives $h(N)\le N^{1/4+o(1)}$ in Erdős's Problem~160 on coloring every nontrivial 4-AP with at least three colors. This result also yields $\ddot{I}{}_4(\hat{I}\pm )=O_{\epsilon }(\hat{I}{\pm }^{5-\epsilon })$ for every $\epsilon >0$, improving the bound toward Ruzsa's question. Our result for $k$-APs disproves Gowers' conjectured lower bound for all even $k\ge 6$ for the first time.

7 pages, comments are welcome. Revised version adds several references