An improved lower bound for arithmetic regularity. (11th March 2016)

• Record Type: Journal Article
• Authors: HOSSEINI, KAAVE; LOVETT, SHACHAR; MOSHKOVITZ, GUY; SHAPIRA, ASAF
• Is Part Of: Mathematical proceedings of the Cambridge Philosophical Society. Volume 161:Part 2(2016:Sep.)
• Page Start: 193
• Page End: 197
• Publication Date: 2016-03-11
• Subjects: Mathematics -- Periodicals; 510.5
• DOI: 10.1017/S030500411600013X
• Languages: English
• ISSNs: 0305-0041

Abstract

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.