2015/04/04 by Hosseini, Kaave, Lovett, Shachar
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1504.01059
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|α whenever α≤ c, where c ≥ 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 in the spectrum, γ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', such that the sumset of the spectrum of A' has bounded size. Our results apply to sets of size |A| = |G|α for any constant α>0, and even in some sub-constant regime.