Source author record

Kaave Hosseini

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

2works

1topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

On the structure of the spectrum of small sets

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 $α\le c$ , where $c \ge 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.

preprint2014arXiv

An Improved Lower Bound for Arithmetic Regularity

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 \to [0,1]$ , there exists a subgroup $H \le 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.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.