2026/07/22 by Ruizhe Shi, Yiqi Dong
Computer Science · Mathematics · #cs.DM #math.CO
7 pages, comments are welcome. Revised version adds several references
arxiv created 2026/07/28 · arxiv updated 2026/07/30
Given a coloring c and an even k≥ 4, a nontrivial k-term arithmetic progression~(k-AP) a,a+d,…,a+(k-1)d is called symmetrically colored if c(a+(i-1)d)=c(a+(k-i)d), ∀ i∈[k/2]. Deng, Tidor, and Zhao asked whether [N] admits a coloring with No(1) colors and no such 4-APs, and gave an O(N^log223)-coloring of [N]. We give an Ok(p)-coloring of \mathbb Z/pk2/4\mathbb Z without such k-APs for every even k≥ 4 and every prime p>k, and hence an Ok(N4/k2)-coloring of [N], improving the exponent in the upper bound for 4-APs from log223 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)≤ N1/4+o(1) in Erdős's Problem~160 on coloring every nontrivial 4-AP with at least three colors. This result also yields ρ4(α)=Oε(α5-ε) for every ε>0, improving the bound toward Ruzsa's question. Our result for k-APs disproves Gowers' conjectured lower bound for all even k≥6 for the first time.