Article contents
An improved lower bound for arithmetic regularity
Published online by Cambridge University Press: 11 March 2016
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 → [0, 1], there exists a subgroup H ⩽ 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.
- Type
- Research Article
- Information
- Mathematical Proceedings of the Cambridge Philosophical Society , Volume 161 , Issue 2 , September 2016 , pp. 193 - 197
- Copyright
- Copyright © Cambridge Philosophical Society 2016
References
REFERENCES
- 3
- Cited by