An improved lower bound for arithmetic regularity
An improved lower bound for arithmetic regularity
复制标题
改进的算术正则性下界
DOI：
10.1017/s030500411600013x
复制
发表时间：
2014
影响因子：
0.8
通讯作者：
A. Shapira
中科院分区：
文献类型：
--
作者：
Kaave Hosseini;Shachar Lovett;Guy Moshkovitz;A. Shapira
摘要绿色[GAFA 2005]提出的算术正则性引理是图论中著名的Szemerédi正则性引理的一个类比。证明了对任意阿贝尔群G和任意有界函数f：G → [0，1]，存在一个指数有界的子群H <$G，使得当限制在H的大多数陪集上时，函数f是伪随机的，即它的所有非平凡傅立叶系数都很小。如果我们希望得到，对于陪集的1-ε分数，非平凡傅立叶系数由ε限定，那么绿色表明，|G/H|以高度为1/ε3的二人塔为界。他还举了一个例子，表明塔的高度Ω（log 1/ε）是必要的。在这里，我们给出一个改进的例子，表明一个高度为Ω（1/ε）的塔是必要的。
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.