An improved lower bound for arithmetic regularity

DOI10.1017/S030500411600013XMaRDI QIDQ5360402zbMATH OpenOpenAlexFDO

Authors Kaave Hosseini, Shachar Lovett, Guy Moshkovitz, Asaf Shapira

Publication date 28 September 2017

Published in Mathematical Proceedings of the Cambridge Philosophical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1405.4409

Mathematics Subject Classification ID

Extremal set theory (05D05) Arithmetic combinatorics; higher degree uniformity (11B30) Finite abelian groups (20K01)

Abstract: The arithmetic regularity lemma due to Green [GAFA 2005] is an analogue of the famous Szemer{'e}di regularity lemma in graph theory. It shows that for any abelian group $G$ and any bounded function $f:Go[0,1]$, there exists a subgroup $HleG$ 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/epsilo{n}^3$. He also gives an example showing that a tower of height $Omega(log1/epsilon)$ is necessary. Here, we give an improved example, showing that a tower of height $Omega(1/epsilon)$ is necessary.

Recommendations

• Popular progression differences in vector spaces
• Lower bounds of tower type for Szemerédi's uniformity lemma
• A Szemerédi-type regularity lemma in abelian groups, with applications
• Stable arithmetic regularity in the finite field model
• A tight lower bound for Szemerédi's regularity lemma

Cites work

• A short proof of Gowers' lower bound for the regularity lemma
• A Szemerédi-type regularity lemma in abelian groups, with applications
• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• Lower bounds of tower type for Szemerédi's uniformity lemma

Cited in

(6)

• A lower bound for range enclosure in interval arithmetic
• Stable arithmetic regularity in the finite field model
• Quantitative structure of stable sets in arbitrary finite groups
• Quantitative structure of stable sets in finite abelian groups
• Tower-type bounds for Roth's theorem with popular differences
• Induced arithmetic removal for partition-regular patterns of complexity 1

This page was built for publication: An improved lower bound for arithmetic regularity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5360402)