On the structure of the spectrum of small sets

详细信息    查看全文

• 作者：Kaave Hosseini¹ ; ^{skhossei@ucsd.edu} ; Shachar Lovett¹ ; ^{slovett@ucsd.edu}
• 关键词：Fourier spectrum ; Sum set ; Doubling constant
• 刊名：Journal of Combinatorial Theory, Series A
• 出版年：2017
• 出版时间：May 2017
• 年：2017
• 卷：148
• 期：Complete
• 页码：1-14
• 全文大小：344 K
• 卷排序：148

文摘

Let G be a finite Abelian group and A a subset of G. The spectrum of A   is the set of its large Fourier coefficients. Known combinatorial results on the structure of spectrum, such as Chang's theorem, become trivial in the regime |A|=|G|α|A|=|G|α whenever α≤cα≤c, where c≥1/2c≥1/2 is some absolute constant. On the other hand, there are statistical results, which apply only to a noticeable fraction of the elements, which give nontrivial bounds even to much smaller sets. One such theorem (due to Bourgain) goes as follows. For a noticeable fraction of pairs γ1,γ2γ1,γ2 in the spectrum, γ1+γ2γ1+γ2 belongs to the spectrum of the same set with a smaller threshold. Here we show that this result can be made combinatorial by restricting to a large subset. That is, we show that for any set A   there exists a large subset A′A′, such that the sumset of the spectrum of A′A′ has bounded size. Our results apply to sets of size |A|=|G|α|A|=|G|α for any constant α>0α>0, and even in some sub-constant regime.