Paper detail

An Improved Lower Bound for Arithmetic Regularity

The arithmetic regularity lemma due to Green [GAFA 2005] is an analogue of the famous Szemer{é}di regularity lemma in graph theory. It shows that for any abelian group $G$ and any bounded function $f:G \to [0,1]$, there exists a subgroup $H \le G$ of bounded index such that, when restricted to most cosets of $H$, the function $f$ is pseudorandom in the sense that all its nontrivial Fourier coefficients are small. Quantitatively, if one wishes to obtain that for $1-ε$ fraction of the cosets, the nontrivial Fourier coefficients are bounded by $ε$, then Green shows that $|G/H|$ is bounded by a tower of twos of height $1/ε^3$. He also gives an example showing that a tower of height $Ω(\log 1/ε)$ is necessary. Here, we give an improved example, showing that a tower of height $Ω(1/ε)$ is necessary.