Four-term progressions in Fourier-uniform sets
A set $A \subset \mathbb{Z}/N\mathbb{Z}$ of density $\alpha$ is Fourier uniform if every Fourier coefficient of $1_A - \alpha$ is $o(N)$. Gowers showed that the statement below fails with $100$ replaced by $4.01$, and Deng, Tidor and Zhao improved this to $3 + \frac12 \log_3 22 \approx 4.406$. They also conjectured that for every $N$ some colouring of $\{1, \dots, N\}$ with $N^{o(1)}$ colours has no symmetrically coloured four-term progression $x, x+d, x+2d, x+3d$ (one in which $x, x+3d$ share a colour and $x+d, x+2d$ share a colour), and showed that this would give a negative answer.
Problem. If $A \subset \mathbb{Z}/N\mathbb{Z}$ has density $\alpha$ and is Fourier uniform, must $A$ contain $\gg \alpha^{100} N^2$ four-term arithmetic progressions?
Source: A question of I. Z. Ruzsa; see E. Croot and V. F. Lev, Open problems in additive combinatorics (2007), Problem 3.2. Listed as Problem 13 in B. Green, 100 open problems (version of January 2026).
Imported from people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf.
Classification
- Primary
- CO — Combinatorics
- Secondary
- NT
- Keywords
- arithmetic progressions, counting lemmas, Fourier uniformity, higher-order Fourier analysis
References
@incollection{croot2007lev,
author = {Croot, Ernie and Lev, Vsevolod F.},
title = {Open problems in additive combinatorics},
booktitle = {Additive Combinatorics},
series = {CRM Proceedings and Lecture Notes},
volume = {43},
pages = {207--233},
publisher = {American Mathematical Society},
year = {2007},
doi = {10.1090/crmp/043/10}
}
@article{gowers2020uniform,
author = {Gowers, W. T.},
title = {A uniform set with fewer than expected arithmetic progressions of length 4},
journal = {Acta Mathematica Hungarica},
volume = {161},
number = {2},
pages = {756--767},
year = {2020},
doi = {10.1007/s10474-020-01072-z}
}
@article{deng2025colourings,
author = {Deng, Mingyang and Tidor, Jonathan and Zhao, Yufei},
title = {Uniform sets with few progressions via colourings},
journal = {Mathematical Proceedings of the Cambridge Philosophical Society},
volume = {179},
number = {1},
pages = {79--103},
year = {2025},
doi = {10.1017/S0305004125000106}
}
@misc{shi2026colorings,
author = {Shi, Ruizhe and Dong, Yiqi},
title = {An improved upper bound for colorings without symmetrically colored $k$-term arithmetic progressions},
year = {2026},
eprint = {2607.20752},
archivePrefix = {arXiv}
}
@misc{green100open,
author = {Green, Ben},
title = {100 open problems},
howpublished = {\url{https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf}},
note = {Problem 13; version of January 2026, most recent update December 2025},
year = {2026}
}
Resolution claims
Given a coloring $c$ and an even $k\ge 4$, a nontrivial $k$-term arithmetic progression~($k$-AP) $a,a+d,\ldots,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 …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-29 | Open → Partially resolved | The registry's curators | An Improved Upper Bound for Colorings Without Symmetrically Colored $k$-Term Arithmetic Progressions v1 recorded from arXiv:2607.20752v2. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-01031, "Four-term progressions in Fourier-uniform sets", clopen.solutions.