An Improved Lower Bound for Arithmetic Regularity

Abstract

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-\epsilon$ fraction of the cosets, the nontrivial Fourier coefficients are bounded by $\epsilon$, then Green shows that $|G/H|$ is bounded by a tower of twos of height $1/{\epsilon }^3$. He also gives an example showing that a tower of height $\Omega (\log 1/\epsilon )$ is necessary. Here, we give an improved example, showing that a tower of height $\Omega (1/\epsilon )$ is necessary.

Cited by in corpus (4)

• Stable arithmetic regularity in the finite-field model
• Tower-type bounds for Roth's theorem with popular differences
• Quasirandomness in additive groups and hypergraphs
• Induced arithmetic removal for partition-regular patterns of complexity 1